編譯原理期末試題(8套含答案)

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

2、(×)9兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。 (× )10一個語義子程序描述了一個文法所對應的翻譯工作。 (×)二、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1詞法分析器的輸出結果是_。A( ) 單詞的種別編碼 B( ) 單詞在符號表中的位置 C( ) 單詞的種別編碼和自身值 D( ) 單詞自身值2 正規(guī)式 M 1 和 M 2 等價是指_。  A( ) M1和M2的狀態(tài)數(shù)相等          B( ) M1和M2的有向邊條數(shù)相

3、等C( ) M1和M2所識別的語言集相等 D( ) M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識別的語言是_。A( ) xyx  B( ) (xyx)* C( ) xnyxn(n0)     D( ) x*yx* 4如果文法G是無二義的，則它的任何句子_。A( )最左推導和最右推導對應的語法樹必定相同 B( ) 最左推導和最右推導對應的語法樹可能不同 C( ) 最左推導和最右推導必定相同   D( )可能存在兩個不同的最左推導，但它們對應的語法樹相同 5構造編譯程序應掌握_。A( )源程序   B

4、( ) 目標語言       C( ) 編譯方法      D( ) 以上三項都是 6四元式之間的聯(lián)系是通過_實現(xiàn)的。 A( ) 指示器         B( ) 臨時變量 C( ) 符號表             D( ) 程序變量 7表達式(AB)(CD)的逆波蘭表示為_。A. ( ) ABCD B( ) ABCD 

5、0;      C( ) ABCD         D( ) ABCD 8. 優(yōu)化可生成_的目標代碼。A( ) 運行時間較短               B( ) 占用存儲空間較小C( ) 運行時間短但占用內(nèi)存空間大 D( ) 運行時間短且占用存儲空間小9下列_優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A. ( ) 強度削弱  

6、   B( ) 刪除歸納變量     C( ) 刪除多余運算   D( ) 代碼外提10編譯程序使用_區(qū)別標識符的作用域。 A. ( ) 說明標識符的過程或函數(shù)名B( ) 說明標識符的過程或函數(shù)的靜態(tài)層次C( ) 說明標識符的過程或函數(shù)的動態(tài)層次 D. ( ) 標識符的行號三、填空題(每空1分，共10分)1計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析器_，它接受輸入的_源程序_，對源程序進行_詞法分析_并識別出一個個單詞符號，其輸出結果是單詞符號，供語法分析器使用。3自上而下分析法

7、采用_移進_、歸約、錯誤處理、_接受_等四種操作。4一個LR分析器包括兩部分：一個總控程序和_一張分析表_。5后綴式abc-/所代表的表達式是_a/(b-c)_。 6局部優(yōu)化是在_基本塊_范圍內(nèi)進行的一種優(yōu)化。四、簡答題（20分）1. 簡要說明語義分析的基本功能。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2. 考慮文法 GS: S (T) | a+S | a T T,S | S 消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TSTT,ST|

