(完整word版)編譯原理期末試題(含答案+大題集+重要知識點)

1、第1頁共 6 頁編譯原理期末試題(一)、是非題(請在括號內(nèi)，正確的劃V,錯誤的劃X)(每個 2 分，共 20 分)1 編譯程序是對高級語言程序的解釋執(zhí)行。(X2一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。(X)3一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。(V)4語法分析時必須先消除文法中的左遞歸。 (X)5 LR 分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。(V)6逆波蘭表示法表示表達式時無須使用括號。(V)7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。(X)8進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。(X)9兩個正規(guī)集相等的必要條件是

2、他們對應的正規(guī)式等價。(X)10一個語義子程序描述了一個文法所對應的翻譯工作。(X)二、選擇題 (請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個 4 分，共 40 分)1詞法分析器的輸出結(jié)果是 _ 。A ( ) 單詞的種別編碼B C( ) 單詞的種別編碼和自身值D2 正規(guī)式 M 1 和 M 2 等價是指 _ 。A . ( ) M1 和 M2 的狀態(tài)數(shù)相等C( ) M1 和 M2 所識別的語言集相等3.文法 G :STxSx|y 所識別的語言是 _B. ( ) (xyx)* C. ( ) xnyxn(n 0) D. ( ) x*yx*( ) 單詞在符號表中的位置( ) 單詞自身

3、值B. ( ) M1 和 M2 的有向邊條數(shù)相等D . ( ) M1 和 M2 狀態(tài)數(shù)和有向邊條數(shù)相等A( ) xyx第2頁共 6 頁4.如果文法 G 是無二義的，則它的任何句子aA ( ) 最左推導和最右推導對應的語法樹必定相同B ( ) 最左推導和最右推導對應的語法樹可能不同C ( ) 最左推導和最右推導必定相同D ( ) 可能存在兩個不同的最左推導，但它們對應的語法樹相同5構(gòu)造編譯程序應掌握 _ 。A ( )源程序B( ) 目標語言C( ) 編譯方法D( ) 以上三項都是6四元式之間的聯(lián)系是通過 _ 實現(xiàn)的。A ( ) 指示器B ( ) 臨時變量C ( ) 符號表D ( ) 程序變量7.

4、_ 表達式(AB)A(CVD)的逆波蘭表示為。A. ( )ABACDVB.( ) ABCDVAC.( ) ABV CDVAD.( ) A VBACDV8. 優(yōu)化可生成 _ 的目標代碼。A . ( ) 運行時間較短B . ( ) 占用存儲空間較小C.( ) 運行時間短但占用內(nèi)存空間大D. ( ) 運行時間短且占用存儲空間小9._ 下列優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A. ( ) 強度削弱B. ( ) 刪除歸納變量C. ( ) 刪除多余運算D. ( ) 代碼外提10._ 編譯程序使用區(qū)別標識符的作用域。A. ( ) 說明標識符的過程或函數(shù)名B( ) 說明標識符的過程或函數(shù)的靜態(tài)層次第3頁共 6 頁

5、C( ) 說明標識符的過程或函數(shù)的動態(tài)層次D. ( ) 標識符的行號三、填空題 (每空 1 分，共 10 分)1計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋 _和_編譯 2掃描器是 _詞法分析器 _，它接受輸入的 _源程序 _，對源程序進行 _詞法分析 _并識別出一個個 單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。3自上而下分析法采用 _移進 _、歸約、錯誤處理、 _接受 _等四種操作。4一個 LR 分析器包括兩部分：一個總控程序和_一張分析表 _。5._后綴式 abc-/所代表的表達式是a/(b-c)_。6局部優(yōu)化是在 _基本塊 _范圍內(nèi)進行的一種優(yōu)化。四、簡答題( 20 分)

6、1.簡要說明語義分析的基本功能。答：語義分析的基本功能包括 : 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2. 考慮文法 GS:ST(T) | a+S | aTTT,S| S消除文法的左遞歸及提取公共左因子。解：消除文法 GS的左遞歸：St(T) | a+S | aTTSTTT,ST |提取公共左因子：ST(T) | aS ST+S |&TTSTTT,ST |第4頁共 6 頁3.試為表達式 w+(a+b)*(c+d/(e-10)+8) 寫出相應的逆波蘭表示。 解： w a b + c d e 10 - / + 8 + * +4.按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序

7、列： while (ACAB 1) C=C+1;else while (A D)A=A+2;。解：該語句的四元式序列如下(其中 E1、E2 和 E3 分別對應 AVCABVD、A1和 AD,并且關(guān)系運算符優(yōu)先級高 )：100 (j,A,C,102)101 (j,_,_,113)102 (jaAd|aAb| &判斷該文法是否是 SLR(1)文法，若是構(gòu)造相應分析表，并對輸入串a(chǎn)b#給出分析過程。解：增加一個非終結(jié)符 S/后，產(chǎn)生原文法的增廣文法有：S-AA- aAd|aAb| &第6頁共 6 頁下 面 構(gòu) 造 它 的 LR(0) 項 目 集 規(guī) 范第7頁共 6 頁abPdSA3.

8、鈕1:1A乍礦處也兮血II!g 抄IllaccI=: ATaAd Ab胡bI：L：A-aA-dA-aAbI,：I A-aABlA-aJLdlI ;MSIs；血從上表可看出,狀態(tài) 10 和 12 存在移進-歸約沖突，該文法不是 LR(0)文法。對于 10 來說有：FOLLOW(A)Qa=b,d,#na= ,3都是對a中的最右非終結(jié)符替換。6. 語法- 一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7. 文法 描述語言的語法結(jié)構(gòu)的形式規(guī)則。8. 基本塊-指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。9. 語法制導翻譯-在語法分析過程中，

9、根據(jù)每個產(chǎn)生式所對應的語義子程序進行翻譯的辦法叫做語法 制導翻譯。10. 短語-令 G 是一個文法，S 劃文法的開始符號，假定a3S是文法 G 的一個句型，如果有aA3且 A 則稱3是句型a3相對非終結(jié)符 A 的短語。11. 待用信息-如果在一個基本塊中，四元式i 對 A 定值，四元式 j 要引用 A 值，而從 i 到 j有 A 的其它定值，則稱 j 是四元式 i 的變量 A 的待用信息。12. 規(guī)范句型-由規(guī)范推導所得到的句型。13. 掃描器-執(zhí)行詞法分析的程序。14. 超前搜索-在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。15. 句柄- 一個句型的最左直接短語。16. 語法制

10、導翻譯-在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義程序進行翻譯的方法法制導翻譯。17. 規(guī)范句型-由規(guī)范推導所得到的句型。18. 素短語-素短語是指這樣一個短語，至少含有一個終結(jié)符，并且，除它自身外不再含任何更小的素短語。19. 語法-是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。_20. 待用信息-如果在一個基本塊中，四元式i 對 A 定值，四元式 j 要引用 A 值，而從 i 到 j有 A 的其它定值，則稱 j 是四元式 i 的變量 A 的待用信息。21. 語義-定義程序的意義的一組規(guī)則。四、簡答題：1. 寫一個文法 G,使其語言為 不以 0 開頭的偶數(shù)集。2. 已知文法 G（S）及相應翻譯

11、方案STaAb pri nt“ 1”STa print“ 2”ATAS pri nt“ 3”ATc pri nt“ 4”輸入 acab,輸出是什么？3. 已知文法 G（S）STbAaS；之間沒叫做語之間沒第12頁共 6 頁AT（B | aBTAa）寫出句子 b（aa）b 的規(guī)范歸約過程。4.考慮下面的程序：procedure p(x, y, z) ;beginy:=x+y;z:=z*z;endbeginA:=2;B:=A*2;P(A, A, B);Print A, Ben d.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出A, B 的值是什么？5.文法 G(S)STdABA aA

12、| aBTBb|描述的語言是什么？6.證明文法 G(S)STSaS|e是二義性的。7.已知文法 G(S)STBAATBS| dBTaA| bS | c的預測分析表如下abcd#SSTBASTBASTBAAATBSATBSATBSArdBBTaABTbSBTC給出句子 adccd 的分析過程。8.寫一個文法 G,使其語言為 L(G)=albmclanbn| l=0, m=1, n=29.已知文法 G(S):STa| (T)TTT,S|S的優(yōu)先關(guān)系表如下：關(guān)系a()5a-.(V.V.=V.)-.5V.V.請計算出該優(yōu)先關(guān)系表所對應的優(yōu)先函數(shù)表。第13頁共 6 頁10. 何謂優(yōu)化？按所涉及的程序范圍

13、可分為哪幾級優(yōu)化？11. 目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？12. 一字母表工=a, b，試寫出工上所有以 a 為首的字組成的正規(guī)集相對應的正規(guī)式。13. 基本的優(yōu)化方法有哪幾種？第 10 頁共 6 頁14. 寫一個文法 G,使其語言為 L(G)=abncn| n015. 考慮下面的程序：procedure p(x, y, z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b, b, a);print aend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a 的值是什么 ?16. 寫出表達式 ab*(c-d)/e

14、 的逆波蘭式和三元序列。17. 證明文法 G(A)ATAA | (A)|是二義性的。18. 令=a,b，則正規(guī)式 a*b|b*a 表示的正規(guī)集是什么？19何謂 DISPLAY 表？其作用是什么？20. 考慮下面的程序：procedure p(x, y, z) ；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b, a-b, a);print aend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a 的值是什么 ?21. 寫一個文法 G,使其語言為 L(G)=anbncm| n0 為奇數(shù)，m0 為偶數(shù)22. 寫出表達式 a:=(b+c)*e+(b

15、+c)/f 的逆波蘭式和三元序列。23. 一個文法 G 別是 LL(1)文法的充要條件是什么？24. 已知文法 GSStS*aF | aF | *aFFt+aF | +a消除文法左遞歸和提公共左因子。25. 符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？ 答案： 1. 所求文法是 GS:StAB |B A0AtAD |CBt2 |4 |6 |8Ct1 |3 |5 |7 |9 |BDt0 |C第15頁共 6 頁2. 輸出是 42313. 句子 b(aa)b 的規(guī)范歸約過程:步驟符號棧輸入串動作0#b(aa)b#預備1#b(aa)b#移進2#b(aa)b#移進3#b(aa)b#移進4#b(Aa

16、)b#歸約5#b(Ma)b#移進6#b(Ma)b#移進7#b(Bb#歸約8#bAb#歸約9#bAb#移進10#S#接受4. 傳地址 A=6, B=16傳值 A=2, B=4_n m5. L(G)=da b |n0, m 06. 證明：因為文法 GS存在句子 aa 有兩個不同的最左推導，所以文法GS是是二義性的。S=SaS=SaSaS=aSaS=aaS=aaS=SaS=aS=aSaS=aaS=aa7. 句子 adccd 的分析過程：步驟符號棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#STBA2#AAaadccd#BTaA3#AAdccd#4#Addccd#ATd5#Accd#6#SBcc

