什么是左递归以及如何消除它？
如果语法 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 → β 1 A′|β 2 A′| …… . | …… . |β n A′
A → α 1 A′|α 2 A′| …… . |α m A′|ε
Example1 - 考虑语法中的左递归。
E → E + T|T
T → T * F|F
F → (E)|id
从语法中消除立即左递归。
解决方案
比较 E → E + T|T 与 A → A α |β
| E | → | E | +T | | | 吨 |
| A | → | A | α | | | Β |
∴ A = E, α = +T, β = T
∴ A → A α |β 变为 A → βA′和 A′ → α A′|ε
∴ A → βA′ 表示 E → TE′
A' → α A'|ε 表示 E' → +TE'|ε
比较 T → T ∗ F|F 与 A → Aα|β
| T | → | T | *F | | | F |
| A | → | A | α | | | β |
∴ A = T, α =∗ F, β = F
∴ A → β A′ 表示 T → FT′
A → α A′|ε 表示 T′ →* FT′|ε
生产 F → (E)|id 没有任何左递归
∴ 结合产生式 1、2、3、4、5，我们得到
E → TE′E′ → +TE′| ε
T → FT′
T →* FT′|ε
F → (E)| id
Example2 - 消除以下语法的左递归。
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′| ε
Example3 - 从语法中消除左递归
E → E + T|T
T → T * F|F
F → (E)|id
解决方案
去除左递归后的产生式将是
E → TE′E′ → +TE′| ∈
T → FT′
T′ →∗ FT′| ∈
F → (E)|id
Example4 - 从语法中删除左递归
E → E(T)|T
T → T(F)|F
F → 身份证
解决方案
消除所有 Aα 产生式中的立即左递归，我们得到
E → TE′E → (T)E′|ε
T → FT′
T′ → (F)T′|ε
F → id
以上是 什么是左递归以及如何消除它？ 的全部内容， 来源链接： utcz.com/z/363359.html
