編譯原理期末試題(8套含答案+大題集)_2(共51頁)

1、PAGE 第 PAGE 58頁共6頁編譯(biny)原理期末試題（一）一、是非題（請在括號內(nèi)，正確(zhngqu)的劃，錯誤的劃）（每個2分，共20分）1編譯程序是對高級語言(yyn)程序的解釋執(zhí)行。( )2一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。()3一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 ( )4語法分析時必須先消除文法中的左遞歸 。 ()5LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。 ()6逆波蘭表示法表示表達式時無須使用括號。 ( )7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 ()8進行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將

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

3、是_。A( ) xyx B( ) (xyx)* C( ) xnyxn(n0) D( ) x*yx* 4如果(rgu)文法G是無二義的，則它的任何句子_。A( )最左推導(dǎo)(tudo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 B( ) 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法(yf)樹可能不同 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表達式(AB)(

4、CD)的逆波蘭表示為_。A. ( ) ABCD B( ) ABCD C( ) ABCD D( ) ABCD 8. 優(yōu)化可生成_的目標(biāo)代碼。A( ) 運行時間較短 B( ) 占用存儲空間較小C( ) 運行時間短但占用內(nèi)存空間大 D( ) 運行時間短且占用存儲空間小9下列_優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A. ( ) 強度削弱 B( ) 刪除歸納變量 C( ) 刪除多余運算 D( ) 代碼外提10編譯程序使用_區(qū)別標(biāo)識符的作用域。 A. ( ) 說明(shumng)標(biāo)識符的過程或函數(shù)名B( ) 說明標(biāo)識符的過程(guchng)或函數(shù)的靜態(tài)層次C( ) 說明標(biāo)識符的過程或函數(shù)(hnsh)的動態(tài)層次

5、D. ( ) 標(biāo)識符的行號三、填空題(每空1分，共10分)1計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析器_，它接受輸入的_源程序_，對源程序進行_詞法分析_并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。3自上而下分析法采用_移進_、歸約、錯誤處理、_接受_等四種操作。4一個LR分析器包括兩部分：一個總控程序和_一張分析表_。5后綴式abc-/所代表的表達式是_a/(b-c)_。 四、簡答題（20分）1. 簡要說明語義分析的基本功能。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2. 考慮文法 GS

6、: S (T) | a+S | a T T,S | S 消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 3. 試為表達式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)(xingyng)的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +4. 按照三種基本(jbn)控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while (AC BD) if (A 1) C=C+1;else while (A D)A=A+2;。解：該語句的四元式

