編譯原理第4章

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

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

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

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

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

6、|NUM|(<表達式>) 的分析程序如下：NNYYY因子INPUTSYM=IDINPUTSYM=(INPUTSYM=下一個符號出口INPUTSYM=下一個符號表達式INPUTSYM=(錯誤出口INPUTSYM=(NY4.4 有文法GA：A:=aABe|，B:=Bb|b（1）求每個非終結(jié)符號的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）說明該文法是LL(1)的文法。解：（1）FIRST(A)(, FOLLOW(A)，#（2）因為該文法中不含左遞歸；FIRST（(A)A）=