北方工业大学编译原理第4章习题

第四章语法分析-自上而下分析4.1语法分析器的功能4.2自上而下分析面临的问题4.3LL(1)分析法4.4递归下降分析程序构造4.5预测分析程序4.1考虑下面文法G[S]S→AaA→BBB→Sb︱c请消除该文法的左递归。解：非终结符排序为S，A，B，S和A的产生式都不含直接左递归。将S代入到B的候选后，B的产生式为：B→Aab︱c把A代入到B的候选后，B的产生式为：B→BBab︱c消除B的直接左递归，B的产生式为：B→cBB→BabB︱ε消除左递归后的文法为：S→AaS→AaA→BB或者A→BBB→cBB→cBB→BabB︱εB→cBabB︱ε4.2试消除下面文法G[A]中的左递归，并提取公共左因子，判断改写后的文法是否为LL(1)文法?A→aABe∣aB→Bb∣d解:（1）首先消除左递归A→aABe∣aB→dBB→bB|ε（2）提取公共左因子A→aAA→ABe|εB→dBB→bB|ε（3）该文法不含左递归，而且每一个非终结符的各个产生式的候选首符集两两不相交。FIRST(A)={a}FOLLOW(A)={d,#}FIRST(A)={ε,a}FOLLOW(A)={d,#}FIRST(B)={d}FOLLOW(B)={e}FIRST(B)={ε,b}FOLLOW(B)={e}证明：对于具有形如A|的产生式有：A→ABe|εB→bB|εFIRST(Abe)∩FOLLOW(A)={a}∩{d,#}=ØFIRST(bB)∩FOLLOW(B)={b}∩{e}=Ø满足LL(1)文法的条件，这个文法是LL(1)的。4.3考虑下面文法G1:（1）消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。S→a∣∧∣(T)T→T,S∣S解：消除文法的直接左递归，得到文法G’(S):S→a∣∧∣(T)T→ST’T’→,ST’|εS、T、T′的递归子程序分别为：procedureS;beginifsym=′a′orsym=′∧′thenadvanceelseifsym=′(′thenbeginadvance;T;ifsym=′)′thenadvanceelseerrorendelseerrorend;procedureT;beginS;T′end;procedureT′;beginifsym=′,′thenbeginadvance;S;T′end;end;其中：过程advance把输入串指示器IP调至指向下一个输入符号；sym是指IP当前所指的那个输入符号；error为出错诊断处理程序。解：消除文法的直接左递归，得到文法G’(S):S→a∣∧∣(T)T→ST’T’→,ST’|ε（2）经改写后的文法是否是LL(1)的？给出它的预测分析表。G’(S):S→a∣∧∣(T)T→ST’T’→,ST’|ε解：求每个非终结符号的FIRST和FPLLOW集合：FIRST(S)={a，∧，(}FIRST(T)={a，∧，(}FIRST(T’)={，，ε}FOLLOW(S)={)，，，#}FOLLOW(T）={)}FOLLOW(T’）={)}该文法的预测分析表为：a∧(),#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T’→εT→,ST’这个分析表不含有多重定义入口，故改写后的文法是LL(1)的。4.4对下面的文法G：E→TEE→+E∣εT→FTT→T∣εF→PFF→*F∣εP→(E)∣a∣b∣∧（1）计算这个文法的每个非终结符的FIRST和FOLLOW。解：FIRST（E）={(，a，b，∧}FIRST（E）={+，ε}FIRST（T）={(，a，b，∧}FIRST（T）={(，a，b，∧，ε}FIRST（F）={(，a，b，∧}FIRST（F）={*，ε}FIRST（P）={(，a，b，∧}FOLLOW（E）={#，)}FOLLOW（E）={#，)}FOLLOW（T）={+，)，#}FOLLOW（T）={+，)，#}FOLLOW（F）={(，a，b，∧，+，)，#}FOLLOW（F）={(，a，b，∧，+，)，#}FOLLOW（P）={*，(，a，b，∧，+，)，#}（2）证明这个文法是LL(1)的。证明：对于具有形如A|的产生式有：E→+E∣εT→T∣εF→*F∣εP→(E)∣a∣b∣∧FIRST(+E)∩FOLLOW(E)={+}∩{#，)}=ØFIRST(T)∩FOLLOW(T)={(，a，b，∧}∩{+，)，#}=ØFIRST(*F)∩FOLLOW(F)={*}∩{(，a，b，∧，+，)，#}=ØFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(∧)=Ø满足LL(1)文法的条件，这个文法是LL(1)的。（3）构造它的预测分析表。+*()ab∧#EETEETEETEETEEE+EEεE-εTTFTTFTTFTTFTTTεTTTεTTTTTTTεFFPFFPFPPFFPFFFεF*FFεFεFεFεFεFεPP(E)PaPbP∧预测分析表（4）构造它的递归下降分析程序。利用预测分析表构造该文法的递归下降分析程序，可使我们尽早的发现分析中出现的错误。分析程序构造如下：procedureE;beginifsym=ˊ(ˊorsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenbeginT;Eendelseerrorend;procedureE;beginifsym=ˊ+ˊthenbeginadvance;Eendelseifsym≠ˊ)ˊandsym≠ˊ#ˊthenerrorend;procedureT;beginifsym=ˊ(ˊorsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenbeginF;Tendelseerrorend;（4）构造它的递归下降分析程序。procedureT;beginifsym=ˊ(ˊorsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenTelseifsym=ˊ*ˊthenerrorend;procedureF;beginifsym=ˊ(ˊorsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenbeginP;Fendelseerrorend;procedureF;beginifsym=ˊ*ˊthenbeginadvance;Fendend;（4）构造它的递归下降分析程序。procedureP;beginifsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenadvanceelseifsym=ˊ(ˊthenbeginadvance;E;ifsym=ˊ)ˊthenadvanceelseerrorendelseerrorend;