试判断下面哪些文法是LL（1)的？如果不是 哪些能改写为LL（1)文法并改写。 （1)S→A｜B A→aA｜

正确答案：(1)设有下列文法： S→A｜B ① A→aA｜a ②｜③ B→bB｜b ④｜⑤ 该文法不是LL(1)文法因为非终结符A、B的两个候选式存在左公因子。 提取左公因子改写后的文法如下： S→A｜B ① A→aA′ ② A′→A｜ε ③ B→bB′ ④ B′→B｜ε ⑤ 验证： 对S：FIRST(A)＝{a)FIRST(B)＝(b}；FIRST(A)∩FIRST(B)＝Ф 对A′：FIRST(A)＝{a)FOLLOW(A′)＝{#}；FIRST(A)n FOLLOW(A′)＝Ф 对B′：FIRST(B)＝{b)FOLLOW(B′)＝{#)；FIRST(B)∩FOLLOW(B′)＝Ф 所以改写后的文法是LL(1)文法。 (2)设有文法： S→AB A→BA｜ε B→Db｜D D→d｜ε 该文法不是LL(1)文法因为关于B的产生式存在左公因子。改写后文法： S→AB A→Ba｜ε B→DB′ B′→b｜ε D→d｜ε 验证： 对A：FIRST(Ba)＝{bda}FOLLOW(A)＝{#bd}；FIRST(Ba)∩ FOLLOW(A)＝Ф 对B′：FIRST(Db)＝{b}FOLLOW(B′)＝{#a}；FIRST(Db)∩FOLLOW(B′)＝Ф 对D：FIRST(d)＝{d}FOLLOW(D)＝{#b}；FIRST(d)∩FOLLOW(D)＝Ф ∴经验证改写后的文法是LL(1)文法。 (3)该文法不是LL(1)文法因为产生式①存在左递归产生式②存在左公因子。改写后文法： M→HM′ ① M′→aHM′｜ε ②｜③ H→bH′｜(M) ④｜⑤ H′→(M)｜ε ⑥｜⑦ 验证： 对②｜③：FIRST(aHM′)＝{a)∩FOLLOW(M′)＝(#)}＝Ф 对④｜⑤：FIRST(bH′)＝{b}∩FIRST((M))＝{(}＝Ф 对⑥｜⑦：FIRST((M))＝{(}∩FOLLOW(H′)＝{#a)}＝Ф ∴经验证改写后的文法是LL(1)文法。 (4)对给定文法设置编号： A→baB｜ε ① B→Abb｜a ②｜③ 对①：FIRST(baB)＝{b}∩FOLLOW(A)＝{b#)≠Ф ∴该文法不是LL(1)文法。 对文法进行改写将A代入B同时提取左公因子则改写后文法为： A→baB｜ε ① B→bB′｜a ② B′→aBbb｜b ③ 对①：FIRST(baB)＝{b}∩FOLLOW(A)＝{#)＝Ф 对②：FIRST(bB′)＝(b)∩FIRST(a)＝{a}＝Ф 对③：FIRST(aBbb)＝{a}∩FIRST(b)＝{6}＝Ф ∴经验证改写后的文法是LL(1)文法。 (5)设有文法： A→aABe｜a B→Bb｜d 该文法不是LL(1)文法因为关于B的产生式有左递归关于A的产生式存在左公因子。改写后文法： A→aA′ A′→ABe→→ B→dB′ B′→bB′→→ 验证： 对A′：FIRST(ABe)＝{a}FOLLOW(A′)＝{d#)有FIRST(ABe)∩FOLLOW(A′)＝Ф 对B′：FIRST(bB′)＝{b}FOLLOW(B′)＝{ε)有FIRST(bB′)∩FOLLOW(B′)＝Ф ∴经验证改写后的文法是LL(1)文法。 (6)设有下列文法： S→Ab｜Ba ① A→aA｜a ②｜③ B→a ④｜⑤ 该文法不是LL(1)文法因为非终结符A的产生式存在左公因子。 提取左公因子改写后的文法G′如下： S→aS′ ／／① S′→aS〞｜b ／／②③ S〞→Ab｜b｜ε ／／④⑤⑥ A→aA′ ／／⑦⑧ A′→A｜ε ／／⑧⑨ 对S′：{a}∩{b}＝Ф 对S〞：FOLLOW(S〞)＝{{#}∪{ε}}∩{b}∩{a}＝Ф 对A′：FOLLOW(A′)＝{b}∩{a}＝Ф ∴经验证改写后的文法G′是LL(1)文法。
设有下列文法：S→A｜B①A→aA｜a②｜③B→bB｜b④｜⑤该文法不是LL(1)文法,因为非终结符A、B的两个候选式存在左公因子。提取左公因子改写后的文法如下：S→A｜B①A→aA′②A′→A｜ε③B→bB′④B′→B｜ε⑤验证：对S：FIRST(A)＝{a),FIRST(B)＝(b}；FIRST(A)∩FIRST(B)＝Ф对A′：FIRST(A)＝{a),FOLLOW(A′)＝{#}；FIRST(A)nFOLLOW(A′)＝Ф对B′：FIRST(B)＝{b),FOLLOW(B′)＝{#)；FIRST(B)∩FOLLOW(B′)＝Ф所以改写后的文法是LL(1)文法。(2)设有文法：S→ABA→BA｜εB→Db｜DD→d｜ε该文法不是LL(1)文法,因为关于B的产生式存在左公因子。改写后文法：S→ABA→Ba｜εB→DB′B′→b｜εD→d｜ε验证：对A：FIRST(Ba)＝{b,d,a},FOLLOW(A)＝{#,b,d}；FIRST(Ba)∩FOLLOW(A)＝Ф对B′：FIRST(Db)＝{b},FOLLOW(B′)＝{#,a}；FIRST(Db)∩FOLLOW(B′)＝Ф对D：FIRST(d)＝{d},FOLLOW(D)＝{#,b}；FIRST(d)∩FOLLOW(D)＝Ф∴经验证,改写后的文法是LL(1)文法。(3)该文法不是LL(1)文法,因为产生式①存在左递归,产生式②存在左公因子。改写后文法：M→HM′①M′→aHM′｜ε②｜③H→bH′｜(M)④｜⑤H′→(M)｜ε⑥｜⑦验证：对②｜③：FIRST(aHM′)＝{a)∩FOLLOW(M′)＝(#,)}＝Ф对④｜⑤：FIRST(bH′)＝{b}∩FIRST((M))＝{(}＝Ф对⑥｜⑦：FIRST((M))＝{(}∩FOLLOW(H′)＝{#,a,)}＝Ф∴经验证,改写后的文法是LL(1)文法。(4)对给定文法设置编号：A→baB｜ε①B→Abb｜a②｜③对①：FIRST(baB)＝{b}∩FOLLOW(A)＝{b,#)≠Ф∴该文法不是LL(1)文法。对文法进行改写,将A代入B同时提取左公因子,则改写后文法为：A→baB｜ε①B→bB′｜a②B′→aBbb｜b③对①：FIRST(baB)＝{b}∩FOLLOW(A)＝{#)＝Ф对②：FIRST(bB′)＝(b)∩FIRST(a)＝{a}＝Ф对③：FIRST(aBbb)＝{a}∩FIRST(b)＝{6}＝Ф∴经验证,改写后的文法是LL(1)文法。(5)设有文法：A→aABe｜aB→Bb｜d该文法不是LL(1)文法,因为关于B的产生式有左递归,关于A的产生式存在左公因子。改写后文法：A→aA′A′→ABe→→B→dB′B′→bB′→→验证：对A′：FIRST(ABe)＝{a},FOLLOW(A′)＝{d,#),有FIRST(ABe)∩FOLLOW(A′)＝Ф对B′：FIRST(bB′)＝{b},FOLLOW(B′)＝{ε),有FIRST(bB′)∩FOLLOW(B′)＝Ф∴经验证,改写后的文法是LL(1)文法。(6)设有下列文法：S→Ab｜Ba①A→aA｜a②｜③B→a④｜⑤该文法不是LL(1)文法,因为非终结符A的产生式存在左公因子。提取左公因子改写后的文法G′如下：S→aS′／／①S′→aS〞｜b／／②③S〞→Ab｜b｜ε／／④⑤⑥A→aA′／／⑦⑧A′→A｜ε／／⑧⑨对S′：{a}∩{b}＝Ф对S〞：FOLLOW(S〞)＝{{#}∪{ε}}∩{b}∩{a}＝Ф对A′：FOLLOW(A′)＝{b}∩{a}＝Ф∴经验证,改写后的文法G′是LL(1)文法。