2021年《編譯原理》復習題及答案

1、精品word可編輯資料- - - - - - - - - - - - -一、判定題：編譯原理課程復習資料第 17 頁，共 13 頁- - - - - - - - - -1. 一個上下文無關(guān)文法的開頭符，可以是終結(jié)符或非終結(jié)符；2. 一個句型的直接短語是唯獨的；3. 已經(jīng)證明文法的二義性是可判定的；4. 每個基本塊可用一個dag表示；5. 每個過程的活動記錄的體積在編譯時可靜態(tài)確定；6.2 型文法肯定是 3 型文法；7. 一個句型肯定句子；8. 算符優(yōu)先分析法每次都是對句柄進行歸約；9. 采納三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化；10. 編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)

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

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

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

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

6、9. 語法制導翻譯10. 短語11. 待用信息12. 規(guī)范句型13. 掃描器14. 超前搜尋15. 句柄16. 語法制導翻譯17. 規(guī)范句型18. 素短語19. 語法20. 待用信息21. 語義四、簡答題：1. 寫一個文法 g, 使其語言為不以 0 開頭的偶數(shù)集；2. 已知文法 gs 及相應翻譯方案saab print “1” sa print“2” aas print “3” ac print“4”輸入 acab, 輸出是什么？3. 已知文法 gs sbaaab | a baa寫出句子 baab的規(guī)范歸約過程；4. 考慮下面的程序：procedure px, y, z；begin y:=x+

7、y; z:=z*z; end begin a:=2; b:=a*2;pa, a, b;print a, b end.試問，如參數(shù)傳遞的方式分別采納傳地址和傳值時，程序執(zhí)行后輸出a,b 的值是什么？5. 文法 gs sdab aaa| abbb|描述的語言是什么？6. 證明文法 gsssas| 是二義性的；7. 已知文法 gssbaabs| d baa| bs | c的猜測分析表如下abcd#ssbasbasbaaabsabsabsadbbaabbsbclm ln n給出句子 adccd的分析過程；8. 寫一個文法 g, 使其語言為 lg=a9. 已知文法 gs: sa| ttt,s|s的優(yōu)先關(guān)

8、系表如下：b c a b | l=0, m=1, n=2關(guān)系aa-.,.=.,.請運算出該優(yōu)先關(guān)系表所對應的優(yōu)先函數(shù)表；10. 何謂優(yōu)化？按所涉及的程序范疇可分為哪幾級優(yōu)化？11. 目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？12. 一字母表 =a, b，試寫出 上全部以 a 為首的字組成的正規(guī)集相對應的正規(guī)式；13. 基本的優(yōu)化方法有哪幾種？n14. 寫一個文法 g, 使其語言為 lg=ab15. 考慮下面的程序：procedure px, y, z; beginy:=y+z; z:=y*z+x end; begin a:=2;b:=3;pa+b, b, a; print ae

9、nd.nc | n 0試問，如參數(shù)傳遞的方式分別采納傳地址和傳值時，程序執(zhí)行后輸出a 的值是什么 .16. 寫出表達式 a b*c-d/e的逆波蘭式和三元序列；17. 證明文法 gaaaa | 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 aend.試問，如參數(shù)傳遞的方式分別采納傳地址和傳值時，程序執(zhí)行后輸出a 的值是什

10、么 .21. 寫一個文法 g, 使其語言為 lg=anbncm| n0為奇數(shù)， m0 為偶數(shù) 22. 寫出表達式 a:=b+c*e+b+c/f的逆波蘭式和三元序列；23. 一個文法 g別是 ll1 文法的充要條件是什么？24. 已知文法 gs s s*af | af | *af f +af | +a排除文法左遞歸和提公共左因子；25. 符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？五、運算題：1. 設(shè)文法 gs:s | a | t tt,s | s排除左遞歸；構(gòu)造相應的first 和 follow集合；構(gòu)造猜測分析表2. 語句 if e then s(1) 改寫文法，使之適合語法制導翻譯；

11、(2) 寫出改寫后產(chǎn)生式的語義動作；3. 設(shè)文法 gs ： st | a tt+s | s1 ）運算 firstvt 和 lastvt；（ 2）構(gòu)造優(yōu)先關(guān)系表；4. 設(shè)某語言的 for語句的形式為11for i: e 其語義說明為i: eto e2do s2limit: eagain: if i limit then begins;i: i 1 goto again end;（ 1）寫出適合語法制導翻譯的產(chǎn)生式；（ 2）寫出每個產(chǎn)生式對應的語義動作；5. 把語句while a0 then a:=a+1 else a:=a*3-1;翻譯成四元式序列；6. 設(shè)有基本塊d:=a-c e:=a*c f

