编译中左递归的原理

㈠ 编译原理——LR分析表

自底向上的语法分析

LR分析表的结构如上，其分为两个部分 Action Goto

两个参数状态i，终结符号a（s(i)代表第i个状态，r(i)代表第i条表达式）

Goto[i,A]=j

文法

容易得知这个文法可以推出 0 1 00 01 等的字符串。因为它是 左递归 。不适用于 LL 文法分析，只能使用 LR 分析。

因为本题入口有两个—— S → L·L S → L ，所以需要构造额外的产生式 S'->S

2.1 第一次遍历

我们从 [S -> . L·L] 开始，构造这个状态的闭包，也就是加上所有能从这个产生式推出的表项。

首先，判断 . 后面是否为 非终结符号A 。如果是，那我们就得找所有由 A-> 推出的产生式，并将它们添加进入 闭包 里(也就是State包里)。循环做即可。

因此我们可以得到 State 0 有

下一步，就是我的 . 往下一位移动。对每个符号X后有个 . 的项，都可以从 State 0 过渡到其他状态。

由以上6条式子可以得知下一位符号可以是 S L B 0 1 。所以自然可以得到5个状态。

State 1 是由 State 0 通过 S 转移到这里的，所以我们找出所有 State 0 中在 S 前有 . 的项。

此状态作为结束状态 Accept ，不需要继续状态转移了。

State 2 是由 State 0 通过 L 转移到这里的，所以我们找出所有 State 0 中在 L 前有 . 的项。

S -> . L·L S -> . L L -> . LB

有3条式子，现在我们将 . 向后推一格，就得到 State 1 的项了。

但是 . 之后的符号分别是 · $ B ， B 为非终结符号，我们得包含 B -> 的项

State 3 是由 State 0 通过 B 转移到这里的，所以我们找出所有 State 0 中在 B 前有 . 的项。

因为 . 后没有其他符号了，因此这个状态不需要继续转移了。

State 4 是由 State 0 通过 0 转移到这里的，所以我们找出所有 State 0 中在 0 前有 . 的项。

因为 . 后没有其他符号了，因此这个状态不需要继续转移了。

很简单，同样的道理找 State 5

State 5 是由 State 0 通过 1 转移到这里的，所以我们找出所有 State 0 中在 1 前有 . 的项。

因为 . 后没有其他符号了，因此这个状态不需要继续转移了。

好的，现在我们第一次遍历完成。

2.2 第二次遍历

第二次遍历自然从 State 2 开始。

我们回到 State2 ，可以看出 . 之后的符号有 · B 0 1 。

State 6 是由 State 2 通过 · 转移到这里的，所以我们找出所有 State 2 中在 · 前有 . 的项。

S -> L. ·L 只有1条，我们往后移发现 L 又为非终结符号，参考 State 0 做的操作，我们得找出所有的式子。

共有5条式子，共同组成 State 6 ，由上面的式子可以看出我们还得继续下一次遍历。先不管着，我们进行下一次状态查找。

State 7 是由 State 2 通过 B 转移到这里的，所以我们找出所有 State 2 中在 B 前有 . 的项。

L -> L. B 也是只有1条，我们往后移发现没有非终结符号了，那就不需要再继续添加其他式子了。

这个状态也不需要继续进行转移了。

接下来很关键，因为我们通过 State2 的 . 后的符号找出了 State 6 State 7 ，接下来还差符号 0 1 ，那么是否像之前一样按例添加状态呢， 答案是不是的 ，因为我们发现通过 0 1 找到的闭包集分别是 B -> 0 B -> 1 ，这与我们的之前的 State 4 State 5 相同。所以我们得将其整合起来，相当于 State 2 通过 0 1 符号找到了 State 4 State 5 状态。

2.3 第三次遍历

回头看第二次遍历，可以看出只有 State 6 可以进行状态转移了。

那么就将 State 6 作为第三次遍历的源头，可以看出 . 之后的符号有 L B 0 1 。

State 8 是由 State 6 通过 L 转移到这里的，所以我们找出所有 State 6 在 L 前有 . 的项。

S -> L· .L L -> . LB 有两条式子，往后移发现有非终结符号 B ，所以经过整合可以得到

