相關(guān)文章
消除左遞歸及提取左公因子
最左推導(dǎo)斩芭、最右推導(dǎo)及其語(yǔ)法樹構(gòu)建
FIRST集合纠亚、FOLLOW集合以及LL(1)文法
消除左遞歸
什么是左遞歸歉甚？
如果一個(gè)文法中有一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串α存在一個(gè)推導(dǎo)A=》Aα，那么這個(gè)文法就是左遞歸的益缠。遞歸分為立即左遞歸和非立即左遞歸脑奠。立即左遞歸單步即可看出來(lái)，非立即左遞歸
舉個(gè)例子：
立即左遞歸：
A ——> Aα | β
非立即左遞歸：
1）A→aB
2）A→Bb
3）B→Ac
4）B→d
消除左遞歸
消除立即左遞歸只需要遵循以下規(guī)律進(jìn)行轉(zhuǎn)換就ok幅慌。
立即左遞歸：
將A ——> Aα | β 轉(zhuǎn)換為
A ——> β A'
A' ——> α A'
非立即左遞歸：
先將其變?yōu)榱⒓醋筮f歸
1）B→aBc
2）B→Bbc
3）B→d
可化簡(jiǎn)為：B→aBc | Bbc | d
然后按照上面的規(guī)則進(jìn)行轉(zhuǎn)換即可
1）B→aBcB' |dB'
2）B'→bcB' |ε
最后進(jìn)行整合
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++) {
將每個(gè)形如 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項(xiàng)擁有一個(gè)共同的左公因子：a，所以可以把他提取出來(lái)互站。
提取規(guī)則
so easy啦
S → aS'|y
S'→ B1|B2|B3|...|Bn
