編譯原理典型例題

1、 /16根據(jù)FIRST和FOLLOW集合構(gòu)造預(yù)測(cè)分析表方法：對(duì)文法G的每個(gè)產(chǎn)生式A-a執(zhí)行第二步和第三步；(2)對(duì)每個(gè)終結(jié)符aeFIRST(a),把A-a加至MA,a中；(3)若cFIRST(a),則對(duì)任何beFOLLOW(A),把Aa加至MA,b中;(4)把所有無(wú)定義的MA,a標(biāo)上出錯(cuò)標(biāo)志。構(gòu)造預(yù)測(cè)分析表方法如下：*+a#SS*aPSSaPSSS*aPSSPP+aPPPPPP.設(shè)文法G(S):S(T)aSaTT,SS消除左遞歸和提公共左因子；構(gòu)造相應(yīng)的FIRST和FOLLOW集合;構(gòu)造預(yù)測(cè)分析表。解答消除左遞歸和提公共左因子，文法變?yōu)镚SS(L)aSSSLSLL,SL此文法沒(méi)有公共左因子(2

2、)構(gòu)造相應(yīng)的FIRST和FOLLOW集合FIRST(S)=a，(FIRST(S)=a,(,FIRST(L)=a,(FIRST(L)=,FOLLOW(S)=,),#FOLLOW(S)=,),#FOLLOW(L)=)FOLLOW(L)=)(3)構(gòu)造預(yù)測(cè)分析表()a,#SSf(L)SfaSSSfSSiSfSSfSiLLfSLLfSLLf,SLLLf.設(shè)文法GSS-(A)S-aA-A+SA-S(1)構(gòu)造每個(gè)非終結(jié)符的FIRSTVT和LASTVT集合；構(gòu)造優(yōu)先關(guān)系表；解答對(duì)于這類(lèi)題目，關(guān)鍵是準(zhǔn)確掌握FIRSTVT和LASTVT集合的定義和構(gòu)造方法。FIRSTVT(P)=alP+na-fP+nQa，aeV

3、T而QeVN即，對(duì)于非終結(jié)符P，其往下推導(dǎo)所可能出現(xiàn)的首個(gè)算符。LASTVT(P)=a|P+na或P+n.aQ，aeVT而QeVN即，對(duì)于非終結(jié)符P，其往下推導(dǎo)所可能出現(xiàn)的最后一個(gè)算符。構(gòu)造FIRSTVT和LASTVT集合的方法(1)構(gòu)造FIRSTV集合若有產(chǎn)生式Pa-或PQa，貝UaeFIRSTVT(P)；若有aeFIRSTVT(Q),且有產(chǎn)生式P-Q，則aeFIRSTVT(P)。(2)構(gòu)造LASTVT集合若有產(chǎn)生式Pa或PaQ,則aeLASTVT(P);若有aeLASTVT(Q)，且有產(chǎn)生式PQ,則aeLASTVT(P)。對(duì)于文法GS,構(gòu)造它的每個(gè)非終結(jié)符的FIRSTVT和LASTVT集合

4、：FIRSTVT(S)=a,(FIRSTVT(A)=+,a,(LASTVT(S)=a,)LASTVT(A)=+,a,)構(gòu)造算符優(yōu)先關(guān)系表方法：(1)=關(guān)系直接看產(chǎn)生式的右部,若出現(xiàn)了Pfab或PfaQb，則a=b(2)關(guān)系求出每個(gè)非終結(jié)符P的FIRSTVT(P)若PfaR，則VbFIRSTVT(R),a關(guān)系求出每個(gè)非終結(jié)符P的LASTVT(P)若PfRb，則VaLASTVT(B),ab對(duì)于文法GS,構(gòu)造它的算符優(yōu)先關(guān)系表如下：a+()a+(8.設(shè)文法G(S)：ST|SVTTUITaUUil-U(1)計(jì)算FIRSTVT和LASTVT；(2)構(gòu)造優(yōu)先關(guān)系表。解答(1)對(duì)于文法GS，構(gòu)造它的每個(gè)非終

5、結(jié)符的FIRSTVT和LASTVT集合。FIRSTVT(S)=V,A,i,-FIRSTVT(T)=A,i,-FIRSTVT(U)=i,-LASTVT(S)=V,A,i,-LASTVT(T)=A,i,-LASTVT(U)=i,-(2)構(gòu)造優(yōu)先關(guān)系表。iVAS.V.A.0八b0doifxythenb:=b-1elsea:=a-1;翻譯為四元式序列。解答對(duì)于這類(lèi)題目，關(guān)鍵是準(zhǔn)確掌握語(yǔ)句的語(yǔ)動(dòng)作。while-do語(yǔ)句的語(yǔ)義動(dòng)作if-then-else語(yǔ)句的語(yǔ)義動(dòng)作作為條件控制的布爾式的翻譯：把AorB解釋成ifAthentrueelseB把AandB解釋成ifAthenBelsefalse把notA解

6、釋成ifAthenfalseelsetrue布爾表達(dá)式賦予兩種“出口”：一是“真”出口；一是“假”出。假設(shè)四元式序列從100開(kāi)始編號(hào)。表達(dá)式a0翻譯為：100（j，a，0，_）101（j，_，_，_）繼續(xù)翻譯表達(dá)式a0Ab0,由于是與運(yùn)算，100號(hào)語(yǔ)句應(yīng)轉(zhuǎn)跳到102號(hào)語(yǔ)句，102號(hào)語(yǔ)句為“真”出口，101號(hào)語(yǔ)句和103號(hào)語(yǔ)句為“假”出，四元式序列為：100（j，a，0，102）101（j，_，_，_）102（j，b，0，_）103（j，_，_，_）繼續(xù)翻譯語(yǔ)句whilea0Ab0doifxywhile語(yǔ)句中的邏輯表達(dá)式的“真”出口應(yīng)轉(zhuǎn)跳到其循環(huán)體的第一個(gè)四元式標(biāo)號(hào)，即104號(hào)語(yǔ)句。100（j，

7、a，0，102）101（j，_，_，_）102（j，b，0，104）103（j，_，_，_）104（j，x，y_）105（j，_，_，_）if語(yǔ)句中的邏輯表達(dá)式的“真”出口為104號(hào)語(yǔ)句，應(yīng)轉(zhuǎn)跳到then中的第一個(gè)四元式標(biāo)號(hào)，“假”出口為105號(hào)語(yǔ)句，應(yīng)轉(zhuǎn)跳到else中的第一個(gè)四元式標(biāo)號(hào)。then中語(yǔ)句翻譯完，應(yīng)轉(zhuǎn)跳出去。100（j，a，0，102）101（j，_，_，_）102（j，b，0，104）103（j，_，_，_）104（j，x，y_）105（j，_，_，_）106（-，b，1，T1）107（:=，T1，_，b）108（j，_，_，_）109（-，a，1，T2）110（:=，T2，_

8、，a）while語(yǔ)句中循環(huán)體翻譯完，應(yīng)轉(zhuǎn)跳到while語(yǔ)句的第一個(gè)四元式標(biāo)號(hào)，即100號(hào)語(yǔ)句。while語(yǔ)句中的邏輯表達(dá)式的“假”出口應(yīng)轉(zhuǎn)跳到while語(yǔ)句后的第一個(gè)四元式標(biāo)號(hào)。100（j，a，0，102）101（j，_，_，112）102（j，b，0，104）103（j，_，_，112）104（j，x，y_）105（j，_，_，_）106（-，b，1，T1）107（:=，T1，_，b）108（j，_，_，100）109（-，a，1，T2）110（:=，T2，_，a）111（j，_，_，100）12.已知文法GS及相應(yīng)翻譯方案TOC o 1-5 h zSaAb1Sa2AAS3Ac4輸入acab,輸出是什么？解答對(duì)于這類(lèi)題目，首先畫(huà)出句子acab對(duì)應(yīng)的語(yǔ)法樹(shù)。每當(dāng)用一個(gè)產(chǎn)生式歸約時(shí)，則執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作。句子acab對(duì)應(yīng)的語(yǔ)法樹(shù)為：第一個(gè)歸約的產(chǎn)生式是Ac，它相應(yīng)的語(yǔ)義動(dòng)作為第一個(gè)歸約的產(chǎn)生式是Ac，它相應(yīng)的語(yǔ)義動(dòng)作為4”。所以，產(chǎn)生輸出4。第二個(gè)歸