17、d#ATBS7#Scccd#BTC8#Scd#9#ABcd#BTC10#Acd#11#Ad#12#dd#ATd13#8.所求文法是 GS:STABATaAc | DDTbD | bBTaBb | aabb第16頁共 6 頁9.11. 目標代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。應著重考慮的問題：(1)如何使生成的目標代碼較短；(2) 如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3) 如何充分利用指令系統(tǒng)的特點。12. 正規(guī)式 a ( a | b )*。13. 刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復寫傳播和刪除無用賦值。14. 文法 GS:STaB

18、 | aBTbe |bBc15. 傳值 a=2傳地址 a=1516.逆波蘭式:abcd-*e/+三元序列：oparg1 arg2(1)-cd*b(1)(3)/ (2)e+a(3)17.證明：因為文法 GS存在句子()有兩個不同的最左推導，所以文法GS是是二義性的。A=AA=(A)A=()A=()A=AA=A=(A)=()* *18. (a b|b a)=a,b,ab,ba,aab,bba .19. Display 表：嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當一個過程運行時必須跟蹤它的所有外 層過程的最新活動記錄起始地址，display 表就是用于登記每個外層過程的

19、最新活動記錄起始地址。20. 傳地址 a=12 傳值 a=521. 所求文法是 GS:STACATaaAbb | abCTccC | cc22. 逆波蘭式 abc+e*bc+f/+:=三元序列oparg1arg2(1) +bc(2) *(1)e(3) +bc/(3)f(5) +(2)(4)(6):=a(5)第17頁共 6 頁23. 一個文法 G 別是 LL(1) 文法的充要條件是 :(1) FIR ST(a)AFIRSTS )=(2)如果3=*s, FIRST(a)AFOLLOW(A)*24. 消除左遞歸STaFS | *aFS ST*aFS |&Ft+aF | +a 提公共左因子 ,

