编译原理作业4解答

《编译原理作业4解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、4.1对下面文法，设计递归下降分析程序。S→aAS

2、(A),A→Ab

3、c首先将左递归去掉，将规则A→Ab

4、c改成A→c{b}过程SINPUTSYM=’a’INPUTSYM=下一个符号YNINPUTSYM=’(’INPUTSYM=下一个符号YINPUTSYM=’)’INPUTSYM=下一个符号YNN出口错误错误过程A过程S过程A非终结符号S的分析程序INPUTSYM=下一个符号错误INPUTSYM=’b’YINPUTSYM=下一个符号INPUTSYM=’c’过程AN非终结符号A的分析程序N出口Y4.2设有文法G[Z]：Z∷=(A),A∷=a

5、Bb,B∷=Aab若采用递归下降分析方

6、法，对此文法来说，在分析过程中，能否避免回溯？为什么？若采用递归下降分析方法，对此文法来说，在分析过程中不能避免回朔。规则A::=a

7、Bb,FIRST(a)={a},FIRST(Bb)={a},即此规则候选式的首符号集有相交，需要通过规则带入使候选式的第一个符号相同，然后提取公因子。但通过规则带入后最后一个候选式总是以B开头，而FIRST(B)={a},所以无法提取出a,候选式的首符号集总是相交。但可将B规则代入A规则得：A∷=a

8、Bb转换成A∷=a{abb}即可避免回溯。4.3若有文法如下，设计递归下降分析程序。<语句>→<语句><赋值语句>

9、ε<赋值语句>→Id=<表达式>

10、；<表达式>→<项>

11、<表达式>+<项>

12、<表达式>-<项><项>→<因子>

13、<项>*<因子>

14、<项>/<因子><因子>→ID

15、NUM

16、(<表达式>)去掉左递归，将规则<语句>→<语句><赋值语句>

17、ε改为<语句>→{<赋值语句>}，FIRST(<赋值语句>)={ID}<表达式>→<项>

18、<表达式>+<项>

19、<表达式>-<项>改为<表达式>→<项>{（+

20、-）<项>}<项>→<因子>

21、<项>*<因子>

22、<项>/<因子>改为<项>→<因子>{（*

23、/）<因子>}语句YNINPUTSYM=’ID’出口赋值语句语句的分析程序赋值语句出口表达式YINPUTSYM=下一个符号错误NINP

24、UTSYM=’=’INPUTSYM=下一个符号N错误INPUTSYM=’ID’Y赋值语句的分析程序INPUTSYM=下一个符号NINPUTSYM=’+’项表达式YY出口NINPUTSYM=’-’复值语句的分析程序表达式的分析程序项出口YINPUTSYM=下一个符号INPUTSYM=’/’NINPUTSYM=’*’项YN因子项的分析程序因子的分析程序INPUTSYM=’)’N错误表达式YINPUTSYM=下一个符号INPUTSYM=’NUM’YYN出口INPUTSYM=下一个符号INPUTSYM=’ID’因子NINPUTSYM=’(’错误Y