《編譯原理》考試試題及答案(匯總)

1、編譯原理考試試題及答案( 匯總)一、是非題 ( 請在括號內(nèi)，正確的劃 " ，錯誤的劃 X)( 每個2 分，共 20分)1 . 編譯程序是對高級語言程序的解釋執(zhí)行。( x )2.個有限狀態(tài)自動機(jī)中，有且僅有一個唯一的終態(tài)。( X)3.個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。( V )4.語法分析時必須先消除文法中的左遞歸。 (x)5.分析法在自左至右掃描輸入串時就能發(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)代碼的效率將起更大作用

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

3、的位置D. ( ) 單詞自身值B.()M1 和 M2D. ( ) M1 和 M2 狀態(tài)數(shù)和有> 0)D .( ) x*如果文法 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)掌握A( ) 源程序B( )目標(biāo)語言C( ) 編譯方法D ( ) 以上三項都是6四元式之間的聯(lián)系是通過實現(xiàn)的。A( ) 指示器B( ) 臨時變量C() 符號表D () 程序變量7 . 表達(dá)式 ( 門 AV B) A (C

4、 V D)的逆波蘭表示為。A ( ) nVAVB. ( ) A 門 BVVAC. ( ) V nVAD . ( ) A 門 BVAV8. 優(yōu)化可生成的目標(biāo)代碼。A( ) 運行時間較短B( ) 占用存儲空間較小C( ) 運行時間短但占用內(nèi)存空間大D( ) 運行時間短且占用存儲空間小9下列優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的。A. ( ) 強度削弱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)識符的行號三、填空題

5、(每空1 分，共10 分)1計算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯。2掃描器是詞法分析器，它接受輸入的源程序，對源程序進(jìn)行詞法分析并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。3自上而下分析法采用移進(jìn)、歸約、錯誤處理、接受等四種操作。4一個分析器包括兩部分：一個總控程序和一張分析表。5后綴式所代表的表達(dá)式是() 。6局部優(yōu)化是在基本塊范圍內(nèi)進(jìn)行的一種優(yōu)化。四、簡答題 (20 分 )1. 簡要說明語義分析的基本功能。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查2.考慮文法GS:S f (T) | | aT f | S消除文法的

6、左遞歸及提取公共左因子。解：消除文法GS 的左遞歸：Sf(T) | | aT fT'f' |提取公共左因子：Sf (T) |'S'f |TT'f' I 3. 試為表達(dá)式 ()*(10)+8) 寫出相應(yīng)的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +4. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：(A<C A B<D)(A > 1)1;(A w D)2;。解：該語句的四元式序列如下( 其中 E1 、 E2 和 E3 分別對應(yīng) AvCA BvD、 A 1和 Aw D,并且關(guān)系運算符優(yōu)先級高

7、) ：100 (j<,102)101 (,113)102 (j<,104)103 (,113)104 (,1,106)105 (,108)106 (+, C, 1, C)107 (,112)108 (j w ,110)109 (,112)110 (+, A, 2, A)111 (,108)112 (,100)1135. 已知文法 GS 為 S f ，試證明文法GS為二義文法證明：由文法 GS :S-, 對句子對應(yīng)的兩棵語法樹為:a S bSb/Ka S ba S bS ba S bbb因此，文法GS 為二義文法五 . 計算題（ 10 分）已知文法判斷該文法是否是（1）文法，若是構(gòu)造

8、相應(yīng)分析表，并對輸入串給出分析過程。解：增加一個非終結(jié)符后，產(chǎn)生原文法的增廣文法有:S'->A下面構(gòu)造它的 （0） 項目集規(guī)范族為：abd氐SiAIi ：W *A 兮“拖A ，血AT InaccIci；L：AW AdIA->aA-d衛(wèi)亠血A->aA'b衛(wèi)亠I5 ：IiA-*>aA.d lI ;A->aAb ?從上表可看出 ,狀態(tài) I0 和 12 存在移進(jìn) -歸約沖突，該文法不是（ 0）文法。對于 I0來說有：（ A）na=n狀態(tài)下面臨輸入符號為a 時移進(jìn)，為a= ，所以在 I0時歸約，為其他時報錯。對于I2 來說有也有與I0 完全相同的結(jié)論。這就是

9、說，以上的移進(jìn)-歸約沖突是可以解決的，因此該文法是（1）文法 其（ 1）分析表為 :對輸入串給出分析過程為:爭驟符號樸輸入邑ACTIOM1s：GOTO202b#r?39029b#S140234口501acc一、是非題 .1. 一個上下文無關(guān)文法 的開始符，可以是 終結(jié)符或 非終結(jié)符。2. 一 個句型的直接短語是唯一的。3. " 已）經(jīng)證明文法的二義性是可判定的。4. （每）個基本塊可用一個表示。（ ）5. 每個過程的活動記錄的體積在編譯時可靜態(tài)確定。（ ）6.2型文法一定是3型文法。7. （一）個句型一定句子。（算）符優(yōu)先分析法每次都是對句柄進(jìn)行歸約。X （）8.9. 采用三元式實現(xiàn)

