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

1、PAGE 第 PAGE 63頁共6頁編譯原理期末(q m)試題（一）一、是非題（請在括號(kuho)內(nèi)，正確的劃，錯誤的劃）（每個2分，共20分）1編譯程序(chngx)是對高級語言程序的解釋執(zhí)行。( )2一個有限狀態(tài)自動機(jī)中，有且僅有一個唯一的終態(tài)。()3一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 ( )4語法分析時必須先消除文法中的左遞歸 。 ()5LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點(diǎn)。 ()6逆波蘭表示法表示表達(dá)式時無須使用括號。 ( )7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 ()8進(jìn)行代碼優(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如果文法G是無二義的，則它的任何句子_。A( )最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 B( ) 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同 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表達(dá)式(AB)(CD)的逆波蘭(b ln)表示為

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

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

6、考慮文法 GS: 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. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)(xingyng)的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +4. 按照(nzho)三種基本控制結(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ùn)算符優(yōu)先級高)： 100 (j,A,C,102) 101 (j,_,_,113) 102 (jaAd|aAb| 判斷(pndun)該文法是否是 SLR(1) 文法，若是構(gòu)造相應(yīng)分析表，并對輸入串 ab# 給出分析過程。解：增加一個非終結(jié)符S/后，產(chǎn)生(chnshng)原文法的增廣文法有： S-A A-aAd|aAb| 下面構(gòu)造它的LR(0)項目集規(guī)范族為： 從上表可看出,狀態(tài)I0和I2存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對于I0來說有：FOLLOW(A)a=b,d,#a=，所以在I0狀

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

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

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

11、一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是（ 二義性的 ）。 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

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

13、.對于數(shù)據(jù)空間的存貯分配， FORTRAN采用( 靜態(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)先分析法每次都是對(最左素短語）進(jìn)行歸約。三、名詞解釋題：1.局部優(yōu)化局限于基本塊范圍的優(yōu)化稱。2.二義性文法如果一個文法存在某個句子

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

15、果有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.超前搜索在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。15.句柄一個句型的最左直接短語。16.語法制導(dǎo)翻譯在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義程序進(jìn)行翻譯的方法 叫做語法制導(dǎo)翻譯。17.規(guī)范句型由規(guī)范推導(dǎo)所得到的句型。18.素短語素短語是指這樣一個短語，至少含有一個終結(jié)符，并且，除它自身外不再含任何更小的素短語。19

16、.語法是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。 20.待用信息如果在一個基本塊中，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。21.語義定義程序的意義的一組規(guī)則。四、簡答題：1.寫一個文法G, 使其語言為 不以0開頭的偶數(shù)集。2.已知文法G(S)及相應(yīng)翻譯方案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,

17、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文法(wnf)G(S)SdABAaA| aBBb| 描述(mio sh)的語言是什么？6. 證明文法G(S) SSaS| 是二義性的。7. 已知文法G(S) SBAABS| dBaA| bS | c的預(yù)測分析表如下 a b c d # SSBASBASBA AABSABSABSAd BBaA BbS Bc給出句子 adccd 的分析過程。8. 寫一個文法G,

18、使其語言為 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. 目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時通常應(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;

19、 z:=y*z+xend;begin a:=2; b:=3; p(a+b, b, a); print aend.試問，若參數(shù)傳遞的方式(fngsh)分別采用傳地址和傳值時，程序執(zhí)行后輸出 a的值是什么? 16.寫出表達(dá)式ab*(c-d)/e的逆波蘭(b ln)式和三元(sn yun)序列。17.證明文法G(A) AAA | (A)| 是二義性的。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

20、+b, a-b, a);print a end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a的值是什么? 21.寫一個文法G, 使其語言為 L(G)=anbncm| n0為奇數(shù)， m0為偶數(shù)22.寫出表達(dá)式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。23.一個文法G別是LL(1)文法的充要條件是什么？24.已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左遞歸和提公共左因子。25.符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？答案：1.所求文法是GS:SAB |B A0AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |

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

22、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)化：對程序進(jìn)行(jnxng)各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級別：局部優(yōu)化、循環(huán)(xnhun)優(yōu)化、全局

23、優(yōu)化11.目標(biāo)(mbio)代碼通常采用三種形式：機(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: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

24、)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)一個過程運(yùn)行時必須跟蹤它的所有外層過程的最新活動記錄起始地址， display表就是用于登記每個外層過程的最新活動記錄起始地址。20.傳地址 a=12傳值 a=521.所求文法是GS: SAC AaaAbb | ab CccC | cc22.逆波蘭式 abc+e*bc+f/+:=三元序列 op

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

26、折查找，雜奏技術(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:i1goto aga

27、inEnd;（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è)(jish)基本塊出口時只有M還被引用，請寫出優(yōu)化后的四元序列。7.已知文法(wnf)G(S)Sa | | (T)TT,S | S(1) 給出句子(j zi)(a,(a,a)的最左推導(dǎo)；(2) 給出句型(T,S),a)的短語, 直接短語，句柄。8.對于 C 語言do S wh

28、ile 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)造相應(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的

29、最左推導(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 | ST,ST |此文法(wnf)無左公共左因子。(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(

30、),#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) 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)Ffor i:=E(1) to E(2)

31、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:=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

32、)(+, 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)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)

33、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=abbcBe=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)=, ), #