12、:=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 | | ttt,s | s(1) 給出句子 a,a,a的最左推導；(2) 給出句型 t,s,a的短語 ,直接短語，句柄；8. 對于 c 語言 do s while e語句(1) 改寫文法，使之適合語法制導翻譯；(2) 寫出改寫后產(chǎn)生式的語義動作；9. 已知文法 gs: s aacbea ab| b b d(1) 給出句子 abbcde 的最左推導及畫出語法樹；(2) 給出句型 aabcde 的短語、

13、素短語；10. 設(shè)文法 gs:s t | as | a t t,s | s 排除左遞歸和提公共左因子； 構(gòu)造相應的 first 和 follow集合； 構(gòu)造猜測分析表；11. 把語句if x0 y0 do x:=a*3 else y:=b+3;翻譯成四元式序列；12. 已知文法 gs: e e+t | tt t*f| f f e| i(1) 給出句型 i+i*i+i的最左推導及畫出語法樹；(2) 給出句型 e+t*i+f的短語，素短語和最左素短語；13. 設(shè)文法 gs ： s t | s t t u |t uu i |-u（ 1）運算 firstvt 和 lastvt；（ 2）構(gòu)造優(yōu)先關(guān)系表；

14、一、判定題：參考答案1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.12. 13. 14. 15. 16. 17. 18.19. 20.21. 22. 二、填空題：1. 最右推導）2. 詞法分析），（語法分析） ，（中間代碼生成） ，（代碼優(yōu)化） ，（目標代碼生成）3. 二義性的）4. 執(zhí)行性），（說明性）5. 單詞符號），（語法單位） ；6. 源程序），（單詞符號）7. 類型、種屬、所占單元大小、地址）8. 現(xiàn)行活動記錄地址和全部外層最新活動記錄的地址9. 句柄）10. 棧式 ，（堆式）11. 類型 ，（作用域）12. 傳地址），（傳值），（傳名）13. 局部優(yōu)化），（循

15、環(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ī)范推導），（規(guī)范）25. 自上而下），（自下而上）26. 句子 27. 從開頭符號動身，向下推導，推出句子）28. 單詞符號），（語法單位）29. 局部優(yōu)化）30. 分析表），（符號棧）31. 上下文無關(guān)文法） ，（正規(guī)）32. 指令拜訪主存次數(shù)加1）33. 最左素短語） 三、名詞說明：1. 局部優(yōu)

16、化：局限于基本塊范疇的優(yōu)化稱；2. 二義性文法：假如一個文法存在某個句子對應兩棵不同的語法樹，就稱這個文法是二義性文法；3. display 表：過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址；4. 詞法分析器：執(zhí)行詞法分析的程序；5. 最左推導：任何一步 = 都是對 中的最右非終結(jié)符替換；6. 語法：一組規(guī)章，用它可形成和產(chǎn)生一組合式的程序；7. 文法：描述語言的語法結(jié)構(gòu)的形式規(guī)章；8. 基本塊：指程序中一次序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最終一個語句；9. 語法制導翻譯：在語法分析過程中，依據(jù)每個產(chǎn)生式所對應的語義

17、子程序進行翻譯的方法叫做語法制導翻譯；10. 短語： 令 g是一個文法， s劃文法的開頭符號， 假定 是文法 g的一個句型， 假如有 s a 且 a，就稱 是句型 相對非終結(jié)符 a 的短語；11. 待用信息：假如在一個基本塊中，四元式i對 a 定值，四元式 j要引用 a 值，而從 i到 j之間沒有 a的其它定值，就稱j 是四元式 i 的變量 a 的待用信息；12. 規(guī)范句型：由規(guī)范推導所得到的句型；13. 掃描器：執(zhí)行詞法分析的程序；14. 超前搜尋：在詞法分析過程中，有時為了確定詞性，需超前掃描如干個字符；15. 句柄：一個句型的最左直接短語；16. 語法制導翻譯：在語法分析過程中，依據(jù)每個

18、產(chǎn)生式所對應的語義程序進行翻譯的方法叫做語法制導翻譯；17. 規(guī)范句型：由規(guī)范推導所得到的句型；18. 素短語：素短語是指這樣一個短語，至少含有一個終結(jié)符，并且，除它自身外不再含任何更小的素短語；19. 語法：是組規(guī)章，用它可形成和產(chǎn)生一個合式的程序；20. 待用信息：假如在一個基本塊中，四元式i對 a 定值，四元式 j要引用 a 值，而從 i到 j之間沒有 a的其它定值，就稱j 是四元式 i 的變量 a 的待用信息；21. 語義：定義程序的意義的一組規(guī)章；四、簡答題：1. 所求文法是 gs:sab |b a0aad |c b2 |4 |6 |8c1 |3 |5 |7 |9 |bd0 |c 2

