編譯原理考試試題及答案匯總

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

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

3、|y所識別的語言是 。A . () xyx B. ( ) (xyx)* C. ( ) xnyxn(n >0) D. ( ) x*yx*4. 如果文法G是無二義的，則它的任何句子a A ( ) 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B ( ) 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C ( ) 最左推導(dǎo)和最右推導(dǎo)必定相同D ( ) 可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同5構(gòu)造編譯程序應(yīng)掌握 。A ( )源程序B( ) 目標(biāo)語言C( ) 編譯方法D( ) 以上三項(xiàng)都是6四元式之間的聯(lián)系是通過 實(shí)現(xiàn)的。A ( ) 指示器B ( ) 臨時變量C ( ) 符號表D ( ) 程序變量7.

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

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

6、本功能。答： 語義分析的基本功能包括 : 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2. 考慮文法 GS:S t (T) | a+S | aT t t,S | S消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸:St (T) | a+S | aTt ST'T't ,st ' | £提取公共左因子：St(T) | aS'S't +S |&TtST'T't ,ST ' |£3. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)的逆波蘭表示。解： w a b + c d e

7、 10 - / + 8 + * +4. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列： while (A<C A B<D)if (A > 1) C=C+1;else while (A < D)A=A+2;。解：該語句的四元式序列如下(其中E1、E2和E3分別對應(yīng)A V CA Bv D、A1和A<D ,并且關(guān)系運(yùn)算符優(yōu)先級高 )：100 (j<,A,C,102)101 (j,_,_,113)102 (j<,B,D,104)103 (j,_,_,113)104 (j=,A,1,106)105 (j,_,_,108)106 (+, C, 1, C)1

8、07 (j,_,_,112)108 (j w ,A,D,110)109 (j,_,_,112)110 (+, A, 2, A)111 (j,_,_,108)112 (j,_,_,100)1135. 已知文法 GS為S t aSb|Sb|b，試證明文法 GS為二義文法。證明：由文法GS: StaSb|Sb|b,對句子aabbbb對應(yīng)的兩棵語法樹為：因此，文法GS為二義文法。五計(jì)算題(io分)已知文法A->aAd|aAb| &判斷該文法是否是 SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。解：增加一個非終結(jié)符 S/后，產(chǎn)生原文法的增廣文法有：S'->

9、;AA- >aAd|aAb| &下 面 構(gòu) 造 它 的 LR(0) 項(xiàng) 目 集 規(guī) 范a.bdA站！ 2血 A->*L：AdATaAdA->-li：luS' *accA->a'AdA->*aAdA供I：A>aA*dATaAbI31I : A->aAb'I :A今加血kA->d-從上表可看出,狀態(tài)10和12存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對于10來說有： FOLLOW(A)Q a=b,d,# n a= ,<!所以在I0狀態(tài)下面臨輸入符號為a時移進(jìn)，為b,d,#時歸約，為其他時報(bào)錯。對于I2來說有也

10、有與I0完全相同的結(jié)論。這就是說，以上的移進(jìn)-歸約沖突是可以解決的，因此該文法是SLR(1)文法。其SLR(1)分析表為：狀態(tài)ACTIONGOTOabdA0s;iir：11cc2s=rirj33Si缶4I:X：r：5X1riTiTl對輸入串a(chǎn)b#給出分析過程為:歩驟狀態(tài)挨符號棧輸入串ACTIONGOTO10#ab#s：202b#Tj33023bSs40234#aAb叱1501#A# 1acc、是非題：1. 一個上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。2. 一個句型的直接短語是唯一的。3. 已經(jīng)證明文法的二義性是可判定的。4. 每個基本塊可用一個 DAG表示。5. 每個過程的活動記錄的體

11、積在編譯時可靜態(tài)確定。6.2型文法一定是3型文法。7. 一個句型一定句子。8. 算符優(yōu)先分析法每次都是對句柄進(jìn)行歸約。X9. 采用三元式實(shí)現(xiàn)三地址代碼時，不利于對中間代碼進(jìn)行優(yōu)化。10. 編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。11. 一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。X12. 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。13. 遞歸下降分析法是一種自下而上分析法。14. 并不是每個文法都能改寫成LL（1）文法。15. 每個基本塊只有一個入口和一個出口。16. 一個LL（1）文法一定是無二義的。17. 逆波蘭法表示的表達(dá)試亦稱前綴式。18. 目標(biāo)代碼生成時，應(yīng)考慮如何充

