編譯原理期末考試試卷試題及答案

1、得分一 填空題（每空2分，共20分）1. 不同的編譯程序關于數(shù)據(jù)空間的存儲分配策略可能不同，但大部分編譯中采用的方案有兩種：靜態(tài)存儲分配方案和動態(tài)存儲分配方案，而后者又分為（1） 和 （2） 。2. 規(guī)范規(guī)約是最（3）規(guī)約。3. 編譯程序的工作過程一般劃分為5個階段：詞法分析、（4） 、語義分析與中間代碼生成，代碼優(yōu)化及（5） 。另外還有（6）和出錯處理。4表達式x+y*z/(a+b)的后綴式為 （7） 。5文法符號的屬性有綜合屬性和 （8）。6假設二位數(shù)組按行存放，而且每個元素占用一個存儲單元，則數(shù)組a1.15,1.20某個元素ai，j的地址計算公式為（9）。7局部優(yōu)化是局限于一個（10）范

2、圍內(nèi)的一種優(yōu)化。得分二 選擇題（1-6為單選題，7-8為多選題，每問2分，共20分）1. 一個上下文無關文法G包括四個組成部分：一組終結符，一組非終結符，一個（ ），以及一組（ ）。A 字符串 B 產(chǎn)生式 C 開始符號 D 文法2.程序的基本塊是指（ ）。A 一個子程序 B 一個僅有一個入口和一個出口的語句C 一個沒有嵌套的程序段 D 一組順序執(zhí)行的程序段，僅有一個入口和一個出口3. 高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ ）分析方法。A 自左向右 B 自頂向下 C 自底向上 D 自右向左4在通常的語法分析方法中，（ ）特別適用于表達式的分析。A 算符優(yōu)先分析法 B LR分

3、析法C 遞歸下降分析法 D LL（1）分析法5經(jīng)過編譯所得到的目標程序是（ ）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機器語言程序或匯編語言程序6 一個文法所描述的語言是（ ）；描述一個語言的文法是（ ）。A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一7 如果在文法G中存在一個句子，當其滿足下列條件（ ）之一時，則稱該文法是二義文法。A 其最左推導和最右推導相同 B 該句子有兩個不同的最左推導C 該句子有兩個不同的最右推導 D 該句子有兩棵不同的語法樹E 該句子對應的語法樹唯一8 下面（ ）語法制導翻譯中，采用拉鏈回填技術。A. 賦值語句 B. 布爾表達式的計算 C. 條

4、件語句 D. 循環(huán)語句得分三 解答題（共60分）1 （共15分）已知文法GE: EETE|（E）|i T*|+（1） 將文法G改造成LL（1）文法；（5分）（2） 構造文法G中每個非終結符的FIRST集合及FOLLOW集合；（5分）（3） 構造LL（1）分析表。（5分）2 （共12分）給定文法GS：SS(S)|（1） 給出句子()()()()的規(guī)范推導過程；（4分）（2） 指出每步推導所得句型的句柄；（4分）（3） 畫出該句子的語法推導樹。（4分）3 （共8分）在一個移入-規(guī)約分析過程中采用以下的語法制導翻譯模式，在按一個產(chǎn)生式規(guī)約時，立即執(zhí)行括號中的動作。 AaB print “0”； Ac

5、 print “1”； BAb print “2”；（1） 當分析器的輸入為aacbb時，打印的字符串是什么（3分）（2） 寫出分析過程。（5分）5 （共15分）設有表格構造文法GS： Sa|(T) TT,S|S(1) 計算文法GS的FIRSTVT集和LASTVT集。（5分）(2) 構造GS的優(yōu)先關系表，并判斷GS是否為算符優(yōu)先文法。（5分）(3) 計算GS的優(yōu)先函數(shù)。（5分）得分二 單項選擇題（每題2分，共10分）1. 設有文法GI： II1|I0|Ia|Ic|a|b|c下列符號串中是該文法句子的有（ ）。 ab0 a0c01 aaa bc10可選項有：A B C D2.程序的基本塊是指（

6、）。A 一個子程序 B 一個僅有一個入口和一個出口的語句C 一個沒有嵌套的程序段 D 一組順序執(zhí)行的程序段，僅有一個入口和一個出口3. 高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（ ）分析方法。A 自左向右 B 自頂向下 C 自底向上 D 自右向左4經(jīng)過編譯所得到的目標程序是（ ）。A 四元式序列 B 間接三元式序列C 二元式序列 D 機器語言程序或匯編語言程序5 運行階段的存儲組織與管理的目的是（ ）。 提高編譯程序的運行速度 節(jié)省編譯程序的存儲空間 提高目標程序的運行速度 為運行階段的存儲分配做準備可選項有：A. B. C. D. 得分2. （10分） 已知文法GS: SaB