34、 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, _, _, (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)

35、*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 素短語(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 .

36、 . . . . . - . (=,#=(2) 是算符優(yōu)先文法，因為任何兩個終結(jié)符之間至多只有一種優(yōu)先關(guān)系。（2分）(3) 給出輸入(shr)串(a,a)#的算符優(yōu)先分析過程。步驟 棧當(dāng)前輸入字符剩余輸入串動作1#(a,a#( 移進(jìn)2#(a,a)#(, 歸約4#(N,a)#(, 移進(jìn)5#(N,a)#,) 歸約7#(N,N）#,) 歸約8#(N)#(=) 移進(jìn)9#(N)#)# 歸約10#N#接受編譯原理(yunl)期末試題（四）簡述編譯程序(bin y chn x)的工作過程。（10）編譯程序的工作過程，是指從輸入源程序開始到輸出目標(biāo)程序為止的整個過程，是非常復(fù)雜的，就其過程而言，一般可以劃分為

37、五個工作階段：詞法分析，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個個的單詞；語法分析，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位；語義分析與中間代碼產(chǎn)生，即對各類語法單位，分析其漢一并進(jìn)行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更高效的代碼；目標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級語言指令形式。二、構(gòu)造下列正規(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三、給出下面(xi mian)語言的相應(yīng)文法：（15

38、）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）文法，如果是，給出其預(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 |Eg

39、Af | 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)。六、對表達(dá)式文法(wnf)G：E E+T | TT T*F | FF (E) | 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（）#=七、有定義二進(jìn)制整數(shù)的文法如下：L

40、LB | BB 0 | 1構(gòu)造一個翻譯模式，計算該二進(jìn)制數(shù)的值（十進(jìn)制的值）。（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編譯(biny)原理期末試題（五）一、單項選擇題(共10小題(xio t)，每小題2分，共20分)1語言(yyn)是A句子的集合 B產(chǎn)生式的集合 C符號串的集合 D句型的集合2編譯程序前三個階段完成的工作是A詞法分析、語法分析和代碼優(yōu)化 B代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語法分析、語義分析和中間代碼生

41、成 D詞法分析、語法分析和代碼優(yōu)化3一個句型中稱為句柄的是該句型的最左 A非終結(jié)符號 B短語 C句子 D直接短語4下推自動機(jī)識別的語言是A0型語言 B1型語言 C2型語言 D3型語言5掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨(dú)立含義的最小語法單位即 A 字符 B單詞 C句子 D句型6對應(yīng)Chomsky四種文法的四種語言之間的關(guān)系是 AL0L1L2L3 BL3L2L1L0 CL3=L2L1L0 DL0L1L2=L37詞法分析的任務(wù)是 A識別單詞 B分析句子的含義 C識別句子 D生成目標(biāo)代碼8常用的中間代碼形式不含 A三元式 B四元式 C逆波蘭式 D語法樹9 代碼優(yōu)化的目的是 A

42、節(jié)省時間 B節(jié)省空間 C節(jié)省時間和空間 D把編譯程序進(jìn)行等價交換10代碼生成階段的主要任務(wù)是 A把高級(goj)語言翻譯成匯編語言 B把高級(goj)語言翻譯成機(jī)器語言 C把中間代碼變換成依賴具體(jt)機(jī)器的目標(biāo)代碼 D把匯編語言翻譯成機(jī)器語言二、填空題（本大題共5小題，每小題2分，共10分）1編譯程序首先要識別出源程序中每個(單詞)，然后再分析每個(句子)并翻譯其意義。 2編譯器常用的語法分析方法有(自底向上)和(自頂向下)兩種。3通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的(綜合)。4程序設(shè)計

43、語言的發(fā)展帶來了日漸多變的運(yùn)行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動態(tài)存儲分配)方案。5對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目標(biāo)程序)。三、名詞解釋題(共5小題，每小題4分，共20分)1詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構(gòu)成源程序的字符串中識別出一個個具有獨(dú)立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。2LL(1)文法 若文法的任何兩個產(chǎn)生式A | 都滿足下面兩個條件：（1）FIRST( ) FIRST( ) = ；（2）若 * ，那么FIRST( ) FOLLOW( A ) = 。 我們

44、把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個L代表從左向右掃描輸入，第二個L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語法樹 句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。給定文法G=(VN，VT，P，S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點(diǎn)的標(biāo)記是開始符號S。(2)每個節(jié)點(diǎn)的標(biāo)記都是V中的一個符號。(3)若一棵子樹的根節(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序為A1A2AR，那么AA1A2AR一定是P中的一條產(chǎn)生式

45、。(4)若一標(biāo)記為A的節(jié)點(diǎn)至少有一個除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。4LR(0)分析器 所謂(suwi)LR(0)分析(fnx)，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前(dngqin)已移進(jìn)和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動作 (是移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等)。5語言和文法文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合

46、。文法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)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)=x| S*x，其中S為文法開始符號，且 簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題(共4小題，每小題5分，共20分)1編譯程序和高級語言有什么區(qū)別? 用匯編語言或高級語言編寫的程序，必須先送入計算機(jī)，經(jīng)過轉(zhuǎn)換成用

47、機(jī)器語言表示的目標(biāo)程序（這個過程即編譯），才能由計算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機(jī)器語言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語言表示的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句，先解釋成為一組機(jī)器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)行人和計算機(jī)的對話，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z

