1、編譯原理期末試題(一)二、選擇題 (請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論 )(每個(gè) 4分，共 40 分)5構(gòu)造編譯程序應(yīng)掌握1詞法分析器的輸出結(jié)果是A( )源程序B ( ) 目標(biāo)語言A( ) 單詞的種別編碼BC ( ) 編譯方法D ( ) 以上三項(xiàng)都是詞在符號(hào)表中的位置6四元式之間的聯(lián)系是通過實(shí)現(xiàn)的。C( ) 單詞的種別編碼和自身值D詞自身值A(chǔ) ( ) 指示器B( ) 臨時(shí)變量2 正規(guī)式 M 1 和 M 2 等價(jià)是指A ( ) M1 和 M2 的狀態(tài)數(shù)相等B( )M1 和 M2 的有向邊條數(shù)相等C ( ) M1 和 M2 所識(shí)別的語言集相等D( )M1 和 M2 狀態(tài)數(shù)和有

2、向邊條數(shù)相等3. 文法G : StxSx|y所識(shí)別的語言是A ( ) xyxB ( ) (xyx)*C. ( ) xnyxn(n 0D. ( ) x*yx*4.如果文法G是無二義的，則它的任何句子。_A( ) 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同B( ) 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同C( ) 最左推導(dǎo)和最右推導(dǎo)必定相同D( ) 可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同C( ) 符號(hào)表D( ) 程序變量7.表達(dá)式(A B) A (C V D)的逆波蘭表示為A. ( ) AVBA CDVVAC ( ) AB V CD VA8. 優(yōu)化可生成B( ) A VBCDD的目標(biāo)代碼。A

3、 ( ) 運(yùn)行時(shí)間較短用存儲(chǔ)空間較小( ) A VBA CDVB( ) 占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 ( ) 代碼外提第3頁共 6 頁10編譯程序使用區(qū)別標(biāo)識(shí)符的作用域。四、簡(jiǎn)答題( 20分)A. ( ) 說明標(biāo)識(shí)符的過程或函數(shù)名2. 考慮文法 GS:B( ) 說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次C( ) 說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次S 7 (T) I a+S | aD. ( ) 標(biāo)識(shí)符的行號(hào)T 7 T,S I S三、填空題 (每空 1

4、 分，共 10 分)消除文法的左遞歸及提取公共左因子。1計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要有兩種途徑： _解釋_和_編譯 _。2.掃描器是 _詞法分析器 _，它接受輸入的 _源解：消除文法 GS 的左遞歸：S7(T) I a+S I aT7 st,ST |提取公共左因子：程序 _，對(duì)源程序進(jìn)行 _詞法分析并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。S7(T) I aS S7 +S I T7STT7 ,STI 3自上而下分析法采用移進(jìn)歸約、錯(cuò)誤處理、接受_等四種操作。3. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)的逆波蘭表示。4一個(gè) LR 分析器包括