8、3. 試為表達式 w+(a+b)*(c+d/(e-10)+8) 寫出相應的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +4. 按照三種基本控制結構文法將下面的語句翻譯成四元式序列：while (A<C B<D) if (A 1) C=C+1;else while (A D)A=A+2;。解：該語句的四元式序列如下(其中E1、E2和E3分別對應ACBD、A1和AD，并且關系運算符優(yōu)先級高)： 100 (j<,A,C,102) 101 (j,_,_,113) 102 (j<,B,D,104) 103 (j,_,_,113) 104 (j=,A

9、,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 1135. 已知文法 GS 為 S aSb|Sb|b ，試證明文法 GS 為二義文法。證明： 由文法GS：SaSb|Sb|b，對句子aabbbb對應的兩棵語法樹為： 因此，文法GS為二義文法。 五.計算題（10分）已知文法 A->aAd|aAb| 判斷該文法是否是 SLR(1) 文法，若是構造相應分析表，并對輸入串

10、ab# 給出分析過程。解：增加一個非終結符S/后，產(chǎn)生原文法的增廣文法有： S'->A A->aAd|aAb| 下面構造它的LR(0)項目集規(guī)范族為： 從上表可看出,狀態(tài)I0和I2存在移進-歸約沖突，該文法不是LR(0)文法。對于I0來說有：FOLLOW(A)a=b,d,#a=，所以在I0狀態(tài)下面臨輸入符號為a時移進，為b,d,#時歸約，為其他時報錯。對于I2來說有也有與I0完全相同的結論。這就是說，以上的移進-歸約沖突是可以解決的，因此該文法是SLR(1)文法。 其SLR(1)分析表為： 對輸入串a(chǎn)b#給出分析過程為： 編譯原理期末試題（二）一、是非題：1.一個上下文無關

11、文法的開始符，可以是終結符或非終結符。 ( )2.一個句型的直接短語是唯一的。 （ ）3.已經(jīng)證明文法的二義性是可判定的。 （ ）4.每個基本塊可用一個DAG表示。 （ ）5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。 （ ）6.2型文法一定是3型文法。 （ ）7.一個句型一定句子。 ( )8.算符優(yōu)先分析法每次都是對句柄進行歸約。 X ( )9.采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。 （ ）10.編譯過程中，語法分析器的任務是分析單詞是怎樣構成的。 ( )11.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。 X ( )12.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 (

12、)13.遞歸下降分析法是一種自下而上分析法。 ( )14.并不是每個文法都能改寫成LL(1)文法。 ( )15.每個基本塊只有一個入口和一個出口。 ( )16.一個LL(1)文法一定是無二義的。 ( )17.逆波蘭法表示的表達試亦稱前綴式。 ( )18.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( )19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關文法來描述。 ( )20.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22.如果一個文法存在某個句子對應兩棵不同的語法樹，則文法是二義性的。 ( )答案：1.× 2.× 3.×

13、; 4. 5. 6.× 7.× 8.× 9. 10.× 11.×12. 13.× 14. 15. 16. 17.× 18. 19. 20.× 21. 22.二、填空題：2.編譯過程可分為 （ 詞法分析） ，（語法分析），（語義分析與中間代碼生成 ），（優(yōu)化）和（目標代碼生成 ）五個階段。3.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（ 二義性的 ）。 4.從功能上說，程序語言的語句大體可分為（ 執(zhí)行性 ）語句和（說明性 ）語句兩大類。5.語法分析器的輸入是（ 單詞符號 ），其輸出是（ 語法單位 ）

14、。6.掃描器的任務是從（ 源程序中 ）中識別出一個個（ 單詞符號 ）。7.符號表中的信息欄中登記了每個名字的有關的性質(zhì)，如(類型、種屬、所占單元大小、地址）等等。8.一個過程相應的DISPLAY表的內(nèi)容為(現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址)10.常用的兩種動態(tài)存貯分配辦法是（棧式）動態(tài)分配和（堆式）動態(tài)分配。11.一個名字的屬性包括( 類型)和(作用域 )。12.常用的參數(shù)傳遞方式有(傳地址），（傳值），（傳名）13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個級別。14.語法分析的方法大致可分為兩類，一類是（ 自上而下 ）分析法，另一類是（

15、 自下而上 ）分析法。15.預測分析程序是使用一張（ 分析表 ）和一個（ 符號棧 ）進行聯(lián)合控制的。17.一張轉換圖只包含有限個狀態(tài),其中有一個被認為是（初）態(tài);而且實際上至少要有一個（終 ）態(tài)。19.語法分析是依據(jù)語言的（語法 ）規(guī)則進行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進行的。21.一個文法G，若它的預測分析表M不含多重定義，則該文法是（LL(1) 文法）文法。22.對于數(shù)據(jù)空間的存貯分配， FORTRAN采用( 靜態(tài)策略， PASCAL采用( 動態(tài))策略。24.最右推導亦稱為（規(guī)范推導），由此得到的句型稱為（規(guī)范）句型。26.對于文法G，僅含終結符號的句型稱為 ( 句子 )。27.所

16、謂自上而下分析法是指(從開始符號出發(fā)，向下推導，推出句子）29.局限于基本塊范圍的優(yōu)化稱（ 局部優(yōu)化 ）。31.2型文法又稱為（上下文無關）文法；3型文法又稱為（正則 ）文法。32.每條指令的執(zhí)行代價定義為(指令訪問主存次數(shù)加1）33.算符優(yōu)先分析法每次都是對(最左素短語）進行歸約。三、名詞解釋題：1.局部優(yōu)化-局限于基本塊范圍的優(yōu)化稱。2.二義性文法-如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義性文法。3.DISPLAY表-過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。5.最左推導-任何一步=>都是對中的最右非終結符替換。6.語法-一組規(guī)則，

17、用它可形成和產(chǎn)生一組合式的程序。7.文法-描述語言的語法結構的形式規(guī)則。8.基本塊-指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。9.語法制導翻譯-在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義子程序進行翻譯的辦法叫做語法制導翻譯。10.短語-令G是一個文法，S劃文法的開始符號，假定是文法G的一個句型，如果有SA且A，則稱是句型相對非終結符A的短語。11.待用信息-如果在一個基本塊中，四元式i對A定值，四元式j要引用A值，而從i到j之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。12.規(guī)范句型-由規(guī)范推導所得到的句型。1

18、3.掃描器-執(zhí)行詞法分析的程序。14.超前搜索-在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。15.句柄-一個句型的最左直接短語。16.語法制導翻譯-在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義程序進行翻譯的方法 叫做語法制導翻譯。17.規(guī)范句型-由規(guī)范推導所得到的句型。18.素短語-素短語是指這樣一個短語，至少含有一個終結符，并且，除它自身外不再含任何更小的素短語。19.語法-是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。 20.待用信息-如果在一個基本塊中，四元式i對A定值，四元式j要引用A值，而從i到j之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。21.語義-定義程序

19、的意義的一組規(guī)則。四、簡答題：1.寫一個文法G, 使其語言為 不以0開頭的偶數(shù)集。2.已知文法G(S)及相應翻譯方案SaAb print “1”Sa print “2”AAS print “3”Ac print “4”輸入acab, 輸出是什么？3. 已知文法G(S)SbAaA(B | aBAa)寫出句子b(aa)b的規(guī)范歸約過程。4. 考慮下面的程序：procedure  p(x, y, z)；beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2;P(A, A, B);Print A, B end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后

20、輸出 A, B的值是什么? 5文法G(S)SdABAaA| aBBb| 描述的語言是什么？6. 證明文法G(S) SSaS| 是二義性的。7. 已知文法G(S) SBAABS| dBaA| bS | c的預測分析表如下 a B c d # SSBASBASBA AABSABSABSAd BBaA BbS Bc給出句子 adccd 的分析過程。8. 寫一個文法G, 使其語言為 L(G)=albmclanbn| l>=0, m>=1, n>=2 9. 已知文法G(S):Sa| (T)TT,S|S的優(yōu)先關系表如下：關系a(),A-.>.>(<.<.=.<

21、;.)-.>.>,<.<.>.>請計算出該優(yōu)先關系表所對應的優(yōu)先函數(shù)表。10. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？11. 目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？12. 一字母表=a, b，試寫出上所有以a為首的字組成的正規(guī)集相對應的正規(guī)式。13. 基本的優(yōu)化方法有哪幾種？14. 寫一個文法G, 使其語言為 L(G)=abncn| n015. 考慮下面的程序：procedure p(x, y, z);begin y:=y+z; z:=y*z+xend;begin a:=2; b:=3; p(a+b, b, a); print a

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

23、一個文法G, 使其語言為 L(G)=anbncm| n>0為奇數(shù)， m>0為偶數(shù)22.寫出表達式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。23.一個文法G別是LL(1)文法的充要條件是什么？24.已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左遞歸和提公共左因子。25.符號表的作用是什么？符號表查找和整理技術有哪幾種？答案：1.所求文法是GS:SAB |B A0AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2.輸出是42313.句子b(aa)b的規(guī)范歸約過程：步驟符號棧輸入串動作0#b(aa)b#預備1#b(a

24、a)b#移進2#b(aa)b#移進3 #b(a a)b# 移進4#b(Aa)b#歸約5 #b(Ma)b#移進6#b(Ma)b#移進7#b(B b# 歸約8#bAb#歸約9#bAb#移進10#S#接受4.傳地址 A=6, B=16傳值 A=2, B=45.L(G)=danbm |n>0, m06.證明： 因為文法GS存在句子aa有兩個不同的最左推導，所以文法GS是是二義性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa7.句子 adccd 的分析過程：步驟符號棧輸入串

25、產(chǎn)生式0#Sadccd#1#ABadccd#SBA2#AAaadccd#BaA3#AAdccd#4#Addccd#Ad5#Accd#6#SBccd#ABS7#Scccd# Bc8#S cd# 9#ABcd#Bc10#Acd#11#A d#12#dd#Ad13# 8.所求文法是GS: SAB AaAc | D DbD | bBaBb | aabb9.函數(shù)a(),f4244g552310.優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化11.目標代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。應著重考慮的問題： (1

26、)如何使生成的目標代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點。12.正規(guī)式 a ( a | b )*。13.刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復寫傳播和刪除無用賦值。14.文法GS:SaB | a Bbc |bBc15.傳值 a=2 傳地址 a=1516.逆波蘭式: abcd-*e/+三元序列: op arg1 arg2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3)17.證明：因為文法GS存在句子 () 有兩個不同的最左推導，所以文法GS是是二義性的。A=>AA=&g

27、t;(A)A=>()A=>() A=>AA=>A=>(A)=>()18.(a*b|b*a)=a,b,ab,ba,aab,bba19.Display表: 嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當一個過程運行時必須跟蹤它的所有外層過程的最新活動記錄起始地址， display表就是用于登記每個外層過程的最新活動記錄起始地址。20.傳地址 a=12傳值 a=521.所求文法是GS: SAC AaaAbb | ab CccC | cc22.逆波蘭式 abc+e*bc+f/+:=三元序列 op arg1 arg2 (1) + b c (2)

28、 * (1) e (3) + b c (4) / (3) f (5) + (2) (4) (6) := a (5) 23.一個文法G別是LL(1)文法的充要條件是: (1) FIRST() FIRST()= (2) 如果 =*>, FIRST() FOLLOW(A)= 24.消除左遞歸SaFS | *aFSS*aFS | F+aF | +a提公共左因子,文法 G(S) SaFS | *aFSS*aFS | F+aFFF |25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進展狀況。主要技術：線性表，對折查找，雜奏技術。五、計算題：1.設文法G(S): S | a | (T)

29、 TT,S | S 消除左遞歸； 構造相應的FIRST和FOLLOW集合； 構造預測分析表 2.語句 if E then S(1) 改寫文法，使之適合語法制導翻譯； (2) 寫出改寫后產(chǎn)生式的語義動作。 3.設文法G（S）：S(T) | aTT+S | S(1）計算FIRSTVT 和LASTVT； （2）構造優(yōu)先關系表。 4.設某語言的for語句的形式為for i:E(1) to E(2) do S其語義解釋為i:E(1)LIMIT:E(2)again: if iLIMIT thenBeginS;i:i1goto againEnd;（1）寫出適合語法制導翻譯的產(chǎn)生式；（2）寫出每個產(chǎn)生式對應的

30、語義動作。5.把語句while a<10 doif c>0 then a:=a+1else a:=a*3-1;翻譯成四元式序列。6.設有基本塊D:=A-CE:=A*CF:=D*ES:=2T:=A-C Q:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假設基本塊出口時只有M還被引用，請寫出優(yōu)化后的四元序列。7.已知文法G(S)Sa | | (T)TT,S | S(1) 給出句子(a,(a,a)的最左推導；(2) 給出句型(T,S),a)的短語, 直接短語，句柄。8.對于 C 語言do S while E語句 (1)改寫文法，使之適合語法制導翻譯； (2)寫出改寫后產(chǎn)

31、生式的語義動作。9.已知文法G(S) SaAcBe AAb| b Bd(1)給出句子abbcde的最左推導及畫出語法樹；(2)給出句型aAbcde的短語、素短語。 10.設文法G(S): S(T) | aS | a TT,S | S 消除左遞歸和提公共左因子； 構造相應的FIRST和FOLLOW集合； 構造預測分析表。11.把語句 if X>0 Y<0 then while X>0 do X:=A*3 else Y:=B+3;翻譯成四元式序列。12.已知文法G(S) EE+T | T TT*F| F F(E)| i (1) 給出句型 (i+i)*i+i的最左推導及畫出語法樹；

32、 (2) 給出句型 (E+T)*i+F 的短語，素短語和最左素短語。 13.設文法G（S）：ST | STTU |TUUi |-U（1）計算FIRSTVT 和LASTVT； （2）構造優(yōu)先關系表。 第53頁共6頁答案：(1)消除左遞，文法變?yōu)镚S：S | a | (T)'TST | ST,ST |此文法無左公共左因子。(2)構造相應的FIRST和FOLLOW集合： FIRST(S)=a, , (， FOLLOW(S)=#, , )FIRST(T)=a, , ( ，F(xiàn)OLLOW(T)=FIRST(T)=, ，F(xiàn)OLLOW(F)=)(3)構造預測分析表：a(),#SSaSS(T)'

33、TTSTTSTTSTTTT,ST2. (1)Cif E thenSCS(1) (2) Cif E then BACK(E.TC, NXQ); C.chain:=E.FC SCS(1) S.chain:=MERG(C.Chain, S(1). Chain)3. (1) FIRSTVT(S)=a, ( FIRSTVT(T)=+, aa, ( LASTVT(S)=a, ) LASTVT(T)=+, a, ) (2) A + ( ) a .> .>+ <. .> <. .>( <. <. <. =. ) .> .> >.4. (1

34、) Ffor i:=E(1) to E(2) do SFS(1)(2) Ffor i:=E(1) to E(2) doGEN(:=, E(1).place, _, entry(i);F.place:=entry(i);LIMIT:=Newtemp;GEN(:=, E(2).place, _, LIMIT);Q:=NXQ;F.QUAD:=q;GEN(j, entry(i), LIMIT, q+2)F.chain:=NXQ;GEN(j, _, _, 0)SFS(1)BACKPATCH(S(1).chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _,

35、_, F.QUAD); S.chain:=F.chain5. (1) (j<, a, 10, (3)(2) (j, _, _, (12)(3) (j>, c, 0, (5)(4) (j, _, _, (8)(5) (+, a, 1, T1)(6) (:=, T1, _, a)(7) (j, _, _, (1)(8) (*, a, 13, T2)(9) (-, T2, 1, T3)(10) (:=, T3, _, a)(11) (j, _, _, (1)6.優(yōu)化后的四元序列D:=A-CE:=A*CF:=D*EM:=F+207. 最左推導S=(T)=>(T,S)=>(S,S

36、)=>(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,S a直接短語 T,S a句柄 T,S8.(1)Sdo M1 S1 while M2 EM (2)M M.quad=nestquad;Sdo M1 S1 while M2 E backpatch(s1.nextlist, M2.quad); backpatch(E.truelist, M1.quad); S.nextlist=E.falelist; 9.(1) S=>aAcBe=>

37、AAbcBe=>abbcBe=>abbcde(2) 短語: aAbcde, Ab, d 素短語: Ab, d10.(1) S (L) | aS SS | LSL L,SL |(2) FIRST(S)=a, ( FIRST(S)=a, (, FIRST(L)=a, ( FIRST(L)=, FOLLOW(S)=, ), # FOLLOW(S)=, ), #FOLLOW(L)= ) FOLLOW(L)= )(3) ( ) a , # SS (L)S aSSSSSSSSSLLSLLSLL,SL LL11.(1) (j>, X, 0, (5)(2) (j, _, _, (3)(3)

38、(j<, Y, 0, (5)(4) (j, _, _, (11)(5) (j>0, X, 0, (7)(6) (j, _, _, (7)(7) (*, 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=>

39、(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)=, , i, - FIRSTVT(T)=, i, - FIRSTVT(U)=i, - LASTVT(S)=, , i, - LASTVT(T)=, i, - LASTVT(U)=i, -(2) i - S .> .> <. .> <. <. <. .> .

40、> <. - <. .> .> <.start1abb2編譯原理期末試題（二）1、 描述由正規(guī)式b*(abb*)*(a| e)定義的語言，并畫出接受該語言的最簡DFA。2、證明文法E ® E + id | id是SLR(1)文法。3、下面是表達式和賦值語句的文法，其中and的類型是bool ´ bool ® bool，+的類型是int ´ int ® int，=的類型是int ´ int ® bool，:= 要求id 和E的類型都是int或者都是bool。為該文法寫一個語法制導定義或翻譯方

41、案，它完成類型檢查。S ® id := EE ® E and E | E + E | E = E |id4、對于下面C語言文件s.c f1(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，則結果是area=12.566360, addr=-1073743076經(jīng)優(yōu)化編譯后，若運行時輸

42、入2，則結果是area=12.566360, addr=-1073743068請解釋為什么輸出結果有區(qū)別。main() float s, pi, r; pi=3.14159;start2abb10ab 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 ® B 0 | B 1 | 1下面的翻譯方案計算這種正二進制數(shù)的十進制值：B

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

44、 i 1;func(j);下面左右兩邊的匯編代碼是兩個不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用func之前將參數(shù)壓棧，調(diào)用結束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有實質(zhì)區(qū)別。請敘述右邊代碼對參數(shù)傳遞的處理方式并推測它帶來的優(yōu)點。func:|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, -4(%ebp)m

45、ovl-4(%ebp), %eax|movl-4(%ebp), %eaxpushl%eax|movl%eax, (%esp)callfunc|callfuncaddl$4, %esp|leaveleave|retret|編譯原理試卷八答案start1abb21、由正規(guī)式b*(abb*)*(a| e)定義的語言是字母表a, b上不含子串a(chǎn)a的所有串的集合。最簡DFA如下：2、先給出接受該文法活前綴的DFA如下：E¢ ®·EE ®·E + idE ®·idI0E¢ ® E·E ® E

46、83;+ idI1E ® id·I2Eid+E ® E +·idI3E ® E + id·I4idI0和I3都只有移進項目，肯定不會引起沖突；I2和I4都無移進項目并僅含一個歸約項目，也肯定不會引起沖突；在I1中，E¢的后繼符號只有$，同第2個項目的展望符號“+”不一樣，因此I1也肯定不會引起沖突。由此可以斷定該文法是SLR(1)的。3、語法制導定義如下。S ® id := E S.type := if (id.type = bool and E.type = bool) or (id.type = int and

47、 E.type = int)then type_ok else type_error E ® E1 and E2 E.type := if E1.type = bool and E2.type = bool then bool else type_error E ® E1 + E2 E.type := if E1.type = int and E2.type = int then int else type_error E ® E1 = E2 E.type := if E1.type = int and E2.type = int then bool else type_error E