12、分利用計(jì)算機(jī)的寄存器的問題。19. 正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。20. 一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。21.3型文法一定是2型文法。22.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，答案：1. x 2. X()(12. V 13. x 14.()(則文法是二義性的。x 7. x 8.xV 15. V 16. V 17. x 18. V 19. V 20. x 21. V 22. V3. x 4. V 5. V 6.9.)10.11.、填空題：2. 編譯過程可分為（詞法分析），（語法分析），（語義分析與中間代碼生成）,（優(yōu)化）和（目標(biāo)代碼生成）五個階段。）。）語句兩大類

13、。3. 如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是（二義性的4. 從功能上說，程序語言的語句大體可分為 （執(zhí)行性 ）語句和（說明性5. 語法分析器的輸入是（ 單詞符號），其輸出是（ 語法單位）。6. 掃描器的任務(wù)是從（源程序中 ）中識別出一個個（單詞符號）。7. 符號表中的信息欄中登記了每個名字的有關(guān)的性質(zhì)，如（類型、種屬、所占單元大小、地址）等等。8. 一個過程相應(yīng)的DISPLA丫表的內(nèi)容為（現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址）10. 常用的兩種動態(tài)存貯分配辦法是（棧式）動態(tài)分配和（堆式）動態(tài)分配。11. 一個名字的屬性包括（類型）和（作用域）。12. 常用的參數(shù)

14、傳遞方式有（傳地址），（傳值），（傳名）13. 根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個級別。14. 語法分析的方法大致可分為兩類，一類是（自上而下）分析法，另一類是（自下而上）分析法。15. 預(yù)測分析程序是使用一張（分析表）和一個（符號棧）進(jìn)行聯(lián)合控制的。17. 一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是（初）態(tài) ；而且實(shí)際上至少要有一個（終 ）態(tài)。19. 語法分析是依據(jù)語言的（語法）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進(jìn)行的。21. 一個文法G,若它的預(yù)測分析表 M不含多重定義，則該文法是（LL（1）文法）文法。22. 對于數(shù)據(jù)空間

15、的存貯分配，F(xiàn)ORTRAN采用（靜態(tài)策略，PASCAL采用（動態(tài)）策略。24.最右推導(dǎo)亦稱為（規(guī)范推導(dǎo)），由此得到的句型稱為（規(guī)范）句型。26. 對于文法G,僅含終結(jié)符號的句型稱為 （句子）。27. 所謂自上而下分析法是指（從開始符號出發(fā)，向下推導(dǎo)，推出句子）29.局限于基本塊范圍的優(yōu)化稱（ 局部優(yōu)化 ）。31.2型文法又稱為（上下文無關(guān)）文法；3型文法又稱為（正則 ）文法。32. 每條指令的執(zhí)行代價定義為（指令訪問主存次數(shù)加1）33. 算符優(yōu)先分析法每次都是對（最左素短語）進(jìn)行歸約。三、名詞解釋題：1. 局部優(yōu)化 局限于基本塊范圍的優(yōu)化稱。2. 二義性文法 如果一個文法存在某個句子對應(yīng)兩棵不

16、同的語法樹，則稱這個文法是二義性文法。3. DISPLAY表-過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。5. 最左推導(dǎo) 任何一步a =>3都是對a中的最右非終結(jié)符替換。6. 語法- 一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7. 文法 描述語言的語法結(jié)構(gòu)的形式規(guī)則。8. 基本塊-指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個 語句，出口就是其中的最后一個語句。9.語法制導(dǎo)翻譯在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序進(jìn)行翻譯的辦法叫做語法A的短語。假定a3 3是文法G的一個句型,制導(dǎo)翻譯。10. 短語 令G是一個文法，S

17、劃文法的開始符號， A3且A二吉3，則稱3是句型as相對非終結(jié)符11. 待用信息-如果在一個基本塊中，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。12. 規(guī)范句型-由規(guī)范推導(dǎo)所得到的句型。13. 掃描器-執(zhí)行詞法分析的程序。14. 超前搜索-在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。15. 句柄 一個句型的最左直接短語。16. 語法制導(dǎo)翻譯-在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義程序進(jìn)行翻譯的方法叫做語法制導(dǎo)翻譯。17. 規(guī)范句型-由規(guī)范推導(dǎo)所得到的句型。18. 素短語-素短語是指這樣一個短語，至少含有一個終結(jié)

18、符，并且，除它自身外不再含任何更小的素短語。19. 語法-是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。_20. 待用信息-如果在一個基本塊中，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。21. 語義-定義程序的意義的一組規(guī)則。四、簡答題：1. 寫一個文法G,使其語言為 不以0開頭的偶數(shù)集。2. 已知文法G（S）及相應(yīng)翻譯方案St aAb print “1 ” St aprint“ 2” at AS print“ 3 ” At cprint“ 4” 輸入acab,輸出是什么？3. 已知文法G（S）St bAaAt （B | aBt Aa

19、）寫出句子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)St dABA aA| aBt Bb| £描述的語言是什么？6. 證明文法G(S)S t SaS| e是二義性的。7. 已知文法G(S)S t BAAt BS| dBt aA| bS | c的預(yù)測分析表如下abcd#SSt BASt BA4 BAAAt BSAt

