北方工業(yè)大學(xué)編譯原理第4章習(xí)題

第四章語法分析-自上而下分析第四章語法分析-自上而下分析語法分析器的功能LL(1)分析法遞歸下降分析程序構(gòu)造預(yù)測(cè)分析程序考慮下面文法G[S]S→AaA→BBB→Sb︱c請(qǐng)消除該文法的左遞歸。和A的產(chǎn)生式都不含直接左遞歸。將S代入到B的候選后，B的產(chǎn)生式為：B→Aab︱c把A代入到B的候選后，B的產(chǎn)生式為：B→BBab︱c消除B的直接左遞歸，B的產(chǎn)生式為：B→cBB→BabB︱εS→AaA→BBS→AaA→BB或者S→AaA→BBB→cBB→BabB︱εB→cBB→cBabB︱ε試消除下面文法G[A中的左遞歸，并提取公共左因子，判斷改寫后的文法是否為L(zhǎng)L(1)文法?A→aABe∣aB→Bb∣d解:首先消除左遞歸A→aABe∣aB→dBB→bB|ε提取公共左因子A→aAA→ABe|εB→dBB→bB|ε該文法不含左遞歸，而且每一個(gè)兩不相交。FIRST(A)={a} FOLLOW(A)={d,#}FIRST(A)={ε,a} FOLLOW(A)={d,#}FIRST(B)=ewajaxz FOLLOW(B)={e}FIRST(B)={ε,b} FOLLOW(B)={e}證明：對(duì)于具有形如A|的產(chǎn)生式有：A→ABe|εB→bB|εFIRST(Abe)∩FOLLOW(A)={a}∩{d,#}=?FIRST(bB)∩FOLLOW(B)=∩{e}=?滿足LL(1)文法的條件，這個(gè)文法是LL(1)的。考慮下面文法G1:S→a∣∧∣(T)T→T,S∣S（1）消去G1的左遞歸。然后對(duì)每個(gè)非終結(jié)符，寫出不帶回溯的遞歸子程序。解：消除文法的直接左遞歸，得到文法G’(S):S→a∣∧∣(T)T→ST’T’→,ST’|εS、T、T′的遞歸子程序分別為：procedureS;beginifsym=′a′orsym=′∧′thenadvanceelseifsym=′(′thenbeginadvance;T;ifsym=′)′thenadvanceelseerrorendelseerror

procedureT′;beginifsym=′,′thenbeginadvance;S;T′end;end;end;procedureT;beginS;T′end;

解：消除文法的直接左遞歸，得到文法G’(S):S→a∣∧∣(T)T→ST’T’→,ST’|ε其中：過程advance把輸入串指示器IP調(diào)至指向下一個(gè)輸入符號(hào)；sym是指IP當(dāng)前所指的那個(gè)輸入符號(hào)；error為出錯(cuò)診斷處理程序。（2）經(jīng)改寫后的文法是否是LL(1)的？給出它的預(yù)測(cè)分析表。解：求每個(gè)非終結(jié)符號(hào)的FIRST和FPLLOW集合：FIRST(S)={a，∧，(}FIRST(T)={a，∧，(}FIRST(T’)={，，ε}FOLLOW(S)={)，，，#}FOLLOW(T）={)}FOLLOW(T’）={)}該文法的預(yù)測(cè)分析表為：

G’(S):S→T→ST’T’→,ST’|εa∧(),#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T’→εT→,ST’這個(gè)分析表不含有多重定義入口，故改寫后的文法是LL(1)的。對(duì)下面的文法E→TEE→+E∣εT→FTT→T∣εF→PFF→*F∣εP→(E)∣a∣b∣∧（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的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）證明這個(gè)文法是LL(1)的。證明：對(duì)于具有形如A|的產(chǎn)生式有：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)文法的條件，這個(gè)文法是LL(1)的。（3）構(gòu)造它的預(yù)測(cè)分析表。預(yù)測(cè)分析表+*()ab∧#EETEETEETEETEEE+EEεE->εTTFTTFTTFTTFTTTεTTTεTTTTTTTεFFPFFPFPPFFPFFFεF*FFεFεFεFεFεFεPP(E)PaPbP∧（4）構(gòu)造它的遞歸下降分析程序。利用預(yù)測(cè)分析表構(gòu)造該文法的遞歸下降分析程序，可使我們盡下：早的發(fā)現(xiàn)分析中出現(xiàn)的錯(cuò)誤。分析程序構(gòu)造如下：procedureE;beginifsym=ˊ(ˊorsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenbeginT;Eendelseerrorend;procedureE;beginifsym=ˊ+ˊthenbegin advance;E elseifsym≠ˊ)ˊand sym≠ˊ#ˊthenend;procedureT;beginifsym=ˊ(ˊorsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenbeginF;Tendelseerrorend;（4）構(gòu)造它的遞歸下降分析程序。procedureT;beginifsym=ˊ(ˊorsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenTelse ifsym=ˊ*ˊthenerrorend;procedureF;beginifsym=ˊ(ˊorsym=ˊaˊorsym=ˊbˊorsym=ˊ∧ˊthenbeginP;F endelseerrorend;procedureF;beginifsym=ˊ*ˊthenbeginadvance;Fendend;（4）構(gòu)造它的遞歸下降分析程序。proce