2022年《編譯原理》復(fù)習(xí)題及答案

1、編譯原理課程復(fù)習(xí)資料一、判定題：1. 一個上下文無關(guān)文法的開頭符,可以是終結(jié)符或非終結(jié)符； 2. 一個句型的直接短語是唯獨(dú)的； 3. 已經(jīng)證明文法的二義性是可判定的； 4. 每個基本塊可用一個 DAG表示； 5. 每個過程的活動記錄的體積在編譯時可靜態(tài)確定； 6.2 型文法肯定是 3 型文法； 7. 一個句型肯定句子； 8. 算符優(yōu)先分析法每次都是對句柄進(jìn)行歸約； 9. 采納三元式實(shí)現(xiàn)三地址代碼時,不利于對中間代碼進(jìn)行優(yōu)化； 10. 編譯過程中,語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的； 11. 一個優(yōu)先表肯定存在相應(yīng)的優(yōu)先函數(shù)； 12. 目標(biāo)代碼生成時,應(yīng)考慮如何充分利用運(yùn)算機(jī)的寄存器的問題；

2、 13. 遞歸下降分析法是一種自下而上分析法； 14. 并不是每個文法都能改寫成 LL1 文法； 15. 每個基本塊只有一個入口和一個出口； 16. 一個 LL1 文法肯定是無二義的； 17. 逆波蘭法表示的表達(dá)試亦稱前綴式； 18. 目標(biāo)代碼生成時,應(yīng)考慮如何充分利用運(yùn)算機(jī)的寄存器的問題； 19. 正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述； 20. 一個優(yōu)先表肯定存在相應(yīng)的優(yōu)先函數(shù)； 21.3 型文法肯定是 2 型文法； 22. 假如一個文法存在某個句子對應(yīng)兩棵不同的語法樹,就文法是二義性的； 二、填空題：1. 稱為規(guī)范推導(dǎo)；2. 編譯過程可分為,和 五個階段；3. 假如一個文法存在某

3、個句子對應(yīng)兩棵不同的語法樹,就稱這個文法是；4. 從功能上說,程序語言的語句大體可分為 語句和 語句兩大類；5. 語法分析器的輸入是,其輸出是；6. 掃描器的任務(wù)是從 中識別出一個個；7. 符號表中的信息欄中登記了每個名字的有關(guān)的性質(zhì),如 等等；8. 一個過程相應(yīng)的 DISPLAY表的內(nèi)容為；9. 一個句型的最左直接短語稱為句型的；10. 常用的兩種動態(tài)存貯安排方法是 動態(tài)安排和 動態(tài)安排；11. 一個名字的屬性包括 和；12. 常用的參數(shù)傳遞方式有,和；13. 依據(jù)優(yōu)化所涉及的程序范疇,可將優(yōu)化分成為,和 三個級別；14. 語法分析的方法大致可分為兩類,一類是 分析法,另一類是 分析法；15

4、. 猜測分析程序是使用一張 和一個 進(jìn)行聯(lián)合掌握的；16. 常用的參數(shù)傳遞方式有,和；17. 一張轉(zhuǎn)換圖只包含有限個狀態(tài),其中有一個被認(rèn)為是 態(tài)；而且實(shí)際上至少要有一個 態(tài)；18. 依據(jù)優(yōu)化所涉及的程序范疇,可將優(yōu)化分成為,和 三個級別；19. 語法分析是依據(jù)語言的 規(guī)章進(jìn)行；中間代碼產(chǎn)生是依據(jù)語言的 規(guī)章進(jìn)行的；20. 一個句型的最左直接短語稱為句型的；21. 一個文法 G,如它的猜測分析表 M不含多重定義,就該文法是 文法；22. 對于數(shù)據(jù)空間的存貯安排, FORTRAN采納 策略, PASCAL采納 策略；23. 假如一個文法存在某個句子對應(yīng)兩棵不同的語法樹,就稱這個文法是；24. 最右

