編譯原理樣題3

1、*編譯原理 樣題一 選擇題【 】1_型文法也稱為正規(guī)文法。A 0 B 1 C 2 D 3【 】2_文法不是LL(1)的。 A 遞歸 B 右遞歸 C 2型 D 含有公共左因子的【 】3 文法EE+E|E*E|i的句子i*i+i*i的不同語法分析樹的總數(shù)為_。A1 B3 C5 D7【 】4四元式之間的聯(lián)系是通過 實現(xiàn)。 A臨時變量 B指示器 C符號表 D程序變量【 】5同心集合并可能會產(chǎn)生的新沖突為 。 A二義 B移進/移進 C移進/歸約 D歸約/歸約【 】6代碼優(yōu)化時所依據(jù)的是 。A語法規(guī)則 B詞法規(guī)則 C等價變換規(guī)則 D語義規(guī)則【 】7表達式a-(-b)*c的逆波蘭表示為 。Aa-bc* Ba

2、bc*- Cab- Dabc-* （注：為單目減運算符）【 】8過程的DISPLAY表記錄了 。A過程的連接數(shù)據(jù) B過程的嵌套層次C過程的返回地址 D過程的入口地址二 填空題1編譯過程的六個階段為：詞法分析、 、語義分析、 代碼優(yōu)化和目標代碼生成。2詞法分析階段的任務(wù)式從左到右掃描 ，從而逐個識別 。3對于文法G1和G2，若有 ，則稱文法G1和G2是等價的。4對于文法GE：ET|E+T TF|T*F FPF|P P(E)|i，句型T+T*F+i的句柄是 ，最左素短語是 。 所謂素短語是指這樣的一個短語，它至少含有一個終結(jié)符，并且，除它自身之外不再含任何更小的素短語。所謂最左素短語是指處于句型最

3、左邊的那個素短語。如，P*P和i是句型P*P+i的素短語，而P*P是它的最左素短語。5最右推導(dǎo)的逆過程稱為 ，也稱為 。6規(guī)范規(guī)約中的可規(guī)約串是 ，算符優(yōu)先分析中的可規(guī)約串是 。7（A B）（C D E） 的逆波蘭式是 。8在屬性文法中文法符號的兩種屬性分別稱為 和 。9符號表的每一項是由名字欄和 兩個欄目組成。在目標代碼生成階段，符號表是 的依據(jù)。10一個過程的DISPLAY表的內(nèi)容是它的 的DISPLAY表的內(nèi)容加上 。三 有窮自動機M接受字母表S0,1上所有滿足下述條件的串：每個1都有0直接跟在右邊。構(gòu)造一個最小的DFA M及和M等價的正規(guī)式。四 證明正規(guī)式(ab)*a 與正規(guī)式a(ba

4、)*等價 （用構(gòu)造他們的最小的DFA方法）。五 寫一個文法，使其語言是：L 1n0m1m0n | m,n0 六 對文法GS S aSb | PP bPc | bQcQ Qa | a(1) 它是否是算符優(yōu)先文法？請構(gòu)造算符優(yōu)先關(guān)系表(2) 文法GS消除左遞歸、提取左公因子后是否是LL（1）文法？請證實。七 已知文法G為:（0） S S（1） S aAd（2） S bAc（3） S aec（4） S bed（5） A e 試構(gòu)造它的LR（1）項目集、可歸前綴圖和LR（1）分析表。八 已知源程序如下： prod:=0; i:=1; while i20 do beginprod:=prod+ai*bi

5、;i:=i+1 end;試按語法制導(dǎo)翻譯法將源程序翻譯成四元式序列（設(shè)A是數(shù)組a的起始地址，B是數(shù)組b的起始地址；機器按字節(jié)編址，每個數(shù)組元素占四個字節(jié)）。九 設(shè)有以下程序段 procedure P(x,y,z) begin Y:=y*3; Z:=X+z; end; begin a:=5; b:=2; p(a*b,a,a); print(a); end若參數(shù)傳遞的方法分別為（1）傳值、（2）傳地址、（3）傳名，試問結(jié)果分別什么？十 對以下文法，請寫出關(guān)于括號嵌套層數(shù)的屬性文法。(為S,L引入屬性h,用來記錄輸出配對的括號個數(shù))文法規(guī)則語 義 規(guī) 則S(T)SiTT,STS十一 對PL/0語言的

6、while語句 while 條件B DO 語句S 的編譯程序，請在空缺處填空，完成該語句的編譯算法：switch (SYM) case WHILESYM: ;GetSym(); CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX); ;GEN(JPC,0,0);if (SYM=DOSYM) ;else Error(18);STATEMENT(FSYS,LEV,TX);GEN(JMP,0,CX1); ；break;編譯原理樣題參考答案一 選擇題（12分） 1. D 2. D 3. B 4. A 5. D 6. C 7. B 8. B二 填空題（8分） 1. 語法分析 中

7、間代碼生成6. 句柄 最左素短語2. 源程序 單詞7. 3. L(G1)=L(G2) （或 G1和G2的語言相同）8. 繼承屬性 綜合屬性（次序可換）4. T T*F9. 信息欄 地址分配5. 規(guī)范歸約 最左歸約10. 直接外層 本過程的SP的地址三SS1 1 00 最小的DFA M如下圖所示：與M等價的正規(guī)式為：(0* | (10)* )*四abX12Y a 正規(guī)式（ab）* a對應(yīng)的NFA如圖：aX12Ya b正規(guī)式a(ba)* 對應(yīng)的NFA如圖：這兩個正規(guī)式最終都可得到最簡的DFA如圖所示：0ba1所以這兩個正規(guī)式等價。五 文法G：S 1S0 | AA 0A1 | 六 1.求出GS的FI

8、RSTVT集和LASTVT集：FIERSTVT（S）=a,b LASTBVT（S）=b,c FIERSTVT(P)=b LASTBVT（P）=c FIERSTVT(Q)=a LASTBVT（Q）=a構(gòu)造優(yōu)先關(guān)系表為： a b c a b c 由于在優(yōu)先關(guān)系中同時出現(xiàn)了aa以及bb，所以該文法不是算符優(yōu)先文法。2. 消除左遞歸和提取左公因子后的文法為：S aSb | PP bPP Pc |QcQ aQQ aQ|求具有相同左部的兩個產(chǎn)生式的Select集的交集：Select(SaSb)Select(SP) = aFirst(P) = ab = Select(PPc)Select(PQc) = Fi

9、rst(P)First(Q)=ba= Select(QaQ)Select(Q) = aFollow(Q) = ac = 所以修改后的文法是LL（1）文法。七 LR(1)項目集和可歸前綴圖如下:ecAdI0:S S , # S aAd , # S bAc , # S aec , #S bed , #I2： Sa Ad , #Sa ec , # A e , d aI1：SS , #SI3: Sb Ac , # Sb ed , # A e , cbI6: SbAc,# AI7：Sbe d , #Ae , cI11：Sbed , #dI10：SbAc , # I4：SaA d , #I5：Sae c , # Ae , deI8：SaAd , #I9：Saec , #c構(gòu)造LR(1)分析表 如下： r4 11S10 6r2 10 r3 9 r1 8S11r5 7r5S9 5S8 4 6S7 3 4S5 2acc 1A#S3bedc1S gotoaS2 action 0狀態(tài)八 四元式序列100 prode:=0101 i:=1102 If i20 goto 104103 goto 114104 T1:=4*I105 T2:=A-4106 T3:=T2T1107 T4:=4*I108 T5:=B-4109 T6:=T5T4110 T7:=T3*T6111 prod:=prod+T7112