19、. 輸出是 42313. 句子 baab的規(guī)范歸約過程：步驟符號棧輸入串動作0#baab#預備1#baab#移進2#baab#移進3#baab#移進4#baab#歸約5#bmabb#移進6#bmab#移進7#bbb#歸約8#bab#歸約9#bab#移進10#s#接受4. 傳地址 a=6, b=16nm傳值a=2, b=45.lg=da6. 證明：b |n 0, m 0由于文法 gs 存在句子 aa 有兩個不同的最左推導，所以文法gs 是是二義性的；s=sas=sasas=asas=aas=aa s=sas=as=asas=aas=aa7. 句子 adccd的分析過程：步驟0#s符號棧adccd

20、#輸入串產(chǎn)生式1#abadccd#sba2#aaaadccd#baa3#aadccd#4#addccd#ad5#accd#6#sbccd#abs7#scccd#bc8#scd#9#abcd#bc10#acd#11#ad#12#dd#ad13#8. 所求文法是 gs: s aba aac | ddbd | b babb | aabb9.函數(shù)a,f4244g552310. 優(yōu)化：對程序進行各種等價變換，使得從變換后的程序動身，能產(chǎn)生更有效的目標代碼；三種級別： 局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化11. 目標代碼通常采納三種形式：機器語言，匯編語言，待裝配機器語言模塊；應著重考慮的問題：(1) 如何使生成

21、的目標代碼較短；(2) 如何充分利用寄存器，以削減拜訪內(nèi)存次數(shù)；(3) 如何充分利用指令系統(tǒng)的特點；12. 正規(guī)式 a a | b *；13. 刪除余外運算，代碼外提，強度減弱，變換循環(huán)掌握條件，合并已知量，復寫傳播和刪除無用賦值；14. 文法 gs:s ab | ab bc |bbc15. 傳值a=2傳地址 a=1516. 逆波蘭式 : abcd-*e/+三元序列 :oparg1arg21-cd2*b13/2e4+a317. 證明：由于文法 gs 存在句子 有兩個不同的最左推導，所以文法gs 是是二義性的；*a=aa=aa=a= a=aa=a=a=18.ab|b a=a,b,ab,ba,aa

22、b,bba19. display表:嵌套層次顯示表由于過程嵌套答應內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當一個過程運行時必需跟蹤它的全部外層過程的最新活動記錄起始地址，display表就是用于登記每個外層過程的最新活動記錄起始地址；20. 傳地址 a=12傳值a=521. 所求文法是 gs:sacaaaabb | abcccc | cc22. 逆波蘭式三元序列abc+e*bc+f/+:=oparg1arg21+bc2*1e3+bc4/3f5+246:=a523. 一個文法 g別是 ll1 文法的充要條件是:(1) first first = (2) 假如 =* , first followa=

23、 24. 排除左遞歸safs | *afs s *afs | f+af | +a提公共左因子 , 文法 g s safs | *afs s *afs | f+aff f |25. 作用：登記源程序中顯現(xiàn)的各種名字及其信息，以及明白各階段的進展狀況；主要技術(shù)：線性表，對折查找，雜奏技術(shù)；五、運算題：1(1) 排除左遞，文法變?yōu)間s ：s | a | t tst | st ,st |此文法無左公共左因子；(2) 構(gòu)造相應的 first 和 follow集合： firsts=a, , ， follows=#, , firstt=a, , ， followt= firstt=, ， followf=(

24、3) 構(gòu)造猜測分析表：a,#ssasstttsttsttsttt t ,st2. 11cif e then scs2cif e then backe.tc, nxq; c.chain:=e.fc1scss.chain:=mergc.chain, s1. chain3. 1firstvts=a, firstvtt=+, aa, lastvts=a, lastvtt=+,a,2a+a.+.112124. 1 ffor i:=eto edo sfs12 ffor i:=eto edo2gen:=, e.place, _, entryi; f.place:=entryi; limit:=newtemp

25、;gen:=, e.place, _, limit; q:=nxq;f.quad:=q;genj, entryi, limit, q+2 f.chain:=nxq;genj, _, _, 01sfs1backpatchs .chain, nxq;gen+, f.place, 1, f.place;genj, _, _, f.quad;s.chain:=f.chain5.1 j, c,0, 54j, _, _, 85+, a,1, t16:=, t1, _, a7j, _, _, 18*, a,13, t29- , t2,1, t310 :=, t3, _, a11 j, _, _, 1126. 優(yōu)化后的四元序列d:=a-c e:=a*c f:=d*e m:=f+207. 最左推導