作业解答第章.doc

4.1 对下面文法，设计递归下降分析程序。 S→aAS|(A) , A→Ab|c 解： 首先将左递归去掉，将规则A→Ab|c 改成 A→c{b} 非终结符号S的分析程序如下： 非终结符号A的分析程序如下： 4.2 设有文法G[Z]： Z∷=(A) , A∷=a|Bb , B∷=Aab 若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？ 解：若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。因为规则A∷=a|Bb和规则B∷=Aab构成了间接左递归，不满足实现没有回溯的递归下降分析方法的条件（1）（书P67），且规则 A: := a|Bb，FIRST(a)={a}，FIRST(Bb)={a}，即此规则候选式的首符号集有相交，不满足实现没有回溯的递归下降分析方法的条件（2）（书P67），在分析过程中，将造成回溯。 改写文法可避免回溯： 将规则B∷=Aab代入规则A∷=a|Bb得：A∷=a|Aabb，再转换成：A∷=a{abb}，可避免回溯。 4.3 若有文法如下，设计递归下降分析程序。 语句→语句赋值语句|ε 赋值语句→ID=表达式 表达式→项|表达式＋项|表达式－项 项→因子|项*因子|项/因子 因子→ID|NUM|(表达式) 解：首先，去掉左递归 语句→语句赋值语句|ε改为： 语句→{赋值语句} 表达式→项 | 表达式 + 项 | 表达式 - 项 改为： 表达式→项{（+ | -）项} 项→因子 | 项 * 因子 | 项 / 因子 改为： 项→因子{（* | /）因子} 则文法变为： 语句→{赋值语句} 赋值语句→ID=表达式 表达式→项{（+ | -）项} 项→因子{（* | /）因子} 因子→ID|NUM|(表达式) 非终结符号 语句 的分析程序如下： 非终结符号 赋值语句 的分析程序如下： 非终结符号 表达式 的分析程序如下： 非终结符号 项 的分析程序如下： 非终结符号 因子 的分析程序如下： 4.4 有文法G[A]：A::=aABe|ε，B::=Bb|b （1）求每个非终结符号的FOLLOW集。 （2）该文法是LL(1)文法吗？ （3）构造LL(1)分析表。 解： FOLLOW(A)=First(B)∪{#}={b,#} FOLLOW(B)={e,b} 该文法中的规则B::=Bb|b为左递归，因此该文法不是LL(1)文法 先消除文法的左递归（转成右递归），文法变为：A::=aABe|ε，B::=bB’，B’=bB’|ε，该文法的LL(1)分析表为： a e b # A POP ， PUSH(eBAa) POP POP B POP ， PUSH(B’b) B’ POP POP ， PUSH(B’b) a POP, NEXTSYM e POP, NEXTSYM b POP, NEXTSYM # ACCEPT 更常用且简单的LL(1)分析表： a e b # A A→aABe A→ε A→ε B B→bB’ B’ B’→ε B’→bB’ 4.5 若有文法A→(A)A|ε （1）为非终结符A构造FIRST集合和FOLLOW集合。 （2）说明该文法是LL(1)的文法。 解： （1）FIRST(A)＝｛(, ε｝ FOLLOW(A)＝｛)，#｝ （2） 该文法不含左递归； FIRST（(A)A）={(}，FIRST（ε）={ε}，FIRST（(A)A）∩FIRST（ε）=Φ， 且FOLLOW(A)＝｛)，#｝，FIRST（(A)A）∩ FOLLOW(A) =Φ， 因此，该文法满足LL(1)文法的条件，是LL(1)文法。 4.6 利用分析表4-1，识别以下算术表达式，请写出分析过程。 （1）i+i*i+i （2）i*(i+i+i) 解： （1）i+i*i+i 步骤 分析栈 余留输入串 分析表元素 所用产生式 1 #E i+i*i+i# POP,PUSH(E’T) E→TE’ 2 #E’T i+i*i+i# POP,PUSH(T’F) T→FT’ 3 #E’T’F i+i*i+i# POP,PUSH(i) F→i 4 #E’T’i i+i*i+i# POP,NEXTSYM 5 #E’T’ +i*i+i# POP T’→ε 6 #E’ +i*i+i# POP,PUSH(E’T+) E’→+TE’ 7 #E’T+ +i*i+i# POP,NEXTSYM 8 #E’T i*i+i# POP,PUSH(T’F) T→FT’ 9 #E