編譯原理期末試題

1、編譯原理期末試題（-）、是非題（請在括號內(nèi)，正確的劃V,錯誤的劃X）（每個2分，共20分）1編譯程序是對高級語言程序的解釋執(zhí)行。（X2 . 一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 （X）3 . 一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。（V）4 .語法分析時必須先消除文法中的左遞歸。（X）5 . LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔ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）二、選擇題（請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論）（每個4分，共40分）1 .詞法分析器的輸出結(jié)果是 oA.（）單詞的種別編碼B.（）單詞在符號表中的位置C.（）單詞的種別編碼和自身值D.（）單詞自身值2 .正規(guī)式M 1和M2等價是指B. （）M1和M2的有向邊條數(shù)相等D. （）M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等A. （）M1和M2的狀態(tài)數(shù)相等C. （）M1和M2所識別的語言集相等3.文法G: STxSx|y所識別的語言是A. () xyxB.()(xyx)* C. () xny

3、xn(n > 0) D. () x*yx*4 .如果文法G是無二義的，則它的任何句子 aA.()最左推導(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)掌握 oA.()源程序B.()目標(biāo)語言C.()編譯方法D.()以上三項都是6 .四元式之間的聯(lián)系是通過 實現(xiàn)的。A.()指示器B .()臨時變量C .()符號表 D.()程序變量7 . 表達(dá)式(B)A(CVD)的逆波蘭表示為。A. () ABACD VB.() A FBCD VAC. () ABV

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

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

6、aTTSTTT ,st , |£提取公共左因子：ST (T) | aS ' ST +S | &TTSVT,T,ST, I3 .試為表達(dá)式w+(a+b)*(c+d/(e-10)+8)寫出相應(yīng)的逆波蘭表示。解：wab + cde10-/ + 8 + * +4 .按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while (A<C A B<D) if (A> 1) C=C+1;else while (A < D)A=A+2;) O解：該語句的四元式序列如下 (其中E1、E2和E3分別對應(yīng)AVCABVD、A1和AD ,并且關(guān)系運算符優(yōu)先級高)：1

7、00 (j<,A,C,102)101 (j,_,_,113)102 0<,B,D,1O4)103 (j,_,_,113)104 (j=,A,1,106)105 (j,_,_,108)106 (+, C, 1, C)107 (j,_,_,112)108 (j w,A,D,110)109 (j,_,_,112)110 (+, A, 2, A)111 (j_,108)112 (j,_,_,100)1135 .已知文法G司為STaSb|Sb|b,試證明文法GS為二義文法。證明:由文法GS: STaSb|Sb|b,對句子aabbbb對應(yīng)的兩棵語法樹為:b因此，文法 GS為一義文法。五計算題(

8、i。分)已知文法ab#給出分析過程。A->aAd|aAb| &判斷該文法是否是SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串解：增加一個非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有:S,->AA- >aAd|aAb| &下面構(gòu)造它的LR(O)項目集規(guī)范abPdSA3.金丑1:1A乍礦處也兮血li：IllaccI=: ATaAd Ab胡bI：L= A->aA-d A->aJl'bI,：I A->aAB,A->aJLdI；MS Is；血從上表可看出，狀態(tài)10和12存在移進(jìn)歸約沖突，該文法不是LR(0)文法。對于10來說有：FOLLOW(

9、A)Q a=b,d,# na=,v!所以在I0狀態(tài)下面臨輸入符號為a時移進(jìn)，為b,d,#時歸約，為其他時報錯。對于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移進(jìn) 歸約沖突是可以解決的，因此該 文 法 是S L R (1) 文 法。其 SLR(1) 分 析 表 為ACTIOHCOWabd$A0鬲rir；11ACC2rir?Ti33S.弘4空r5X1XLXiT±對輸入串a(chǎn)b#給出分析過程為:先哪播入由ACTIOMGOTO1Ts；202bitXi53029b#S40234ftaAb¥1&01acc編譯原理期末試題（二）、是非題：1 .一個上下文無關(guān)文法的開始符，

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