20、 文法 G (S)StaFS| *aFSSt*aFS|&Ft+aFFtF |&25. 作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進展狀況。 主要技術(shù)：線性表，對折查找，雜奏技術(shù)。五、計算題：1. 設文法 G(S):ST| a | (T)TtT,S | S 消除左遞歸；構(gòu)造相應的 FIRST 和 FOLLOW!合； 構(gòu)造預測分析表2. 語句 if E then S(1)改寫文法，使之適合語法制導翻譯；(2)寫出改寫后產(chǎn)生式的語義動作。3. 設文法 G( S)：St(T) | aTtT+S | S(1 )計算 FIRSTVT 和 LASTVT；(2)構(gòu)造優(yōu)先關(guān)系表。

21、4. 設某語言的 for 語句的形式為for i:= E1)to Edo S其語義解釋為i: = E(1)LIMIT: = Eagai n: if iv=LIMIT thenBeginS;i: = i + 1goto againEnd;( 1 )寫出適合語法制導翻譯的產(chǎn)生式； (2)寫出每個產(chǎn)生式對應的語義動作。5. 把語句while a0 then a:=a+1else a:=a*3-1;翻譯成四元式序列。6. 設有基本塊D:=A-CE:=A*CF:=D*E第18頁共 6 頁S:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假設基本塊出口時只有 M 還被

22、引用，請寫出優(yōu)化后的四元序列。7. 已知文法 G(S)STa |A| (T)T,S | S(1)給出句子 (a,(a,a) 的最左推導；(2)給出句型 (T,S),a) 的短語 , 直接短語，句柄。8. 對于 C 語言 do S while E 語句(1)改寫文法，使之適合語法制導翻譯；(2)寫出改寫后產(chǎn)生式的語義動作。9. 已知文法 G(S)StaAcBeAtAb| bBtd(1) 給出句子 abbcde 的最左推導及畫出語法樹；(2) 給出句型 aAbcde 的短語、素短語。10. 設文法 G(S):St(T) | aS | aTtT,S | S 消除左遞歸和提公共左因子； 構(gòu)造相應的 F