5、兩部分：一個(gè)總控程序和解： w a b + c d e 10 - / + 8 + * +張分析表 _。4. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯5.后綴式abc-/所代表的表達(dá)式是a/(b-c)_。成四元式序列：6局部?jī)?yōu)化是在 _基本塊 _范圍內(nèi)進(jìn)行的一種優(yōu)while (AC A B 1) C=C+1;else while (AA=A+2;。第9頁共6頁解：該語句的四元式序列如下(其中E1、E2和E3分別對(duì)應(yīng)A C A B D、A1和AD ,并且關(guān)系運(yùn)算符優(yōu)先級(jí)高)：100 (j,A,C,102)101 (j,亠113)102 (jaAd|aAb| eab#給出分析過程。判斷該文法是否是

6、SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串解：增加一個(gè)非終結(jié)符 S/后，產(chǎn)生原文法的增廣文法有:S-AA- aAd|aAb| e下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為:sbaAh=A-aAdAfaAbJIT，LtA-a.*Ad AT a述 A-aAd A今加AT11：hi ST般I.： 血T皆陽ATThrI：L： ATaA 記 ATaA 嗆b!止今叢記I !1=!ATaA 出I : ATaAb*I.=從上表可看出,狀態(tài)10和12存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對(duì)于10來說有： FOLLOW(A)Q a=b,d,# n a= 所以在I0狀態(tài)下面臨輸入符號(hào)為 a時(shí)移進(jìn)，為b,d,

7、#時(shí)歸約，為其他時(shí) 報(bào)錯(cuò)。對(duì)于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移進(jìn)-歸約沖突是可以解決的，因此該文法是 SLR（1）文法。其SLR（1）分析表為：ACTI0Habd0SiTiIs11acc2工1口133334口巴5X1IIri11對(duì)輸入串a(chǎn)b#合出分析過程為:步驟符號(hào)棧輸入串ACTLOMGOTO10#ab#202b#rj33023iaAb#S40234#aAb1501acc編譯原理期末試題（二）二、填空題：2. 編譯過程可分為（詞法分析），（語法分析），（語義分析與中間代碼生成），（優(yōu)化）和（目標(biāo)代碼生成）五個(gè)階段。3. 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這

8、個(gè)文法是（4. 從功能上說，程序語言的語句大體可分為（執(zhí)行性 ）語句和5. 語法分析器的輸入是（ 單詞符號(hào)），其輸出是（語法單位6. 掃描器的任務(wù)是從（ 源程序中）中識(shí)別出一個(gè)個(gè)（單詞符號(hào)7. 符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如二義性的）。（說明性）語句兩大類。）。）。（類型、種屬、所占單元大小、地址）等等。 ）8. 一個(gè)過程相應(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è)名字的屬性包括（類型）和（作用域12. 常用的參數(shù)傳遞方式有（傳地址），（傳值），13. 根據(jù)優(yōu)化

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

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

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

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

13、形成和產(chǎn)生一個(gè)合式的程序。_20. 待用信息-如果在一個(gè)基本塊中，四元式 i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)有A的其它定值，則稱j是四元式i的變量A的待用信息。21. 語義-定義程序的意義的一組規(guī)則。四、簡(jiǎn)答題：1. 寫一個(gè)文法G,使其語言為 不以0開頭的偶數(shù)集。2. 已知文法G（S）及相應(yīng)翻譯方案“ 1” “ 2”“3”“ 4”St aAb printSt aprintAt as printAt cprint=之間沒叫做語之間沒輸入acab,輸出是什么？3. 已知文法G(S)St bAaAt (B | aBt Aa)寫出句子b(aa)b的規(guī)范歸約過程。4. 考慮下面的程序：p roc

14、edurep(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ù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出5. 文法G(S)St dABAt aA| aBt Bb| 描述的語言是什么？6. 證明文法G(S)St SaS| 是二義性的。7. 已知文法G(S)St baAt BS| dBt aA| bS | c的預(yù)測(cè)分析表如下abcd#sSt baSt baSt baAAt BSAt BSAt BSATdBBt aABt bSBtc給出句子adccd的分析過程。

15、8. 寫一個(gè)文法 G,使其語言為 L(G)=a lbmclanbn| 1=0, m=1, n=29. 已知文法G(S):St a| (T)Tt T,S|S的優(yōu)先關(guān)系表如下：關(guān)系a()Ja-.(.=.J.請(qǐng)計(jì)算出該優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)表。10.11.12.13.14.15.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？一字母表2 =a, b，試寫出 2上所有以a為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。 基本的優(yōu)化方法有哪幾種？寫一個(gè)文法G,使其語言為L(zhǎng)(G)=ab ncn| n 0考慮下面的程序：第13頁共6頁a 的值是什么 ?a 的值

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

17、gin a:=5; b:=2; p(a+b, a-b, a); print aend. 試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出21. 寫一個(gè)文法 G, 使其語言為 L(G)=a nbncm| n0 為奇數(shù)， m0 為偶數(shù) 22. 寫出表達(dá)式 a:=(b+c)*e+(b+c)/f 的逆波蘭式和三元序列。23. 一個(gè)文法 G 別是 LL(1) 文法的充要條件是什么？24. 已知文法 GSSt S*aF | aF | *aF Ft +aF | +a 消除文法左遞歸和提公共左因子。25. 符號(hào)表的作用是什么？符號(hào)表查找和整理技術(shù)有哪幾種？ 答案： 1. 所求文法是 GS:StAB

18、 |B A0 AtAD |C Bt2 |4 |6 |8 Ct1 |3 |5 |7 |9 |B Dt0 |C2. 輸出是 42313. 句子 b(aa)b 的規(guī)范歸約過程：步驟符號(hào)棧輸入串動(dòng)作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=45. L(G)=da nbm | n0, m 06. 證明：因?yàn)槲姆℅S存在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。S=S

19、aS=SaSaS=aSaS=aaS=aaS=SaS=aS=aSaS=aaS=aa7. 句子adccd的分析過程：步驟符號(hào)棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#S7 BA2#AAaadccd#B7 aA3#AAdccd#4#Addccd#A7d5#Accd#6#SBccd#A7 bs7#Scccd#B7c8#Scd#9#ABcd#B7c10#Acd#11#Ad#12#dd#A7d13#8. 所求文法是GS:S 7 ABA 7 aAc | DD7bD|bB7 aBb I aabb 9.11. 目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。應(yīng)著重考慮的問題：(1)

20、如何使生成的目標(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 傳地址a=15arg1 arg2 d(1)eopcba16. 逆波蘭式：abcd-*e/+三元序列：(1)(2)(3)(4)17. 證明：因?yàn)槲姆℅S存在句子()有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。A=AA=(A)A=()A=()A=AA=A=(A)=()*

21、 *18. (a b|b a)=a,b,ab,ba,aab,bba19. Display 表：嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過程運(yùn)行時(shí)必須跟蹤它的所有外 層過程的最新活動(dòng)記錄起始地址，dis play 表就是用于登記每個(gè)外層過程的最新活動(dòng)記錄起始地址。20. 傳地址 a=12 傳值 a=521. 所求文法是GS:St ACAt aaAbb | abCT ceC | cc22. 逆波蘭式 abc+e*bc+f/+:=第17頁共6頁三元序列oparg1(1) +bc(2) *(1)e(3) +bc/(3)f(5) +(2)(6)：=aarg223. 一個(gè)

22、文法G別是LL(1)(1) FIRST(文法的充要條件是：a ) n FIRST )=(2) 如果 3= , FIRST( a ) n FOLLOW(A)*24. 消除左遞歸St aFS | *aFS St *aFS |Ft+aF | +a 提公共左因子，文法G (S)St aFS | *aFS St *aFS |Ft+aFFt F | 25. 作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進(jìn)展?fàn)顩r。 主要技術(shù)：線性表，對(duì)折查找，五、計(jì)算題：1.設(shè)文法G(S):St a | a | (T)Tt t,S | S消除左遞歸；雜奏技術(shù)。構(gòu)造相應(yīng)的 first和 構(gòu)造預(yù)測(cè)分析表(1)消除左