10、三地址代碼時，不利于對中間代碼進(jìn)行優(yōu)化。10.編譯過）程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。（）11.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。X12. 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機(jī)的寄存器的問題。13.（）歸下降分析法是一種自 下遞而 上 分析法。14.并不是每 個 文法都能改 寫成（1）文法。15.一 個每個基入口和一個本塊只有出口。16. 一個（1）文法一定是無二義的。17.亦 稱逆前 綴式波 蘭。法 表 示的表達(dá)試18. 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機(jī)的寄存器的問題。（ ）19. 正 規(guī) 文法產(chǎn)生 的語言 都可以用 上下文 無關(guān)文法 來描述。20. 一個優(yōu)先表一定

11、存在相應(yīng)的優(yōu)先函數(shù)。21.3型文法一定是2型文法。22. 如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則文法是二義性的。（ ）x 2.x 3. x4.V5.V 6. x 7. x答案： 1.8. x 9. V 10. x 11.12. V 13.x 14.V15.V 16.V 17.x 18.xV 19. V 20. x 21. V 22. V二、填空題：2. 編譯過程可分為（ 詞法分析），（語法分析），（語義分析與中間代碼生成 ），（優(yōu)化）和（目標(biāo)代碼生成）五個階段。3. 如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是（ 二義性的 ）。4. 從功能上說， 程序語言的語句大體可

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

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

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

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

16、1.待用信息如果在一個基本塊中，四元式i 對 A 定值，四元式 j 要引用 A值，而從 i 到 j 之間沒有 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é)符，并且，除它自吾。身外不再含任何更小的素短語1

17、9. 語法是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。20. 待用信息如果在一個基本塊中，四元式i 對 A 定值，四元式j(luò)要引用i 的變量值，而從i 到j(luò) 之間沒有A 的其它定值，則稱j 是四元式i、一的待用信息。21. 語義定義程序的意義的一組規(guī)則。四、簡答題：1. 寫一個文法G,使其語言為不以 0 開頭的偶數(shù)集。s-Sa A“ 3”Ac“ 4”輸入 ,輸出是什么？3. 已知文法 G(S) SA (B | aB )2. 已知文法 G(S) 及相應(yīng)翻譯方案 ” P（x, y, z ） ；*z;2;*2 ?P(A, A, B);A, B試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出

18、A, B 的值是什么 ？5. 文法 G(S) SA aB 描述的語言是什么？6. 證明文法 G(S)S 是二義性的。7. 已知文法 G(S) S A dB I c的預(yù)測分析表如下abcd#SS|S|SAAfAfAfAf dB BfB fB fc給出句子的分析過程。8. 寫一個文法 G,使其語言為 L(G)= l>=0, m>=1, n>=29. 已知文法 G(S):S-(T)T f的優(yōu)先關(guān)系表如下：關(guān)系a()Ja-.>.>(V.V.=V.)-.>.>JV.V.>.>10?何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？11. 目標(biāo)代碼有哪幾種

19、形式？生成目標(biāo)代碼時通常應(yīng)考慮哪幾個問題？、12.一字母表藝 =a, b ，試寫出藝上所有以 a 為首的字組成的正規(guī)集相對應(yīng)的正規(guī)式。13. 基本的優(yōu)化方法有哪幾種？14. 寫一個文法 G,使其語言為 L(G)= n > 015. 考慮下面的程序：P(x, y, z);2；3；p(, b, a);a試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a 的值是什么 ？16. 寫出表達(dá)式 a + b*() 的逆波蘭式和三元序列。17. 證明文法 G(A)A f | (A)|是二義性的。18. 令藝 = ，則正規(guī)式 a*a 表示的正規(guī)集是什么？19. 何謂表？其作用是什么？20.

20、考慮下面的程序：P(x, y, z) ；2；p(, , a);a試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a 的值是什么 ？21. 寫一個文法 G,使其語言為 L(G)= n>0 為奇數(shù)， m>0 為偶數(shù) 22. 寫出表達(dá)式 ()*() 的逆波蘭式和三元序列。23. 個文法 G 別是 (1) 文法的充要條件是什么？24. 已知文法 GSS S*|*I、消除文法左遞歸和提公共左因子。25. 符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？答案： 1. 所求文法是 GS:S A0AB 2468C 1357|9步驟符號棧輸入串動作0#b()預(yù)備1()移進(jìn)2()移進(jìn)a