5、推導(dǎo)亦稱為,由此得到的句型稱為；句型；分析法；25. 語法分析的方法大致可分為兩類,一類是分析法,另一類是26. 對于文法 G,僅含終結(jié)符號的句型稱為；27. 所謂自上而下分析法是指28. 語法分析器的輸入是 29. 局限于基本塊范疇的優(yōu)化稱,其輸出是；30. 猜測分析程序是使用一張和一個進(jìn)行聯(lián)合掌握的；31.2 型文法又稱為文法； 3 型文法又稱為文法；32. 每條指令的執(zhí)行代價定義為33. 算符優(yōu)先分析法每次都是對進(jìn)行歸約；三、名詞說明：1. 局部優(yōu)化 2. 二義性文法 3.DISPLAY 表 4. 詞法分析器 5. 最左推導(dǎo) 6. 語法 7. 文法 8. 基本塊 9. 語法制導(dǎo)翻譯 10

6、. 短語 11. 待用信息 12. 規(guī)范句型 13. 掃描器 14. 超前搜尋 15. 句柄 16. 語法制導(dǎo)翻譯 17. 規(guī)范句型 18. 素短語 19. 語法 20. 待用信息 21. 語義四、簡答題：1. 寫一個文法G,使其語言為不以0 開頭的偶數(shù)集；2. 已知文法 GS 及相應(yīng)翻譯方案 SaAb print “ 1” Sa print “ 2” AAS print “ 3” Ac print “ 4” 輸入 acab, 輸出是什么？3. 已知文法 GS SbAa AB | a BAa 寫出句子 baab 的規(guī)范歸約過程；4. 考慮下面的程序： Procedure px, y, z； b

7、egin y:=x+y; z:=z*z; end begin A:=2; B:=A*2; PA, A, B; Print A, B end. 試問,如參數(shù)傳遞的方式分別采納傳地址和傳值時,程序執(zhí)行后輸出 5. 文法 GS SdAB AaA| a BBb| 描述的語言是什么？6. 證明文法 GS SSaS| 是二義性的；7. 已知文法 GS SBA ABS| d BaA| bS | c 的猜測分析表如下A,B 的值是什么？ a b c d # S SBASBASBAAd A ABSABSABS B BaABbSBc給出句子 adccd 的分析過程；l b mc l a nbn| l=0, m=1

8、, n=2 8. 寫一個文法G, 使其語言為 LG=a9. 已知文法 GS: Sa| T TT,S|S 的優(yōu)先關(guān)系表如下：關(guān)系a,a-.=.,.請運(yùn)算出該優(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)的正規(guī)式；13. 基本的優(yōu)化方法有哪幾種？14. 寫一個文法G, 使其語言為 LG=abncn| n 0 15. 考慮下面的程序：procedure px, y, z; begin y:=y+z; z:=y*z+x e

9、nd; begin a:=2; b:=3; pa+b, b, a; print a end. 試問,如參數(shù)傳遞的方式分別采納傳地址和傳值時,程序執(zhí)行后輸出16. 寫出表達(dá)式ab*c-d/e的逆波蘭式和三元序列；17. 證明文法 GA AAA | A| 是二義性的；18. 令 =a,b ,就正規(guī)式a*b|b*a 表示的正規(guī)集是什么？19. 何謂 DISPLAY表？其作用是什么？20. 考慮下面的程序：procedure px, y, z； begin y:=y+2; z:=z+x; end begin a:=5; b:=2; pa+b, a-b, a; print a end. 試問,如參數(shù)傳遞