48、言編寫的程序，一次就會部翻譯成機(jī)器語言表示的程序，而且過程進(jìn)行很快，在過程中，不能進(jìn)行人機(jī)對話修改。FORTRAN語言就是編譯型高級語言。2編譯程序的工作分為那幾個階段? 詞法(cf)分析、語法分析和語義分析是對源程序進(jìn)行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進(jìn)行(jnxng)綜合(稱為編譯程序(bin y chn x)的后端)，它們從源程序的中間表示建立起和源程序等價的目標(biāo)程序。3簡述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點(diǎn)。4簡

49、述代碼優(yōu)化的目的和意義。 代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進(jìn)行一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運(yùn)行時所需要的時間短，同時所占用的存儲空間少。五、綜合應(yīng)用題(共3小題，每小題10分，共30分)1證明下述文法G：SaSbS|aS|d是二義性文法。解：一個文法，如果存在某個句子有不只一棵語法分析樹與之對應(yīng)，那么稱這個文法是二義性文法。句子aadbd有兩棵語法樹。如下圖：SaSSabSdddSSabSSad(1) (2)由此可知，SaSbS|aS|d定義的文法是二義性文法。ASBbBSab2對于文法GS：SAB，AAa|bB，Ba|Sb求

50、句型baSb的全部短語、直接短語和句柄？句型baSb的語法樹如圖五(2)所示。解：baSb為句型baSb的相對于S的短語(duny)，ba為句型baSb的相對于A的短語，Sb為句型baSb的相對于B的短語，且為直接短語，a為句型baSb的相對于B的短語，且為直接短語和句柄。3設(shè)有非確定(qudng)的有自限動機(jī)NFA M=(A，B，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_型文法也稱為

51、正規(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四元式之間的聯(lián)系是通過 實現(xiàn)。 A臨時變量 B指示器 C符號表 D程序變量【 】5同心集合并可能會產(chǎn)生的新沖突為 。 A二義 B移進(jìn)/移進(jìn) C移進(jìn)/歸約 D歸約/歸約【 】6代碼優(yōu)化時所依據(jù)的是 。A語法規(guī)則 B詞法規(guī)則 C等價變換規(guī)則 D語義規(guī)則【 】7表達(dá)式a-(-b)*c的逆波蘭(b ln)表示為 。Aa-bc* B HYPERLINK mailto:a

52、bc*- abc*- Cab- Dabc-* （注：為單目減運(yùn)算符）【 】8過程(guchng)的DISPLAY表記錄了 。A過程的連接(linji)數(shù)據(jù) B過程的嵌套層次C過程的返回地址 D過程的入口地址二 填空題3對于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的語言相同），則稱文法G1和G2是等價的。4對于文法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）

53、的逆波蘭式是。8在屬性文法中文法符號的兩種屬性分別稱為繼承屬性 和綜合屬性（次序可換）。9符號表的每一項是由名字欄和 地址分配 兩個欄目組成。在目標(biāo)代碼生成階段，符號表是 地址分配 的依據(jù)。 10一個過程的DISPLAY表的內(nèi)容是它的直接外層 的DISPLAY表的內(nèi)容加上本過程的SP的地址三 有窮自動機(jī)M接受字母表0,1上所有滿足下述條件的串：每個1都有0直接跟在右邊。構(gòu)造一個最小的DFA M及和M等價的正規(guī)式?！尽俊尽克?證明正規(guī)式(ab)*a 與正規(guī)式a(ba)*等價 （用構(gòu)造他們的最小的DFA方法）?！敬鸢?d n)：】 五 寫一個文法(wnf)，使其語言是：L 1n0m1m0n | m

54、,n0 【】【】五 文法(wnf)G：S 1S0 | AA 0A1 | 六 對文法GS S aSb | PP bPc | bQcQ Qa | a它是否是算符優(yōu)先文法？請構(gòu)造算符優(yōu)先關(guān)系表文法GS消除左遞歸、提取左公因子后是否是LL（1）文法？請證實?！尽俊尽?.求出GS的FIRSTVT集和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)系中同時(tngsh)出現(xiàn)了aa以及(yj)bb，所以該文法不是(b

55、shi)算符優(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)First(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）分析表?！尽俊敬鸢?/p>

56、：】ecAdI0: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 , cI11：Sbed , #dI10：SbAc , # I4：SaA d , #I5：Sae c , # Ae , deI8：SaAd , #I9：Saec , #c構(gòu)造LR(1)分析表 如下： r4 11S10 6r2 10 r3 9 r1 8S11r5 7r5S9 5S8 4 6S

57、7 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)翻譯法將源程序翻譯成四元式序列（設(shè)A是數(shù)組a的起始地址，B是數(shù)組b的起始地址；機(jī)器(j q)按字節(jié)編址，每個數(shù)組元素占四個字節(jié)）?！敬鸢?d n)：】九 設(shè)有以下(yxi)程序(chngx)段 procedure P(x,y,z) begin Y:=y*3; Z:=X+z; end; begin a:=5; b:=2; p(a*b,a,a); p