21、移進(jìn)3(a1)4(Aa歸約1)5()移進(jìn)6()移進(jìn)7(B歸約8歸約9移進(jìn)10接受D 02. 輸出是 42313. 句子 b()b 的規(guī)范歸約過程：4. 傳地址 6, 16傳值 2,45(G)= >0, m> 06. 證明：因為文法GS存在句子有兩個不同的最左推導(dǎo)，所以文法GS 是是二義性的。>>>>>>>>>>7. 句子的分析過程：步驟符號棧輸入串產(chǎn)生式01S2B34A d5678910111213#8. 所求文法是 GS: S A D D b B9.AB cB cA d函數(shù)a()5f4244g552310.優(yōu)化：對程序進(jìn)

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

23、a(3)17. 證明：因為文法 GS 存在句子 () 有兩個不同的最左推導(dǎo)，所以文法GS 是是二義性的。>>(A)>()>()>* >>(A)=>()18.(a a)= 一19 表 : 嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此， 當(dāng)一個過 程運行時必須跟蹤它的所有外層過程的最新活動記錄起始地址，表就是用于登記每個外層過程的最新活動記錄起始地址。20.傳地址 12傳值 521.所求文法是 GS:22. 逆波蘭式 * 三元序列 1 2(1)+bc(2)*(1)e(3)+bc(4)/ (3) f(5)+(2)(4)(6)a (

24、5)23. 一個文法 G 別是 (1) 文法的充要條件是 :(1) ( a n( B) =(2)如果 B =*> , ( a ) n (A)= 24. 消除左遞歸S'| * 'S' *'|F |, 文法 G' (S)提公共左因子S'| * 'S' *'|F'F' F|25. 作用：登記源程序中出現(xiàn)的各種名字及其信息，況。主要技術(shù)：線性表，對折查找，雜奏技術(shù)。五、計算題：1. 設(shè)文法G(S):以及了解各階段的進(jìn)展?fàn)頢 八 | a | (T)T | S 構(gòu)造相應(yīng)的和集合； 構(gòu)造預(yù)測分析表2. 語句 ES(

25、1) 改寫文法，使之適合語法制導(dǎo)翻譯；(2) 寫出改寫后產(chǎn)生式的語義動作。3. 設(shè)文法 G( S) ：Sf (T) | aT |S(1)計算 和；(2) 構(gòu)造優(yōu)先關(guān)系表。4. 設(shè)某語言的語句的形式為(1) ( 2)i: = E(1) E"S其語義解釋(為1)i: = S :=目 2):i v =S;i: = i +1( 1) 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；( 2) 寫出每個產(chǎn)生式對應(yīng)的語義動作。5. 把語句a<10c>0 1*3-1; 翻譯成四元式序列。6. 設(shè)有基本塊*C*E2*C2*S*Q*5假設(shè)基本塊出口時只有M 還被引用，請寫出優(yōu)化后的四元序列7. 已知文法 G(

26、S) S a | 八 | (T)Tf | S(1) 給出句子 (a,() 的最左推導(dǎo)；(2) 給出句型 () 的短語 , 直接短語，句柄。 8. 對于 C語言 SE語句(1) 改寫文法，使之適合語法制導(dǎo)翻譯；(2) 寫出改寫后產(chǎn)生式的語義動作。9. 已知文法 G(S)S fA f bBfd(1) 給出句子的最左推導(dǎo)及畫出語法樹；(2) 給出句型的短語、素短語。10. 設(shè)文法 G(S):S f (T) | | aT f | S消除左遞歸和提公共左因子；構(gòu)造相應(yīng)的和集合；構(gòu)造預(yù)測分析表。11. 把語句X>0 V YvoX>0 *33;翻譯成四元式序列。12. 已知文法 G(S)Ef |

27、 TT f T* FF f (E)| i(1) 給出句型 ()* 的最左推導(dǎo)及畫出語法樹；(2) 給出句型 ()* 的短語，素短語和最左素短語。13. 設(shè)文法 G( S) ：SfT | S V TTf U A UUf i(1)計算 和；(2)構(gòu)造優(yōu)先關(guān)系表。答案： ( 1) 消除左遞，文法變?yōu)镚 S:S-: | a | (T)'T'|ST'|此文法無左公共左因子。構(gòu)造相應(yīng)的和集合：(S) =a, 八,(，(S)=#, , )(T) =a, 八,(，(T)=(T')=, ,(F)=)(3) 構(gòu)造預(yù)測分析表：aA()#5SS aS人S (T)'TT '