10、的方式分別采納傳地址和傳值時,程序執(zhí)行后輸出 a 的值是什么 . a 的值是什么 . 21. 寫一個文法 G, 使其語言為 LG=a nb nc m| n0 為奇數(shù), m0 為偶數(shù) 22. 寫出表達(dá)式 a:=b+c*e+b+c/f 的逆波蘭式和三元序列；23. 一個文法 G別是 LL1 文法的充要條件是什么？24. 已知文法 GS SS*aF | aF | *aF F+aF | +a 排除文法左遞歸和提公共左因子；25. 符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？五、運(yùn)算題：1. 設(shè)文法 GS: S | a | T TT,S | S排除左遞歸；構(gòu)造相應(yīng)的 FIRST 和 FOLLOW集

11、合；構(gòu)造猜測分析表 2. 語句 if E then S 1 改寫文法,使之適合語法制導(dǎo)翻譯；2 寫出改寫后產(chǎn)生式的語義動作；3. 設(shè)文法 GS ：S T | a TT+S | S 1 ）運(yùn)算 FIRSTVT 和 LASTVT；（ 2）構(gòu)造優(yōu)先關(guān)系表；4. 設(shè)某語言的 for 語句的形式為 1 to E 2 do S for i:E 其語義說明為 1 i:E 2 E LIMIT: again: if i LIMIT then Begin S; i: i 1 goto again End; （1）寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；（2）寫出每個產(chǎn)生式對應(yīng)的語義動作；5. 把語句 while a0 th

12、en a:=a+1 else a:=a*3-1; 翻譯成四元式序列；6. 設(shè)有基本塊 D:=A-C E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q K:=G*5 L:=K+J M:=L 假設(shè)基本塊出口時只有 M仍被引用,請寫出優(yōu)化后的四元序列；7. 已知文法 GS Sa | | T TT,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. 已知文法 GS: S aAcBe

13、A Ab| b B d 1 給出句子 abbcde 的最左推導(dǎo)及畫出語法樹； 2 給出句型 aAbcde 的短語、素短語；10. 設(shè)文法 GS: ST | aS | a TT,S | S 排除左遞歸和提公共左因子； 構(gòu)造相應(yīng)的 FIRST 和 FOLLOW集合； 構(gòu)造猜測分析表；11. 把語句 if X0 Y0 do X:=A*3 else Y:=B+3; 翻譯成四元式序列；12. 已知文法 GS: E E+T | T T T*F| F F E| i 1給出句型 i+i*i+i的最左推導(dǎo)及畫出語法樹； 2給出句型 E+T*i+F 的短語,素短語和最左素短語；13. 設(shè)文法 GS ：S T |

14、S T T U |T U Ui |-U （ 1）運(yùn)算 FIRSTVT 和 LASTVT；（ 2）構(gòu)造優(yōu)先關(guān)系表；參考答案一、判定題：1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 二、填空題：1. 最右推導(dǎo)）2. 詞法分析）,（語法分析）,（中間代碼生成） ,（代碼優(yōu)化） ,（目標(biāo)代碼生成）3. 二義性的）4. 執(zhí)行性）,（說明性）5. 單詞符號）,（語法單位）；6. 源程序）,（單詞符號）7. 類型、種屬、所占單元大小、地址） 8. 現(xiàn)行活動記錄地址和全部外層最新活動記錄的地址 9.

15、 句柄）10. 棧式 ,（堆式）11. 類型 ,（作用域）12. 傳地址）,（傳值）,（傳名）13. 局部優(yōu)化）,（循環(huán)優(yōu)化） ,（全局優(yōu)化）14. 自上而下）,（自下而上）15. 分析表）,（符號棧）16. 傳地址）,（傳值）,（傳名）17. 初）,（終）18.9 局部優(yōu)化）,（循環(huán)優(yōu)化）,（全局優(yōu)化）19. 語法）,（語義）20. 句柄）21.LL1 文法）22. 靜態(tài)）,（動態(tài)）23. 二義性文法）24. 規(guī)范推導(dǎo)）,（規(guī)范）25. 自上而下）,（自下而上）26. 句子 27. 從開頭符號動身,向下推導(dǎo),推出句子）28. 單詞符號）,（語法單位）29. 局部優(yōu)化）30. 分析表）,（符號

