 |
练习 |
|
若文法G1的产生式为:
(1) S→aSb
(2) S→aS
(3) S→ε
请提取文法中的左公因子。
参考答案:
对产生式(1)、(2)提取左公因子后得:
S→ aS(b|ε)
S→ε
进一步变换为文法G′1:
S→aSA
A→b
A→ε
S→ε |
 |
练习 |
|
若文法G2的产生式为:
(1) A→ad
(2) A→Bc
(3) B→aA
(4) B→bB
请提取文法中的隐式左公因子。
参考答案:
产生式(2)的右部以非终结符开始,因此左公共因子可能是隐式的,所以这种情况下对右部以非终结符开始的产生式,用其相同左部而右部以终结符开始的产生式进行相应替换,对文法G2分别用(3)、(4)的右部替换(2)中的B,可得:
(1) A→ad
(2) A→aAc
(3) A→bBc
(4) B→aA
(5) B→bB
提取产生式(1)、(2)的左公共因子得:
A→a(d|Ac)
A→bBc
B→aA
B→bB
引进新非终结符A′,去掉'(',')'后得G′2为:
(1) A→aA′
(2) A→bBc
(3) A′→d
(4) A′→Ac
(5) B→aA
(6) B→bB
不难验证经提取左公共因子后文法G′1仍不是LL(1)文法。而文法G′2变成LL(1)文法,因此文法中不含左公共因子只是LL(1)文法的必要条件。
值得注意的是对文法进行提取左公共因子变换后,有时会使某些产生式变成无用产生式,在这种情况下必须对文法重新压缩(或化简)。 |
|