58、rint(a); end若參數(shù)傳遞的方法(fngf)分別為（1）傳值、（2）傳地址、（3）傳名，試問結(jié)果分別什么？【】【】十 （1）傳值 5； （2）傳地址 25； （3）傳名 45十 對以下文法，請寫出關(guān)于括號嵌套層數(shù)的屬性文法。(為S,L引入屬性h,用來記錄輸出配對的括號個數(shù))文法規(guī)則語 義 規(guī) 則S(T)SiTT,STS答案(d n)： 十一(ShY) 對PL/0語言(yyn)的while語句 while 條件B DO 語句S 的編譯程序，請在空缺處填空，完成該語句的編譯算法：switch (SYM) case WHILESYM: CX1=CX ;GetSym(); CONDITION(

59、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;編譯原理期末試題（七）回答下列問題：(30分)1什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？解答：S-屬性文法是只含有綜合屬性的屬性文法。 （2分）L-屬性文法要求對于每個產(chǎn)生式AX1X2Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj的一個繼承屬性，且該屬性僅依賴于：產(chǎn)

60、生式Xj的左邊符號X1,X2Xj-1的屬性；A的繼承屬性。 （2分）S-屬性文法是L-屬性文法的特例。 （2分）2什么(shn me)是句柄？什么是素短語？一個句型的最左直接短語(duny)稱為該句型的句柄。（3分）素短語是這樣的一個短語，它至少包含一個終結(jié)符并且不包含更小的素短語。（3分）3劃分程序(chngx)的基本塊時，確定基本塊的入口語句的條件是什么？解答：（1）程序第一個語句，或（2）能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或（3）緊跟在條件轉(zhuǎn)移語句后面的語句。4(6分)運(yùn)行時的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個過程