20、 BSAt BSAt dBBt aAB t bSB t c給出句子adccd的分析過程。8. 寫一個文法 G,使其語言為 L(G)=a lbmclanbn| l>=0, m>=1, n>=29. 已知文法G(S):St a| (T)Tt T,S|S的優(yōu)先關(guān)系表如下：關(guān)系a()5a-.>.>(V.V.=V.)-.>.>JV.V.>.>請計(jì)算出該優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)表。10. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？11. 目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時通常應(yīng)考慮哪幾個問題？12. 一字母表工=a, b，試寫出工上所有以a為首

21、的字組成的正規(guī)集相對應(yīng)的正規(guī)式。13. 基本的優(yōu)化方法有哪幾種？14. 寫一個文法G,使其語言為L(G)=ab ncn| n > 015. 考慮下面的程序：procedure p(x, y, z);beginy：=y+z;z:=y*z+xen d;begina:=2;b:=3;p(a+b, b, a);print aen d.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么？16. 寫出表達(dá)式a + b*(c-d)/e的逆波蘭式和三元序列。17. 證明文法G(A)A t AA | (A)|£是二義性的。18. 令=a,b，則正規(guī)式a b|b a表示的正規(guī)

22、集是什么？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 aen d.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么？21. 寫一個文法G,使其語言為L(G)=a nbnc1 n>0 為奇數(shù)，m>0為偶數(shù)22. 寫出表達(dá)式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。23. 一個文法G別是LL(1)文法的充要條件是什么？24. 已知文法GSSt S*aF | aF | *

23、aFFt +aF | +a消除文法左遞歸和提公共左因子。25. 符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？答案：1.所求文法是GS:St AB |B A0At AD |CBt 2 |4 |6 |8Ct 1 |3 |5 |7 |9 |BDt 0 |C2. 輸出是42313. 句子b(aa)b的規(guī)范歸約過程：步驟符號棧輸入串動作0#b(aa)b#預(yù)備1#b(aa)b#移進(jìn)2#b(aa)b#移進(jìn)3#b(aa)b#移進(jìn)4#b(Aa)b#歸約5#b(Ma)b#移進(jìn)6#b(Ma)b#移進(jìn)7#b(Bb#歸約8#bAb#歸約9#bAb#移進(jìn)10#S#接受4. 傳地址 A=6, B=16傳值 A=2,

24、B=45. L(G)=da nbm |n>0, m > 06. 證明：因?yàn)槲姆℅S存在句子aa有兩個不同的最左推導(dǎo)，所以文法GS是是二義性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aaS=>SaS=>aS=>aSaS=>aaS=>aa7. 句子adccd的分析過程：步驟符號棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#St BA2#AAaadccd#Bt aA3#AAdccd#4#Addccd#At d5#Accd#6#SBccd#At BS7#Scccd#Bt c8#Scd#9#ABcd#Bt c10

25、#Acd#11#Ad#12#dd#At d13#8. 所求文法是GS:S t ABA t aAc | DD t bD | bBt aBb | aabb9.函數(shù)a()511. 目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。應(yīng)著重考慮的問題：(1) 如何使生成的目標(biāo)代碼較短；(2) 如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3) 如何充分利用指令系統(tǒng)的特點(diǎn)。12. 正規(guī)式 a ( a | b )*。13. 刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播和刪除無用賦值。14. 文法 GS:St aB | aB t be |bBc15. 傳值 a=2傳地址

26、 a=1516.逆波蘭式:abcd-*e/+三元序列：oparg1 arg2(1)-cd*b(1)(3)/ (2)e+a(3)17.證明：因?yàn)槲姆℅S存在句子()有兩個不同的最左推導(dǎo)，所以文法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ù)，因此，當(dāng)一個過程運(yùn)行時必須跟蹤它的所有外 層過程的最新活動記錄起始地址，display 表就是用于登記每個外

