编译原理2型文法一定会满足1

‘壹’ 编译原理的LL（1）文法是什么意思

1.文法不含左递归，没有公共左因子
2.对于文法中的每个非终结符A的产生式的候选首符集两两不相交。
3.对于文法中的每个非终结符A，它存在某个候选首符集包括ε，则FIRST（A）∩FOLLOW（A）=空
满足以上条件的文法为LL（1）文法

‘贰’ 在编译原理中，什么是上下文无关文法什么是语言

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

‘叁’ 编译原理 文法类型

    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型文法

‘肆’ 编译原理-LL1文法详细讲解

我们知道2型文法( CFG )，它的每个产生式类型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一个表达式的文法:

最终推导出 id + (id + id) 的句子，那么它的推导过程就会构成一颗树，即 CFG 分析树：

从分析树可以看出，我们从文法开始符号起，不断地利用产生式的右部替换产生式左部的非终结符，最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。

从文法开始符号起，不断用非终结符的候选式(即产生式)替换当前句型中的非终结符，最终得到相应的句子。
在每一步推导过程中，我们需要做两个选择:

因为一个句型中，可能存在多个非终结符，我们就不确定选择那一个非终结符进行替换。
对于这种情况，我们就需要做强制规定，每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。

自顶向下的语法分析采用最左推导方式，即总是选择每个句型的最左非终结符进行替换。

最终的结果是要推导出一个特定句子(例如 id + (id + id) )。
我们将特定句子看成一个输入字符串，而每一个非终结符对应一个处理方法，这个处理方法用来匹配输入字符串的部分，算法如下:

方法解析:

这种方式称为递归下降分析( Recursive-Descent Parsing )：

当选择的候选式不正确，就需要回溯( backtracking )，重新选择候选式，进行下一次尝试匹配。因为要不断的回溯，导致分析效率比较低。

这种方式叫做预测分析( Predictive Parsing )：

要实现预测分析，我们必须保证从文法开始符号起，每一个推导过程中，当前句型最左非终结符 A 对于当前输入字符 a ,只能得到唯一的 A 候选式。

根据上面的解决方法，我们首先想到，如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。
进而我们可以得出，如果一个非终结符 A ，它的候选式都是以终结符开头，并且这些终结符都各不相同，那么本身就符合预测分析了。

这就是S_文法，满足下面两个条件:

例子:

这就是一个典型的S_文法，它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S -> aA | bAB , 只有遇到终结符 a 和 b 的时候，才能返回 S 的候选式，遇到其他终结符时，直接报错，匹配不成功。

虽然S_文法可以实现预测分析，但是从它的定义上看，S_文法不支持空产生式(ε产生式)，极大地限制了它的应用。

什么是空产生式(ε产生式)？

例子

这里 A 有了空产生式，那么 S 的产生式组 S -> aA | bAB ，就可以是 a | bB ,这样 a , bb , bc 就变成这个文法 G 的新句子了。

根据预测分析的定义，非终结符对于任一终结符得到的产生式是确定的，要么能获取唯一的产生式，要么不匹配直接报错。

那么空产生式何时被选择呢？

由此可以引入非终结符 A 的后继符号集的概念:
定义: 由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符 a 的集合，就是这个非终结符 A 的后继符号集，记为 FOLLOW(A) 。

因此对于 A -> ε 空产生式，只要遇到非终结符 A 的后继符号集中的字符，可以选择这个空产生式。
那么对于 A -> a 这样的产生式，只要遇到终结符 a 就可以选择了。

由此我们引入的产生式可选集概念:
定义: 在进行推导时，选用非终结符 A 一个产生式 A→β 对应的输入符号的集合，记为 SELECT(A→β)

因为预测分析要求非终结符 A 对于输入字符 a ,只能得到唯一的 A 候选式。
那么对于一个文法 G 的所有产生式组，要求有相同左部的产生式，它们的可选集不相交。

在 S_文法基础上，我们允许有空产生式，但是要做限制:

将上面例子中的文法改造:

但是q_文法的产生式不能是非终结符打头，这就限制了其应用，因此引入LL(1)文法。

LL(1)文法允许产生式的右部首字符是非终结符，那么怎么得到这个产生式可选集。
我们知道对于产生式:

定义: 给定一个文法符号串 α ， α 的 串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。

定义已经了解清楚了，那么该如何求呢？
例如一个文法符号串 BCDe , 其中 B C D 都是非终结符， e 是终结符。

因此对于一个文法符号串 X1X2 … Xn ，求解 串首终结符集 FIRST(X1X2 … Xn) 算法:

但是这里有一个关键点，如何求非终结符的串首终结符集？

因此对于一个非终结符 A , 求解 串首终结符集 FIRST(A) 算法:

这里大家可能有个疑惑，怎么能将 FIRST(Bβ) 添加到 FIRST(A) 中，如果问文法符号串 Bβ 中包含非终结符 A ，就产生了循环调用的情况，该怎么办?

对于 串首终结符集 ，我想大家疑惑的点就是，串首终结符集到底是针对 文法符号串 的，还是针对 非终结符 的，这个容易弄混。
其实我们应该知道， 非终结符 本身就属于一个特殊的 文法符号串 。
而求解 文法符号串 的串首终结符集，其实就是要知道文法符号串中每个字符的串首终结符集:

上面章节我们知道了，对于非终结符 A 的 后继符号集 :
就是由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符的集合，记为 FOLLOW(A) 。

仔细想一下，什么样的终结符可以出现在非终结符 A 后面，应该是在产生式中就位于 A 后面的终结符。例如 S -> Aa ，那么终结符 a 肯定属于 FOLLOW(A) 。

因此求非终结符 A 的 后继符号集 算法：

如果非终结符 A 是产生式结尾，那么说明这个产生式左部非终结符后面能出现的终结符，也都可以出现在非终结符 A 后面。

我们可以求出 LL(1) 文法中每个产生式可选集:

根据产生式可选集，我们可以构建一个预测分析表，表中的每一行都是一个非终结符，表中的每一列都是一个终结符，包括结束符号 $ ，而表中的值就是产生式。
这样进行语法推导的时候，非终结符遇到当前输入字符，就可以从预测分析表中获取对应的产生式了。

有了预测分析表，我们就可以进行预测分析了，具体流程:

可以这么理解：

我们知道要实现预测分析，要求相同左部的产生式，它们的可选集是不相交。
但是有的文法结构不符合这个要求，要进行改造。

如果相同左部的多个产生式有共同前缀，那么它们的可选集必然相交。
例如:

那么如何进行改造呢？
其实很简单，进行如下转换:

如此文法的相同左部的产生式，它们的可选集是不相交，符合现预测分析。

这种改造方法称为 提取公因子算法 。

当我们自顶向下的语法分析时，就需要采用最左推导方式。
而这个时候，如果产生式左部和产生式右部首字符一样(即A→Aα)，那么推导就可能陷入无限循环。
例如:

因此对于:

文法中不能包含这两种形式，不然最左推导就没办法进行。

例如:

它能够推导出如下:

你会惊奇的发现，它能推导出 b 和 (a)* (即由 0 个 a 或者无数个 a 生成的文法符号串)。其实就可以改造成:

因此消除 直接左递归 算法的一般形式：

例如:

消除间接左递归的方法就是直接带入消除，即

消除间接左递归算法：

这个算法看起来描述很多，其实理解起来很简单：

思考 : 我们通过 Ai -> Ajβ 来判断是不是间接左递归，那如果有产生式 Ai -> BAjβ 且 B -> ε ,那么它是不是间接左递归呢？
间接地我们可以推出如果一个产生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那么这个产生式是不是间接左递归。

‘伍’ 四种文法的类型(编译原理)

乔姆斯基（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(E)：E -> E+E | E*E | (E) | i
这两种展开
E E
E + E E * E
i E * E E + E i
i i i i

都可以表示i+i*i

所以;文法具有二义性。

‘柒’ 编译原理中,形式语言里怎么区分2型文法与3型文法

通过算法对文法的每一产生式进行分析,如果存在复杂递归,则必是上下文无关文法,否则就是正则文法.
1、像A->Aa|ε这样的文法,虽然存在递归,但却是单一的自递归,可以通过有穷自动机表示和分析处理,所以是正则文法；
2、但是像E->E+T,T->id|(E)这样的文法显然非单一的自递归,而是存在复杂递归,自动机是无法表示和处理的,必然是上下文无关文法.
另外还请注意：
1、正则文法是上下文文法的子集,正则文法也属于上下文无法,但有的上下文文法不一定是正则文法；
2、同时再结合这两个的形式定义认真揣摩必定能悟出一二.

‘捌’ 编译原理 2型文法一定是1型文法吗 不是一种包含关系吗

1型文法就是上下文有关文法，2型文法是上下文无关文法，1型文法的确是包含了2型文法，因为只要你在1型文法的基础上，加下一个条件：非终结符的替换不必考虑上下文，就成为2型文法了。

‘玖’ 编译原理-文法定义

文法定义公式如下:

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型文法。