什么是编译器设计中的非立即左递归？
如果语法 G (V, T, P, S) 具有形式中的产生式，则它是左递归的。
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′|ε
在下面的语法中，它没有立即或直接左递归。但是在这里，它可以有非立即左递归。
S → 抗体
A → Sc|d
这里，S 是左递归的，因为 S ⇒ A b ⇒ S cb
去除左递归的算法
输入- 没有循环的语法 G 或 ε - 产生式。
输出- 没有左递归的等效语法。
方法
将非终结符排序为 A 1、 A 2、………………。. 一个_
for i = 1 to n{
for j = 1 to i – 1
{
replace each production Ai → Ajγ
by productions Ai → δ1γ| δ2γ| … … . . |δKγ
where Aj → δ1|δ2| … … . |δK
}
Remove immediate left Recursion among Ai productions.
}
Example1 - 从以下语法中删除或消除左递归。
S → 抗体
A → 科学 | d
解决方案
这些产生式没有立即左递归。所以不能直接消除。我们可以使用这里的算法来去除左递归。
Step1 - 将非终结符 S, A 排序为 A 1 , A 2即标记 S =A 1 , A = A 2
替换值
∴ A 1 → A 2 b …………… (1)
A 2 → A 1 c|d …………… (2)
Step2 - 将(1)的值放入(2)中
∴ A 1 → A 2 b
A 2 → A 1 bc|d
Step3 - 再次替换 A 1 = S 和 A 2 = A
∴ S → A b ……………。(3)
A → A bc | d………………。(4)
Step4 - 删除 A → A bc 中的立即左递归 | d
所以，
Example2 - 从以下语法中删除左递归。
S → Aa |b
A → 交流 | Sd|e
解决方案
由于我们没有立即左递归，所以我们必须在这里应用算法。
Step1 - 将 S、A 分别重命名为 A 1、 A 2。
A 1 → A 2 a | b ……………… (1)
A 2 → A 2 c | A1d|e ………………。(2)
Step2 - 在语句 (2) 的 RHS 中替换语句 (1)的 A 1的值。
A 1 → A 2 a | b
A 2 → A 2 c |A 2 ad|bd|e。
Step3 - 再次替换 A 1 = S, A 2 = A
S → Aa |b …………….. (3)
A → Ac |A ad|bd|e ……………… (4)
Step4 - 语句 (4) 具有立即左递归。删除立即左递归，我们得到
以上是 什么是编译器设计中的非立即左递归？ 的全部内容， 来源链接： utcz.com/z/363360.html
