编译原理怎么判断文法

A. 编译原理怎么判断是否为slr文法

LL(1)就是向前只搜索1个符号,即与FIRST()匹配,如果FIRST为空则还要考虑FELLOW.
LR需要构造一张LR分析表,此表用于当面临输入字符时,将它移进,规约（即自下而上分析思想）,接受还是出错.
LR(0)找出句柄前缀,构造分析表,然后根据输入符号进行规约.
SLR(1)使用LR(0)时若有冲突,不知道规约,移进,活移进哪一个,所以需要向前搜索,则只把有问题的地方向前搜索一次.
LR(1)1.在每个项目中增加搜索符.2.举个列子如有A->α.Bβ,则还需将B的规则也加入.
LALR(1)就是假如两个产生式集相同则将它们合并为一个,几合并同心集.

B. 编译原理文法

编译原理文法的概念为：每一种自然语言或者是编程语言都需要文法来描述，文法相当于语言学的语义分析，即分析每一句话所表示的含义，编译器需要利用文法来完成其语法分析和语义分析。

字母表是元素的非空有穷集合，字母表中的元素称之为符号，因此，字母表也称之为符号集。例如C语言中的字母表由字母、数字、关键字等组成。

符号串，就是由符号集中的元素组成的序列。例如，给定符号集a、b、c，那么abc、abb、ac就是由该符号集组成的符号串。一个文法中，含有一个，或多个产生式，产生式，描述了将终结符集合和非终结符集合组合成串的方法。

C. 编译原理中，形式语言里怎么区分2型文法与3型文法

二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文无关文法，表现在产生式上就是产生式的左部只有一个非终结符；3型文法从广义上讲包括左线形文法、右线形文法和正规文法
。
B、左线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最左端。
C、右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端
。
D、正规文法是右线形文法的一个子集，其产生式右部只有三种情况：
1）空串
2）只有一个终结符
3）只有一个终结符后接一个非终结符
E、所有的3型文法都是2型文法。

D. 编译原理实现判断是不是一个文法的句子

构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。

E. 编译原理 文法类型

    0型文法(Type-0 Grammar)

    1型文法(Type-1 Grammar)

    2型文法(Type-2 Grammar)

    3型文法(Type-3 Grammar)

无限制文法(Unrestricted Grammar) /短语结构文法(Phrase Structure Grammar, PSG )

∀α → β∈P， α中至少包含1个非终结符

0型语言

由0型文法G生成的语言L(G )

上下文有关文法(Context-Sensitive Grammar , CSG )

∀α → β∈P，｜α｜≤｜β｜

产生式的一般形式： α1Aα2 → α1βα2 ( β≠ε )

上下文有关语言（1型语言）

由上下文有关文法(1型文法) G生成的语言L(G )

上下文无关文法(Context-Free Grammar, CFG )

∀α → β∈P，α ∈ VN

产生式的一般形式：A→β

上下文无关语言（2型语言）

由上下文无关文法(2型文法) G生成的语言L(G )

正则文法(Regular Grammar, RG )

右线性(Right Linear)文法： A→wB 或 A→w

左线性(Left Linear) 文法： A→Bw 或 A→w

左线性文法和右线性文法都称为正则文法

0型文法：α中至少包含1个非终结符

1型文法（CSG） ：｜α｜≤｜β｜

2型文法（CFG） ：α ∈ VN

3型文法（RG）：A→wB 或 A→w (A→Bw 或A→w)

0型文法包含1型文法，1型文法包含2型文法，2型文法包含3型文法

F. 四种文法的类型(编译原理)

乔姆斯基（Chomsky）按产生式的类型把文法分为四种类型：0、1、2、3型文法。

*在下文中的产生式中，箭头左边的大写字母为严格的非终结符，而其左边的小写字母不严格要求为非终结符，如[0型文法]中的第2条产生式。

【0型文法】

产生式形式：α→β

要求：箭头左边的α 至少 含有 一个非终结符 ， 其余 不加任何限制

    例如，G：C→AaB

                     aA→a

                     B→b|Bb

【1型文法】

产生式形式：α→β

要求： |α|≤|β| (产生式左端的长度<=右端的长度)，S→ε除外。

例如G： C→aAB

               aA→aBa

               B→b|Bb 

【2型文法】(上下文无关文法)

产生式形式：A→β，A∈VN(终结符) ，β∈V *(VN∪VT，即可为终结符也可为非终结符) 

说明：当以β替换A时，与A的上下文环境无关；

          大部分程序设计语言近似于2型文法。

【3型文法】(正规文法 / 右线性文法)

产生式形式：A→a，A→aB，

说明：a∈VT(终结符) ，  A，B∈VN(非终结符)，即产生式右端的第一个符号必须为 终结符

例如 G：A→aB

              B→b|bB

【其他说明】对于这四种类型的文法：

*包含关系：0 > 1 > 2 > 3 (以'>'代替包含符，'A>B'译为A包含B)

*严格程度：3 > 2 > 1 > 0

*判断文法所属类型的顺序：3 → 2 → 1 → 0

G. 编译原理-文法定义

文法定义公式如下:

Chomsky 文法分类将文法分为四种，0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。

又被称为无限制文法(Unrestricted Grammar), 或者短语结构文法（Phrase Structure Grammar）
定义: 对于产生式 α→β ， α 至少包含一个非终结符。

为什么要叫无限制文法，明明它要求产生式的左部必须包含一个非终结符。

又被称为上下文有关文法(Context-Sensitive Grammar)
定义：对于产生式 α→β , |α| <= |β| , 仅仅 S→ε 除外

为什么叫做上下文有关文法？

一般情况下，这种产生式的形式为 α1Aα2→α1βα2

又被称为上下文无关文法(Context-Free Grammar)
定义：对任一产生式 α→β ，都有 α∈VN，β∈(VN∪VT)*

为什么叫上下文无关文法？

又被称为正则文法（Regular Grammar，RG），分为右线性（Right Linear）文法和左线性（Left Linear）文法。

定义: 对任一产生式 α→β ，都有 α∈VN，β最多两个字符元素，如果有二个字符必须是（终结符+非终结符）的格式，如果是一个字符，那么必须是终结符。

根据产生式右部非终结符位置不同，分为右线性文法和左线性文法。

可以看出，不同文法就是对产生式进行逐层的限制，所以各个文法是包含关系，即0型文法包含1型文法；1型文法又包含2型文法；2型文法最后包含3型文法。