23、IRST 和 FOLLOW!合；構(gòu)造預測分析表。11. 把語句if X0 V Y0 do X:=A*3else Y:=B+3;翻譯成四元式序列。12. 已知文法 G(S)EtE+T | TTtT*F| FFt(E)| i(1)給出句型 (i+i)*i+i 的最左推導及畫出語法樹；(2)給出句型 (E+T)*i+F 的短語，素短語和最左素短語。13. 設文法 G(S)：StT | SVTTTU|T人UUti |-U (1)計算 FIRSTVT 和 LASTVT；( 2)構(gòu)造優(yōu)先關(guān)系表。第19頁共 6 頁答案：消除左遞，文法變?yōu)镚 S:STA| a | (T)ST | STT,ST |此文法無左公

24、共左因子。構(gòu)造相應的 FIRST 和 FOLLOWI 合： FIRST(S)=a,A,(，F(xiàn)OLLOW(S)=#, , )FIRST(T)=a,A,(，F(xiàn)OLLOW(T)=FIRST(T )=, , FOLLOW(F)=)(3)構(gòu)造預測分析表：aA()5#SSTaST人ST(T)TTTSTTTSTTTSTTTTTT,ST 2. (1)CTif E thenSTCS1 2(2)CTif E then BACK(E.TC, NXQ); C.chain:=E.FCSTCSS.chain:=MERG(C.Chain, S.Chain)3. (1) FIRSTVT(S)=a, ( FIRSTVT(T)=

25、+, aa, (LASTVT(S)=a, ) LASTVT(T)=+, a, )1 (2)4. (1) FTfor i:=E to E doSTFS(1)2FTfor i:=Eto EdoGEN(:=, E(1).place, _, entry(i);F.place:=e ntry(i);LIMIT:=Newtemp;GEN(:=, E.place, _, LIMIT);Q:=NXQ;F.QUAD:=q;GEN(j , entry(i), LIMIT, q+2) F.chai n:=NXQ;GEN(j, _, _, 0)STFS(1)BACKPATCH(S .chain, NXQ);GEN(+

26、, F.place, 1, F.place);GEN(j, _, _, F.QUAD);S.chai n:=F.chain5.(1) (j.+V.V.(V.V.V.=).第21頁共 6 頁(2)(j, _, _, (i2)(3)(j, c,0, (5)(4)(j, _, _, (8)(5)(+, a,i, Ti)(6)(:=, Ti,_, a)(7)(j, _, _, (i)(8)(*, a,i3, T2)(9)(- , T2,i, T3)(i0) (:=, T3, _, a)(ii)(j, _, _, (i)6. 優(yōu)化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+207. 最左推

27、導S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a, a)短語(T,S),a)(T,S),a(T,S)T,Sa直接短語T,Sa句柄T,S8.(1)STdo MiSiwhile M2EM(2)M.quad=nestquad;Stdo MiSiwhile M2E backpatch(si.nextlist, M2.quad)backpatch(E.truelist, Mi.quad);S.nextlist=E.falelist;9.(i) S=aAcBe=AAbcBe=abbcBe=abbcde(2) 短語 : aAbc

28、de, Ab, d素短語 : Ab, di0.(i) SL(2)T(L) | aSSTS |sTSLLT,SL|sFIRST(S)=a, (FIRST(S)=a, (,sFIRST(L)=a, (FIRST(L)=,sFOLLOW(S)=, ), #FOLLOW(S)=, ), #FOLLOW(L)= )FOLLOW(L)= )()aJ#第22頁共 6 頁SST(L)STaSSSSTST&sS:STgST&LLTSLLTSLL,SLLL11. (1) (j, X, 0, (5)(j, _, _, (3)(3) (j0, X, 0,)(6) (j, _, _, (7)(7) (*

29、, A, 3, T1)(8) (:=, T1, _, N)(9) (j,亠，(5)(10) (j,亠，(13)(11) (+, B, 3, T2)(12) (:=, T2, _, Y)12. (1) E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+T=(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T =(i+i)*i+F=(i+i)*i+i(2)短語 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F素短語 i, E+T最左素短語 E+T13. (1)FIRSTVT(S)=V

30、,A, i, - FIRSTVT(T)=A, i, -FIRSTVT(U)=i, -LASTVT(S)=V,A, i, - LASTVT(T)=A, i, -LASTVT(U)=i, -(2)iVA-S.VV.V.V.AV.V.-V.V.第 18 頁共 6 頁編譯原理期末試題(二)1、描述由正規(guī)式 b*(abb*)*(a| )定義的語言，并畫出接受該語言的最簡DFA 。2、證明文法 E E + id | id 是 SLR(1) 文法。3、下面是表達式和賦值語句的文法，其中and 的類型是 bool bool bool ，+的類型是 intintint ， =的類型是 int int bool

31、，:= 要求 id 和 E 的類型都是 int 或者都是 bool 。為該文法寫一個語法制導定義或翻譯方案，它完成類型檢查。S id := EE E and E | E + E | E = E |id4、對于下面 C 語言文件 s.cf1(int x)long x;x = 1;f2(int x)long x;x = 1;某編譯器編譯時報錯如下：s.c: In function f1 :s.c:3: warning: declaration of x shadows a parameter請回答，對函數(shù) f2 為什么沒有類似的警告錯誤。5、下面 C 語言程序經(jīng)非優(yōu)化編譯后，若運行時輸入2，則結(jié)果

32、是area=12.566360, addr=-1073743076 經(jīng)優(yōu)化編譯后，若運行時輸入2，則結(jié)果是area=12.566360, addr=-1073743068 請解釋為什么輸出結(jié)果有區(qū)別。main()float s, pi, r;pi=3.14159; scanf(%f, &r); printf(area=%f, addr=%dn, s=pi*r*r, &r);6、描述由正規(guī)式 b a(bb a) b 定義的語言，并畫出接受該語言的最簡DFA 。7、下面的文法產(chǎn)生代表正二進制數(shù)的0 和 1 的串集：B 0 | B 1 | 1第24頁共 6 頁下面的翻譯方案計算這種正

33、二進制數(shù)的十進制值：BBi0 B. val := Bi.val 2 | Bi1 B. val := Bi.val 2 +1|1 B. val := 1 請消除該基礎文法的左遞歸，再重寫一個翻譯方案，它仍然計算這種正二進制數(shù)的十進 制值。8、 在 C 語言中，如果變量 i 和 j 都是 long 類型，請寫出表達式 &和表達式& &j 的類型表達式。為幫助你回答問題，下面給出一個程序作為提示，它運行時輸出1。mai n() long i, j;printf( %dn ” &i &j);9、 一個 C 語言的函數(shù)如下：fun c(i) long i; lon

34、g j;j = i -1;fun c(j);下面左右兩邊的匯編代碼是兩個不同版本GCC 編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用 func 之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有 實質(zhì)區(qū)別。請敘述右邊代碼對參數(shù)傳遞的處理方式并推測它帶來的優(yōu)點。|func:pushl%ebp|pushl%ebpmovl%esp, %ebp|movl%esp, %ebpsubl$4, %esp|subl$8, %espmovl8(%ebp), %edx|movl8(%ebp), %eaxdecl%edx|decl%eaxmovl%edx, -4(%ebp)|movl%eax, -

35、4(%ebp)movl-4(%ebp), %eax |movl-4(%ebp), %eaxpushl%eax|movl%eax, (%esp)callfunc|callfuncaddl$4, %esp|leaveleave|retret|編譯原理試卷八答案1、由正規(guī)式 b*(abb*)*(a|)定義的語言是字母表DFA 如下：a, b上不含子串 aa 的所有串的集合。最簡第25頁共 6 頁2、先給出接受該文法活前綴的DFA 如下:3、語法制導定義如下。S id := E S.type := if (id .type = bool and E.type = bool) or (id .type

36、= intand E.type = int) then type_ok else type_error EE1and E2 E.type := if E1.type =bool andE2.type =bool then bool elsetype_error EE1+ E2 E.type :=if E1.type = int andE2.type = int the nint else type_error EE1=E2 E.type :=if E1.type = int andE2.type = int the nbool else type_error Eid E.type :=look

37、up(id.e ntry) 4、對于函數(shù) f1，局部變量 x 聲明的作用域是整個函數(shù)體，導致在函數(shù)體中不可能訪問形式參數(shù) X。由于這是一個合法的 C 語言函數(shù)，因此編譯器給出警告錯誤。對于函數(shù) f2，由于局部變量x 的作用域只是函數(shù)體的一部分，不會出現(xiàn)上述問題，因而編譯器不報錯。變量 s, pi, r 在局部數(shù)據(jù)區(qū)都分配 4 個字節(jié)的空間。使用優(yōu)化編譯時,pi*r*r 變成 3.14159*r*r，pi=3.14159 成為無用賦值而刪去，函數(shù)中不再有pi 的引用，因此不必為 pi 分配空間。類似地，s=3.14159*r*r 也是一個無用賦值(表達式要 計算，但賦值是無用的)，也不必為 s

38、分配空間。這樣，和非優(yōu)化情況相比，局部數(shù)據(jù)區(qū)少 了 8 個字節(jié)，因此 r 的地址向高地址方向移動了8 個字節(jié)。6、正規(guī)式 b a(bb a) b 體現(xiàn)的特點是，每個 a 的左邊都有若干 b，除非 a 是第一個字母。該 正規(guī)式定義的語言是： 至少含一個 a,但不含子串 aa 的所有 a 和 b 的串集。最簡 DFA 如下:7、消除左遞歸后的文法:B 1 B5、使用非優(yōu)化編譯時,由于復寫傳Io和 13都只有移進項目，肯定不會引起沖突；I2和|4都無移進項目并僅含一個歸約項目， 也肯定不會引起沖突； 在 Ii中，E 的后繼符號只有$，同第 2 個項目的展望符號“ + ”不一樣, 因此 Ii也肯定不會

39、引起沖突。由此可以斷定該文法是SLR(1)的。第 21 頁共 6 頁相應的翻譯方案如下：B1 B .i := 1 B B. val := B .valB0 B1.i := B .i2 B1B .val := B1.val|1 B1.i := B .i2 +1 B1B .val := B1.val| B .val := B .i8、表達式 &i 的類型表達式是 pointer(long) ，表達式 &i &j 的類型表達式是 long 。按照 C 語 言的規(guī)定，指向同一個類型的兩個指針可以相加減，它們值的差是它們之間的元素個數(shù)。9、左邊的編譯器版本：一般只為局部變量分配空

40、間。調(diào)用函數(shù)前，用若干次pushl 指令將參數(shù)壓棧，返回后用 addl $n, %esp 一次將所有參數(shù)退棧 (常數(shù) n 根據(jù)調(diào)用前做了多少次 pushl 來決定)。右邊的編譯器版本： 除了為局部變量分配空間外， 同時還為本函數(shù)中出現(xiàn)的函數(shù)調(diào)用的 參數(shù)分配空間，并且參數(shù)所用空間靠近棧頂。調(diào)用函數(shù)前，用 movl 指令將參數(shù)移入棧頂， 調(diào)用結(jié)束后無需參數(shù)退棧指令。優(yōu)點是每次函數(shù)調(diào)用結(jié)束后不需要執(zhí)行 addl $n, %esp 指令，另外增加優(yōu)化的可能性。第27頁共 6 頁編譯原理期末試題（三）1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對循環(huán)的優(yōu)化可以有哪三種?答：從優(yōu)化的范圍的角度，優(yōu)化可以分為

41、局部優(yōu)化和全局優(yōu)化兩類； 對循環(huán)的優(yōu)化有三種：循環(huán)不變表達式外提、歸納變量刪除與計算強度削減2、寫出表達式 a=b*c+b*d 對應的逆波蘭式、四元式序列和三元式序列答：逆波蘭式：abc*bd*+:=四元式序列：三兀式序列:O P ARG1 ARG2(1) (*，b，c，t1)(1) (* b， c )(*，b，d，t2)(* b， d )什，t1，t2，t3)(3) 什 (1) ，(2)(:=，t3，/，a)(:=(3)，a)3、對于文法 G(S)三、設有字母表a，b上的正規(guī)式 R=（ab|a）解: （ 1）（2）將（1）所得的非確定有限自動機確定化ab-01131221+3SbMbM(L

42、|aLMa)答：1）S bMb b(Lbb(Ma)b2）短語:Ma) ， (Ma)，b(Ma)b直接短語: Ma)句柄:Ma)(TM a )第28頁共 6 頁(3) 對(2)得到的 DFA 化簡，合并狀態(tài) 0 和 2 為狀態(tài) 2:(4) 令狀態(tài) 1 和 2 分別對應非終結(jié)符 B 和 AG: A aB|a|; B aB|bA|a|b| 可化簡為：G: AaB|; B aB|bA| &四、設將文法 G 改寫成等價的 LL(1)文法，并構(gòu)造預測分析表。G: S S*aT|aT|*aT ； T +aT|+a解：消除左遞歸后的文法 G: S aTS |*aTS S *aTS | &T +

43、aT|+a提取左公因子得文法 G:SaTS *aTS S *aTS | &T+aT T T| &Select(S aTS)=aSelect(S *aTS )=*Select(SaTS)nSelect(S*aTS=Select(S *aTS )=*Select(S 滬 Follow(s )=#Select(S *aTS nSelect(S 滬 Select(T +aT)=+Select(T T)=First(T) =+Select(T 滬 Follow(T=*,#Select(T T)nSelect(T 滬所以該文法是LL(1)文法預測分析表：*+a#S*aTS aTS+a第29

44、頁共 6 頁S*aTS T+aTTT6 設文法 G 為：S A; A BA|B aB|b解：(1 )拓廣文法 G: (0) S S (1) S AA BA(3) A B aB (5) B b ; FIRST(A) = & , a, b ; FIRST(B) = a, b構(gòu)造的 DFA 如下：項 目 集 規(guī) 范 族 看 出 ， 不 存 在 沖 突 動 作 。 . 該 文 法 是L R ( 1 ) 文 法(2) LR分析表如下：ActionGotoBsAB0S4r3131acc2rl3SiSir3sS4S4S575r5r5r56r27rlrl輸入串 abab 的分析過程為:第30頁共 6

45、頁當前孑符動作0ababis移進(2)04Sabab轎進045ijabab#歸妁B-*b&17-E3b#歸絢B-eiE(J3a屏移進034b#越追b(8)0047希aB舊灼B-aB033s?BB歸約A-E10：0336竊BA歸灼A-BA(11)伽SBA9歸釣2BA121A0曬&CC簡答題 3、設有文法 GS: S f S（S）S| ,該文法是否為二義文法？說明理 由。答：是二義的，因為對于（）（）可以構(gòu)造兩棵不同的語法樹。五、給定文法 GS:SfaA|bQ; AfaA|bB|b ; BbD|aQ QaQ|bD|b; DfbB|aA;EaB|bFFfbD|aE|b構(gòu)造相應的最小的

46、 DFA。解：先構(gòu)造其 NFA :用子集法將 NFA 確定化: 第31頁共 6 頁將 S、A、Q、BZ、DZ、D、B 重新命名，分別用 0、1、2、3、4、5、6 表示。abSAQAABZQQDZBZQDDZABDABBQD第32頁共 6 頁P1=( 0,5, 6 , 1,2 , 3,4 )再用 b 進行分割：P2=( 0 , 5, 6 , 1,2 , 3,4 )再用 a、b 進行分割，仍不變。 再令0為A,1,2為 B,3,4為 C,5,6為Db最小化為右上圖。六、對文法 G(S): S - a |A| (T)答: (1)FIRSTVT(S) a,A,(FIRSTVT(T) , ,a,A,(

47、LASTVT(S) a,A,)LASTVT(T) , ,a,A,)(2)是算符優(yōu)先文法，因為任何兩個終結(jié)符之間至多只有一種優(yōu)先關(guān)系。(2 分)aA()J#aA(=J#=步驟棧當前輸入字符剩余輸入串 動作1(a,a#(移進2#(a,a)#(,歸約4#(N5a)#(,移進5#(N,a)#,)歸約7#(N,N)#,)歸約8#(N)#(=)移進9#(N)#)#歸約10#N#接受(3)給出輸入串(a,a)# 的算符優(yōu)先 分析過程。因為 3、4 中含有 z,所以它們?yōu)榻K態(tài)A令 P=( 0,125,6 , 3,4)用匕進行分割:、給出下面語言的相應文法:L1=anbn| n1(15)L2=anbm+nam|

48、 n1，m0G1 :A aAb |abG1:第 27 頁共61頁bBb|ab編譯原理期末試題（四）、簡述編譯程序的工作過程。（10）編譯程序的工作過程，是指從輸入源程序開始到輸出目標程序為止的整個過程， 是非常復雜的，就其過程而言，一般可以劃分為五個工作階段：詞法分析，對 構(gòu)成源程序的字符串進行掃描和分解， 識別出一個個的單詞；語法分析，根據(jù) 語言的語法規(guī)則，把單詞符號串分解成各類語法單位；語義分析與中間代碼產(chǎn) 生，即對各類語法單位，分析其漢一并進行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更 高效的代碼；目標代碼生成，把中間代碼變換成特定機器上的低級語言指令形 式。1( 0 | 1)*1二、構(gòu)造下列正規(guī)式

49、相應的DFA （用狀態(tài)轉(zhuǎn)換圖表示）（15）（1）11第34頁共 6 頁四、對下面的文法 G :STa |b | (T)TTT, S | S(1) 消去文法的左遞歸，得到等價的文法G2 ;(2) 判斷文法 G2 是否 LL( 1)文法，如果是，給出其預測分析表。(15)G2STa | b |(T)TTSTTT,S T |G2 是 LL (1)文法。ab()#SSTaSTbST(T)TTTSTTTST TTSTTTTTT, ST五、設有文法 GA:ATBCc|gDBBTbCDE |CTDaB | caDTdD |ETgAf | c(1) 計算該文法的每一個非終結(jié)符的FIRST 集和 FOLLOW

50、集;(2) 試判斷該文法是否為 LL (1)文法。(15)FIRSTFOLLOWAA,b,c,d,gBbA,c,dCA,c,dC,d,gDDA,b,c,gEC,g是 LL (1)文法。六、對表達式文法 G :ETE+T | TTTT*F | FFT(E) | I(1)造各非終結(jié)符的FIRSTVT和 LASTVT 集合;2)構(gòu)造文法的算符優(yōu)先關(guān)系表。(15)第35頁共 6 頁FIRSTVTLASTVTE*, +, (, i*, + ,), iT*, (, i* ,), iF(,i),i算符優(yōu)先關(guān)系表+*I()#+*I()#七、有定義二進制整數(shù)的文法如下：LTLB | BBT0 |1構(gòu)造一個翻譯模

51、式，計算該二進制數(shù)的值（十進制的值）。（15）引入 L、B 的綜合屬性 val，翻譯模式為：STLprint（L.val）LTLIBL.val= Li.val*2+B.valLTBL.val= B.valBT0B.val=0BT1B.val=1第36頁共 6 頁編譯原理期末試題（五）、單項選擇題（共 10 小題，每小題 2 分，共 20 分）1 .語言是A .句子的集合B .產(chǎn)生式的集合C.符號串的集合D .句型的集合2. 編譯程序前三個階段完成的工作是A.詞法分析、語法分析和代碼優(yōu)化B .代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語法分析、語義分析和中間代碼生成D .詞法分析、語法分析和代碼

52、優(yōu)化3. 個句型中稱為句柄的是該句型的最左A .非終結(jié)符號 B .短語 C .句子D .直接短語4. 下推自動機識別的語言是A . 0 型語言B . 1 型語言C. 2 型語言D . 3 型語言5. 掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法 單位即6.對應 Chomsky 四種文法的四種語言之間的關(guān)系是C .把中間代碼變換成依賴具體機器的目標代碼D .把匯編語言翻譯成機器語言、填空題（本大題共 5 小題，每小題 2 分，共 10 分）1 .編譯程序首先要識別出源程序中每個（單詞），然后再分析每個（句子）并翻譯其意義。2. 編譯器常用的語法分析方法有（自底向上

53、）和（自頂向下）兩種。A.字符B.單詞C.句子D .句型A. LoLiL2L3C. L3=L2LiLoB. L3L2L1LoD . LoL1L2=L3B .分析句子的含義D.生成目標代碼C .逆波蘭式D .語法樹B.節(jié)省空間D .把編譯程序進行等價交換第37頁共 6 頁3. 通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的(綜合)。4程序設計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動態(tài)存儲分配)方案。5 對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目

54、標程序)。三、名詞解釋題(共 5 小題，每小題 4 分，共 20 分)1 詞法分析詞法分析的主要任務是從左向右掃描每行源程序的符號，按照詞法規(guī)則 從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位， 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(toke n)，送給語法分析程序。2. LL文法若文法的任何兩個產(chǎn)生式A |都滿足下面兩個條件：(1) FIRST( ) FIRST()=;(2)若* ，那么 FIRST( ) FOLLOW( A )=。我們把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個 L 代表從左向右掃描輸入，第二個L 表示產(chǎn)生最左推導，1 代表在決定分析器的每步動作時向前看一個輸入符

55、號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3. 語法樹句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導樹)。 給定文法 G=(VN,VT, P, S),對于 G 的任何句型都能構(gòu)造與之關(guān)聯(lián)的 語法樹。這棵樹具有下列特征：(1) 根節(jié)點的標記是開始符號So(2) 每個節(jié)點的標記都是 V 中的一個符號。(3) 若一棵子樹的根節(jié)點為 A，且其所有直接子孫的標記從左向右的排列 次序為 A1A2-AR，那么 AA1A2-AR一定是 P 中的一條產(chǎn)生式。(4) 若一標記為 A 的節(jié)點至少有一個除它以外的子孫，貝 UAVN。(5) 若樹的所有葉節(jié)點上的標記從左

56、到右排列為字符串w，則 w 是文法 G的句型；若 w 中僅含終結(jié)符號，則 w 為文法 G 所產(chǎn)生的句子。4. LR(0)分析器所謂 LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的 每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再 向前查看 0 個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否 已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作(是移進還是按某一產(chǎn)生式進行歸約等)。5.語言和文法文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。 文法 G 定義為四元組的形式：G=(VN,VT, P, S)其中：VN是非空有窮集合，稱為非終結(jié)符

57、號集合；VT是非空有窮集合， 稱為終結(jié)符號集合；P是產(chǎn)生式的集合（非空）；S 是開始符號（或識別符號）。 這里，VNAVT=, SVN。V=VNUVT，稱為文法 G 的字母表，它是出現(xiàn) 文法產(chǎn)生式中的一切符號的集合。第38頁共 6 頁文法 G 所描述的語言用 L（G）表示，它由文法 G 所產(chǎn)生的全部句子組成，即L（G）=x| S *x，其中 S 為文法開始符號，且x VT簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題（共 4 小題，每小題 5 分，共 20 分）1 編譯程序和高級語言有什么區(qū)別？用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器 語言表示的目標程序（

58、這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程 的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn) 換過的叫目標程序，也就是機器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來 將匯編語言編寫的程序，按照一一對應的關(guān)系，轉(zhuǎn)換成用機器語言表示的程序。 解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句，先解釋成為一組機器語言的指令， 然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序 止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的對話，隨時可以修改高級語言的程序。BASIC 語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序

59、，一次就會部翻譯成機器語言表示的程序，而且過程進行很快， 在過程中，不能進行人機對話修改。FORTRAN 語言就是編譯型高級語言。2 編譯程序的工作分為那幾個階段？詞法分析、語法分析和語義分析是對源程序進行的分析（稱為編譯程序的前端），而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合（稱為編譯程序的后端），它們從源程序的中間表示建立起和源程序等價的目標程序。3.簡述自下而上的分析方法。所謂自下而上分析法就是從輸入串開始，逐步進行歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上歸約”，直到根節(jié)點。4簡述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量生成 好”的代碼的編譯

60、階段。也就是要對程序代碼進行 一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目 標程序運行時所需要的時間短，同時所占用的存儲空間少。五、綜合應用題（共 3 小題，每小題 10 分，共 30 分）1 證明下述文法 G:SaSbS|aS|d是二義性文法。解： 一個文法，如果存在某個句子有不只一棵語法分析樹與之對應，那么稱這個 文法是二義性文法。第39頁共 6 頁句子 aadbd 有兩棵語法樹。如下圖：解：baSb 為句型 baSb 的相對于 S 的短語，ba 為句型 baSb 的相對于 A 的短語，Sb 為句型 baSb 的相對于 B 的短語，且為直接短語，a 為句型 baSb 的相對于 B 的短語，且為直接短語 和句柄。3設有非確定的有自限動機NFA M=(A , B , C , 0, 1 , A , C)，其中：(A , 0)=C (A , 1)=A ,