編譯原理習(xí)題(含歷年專業(yè)考試題)課件

1、編譯原理習(xí)題(含歷年專業(yè)考試題)編譯原理第一章-第六章補(bǔ)充編譯原理習(xí)題(含歷年專業(yè)考試題)例1文法 GP 及相應(yīng)翻譯方案為： P bQb print: ” 1 ” Q cR print: ” 2 ” Q a print: ” 3 ” R Qad (print: ” 4 ” （ 1) 該文法是不是算符優(yōu)先文法，請構(gòu)造算符優(yōu)先關(guān)系表證實之。 (2) 輸入串為 bcccaadadadb 時，該翻譯方案的輸出是什么。 編譯原理習(xí)題(含歷年專業(yè)考試題)(1）文法GP的每個非終結(jié)符的FIRSTVT集和LASTVT集如下： FIRSTVT(P)=b；FIRSTVT(Q)=a,c； FIRSTVT(R)=a,

2、c； LASTVT(P)=b；LASTVT(Q)=a,c； LASTVT(R)=d)。 構(gòu)造優(yōu)先關(guān)系表：由表3.19可看出：終結(jié)符對（c,a )存在著兩種優(yōu)先關(guān)系和，故文法G不是一個算符優(yōu)先文法。P bQb print: ” 1 ” Q cR print: ” 2 ” Q a print: ” 3 ” R Qad (print: ” 4 ” 編譯原理習(xí)題(含歷年專業(yè)考試題)P bQb print: ” 1 ” Q cR print: ” 2 ” Q a print: ” 3 ” R Qad (print: ” 4 ” (2)對輸入串bcccaadadadb,畫出其語法樹，。 采用修剪語法樹的辦

3、法，按句柄方式自下而上歸約語法樹，每當(dāng)一個產(chǎn)生式得到匹配（歸約）時執(zhí)行相應(yīng)的語義動作。因此，第一個句柄匹配的產(chǎn)生式為Qa,執(zhí)行相應(yīng)的語義動作：打印3;第二個句柄匹配的產(chǎn)生式為RQad,執(zhí)行相應(yīng)的語義動作：打印4；。由此得到最終的翻譯結(jié)果為：。編譯原理習(xí)題(含歷年專業(yè)考試題)1. 語法分析之所以采用上下文無關(guān)文法是因為它的描述能力最強(qiáng)。（） 2. 欲構(gòu)造行之有效的自上而下分析器，則必須消除左遞歸。（） 3. 文法 ( SaS|bcS| ) 描述的語言是（ a|bc ） * ( ) 4. 在自下而上的語法分析中，語法樹與分析樹一定相同。（ ） 5. 二義文法不是上下文無關(guān)文法.（ ） 6. 每一個

4、算符優(yōu)先文法，必定能找到一組優(yōu)先函數(shù)與之對應(yīng)。7. 語法分析時必須先消除文法中的左遞歸。（） 8. 規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。（） 9. 一個文法所有句型的集合形成該文法所能接受的語言。（） 10. LL(1) 文法一定不含左遞歸和二義性。（） 編譯原理習(xí)題(含歷年專業(yè)考試題)已知文法 GS ： S dAB A aA|a B Bb| （1） 試問 GS 是否為正規(guī)文法，為什么？ （2） GS 所產(chǎn)生的語言是什么？ （3） GS 能否改寫為等價的正規(guī)文法 ?答：(1)因為S dAB不符合正規(guī)文法產(chǎn)生式AaB或Aa, aVT* ,A,BVN的格式，故GS不是正規(guī)文法。 (2) GS產(chǎn)生的

5、語言為： L=danbm|n1,m0 (3)可以得到GS對應(yīng)的正規(guī)文法GS: SdA AaA|aB|a BbB|編譯原理習(xí)題(含歷年專業(yè)考試題)給出文法 G1 ： S aSb|P P bPc|bQc Q Qa|a （ 1) 它是 Chomsky 哪一型文法？ （ 2 ）它生成的語言是什么？ 根據(jù)Chomsky的定義，對任何形如A的產(chǎn)生式，有AVN，(VTVN)*時為2型文法。而文法G1恰好滿足這一要求，故為Chomsky 2型文法。 (2)由文法Gl可以看出：S推出串的形式是aiPbi(i0), P推出串的形式是bjQcj(j1), Q推出串的形式是ak(k1).因此，文法G1生成的語言是L=

6、aibjakcjbi|i0,jl,k1 。編譯原理習(xí)題(含歷年專業(yè)考試題)已知文法 GS: S S*aP|aP|*aP P +aP|+a （1）將文法 GS 改寫為 LL(1 ）文法 G S 。 （2） 寫出文法 G S 的預(yù)測分析表。編譯原理習(xí)題(含歷年專業(yè)考試題) 文法 GM 是否 LL(1) 的，說明理由。 GM ： M TB T Ba| B Db|eT| D d| 編譯原理習(xí)題(含歷年專業(yè)考試題)設(shè)有文法 GS ： S SAS|b A bSb|b 試構(gòu)造一個與其等價的算符文法。經(jīng)分析可知GS產(chǎn)生的句子為奇數(shù)個b,其正規(guī)式為b(bb)*,由此得到NFA,編譯原理習(xí)題(含歷年專業(yè)考試題)令

7、S對應(yīng)狀態(tài)X, A對應(yīng)狀態(tài)Y, B對應(yīng)狀態(tài)1，我們得到改寫的文法GS為： GS：SbA|b AbB BbA|b 對文法GS求FIRSTOP集與LASTOP集如下： FIRSTOP(S)=b；FIRSTOP(A)=b；FIRSTOP(B)=b； LASTOP(S)=b；LASTOP(A)=b； LASTOP(B)=b 。由于文法GS只存在形如P.aR.的產(chǎn)生式，則： 由SbA得bFIRSTOP(A），即bb； 由AbB得bFIRSTOP(B），即b b；由于終結(jié)符對（b,b)僅滿足一種優(yōu)先關(guān)系，故為算符優(yōu)先文法。編譯原理習(xí)題(含歷年專業(yè)考試題)1. LR 分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤

8、，但不能準(zhǔn)確地指出出錯地點(diǎn)。 （） 2. 構(gòu)造 LR 分析器的任務(wù)就是產(chǎn)生 LR 分析表。 （） 3 .LR 文法肯定是無二義的，一個無二義文法決不會是 LR 文法。 （） 4. 在任何時候，分析棧的活前綴 X1X2.Xm 的有效項目集就是棧頂狀態(tài) Sm 所在的那個 項目集。 （） 5 同心集的合并有可能產(chǎn)生新的“移進(jìn)”“歸約”沖突。 （） 6. 由于 LR(0) 分析表構(gòu)造簡單，所以它的描述能力強(qiáng)、適用面寬； LR(1) 分析表因構(gòu)造復(fù)雜而描述能力弱、適用面窄。 （） 7 所有 LR 分析器的總控程序都是一樣的，只是分析表各有不同。 （） 8. LR 分析技術(shù)無法適用二義文法。 （） 9.

9、項目 A 1 2 對活前綴 1 是有效的，其條件是存在規(guī)范推導(dǎo) S*= aAW= a 1 2 。 （） 10. SLR(1) 文法的特點(diǎn)是：當(dāng)符號棧中的符號串為，而面臨的輸入符號為則存在 把歸約為 A 的規(guī)范句型的前綴 A 時，方可把 a 歸約為 A 。 （ ） 編譯原理習(xí)題(含歷年專業(yè)考試題)文法 G 的產(chǎn)生式如下： S BB B aB|b 請分別構(gòu)造該文法的（ 1) LR (0 ）分析表； (2 ） SLR 分析表； (3 ）規(guī)范 LR 分析表（即 LR （ 1 ）分析表）；（ 4 ） LALR 分析表。 答：（1）將文法G拓廣為文法G： 0）SS I）SBB 2）BaB 3）Bb編譯原理

10、習(xí)題(含歷年專業(yè)考試題)構(gòu)造SLR分析表必須先求出形如Aa.的FOLLOW (A)，即對文法G的 Bb SBB BaB求FOLLOW集，由FOLLOW的構(gòu)造文法得： FOLLOW（S）； FIRST（B）cFOLLOW（B），即FOLLOW（B）a,b； 由SS得：FOLLOW（S）FOLLOW（S），即FOLLOW（S）； 由SBB得：FOLLOW（S） FOLLOW（B），即FOLLOW（B）a,b，。 根據(jù)SLR(1)分析表的構(gòu)造方法得文法G的SLR(1)分析表，見表4.2。編譯原理習(xí)題(含歷年專業(yè)考試題)編譯原理習(xí)題(含歷年專業(yè)考試題)（4）構(gòu)造LALR分析表 根據(jù)LR (1)項目集族

11、，將同心集合并在一起，即將圖4.4中的I3與I6、I勺與I7以及I8與I9分別合并成： I36: BaB,a/b/# I47: Bba/b/# BaB,a/b/# I89：BaB,a/b/# Bb,a/b/# 由合并后的集族按照LALR分析表的構(gòu)造算法得到LALR分析表，見表4.4.由此表看出，它與SLR表是相同的。注意，這是因為文法G既可以用SLR構(gòu)造又可以用LALR構(gòu)造。但有些文法卻只能用LALR構(gòu)造而不能用SLR構(gòu)造。 編譯原理習(xí)題(含歷年專業(yè)考試題)LR (0), SLR(1), LR(1)及LALR的共同特征就是用規(guī)范歸約的方法尋找句柄，即LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)行輸

12、入符號所唯一決定的。它們的本質(zhì)區(qū)別是尋找句柄的方法不同。如果當(dāng)前的棧頂狀態(tài)為歸約狀態(tài)（即有形如Aa的項目屬于棧頂狀態(tài)），則： 對LR (0)來說，無論現(xiàn)行輸入符號是什么，都認(rèn)為棧頂?shù)姆柎疄榫浔M(jìn)行歸約； 對SLR(1)來說，則對現(xiàn)行輸入符號加了一點(diǎn)限制，即該輸入符號必須屬于允許跟在句柄之后的字符范圍內(nèi)，才認(rèn)為棧頂?shù)姆柎疄榫浔M(jìn)行歸約； 對LR(1)來說，對現(xiàn)行輸入符號的限制則更加嚴(yán)格，它在該輸入符號跟在棧頂符號串后形成一個規(guī)范句型的前綴時，才認(rèn)為棧頂?shù)倪@個符號串為句柄，從而進(jìn)行歸約。由于要對不同的輸入符號進(jìn)行判斷，因此LR(1)的狀態(tài)數(shù)要比LR(0)、SLR(1)多。 LR (0), SLR(1), LR(1)及LALR比較編譯原理習(xí)題(含歷年專業(yè)考試題) LALR從本質(zhì)上講與LR（1)相同，只不過它把那些棧頂符號串相同但現(xiàn)行輸入符號不同（即認(rèn)為這個相同的棧頂符號串為同心）的判斷合一（使?fàn)顟B(tài)數(shù)又減少到與LR（0）、SLR(1)一樣），只有輸入符號跟在棧頂符號串后面形成一規(guī)范句型前綴時，才認(rèn)為棧頂?shù)倪@個