什么是左递归?如何消除左递归?
compiler designprogramming languagescomputer programming更新于 2025/9/29 14:37:17
如果语法 G (V, T, P, S) 中有一个如下形式的产生式，则该语法是左递归的。
A → A α |β.
上述语法是左递归的，因为产生式的左侧出现在产生式右侧的第一个位置。它可以通过将一对产生式替换为来消除左递归
A → βA′
A → αA′|ϵ
消除左递归
可以通过引入新的非终结符 A 来消除左递归，使得。
这种递归也称为立即左递归。
在左递归语法中，展开 A 将生成 Aα、Aαα、Aααα每一步都会导致其进入无限循环
左递归的一般形式为
A → Aα1|Aα2| … . |Aαm|β1|β2| … . . βn
可以替换为
A → β1A′|β2A′| … . . | … . . |βnA′
A → α1A′|α2A′| … . . |αmA′|ε
示例 1 − 考虑文法中的左递归。
E → E + T|T
T → T * F|F
F → (E)|id
从语法中消除立即左递归。
解决方案
Comparing E → E + T|T with A → A α |β
E→E+T|TA→Aα|Β
∴ A = E, α = +T, β = T
∴ A → A α |β is changed to A → βA′and A′ → α A′|ε
∴ A → βA′ means E → TE′
A′ → α A′|ε means E′ → +TE′|ε
Comparing T → T ∗ F|F with A → Aα|β
T→T*F|FA→Aα|β
∴ A = T, α =∗ F, β = F
∴ A → β A′ means T → FT′
A → α A′|ε means T′ →* FT′|ε
Production F → (E)|id does not have any left recursion
∴ Combining productions 1, 2, 3, 4, 5, we get
E → TE′
E′ → +TE′| ε
T → FT′
T →* FT′|ε
F → (E)| id
示例 2 − 消除以下文法的左递归。
S → a|^|(T)
T → T, S|S
解答
在 T 产生式中，我们有直接左递归。
比较 T → T, S|S 与 A → A α | β 其中 A = T, α =, S 且 β = S
∴完整语法将是
S→ a|^(T)
T→ ST′
T′ →,ST′| ε
示例 3 − 从语法中消除左递归
E → E + T|T
T → T * F|F
F → (E)|id
解决方案
消除左递归后的产生式将是
E → TE′
E′ → +TE′| ∈
T → FT′
T′ →∗ FT′| ∈
F → (E)|id
示例 4 − 从文法中删除左递归
E → E(T)|T
T → T(F)|F
F → id
解决方案
消除所有 Aα 产生式中的直接左递归，我们得到
E → TE′
E → (T)E′|ε
T → FT′
T′ → (F)T′|ε
F → id
相关文章
描述编程语言设计中影响存储管理的问题?
我们能将非确定性有限自动机转换为确定性有限自动机吗?
Construct NFA for the following language and convert it into DFA using the algorithm - L = (aa+ (bb*)c*)
为以下语法构建一个预测解析表并检查字符串 \id + id * id 是否被接受。
为以下语法构建 SLR (1) 解析表\S → x A y |x B y |x A z\A → q s | q\B → q
为以下语法构建 SLR 解析表。另外，解析输入字符串 a * b + a。
考虑语法\S → CC\C → c C | d\为 LALR (1) 解析器构建解析表。
考虑有歧义的语法。\E → E + E\E → E * E\E → (E)\E → id\(a) 为上述语法构造 LR (0) 项。\(b) 为语法构造 SLR 解析表。\(c) 解析输入字符串 id + id * id。
为表达式\-(a + b) * (c + d) - (a + b + c) 构造四元组、三元组和间接三元组
为给定的语法构建 LALR (1) 解析表。\问题− 为该语法构建 LALR (1) 解析表。\S → A a|b A c|dc|bda\A → d\使用 LALR 解析表解析输入字符串"bdc"。
打印
下一节:编译器设计中的非立即左递归是什么? ❯❮ 上一节:编译器设计中的自上而下回溯解析是什么?