11、 .每個基本塊只有一個入口和一個出口。16 .一個LL （1）文法一定是無二義的。17 .逆波蘭法表示的表達(dá)試亦稱前綴式。18 .目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。19 .正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。20 . 一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。()()()()()08.X9. V10.X21.3型文法一定是2型文法。舲如梟分直法存在某妒質(zhì)制應(yīng)兩棵花同的詩詼樹， 答案：1.X2.X3.X4. V5. V6.X7.X、填空題：2 .編譯過程可分為（詞法分析），（語法分析），代碼生成）五個階段。3 .如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹,（）1則禍為

12、ZK性的。11.X（語義分析與中間代碼生成則稱這個文法是（4 .從功能上說，程序語言的語句大體可分為（執(zhí)行性）語句和（說明性5 .語法分析器的輸入是（單詞符號），其輸出是（語法單位）OX21. V22. V）,（優(yōu)化）和（目標(biāo)二義性的）語旬兩大°類。曳捋推贊的的債懸極華登i源蹣簾名字的有珈鯽剜胤 姐個（樊型符神屬、所拈單元大小、地址）等等。8. 一個過程相應(yīng)的DISPLA Y表的內(nèi)容為（現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址10.常用的兩種動態(tài)存貯分配辦法是（棧式）動態(tài)分配和（堆式）動態(tài)分配。11 .一個名字的屬性包括（類型）和（作用域12 .常用的參數(shù)傳遞方式有（傳地址），（

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

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

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

16、有a A3且A s則稱3是句型a3§相對非終結(jié)符A的短語。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é)符，并且，除它自身外不再

17、含任何更小的素短語。19 .語法是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。_20 .待用信息如果在一個基本塊中，四元式 i對A定值，四元式j(luò)要引用A值，而從i到j(luò)有A的其它定值，則稱j是四元式i的變量A的待用信息。21 .語義定義程序的意義的一組規(guī)則。四、簡答題：1 .寫一個文法G,使其語言為不以0開頭的偶數(shù)集。及相應(yīng)翻譯方案a 1 ”2" 3" 4" 2 .已知文法G (S)ST aAb pri ntST a printAT AS pri ntAT c pri nt輸入acab,輸出是什么？3 .已知文法G （S）ST bAaAT (B I aBT Aa)寫出句

18、子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.A,B的值是什么？試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出5 .文法G(S)ST dABZ aA| aBT Bb| £描述的語言是什么？6 .證明文法G(S)STSaS| e是二義性的。7 .已知文法G(S)ST BAAT BS| dBT aA| bS | c的預(yù)測分析表如下abcd#SST BAST BAST BAAAT BSAT BSA