7、c|bABAaAb|bBb|（4） 構造其LL（1）分析表；（5） 判斷符號串baabbb是否為該文法的句子（寫出含有符號棧、輸入串和規(guī)則的分析過程）。答案：(1) 棧式動態(tài)存儲分配(2) 堆式動態(tài)存儲分配(3) 左(4) 語法分析(5) 目標代碼生成(6) 表格管理(7) xyz*ab+/+(8) 繼承屬性(9) a+(i-1)*20+j-1(10) 基本塊一、 選擇題（每問2分，共20分）1.C B 2.D 3.B 4.A 5.D 6.A,C7.BCD,選對一個得1分且不超過滿分，選錯一個扣一分，扣完為止。8.BCD，選對一個得1分且不超過滿分，選錯一個扣一分，扣完為止。二、 解答題1（1

8、）文法存在左遞歸，消除左遞歸后的文法為：E(E)E|i E（2分）ETEE| （2分）T*|+ （1分）（2）(5分)沒考慮#扣0.5分，其它錯或少寫一個扣0.5分FIRST(E)=(,i FIRST(E)=*,+, FIRST(T)=*,+ FOLLOW(E)=),*,+,# FOWLLOW(E)= ),*,+,# FOLLOW(T)=(,i（3）每錯一個扣0.5分，全錯或不寫不得分，扣完為止，共5分()i*+#EE(E)EEiEEE ETEEE ETEEE E TT*T+2（1）規(guī)范推導過程如下。寫錯推導符號扣0.5分,錯寫或少寫一步推導扣0.5分，扣完為止，最左推導扣2分，共4分。（2）

9、（1）中加下劃線的部分是句柄，標識如（1）。每少寫一個句柄扣0.5分，扣完為止，共4分。（3）每少寫步扣0.5分，扣完為止，共4分。SS ( S )S ( S ) ) )S ( S ) )S ( S ) ) S ( S ) )3（1）打印的字符串是：12020（錯一個扣0.5分，共3分）（2）歸約過程中錯一步扣0.5分，扣完為止。（共5分）5（1）少寫一個扣1分，全錯或不寫不得分，共5分。FIRSTVT(S)=a,(FIRSTVT(T)=, a,(LASTVT(S)= a,)LASTVT(T)= a,), ,三、 單項選擇題（每題2分，共10分）1.B 2.D 3.B 4.D 5.C四、 解答

10、題（共70分）1（1） L(G)=0m1m|M1 共2分，寫成扣1分（2） S=>0S1=>00S11=>000111，共3分， =>寫成->扣1分（3） 共3分，錯處扣0.5分，扣完為止一、判斷題：1.一個上下文無關文法的開始符，可以是終結符或非終結符。 ( )2.一個句型的直接短語是唯一的。 ( )3.已經(jīng)證明文法的二義性是可判定的。 （ ）4.每個基本塊可用一個DAG表示。 （ ）5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。 （ ）6.2型文法一定是3型文法。 （ ）7.一個句型一定句子。 ( )8.算符優(yōu)先分析法每次都是對句柄進行歸約。 ( )9.采用

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

12、文法來描述。 ( )20.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22.如果一個文法存在某個句子對應兩棵不同的語法樹，則文法是二義性的。 ( )二、填空題：1.( )稱為規(guī)范推導。2.編譯過程可分為 （ ） ，（ ），（ ），（ ）和（ ）五個階段。3.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（ ）。 4.從功能上說，程序語言的語句大體可分為（ ）語句和（ ）語句兩大類。5.語法分析器的輸入是（ ），其輸出是（ ）。6.掃描器的任務是從（ ）中識別出一個個（ ）。7.符號表中的信息欄中登記了每個名字的有關的性質(zhì)，如（ ）等等。8.一個

13、過程相應的DISPLAY表的內(nèi)容為（ ）。9.一個句型的最左直接短語稱為句型的（ ）。10.常用的兩種動態(tài)存貯分配辦法是（ ）動態(tài)分配和（ ）動態(tài)分配。11.一個名字的屬性包括( )和( )。12.常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（ ），（ ）和（ ）三個級別。14.語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。15.預測分析程序是使用一張（ ）和一個（ ）進行聯(lián)合控制的。16.常用的參數(shù)傳遞方式有（ ），（ ）和（ ）。17.一張轉換圖只包含有限個狀態(tài),其中有一個被認為是（ ）態(tài);而且實際上至少要有一個（ ）

14、態(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.如果一個文法存在某個句子對應兩棵不同的語法樹， 則稱這個文法是( )。24.最右推導亦稱為（ ），由此得到的句型稱為（ ）句型。25.語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。26.對于文

15、法G，僅含終結符號的句型稱為 ( )。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.基本塊9.語法制導翻譯10.短語11.待用信息12.規(guī)范句型13.掃描器14.超前搜索15.句柄16.語法制導翻譯17.規(guī)范句型

16、18.素短語19.語法20.待用信息21.語義四、簡答題：1.寫一個文法G, 使其語言為 不以0開頭的偶數(shù)集。2.已知文法G(S)及相應翻譯方案SaAb print “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ù)傳遞的方式分別采