27、層過程的最新活動記錄起始地址。20. 傳地址 a=12 傳值 a=521. 所求文法是GS:S t ACA t aaAbb | abC t ceC | cc22.逆波蘭式 abc+e*bc+f/+:=三元序列oparg1arg2(1) +bc(2) *(1)e(3) +bc/(3)f(5) +(2)(4)(6):=a(5)23. 一個文法G別是LL(1)文法的充要條件:(1) FIRST( a ) n FIRST( 3 )=(2) 如果 3 =*> £ , FIRST( a ) n FOLLOW(A)=©24. 消除左遞歸St aFS | *aFS 'S

28、9;t *aFS' |&Ft +aF | +a 提公共左因子 , 文法 G' (S)StaFS'| *aFS 'S't *aFS' |&Ft+aF'F't F | &25. 作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進(jìn)展?fàn)顩r。 主要技術(shù)：線性表，對折查找，雜奏技術(shù)。五、計(jì)算題：1. 設(shè)文法 G(S):S t a | a | (T)T t T,S | S 消除左遞歸；構(gòu)造相應(yīng)的FIRST和FOLLOW合； 構(gòu)造預(yù)測分析表2. 語句 if E then S(1) 改寫文法，使之適合語法制導(dǎo)翻譯；

29、(2) 寫出改寫后產(chǎn)生式的語義動作。3. 設(shè)文法 G( S)：St(T) | aTt T+S | S(1)計(jì)算 FIRSTVT 和 LASTVT；(2) 構(gòu)造優(yōu)先關(guān)系表。4. 設(shè)某語言的 for 語句的形式為for i:= E(1) to E do S其語義解釋為i: = E(1)LIMIT: = Eagai n: if iv= LIMIT thenBeginS;i: = i + 1goto again End;( 1 )寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；( 2)寫出每個產(chǎn)生式對應(yīng)的語義動作。5. 把語句 while a<10 doif c>0 then a:=a+1 else a:=

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

31、(1) 給出句子 abbcde 的最左推導(dǎo)及畫出語法樹；(2) 給出句型aAbcde的短語、素短語。10. 設(shè)文法 G(S):S t (T) | aS | aT tT,S | S 消除左遞歸和提公共左因子； 構(gòu)造相應(yīng)的FIRST和FOLLOW!合；構(gòu)造預(yù)測分析表。11. 把語句if X>0 V Y<0then while X>0 do X:=A*3else Y:=B+3;翻譯成四元式序列。12. 已知文法 G(S)E t E+T | TTtT*F| FFt(E)| i(1) 給出句型 (i+i)*i+i 的最左推導(dǎo)及畫出語法樹；(2) 給出句型 (E+T)*i+F 的短語，素

32、短語和最左素短語。13. 設(shè)文法 G(S)：StT | S VTTt u |T 人 UUti |-U (1)計(jì)算 FIRSTVT 和 LASTVT；( 2)構(gòu)造優(yōu)先關(guān)系表。答案： 消除左遞，文法變?yōu)镚 S:St a | a | (T)'ST' | ST't ,ST' | £此文法無左公共左因子。構(gòu)造相應(yīng)的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)造預(yù)測分析表：aa

33、()5#SSTaSt人St (T)'TTt st'Tt ST'Tt ST'T'T't£T't ,ST '2. (1)CT if E thenSt cS1)(2)C tif e then BACK(E.TC, NXQ); C.chain:=E.FCS t cS1 S.chain:=MERG(C.Chain, S .Chain)3. (1) FIRSTVT(S)=a, ( FIRSTVT(T)=+, aa, (LASTVT(S)=a, ) LASTVT(T)=+, a, )a+()a.>.>+V.>V.&g