16、棧）31. 上下文無關(guān)文法） ,（正規(guī)）32. 指令拜訪主存次數(shù)加 1）33. 最左素短語）三、名詞說明：1. 局部優(yōu)化：局限于基本塊范疇的優(yōu)化稱；2. 二義性文法：假如一個文法存在某個句子對應(yīng)兩棵不同的語法樹,就稱這個文法是二義性文法；3.DISPLAY 表：過程的嵌套層次顯示表,記錄該過程的各外層過程的最新活動記錄的起始地址；4. 詞法分析器：執(zhí)行詞法分析的程序；5. 最左推導(dǎo)：任何一步 =都是對 中的最右非終結(jié)符替換；6. 語法：一組規(guī)章,用它可形成和產(chǎn)生一組合式的程序；7. 文法：描述語言的語法結(jié)構(gòu)的形式規(guī)章；8. 基本塊：指程序中一次序執(zhí)行的語句序列,其中只有一個入口和一個出口,入口

17、就是其中的第一個語 句,出口就是其中的最終一個語句；9. 語法制導(dǎo)翻譯：在語法分析過程中,依據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序進(jìn)行翻譯的方法叫做語法制導(dǎo)翻譯；10. 短語： 令 G是一個文法, S劃文法的開頭符號,假定 是文法 G的一個句型, 假如有 S A且 A ,就稱 是句型 相對非終結(jié)符 A 的短語；11. 待用信息：假如在一個基本塊中,四元式 i 對 A 定值,四元式 j 要引用 A值,而從 i 到 j 之間沒有 A的其它定值,就稱 j 是四元式 i 的變量 A 的待用信息；12. 規(guī)范句型：由規(guī)范推導(dǎo)所得到的句型；13. 掃描器：執(zhí)行詞法分析的程序；14. 超前搜尋：在詞法分析過程中,有

18、時為了確定詞性,需超前掃描如干個字符；15. 句柄：一個句型的最左直接短語；16. 語法制導(dǎo)翻譯：在語法分析過程中,依據(jù)每個產(chǎn)生式所對應(yīng)的語義程序進(jìn)行翻譯的方法 叫做語法制導(dǎo)翻譯；17. 規(guī)范句型：由規(guī)范推導(dǎo)所得到的句型；18. 素短語：素短語是指這樣一個短語,至少含有一個終結(jié)符,并且,除它自身外不再含任何更小的素短語；19. 語法：是組規(guī)章,用它可形成和產(chǎn)生一個合式的程序；20. 待用信息：假如在一個基本塊中,四元式i 對 A 定值,四元式j(luò) 要引用 A值,而從i 到 j 之間沒有A的其它定值,就稱j 是四元式 i 的變量 A 的待用信息；21. 語義：定義程序的意義的一組規(guī)章；四、簡答題：

19、1. 所求文法是 GS: SAB |B A0AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2. 輸出是 4231 3. 句子 baab 的規(guī)范歸約過程：步驟符號棧輸入串動作0 # baab# 預(yù)備1 #b aab# 移進(jìn)2 #b aab# 移進(jìn)3 #ba ab# 移進(jìn)4 #bA ab# 歸約5 #bMa bb# 移進(jìn)6 #bMa b# 移進(jìn)7 #bB b# 歸約8 #bA b# 歸約9 #bAb # 移進(jìn)10 #S # 接受4. 傳地址 A=6, B=16 傳值 A=2, B=4 5.LG=danbm |n 0, m 06. 證明：由于文法 GS 存在句子 aa

