消除立即左递归

我明白，为了从包含 A⇒Aα 形式产生的语法中消除立即左递归，我需要将其替换为 A⇒βA' 和 A'⇒αA/ε

我有以下产生式，我需要消除立即左递归

E⇒E+T/T

E⇒E+T/T

T⇒T*F/T

F⇒(E)/(id)

我可以看到，消除后第一个生产变成

E⇒TE'

E'⇒+TE'/Tε

有人可以解释这是怎么来的吗

这实际上只是遵循算法的问题。我们来看一下一般情况。根据算法的形式规则：

A => A a1 | ... | A aN | b1 | .. | bN

where A a1, ..., A aN是终结符和非终结符的非零左递归序列，并且b1, ..., bN是终结符和不以终结符开头的非终结符的序列A.

该算法表示我们需要将其替换为

A => b1 A' | ... | bN A'
A' => a1 A' | ... | aN A' | epsilon

我们来看看你的案例。在这里我们有

E => E + T | T

所以你可以想到a1是序列+ T since E + T是终结符和非终结符的左递归序列。同样你可以想到B1 as T因为这是一个非左递归序列。我们现在用它来定义新的非终结符E as:

E => b1 E'

自从b1 is T这变成

E => T E'

定义E' we get

E' => a1 E' | epsilon

自从a1 is + T这变成

E' => + T E' | epsilon 

这样你就得到了语法

E => T E'
E' => + T E' | epsilon