23、遞，文法變?yōu)镚St a | a | (T)Tt st | STt ,st | 此文法無左公共左因子。構(gòu)造相應(yīng)的 first和FOLLOW集合： FIRST(S)=a, a, (, FOLLOW(S)=#, , )FIRST(T)=a,人，(, FOLLOW(T)=FIRST(T )=, , FOLLOW(F)=)(3)構(gòu)造預(yù)測(cè)分析表：FOLLOW集合;S:aa()J#SSTaSt人St (T)tTt stTt stTt stTTtTt ,ST 2. 語句 if E then S(1) 改寫文法，使之適合語法制導(dǎo)翻譯;(2) 寫出改寫后產(chǎn)生式的語義動(dòng)作。3. 設(shè)文法G( S):St(T) | a

24、Tt T+S | S(1 )計(jì)算 FIRSTVT 和 LASTVT(2)構(gòu)造優(yōu)先關(guān)系表。4. 設(shè)某語言的for語句的形式為for i:= E1)to E do S其語義解釋為i:=白LIMIT:aga in: if i=E=limit thenBeginS;i: = i + 1goto again End;( 1 )寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；( 2)寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。5. 把語句 while a0 then a:=a+1 else a:=a*3-1;翻譯成四元式序列。6. 設(shè)有基本塊D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*QK:

25、=G*5L:=K+JM:=L假設(shè)基本塊出口時(shí)只有M還被引用，請(qǐng)寫出優(yōu)化后的四元序列。7. 已知文法 G(S)St a | A | (T)Tt T,S | S(1) 給出句子 (a,(a,a)的最左推導(dǎo)；(2) 給出句型 (T,S),a)的短語 , 直接短語，句柄。8. 對(duì)于 C 語言 do S while E 語句(1) 改寫文法，使之適合語法制導(dǎo)翻譯；(2) 寫出改寫后產(chǎn)生式的語義動(dòng)作。9. 已知文法 G(S)S t aAcBe A t Ab| b Btd(1) 給出句子 abbcde 的最左推導(dǎo)及畫出語法樹；(2) 給出句型aAbcde的短語、素短語。10. 設(shè)文法 G(S):St(T)

26、| aS | aTtT,S | S消除左遞歸和提公共左因子； 構(gòu)造相應(yīng)的 FIRST和FOLLOW!合；構(gòu)造預(yù)測(cè)分析表。11. 把語句if X0 V Y0 do X:=A*3else Y:=B+3;翻譯成四元式序列。12. 已知文法 G(S)E7E+T | TT 7T*F| FF7(E)| i(1) 給出句型 (i+i)*i+i 的最左推導(dǎo)及畫出語法樹；(2) 給出句型 (E+T)*i+F 的短語，素短語和最左素短語。13. 設(shè)文法 G(S)：S7 T|S VTT7 u |T 人 UU7i |-U( 1)計(jì)算 FIRSTVT 和 LASTVT；( 2)構(gòu)造優(yōu)先關(guān)系表。第19頁共 6 頁答案：(

27、6)(:=,T1, _, a)2. (1)(7)(j, _, _, (1)Ct if E then(8)(*, a, 13 , T2)St CS(1)(9)(-,T2,1 , T3)(2)(10)(:=,T3, _, a)Ct ifE thenBACK(E.TC, NXQ);(11)(j,亠，(1)C.chai n:=E.FCSt cS1S.chai n:=MERG(C.Cha in,S.Chain)3. (1) FIRSTVT(S)=a, ( FIRSTVT(T)=+, aLASTVT(S)=a, ) LASTVT(T)=+, a, )a，(a+()a+(.F tfor i:=E (1) t

28、o E doSt FS(1)Ft for i:=E(1) to E doGEN(:=, E1.place, _, entry(i); F.p lace:=e ntry(i);LIMIT:=Newte mp;GEN(:=, E .place, _, LIMIT);Q:=NXQ;F.QUAD:=q;GEN(j , entry(i), LIMIT, q+2) F.chai n:=NXQ;GEN(j, _, _, 0)St FS(1)BACKPATCH(S .chain, NXQ); GEN(+, F. place, 1, F.p lace); GEN(j,亠,F.QUAD);S.chai n:=F.

29、chai n5.(1) (j, c,0 , (5)(j, _, _, (8)(+, a, 1 , T1)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,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)St do M1 S1 while M 2 E(2)MtM.quad=nestquad;S t do MSiback patch(s i.n extlist, Mback patch

30、(E.truelist, Mwhile M E2.quad);i.quad);S.n extlist=E.falelist;9. (1) S=aAcBe=AAbcBe=abbcBe=abbcde(2)短語：aAbcde, Ab, d 素短語：Ab, d10. (1) St (L) I aS St s I &Lt SLLt ,SL (2)FIRST(S )=a,(,FIRST(L)=a,I &FIRST(S)=a,(第23頁共6頁FIRST(L )=, 門FOLLOW(S)=,FOLLOW(S )=, ), #FOLLOW(L)=FOLLOW )= )(3),#)FIRSTVT(U)=i, -L

31、ASTVT(S)=V ,A , i, - LASTVT(T)=A , i, -LASTVT(U)=i, -()a5#SS(L)SfaSSSSS fSfSS fSfLLfSLLfSLL f ,SLLL fiVAS.V.A.-., X, 0, (5)(j, _, _, (3) (j0, X, 0, (7) (j, _, _, (7) (*, A, 3, T (:=,T (j, _, _, (j, _, _, (+, B, 3, (:=,T1)1, _, N)(5) (13)T2)2, _, Y)=(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T=(

32、i+i)*i+F=(i+i)*i+i(2)(E+T)*i,13.(1)短語i, F,(E+T)*i+F 素短語i, E+T 最左素短語E+TFIRSTVT(S)=V , FIRSTVT(T)= A ,E+T,(E+T),A , i,i, -(2)(3)(4)(5)(6)(8)(9)(10)(11)(12)12.(1)E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+Taddr=-1073743068 請(qǐng)解釋為什么輸出結(jié)果有區(qū)別。2，則結(jié)果是area=12.566360,第16頁共 6 頁編譯原理期末試題main()float s, pi, r;1。

33、1 、描述由正規(guī)式 b*(abb*)*(a| ) 定義的語言， 并畫出接受該語言的最簡(jiǎn)DFA 。2、證明文法 E E + id | id是SLR(1)文法。3、下面是表達(dá)式和賦值語句的文法，其中and 的類型是 bool boolbool ，+的類型是 int int int,=的類型是 int int bool， := 要求 id 和 E 的類型都是 int 或者 都是 bool 。為該文法寫一個(gè)語法制導(dǎo)定義或 翻譯方案，它完成類型檢查。S id := EE E and E | E + E | E = E |id4、對(duì)于下面 C 語言文件 s.cf1(int x)long x;x = 1;f

34、2(int x)long x; x = 1;某編譯器編譯時(shí)報(bào)錯(cuò)如下：s.c: In function f1 :s.c:3: warning: declaration of shadows a parameter 請(qǐng)回答，對(duì)函數(shù) f2 為什么沒有類似的警告 錯(cuò)誤。5、下面 C 語言程序經(jīng)非優(yōu)化編譯后，若運(yùn) 行時(shí)輸入 2，則結(jié)果是area=12.566360, addr=-1073743076 經(jīng)優(yōu)化編譯后，若運(yùn)行時(shí)輸入pi=3.14159;scanf(%f, &r);printf(area=%f, addr=%dn, s=pi*r*r, &r);6、描述由正規(guī)式 b a(bb a) b 定義的語

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

36、rintf( “%dn ”,&i &j);9、一個(gè) C 語言的函數(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è)它帶來的優(yōu)點(diǎn)。func:最簡(jiǎn)DFA如下：2、先給出接受該文法活前綴的DFA如下:func:pus pushlmov movlsubl sublE岳dE%ebp idl %esp, %ebp %es p, %eb p

37、$4,i%es p$8, %es PE + id 沖I2和ImomovldeflE8(%eb P), %edx8(%ebp2, %eax%edx|0和I3都只有移進(jìn)項(xiàng)目，肯定不會(huì)引起 4都無移進(jìn)項(xiàng)目并僅含一個(gè)歸約Ii 中，E 2個(gè)項(xiàng)目的展望符 Ii也肯定不會(huì)引起沖E突。+由此可以斷定該文法是EsLRti)的。|4項(xiàng)目，也肯定不會(huì)引起沖突；在 的后繼符號(hào)只有$，同第 號(hào)“ + ”不一樣，因此I3decl%eaxmovl %edx, -4(%eb p) movl%eax, -4(%eb p)-4(%eb p), %eax -4(%eb p), %eaxI %eax %eax, (%es p)fun

38、cfunc$4, %es pmovl movlpushl movlcall calladdileaveleaveretret編譯原理試卷八答案1、由正規(guī)式b*(abb*)*(a|)定義的語言是字母表a, b上不含子串a(chǎn)a的所有start3、語法制導(dǎo)定義如下。S id := E S.type := if(id .type = bool and E.type = bool) or (id .type = int and E.type = int)then typ e_ok else typ e_error E Ei and E2 E.type := ifEi.type = bool and E2.

39、type = bool then bool else typ e_error E Ei + E2 E.t ype := if Ei.t ype =int and E2.type = int then int else typ e_error E Ei = E2=int and E2.type E.t ype := if Ei.t ype =int then bool elsetyp e_error E idlook up (id.e ntry) E.t ype4、對(duì)于函數(shù)f1，局部變量x聲明的作用域 是整個(gè)函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問 形式參數(shù)x。由于這是一個(gè)合法的 C語言函 此編譯器給出

40、警告錯(cuò)誤。第31頁共6頁a,b的串對(duì)于函數(shù)f2，由于局部變量x的作用域 只是函數(shù)體的一部分，不會(huì)出現(xiàn)上述問題， 因而編譯器不報(bào)錯(cuò)。5、 使用非優(yōu)化編譯時(shí)，變量 S, pi, r在局部 數(shù)據(jù)區(qū)都分配4個(gè)字節(jié)的空間。使用優(yōu)化編 譯時(shí)，由于復(fù)寫傳播，pi*r*r 變成3.14159*r*r，pi=3.14159成為無用賦值而刪 去，函數(shù)中不再有 pi的引用，因此不必為 pi分配空間。類似地，s=3.14159*r*r也是一 個(gè)無用賦值(表達(dá)式要計(jì)算，但賦值是無用 的)，也不必為S分配空間。這樣，和非優(yōu) 化情況相比，局部數(shù)據(jù)區(qū)少了 8個(gè)字節(jié)，因 此r的地址向高地址方向移動(dòng)了8個(gè)字節(jié)。6、正規(guī)式b a(

41、bb a) b體現(xiàn)的特點(diǎn)是，每個(gè) a的左邊都有若干b，除非a是第一個(gè)字母。 該正規(guī)式定義的語言是：至少含一個(gè) 不含子串a(chǎn)a的所有a和 集。最簡(jiǎn)DFA如下：將所有參數(shù)退棧(常數(shù)n根據(jù)調(diào)用前做了多 少次PushI來決定)。右邊的編譯器版本：除了為局部變量分 配空間外，同時(shí)還為本函數(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)化的可能 性。7、的類型表達(dá)式是pointer(long), 的類型表達(dá)式是long。按照C 指向同一個(gè)類

42、型的兩個(gè)指針可消除左遞歸后的文法:B 1 BB 0 B | 1 B相應(yīng)的翻譯方案如下:B1 B .i := 1 BB. val :=B .valB0 B 1.i := B .i2 B 1B.val :=B1 .val|1 B 1.i := B .i2 +1 B 1B.val :=B1 .val|B .val := B .i表達(dá)式& 表達(dá)式& &j 語言的規(guī)定， 以相加減，它們值的差是它們之間的元素個(gè) 數(shù)。9、左邊的編譯器版本：一般只為局部變量 分配空間。調(diào)用函數(shù)前，用若干次Pushi指令將參數(shù)壓棧，返回后用addl $n, %esp 次編譯原理期末試題（三）1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪

43、兩類？對(duì)循環(huán)的優(yōu)化可以有哪三種?答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部?jī)?yōu)化和全局優(yōu)化兩類;對(duì)循環(huán)的優(yōu)化有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計(jì)算強(qiáng)度削減。2、寫出表達(dá)式a=b*c+b*d對(duì)應(yīng)的逆波蘭式、四元式序列和三元式序列。答：逆波蘭式:abc*bd*+:=b(Ma)bb(Ma)b(1) (*，b，c，t 1)(1) (*b，c )(*，b，d，t 2)(2) (*b，d )(+，t1，t 2, t3)(3) (+(1)，(2)(4)(:=，t3，/，a)(:=(3)，a)四元式序列:三元式序列：0P ARG1 ARG23、對(duì)于文法（SbMbM(L |aLMa)答：1）2）短語: 直接短語:Ma)， (Ma)，Ma)句柄:Ma)S bMb b(Lb設(shè)有字母表a，b上的正規(guī)式R=（ab|a）*。（2）將（1）所得的非確定有限自動(dòng)機(jī)確定化ab-01131221(3)對(duì)(2)得到的DFA化簡(jiǎn)，合并狀態(tài)0和2為狀態(tài)2:-+ba+(4)令狀態(tài)G: ATaB|a| ；1和2分別對(duì)應(yīng)