编译原理第4章

第四章作业4.1对下面文法，设计递归下降分析程序。S→aAS|(A),A→Ab|c解：将左递归去掉，将规则A→Ab|c改成A→c{b}非终结符号S的分析程序如下：非终结符号A的分析程序如下：SINPUTSYM=’a’INPUTSYM=’(’INPUTSYM=下一个符号AINPUTSYM=下一个符号AINPUTSYM=’)’SINPUTSYM=下一个符号错误错误出口NNNYYY4.2设有文法G[Z]：Z∷=(A),A∷=a|Bb,B∷=Aab若采用递归下降分析方法，对此文法来说，在分析过程中，能否避免回溯？为什么？解：若采用递归下降分析方法，对此文法来说，在分析过程中，不能避免回朔。因为A∷=a|Bb和B∷=Aab构成了间接的左递归，不满足实现没有回溯的递归下降分析方法的条件，因此在分析过程中，将造成回溯。4.3若有文法如下，设计递归下降分析程序。语句→语句赋值语句|ε赋值语句→ID=表达式过程AINPUTSYM=’c’INPUTSYM=下一个符号YINPUTSYM=’b’N错误INPUTSYM=下一个符号Y出口N表达式→项|表达式＋项|表达式－项项→因子|项*因子|项/因子因子→ID|NUM|(表达式)解：首先，去掉左递归（1）语句→语句赋值语句|ε改为：语句→{赋值语句}（3）表达式→项|表达式+项|表达式-项改为：表达式→项{（+|-）项}（4）项→因子|项*因子|项/因子改为：项→因子{（*|/）因子}则文法变为：语句→{赋值语句}赋值语句→ID=表达式表达式→项{（+|-）项}项→因子{（*|/）因子}因子→ID|NUM|(表达式)非终结符号语句→{赋值语句}的分析程序如下：非终结符号赋值语句→ID=表达式的分析程序如下：语句INPUTSYM=’ID’NY赋值语句出口赋值语句INPUTSYM=’ID’错误NINPUTSYM=下一个符号INPUTSYM=’=’错误NINPUTSYM=下一个符号Y表达式出口非终结符号表达式→项{（+|-）项}的分析程序如下：非终结符号项→因子{（*|/）因子}的分析程序如下：表达式INPUTSYM=’+’NINPUTSYM=’-’INPUTSYM=下一个符号Y出口项NY非终结符号因子→ID|NUM|(表达式)的分析程序如下：项INPUTSYM=’*’NINPUTSYM=’/’INPUTSYM=下一个符号Y出口因子NY项4.4有文法G[A]：A::=aABe|ε，B::=Bb|b（1）求每个非终结符号的FOLLOW集。（2）该文法是LL(1)文法吗？（3）构造LL(1)分析表。解：（1）FOLLOW(A)=First(B)∪{#}={b,#}FOLLOW(B)={e,b}（2）B::=Bb|b为左递归，因此该文法不是LL(1)文法；NNYYY因子INPUTSYM=’ID’INPUTSYM=’(’INPUTSYM=下一个符号出口INPUTSYM=下一个符号表达式INPUTSYM=’(’错误出口INPUTSYM=’(’NY（3）先将B::=Bb|b转成右递归，文法变为：A::=aABe|ε，B::=bB’，B’=bB’|ε，因此该文法的LL(1)分析表为：aeb#APOP，PUSH(eBAa)POPPOPBPOP，PUSH(B’b)B’POPPOP，PUSH(B’b)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)文法。