19、T BSArdBBT aABT bSBTC給出句子adccd的分析過程。8 .寫一個文法 G,使其語言為 L(G)=a Lmdanpi |>=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.)一.>.>V.V.>.>請計算出該優(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為首的字組成的正規(guī)集相對應(yīng)的正

20、規(guī)式。13 .基本的優(yōu)化方法有哪幾種？14 .寫一個文法G,使其語言為L(G)=ab ncn| n> 015 .考慮下面的程序：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 .寫出表達(dá)式a+b*(c-d)/e的逆波蘭式和三元序列。17 .證明文法G(A)AT AA | (A)|£是二義性的。18 .令=a,b,則正規(guī)式a-b|b表示的正規(guī)集是什么？19響謂DISPLAY表？其作用

21、是什么？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|n>0為奇數(shù)，m>0為偶數(shù)22 .寫出表達(dá)式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。23 . 一個文法G別是LL(1)文法的充要條件是什么？24 .已知文法GSStS*aF | aF| *aFFt +aF | +a消除文法左遞歸和提公共左

22、因子。25 .符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？答案：1.所求文法是GS: StAB |B AOAtAD |CBt2 |4 |6 |8Ct1 |3 |5 |7 |9 |BDtO |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, B=4 _n m5 . L(G)=da b |n>0, m

23、 >06 .證明：因為文法GS存在句子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#AAdeed#4#Addeed#ATd5#Accd#6#SBccd#AT BS7#Scccd#BTC8#Scd#9#ABcd#BTC10#Acd#11#Ad#12#dd#ATd13#8 .所求文法是G

24、S:STABA T aAc | DDT bD | b BT aBb | aabb函數(shù)a()9f4244g55239.10.優(yōu)化:對程序進(jìn)行各種等價變換，使得從變換后的程序出發(fā),能產(chǎn)生更有效的目標(biāo)代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化11 .目標(biāo)代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。應(yīng)著重考慮的問題：如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點。12 .正規(guī)式 a ( a | b )*。13 .刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播和刪除無用賦值。14 文法 GS:ST a

25、B | aB T be |bBc15 .傳值a=2傳地址a=1516 .逆波蘭式:abcd-*e/+三元序列：op arg1 arg2-cd(2) *b(1)(3) / (2)e+a(3)17 .證明：因為文法GS存在句子()有兩個不同的最左推導(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)一個過程運行時必須跟蹤它的所有外層 過程

26、的最新活動記錄起始地址，display表就是用于登記每個外層過程的最新活動記錄起始地址。20 .傳地址a=12傳值a=521 .所求文法是GS:ST ACAT aaAbb | abCT ccC | cc22 .逆波蘭式 abc+e*bc+f/+:=三元序列op arg1 arg2|7 J/ )/ XJ/ 12 3 4 /( /( /( /)(3+ - J/ )/ 5 6 /( /(!/ !/ 4 5 /| /(23 . 一個文法G別是LL(1)文法的充要條件是：(1) FIRST(5)AFIRST®)=©(2) 如果 3 二:s , FIRST( a ) A FOLLOW(

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

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

29、 a:=a+1else a:=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)STa|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 aAcBeAtAb|bBtd(1)給出句子abbcd

30、e的最左推導(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的短語，素短語和最左素短語。13 .設(shè)文法G(S)：St

31、T|S VTTT u |T 人 UUti |-U (1)計算 FIRSTVT 和 LASTVT；(2)構(gòu)造優(yōu)先關(guān)系表。答案：(力消除左遞，文法變?yōu)镚網(wǎng)：STA|a|(T)'ST |STT,ST 相此文法無左公共左因子。(2)構(gòu)造相應(yīng)的 FIRST 和 FOLLOWI 合:FIRST(S)=a, A, ( , FOLLOW(S)=#, ) FIRST(T)=a, A, (, FOLLOW(T)=FIRST(T )= £, FOLLOW(F)=)構(gòu)造預(yù)測分析表：aA()5#sSTaST人ST (T)'TTT ST,TTSTTTSTT,T'T£TT ,ST

32、 '2. (1)CT if EthenST CS12(2)CT if E then BACK(E.TC, NXQ); C.chain:=E.FC STCS° S.chain:=MERG(C.Chain, S (D.Chain)3. (1) FIRSTVT(S)=a, ( FIRSTVT(T)=+, a a, () LASTVT(S)=a,)LASTVT(T)=+, a,)(2)a+()a.>.>+V.>V.>(V.V.V.).>.>>.I1(2)4. (1) F T for i:=E to E do ST FS2 FT fori:=E

33、 (1) to E (2) doGEN(:=, E (1) .place, entry(i); F.place:=e ntry(i); LIMIT:=Newtemp;GEN(:=, E (2).place,_, LIMIT); Q:=NXQ;F.QUAD:=q;GEN(j< , entry(i), LIMIT, q+2) F.chai n:=NXQ;GEN(j, 0) ST FSBACKPATCH(S .chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, F.QUAD); S.chai n:=F.chain)5. (1)(j<,a/10

34、, ,(3)(2) (j, , _ ,(12)(3) (j>, c. 'O', (5)(4) (j, , _ ,(8) (+, a,Ti)(：=,Ti, a) (j_(i) (*. a,'i3T2)(-,T2,'iT3)(:=,T3, a)5)!/ )/ 6 7 /1J/ )/ 8 9 fvio(11) 0_(i)6 .優(yōu)化后的四元序列 D:=A-C E:=A*C F:=D*E M:=F+207 .最左推導(dǎo)S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T)=>(a,(T,S)=>(a,(S,S)=>

35、;(a,(a,S)=>(a,(a, a) 短語 (T,S),a) (T,S),a (T,S) T,S a 直接短語 T,S a 句柄 T,S8 . (1)ST do Mi Si while M 2EMA£M.quad=nestquad;i.nextlist, M 2.quad).quad);')=a, (, s')=， sStdo Mi Si while M 2E backpatch(s backpatch(E.truelist, MS.nextlist=E.falelist;9.(i) S=>aAcBe=>AAbcBe=>abbcBe=>

36、;abbcde(2)短語：aAbcde, Ab, d素短語：Ab, diO.(i) ST (L) | aS 'L S'TS|sTSL'(2) L'T ,SL ' | sFIRST(S)=a, ( FIRST(SFIRST(L)=a, ( FIRST(LFOLLOW(S)= ), # FOLLOW(S ')= ), #FOLLOW(L)=) FOLLOW(L ')=)()aJ#sST(L)ST aS'S'SSTS'T&ss:STgS*T&LLTSL'LTSL'L SL 'L&#

37、39;L11. (1)(j>,X, 0, (5)。)(3) (j<, Y, 0, (5)(j，、)(5) (j>0, X, 0,(7)；(6) (j, , , (7)(7) (*,A,3,Ti)(8) (：=,Ti,_, N)(10) L，(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+

38、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, A,i,-FIRSTVT(T)= A, i, -FIRSTVT(U)=i, -LASTVT(S)=V , A,i,-LASTVT(T)=A, i, -LASTVT(U)=i, -(2)IVAS.>.>VV.>V.V.AV.>.>V.一V.>.>V.編譯原理期末試題(二)1、描述由正規(guī)式b*(abb

39、*)*(a|)定義的語言，并畫出接受該語言的最簡 DFAo2、證明文法E E + id | id是SLR(1)文法。3、下面是表達(dá)式和賦值語句的文法，其中 and的類型是bool bool bool , +的類型是int int int ,=的類型是int int bool ,要求id和E的類型都是int或者都是bool o為 該文法寫一個語法制導(dǎo)定義或翻譯方案，它完成類型檢查。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；)某編譯器編譯時報錯如

40、下：s.c: In function 4f1 ':s.c:3: warning: declaration of 'x ' shadows a parameter 請回答，對函數(shù)f2為什么沒有類似的警告錯誤。5、下面C語言程序經(jīng)非優(yōu)化編譯后，若運行時輸入2,則結(jié)果是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(H%r, &r); printf(&

41、quot;area=%f, addr=%dn", s=pi*r*r, &r);)6、描述由正規(guī)式ba(bba)b定義的語言，并畫出接受該語言的最簡DFAo7、下面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0和1的串集：B B0|B1 | 1下面的翻譯方案計算這種正二進(jìn)制數(shù)的十進(jìn)制值：B Bi 0 B. val := B i.val 2 | Bi 1 B. val := Bi.val 2 +1| 1 B. val := 1 請消除該基礎(chǔ)文法的左遞歸，再重寫一個翻譯方案，它仍然計算這種正二進(jìn)制數(shù)的十進(jìn)制值。8、在C語言中，如果變量i和j都是long類型，請寫出表達(dá)式&和表達(dá)式&

42、&j的類型表達(dá)式。為幫助你回答問題，下面給出一個程序作為提示，它運行時輸出1omai n() long i, j;printf( %dn " &i &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)]有 實質(zhì)區(qū)別。右邊代碼對參數(shù)傳遞的處理方式并推測它帶來的優(yōu)點。pushl movl%ebp%esp,%ebpsubl$4,%espm

43、ovl8(%ebp),%edxdeci%edxmovl%edx,-4(%ebp)movl-4(%ebp), %eax |pushl%eaxcallfuncaddl$4,%espleaveretfunc:pushl%ebpmovl%esp, %ebpsubl$8, %espmovl8(%ebp), %eaxdeci%eaxmovl%eax, -4(%ebp)movl-4(%ebp), %eaxmovl%eax, (%esp)callfuncleave ret編譯原理試卷八答案1、由正規(guī)式b*(abb*)*(a|)定義的語言是字母表a,b上不含子串a(chǎn)a的所有串的集合。最簡DFA如下：2、先給出接受

44、該文法活前綴的 DFA如下:I。和13都只有移進(jìn)項目，肯定不會引起沖突；I2和|4都無移進(jìn)項目并僅含一個歸約項目，也肯 定不會引起沖突；在li中，E的后繼符號只有$,同第2個項目的展望符號“ +”不一樣，因此li也肯定不會引起沖突。由此可以斷定該文法是SLR的。3、語法制導(dǎo)定義如下。S id := E S.type := if (id .type = bool and E.type = bool) or (id .type = intand E.type = int) then type_ok else type errorE E1 and E2 E.type := if El.type =

45、bool and E2.type =bool then bool elsetype_errorEE1+ E2E.type:=if El.type =int andE2.type =int the n int else type_errorEE1=E2E.type:=if El.type =int andE2.type =int the n bool else type_errorEidE.type：=|ookup(id.entry)4、對于函數(shù)f1 ,局部變量x聲明的作用域是整個函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問形式 參數(shù)X。由于這是一個合法的C語言函數(shù)，因此編譯器給出警告錯誤。對于函數(shù)f2,由

46、于局部變量x的作用域只是函數(shù)體的一部分，不會出現(xiàn)上述問題，因而編譯器不報錯。5、使用非優(yōu)化編譯時，變量s, pi, r在局部數(shù)據(jù)區(qū)都分配4個字節(jié)的空間。使用優(yōu)化編譯時， 由于復(fù)寫傳播，pi*r*r變成3.14159*r*r, pi=3.14159成為無用賦值而刪去，函數(shù)中不再有 pi的引用，因此不必為pi分配空間。類似地，s=3.14159*r*r也是一個無用賦值(表達(dá)式要 計算，但 賦值是無用的)，也不必為s分配空間。這樣，和非優(yōu)化情況相比，局部數(shù)據(jù)區(qū)少了 8個字節(jié)，因此r的地址向高地址方向移動了8個字節(jié)。6、正規(guī)式ba(bba)b體現(xiàn)的特點是，每個a的左邊都有若干b,除非a是第一個字母。該

47、 正規(guī)式定 義的語言是：至少含一個a,但不含子串a(chǎn)a的所有a和b的串集。最簡DFA如下：7、消除左遞歸后的文法:相應(yīng)的翻譯方案如下:B1B J := 1 BB. val := B .valB0B 1.i := B .i2 B 1 B .val := B 1 .val|1B 1.i := B .i2 +1 B 1 B .val := B 1 .val|B .val := B .i8、表達(dá)式&i的類型表達(dá)式是pointer(long),表達(dá)式&i &j的類型表達(dá)式是long。按照C語言的 規(guī)定，指向同一個類型的兩個指針可以相加減，它們值的差是它們之間的元素個數(shù)。9、左邊的編

48、譯器版本：一般只為局部變量分配空間。調(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)化的可能性。編譯原理期末試題(三)1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對循環(huán)的優(yōu)化可以有哪三種？答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局

49、優(yōu)化兩類；對循環(huán)的優(yōu)化 有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計算強度削減2、寫出表達(dá)式a=b*c+b*d對應(yīng)的逆波蘭式、四元式序列和三元式序列答：逆波蘭式：abc*bd*+:=四元式序列：2)短語:二亓式序列：OP ARG1 ARG2 b(Ma)b直接短語：Ma)句柄：Ma)對于文法bMbG(S)bMbb(Lb b(Ma)b設(shè)有字母表a, b)上的正規(guī)式R=(ab|a)解：(2)將(1)所得的非確定有限自動機確定化£ab-01131221+3-+©2 ) +ba(3)對(2)得到的DFA化簡，合并狀態(tài)。和2為狀態(tài)2:(4)令狀態(tài)1和2分別對應(yīng)非終結(jié)符B和AG: A a

50、B|a|£； B aB|bA|a|b| 可化簡為：G: AaB|£； B aB|bA| &四、設(shè)將文法G改寫成等價的LL(1)文法，并構(gòu)造預(yù)測分析表。G: S S*aT|aT|*aT ； T +aT|+a解：消除左遞歸后的文法G':S- aTS faTS JS' *aTS 1 | &T +aT|+a提取左公因子得文法G'':SaTS ' *aTS 'S' *aTS ” &T+aT 'T - T| &Select(S aTS')=aSelect(S *aTS ' )=*Select(S aTS') n Select(S *aTS =©Select(S ' *aTS ' )=*Select(S '滬 Follow(s ' )=#Select(S ' *aTS ' n Select(S '滬 Select(T +a)=+Select(T , T)=First(T)