20、 有兩個不同的最左推導(dǎo),所以文法 S=SaS=SaSaS=aSaS=aaS=aa S=SaS=aS=aSaS=aaS=aa GS 是是二義性的；7. 句子 adccd 的分析過程：8. 所求文法是步驟#S 符號棧adccd# 輸入串SBA產(chǎn)生式0 1 #AB adccd# 2 #AAa adccd# BaA3 #AA dccd# Ad4 #Ad dccd# 5 #A ccd# ABS6 #SB ccd# 7 #Sc ccd# Bc8 #S cd# Bc9 #AB cd# 10 #Ac d# Ad11 #A d# 12 #d d# 13 # # GS: SAB AaAc | D DbD | b

21、BaBb | aabb 9. 函數(shù)a , f 4 2 4 4 g 5 5 2 3 10. 優(yōu)化：對程序進(jìn)行各種等價變換,使得從變換后的程序動身,能產(chǎn)生更有效的目標(biāo)代碼；三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化 11. 目標(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: S aB | a Bbc |bBc 15

22、. 傳值 a=2 傳地址 a=15 16. 逆波蘭式 : abcd-*e/+ 三元序列 : op arg1 arg2 1 - c d 2 * b 1 3 / 2 e 4 + a 3 17. 證明：由于文法 GS 存在句子 有兩個不同的最左推導(dǎo),所以文法GS 是是二義性的；A=AA=AA=A= A=AA=A=A= 18.a*b|b*a=a,b,ab,ba,aab,bba19.Display表: 嵌套層次顯示表由于過程嵌套答應(yīng)內(nèi)層過程引用外層過程定義的數(shù)據(jù),因此,當(dāng)一個過程運(yùn)行時必需跟蹤它的全部外層過程的最新活動記錄起始地址, display表就是用于登記每個外層過程的最新活動記錄起始地址；20.

23、 傳地址 a=12 傳值 a=5 21. 所求文法是 GS: SAC AaaAbb | ab CccC | cc 22. 逆波蘭式 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別是 LL1 文法的充要條件是 : 1 FIRST FIRST = 2 假如 = * , FIRST FOLLOWA= 24. 排除左遞歸 SaFS | *aFS S*aFS | F+aF | +a提公共左因子 , 文法GS SaFS | *aFS S*aFS | F+aFFF |

24、25. 作用：登記源程序中顯現(xiàn)的各種名字及其信息,以及明白各階段的進(jìn)展?fàn)顩r；主要技術(shù)：線性表,對折查找,雜奏技術(shù)；五、運(yùn)算題：11 排除左遞,文法變?yōu)镚S ：S | a | TTST | S |T,ST此文法無左公共左因子；2 構(gòu)造相應(yīng)的 FIRST 和 FOLLOW集合：FIRSTS=a, , , FOLLOWS=#, , FIRSTT=a, , ,FOLLOWT= FIRSTT=, ,FOLLOWF= 3 構(gòu)造猜測分析表：S a , ,ST# SaSSTT TSTTSTTSTTTT2. 1 Cif E then 1 SCS 2 Cif E then BACKE.TC, NXQ; C.cha

25、in:=E.FC SCS 1 S.chain:=MERGC.Chain, S 1 . Chain 3. 1 FIRSTVTS=a, FIRSTVTT=+, a a, LASTVTS=a, LASTVTT=+, a, 2 a + a . + . . . . . for i:=E2 do 1 SFS2 Ffor i:=EGEN:=, E1 to E 2 do 1 .place, _, entryi; F.place:=entryi; LIMIT:=Newtemp; GEN:=, E 2 .place, _, LIMIT; Q:=NXQ; F.QUAD:=q; GENj, entryi, LIMIT

26、, q+2 F.chain:=NXQ; GENj, _, _, 0 1 SFS BACKPATCHS 1 .chain, NXQ; GEN+, F.place, 1, F.place; GENj, _, _, F.QUAD; S.chain:=F.chain 5.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 12 6. 優(yōu)化后的四元序列 D:=A-C E:=A*C F:=D*E M:=F+20 7. 最左推導(dǎo) S=T=T,S=S,S=a,S=a,T=a,T,S=a,S,S=a,a,S=a,a,a