如何消除左递归、何时需要消除左递归—编译原理

系列文章戳这里👇

1. 什么是上下文无关文法、最左推导和最右推导
2. 如何判断二义文法及消除文法二义性
3. 何时需要消除左递归
4. 什么是句柄、什么是自上而下、自下而上分析
5. 什么是LL(1)、LR(0)、LR(1)文法、LR分析表
6. LR(0)、SLR(1)、LR(1)、LALR(1)文法之间的关系
7. 编译原理第三章习题
8. 词法分析、构建DFA、上下文无关文法、LL(1)分析、提取正规式
9. 证明LL(1)、SLR(1)、LALR(1)文法
10. 翻译方案、属性栈代码
11. 【运行时环境】什么是活动记录、 活动记录与汇编代码的关系

什么是左递归

一个文法是左递归的,如果它有非终结符$A$,对某个串$\alpha$,存在推导$A\to \ast Ax$。自上而下的分析方法不能用于左递归文法，因此需要消除左递归。由形式为$A\to Aa$的产生式引起的左递归称为直接左递归。

什么时候需要消除左递归

在进行自上而下的分析(比如$LL(1)$分析时，构造预测分析器也是$LL(1)$分析)需要消除左递归，因为自上而下的分析方法不能用于左递归文法。任何二义文法绝不是$LR$文法。

怎么消除左递归

直接左递归

举个栗子

非直接左递归

举个栗子

举个栗子

提取左因子