可以看出 . 的后面还有一个符号，所以这里我们还得再进行一次遍历。

接下来，又是遇到重复的包的情况，可以看出我们由 State 6 通过 B 0 1 得到的闭包分别是 L->B B->0 B->1 ，很明显，这分别对应于 State 3 State 4 State 5 。

第三次遍历也就结束了。

2.4 第四次遍历

回看第三次遍历，可以看出只有 State 8 可以进行状态转移，其 . 之后的符号分别是 B 0 1 。

诶，感觉很熟悉，就是上面几行刚说的情况，也就是说通过这三个符号找到的闭包是我们之前遇到的状态，分别是 State 3 State 4 State 5 。

做到这里，我们发现我们已经全部遍历完毕！

总共有8个状态，通过以上流程做成个图是什么样子的？来看看！

这么一看就很清晰明了了，我们就可以通过这个图做出我们的 LR分析表

其实就是我们之前呈现的表

在状态 I2 和 I8 中，既有 移入 项目，也有 规约 项目，存在 移入 - 规约的冲突 ，所以不是 LR(0) 文法，但是因为 FOLLOW(S) ∩ {0, 1} = ∅，所以可以用 FOLLOW 集解决冲突，所以该文法是 SLR(1) 文法。

上表我们发现还有 r1，r2，r3 等。这个其实就是代表状态停止转移时为 第几条表达式 ，r3代表第三条表达式 L -> LB 。

当我们构建了表之后，我们如何运用起来呢？

下面我们通过一个例子来说明

以上字符串是如何被SLR分析器识别的呢？

㈡ 【编译原理】第四章：语法分析

从分析树的根节点到叶节点方向构造分析树。
即从开始符号S推导出词串w的过程。

例：

总是选择每个句型的 最左非终结符 进行替换。

总是选择每个句型的 最右非终结符 进行替换。

在自底向上的分析中，总是采用 最左规约 的方式，因此把 最左规约 称为 规范规约 ，对应的 最右推导 称为 规范推导 。

最左推导、最右推导具有唯一性。

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

由一组 过程 组成，每一个过程对应一个 非终结符 。
从文法开始符号S开始，递归调用文法中的其他非终结符，最终扫描整个输入串，完成分析。

如果其间有不唯一的产生式，就可能需要退回上一步重新尝试的情况，称为 回溯 。

预测分析 是 递归下降分析 技术的一个特例，通过输入中向前看固定个数的符号选择正确的产生式。
如果一个文法可以构造出向前看k个符号的预测分析器，称为LL(k)文法 。

预测分析不需要回溯，具有确定性。

含有 形式产生式的文法称为是 直接左递归 的。
如果一个文法中有一个非终结符A使得对某个串存在推导 ，那么这个文法是 左递归 的。其中，经过两步或以上推导产生的左递归，称为 间接左递归 的。
左递归会使递归下降分析器陷入无限循环。

文法
即
该文法是直接左递归的，会陷入无限循环。

将以上文法转换为：


即可消除左递归。事实上，这个过程把左递归转换成了右递归。

消除直接左递归的一般形式

使用代入法。

对于一个文法，通过改写产生式来 推迟决定 ，等获得足够多的输入信息再做正确的决定。

例：文法：

可以改写为：

从文法的开始符号S开始，每一步推导根据当前句型的最左非终结符A和当前输入符号α，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

S_文法（简单的确定型文法）

可能在某个举行中紧跟在A后面的终结符a的集合，记为 FOLLOW(A) 。
如果A是某个句型的最右符号，则将结束符“ $ ”添加到FOLLOW(A)中。

例：文法：






中，FOLLOW(B) = {a, c}

产生式 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 SELECT(A->β) 。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)

q_文法

文法符号串α串首终结符的集合，记作 FIRST(A) 。

㈢ 编译原理的消除左递归是怎么回事啊

如果一个CFG像这样
A -> Ab
A -> e

就是有左递归，语法分析里的递归下降法和LL（1）就不能处理啦，因为程序会陷入递归而无法前进。
而CFG
A -> bA'
A' -> bA'|e
和前面一个表达的语言是一样的，但所有语法的第一项都是终结符，就消除了左递归。