28、;T'T'T'T'T''2. (1)Cl (E(2)(i)S (, S.)3. (1) (S)=a, ( (T)=+, , (S) =(T)=+, a, )a+()a.>.>+V.>V.>(V.V.V.=).>.>>.4. (1) F(i)ES -(1) E (2)(2)F-,_,(, E(i)； (i) ；(,E (2) , _,) ；(j w, (i), , 2)5. (1) (j<, a,10 ', (3)Sh_ ，0)(S ,);(+, , 1,);(j, _, _,);jjj,_/

29、?8,)a+,j,_,?, ,2,/a/ )j(1), (5) T1), T2), T3)*C*E207. 最左推導(dǎo)(T)=>()=>()=>()=>(a,(T)=>(a,()=>(a,()=>(a,()=>(a ,()短語()()()a直接短語a句柄8.(1)Sf Mi S i M2 EMe(2)Mfe;Sf M1 S 1 M2 E (s1, M 2);(, M1);J9.(1) >>>>10.(1 S) S 'ff(LS ) | e'Lf'| eL'f'')=a, (,e

30、 (2) (S)=a, (S(L)=a, ( (L')=,e (S)=, ), # (S')=, ), #(L)= ) (L')= )()a#SS-(L)S '0S'f SS；- S'- SS；S LL 'L 'L''L'EL '11.(1) (j>, X, 0, (5) (j, _, _, (3)(3) (j<, Y, 0, (5) ( j,亠， (11)(5) (j>0, X, 0, (7)(6) (j, _, _, (7)(7) (*, A, 3, T 1)(8) (, T亠

31、，, _, N)(9) (j,(5)(10) (j, 亠,(13)(11)(+, B, 3, T2)(12)(, T2, _, Y)12.(1) >>>T*>F*>(E)*>()*>()*=>()*>()*>()*>()*>()*=>()*>()*短語 i, F,素短 (),()*i,()*語 i, 最左素短語? (S)=V ,A ,-(T)=A , i ,-(U)=i, -(S)=V ,A ,-(T)=A , i ,-( 2)(叭,-SiVA-.>.>VV.>V.V.AV.>.>

32、V.-V.>.>V.1、描述由正規(guī)式 b*(*)*( e) 定義的語言，并畫出接受該語言的最簡。2、證明文法 E?E+|是(1) 文法。3、 下面是表達(dá)式和賦值語句的文法，其中的類型是？ ，+的類型是 ?, =的類型是 ？，要求和 E 的類型都是或者都是。為該文法寫一個語法制導(dǎo)定義或翻譯方案，它完成類型檢查。S ? EE?EE|E+E|E=E4、對于下面C 語言文件f1( x)x;x = 1;f2( x)x;x = 1;某編譯器編譯時報錯如下：: f1 ':3: :x'a請回答，對函數(shù)f2 為什么沒有類似的警告錯誤。5、下面 C 語言程序經(jīng)非優(yōu)化編譯后，若運行時輸入

33、2，則結(jié)果是12.566360, 1073743076經(jīng)優(yōu)化編譯后，若運行時輸入2，則結(jié)果是12.566360, 1073743068請解釋為什么輸出結(jié)果有區(qū)別()s, , r;3.14159;("", );(", n", *r*r, );6描述由正規(guī)式b*a( *a) *b* 定義的語言，并畫出接受該語言的最、簡面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0 和 1 的串集：B ? B 0 | B 1 | 1 下面的翻譯方案計算這種正二進(jìn)制數(shù)的十進(jìn)制值：B ?B 0 B i 2 | B i 1 B i 2 +1| i i 請消除該基礎(chǔ)文法的左遞歸，再重寫一個翻譯方案，

34、它仍然計算這種正二進(jìn)制數(shù)的十進(jìn)制值。8、 在 C 語言中，如果變量 i 和 j 都是類型，請寫出表達(dá)式和 表達(dá)式的類型表達(dá)式。 為幫助你回答問題， 下面給出一個程序作 為提示，它運行時輸出 i。() i, j;(“ n” , );9、一個C 語言的函數(shù)如下：(i) i; j;j = i - 1；(j);下面左右兩邊的匯編代碼是兩個不同版本編譯器為該函數(shù)產(chǎn)生的代碼。 左邊的代碼在調(diào)用之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有實質(zhì)區(qū)別。請敘述右邊代碼對參數(shù)傳遞的處理方式并推測它帶來的優(yōu)點。I:|$4,I$8,8(), II8(),I,-4()I,-4()-4(),I-4(),I,()I$4,I編譯原理試卷八答案1、由正規(guī)式b*(*)*( e)定義的語言是字母表a, b 上不含子串a(chǎn)的所有串的集合。最簡如下：2、先給出接受該文法活前綴的如下:EE+?丨4I 0 和 I 3 都只有移進(jìn)項目，肯定不會引起沖突；I 2 和 I 4 都無移進(jìn)項目并僅含一個歸約項目，也肯定不會引起沖突；在Ii 中， E0 的后繼符號只有 $，同第 2 個項目的展望符號“+”不一樣，因此I i 也肯定不會引起沖突。由此可以斷定該文法是( 1)的。3、語法制導(dǎo)定義如下S ? E (= E ? Ei E2 EE ? E i + E 2 E E ? Ei =E