- 在进行语法分析的时候，如果采用自上而下的分析方法（从开始符开始，推句子），那么要求文法不是左递归的，进而如果是左递归的，则要求消除左递归
-
左递归的定义：文法经过一次或多次推导之后，出现如下形式
微信公众号：JavaWeb架构师 - 左递归的分类
- 直接左递归：P → Pa
- 简介左递归：P → Aa， A → …… → Pb
直接左递归的消除
- 对于 P → Pa | b 形式(b可为空)，可以知道，推导结束的时候一定有一个b在最开始位置（如ba），后面是无数多个a，所以可以归纳得出如下的消除方法
P → bP';
P' → aP' | ε;
- 更一般化的形如P → PX|Y（其中X和Y看作一个整体，比如：P → Pabc|ab|b，X就是abc，Y就是ab|b），可以归纳成如下形式：
P → YP'; 比如：P → abP' | b P'
P' → XP' | ε; 比如： P' → abcP' | ε
间接左递归的消除
-
对于P → Aa | x1， A → …… → Pb | x2的形式
-
消除规则
- 1） 若消除过程中出现了直接左递归，就按照直接左递归的方法，来消除
- 2） 若产生式右部最左的符号是非终结符，且这个非终结符序号大于等于左部非终结符，则暂不处理（后面会处理到）
- 3） 若序号小于左部的非终结符，则用之前求到的式子的右部来替换
-
步骤伪代码
// 1.把文法G的所有非终结符按任意顺序排列，并编号
[P1,P2,……,Pn]
// 2.按上面的排列顺序，对这些非终结符进行遍历
for(int i = 1; i <= n; ++i) {
for(int j = 1; i <= i - 1; ++j) {
// 3.将当前处理的非终结符中的序号小于等于它的非终结符按规则3）进行替换（序号大于的按规则2）处理）
2）、3）
}
// 4.消除i序号的非终结符的直接左递归（如果存在的话）
1）
}
// 5.删除其中不可达的非终结符（从开始符开始，无法再推出的非终结符）
- 注意
- 第一步对非终结符进行排序的序列不同，最后结果的产生式有可能不同，但它们是等价的
- 开始符号不能改变
- 该算法，能同时消除直接、间接左递归
例题
- 存在如下文法，消除左递归
1）S → Qc | c
2）Q → Rb | b
3）R → Sa | a
1）把文法G的所有非终结符按任意顺序排列，并编号
R、Q、S
2）按上面的排列顺序，对这些非终结符进行遍历
3）将当前处理的非终结符中的序号小于等于它的非终结符按规则3）进行替换（序号大于的按规则2）处理）
R:
R的右部中的非终结符有S;
S的下标大于R，可以暂时不处理;
所以此时R改写为：R → Sa | a
----------------------------------------------
Q:
Q的右部中的非终结符有R;
R的下标小于Q，将R的右部替换进来;
所以此时Q改写为：Q → Sab | ab | b;
S的下标大于Q，可以暂时不处理;
所以此时Q改写为：Q → Sab | ab | b;
-----------------------------------------
S:
S的右部中的非终结符有Q;
Q的下标小于S，将Q的右部替换进来;
所以此时S改写为：S → Sabc |abc | bc | c
S的下标等于S，可以暂时不处理;
所以此时S改写为：S → Sabc |abc | bc | c
4）消除i序号的非终结符的直接左递归（如果存在的话）
S → Sabc |abc | bc | c
∴ X = abc，Y = abc | bc | c
∴ 直接消除左递归的结果是：
S → abcS' | bcS' | cS'
S' → abcS' | ε
5）删除其中不可达的非终结符，这里就是Q、R了
∴ 最终消除左递归的结果是
S → abcS' | bcS' | cS'
S' → abcS' | ε作者：冯强计算机考研
链接：https://www.jianshu.com/p/7cd310e6c74e
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。