7、序列如下(其中(qzhng)E1、E2和E3分別對應(yīng)ACBD、A1和AD，并且關(guān)系運算符優(yōu)先級高)： 100 (j,A,C,102) 101 (j,_,_,113) 102 (jaAd|aAb| 判斷該文法是否是 SLR(1) 文法，若是構(gòu)造相應(yīng)(xingyng)分析表，并對輸入串 ab# 給出分析過程。解：增加一個非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有： S-A A-aAd|aAb| 下面構(gòu)造它的LR(0)項目集規(guī)范族為： 從上表可看出,狀態(tài)I0和I2存在移進-歸約沖突，該文法不是LR(0)文法。對于I0來說有：FOLLOW(A)a=b,d,#a=，所以在I0狀態(tài)下面臨輸入符號為a時移進，為

8、b,d,#時歸約，為其他時報錯。對于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移進-歸約沖突是可以解決的，因此該文法是SLR(1)文法。 其SLR(1)分析表為： 對輸入串a(chǎn)b#給出分析過程為： 編譯原理期末(q m)試題（二）一、是非題：1.一個上下文無關(guān)(wgun)文法的開始符，可以是終結(jié)符或非終結(jié)符。 ( )2.一個句型的直接短語(duny)是唯一的。 （ ）3.已經(jīng)證明文法的二義性是可判定的。 （ ）4.每個基本塊可用一個DAG表示。 （ ）5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。 （ ）6.2型文法一定是3型文法。 （ ）7.一個句型一定句子。 ( )8.算符優(yōu)先分

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

10、。 ( )19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ( )20.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則文法是二義性的。 ( )答案(d n)：1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.二、填空題：2.編譯(biny)過程可分為 （ 詞法(cf)分析） ，（語法分析），（語義分析與中間代碼生成 ），（優(yōu)化）和（目標(biāo)代碼生成 ）五個階段。3.如果一個文法存在某個句子對應(yīng)兩棵不同的

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

12、（傳值），（傳名）13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個級別。14.語法分析的方法大致可分為兩類，一類是（ 自上而下 ）分析法，另一類是（ 自下而上 ）分析法。15.預(yù)測分析程序是使用一張（ 分析表 ）和一個（ 符號棧 ）進行聯(lián)合控制的。17.一張轉(zhuǎn)換圖只包含有限個狀態(tài),其中有一個被認(rèn)為是（初）態(tài);而且實際上至少要有一個（終 ）態(tài)。19.語法分析是依據(jù)語言的（語法 ）規(guī)則進行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進行的。21.一個文法G，若它的預(yù)測分析表M不含多重定義，則該文法是（LL(1) 文法）文法。22.對于數(shù)據(jù)空間的存貯分配， FOR

13、TRAN采用( 靜態(tài)策略， PASCAL采用( 動態(tài))策略。24.最右推導(dǎo)亦稱為（規(guī)范推導(dǎo)），由此得到的句型稱為（規(guī)范）句型。26.對于文法G，僅含終結(jié)符號的句型稱為 ( 句子 )。27.所謂自上而下分析法是指(從開始符號出發(fā)，向下推導(dǎo)，推出句子）29.局限于基本塊范圍的優(yōu)化稱（ 局部優(yōu)化 ）。31.2型文法又稱為（上下文無關(guān)）文法；3型文法又稱為（正則 ）文法。32.每條指令的執(zhí)行代價定義為(指令訪問主存次數(shù)加1）33.算符優(yōu)先分析法每次都是對(最左素短語）進行歸約。四、簡答題：1.寫一個文法G, 使其語言為 不以0開頭的偶數(shù)集。2.已知文法G(S)及相應(yīng)翻譯方案SaAb print “1”

14、Sa print “2”AAS print “3”Ac print “4”輸入acab, 輸出是什么？3. 已知文法G(S)SbAaA(B | aBAa)寫出句子b(aa)b的規(guī)范(gufn)歸約過程。4. 考慮(kol)下面的程序：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.試問(shwn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 A, B的值是什么? 看著也熟悉5文法G(S)SdABAaA| aBBb| 描述的語言是什么？6. 證明文法G(S)

15、 SSaS| 是二義性的。7. 已知文法G(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)系(gun x)表所對應(yīng)的優(yōu)先函數(shù)表。10. 何謂(hwi)優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？11. 目標(biāo)代碼有哪幾種形式？生成(shn chn)目標(biāo)

16、代碼時通常應(yīng)考慮哪幾個問題？12. 一字母表=a, b，試寫出上所有以a為首的字組成的正規(guī)集相對應(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)| 是二義性的

17、。18.令=a,b，則正規(guī)式a*b|b*a 表示的正規(guī)集是什么？19.何謂DISPLAY表？其作用是什么？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.已知

18、文法GSSS*aF | aF | *aFF+aF | +a消除文法左遞歸和提公共(gnggng)左因子。25.符號表的作用是什么？符號表查找和整理(zhngl)技術(shù)有哪幾種？答案(d n)：1.所求文法是GS:SAB |B A0AAD |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

19、#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=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.所求文法(

20、wnf)是GS: SAB AaAc | D DbD | bBaBb | aabb9.函數(shù)a(),f4244g552310.優(yōu)化：對程序(chngx)進行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級別：局部優(yōu)化、循環(huán)(xnhun)優(yōu)化、全局優(yōu)化11.目標(biāo)代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。應(yīng)著重考慮的問題： (1)如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點。12.正規(guī)式 a ( a | b )*。13.刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播和刪除無用賦

21、值。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存在句子 () 有兩個不同的最左推導(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)一個過程運行時必須跟蹤(gnzng)它的所有

22、外層過程的最新活動記錄起始地址， display表就是用于登記每個外層過程的最新活動(hu dng)記錄起始地址。20.傳地址(dzh) a=12傳值 a=521.所求文法是GS: SAC AaaAbb | ab CccC | cc22.逆波蘭式 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別是LL(1)文法的充要條件是: (1) FIRST() FIRST()= (2) 如果 =*, FIRST() FOLLOW(A

23、)= 24.消除左遞歸SaFS | *aFSS*aFS | F+aF | +a提公共左因子,文法 G(S) SaFS | *aFSS*aFS | F+aFFF |25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進展?fàn)顩r。主要技術(shù)：線性表，對折查找，雜奏技術(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）計算FI

24、RSTVT 和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:i1goto againEnd;（1）寫出適合語法制導(dǎo)翻譯(fny)的產(chǎn)生式；（2）寫出每個產(chǎn)生(chnshng)式對應(yīng)的語義動作。5.把語句(yj)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

25、+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語句 (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)造相

26、應(yīng)的FIRST和FOLLOW集合； 構(gòu)造預(yù)測分析表。11.把語句 if X0 Y0 do X:=A*3 else Y:=B+3;翻譯成四元(s yun)式序列(xli)。12.已知文法(wnf)G(S) EE+T | T TT*F| F F(E)| i (1) 給出句型 (i+i)*i+i的最左推導(dǎo)及畫出語法樹； (2) 給出句型 (E+T)*i+F 的短語，素短語和最左素短語。 13.設(shè)文法G（S）：ST | STTU |TUUi |-U（1）計算FIRSTVT 和LASTVT； （2）構(gòu)造優(yōu)先關(guān)系表。 答案(d n)：(1)消除(xioch)左遞，文法變?yōu)镚S：S | a | (T)TST

27、 | ST,ST |此文法無左公共(gnggng)左因子。(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)3. (1) FIRSTV

28、T(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)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), LIMIT, q+2)F.chain:=

29、NXQ;GEN(j, _, _, 0)SFS(1)BACKPATCH(S(1).chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain(1) (j, c, 0, (5)(j, _, _, (8)(+, a, 1, T1)(:=, T1, _, a)(j, _, _, (1)(*, a, 13, T2)(-, T2, 1, T3)(:=, T3, _, a)(j, _, _, (1)6.優(yōu)化后的四元(s yun)序列D:=A-CE:=A*CF:=D*EM:=F+207. 最左推導(dǎo)(tudo)

30、S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)短語(duny) (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 backpatch(s1.nextlist, M2.quad); backpatch(E.truelist, M1.quad); S.nextlist=E.falelist; 9.(1) S=aAcBe=AAbcBe=abb

31、cBe=abbcde(2) 短語: aAbcde, Ab, d 素短語: Ab, d10.(1) S (L) | aS SS | LSL L,SL |(2) FIRST(S)=a, ( FIRST(S)=a, (, FIRST(L)=a, ( FIRST(L)=, FOLLOW(S)=, ), # FOLLOW(S)=, ), #FOLLOW(L)= ) FOLLOW(L)= )(3) ( ) a , # SS (L)S aSSSSSSSSSLLSLLSLL,SL LL11.(1) (j, X, 0, (5)(2) (j, _, _, (3)(3) (j0, X, 0, (7)(6) (j,

32、_, _, (7)(7) (*, A, 3, T1)(8) (:=, T1, _, N)(9) (j, _, _, (5)(10) (j, _, _, (13)(11) (+, B, 3, T2)(12) (:=, T2, _, Y)12.(1) E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+T =(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T =(i+i)*i+F=(i+i)*i+i (2) 短語(duny) i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短語(

33、duny) i, E+T最左素短語(duny) E+T13.(1) FIRSTVT(S)=, , i, - FIRSTVT(T)=, i, - FIRSTVT(U)=i, - LASTVT(S)=, , i, - LASTVT(T)=, i, - LASTVT(U)=i, -(2) i - S . . . . . . - . (=,#=(2) 是算符優(yōu)先文法，因為任何兩個終結(jié)符之間至多只有一種優(yōu)先關(guān)系。（2分）(3) 給出輸入串(a,a)#的算符優(yōu)先分析過程。步驟 棧當(dāng)前輸入字符剩余輸入串動作1#(a,a#( 移進2#(a,a)#(, 歸約4#(N,a)#(, 移進5#(N,a)#,) 歸約7

34、#(N,N）#,) 歸約8#(N)#(=) 移進9#(N)#)# 歸約10#N#接受編譯原理期末(q m)試題（四）簡述編譯程序的工作(gngzu)過程。（10）編譯程序的工作過程，是指從輸入源程序開始(kish)到輸出目標(biāo)程序為止的整個過程，是非常復(fù)雜的，就其過程而言，一般可以劃分為五個工作階段：詞法分析，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個的單詞；語法分析，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位；語義分析與中間代碼產(chǎn)生，即對各類語法單位，分析其漢一并進行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更高效的代碼；目標(biāo)代碼生成，把中間代碼變換成特定機器上的低級語言指令形式。二、構(gòu)造下列

35、正規(guī)式相應(yīng)的DFA（用狀態(tài)轉(zhuǎn)換圖表示）（15）1（0 | 1）*10,10*10*10*10*1letter（letter | digit）*31021（1）0051（2）104130211letter(3)2letter1digit三、給出下面語言(yyn)的相應(yīng)文法：（15）L1=an bn | n1 L2=anbm+nam | n1，m0 G1： SAB AaAb | ab BbBa | G1： AaAb |ab 四、對下面(xi mian)的文法G： Sa | b | （T）TT，S | S(1) 消去文法(wnf)的左遞歸，得到等價的文法G2；(2) 判斷文法G2是否LL（1）文法，

36、如果是，給出其預(yù)測分析表。（15）G2： Sa | b | （T） T ST T，S T | G2是LL（1）文法。ab（），#SSa Sb S（T）TT STT STT STTT T，S T 五、設(shè)有文法GA：ABCc | gDBBbCDE |CDaB | caDdD |EgAf | c計算該文法的每一個非終結(jié)符的FIRST集和FOLLOW集；試判斷該文法是否為LL（1）文法。（15）FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g是LL（1）文法(wnf)。六、對表達式文法(wnf)G：E E+T | TT T*F | FF (E)

37、| I（1）造各非終結(jié)符的FIRSTVT和LASTVT集合(jh)；（2）構(gòu)造文法的算符優(yōu)先關(guān)系表。（15）FIRSTVTLASTVTETF*，+，（，i*，（，i（，i*，+，），i*，），i），i 算符優(yōu)先關(guān)系表+*I（）#+*I（）#=七、有定義二進制整數(shù)的文法如下：L LB | BB 0 | 1構(gòu)造一個翻譯模式，計算該二進制數(shù)的值（十進制的值）。（15）引入L、B的綜合屬性val，翻譯模式為： S L print(L.val)L L1B L.val= L1.val*2+B.valL B L.val= B.valB 0 B.val=0B 1 B.val=1編譯原理(yunl)期末試題（五

38、）一、單項選擇題(共10小題(xio t)，每小題2分，共20分)1語言(yyn)是A句子的集合 B產(chǎn)生式的集合 C符號串的集合 D句型的集合2編譯程序前三個階段完成的工作是A詞法分析、語法分析和代碼優(yōu)化 B代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語法分析、語義分析和中間代碼生成 D詞法分析、語法分析和代碼優(yōu)化3一個句型中稱為句柄的是該句型的最左 A非終結(jié)符號 B短語 C句子 D直接短語4下推自動機識別的語言是A0型語言 B1型語言 C2型語言 D3型語言5掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即 A 字符 B單詞 C句子 D句型6對應(yīng)Chomsky四

39、種文法的四種語言之間的關(guān)系是 AL0L1L2L3 BL3L2L1L0 CL3=L2L1L0 DL0L1L2=L37詞法分析的任務(wù)是 A識別單詞 B分析句子的含義 C識別句子 D生成目標(biāo)代碼8常用的中間代碼形式不含 A三元式 B四元式 C逆波蘭式 D語法樹9 代碼優(yōu)化的目的是 A節(jié)省時間 B節(jié)省空間 C節(jié)省時間和空間 D把編譯程序進行等價交換10代碼生成階段的主要(zhyo)任務(wù)是 A把高級語言(yyn)翻譯成匯編語言 B把高級(goj)語言翻譯成機器語言 C把中間代碼變換成依賴具體機器的目標(biāo)代碼 D把匯編語言翻譯成機器語言二、填空題（本大題共5小題，每小題2分，共10分）1編譯程序首先要識別出

40、源程序中每個(單詞)，然后再分析每個(句子)并翻譯其意義。 2編譯器常用的語法分析方法有(自底向上)和(自頂向下)兩種。3通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的(綜合)。4程序設(shè)計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動態(tài)存儲分配)方案。5對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目標(biāo)程序)。三、名詞解釋題(共5小題，每小題4分，共20分)1詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構(gòu)成源程序的字符串中識別

41、出一個個具有獨立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。2LL(1)文法 若文法的任何兩個產(chǎn)生式A | 都滿足下面兩個條件：（1）FIRST( ) FIRST( ) = ；（2）若 * ，那么FIRST( ) FOLLOW( A ) = 。 我們把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個L代表從左向右掃描輸入，第二個L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語法樹 句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。給定文法G=(

42、VN，VT，P，S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點的標(biāo)記是開始符號S。(2)每個節(jié)點的標(biāo)記都是V中的一個符號。(3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標(biāo)記從左向右的排列次序為A1A2AR，那么AA1A2AR一定是P中的一條產(chǎn)生式。(4)若一標(biāo)記為A的節(jié)點至少有一個(y )除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點(ji din)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號(fho)，則w為文法G所產(chǎn)生的句子。4LR(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根

43、據(jù)分析棧當(dāng)前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動作 (是移進還是按某一產(chǎn)生式進行歸約等)。5語言和文法文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：G=(VN，VT，P，S)其中：VN 是非空有窮集合，稱為非終結(jié)符號集合；VT 是非空有窮集合，稱為終結(jié)符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。這里，VNVT=，SVN。V=VNVT，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法G所描述的語言用L(G)

44、表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)=x| S*x，其中S為文法開始符號，且 簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題(共4小題，每小題5分，共20分)1編譯程序和高級語言有什么區(qū)別? 用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標(biāo)程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機器語言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應(yīng)的關(guān)系，轉(zhuǎn)換成用機器語言表示的程序。解釋型編

45、譯程序?qū)⒏呒壵Z言程序的一個語句，先解釋成為一組機器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的對話，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫(binxi)的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快，在過程中，不能進行人機對話修改(xigi)。FORTRAN語言就是編譯型高級語言。2編譯程序的工作分為那幾個(j )階段? 詞法分析、語法分析和語義分析是對源程序進行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合

46、稱為對源程序進行綜合(稱為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價的目標(biāo)程序。3簡述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。4簡述代碼優(yōu)化的目的和意義。 代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運行時所需要的時間短，同時所占用的存儲空間少。五、綜合應(yīng)用題(共3小題，每小題10分，共30分)1證明下述文法G：SaSbS|aS|d是二義性文法。解：一個文法，如果存在某個句子

47、有不只一棵語法分析樹與之對應(yīng)，那么稱這個文法是二義性文法。句子aadbd有兩棵語法樹。如下圖：SaSSabSdddSSabSSad(1) (2)由此可知，SaSbS|aS|d定義的文法是二義性文法。ASBbBSab2對于文法GS：SAB，AAa|bB，Ba|Sb求句型baSb的全部短語、直接短語和句柄？句型baSb的語法樹如圖五(2)所示。解：baSb為句型baSb的相對(xingdu)于S的短語，ba為句型baSb的相對于A的短語，Sb為句型baSb的相對于B的短語，且為直接短語，a為句型baSb的相對于B的短語，且為直接短語和句柄。3設(shè)有非確定(qudng)的有自限動機NFA M=(A，B

48、，C，0，1，A，C)，其中(qzhng)： (A，0)=C (A，1)=A，B (B，1)=C (C，1)=C。請畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。解：狀態(tài)轉(zhuǎn)換距陣為：01ACA，BBCCC狀態(tài)轉(zhuǎn)換圖為11011編譯原理期末試題（六）編譯原理 樣題【 】1_型文法也稱為正規(guī)文法。A 0 B 1 C 2 D 3【 】2_文法不是LL(1)的。 A 遞歸 B 右遞歸 C 2型 D 含有公共左因子的【 】3 文法EE+E|E*E|i的句子i*i+i*i的不同語法分析樹的總數(shù)為_。A1 B3 C5 D7【 】4四元(s yun)式之間的聯(lián)系是通過 實現(xiàn)(shxin)。 A臨時(ln sh)變量 B指示器

49、 C符號表 D程序變量【 】5同心集合并可能會產(chǎn)生的新沖突為 。 A二義 B移進/移進 C移進/歸約 D歸約/歸約【 】6代碼優(yōu)化時所依據(jù)的是 。A語法規(guī)則 B詞法規(guī)則 C等價變換規(guī)則 D語義規(guī)則【 】7表達式a-(-b)*c的逆波蘭表示為 。Aa-bc* B HYPERLINK mailto:abc*- abc*- Cab- Dabc-* （注：為單目減運算符）【 】8過程的DISPLAY表記錄了 。A過程的連接數(shù)據(jù) B過程的嵌套層次C過程的返回地址 D過程的入口地址二 填空題3對于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的語言相同），則稱文法G1和G2是等價的。4對于文

50、法GE：ET|E+T TF|T*F FPF|P P(E)|i，句型T+T*F+i的句柄是T ，最左素短語是 T*F。 5最右推導(dǎo)的逆過程稱為規(guī)范歸約 ，也稱為 最左歸約。6規(guī)范規(guī)約中的可規(guī)約串是句柄 ，算符優(yōu)先分析中的可規(guī)約串是 最左素短語7（A B）（C D E） 的逆波蘭式是。8在屬性文法中文法符號的兩種屬性分別稱為繼承屬性 和綜合屬性（次序可換）。9符號表的每一項是由名字欄和 地址分配 兩個欄目組成。在目標(biāo)代碼生成階段，符號表是 地址分配 的依據(jù)。 10一個過程的DISPLAY表的內(nèi)容是它的直接外層 的DISPLAY表的內(nèi)容加上本過程的SP的地址三 有窮自動機M接受字母表0,1上所有滿足

51、下述條件的串：每個1都有0直接跟在右邊。構(gòu)造一個最小的DFA M及和M等價的正規(guī)式。【】【】四 證明(zhngmng)正規(guī)式(ab)*a 與正規(guī)(zhnggu)式a(ba)*等價 （用構(gòu)造(guzo)他們的最小的DFA方法）?！敬鸢福骸?五 寫一個文法，使其語言是：L 1n0m1m0n | m,n0 【】【】五 文法G：S 1S0 | AA 0A1 | 六 對文法(wnf)GS S aSb | PP bPc | bQcQ Qa | a它是否是算符優(yōu)先文法(wnf)？請構(gòu)造算符優(yōu)先關(guān)系表文法GS消除左遞歸、提取左公因子(ynz)后是否是LL（1）文法？請證實?！尽俊尽?.求出GS的FIRSTVT

52、集和LASTVT集：FIERSTVT（S）=a,b LASTBVT（S）=b,c FIERSTVT(P)=b LASTBVT（P）=c FIERSTVT(Q)=a LASTBVT（Q）=a構(gòu)造優(yōu)先關(guān)系表為： a b c a b c 由于在優(yōu)先關(guān)系中同時出現(xiàn)了aa以及bb，所以該文法不是算符優(yōu)先文法。消除左遞歸和提取左公因子后的文法為：S aSb | PP bPP Pc |QcQ aQQ aQ|求具有相同左部的兩個產(chǎn)生式的Select集的交集：Select(SaSb)Select(SP) = aFirst(P) = ab = Select(PPc)Select(PQc) = First(P)Fi

53、rst(Q)=ba= Select(QaQ)Select(Q) = aFollow(Q) = ac = 所以修改后的文法是LL（1）文法。七 已知文法G為:S SS aAdS bAcS aecS bedA e 試構(gòu)造它的LR（1）項目集、可歸前綴圖和LR（1）分析表?！尽俊敬鸢福骸縠cAdI0:S S , # S aAd , # S bAc , # S aec , #S bed , #I2： Sa Ad , #Sa ec , # A e , d aI1：SS , #SI3: Sb Ac , # Sb ed , # A e , cbI6: SbAc,# AI7：Sbe d , #Ae , cI1

54、1：Sbed , #dI10：SbAc , # I4：SaA d , #I5：Sae c , # Ae , deI8：SaAd , #I9：Saec , #c構(gòu)造LR(1)分析(fnx)表 如下(rxi)： r4 11S10 6r2 10 r3 9 r1 8S11r5 7r5S9 5S8 4 6S7 3 4S5 2acc 1A#S3bedc1S gotoaS2 action 0狀態(tài)八 已知源程序如下(rxi)： prod:=0; i:=1; while i20 do beginprod:=prod+ai*bi;i:=i+1 end;試按語法制導(dǎo)翻譯法將源程序翻譯成四元式序列(xli)（設(shè)A是數(shù)

55、組a的起始地址，B是數(shù)組b的起始地址；機器按字節(jié)編址，每個數(shù)組元素占四個字節(jié)）?！敬鸢?d n)：】九 設(shè)有以下(yxi)程序段 procedure P(x,y,z) begin Y:=y*3; Z:=X+z; end; begin a:=5; b:=2; p(a*b,a,a); print(a); end若參數(shù)傳遞的方法分別為（1）傳值、（2）傳地址、（3）傳名，試問結(jié)果分別什么？【】【】十 （1）傳值 5； （2）傳地址 25； （3）傳名 45十 對以下文法，請寫出關(guān)于括號嵌套層數(shù)的屬性文法。(為S,L引入屬性h,用來記錄輸出配對的括號個數(shù))文法規(guī)則語 義 規(guī) 則S(T)SiTT,STS

56、答案(d n)： 十一(ShY) 對PL/0語言的while語句(yj) while 條件B DO 語句S 的編譯程序，請在空缺處填空，完成該語句的編譯算法：switch (SYM) case WHILESYM: CX1=CX ;GetSym(); CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX); CX2=CX ;GEN(JPC,0,0);if (SYM=DOSYM) GetSym() ;else Error(18);STATEMENT(FSYS,LEV,TX);GEN(JMP,0,CX1); CODECX2.A=CX ；break;編譯原理期末試題（七）回答下

57、列(xili)問題：(30分)1什么是S-屬性文法(wnf)？什么是L-屬性文法？它們之間有什么關(guān)系？解答(jid)：S-屬性文法是只含有綜合屬性的屬性文法。 （2分）L-屬性文法要求對于每個產(chǎn)生式AX1X2Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj的一個繼承屬性，且該屬性僅依賴于：產(chǎn)生式Xj的左邊符號X1,X2Xj-1的屬性；A的繼承屬性。 （2分）S-屬性文法是L-屬性文法的特例。 （2分）2什么是句柄？什么是素短語？一個句型的最左直接短語稱為該句型的句柄。（3分）素短語是這樣的一個短語，它至少包含一個終結(jié)符并且不包含更小的素短語。（3分）3劃分程序的基本塊時，確定基本塊的

58、入口語句的條件是什么？解答：（1）程序第一個語句，或（2）能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或（3）緊跟在條件轉(zhuǎn)移語句后面的語句。4(6分)運行時的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現(xiàn)行層、直接外層、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。5(6分)對下列四元式序列生成目標(biāo)代碼： A:=B*

59、CD:=E+FG:=A+DH:=G*2其中，H是基本塊出口的活躍變量， R0和R1是可用寄存器答：LD R0， BMUL R0， CLD R1， EADD R1， FADD R0， R1MUL R0， 2ST R0， H二、設(shè)=0，1上的正規(guī)集S由倒數(shù)第二個字符(z f)為1的所有字符串組成，請給出該字集對應(yīng)的正規(guī)式，并構(gòu)造一個識別該正規(guī)集的DFA。(8分)答：構(gòu)造相應(yīng)(xingyng)的正規(guī)式：(0|1)*1(0|1) (3分)NFA: (2分) 1 110432 1 0 0確定(qudng)化：(3分)I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,

60、2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 1三、寫一個文法使其語言為L(G)= anbmambn | m,n1。(6分)答：文法G(S):S aSb | BB bBa | ba四、對于文法G(E): (8分)ET|E+TTF|T*FF(E)|iETF(E)E+TFiTT*F1. 寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。2. 寫出上述句型的短語，直接短語、句柄和素短語。答：1. (4分)ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 2. (4分)短語(duny)：(T*F+i), T*F+i,