相關(guān)文章

消除左遞歸及提取左公因子
最左推導(dǎo)、最右推導(dǎo)及其語法樹構(gòu)建
FIRST集合、FOLLOW集合以及LL(1)文法

消除左遞歸

什么是左遞歸？

如果一個文法中有一個非終結(jié)符號A使得對某個串α存在一個推導(dǎo)A=》Aα，那么這個文法就是左遞歸的。遞歸分為立即左遞歸和非立即左遞歸。立即左遞歸單步即可看出來，非立即左遞歸
舉個例子：

立即左遞歸：
A ——> Aα | β


非立即左遞歸：
 1）A→aB
 2）A→Bb
 3）B→Ac
 4）B→d

消除左遞歸

消除立即左遞歸只需要遵循以下規(guī)律進行轉(zhuǎn)換就ok。

立即左遞歸：

將A ——> Aα | β 轉(zhuǎn)換為

A ——> β A' 
A' ——> α A'

非立即左遞歸：

先將其變?yōu)榱⒓醋筮f歸
 1）B→aBc
 2）B→Bbc 
 3）B→d
可化簡為：B→aBc | Bbc | d

然后按照上面的規(guī)則進行轉(zhuǎn)換即可
 1）B→aBcB' |dB'
 2）B'→bcB' |ε

最后進行整合
 1）A→aB
 2）A→Bb
 3）B→(aBc|d)B'
 4）B'→bcB'|ε

通用算法

以某種順序排列非終結(jié)符A1，A2，……，An；

for(int i = n; i<=n; i++) {
    for(int j = n; j<=i-1; j++) {
        將每個形如 Ai → Ajγ 的產(chǎn)生式替換為產(chǎn)生式組 Ａi → ξ1γ｜ξ2γ｜……｜ξkγ ，
        其中，Aj→a1｜a2｜……｜ak是所有的當(dāng)前Aj產(chǎn)生式
    }
    消除關(guān)于Ai產(chǎn)生式中的直接左遞歸性
}

提取左公因子

什么是左公因子？

和數(shù)學(xué)中的公因子含義相同，就是公共的因子，而左公因子就是最左邊的公因子。

例如：

S → aB1|aB2|aB3|aB4|...|aBn|y

可以看出前n項擁有一個共同的左公因子：a，所以可以把他提取出來。

提取規(guī)則

so easy啦

S → aS'|y
S'→ B1|B2|B3|...|Bn