编译语法首先消除左递归

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

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

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

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

⑵ 编译原理左递归消除

这些题很难啊！！！
都有间接左递归。要先变成直接左递归，然后消除掉。
--------------------
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：

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

⑶ 如何消除左递归

首先，什么叫做左递归呢？ 一个左递归的语法通常有这样的形式 : A-> Aa .而自顶向下的语法分析是无法处理左递归语法的。为什么呢？无论是递归分析还是预测分析或者是LL文法分析，在碰到左递归这种语法时都会陷入死循环当中。如果我们用递归分析，那么在分析A这个非终结符号的时候就会调用functionA，functionA将A分解成A，a，然后在我们再次碰到A的时候又会调用functionA，这样便形成了无限递归。如果我们用非递归的LL文法分析，那么在我们将把A->Aa无限次地压入到栈中，即每次弹出A都会压入Aa。所以我们必须采取手段消除左递归，下面给出标准方法。
其中β1…βn 不是从A开始
其实原理在于通过转换将A的语法不从非终结符号（A本身）开始，而是从终结符号β1…βn 开始。虽然A的原语法是从A本身开始的，但是第一个符号一定是β1…βn中的一个，而不可能是任何一个α。所以我们通过一个中间变量A’来表示剩下的α，然而不要忘记由于A’ ->αA’ 这条规则，A’ -> ε 必须也存在于语法规则中，否则末尾将无法匹配完成。
但是，上述方法只适用于立即左递归，还有一种更隐蔽的非立即左递归，如 S -> Aa | b , A -> Sc | d ,我们如果用自顶向下的分析方法会陷入 S -> Aa -> Sca 这样的死循环中。当然，也有相应的解决办法。
将所有非终端符号以某个固定的顺序A_1, \ldots A_n排列
从 i = 1 到 n {
从 j = 1 到 i – 1 {
设A_j的生成规则为
A_j \rightarrow \delta_1 | \ldots | \delta_k
将所有规则 A_i \rightarrow A_j \gamma换成
A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma
移除A_i规则中的直接左递归
}
}
也许看上面的规则过于抽象，我们用S -> Aa | b , A -> Sc | d 来实践一下上述的方法。我们以S，A的顺序排列。则只需执行一次主程序体，且Ai 为A，Aj为S。则：
A -> Aac | bc | d, 然后再运用前面的规则消除直接左递归可得：A -> bcA’ | dA’ , A’ -> acA’ | ε
请注意，以上的解决方案是基于右递归的文法，并不是完全适用于所有的情况。我们得到的文法可能含有 ε表达式，并且可能会改变语法的结合律。解决方案就是保留左递归的语法，不用自顶向下的方式分析。

⑷ 编译原理：消除文法中的左递归

总得有个规则吧。如果不能提供，可以自己看看bison源代码分析--gcc源代码分析语法分析部分。

⑸ 编译原理文法问题，急急急

第一题
S->AB

A->aA'b
A'->aA'b|ε
B->B'
B'->dB'|ε
----------------------
第二题
S->aS'b

S'->aS'b|D
D->dD|ε
----------------------
第三题
最左推导的话，我认为要先消除左递归才行（把左递归转成右递归），消除之后:
N->DN'
N'->DN'|ε
D->0|1|2|...|9
最左推导为 N->DN'->2N'->2DN'->25N'->25DN'->258N'->258
规范推导(最右推导)为N->ND->N8->ND8->N58->D58->258
----------------------
第四题
构造一下语法树就知道了。直接短语是深度为2的节点（根节点是深度0）。短语是深度为2的节点代入深度为1的产生式中。句柄是所有直接短语中最左的那个。
1.baaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
_______|
______a
直接短语为 Aa、a
短语为 Aaa
句柄为 Aa
2.bBaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
直接短语为 Aa、a
短语为 Aaa
句柄为 Aa

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

提取左因子---避免程序回溯；
消除左递归---消除死循环。

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

从分析树的根节点到叶节点方向构造分析树。
即从开始符号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) 。

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

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

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

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