参考答案

正确答案：(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→ABA→BA｜εB→Db｜DD→d｜ε该文法不是LL(1)文法因为关于B的产生式存在左公因子。改写后文法：S→ABA→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｜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)文法。
设有下列文法：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)文法。