17、用傳地址和傳值時，程序執(zhí)行后輸出 A, B的值是什么 5.文法G(S)SdABAaA| aBBb| 描述的語言是什么？6.證明文法G(S) SSaS| 是二義性的。7.已知文法G(S) SBAABS| dBaA| bS | c的預測分析表如下 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)先關系表如下：關系a(),a.>.>(<.&

18、lt;.=.<.)-.>.>,<.<.>.>請計算出該優(yōu)先關系表所對應的優(yōu)先函數(shù)表。10.何謂優(yōu)化按所涉及的程序范圍可分為哪幾級優(yōu)化11.目標代碼有哪幾種形式生成目標代碼時通常應考慮哪幾個問題12.一字母表=a, b，試寫出上所有以a為首的字組成的正規(guī)集相對應的正規(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 ae

19、nd.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a的值是什么 16.寫出表達式ab*(c-d)/e的逆波蘭式和三元序列。17.證明文法G(A) AAA | (A)| 是二義性的。25.符號表的作用是什么符號表查找和整理技術有哪幾種五、計算題：1.設文法G(S): S | a | (T) TT,S | S 消除左遞歸； 構造相應的FIRST和FOLLOW集合； 構造預測分析表 3.設文法G（S）：S(T) | aTT+S | S(1）計算FIRSTVT 和LASTVT； （2）構造優(yōu)先關系表。 7.已知文法G(S)Sa | | (T)TT,S | S(1) 給出句子(a,(a

20、,a)的最左推導；(2) 給出句型(T,S),a)的短語, 直接短語，句柄。9.已知文法G(S) SaAcBe AAb| b Bd(1)給出句子abbcde的最左推導及畫出語法樹；(2)給出句型aAbcde的短語、素短語。 10.設文法G(S): S(T) | aS | a TT,S | S 消除左遞歸和提公共左因子； 構造相應的FIRST和FOLLOW集合； 構造預測分析表。參考答案一、是非題：1.× 2.× 3.× 4. 5. 6.× 7.× 8.× 9. 10.× 11.×12. 13.× 14.

21、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)化），（循環(huán)優(yōu)化），（全局優(yōu)化）14.(自上而下），（自下而上）15.(分析表），（符號棧）16.(傳

22、地址），（傳值），（傳名）17.(初），（終）18.(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）19.(語法），（語義）20.(句柄）21.(LL(1) 文法）22.(靜態(tài)），（動態(tài)）23.(二義性文法）24.(規(guī)范推導），（規(guī)范）25.(自上而下），（自下而上）26.(句子)27.(從開始符號出發(fā)，向下推導，推出句子）28.(單詞符號），（語法單位）29.(局部優(yōu)化）30.(分析表），（符號棧）31.(上下文無關文法），（正規(guī)）32.(指令訪問主存次數(shù)加1）33.(最左素短語）三、名詞解釋題： 1.局部優(yōu)化-局限于基本塊范圍的優(yōu)化稱。2.二義性文法-如果一個文法存在某個句子對應兩棵不同的語法樹，

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

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

25、何更小的素短語。19.語法-是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。 20.待用信息-如果在一個基本塊中，四元式i對A定值，四元式j要引用A值，而從i到j之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。21.語義-定義程序的意義的一組規(guī)則。四、簡答題： 1.所求文法是GS:SAB |B A0AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2.輸出是42313.句子b(aa)b的規(guī)范歸約過程：步驟符號棧輸入串動作0#b(aa)b#預備1#b(aa)b#移進2#b(aa)b#移進3 #b(a a)b# 移進4#b(Aa)b#歸約5 #b(Ma)b#移進6#

26、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 |n>0, m06.證明： 因為文法GS存在句子aa有兩個不同的最左推導，所以文法GS是是二義性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=>aS=>aSaS=>aaS=>aa7.句子 adccd 的分析過程：步驟符號棧輸入串產(chǎn)生式0#Sadccd#1#ABadccd#SBA2#AAaadccd#BaA3#AAdccd#4#Addccd

27、#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)化11.目標代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。應著重考慮的問題： (1)如何使生成的目標代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點。12

28、.正規(guī)式 a ( a | b )*。13.刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復寫傳播和刪除無用賦值。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.證明：因為文法GS存在句子 () 有兩個不同的最左推導，所以文法GS是是二義性的。A=>AA=>(A)A=>()A=>() A=>AA=>A=>(A)=>()25.作用

29、：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進展狀況。主要技術：線性表，對折查找，雜奏技術。五、計算題：1.(1)消除左遞，文法變?yōu)镚S：S | a | (T)'TST | ST,ST |此文法無左公共左因子。(2)構造相應的FIRST和FOLLOW集合： FIRST(S)=a, , (， FOLLOW(S)=#, , )FIRST(T)=a, , ( ，F(xiàn)OLLOW(T)=FIRST(T)=, ，F(xiàn)OLLOW(F)=)(3)構造預測分析表：a(),#SSaSS(T)'TTSTTSTTSTTTT,ST2. (1)Cif E thenSCS(1) (2) Cif E t

30、hen BACK(E.TC, NXQ); C.chain:=E.FC SCS(1) S.chain:=MERG(C.Chain, S(1). Chain)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, _,