編譯原理復(fù)習(xí)題及參考答案

1、中南大學(xué)網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案編譯原理一、判斷題：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)成的。 ( )11.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 (

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

3、法是二義性的。 ( )二、填空題：1.( )稱為規(guī)范推導(dǎo)。2.編譯過程可分為 （ ） ，（ ），（ ），（ ）和（ ）五個階段。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.一個

4、名字的屬性包括( )和( )。12.常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個級別。14.語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。15.預(yù)測分析程序是使用一張（ ）和一個（ ）進行聯(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ī)則進行

5、的。20.一個句型的最左直接短語稱為句型的（ ）。21.一個文法G，若它的預(yù)測分析表M不含多重定義，則該文法是（ ）文法。22.對于數(shù)據(jù)空間的存貯分配， FORTRAN采用( )策略， PASCAL采用( )策略。23.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹， 則稱這個文法是( )。24.最右推導(dǎo)亦稱為（ ），由此得到的句型稱為（ ）句型。25.語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。26.對于文法G，僅含終結(jié)符號的句型稱為 ( )。27.所謂自上而下分析法是指（ ）。28.語法分析器的輸入是（ ），其輸出是（ ）。29.局限于基本塊范圍的優(yōu)化稱（ ）。3

6、0.預(yù)測分析程序是使用一張（ ）和一個（ ）進行聯(lián)合控制的。31.2型文法又稱為（ ）文法；3型文法又稱為（ ）文法。32.每條指令的執(zhí)行代價定義為（ ）。33.算符優(yōu)先分析法每次都是對（ ）進行歸約。三、名詞解釋：1.局部優(yōu)化2.二義性文法3.DISPLAY表4.詞法分析器5.最左推導(dǎo)6.語法7.文法8.基本塊9.語法制導(dǎo)翻譯10.短語11.待用信息12.規(guī)范句型13.掃描器14.超前搜索15.句柄16.語法制導(dǎo)翻譯17.規(guī)范句型18.素短語19.語法20.待用信息21.語義四、簡答題：1.寫一個文法G, 使其語言為 不以0開頭的偶數(shù)集。2.已知文法G(S)及相應(yīng)翻譯方案SaAb print

7、 “1”Sa print “2”AAS print “3”Ac print “4”輸入acab, 輸出是什么？3.已知文法G(S)SbAaA(B | aBAa)寫出句子b(aa)b的規(guī)范歸約過程。4.考慮下面的程序：procedure p(x, y, z)；beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2;P(A, A, B);Print A, B end.試問，若參數(shù)傳遞的方式分別采用傳位置和傳值時，程序執(zhí)行后輸出 A, B的值是什么? 5.文法G(S)SdABAaA| aBBb| 描述的語言是什么？6.證明文法G(S) SSaS| 是二義性的。7.已知文法G

8、(S) SBAABS| dBaA| bS | c的預(yù)測分析表如下 a b c d # SSBASBASBA AABSABSABSAd BBaA BbS Bc給出句子 adccd 的分析過程。8.寫一個文法G, 使其語言為 L(G)=albmclanbn| l=0, m=1, n=2 9.已知文法G(S):Sa| (T)TT,S|S的優(yōu)先關(guān)系表如下：關(guān)系a(),a-.(.=.,.請計算出該優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)表。10.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？11.目標代碼有哪幾種形式？生成目標代碼時通常應(yīng)考慮哪幾個問題？12.一字母表=a, b，試寫出上所有以a為首的字組成的正規(guī)集相

9、對應(yīng)的正規(guī)式。13.基本的優(yōu)化方法有哪幾種？14.寫一個文法G, 使其語言為 L(G)=abncn| n015.考慮下面的程序：procedure p(x, y, z);begin y:=y+z; z:=y*z+xend;begin a:=2; b:=3; p(a+b, b, a); print aend.試問，若參數(shù)傳遞的方式分別采用傳位置和傳值時，程序執(zhí)行后輸出 a的值是什么? 16.寫出表達式ab*(c-d)/e的逆波蘭式和三元序列。17.證明文法G(A)AAA | (A)| 是二義性的。18.令=a,b，則正規(guī)式a*b|b*a 表示的正規(guī)集是什么？19.何謂DISPLAY表？其作用是什

10、么？20.考慮下面的程序：procedure p(x, y, z)；beginy:=y+2;z:=z+x; end begina:=5;b:=2;p(a+b, a-b, a);print a end.試問，若參數(shù)傳遞的方式分別采用傳位置和傳值時，程序執(zhí)行后輸出 a的值是什么? 21.寫一個文法G, 使其語言為 L(G)=anbncm| n0為奇數(shù)， m0為偶數(shù)22.寫出表達式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。23.一個文法G別是LL(1)文法的充要條件是什么？24.已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左遞歸和提公共左因子。25.符號表的

11、作用是什么？符號表查找和整理技術(shù)有哪幾種？五、計算題：1.設(shè)文法G(S): S | a | (T) TT,S | S 消除左遞歸； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測分析表 2.語句 if E then S(1)改寫文法，使之適合語法制導(dǎo)翻譯； (2)寫出改寫后產(chǎn)生式的語義動作。 3.設(shè)文法G（S）：S(T) | aTT+S | S(1)計算FIRSTVT 和LASTVT； (2)構(gòu)造優(yōu)先關(guān)系表。 4.設(shè)某語言的for語句的形式為for i:E(1) to E(2) do S其語義解釋為i:E(1)LIMIT:E(2)again: if iLIMIT thenBeginS;i:

12、i1goto againEnd;（1）寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；（2）寫出每個產(chǎn)生式對應(yīng)的語義動作。5.把語句while a0 then a:=a+1else a:=a*3-1;翻譯成四元式序列。6.設(shè)有基本塊D:=A-CE:=A*CF:=D*ES:=2T:=A-C Q:=A*CG:=2*SJ:=T*QK:=G*5L:=K+JM:=L假設(shè)基本塊出口時只有M還被引用，請寫出優(yōu)化后的四元序列。7.已知文法G(S)Sa | | (T)TT,S | S(1) 給出句子(a,(a,a)的最左推導(dǎo)；(2) 給出句型(T,S),a)的短語, 直接短語，句柄。8.對于 C 語言do S while E語句

13、 (1)改寫文法，使之適合語法制導(dǎo)翻譯； (2)寫出改寫后產(chǎn)生式的語義動作。9.已知文法G(S) SaAcBe AAb| b Bd(1)給出句子abbcde的最左推導(dǎo)及畫出語法樹；(2)給出句型aAbcde的短語、素短語。 10.設(shè)文法G(S): S(T) | aS | a TT,S | S 消除左遞歸和提公共左因子； 構(gòu)造相應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測分析表。11.把語句 if X0 Y0 do X:=A*3 else Y:=B+3;翻譯成四元式序列。12.已知文法G(S) EE+T | T TT*F| F F(E)| i (1) 給出句型 (i+i)*i+i的最左推導(dǎo)及畫出

14、語法樹； (2) 給出句型 (E+T)*i+F 的短語，素短語和最左素短語。 13.設(shè)文法G（S）：ST | STTU |TUUi |-U（1）計算FIRSTVT 和LASTVT； （2）構(gòu)造優(yōu)先關(guān)系表。 7 / 14參考答案一、是非題：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)化），（目標代碼生成）3.(二義性的）4.(執(zhí)行性），（說明性）5.(單詞符號），（語法單位）。6.(源程序），（單詞符號

15、）7.(類型、種屬、所占單元大小、位置）8.(現(xiàn)行活動記錄位置和所有外層最新活動記錄的位置)9.(句柄）10.(棧式)，（堆式）11.(類型)，（作用域）12.(傳位置），（傳值），（傳名）13.(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）14.(自上而下），（自下而上）15.(分析表），（符號棧）16.(傳位置），（傳值），（傳名）17.(初），（終）18.(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）19.(語法），（語義）20.(句柄）21.(LL(1) 文法）22.(靜態(tài)），（動態(tài)）23.(二義性文法）24.(規(guī)范推導(dǎo)），（規(guī)范）25.(自上而下），（自下而上）26.(句子)27.(從開始符號出

16、發(fā)，向下推導(dǎo)，推出句子）28.(單詞符號），（語法單位）29.(局部優(yōu)化）30.(分析表），（符號棧）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ī)則

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

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

19、AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2.輸出是42313.句子b(aa)b的規(guī)范歸約過程：步驟符號棧輸入串動作0#b(aa)b#預(yù)備1#b(aa)b#移進2#b(aa)b#移進3 #b(a a)b# 移進4#b(Aa)b#歸約5 #b(Ma)b#移進6#b(Ma)b#移進7#b(B b# 歸約8#bAb#歸約9#bAb#移進10#S#接受4.傳位置 A=6, B=16傳值 A=2, B=45.L(G)=danbm |n0, m06.證明： 因為文法GS存在句子aa有兩個不同的最左推導(dǎo)，所以文法GS是是二義性的。S=SaS=SaSaS=aSaS=aaS=

20、aa S=SaS=aS=aSaS=aaS=aa7.句子 adccd 的分析過程：步驟符號棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#SBA2#AAaadccd#BaA3#AAdccd#4#Addccd#Ad5#Accd#6#SBccd#ABS7#Scccd# Bc8#S cd# 9#ABcd#Bc10#Acd#11#A d#12#dd#Ad13# 8.所求文法是GS: SAB AaAc | D DbD | bBaBb | aabb9.函數(shù)a(),f4244g552310.優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化

21、11.目標代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。應(yīng)著重考慮的問題： (1)如何使生成的目標代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點。12.正規(guī)式 a ( a | b )*。13.刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播和刪除無用賦值。14.文法GS:SaB | a Bbc |bBc15.傳值 a=2 傳位置 a=1516.逆波蘭式: abcd-*e/+三元序列: op arg1 arg2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3)17.證明：因

22、為文法GS存在句子 () 有兩個不同的最左推導(dǎo)，所以文法GS是是二義性的。A=AA=(A)A=()A=() A=AA=A=(A)=()18.(a*b|b*a)=a,b,ab,ba,aab,bba19.Display表: 嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當(dāng)一個過程運行時必須跟蹤它的所有外層過程的最新活動記錄起始位置， display表就是用于登記每個外層過程的最新活動記錄起始位置。20.傳位置 a=12傳值 a=521.所求文法是GS: SAC AaaAbb | ab CccC | cc22.逆波蘭式 abc+e*bc+f/+:=三元序列 op arg1 ar

23、g2 (1) + b c (2) * (1) e (3) + b c (4) / (3) f (5) + (2) (4) (6) := a (5) 23.一個文法G別是LL(1)文法的充要條件是: (1) FIRST() FIRST()= (2) 如果 =*, FIRST() FOLLOW(A)= 24.消除左遞歸SaFS | *aFSS*aFS | F+aF | +a提公共左因子,文法 G(S) SaFS | *aFSS*aFS | F+aFFF |25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進展狀況。主要技術(shù)：線性表，對折查找，雜奏技術(shù)。五、計算題：1.(1)消除左遞，

24、文法變?yōu)镚S：S | a | (T)TST | ST,ST |此文法無左公共左因子。(2)構(gòu)造相應(yīng)的FIRST和FOLLOW集合： FIRST(S)=a, , (， FOLLOW(S)=#, , )FIRST(T)=a, , ( ，F(xiàn)OLLOW(T)=FIRST(T)=, ，F(xiàn)OLLOW(F)=)(3)構(gòu)造預(yù)測分析表：a(),#SSaSS(T)TTSTTSTTSTTTT,ST2. (1)Cif E thenSCS(1) (2) Cif E then BACK(E.TC, NXQ); C.chain:=E.FC SCS(1) S.chain:=MERG(C.Chain, S(1). Chain)

25、3. (1) FIRSTVT(S)=a, ( FIRSTVT(T)=+, aa, ( LASTVT(S)=a, ) LASTVT(T)=+, a, ) (2) a + ( ) a . .+ ( . . . .4. (1) Ffor i:=E(1) to E(2) do SFS(1)(2) Ffor i:=E(1) to E(2) doGEN(:=, E(1).place, _, entry(i);F.place:=entry(i);LIMIT:=Newtemp;GEN(:=, E(2).place, _, LIMIT);Q:=NXQ;F.QUAD:=q;GEN(j, entry(i), LIM

26、IT, q+2)F.chain:=NXQ;GEN(j, _, _, 0)SFS(1)BACKPATCH(S(1).chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain5. (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)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,S a直接短語 T,S a句柄 T,S8.(1)Sdo M1 S1 while M2 EM (2)M M.quad=nestquad;Sdo M1 S1 while M2 E backpa