[高命中]編譯原理期末試題及答案

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

2、)10一個(gè)語(yǔ)義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 ()二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1詞法分析器的輸出結(jié)果是_。A( ) 單詞的種別編碼 B( ) 單詞在符號(hào)表中的位置 C( ) 單詞的種別編碼和自身值 D( ) 單詞自身值2 正規(guī)式 M 1 和 M 2 等價(jià)是指_。 A( ) M1和M2的狀態(tài)數(shù)相等 B( ) M1和M2的有向邊條數(shù)相等C( ) M1和M2所識(shí)別的語(yǔ)言集相等 D( ) M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識(shí)別的語(yǔ)言是_。A( ) xyx B( ) (xyx)* C( ) xnyxn(n0

3、) D( ) x*yx* 4如果文法G是無(wú)二義的，則它的任何句子_。A( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同 B( ) 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同 C( ) 最左推導(dǎo)和最右推導(dǎo)必定相同 D( )可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同 5構(gòu)造編譯程序應(yīng)掌握_。A( )源程序B( ) 目標(biāo)語(yǔ)言 C( ) 編譯方法 D( ) 以上三項(xiàng)都是 6四元式之間的聯(lián)系是通過(guò)_實(shí)現(xiàn)的。 A( ) 指示器 B( ) 臨時(shí)變量 C( ) 符號(hào)表 D( ) 程序變量 7表達(dá)式(AB)(CD)的逆波蘭表示為_(kāi)。A. ( ) ABCD B( ) ABCD C( ) ABCD D( ) ABC

4、D 8. 優(yōu)化可生成_的目標(biāo)代碼。A( ) 運(yùn)行時(shí)間較短 B( ) 占用存儲(chǔ)空間較小C( ) 運(yùn)行時(shí)間短但占用內(nèi)存空間大 D( ) 運(yùn)行時(shí)間短且占用存儲(chǔ)空間小9下列_優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A. ( ) 強(qiáng)度削弱 B( ) 刪除歸納變量 C( ) 刪除多余運(yùn)算 D( ) 代碼外提10編譯程序使用_區(qū)別標(biāo)識(shí)符的作用域。 A. ( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)名B( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的靜態(tài)層次C( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的動(dòng)態(tài)層次 D. ( ) 標(biāo)識(shí)符的行號(hào)三、填空題(每空1分，共10分)1計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析

5、器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。3自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。4一個(gè)LR分析器包括兩部分：一個(gè)總控程序和_一張分析表_。5后綴式abc-/所代表的表達(dá)式是_a/(b-c)_。 6局部?jī)?yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。四、簡(jiǎn)答題（20分）1. 簡(jiǎn)要說(shuō)明語(yǔ)義分析的基本功能。答：語(yǔ)義分析的基本功能包括: 確定類(lèi)型、類(lèi)型檢查、語(yǔ)義處理和某些靜態(tài)語(yǔ)義檢 查。2. 考慮文法 GS: S (T) | a+S | a T T,S | S 消除文法的左遞歸及提取公共左因子。解：消除文法

6、GS的左遞歸： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 3. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫(xiě)出相應(yīng)的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +5. 已知文法 GS 為 S aSb|Sb|b ，試證明文法 GS 為二義文法。證明： 由文法GS：SaSb|Sb|b，對(duì)句子aabbbb對(duì)應(yīng)的兩棵語(yǔ)法樹(shù)為： 因此，文法GS為二義文法。 五.計(jì)算題（10分）已知文法 A-aAd|aAb| 判斷該文法是否是 SLR(1) 文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串 a

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

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

9、自下而上分析法。 ( )14.并不是每個(gè)文法都能改寫(xiě)成LL(1)文法。 ( )15.每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。 ( )16.一個(gè)LL(1)文法一定是無(wú)二義的。 ( )17.逆波蘭法表示的表達(dá)試亦稱(chēng)前綴式。 ( )18.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( )19.正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。 ( )20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則文法是二義性的。 ( )答案：1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.12. 1

10、3. 14. 15. 16. 17. 18. 19. 20. 21. 22.二、填空題：2.編譯過(guò)程可分為 （ 詞法分析） ，（語(yǔ)法分析），（語(yǔ)義分析與中間代碼生成 ），（優(yōu)化）和（目標(biāo)代碼生成 ）五個(gè)階段。3.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是（ 二義性的 ）。 4.從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為（ 執(zhí)行性 ）語(yǔ)句和（說(shuō)明性 ）語(yǔ)句兩大類(lèi)。5.語(yǔ)法分析器的輸入是（ 單詞符號(hào) ），其輸出是（ 語(yǔ)法單位 ）。6.掃描器的任務(wù)是從（ 源程序中 ）中識(shí)別出一個(gè)個(gè)（ 單詞符號(hào) ）。7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如(類(lèi)型、種屬、所占單元大小、地址）等等

11、。8.一個(gè)過(guò)程相應(yīng)的DISPLAY表的內(nèi)容為(現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址)10.常用的兩種動(dòng)態(tài)存貯分配辦法是（棧式）動(dòng)態(tài)分配和（堆式）動(dòng)態(tài)分配。11.一個(gè)名字的屬性包括( 類(lèi)型)和(作用域 )。12.常用的參數(shù)傳遞方式有(傳地址），（傳值），（傳名）13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為(局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個(gè)級(jí)別。14.語(yǔ)法分析的方法大致可分為兩類(lèi)，一類(lèi)是（ 自上而下 ）分析法，另一類(lèi)是（ 自下而上 ）分析法。15.預(yù)測(cè)分析程序是使用一張（ 分析表 ）和一個(gè)（ 符號(hào)棧 ）進(jìn)行聯(lián)合控制的。17.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài),其中有一個(gè)被認(rèn)為是（初）態(tài)

12、;而且實(shí)際上至少要有一個(gè)（終 ）態(tài)。19.語(yǔ)法分析是依據(jù)語(yǔ)言的（語(yǔ)法 ）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語(yǔ)言的（語(yǔ)義）規(guī)則進(jìn)行的。21.一個(gè)文法G，若它的預(yù)測(cè)分析表M不含多重定義，則該文法是（LL(1) 文法）文法。22.對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN采用( 靜態(tài)策略， PASCAL采用( 動(dòng)態(tài))策略。24.最右推導(dǎo)亦稱(chēng)為（規(guī)范推導(dǎo)），由此得到的句型稱(chēng)為（規(guī)范）句型。26.對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱(chēng)為 ( 句子 )。27.所謂自上而下分析法是指(從開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子）29.局限于基本塊范圍的優(yōu)化稱(chēng)（ 局部?jī)?yōu)化 ）。31.2型文法又稱(chēng)為（上下文無(wú)關(guān)）文法；3型文法又稱(chēng)為

13、（正則 ）文法。32.每條指令的執(zhí)行代價(jià)定義為(指令訪問(wèn)主存次數(shù)加1）33.算符優(yōu)先分析法每次都是對(duì)(最左素短語(yǔ)）進(jìn)行歸約。四、簡(jiǎn)答題：1.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 不以0開(kāi)頭的偶數(shù)集。2.已知文法G(S)及相應(yīng)翻譯方案SaAb print “1”Sa print “2”AAS print “3”Ac print “4”輸入acab, 輸出是什么？3. 已知文法G(S)SbAaA(B | aBAa)寫(xiě)出句子b(aa)b的規(guī)范歸約過(guò)程。4. 考慮下面的程序：procedure p(x, y, z)；beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2;P(A, A,

14、 B);Print A, B end.試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 A, B的值是什么? 5文法G(S)SdABAaA| aBBb| 描述的語(yǔ)言是什么？6. 證明文法G(S) SSaS| 是二義性的。7. 已知文法G(S) SBAABS| dBaA| bS | c的預(yù)測(cè)分析表如下 a b c d # SSBASBASBA AABSABSABSAd BBaA BbS Bc給出句子 adccd 的分析過(guò)程。8. 寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 L(G)=albmclanbn| l=0, m=1, n=2 9. 已知文法G(S):Sa| (T)TT,S|S的優(yōu)先關(guān)系表如下

15、：關(guān)系a(),a-.(.=.,.請(qǐng)計(jì)算出該優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)表。10. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？11. 目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？12. 一字母表=a, b，試寫(xiě)出上所有以a為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。13. 基本的優(yōu)化方法有哪幾種？14. 寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 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 aend.試問(wèn)，若參數(shù)傳遞的方式分別采

16、用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a的值是什么? 16.寫(xiě)出表達(dá)式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.試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a的值是什么? 21.寫(xiě)一個(gè)文法G, 使其語(yǔ)言為 L(G)=anbncm

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

18、#b(Aa)b#歸約5 #b(Ma)b#移進(jìn)6#b(Ma)b#移進(jìn)7#b(B b# 歸約8#bAb#歸約9#bAb#移進(jìn)10#S#接受4.傳地址 A=6, B=16傳值 A=2, B=45.L(G)=danbm |n0, m06.證明： 因?yàn)槲姆℅S存在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。S=SaS=SaSaS=aSaS=aaS=aa S=SaS=aS=aSaS=aaS=aa7.句子 adccd 的分析過(guò)程：步驟符號(hào)棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#SBA2#AAaadccd#BaA3#AAdccd#4#Addccd#Ad5#Accd#6#SBccd#AB

19、S7#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)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化11.目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。應(yīng)著重考慮的問(wèn)題： (1)如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點(diǎn)。12.正規(guī)式 a ( a | b )*。13

20、.刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫(xiě)傳播和刪除無(wú)用賦值。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.證明：因?yàn)槲姆℅S存在句子 () 有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。A=AA=(A)A=()A=() A=AA=A=(A)=()18.(a*b|b*a)=a,b,ab,ba,aab,bba19.Display表: 嵌套層次顯示表由于過(guò)程嵌套允

21、許內(nèi)層過(guò)程引用外層過(guò)程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過(guò)程運(yùn)行時(shí)必須跟蹤它的所有外層過(guò)程的最新活動(dòng)記錄起始地址， display表就是用于登記每個(gè)外層過(guò)程的最新活動(dòng)記錄起始地址。20.傳地址 a=12傳值 a=521.所求文法是GS: SAC AaaAbb | ab CccC | cc22.逆波蘭式 abc+e*bc+f/+:=三元序列 op arg1 arg2 (1) + b c (2) * (1) e (3) + b c (4) / (3) f (5) + (2) (4) (6) := a (5) 23.一個(gè)文法G別是LL(1)文法的充要條件是: (1) FIRST() FIRST()= (2)

22、如果 =*, FIRST() FOLLOW(A)= 24.消除左遞歸SaFS | *aFSS*aFS | F+aF | +a提公共左因子,文法 G(S) SaFS | *aFSS*aFS | F+aFFF |25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進(jìn)展?fàn)顩r。主要技術(shù)：線(xiàn)性表，對(duì)折查找，雜奏技術(shù)。五、計(jì)算題：1.設(shè)文法G(S): S | a | (T) TT,S | S 消除左遞歸； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測(cè)分析表 2.語(yǔ)句 if E then S(1) 改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯； (2) 寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。 4.設(shè)某語(yǔ)言的for

23、語(yǔ)句的形式為for i:E(1) to E(2) do S其語(yǔ)義解釋為i:E(1)LIMIT:E(2)again: if iLIMIT thenBeginS;i:i1goto againEnd;（1）寫(xiě)出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式；（2）寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。5.把語(yǔ)句while a0 then a:=a+1else a:=a*3-1;翻譯成四元式序列。6.設(shè)有基本塊D:=A-CE:=A*CF:=D*ES:=2T:=A-C Q:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假設(shè)基本塊出口時(shí)只有M還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元序列。7.已知文法G(S)Sa | | (T)T

24、T,S | S(1) 給出句子(a,(a,a)的最左推導(dǎo)；(2) 給出句型(T,S),a)的短語(yǔ), 直接短語(yǔ)，句柄。8.對(duì)于 C 語(yǔ)言do S while E語(yǔ)句 (1)改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯； (2)寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。9.已知文法G(S) SaAcBe AAb| b Bd(1)給出句子abbcde的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)；(2)給出句型aAbcde的短語(yǔ)、素短語(yǔ)。 10.設(shè)文法G(S): S(T) | aS | a TT,S | S 消除左遞歸和提公共左因子； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測(cè)分析表。解 10.(1) S (L) | aS SS | LSL

25、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.把語(yǔ)句 if X0 Y0 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的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)； (2) 給出句型 (E+T)*i+

26、F 的短語(yǔ)，素短語(yǔ)和最左素短語(yǔ)。 解 (1)消除左遞，文法變?yōu)镚S：S | a | (T)TST | ST,ST |此文法無(wú)左公共左因子。(2)構(gòu)造相應(yīng)的FIRST和FOLLOW集合： FIRST(S)=a, , (， FOLLOW(S)=#, , )FIRST(T)=a, , ( ，F(xiàn)OLLOW(T)=FIRST(T)=, ，F(xiàn)OLLOW(F)=)(3)構(gòu)造預(yù)測(cè)分析表：a(),#SSaSS(T)TTSTTSTTSTTTT,ST2. (1)Cif E thenSCS(1) (2) Cif E then BACK(E.TC, NXQ); C.chain:=E.FC SCS(1) S.chain:

27、=MERG(C.Chain, S(1). Chain)4. (1) 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(+,

28、F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain5. (1) (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. 最左推導(dǎo)S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T

29、,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)短語(yǔ) (T,S),a) (T,S),a (T,S) T,S a直接短語(yǔ) 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=AAbcBe=abbcBe=abbcde(2) 短語(yǔ): aAbcde, Ab, d 素短語(yǔ): Ab, d

30、11.(1) (j, X, 0, (5)(2) (j, _, _, (3)(3) (j0, 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=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T =(i+i)*i+F=(

31、i+i)*i+i (2) 短語(yǔ) i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短語(yǔ) i, E+T最左素短語(yǔ) E+T編譯原理期末試題（二）1、描述由正規(guī)式b*(abb*)*(a| e)定義的語(yǔ)言，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA。2、證明文法E E + id | id是SLR(1)文法。3、下面是表達(dá)式和賦值語(yǔ)句的文法，其中and的類(lèi)型是bool bool bool，+的類(lèi)型是int int int，=的類(lèi)型是int int bool，:= 要求id 和E的類(lèi)型都是int或者都是bool。為該文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義或翻譯方案，它完成類(lèi)型檢查。S id := EE E a

32、nd E | E + E | E = E |id4、對(duì)于下面C語(yǔ)言文件s.c f1(int x)long x;x = 1;f2(int x)long x;x = 1;某編譯器編譯時(shí)報(bào)錯(cuò)如下：s.c: In function f1:s.c:3: warning: declaration of x shadows a parameter請(qǐng)回答，對(duì)函數(shù)f2為什么沒(méi)有類(lèi)似的警告錯(cuò)誤。5、下面C語(yǔ)言程序經(jīng)非優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是area=12.566360, addr=-1073743076經(jīng)優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是area=12.566360, addr=-107374306

33、8請(qǐng)解釋為什么輸出結(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*定義的語(yǔ)言，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA。7、下面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0和1的串集：B B 0 | B 1 | 1下面的翻譯方案計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值：B B1 0B.val := B1.val 2 | B1 1B.val := B1.val 2 +1| 1 B.val := 1 請(qǐng)消除該基礎(chǔ)文法的左遞歸，再重寫(xiě)一個(gè)翻譯方案，它仍然計(jì)

34、算這種正二進(jìn)制數(shù)的十進(jìn)制值。8、在C語(yǔ)言中，如果變量i和j都是long類(lèi)型，請(qǐng)寫(xiě)出表達(dá)式&i和表達(dá)式&i-&j的類(lèi)型表達(dá)式。為幫助你回答問(wèn)題，下面給出一個(gè)程序作為提示，它運(yùn)行時(shí)輸出1。main() long i, j;printf(“%dn”, &i-&j);9、一個(gè)C語(yǔ)言的函數(shù)如下：func(i) long i; long j;j = i 1;func(j);下面左右兩邊的匯編代碼是兩個(gè)不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用func之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對(duì)參數(shù)傳遞的處理方式?jīng)]有實(shí)質(zhì)區(qū)別。請(qǐng)敘述右邊代碼對(duì)參數(shù)傳遞的處理方式并推測(cè)它帶來(lái)的優(yōu)點(diǎn)。func:

35、|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)movl-4(%ebp), %eax|movl-4(%ebp), %eaxpushl%eax|movl%eax, (%esp)callfunc|callfuncaddl$4, %esp|leaveleave|retret|start1abb21、由正規(guī)式b*(ab

36、b*)*(a| e)定義的語(yǔ)言是字母表a, b上不含子串a(chǎn)a的所有串的集合。最簡(jiǎn)DFA如下：2、先給出接受該文法活前綴的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4idI0和I3都只有移進(jìn)項(xiàng)目，肯定不會(huì)引起沖突；I2和I4都無(wú)移進(jìn)項(xiàng)目并僅含一個(gè)歸約項(xiàng)目，也肯定不會(huì)引起沖突；在I1中，E的后繼符號(hào)只有$，同第2個(gè)項(xiàng)目的展望符號(hào)“+”不一樣，因此I1也肯定不會(huì)引起沖突。由此可以斷定該文法是SLR(1)的。3、語(yǔ)法制導(dǎo)定義如下。S id := E S.type := if (id.type = bool and E.

37、type = bool) or (id.type = int and 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 the

38、n bool else type_error E id E.type := lookup(id.entry) 4、對(duì)于函數(shù)f1，局部變量x聲明的作用域是整個(gè)函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問(wèn)形式參數(shù)x。由于這是一個(gè)合法的C語(yǔ)言函數(shù)，因此編譯器給出警告錯(cuò)誤。對(duì)于函數(shù)f2，由于局部變量x的作用域只是函數(shù)體的一部分，不會(huì)出現(xiàn)上述問(wèn)題，因而編譯器不報(bào)錯(cuò)。5、使用非優(yōu)化編譯時(shí)，變量s, pi, r在局部數(shù)據(jù)區(qū)都分配4個(gè)字節(jié)的空間。使用優(yōu)化編譯時(shí)，由于復(fù)寫(xiě)傳播，pi*r*r 變成3.14159*r*r，pi=3.14159成為無(wú)用賦值而刪去，函數(shù)中不再有pi的引用，因此不必為pi分配空間。類(lèi)似地，s=3.1

39、4159*r*r也是一個(gè)無(wú)用賦值（表達(dá)式要計(jì)算，但賦值是無(wú)用的），也不必為s分配空間。這樣，和非優(yōu)化情況相比，局部數(shù)據(jù)區(qū)少了8個(gè)字節(jié)， 因此r的地址向高地址方向移動(dòng)了8個(gè)字節(jié)。6、正規(guī)式b*a(bb*a) *b*體現(xiàn)的特點(diǎn)是，每個(gè)a的左邊都有若干b，除非a是第一個(gè)字母。該正規(guī)式定義的語(yǔ)言是：至少含一個(gè)a，但不含子串a(chǎn)a的所有a和b的串集。最簡(jiǎn)DFA如下：start2abb10ab7、消除左遞歸后的文法：B 1 BB 0 B | 1 B | e相應(yīng)的翻譯方案如下：B 1 B.i := 1 BB.val := B.valB 0 B1.i := B.i 2 B1 B.val := B1.val| 1

40、 B1.i := B.i 2 +1 B1 B.val := B1.val| e B.val := B.i8、表達(dá)式&i的類(lèi)型表達(dá)式是pointer(long)，表達(dá)式&i-&j的類(lèi)型表達(dá)式是long。按照C語(yǔ)言的規(guī)定，指向同一個(gè)類(lèi)型的兩個(gè)指針可以相加減，它們值的差是它們之間的元素個(gè)數(shù)。9、左邊的編譯器版本：一般只為局部變量分配空間。調(diào)用函數(shù)前，用若干次pushl指令將參數(shù)壓棧，返回后用addl $n, %esp一次將所有參數(shù)退棧（常數(shù)n根據(jù)調(diào)用前做了多少次pushl來(lái)決定）。右邊的編譯器版本：除了為局部變量分配空間外，同時(shí)還為本函數(shù)中出現(xiàn)的函數(shù)調(diào)用的參數(shù)分配空間，并且參數(shù)所用空間靠近棧頂。調(diào)用

41、函數(shù)前，用movl指令將參數(shù)移入棧頂，調(diào)用結(jié)束后無(wú)需參數(shù)退棧指令。優(yōu)點(diǎn)是每次函數(shù)調(diào)用結(jié)束后不需要執(zhí)行addl $n, %esp指令，另外增加優(yōu)化的可能性。編譯原理期末試題（三）1、 從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類(lèi)？對(duì)循環(huán)的優(yōu)化可以有哪三種？ 答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部?jī)?yōu)化和全局優(yōu)化兩類(lèi)；對(duì)循環(huán)的優(yōu)化有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計(jì)算強(qiáng)度削減。2、寫(xiě)出表達(dá)式a=b*c+b*d對(duì)應(yīng)的逆波蘭式、四元式序列和三元式序列。 答：逆波蘭式： abc*bd*+:= 四元式序列：三元式序列: OP ARG1 ARG2(1) (*， b， c， t1) (1) (* b， c )(2) (*， b， d， t2) (2) (* b， d )(3) (+， t1， t2，t3) (3) (+ (1)， (2)(4) (:=， t3， /， a)(4) (:= (3)， a)3、對(duì)于文法G(S): SbM(TMabL)答：1） 2） 短語(yǔ): Ma)， (Ma