设有文法G(A): A→aAB|a B→Bb|d (1)证明文法G(A)是否为LL(1)文法?说明为什么?
文法,
已帮助 人
设有文法G(A): A→aAB|a B→Bb|d (1)证明文法G(A)是否为LL(1)文法?说明为什么? (2)试改写文法为LL(1)文法。
请帮忙给出正确答案和分析,谢谢!
-
正确答案:(1)文法G(A)不是LL(1)文法。因为G(A)含有左递归含有左公因子。 (2)改写后的文法: A→aA′ A′→AB|ε B→dB′ B′→bB′|ε 验证:对A′有FIRST(AB)={a}∩FOLLOW(A′)={#)=Ф 对B′有FIRST(bB′)={B)∩FOLLOW(B′)={#)=Ф ∴改写后的文法是LL(1)文法。
文法G(A)不是LL(1)文法。因为G(A)含有左递归,含有左公因子。(2)改写后的文法:A→aA′A′→AB|εB→dB′B′→bB′|ε验证:对A′有FIRST(AB)={a}∩FOLLOW(A′)={#)=Ф对B′有FIRST(bB′)={B)∩FOLLOW(B′)={#)=Ф∴改写后的文法是LL(1)文法。
