编译原理第4章.doc

《编译原理第4章.doc》由会员分享，可在线阅读，更多相关《编译原理第4章.doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、_第四章作业4.1 对下面文法，设计递归下降分析程序。SaAS|(A) , AAb|c解：将左递归去掉，将规则AAb|c 改成 Acb非终结符号S的分析程序如下：SINPUTSYM=aINPUTSYM=(INPUTSYM=下一个符号AINPUTSYM=下一个符号AINPUTSYM=)SINPUTSYM=下一个符号错误错误出口NNNYYY非终结符号A的分析程序如下：过程A INPUTSYM=cINPUTSYM=下一个符号YINPUTSYM=bN错误INPUTSYM=下一个符号Y出口N4.2 设有文法GZ： Z=(A) , A=a|Bb , B=Aab若采用递归下降分析方法，对此文法来说，在分析过

2、程中，能否避免回溯？为什么？解：若采用递归下降分析方法，对此文法来说，在分析过程中，不能避免回朔。因为A=a|Bb和B=Aab构成了间接的左递归，不满足实现没有回溯的递归下降分析方法的条件，因此在分析过程中，将造成回溯。4.3 若有文法如下，设计递归下降分析程序。 | ID= | |*|/ ID|NUM|()解：首先，去掉左递归（1）|改为： （3） | + | - 改为：（+ | -）（4） | * | / 改为：（* | /）则文法变为： ID= （+ | -） （* | /） ID|NUM|()非终结符号 的分析程序如下：语句INPUTSYM=IDNY赋值语句出口非终结符号 ID= 的分

3、析程序如下：赋值语句INPUTSYM=ID错误NINPUTSYM=下一个符号INPUTSYM=错误NINPUTSYM=下一个符号Y表达式出口非终结符号（+ | -） 的分析程序如下：表达式INPUTSYM=+NINPUTSYM=-INPUTSYM=下一个符号Y出口项NY非终结符号 （* | /） 的分析程序如下：复值语句的分析程序项INPUTSYM=*NINPUTSYM=/INPUTSYM=下一个符号Y出口因子NY项非终结符号 ID|NUM|() 的分析程序如下：NNYYY因子INPUTSYM=IDINPUTSYM=(INPUTSYM=下一个符号出口INPUTSYM=下一个符号表达式INPUT

4、SYM=(错误出口INPUTSYM=(NY4.4 有文法GA：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)文法；（3） 先将B:=Bb|b转成右递归，文法变为：A:=aABe|，B:=bB，B=bB|，因此该文法的LL(1)分析表为：aeb#APOP ，PUSH(eBAa)POPPOPBPOP ，PUSH(Bb)BPOPPOP ，PUSH(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)文法。9_