有消除左递归的算法，一般编译原理书上会有介绍，不是很复杂。

㈣ 编译原理语法分析中消除左递归的问题。比如A→Ab|c中为什么说它是左递归呢，明明是A定义为Ab或者

A->Ab|c为什么是左递归，和为什么要消除左递归：

定义，就无需争辩了。至于为什么自顶向下文法不能处理左递归,解释如下：

c∈FIRST(A)，所以当预测分析的栈顶出现非终结符A，而输入字符串最左边为c时，就不知道用产生式A->Ab还是A->c了。无法构造预测分析表。比如输入字符串为cbb，我们人当然容易知道是A->Ab->Abb->cbb了，但是电脑没那么聪明，如果不消除左递归，只有回溯了。

㈤ 【编译原理】自顶向下LL（1）分析中，消除左递归和提取左因子的目的是什么

通常LL(1) 是以函数递归调用来实现的
如文法: A -> A + a | a
代码实现则为:
function A()
{
A();
match('+');
Term(a);
}
这样你可以看得出死循环了吧...?
将文法消除左递归后
A -> aA'
A' -> +aA'
则可以避免这一问题
提出公因式 就像楼上说的一样,避免程序回溯,消除二义性.
楼上高手啊,求搞基.

㈥ 关于LL(1)文法的编译原理题目

判断是不是LL(1)，首先看候选式的首字符有没有相同的，第二判断首字符迭代进去是否会构成左递归。
如果首字符不相同，也没用左递归就说明此文法是LL(1)
M→MaH｜H
H→(M)｜b(M)｜b
第一个产生式中存在左递归:M->MaH
第二个产生式中存在首字符相同:H->b(M) ,
H->b
怎么改呢？
对第一个产生式，消除左递归就是要变成右递归，把右边剩下的符号提到前面:
M->aHM'

M'->aHM'
对第二个产生式，提出公共因子
H->b( (M)|ε)
=>
H->bH'

H'->(M)|ε

㈦ 编译原理A->A,(A)|a消除左递归

A::=aA'
A'::=,(A)A'|ε

㈧ 编译原理中 左递归具体解释是什么

定义：
"一个文法是左递归的，若我们可以找出其中存在某非终端符号A，最终会推导出来的句型(sentential form)里面包含以自己为最左符号(left-symbol)的句型"
即
A -> Aa 或
A -> Ba
B -> A
两种形式的文法.

㈨ 编译原理左递归消除

这些题很难啊！！！
都有间接左递归。要先变成直接左递归，然后消除掉。
--------------------
G3.1
S->SA|Ab|b|c
A->Bc|a
B->Sb|b
--------------------
间接左递归转直接左递归
B代入A：A ->(Sb|b)c|a -> Sbc|bc|a
A代入S：S -> S(Sbc|bc|a)|(Sbc|bc|a)b|b|c -> SSbc|Sbc|Sa|Sbcb|bcb|ab|b|c
消除直接左递归
S->bcbS'|abS'|bS'|cS'
S'->SbcS'|bcS'|aS'|bcbS'|ε
S'还是有直接左递归，继续消除
S'->bcS'T|aS'T|bcbS'T
T->bcS'T|ε
最后，这题答案就是S,S',T的产生式

--------------------
下面两题更难了，上一题反复代入还能把其他非终结符消掉，下面两个文法都是最后代入还剩下两个非终结符反复迭代，佛了！
G3.2
E->ET+|T

T->TF*|F

F->E|i
--------------------
F代入T: T->T(E|i)*|(E|i)->TE*|Ti*|E|i
T代入E：

--------------------
G3.3
S->V_1

V_1->V_2|V_1 2 V_2

V_2->V_3|V_2 + V_3
V_3->V_1 * |(
这些字母我都不认识了，换一下
S->A|SiA
A->B|A+B
B->S*|(
--------------------
B代入A：A->(S*|()|A+(S*|()->S*|(|A+S*|A+(
A代入S：

--------------------

㈩ 编译原理-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(α) 包括空串ε，那么这个产生式是不是间接左递归。