34、t;(V.V.V.=).>.>>.(2)(1) (2)4. (1) F t for i:=E ()to E doSt fS1)(2) Ft for i:=E to E do GEN(:=, E (1) .place, _, entry(i); F.place:=e ntry(i); LIMIT:=Newtemp;GEN(:=, E .place, _, LIMIT); Q:=NXQ;F.QUAD:=q;GEN(j w , entry(i), LIMIT, q+2) F.chai n:=NXQ;GEN(j, _, _, 0) St fL BACKPATCH(S .chain,

35、NXQ);GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD);S.chai n:=F.chain5. (1) (j<, a,'10' , (3)(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)化后

36、的四元序列D:=A-CE:=A*CF:=D*EM:=F+207. 最左推導(dǎo)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,S a直接短語T,Sa句柄T,S8. (1)St do Mi Si while M 2 EM £(2)Mt £M.quad=nestquad;Stdo Mi Si while M 2 E backpatch(s i.nextlist, M2.quad);bac

37、kpatch(E.truelist, Mi.quad);S.nextlist=E.falelist;9.(i) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde(2)短語 : aAbcde, Ab, d 素短語 : Ab, di0.(i) St (L) | aS 'S't S | £LtSL'L't,SL' | £(2)FIRST(S)=a, (FIRST(S' )=a, (,£ FIRST(L)=a, (FIRST(L')=,£ FOLLOW(S)=, ),

38、 # FOLLOW(S' )=, ), #FOLLOW(L)= )FOLLOW(L')= )()a5#SS t (L)S t aS'S'S sS't £ST SS't £ST £LLt SL'Lt SL'LT,SL 'L'LT £11. (1) (j>, X, 0, (5)(j, _, _, (3)(3) (j<, Y, 0, (5)(j，亠，(11)(5) (j>0, X, 0,)(6) (j, _, _, (7)(7) (*, A, 3, T 1)(8)

39、 (:=, T1, _, N)(9) (j,亠，(5)(10) (j,亠，(13)(11) (+, B, 3, T2)(12) (:=, T 2, _, 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

40、)*i+F素短語i, E+T最左素短語E+T13. (1) 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)iVA-S.>.>VV.>V.V.AV.>.>V.-V.>.>V.DFA。1、 描述由正規(guī)式b*(abb*)* (a|)定義的語言，并畫出接受該語言的最簡2、證明文法 E ； E + id | id 是 SLR(1文法。3、 下面是表達(dá)式和賦值語句的文法，其

41、中and的類型是bool bool bool, +的類型是int int . int,=的類型是int int . bool ,:=要求id和E的類型都是int或者都是bool。為該 文法寫一個語法制導(dǎo)定義或翻譯方案，它完成類型檢查。S > id := EE > Eand E | E + E | E = E |id4、對于下面C語言文件s.cf1(i nt x)long x;x = 1;f2(i nt x)long x;x = 1;某編譯器編譯時報(bào)錯如下：s.c: In function f1 ':s.c:3: warning: declarati on of x'

42、 shadows a parameter請回答，對函數(shù)f2為什么沒有類似的警告錯誤。5、 下面C語言程序經(jīng)非優(yōu)化編譯后，若運(yùn)行時輸入2，則結(jié)果是area=12.566360,addr=-1073743076經(jīng)優(yōu)化編譯后，若運(yùn)行時輸入2，則結(jié)果是area=12.566360,addr=-1073743068請解釋為什么輸出結(jié)果有區(qū)別。main ()float s, pi, r;pi=3.14159;scan f("%f', &r);prin tf("area=%f,addr=%dn", s=pi*r*r, &r);6、 描述由正規(guī)式 b a(

43、bb a) b定義的語言，并畫出接受該語言的最簡DFA。7、 下面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0和1的串集：B T B 0 | B 1 | 1下面的翻譯方案計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值：B Bi0B.val :=B1.val2 |Bi1B.val :=B1 .val2 +1|1 B.val := 1 請消除該基礎(chǔ)文法的左遞歸，再重寫一個翻譯方案，它仍然計(jì)算這種正二進(jìn)制數(shù)的十進(jìn) 制值。& 在C語言中，如果變量i和j都是long類型，請寫出表達(dá)式 &和表達(dá)式&-&j的類型表 達(dá)式。為幫助你回答問題，下面給出一個程序作為提示，它運(yùn)行時輸出1。mai n() long i

44、, j;pri ntf( “ d , &t&j);9、一個C語言的函數(shù)如下：fun c(i) long i; long j; j = i -1； fun c(j);下面左右兩邊的匯編代碼是兩個不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用func之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有 實(shí)質(zhì)區(qū)別。請敘述右邊代碼對參數(shù)傳遞的處理方式并推測它帶來的優(yōu)點(diǎn)。func:| func:pushl%ebppushl%ebpmovl%esp, %ebpmovl%esp, %ebpsubl$4, %espsubl$8, %espmovl8(%ebp), %

45、edxmovl8(%ebp), %eaxdecl%edxdecl%eaxmovl%edx, -4(%ebp)movl%eax, -4(%ebp)movl-4(%ebp), %eaxmovl-4(%ebp), %eaxpushl%eaxmovl%eax, (%esp)callfunccallfuncaddl$4, %espleaveleaveretret編譯原理試卷八答案1、由正規(guī)式b*(abb*)*(a|;)定義的語言是字母表a, b上不含子串a(chǎn)a的所有串的集合。最簡DFA如下：2、先給出接受該文法活前綴的DFA如下:也肯定不會引起沖突;在h中，E的后繼符號只有$，同第2個項(xiàng)目的展望符號+”不

46、一樣,因此I1也肯定不會引起沖突。由此可以斷定該文法是SLR(1的。3、語法制導(dǎo)定義如下。S > id := E S.type := if (id.type = bool and E.type = bool) or (id.type = int andE.type = int) then type_ok else type_error E tE1 andE2E.type:=if E1 .type= bool and E?.type = bool then bool else type_error E tE1 +E2E.type:=if E1 .type= int and E?.type=

47、 intthenint else type_error E tE1 =E2E.type:=if E1 .type= int and E?.type= intthenbool else type_error E -idE.type:=lookup(id.entry) 4、對于函數(shù)fl，局部變量x聲明的作用域是整個函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問形式 參數(shù)X。由于這是一個合法的 C語言函數(shù)，因此編譯器給出警告錯誤。對于函數(shù)f2，由于局部變量x的作用域只是函數(shù)體的一部分，不會出現(xiàn)上述問題，因而編譯器不報(bào)錯。5、使用非優(yōu)化編譯時，變量s, pi, r在局部數(shù)據(jù)區(qū)都分配 4個字節(jié)的空間。使用優(yōu)化編譯時,

48、由于復(fù)寫傳播，pi*r*r變成3.14159*r*r，pi=3.14159成為無用賦值而刪去，函數(shù)中不再有pi的引用，因此不必為 pi分配空間。類似地，s=3.14159*r*r也是一個無用賦值(表達(dá)式要 計(jì)算，但賦值是無用的)，也不必為s分配空間。這樣，和非優(yōu)化情況相比，局部數(shù)據(jù)區(qū)少 了 8個字節(jié)，因此r的地址向高地址方向移動了8個字節(jié)。6、正規(guī)式b a(bb a) b -體現(xiàn)的特點(diǎn)是，每個 a的左邊都有若干b，除非a是第一個字母。該 正規(guī)式定義的語言是：至少含一個 a,但不含子串a(chǎn)a的所有a和b的串集。最簡DFA如下:7、消除左遞歸后的文法:B > 1 BB )0 B' |

49、1 B ' | ;相應(yīng)的翻譯方案如下：B一；1 B.i := 1 B B.val := B .valB”r0 B1.i := B.i 2 B1 B .val := Bl.val|1 B1.i := B.i 2 +1 B1 B.val := B 1.val|;B .val := B.i&表達(dá)式&的類型表達(dá)式是 pointer(long)，表達(dá)式&-&j的類型表達(dá)式是long。按照C語言 的規(guī)定，指向同一個類型的兩個指針可以相加減，它們值的差是它們之間的元素個數(shù)。9、左邊的編譯器版本：一般只為局部變量分配空間。調(diào)用函數(shù)前，用若干次pushl指令將參數(shù)壓棧，返

50、回后用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)點(diǎn)是每次函數(shù)調(diào)用結(jié)束后不需要執(zhí)行addl $n, %esp指令，另外增加優(yōu)化的可能性。編譯原理期末試題(三)1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對循環(huán)的優(yōu)化可以有哪三種?答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類；對循環(huán)的優(yōu)化有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計(jì)算強(qiáng)度削減

51、。M a )2、寫出表達(dá)式a=b*c+b*d對應(yīng)的逆波蘭式、四元式序列和三元式序列。答：逆波蘭式：abc*bd*+:=四元式序列：三兀式序列:OP ARG1ARG2(1) (*，b，c，t 1)(1)(*b，c )(*，b，d，t 2)(*b，d )(3) (+ ，t1，t 2,t 3)(3)什(1) ，(2)(:=，t3，/，a)(:=(3)，a)3、對于文法G(S):答.1)S= bMb = b(Lb= b(Ma)bS2) 短語：Ma) ， (Ma)， b(Ma)b直接短語：Ma) 句柄：Ma)bMb三、設(shè)有子母表a，b上的正規(guī)式R=(ab|a)*。S； bMbM-； (L |a L； Ma)解: ( 1)(2) 將(1)所得的非確定有限自動機(jī)確定化£