編譯原理第4章

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第四章作業(yè)4.1 對(duì)下面文法，設(shè)計(jì)遞歸下降分析程序。 SaAS|(A) , AAb|c解：將左遞歸去掉，將規(guī)則AAb|c 改成 Acb非終結(jié)符號(hào)S的分析程序如下：SINPUTSYM=aINPUTSYM=(INPUTSYM=下一個(gè)符號(hào)AINPUTSYM=下一個(gè)符號(hào)AINPUTSYM=)SINPUTSYM=下一個(gè)符號(hào)錯(cuò)誤錯(cuò)誤出口NNNYYY非終結(jié)符號(hào)A的分析程序如下：過(guò)程A INPUTSYM=cINPUTSYM=下一個(gè)符號(hào)YINPUTSYM=bN錯(cuò)誤INPUTSYM=下一個(gè)符號(hào)Y出口N4.2 設(shè)有文法GZ： Z=(A) , A=a|Bb , B=Aab若采用遞歸下降分析方

2、法，對(duì)此文法來(lái)說(shuō)，在分析過(guò)程中，能否避免回溯？為什么？解：若采用遞歸下降分析方法，對(duì)此文法來(lái)說(shuō)，在分析過(guò)程中，不能避免回朔。因?yàn)锳=a|Bb和B=Aab構(gòu)成了間接的左遞歸，不滿足實(shí)現(xiàn)沒(méi)有回溯的遞歸下降分析方法的條件，因此在分析過(guò)程中，將造成回溯。4.3 若有文法如下，設(shè)計(jì)遞歸下降分析程序。 <語(yǔ)句><語(yǔ)句><賦值語(yǔ)句>| <賦值語(yǔ)句>ID=<表達(dá)式> <表達(dá)式><項(xiàng)>|<表達(dá)式><項(xiàng)>|<表達(dá)式><項(xiàng)> <項(xiàng)><因子>|<項(xiàng)>*

3、<因子>|<項(xiàng)>/<因子> <因子>ID|NUM|(<表達(dá)式>)解：首先，去掉左遞歸（1）<語(yǔ)句><語(yǔ)句><賦值語(yǔ)句>|改為： <語(yǔ)句><賦值語(yǔ)句>（3）<表達(dá)式><項(xiàng)> | <表達(dá)式> + <項(xiàng)> | <表達(dá)式> - <項(xiàng)> 改為：<表達(dá)式><項(xiàng)>（+ | -）<項(xiàng)>（4）<項(xiàng)><因子> | <項(xiàng)> * <因子> | &

4、lt;項(xiàng)> / <因子> 改為：<項(xiàng)><因子>（* | /）<因子>則文法變?yōu)椋?lt;語(yǔ)句><賦值語(yǔ)句> <賦值語(yǔ)句>ID=<表達(dá)式> <表達(dá)式><項(xiàng)>（+ | -）<項(xiàng)> <項(xiàng)><因子>（* | /）<因子> <因子>ID|NUM|(<表達(dá)式>)非終結(jié)符號(hào) <語(yǔ)句><賦值語(yǔ)句> 的分析程序如下：語(yǔ)句INPUTSYM=IDNY賦值語(yǔ)句出口非終結(jié)符號(hào) <賦值語(yǔ)句>ID=

5、<表達(dá)式> 的分析程序如下：賦值語(yǔ)句INPUTSYM=ID錯(cuò)誤NINPUTSYM=下一個(gè)符號(hào)INPUTSYM=錯(cuò)誤NINPUTSYM=下一個(gè)符號(hào)Y表達(dá)式出口非終結(jié)符號(hào)<表達(dá)式><項(xiàng)>（+ | -）<項(xiàng)> 的分析程序如下：表達(dá)式INPUTSYM=+NINPUTSYM=-INPUTSYM=下一個(gè)符號(hào)Y出口項(xiàng)NY非終結(jié)符號(hào) <項(xiàng)><因子>（* | /）<因子> 的分析程序如下：復(fù)值語(yǔ)句的分析程序項(xiàng)INPUTSYM=*NINPUTSYM=/INPUTSYM=下一個(gè)符號(hào)Y出口因子NY項(xiàng)非終結(jié)符號(hào) <因子>ID

6、|NUM|(<表達(dá)式>) 的分析程序如下：NNYYY因子INPUTSYM=IDINPUTSYM=(INPUTSYM=下一個(gè)符號(hào)出口INPUTSYM=下一個(gè)符號(hào)表達(dá)式INPUTSYM=(錯(cuò)誤出口INPUTSYM=(NY4.4 有文法GA：A:=aABe|，B:=Bb|b（1）求每個(gè)非終結(jié)符號(hào)的FOLLOW集。（2）該文法是LL(1)文法嗎？（3）構(gòu)造LL(1)分析表。解：（1） FOLLOW(A)=First(B)#=b,# FOLLOW(B)=e,b（2） B:=Bb|b為左遞歸，因此該文法不是LL(1)文法；（3） 先將B:=Bb|b轉(zhuǎn)成右遞歸，文法變?yōu)椋篈:=aABe|，B:=bB，B=bB|，因此該文法的LL(1)分析表為：aeb#APOP ，PUSH(eBAa)POPPOPBPOP ，PUSH(Bb)BPOPPOP ，PUSH(Bb)4.5 若有文法A(A)A|（1）為非終結(jié)符A構(gòu)造FIRST集合和FOLLOW集合。（2）說(shuō)明該文法是LL(1)的文法。解：（1）FIRST(A)(, FOLLOW(A)，#（2）因?yàn)樵撐姆ㄖ胁缓筮f歸；FIRST（(A)A）=