参考答案

正确答案：(1)因为文法含有左递归所以文法不是LL(1)文法。考虑该文法对应的语言为正规式(a｜b)*ab｜b描述的集合。文法改写为：S→aA｜bBA→aA｜bBB→aA｜bC｜εC→aA｜bCC→aA｜bC对改写的文法验证：对S：FIRST(aA)＝{a}FIRST(bB)＝{b}有FIRST(aA)∩FIRST(bB)＝Ф对A：FIRST(aA)＝{a}FIRST(bB)＝{b}有FIRST(aA)∩FIRST(6B)＝Ф对B：FIRST(bC)＝{b}FIRST(aA)＝{a}FOLLOW(B)＝{#}且3个集合彼此不相交对C：FIRST(bC)＝{b}FIRST(aA)＝{a}有FIRST(aA)∩FIRST(6C)＝Ф∴经验证改写后的文法是LL(1)文法。(2)对文法S→aSbS｜bSaS｜ε验证：FIRST(aSbS)＝{a} FIRST(bSaS)＝{b} FOLLOW(S)＝{ab}且3个集合的交集不为空集。∴文法不是LL(1)文法。考虑文法对应的语言为含有相同个数的a、b串。文法改写为：S→aBS｜bAS｜εA→a｜bAA B→b｜aBB对改写的文法验证：对S：FIRST(aBS)＝{a}FIRST(bAS)＝{b}FOLLOW(S)＝{#}且3个集合的交集不为空集。对A：FIRST(a)＝{a}FIRST(6AA)＝{b}有FIRST(a)∩FIRST(6AA)＝Ф对B：FIRST(b)＝{b}FIRST(aBB)＝{a}有FIRST(b)∩FIRST(aBB)＝Ф∴经验证改写后的文法是LL(1)文法。(3)因为文法含有左递归所以文法不是LL(1)文法。文法改写为：S→A A→BA｜ε B｜aB｜b(或S→aA｜bS｜ε A→a｜A｜bS)对改写的文法验证：对S：FIRST(A)＝{ab}∪{ε}FOLLOW(S)＝{#}有FIRST(A)∩FOLLOW(S)＝Ф对A：FIRST(a)＝{a}FIRST(bAA)＝{b}有FIRST(a)∩FIRST(bAA)＝Ф对B：FIRST(b)＝{b}FIRST(aBB)＝{a}有FIRST(b)∩FIRST(aBB)＝Ф∴经验证改写后的文法是LL(1)文法。
因为文法含有左递归,所以文法不是LL(1)文法。考虑该文法对应的语言为正规式(a｜b)*ab｜b描述的集合。文法改写为：S→aA｜bBA→aA｜bBB→aA｜bC｜εC→aA｜bCC→aA｜bC对改写的文法验证：对S：FIRST(aA)＝{a},FIRST(bB)＝{b},有FIRST(aA)∩FIRST(bB)＝Ф对A：FIRST(aA)＝{a},FIRST(bB)＝{b},有FIRST(aA)∩FIRST(6B)＝Ф对B：FIRST(bC)＝{b},FIRST(aA)＝{a},FOLLOW(B)＝{#},且3个集合彼此不相交对C：FIRST(bC)＝{b},FIRST(aA)＝{a},有FIRST(aA)∩FIRST(6C)＝Ф∴经验证,改写后的文法是LL(1)文法。(2)对文法S→aSbS｜bSaS｜ε验证：FIRST(aSbS)＝{a},FIRST(bSaS)＝{b},FOLLOW(S)＝{a,b}且3个集合的交集不为空集。∴文法不是LL(1)文法。考虑文法对应的语言为含有相同个数的a、b串。文法改写为：S→aBS｜bAS｜εA→a｜bAAB→b｜aBB对改写的文法验证：对S：FIRST(aBS)＝{a},FIRST(bAS)＝{b},FOLLOW(S)＝{#}且3个集合的交集不为空集。对A：FIRST(a)＝{a},FIRST(6AA)＝{b},有FIRST(a)∩FIRST(6AA)＝Ф对B：FIRST(b)＝{b},FIRST(aBB)＝{a},有FIRST(b)∩FIRST(aBB)＝Ф∴经验证,改写后的文法是LL(1)文法。(3)因为文法含有左递归,所以文法不是LL(1)文法。文法改写为：S→AA→BA｜εB｜aB｜b(或S→aA｜bS｜εA→a｜A｜bS)对改写的文法验证：对S：FIRST(A)＝{a,b}∪{ε},FOLLOW(S)＝{#},有FIRST(A)∩FOLLOW(S)＝Ф对A：FIRST(a)＝{a},FIRST(bAA)＝{b},有FIRST(a)∩FIRST(bAA)＝Ф对B：FIRST(b)＝{b},FIRST(aBB)＝{a},有FIRST(b)∩FIRST(aBB)＝Ф∴经验证,改写后的文法是LL(1)文法。