編譯原理期末試題（8套含答案大題集）

本文格式為Word版，下載可任意編輯——編譯原理期末試題（8套含答案大題集）《編譯原理》期末試題（一）

一、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃×）（每個2分，共20分）1．編譯程序是對高級語言程序的解釋執(zhí)行。(×)

2．一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。(×)3．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。(√)4．語法分析時必需先消除文法中的左遞歸。(×)

5．LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能確鑿地指出出錯地點。(√)6．逆波蘭表示法表示表達式時無須使用括號。(√)7．靜態(tài)數(shù)組的存儲空間可以在編譯時確定。(×)

8．進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。(×)9．兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。(×)10．一個語義子程序描述了一個文法所對應的翻譯工作。(×)

二、選擇題(請在前括號內(nèi)選擇最確鑿的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1．詞法分析器的輸出結(jié)果是_____。

A．()單詞的種別編碼B．()單詞在符號表中的位置C．()單詞的種別編碼和自身值D．()單詞自身值2．正規(guī)式M1和M2等價是指_____。

A．()M1和M2的狀態(tài)數(shù)相等B．()M1和M2的有向邊條數(shù)相等C．()M1和M2所識別的語言集相等D．()M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等3．文法G：S→xSx|y所識別的語言是_____。

A．()xyxB．()(xyx)*C．()xnyxn(n≥0)D．()x*yx*4．假使文法G是無二義的，則它的任何句子α_____。A．()最左推導和最右推導對應的語法樹必定一致B．()最左推導和最右推導對應的語法樹可能不同C．()最左推導和最右推導必定一致

D．()可能存在兩個不同的最左推導，但它們對應的語法樹一致5．構造編譯程序應把握______。

A．()源程序B．()目標語言C．()編譯方法D．()以上三項都是6．四元式之間的聯(lián)系是通過_____實現(xiàn)的。A．()指示器B．()臨時變量C．()符號表D．()程序變量

第1頁共6頁

7．表達式(┐A∨B)∧(C∨D)的逆波蘭表示為_____。A.()┐AB∨∧CD∨B．()A┐B∨CD∨∧C．()AB∨┐CD∨∧D．()A┐B∨∧CD∨8.優(yōu)化可生成_____的目標代碼。

A．()運行時間較短B．()占用存儲空間較小

C．()運行時間短但占用內(nèi)存空間大D．()運行時間短且占用存儲空間小9．以下______優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A.()強度減弱B．()刪除歸納變量C．()刪除多余運算D．()代碼外提10．編譯程序使用_____區(qū)別標識符的作用域。A.()說明標識符的過程或函數(shù)名

B．()說明標識符的過程或函數(shù)的靜態(tài)層次C．()說明標識符的過程或函數(shù)的動態(tài)層次D.()標識符的行號

三、填空題(每空1分，共10分)

1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：___解釋__和__編譯___。

2．掃描器是__詞法分析器___，它接受輸入的__源程序___，對源程序進行___詞法分析__并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。

3．自上而下分析法采用___移進__、歸約、錯誤處理、___接受__等四種操作。4．一個LR分析器包括兩部分：一個總控程序和___一張分析表__。5．后綴式abc-/所代表的表達式是___a/(b-c)__。6．局部優(yōu)化是在__基本塊___范圍內(nèi)進行的一種優(yōu)化。四、簡答題（20分）

1.簡要說明語義分析的基本功能。

答：語義分析的基本功能包括:確定類型、類型檢查、語義處理和某些靜態(tài)語義檢查。

2.考慮文法G[S]:S→(T)|a+S|aT→T,S|S

消除文法的左遞歸及提取公共左因子。解：消除文法G[S]的左遞歸：S→(T)|a+S|aT→ST′T′→,ST′|ε提取公共左因子：

第2頁共6頁

S→(T)|aS′S′→+S|εT→ST′T′→,ST′|ε

3.試為表達式w+(a+b)*(c+d/(e-10)+8)寫出相應的逆波蘭表示。解：wab+cde10-/+8+*+

4.依照三種基本控制結(jié)構文法將下面的語句翻譯成四元式序列：while(AaAd|aAb|ε

判斷該文法是否是SLR(1)文法，若是構造相應分析表，并對輸入串a(chǎn)b#給出分析過程。解：增加一個非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：S'->AA->aAd|aAb|ε下

面

構

造

它

的

LR(0)

項

目

集

規(guī)

范

族

第4頁共6頁

為

：

從上表可看出,狀態(tài)I0和I2存在移進-歸約沖突，該文法不是LR(0)文法。對于I0來說有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0狀態(tài)下面臨輸入符號為a時移進，為b,d,#時歸約，為其他時報錯。對于I2來說有也有與I0完全一致的結(jié)論。這就是說，以上的移進-歸約沖突是可以解決的，因此該文法是SLR(1)文法。其SLR(1)分析表為：

對輸入串a(chǎn)b#給出分析過程為：

第5頁共6頁

《編譯原理》期末試題（二）

一、是非題：

1.一個上下文無關文法的開始符，可以是終結(jié)符或非終結(jié)符。()2.一個句型的直接短語是唯一的。（）3.已經(jīng)證明文法的二義性是可判定的。（）4.每個基本塊可用一個DAG表示。（）5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。（）6.2型文法一定是3型文法。（）7.一個句型一定句子。()8.算符優(yōu)先分析法每次都是對句柄進行歸約。X()9.采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。（）10.編譯過程中，語法分析器的任務是分析單詞是怎樣構成的。()11.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。X()12.目標代碼生成時，應考慮如何充分利用計算機的寄放器的問題。()13.遞歸下降分析法是一種自下而上分析法。()14.并不是每個文法都能改寫成LL(1)文法。()15.每個基本塊只有一個入口和一個出口。()16.一個LL(1)文法一定是無二義的。()17.逆波蘭法表示的表達試亦稱前綴式。()18.目標代碼生成時，應考慮如何充分利用計算機的寄放器的問題。()19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關文法來描述。()20.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。()21.3型文法一定是2型文法。()22.假使一個文法存在某個句子對應兩棵不同的語法樹，則文法是二義性的。()答案：1.×2.×3.×4.√5.√6.×7.×8.×9.√10.×

11.×

12.√13.×14.√15.√16.√17.×18.√19.√20.×21.√22.√

二、填空題：

2.編譯過程可分為（詞法分析），（語法分析），（語義分析與中間代碼生成），（優(yōu)化）和（目標代碼生成）五個階段。

3.假使一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（二義性的）。4.從功能上說，程序語言的語句大體可分為（執(zhí)行性）語句和（說明性）語句兩大類。5.語法分析器的輸入是（單詞符號），其輸出是（語法單位）。6.掃描器的任務是從（源程序中）中識別出一個個（單詞符號）。

7.符號表中的信息欄中登記了每個名字的有關的性質(zhì)，如(類型、種屬、所占單元大小、地址）等等。8.一個過程相應的DISPLAY表的內(nèi)容為(現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址)10.常用的兩種動態(tài)存貯分派方法是（棧式）動態(tài)分派和（堆式）動態(tài)分派。11.一個名字的屬性包括(類型)和(作用域)。12.常用的參數(shù)傳遞方式有(傳地址），（傳值），（傳名）

13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個級別。14.語法分析的方法大致可分為兩類，一類是（自上而下）分析法，另一類是（自下而上）

分析法。

15.預計分析程序是使用一張（分析表）和一個（符號棧）進行聯(lián)合控制的。

17.一張轉(zhuǎn)換圖只包含有限個狀態(tài),其中有一個被認為是（初）態(tài);而且實際上至少要有一個（終）態(tài)。19.語法分析是依據(jù)語言的（語法）規(guī)則進行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進行的。

第6頁共6頁

21.一個文法G，若它的預計分析表M不含多重定義，則該文法是（LL(1)文法）文法。22.對于數(shù)據(jù)空間的存貯分派，F(xiàn)ORTRAN采用(靜態(tài)策略，PASCAL采用(動態(tài))策略。24.最右推導亦稱為（規(guī)范推導），由此得到的句型稱為（規(guī)范）句型。26.對于文法G，僅含終結(jié)符號的句型稱為(句子)。

27.所謂自上而下分析法是指(從開始符號出發(fā)，向下推導，推出句子）29.局限于基本塊范圍的優(yōu)化稱（局部優(yōu)化）。

31.2型文法又稱為（上下文無關）文法；3型文法又稱為（正則）文法。32.每條指令的執(zhí)行代價定義為(指令訪問主存次數(shù)加1）33.算符優(yōu)先分析法每次都是對(最左素短語）進行歸約。三、名詞解釋題：

1.局部優(yōu)化局限于基本塊范圍的優(yōu)化稱。

2.二義性文法假使一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義性文法。3.DISPLAY表過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。5.最左推導任何一步α=>β都是對α中的最右非終結(jié)符替換。6.語法一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法描述語言的語法結(jié)構的形式規(guī)則。

8.基本塊指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個

語句，出口就是其中的最終一個語句。

9.語法制導翻譯在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義子程序進行翻譯的方法叫做語法制導翻譯。

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ù)每個產(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.寫一個文法G,使其語言為不以0開頭的偶數(shù)集。2.已知文法G(S)及相應翻譯方案

S→aAb{print“1〞}S→a{print“2〞}A→AS{print“3〞}A→c{print“4〞}輸入acab,輸出是什么？3.已知文法G(S)

S→bAa

A→(B|aB→Aa)

第7頁共6頁

寫出句子b(aa)b的規(guī)范歸約過程。4.考慮下面的程序：

?

procedurep(x,y,z)；beginy:=x+y;z:=z*z;endbegin

A:=2;B:=A*2;P(A,A,B);PrintA,Bend.

試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出A,B的值是什么?5．文法G(S)S→dABA→aA|aB→Bb|ε

描述的語言是什么？6.證明文法G(S)S→SaS|ε是二義性的。7.已知文法G(S)S→BAA→BS|d

B→aA|bS|c的預計分析表如下

abcd#SS→BAS→BAS→BAAA→BSA→BSA→BSA→dBB→aAB→bSB→c

給出句子adccd的分析過程。

lmlnn

8.寫一個文法G,使其語言為L(G)={abcab|l>=0,m>=1,n>=2}9.已知文法G(S):S→a|(T)T→T,S|S

的優(yōu)先關系表如下：

關系a(),a--.>.>(.>,.>請計算出該優(yōu)先關系表所對應的優(yōu)先函數(shù)表。10.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？

11.目標代碼有哪幾種形式？生成目標代碼時尋常應考慮哪幾個問題？

12.一字母表Σ={a,b}，試寫出Σ上所有以a為首的字組成的正規(guī)集相對應的正規(guī)式。

第8頁共6頁

13.基本的優(yōu)化方法有哪幾種？

nn

14.寫一個文法G,使其語言為L(G)={abc|n≥0}15.考慮下面的程序：

?

procedurep(x,y,z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;

p(a+b,b,a);printaend.

試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么?16.寫出表達式a＋b*(c-d)/e的逆波蘭式和三元序列。17.證明文法G(A)A→AA|(A)|ε是二義性的。

**

18.令Σ={a,b}，則正規(guī)式ab|ba表示的正規(guī)集是什么？19.何謂DISPLAY表？其作用是什么？20.考慮下面的程序：

?

procedurep(x,y,z)；beginy:=y+2;z:=z+x;endbegin

a:=5;b:=2;

p(a+b,a-b,a);printaend.

試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么?

nnm

21.寫一個文法G,使其語言為L(G)={abc|n>0為奇數(shù)，m>0為偶數(shù)}22.寫出表達式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。23.一個文法G別是LL(1)文法的充要條件是什么？24.已知文法G[S]

S→S*aF|aF|*aFF→+aF|+a

消除文法左遞歸和提公共左因子。

25.符號表的作用是什么？符號表查找和整理技術有哪幾種？答案：1.所求文法是G[S]:

S→AB|BA0A→AD|C

B→2|4|6|8

C→1|3|5|7|9|B

第9頁共6頁

D→0|C2.輸出是4231

3.句子b(aa)b的規(guī)范歸約過程：步驟符號棧012345678910##b#b(#b(a#b(A#b(Ma#b(Ma)#b(B#bA#bAb#S輸入串b(aa)b#(aa)b#aa)b#a)b#a)b#)b#b#b#b###預備移進移進移進歸約移進移進歸約歸約移進接受動作4.傳地址A=6,B=16傳值A=2,B=4

nm

5.L(G)={dab|n>0,m≥0}6.證明：

由于文法G[S]存在句子aa有兩個不同的最左推導，所以文法G[S]是是二義性的。

S=>SaS=>SaSaS=>aSaS=>aaS=>aaS=>SaS=>aS=>aSaS=>aaS=>aa7.句子adccd的分析過程：步驟符號棧輸入串產(chǎn)生式0123456789101112138.所求文法是G[S]:S→AB

A→aAc|DD→bD|bB→aBb|aabb

第10頁共6頁

#S#AB#AAa#AA#Ad#A#SB#Sc#S#AB#Ac#A#d#adccd#adccd#adccd#dccd#dccd#ccd#ccd#ccd#cd#cd#d#d#d##S→BAB→aA

A→dA→BSB→cB→cA→d

9.

函數(shù)fga45(25)42,4310.優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化

11.目標代碼尋常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。

應著重考慮的問題：

(1)如何使生成的目標代碼較短；

(2)如何充分利用寄放器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點。12.正規(guī)式a(a|b)*。

13.刪除多余運算，代碼外提，強度減弱，變換循環(huán)控制條件，合并已知量，復寫傳播和刪除無用賦值。14.文法G[S]:

S→aB|aB→bc|bBc15.傳值a=2傳地址a=15

16.逆波蘭式:abcd-*e/+

三元序列:oparg1arg2(1)-cd(2)*b(1)(3)/(2)e(4)+a(3)17.證明：

由于文法G[S]存在句子()有兩個不同的最左推導，所以文法G[S]是是二義性的。

A=>AA=>(A)A=>()A=>()

A=>AA=>A=>(A)=>()

**

18.(ab|ba)={a,b,ab,ba,aab,bba??}19.Display表:嵌套層次顯示表

由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當一個過程運行時必需跟蹤它的所有外層過程的最新活動記錄起始地址，display表就是用于登記每個外層過程的最新活動記錄起始地址。20.傳地址a=12傳值a=5

21.所求文法是G[S]:S→AC

A→aaAbb|abC→ccC|cc

22.逆波蘭式abc+e*bc+f/+:=

三元序列oparg1arg2(1)+bc(2)*(1)e(3)+bc(4)/(3)f(5)+(2)(4)(6):=a(5)

第11頁共6頁

23.一個文法G別是LL(1)文法的充要條件是:(1)FIRST(α)∩FIRST(β)=Ф

*

(2)假使β=>ε,FIRST(α)∩FOLLOW(A)=Ф24.消除左遞歸

S→aFS’|*aFS’S’→*aFS’|εF→+aF|+a

提公共左因子,文法G’(S)S→aFS’|*aFS’S’→*aFS’|εF→+aF’F’→F|ε

25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進展狀況。主要技術：線性表，對折查找，雜奏技術。五、計算題：1.設文法G(S):

S→^|a|(T)T→T,S|S

⑴消除左遞歸；

⑵構造相應的FIRST和FOLLOW集合；⑶構造預計分析表2.語句ifEthenS

(1)改寫文法，使之適合語法制導翻譯；(2)寫出改寫后產(chǎn)生式的語義動作。3.設文法G（S）：S→(T)|aT→T+S|S

(1）計算FIRSTVT和LASTVT；（2）構造優(yōu)先關系表。4.設某語言的for語句的形式為

(1)(2)

fori:＝EtoEdoS其語義解釋為

(1)

i:＝E

(2)

LIMIT:＝E

again:ifi＜＝LIMITthen

BeginS;

i:＝i＋1gotoagainEnd;

（1）寫出適合語法制導翻譯的產(chǎn)生式；（2）寫出每個產(chǎn)生式對應的語義動作。5.把語句

whilea0thena:=a+1

elsea:=a*3-1;

翻譯成四元式序列。6.設有基本塊D:=A-C

第12頁共6頁

E:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ:=T*Q

K:=G*5L:=K+JM:=L

假設基本塊出口時只有M還被引用，請寫出優(yōu)化后的四元序列。7.已知文法G(S)S→a|^|(T)T→T,S|S

(1)給出句子(a,(a,a))的最左推導；

(2)給出句型((T,S),a)的短語,直接短語，句柄。8.對于C語言doSwhileE語句

(1)改寫文法，使之適合語法制導翻譯；(2)寫出改寫后產(chǎn)生式的語義動作。9.已知文法G(S)S→aAcBeA→Ab|bB→d

(1)給出句子abbcde的最左推導及畫出語法樹；(2)給出句型aAbcde的短語、素短語。10.設文法G(S):

S→(T)|aS|aT→T,S|S

⑴消除左遞歸和提公共左因子；

⑵構造相應的FIRST和FOLLOW集合；⑶構造預計分析表。11.把語句

ifX>0∨Y0doX:=A*3elseY:=B+3;

翻譯成四元式序列。12.已知文法G(S)E→E+T|TT→T*F|FF→(E)|i

(1)給出句型(i+i)*i+i的最左推導及畫出語法樹；

(2)給出句型(E+T)*i+F的短語，素短語和最左素短語。13.設文法G（S）：S→T|S∨TT→U|T∧UU→i|-U

（1）計算FIRSTVT和LASTVT；（2）構造優(yōu)先關系表。

第13頁共6頁

答案：(1)消除左遞，文法變?yōu)镚’[S]：

S→^|a|(T)'T→ST’|ST’→,ST’|ε

此文法無左公共左因子。

(2)構造相應的FIRST和FOLLOW集合：FIRST(S)={a,^,(}，F(xiàn)OLLOW(S)={#,,,)}FIRST(T)={a,^,(}，F(xiàn)OLLOW(T)={}}FIRST(T’)={,,ε}，F(xiàn)OLLOW(F)={)}(3)構造預計分析表：a^(STT?S→aT→ST?S→^T→ST?S→(T)'T→ST?)T?→ε,T?→,ST?#2.(1)C→ifEthen

(1)

S→CS(2)

C→ifEthen{BACK(E.TC,NXQ);C.chain:=E.FC}

(1)(1)

S→CS{S.chain:=MERG(C.Chain,S.Chain)}3.(1)FIRSTVT(S)={a,(}FIRSTVT(T)={+,aa,(}LASTVT(S)={a,)}

LASTVT(T)={+,a,)}

(2)a+(a.>+.>(1)(2)4.(1)F→fori:=EtoEdo(1)

S→FS

(1)(2)

(2)F→fori:=EtoEdo

(1)

{GEN(:=,E.place,_,entry(i));F.place:=entry(i);LIMIT:=Newtemp;

(2)

GEN(:=,E.place,_,LIMIT);Q:=NXQ;F.QUAD:=q;

GEN(j≤,entry(i),LIMIT,q+2)F.chain:=NXQ;GEN(j,_,_,0)}

(1)

S→FS

(1)

{BACKPATCH(S.chain,NXQ);GEN(+,F.place,1,F.place);GEN(j,_,_,F.QUAD);S.chain:=F.chain}

5.(1)(j.>=.>.(2)(j,_,_,(12))(3)(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.最左推導

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,Sa

直接短語T,Sa句柄T,S8.(1)

S→doM1S1whileM2EM→ε(2)

M→ε{M.quad=nestquad;}

S→doM1S1whileM2E{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’S’→S|εL→SL’

L’→,SL’|ε

(2)FIRST(S)={a,(}FIRST(S’)={a,(,ε}FIRST(L)={a,(}FIRST(L’)={,,ε}

FOLLOW(S)={,,),#}FOLLOW(S’)={,,),#}FOLLOW(L)={)}FOLLOW(L’)={)}

第15頁共6頁

(3)

()a,SS→(L)S→aS?S?S?→SS?→εS?→SS?→εLL→SL?L→SL?L?→,SL?L?L?→ε

11.(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)*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)短語i,F,E+T,(E+T),(E+T)*i,(E+T)*i+F素短語i,E+T最左素短語E+T

13.(1)FIRSTVT(S)={∨,∧,i,-}FIRSTVT(T)={∧,i,-}FIRSTVT(U)={i,-}

LASTVT(S)={∨,∧,i,-}

LASTVT(T)={∧,i,-}

LASTVT(U)={i,-}

(2)

i∨∧-S.>.>∨.>.>《編譯原理》期末試題（三）

1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對循環(huán)的優(yōu)化可以有哪三種？答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類；對循環(huán)的優(yōu)化有三種：循環(huán)不變表達式外提、歸納變量刪除與計算強度削減。2、寫出表達式a=b*c+b*d對應的逆波蘭式、四元式序列和三元式序列。答：逆波蘭式：abc*bd*+:=四元式序列：

三元式序列:OPARG1ARG2

(1)(*b，c)(2)(*b，d)(3)(+(1)，(2))(4)(:=(3)，a)

(1)(*，b，c，t1)(2)(*，b，d，t2)(3)(+，t1，t2，t3)(4)(:=，t3，/，a)

3、對于文法G(S):

S?bMbM?(L|aL?Ma）

答：1）S?bMb?b(Lb?b(Ma)b2）短語:Ma)，(Ma)，b(Ma)b直接短語:Ma)句柄:Ma)

b(SMbTLMa)三、設有字母表{a，b}上的正規(guī)式R=(ab|a)*。

解：（1）

2-0εa1abε+3

（2）將（1）所得的非確定有限自動機確定化

εab-01131221+3第21頁共6頁

2+

-+a0ba1+a

（3）對（2）得到的DFA化簡，合并狀態(tài)0和2為狀態(tài)2：

2-+ba1+

（4）令狀態(tài)1和2分別對應非終結(jié)符B和A

G:A→aB|a|ε；B→aB|bA|a|b|ε；可化簡為：G:A→aB|ε；B→aB|bA|ε

a四、設將文法G改寫成等價的LL(1)文法，并構造預計分析表。

G：S→S*aT|aT|*aT；T→+aT|+a

解：消除左遞歸后的文法G’:S→aTS’|*aTS’

S’→*aTS’|ε

T→+aT|+a

提取左公因子得文法G’’:S→aTS’|*aTS’

S’→*aTS’|εT→+aT’

T’→T|εSelect(S→aTS’)={a}Select(S→*aTS’)={*}

Select(S→aTS’)∩Select(S→*aTS’)=ФSelect(S’→*aTS’)={*}

Select(S’→ε)=Follow(s’)={#}

Select(S’→*aTS’)∩Select(S’→ε)=ФSelect(T→+aT’)={+}

Select(T’→T)=First(T)={+}

Select(T’→ε)=Follow(T’)={*,#}

Select(T’→T)∩Select(T’→ε)=Ф所以該文法是LL(1)文法。預計分析表：*+a#S→*aTS’→aTS’第22頁共6頁

S’→*aTS’TT’→ε→ε→ε→+aT’→T6設文法G為：S→A；A→BA|ε；B→aB|b

解：（1）拓廣文法G’：(0)S’→S(1)S→A(2)A→BA(3)A→ε(4)

B→aB(5)B→b；FIRST(A)={ε,a,b}；FIRST(B)={a,b}

構造的DFA如下:

項目集規(guī)范族看出，不存在沖突動作?！嘣撐姆ㄊ荓R(1)文法。

（2）LR(1)分析表如下：

(3)輸入串a(chǎn)bab的分析過程為：

第23頁共6頁

簡答題3、設有文法G[S]:S→S(S)S|ε，該文法是否為二義文法？說明理由。答：是二義的，由于對于（）（）可以構造兩棵不同的語法樹。SS

S(S)SS(S)S

εεS(S)SS(S)Sεε

εεεεεε

五、給定文法G[S]：

S→aA|bQ；A→aA|bB|b；B→bD|aQ；Q→aQ|bD|b；D→bB|aA；E→aB|bF

F→bD|aE|b

構造相應的最小的DFA。

解：先構造其NFA：用子集法將NFA確定化：

SAQBZDZDBaAAQQAAQbQBZDZDBBD

第24頁共6頁

將S、A、Q、BZ、DZ、D、B重新命名，分別用0、1、2、3、4、5、6表示。由于3、4中含有z，所以它們?yōu)榻K態(tài)。

令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b進行分割：

P1＝（｛0,5,6｝,｛1,2｝,｛3,4｝）再用b進行分割：P2＝（｛0｝,｛5,6｝,｛1,2｝,｛3,4｝）再用a、b進行分割，仍不變。再令｛０｝為A，｛1，2｝為B，｛3，4｝為C，｛5，6｝為D。最小化為右上圖。

六、對文法G(S)：S→a|^|(T)；T→T，S|S

答：(1)

FIRSTVT(S)?{a,^,(}FIRSTVT(T)?{,,a,^,(}

LASTVT(S)?{a,^,)}LASTVT(T)?{,,a,^,)}a^)a^(),#>>>>>>=>>>>#)歸約)#(=)移進#)>#歸約#接受第25頁共6頁

《編譯原理》期末試題（四）

一、簡述編譯程序的工作過程。（10）

編譯程序的工作過程，是指從輸入源程序開始到輸出目標程序為止的整個過程，是十分繁雜的，就其過程而言，一般可以劃分為五個工作階段：①詞法分析，對構成源程序的字符串進行掃描和分解，識別出一個個的單詞；②語法分析，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位；③語義分析與中間代碼產(chǎn)生，即對各類語法單位，分析其漢一并進行初步翻譯；④代碼優(yōu)化，以期產(chǎn)生更高效的代碼；⑤目標代碼生成，把中間代碼變換成特定機器上的低級語言指令形式。

二、構造以下正規(guī)式相應的DFA（用狀態(tài)轉(zhuǎn)換圖表示）（15）（1）1（0|1）*1

0,1（2）0*10*10*10*1（3）letter（letter|digit）*

（1）

（2）

(3)

100201121301314015letterletter12digit三、給出下面語言的相應文法：（15）

L1={anbn|n≥1}L2={anbm+nam|n≥1，m≥0}

G1：

A→aAb|ab

G1：S→AB

第26頁共6頁

A→aAb|abB→bBa|ε

四、對下面的文法G：

S→a|b|（T）T→T，S|S

(1)消去文法的左遞歸，得到等價的文法G2；

(2)判斷文法G2是否LL（1）文法，假使是，給出其預計分析表。（15）G2：

S→a|b|（T）

T→ST’

T’→，ST’|εG2是LL（1）文法。STT’aS→abS→b（），#S→（T）T→ST’T→ST’T→ST’T’→εT’→，ST’五、設有文法G[A]：A→BCc|gDB

B→bCDE|εC→DaB|caD→dD|εE→gAf|c

(1)計算該文法的每一個非終結(jié)符的FIRST集和FOLLOW集；(2)試判斷該文法是否為LL（1）文法。（15）ABCDEFIRSTA,b,c,d,gbA,c,dDC,gFOLLOWA,c,dC,d,gA,b,c,g是LL（1）文法。

六、對表達式文法G：

E→E+T|TT→T*F|FF→(E)|I

（1）造各非終結(jié)符的FIRSTVT和LASTVT集合；（2）構造文法的算符優(yōu)先關系表。（15）

第27頁共6頁

ETF

算符優(yōu)先關系表+*I（）#+>>>>>>=>#>>>>=七、有定義二進制整數(shù)的文法如下：

L→LB|BB→0|1

構造一個翻譯模式，計算該二進制數(shù)的值（十進制的值）。（15）引入L、B的綜合屬性val，翻譯模式為：S→L{print(L.val)}

L→L1B{L.val=L1.val*2+B.val}L→B{L.val=B.val}B→0{B.val=0}B→1{B.val=1}

第28頁共6頁

《編譯原理》期末試題（五）

一、單項選擇題(共10小題，每題2分，共20分)

1．語言是

A．句子的集合B．產(chǎn)生式的集合C．符號串的集合D．句型的集合2．編譯程序前三個階段完成的工作是A．詞法分析、語法分析和代碼優(yōu)化B．代碼生成、代碼優(yōu)化和詞法分析

C．詞法分析、語法分析、語義分析和中間代碼生成D．詞法分析、語法分析和代碼優(yōu)化

3．一個句型中稱為句柄的是該句型的最左

A．非終結(jié)符號B．短語C．句子D．直接短語4．下推自動機識別的語言是

A．0型語言B．1型語言C．2型語言D．3型語言

5．掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即

A．字符B．單詞C．句子D．句型6．對應Chomsky四種文法的四種語言之間的關系是A．L0?L1?L2?L3B．L3?L2?L1?L0C．L3=L2?L1?L0D．L0?L1?L2=L37．詞法分析的任務是

A．識別單詞B．分析句子的含義C．識別句子D．生成目標代碼8．常用的中間代碼形式不含

A．三元式B．四元式C．逆波蘭式D．語法樹9．代碼優(yōu)化的目的是

A．節(jié)省時間B．節(jié)省空間

C．節(jié)省時間和空間D．把編譯程序進行等價交換10．代碼生成階段的主要任務是A．把高級語言翻譯成匯編語言B．把高級語言翻譯成機器語言

C．把中間代碼變換成依靠具體機器的目標代碼D．把匯編語言翻譯成機器語言

二、填空題（本大題共5小題，每題2分，共10分）

1．編譯程序首先要識別出源程序中每個(單詞)，然后再分析每個(句子)并翻譯其意義。2．編譯器常用的語法分析方法有(自底向上)和(自頂向下)兩種。

3．尋常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的(綜合)。

第29頁共6頁

4．程序設計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分派)方案和(動態(tài)存儲分派)方案。

5．對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目標程序)。

三、名詞解釋題(共5小題，每題4分，共20分)

1．詞法分析

詞法分析的主要任務是從左向右掃描每行源程序的符號，依照詞法規(guī)則從構成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。2．LL(1)文法

若文法的任何兩個產(chǎn)生式A??|?都滿足下面兩個條件：（1）FIRST(?)?FIRST(?)=?；

（2）若??*?，那么FIRST(?)?FOLLOW(A)=?。

我們把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個L代表從左向右掃描輸入，其次個L表示產(chǎn)生最左推導，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3．語法樹

句子的樹結(jié)構表示法稱為語法樹(語法分析樹或語法推導樹)。給定文法G=(VN，VT，P，S)，對于G的任何句型都能構造與之關聯(lián)的語法樹。這棵樹具有以下特征：(1)根節(jié)點的標記是開始符號S。

(2)每個節(jié)點的標記都是V中的一個符號。(3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標記從左向右的排列次序為A1A2…AR，那么A?A1A2…AR一定是P中的一條產(chǎn)生式。(4)若一標記為A的節(jié)點至少有一個除它以外的子孫，則A?VN。(5)若樹的所有葉節(jié)點上的標記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。4．LR(0)分析器

所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作(是移進還是按某一產(chǎn)生式進行歸約等)。

5．語言和文法

文法就是語言結(jié)構的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：

G=(VN，VT，P，S)其中：VN是非空有窮集合，稱為非終結(jié)符號集合；VT是非空有窮集合，稱為終結(jié)符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。這里，VN∩VT=?，S?VN。V=VN∪VT，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號的集合。第30頁共6頁

文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即

L(G)={x|S?*x，其中S為文法開始符號，且x?VT?}簡單的說，文法描述的語言是該文法一切句子的集合。

四、簡答題(共4小題，每題5分，共20分)

1．編譯程序和高級語言有什么區(qū)別?

用匯編語言或高級語言編寫的程序，必需先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標程序，也就是機器語言。

編譯程序的工作狀況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，依照一一對應的關系，轉(zhuǎn)換成用機器語言表示的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句，先解釋成為一組機器語言的指令，然后馬上執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的\對話\，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快，在過程中，不能進行人機對話修改。FORTRAN語言就是編譯型高級語言。2．編譯程序的工作分為那幾個階段?

詞法分析、語法分析和語義分析是對源程序進行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合(稱為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價的目標程序。3．簡述自下而上的分析方法。

所謂自下而上分析法就是從輸入串開始，逐步進行“歸約〞，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約〞，直到根節(jié)點。4．簡述代碼優(yōu)化的目的和意義。

代碼優(yōu)化是盡量生成“好〞的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果一致的前提下，盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間少。

五、綜合應用題(共3小題，每題10分，共30分)

1．證明下述文法G：

S?aSbS|aS|d

是二義性文法。解：

一個文法，假使存在某個句子有不只一棵語法分析樹與之對應，那么稱這個文法是二義性文法。

句子aadbd有兩棵語法樹。如下圖：SSaSSaSbaSd第31頁共6頁daSd

bSd

(1)(2)

由此可知，S?aSbS|aS|d定義的文法是二義性文法。2．對于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短語、直接短語和句柄？

S

句型baSb的語法樹如圖五(2)所示。

AB

bBSb

a解：baSb為句型baSb的相對于S的短語，ba為句型baSb的相對于A的短語，Sb為句型baSb的相對于B的短語，且為直接短語，a為句型baSb的相對于B的短語，且為直接短語和句柄。

3．設有非確定的有自限動機NFAM=({A，B，C}，{0，1}，?，{A}，{C})，其中：?(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)換距陣為：?ABC狀態(tài)轉(zhuǎn)換圖為

0C??1A，BCC11AB11C10《編譯原理》期末試題（六）

編譯原理樣題

1．____型文法也稱為正規(guī)文法。

[A]0[B]1[C]2[D]3

第32頁共6頁

2．____文法不是LL(1)的。

[A]遞歸[B]右遞歸[C]2型[D]含有公共左因子的3．文法E→E+E|E*E|i的句子i*i+i*i的不同語法分析樹的總數(shù)為______。

[A]1[B]3[C]5[D]74．四元式之間的聯(lián)系是通過實現(xiàn)。

[A]臨時變量[B]指示器[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的逆波蘭表示為。

[A]a-b@c*[B]ab@c*-[C]ab@-[D]ab@c-*（注：@為單

目減運算符）

8．過程的DISPLAY表記錄了。

[A]過程的連接數(shù)據(jù)[B]過程的嵌套層次[C]過程的返回地址[D]過程的入口地址

二填空題

3．對于文法G1和G2，若有L(G1)=L(G2)（或G1和G2的語言一致），則稱文法G1和G2是等價的。

4．對于文法G[E]：E→T|E+TT→F|T*FF→P^F|PP→(E)|i，句型T+T*F+i的句柄是T，最左素短語是T*F。5．最右推導的逆過程稱為規(guī)范歸約，也稱為最左歸約。

6．規(guī)范規(guī)約中的可規(guī)約串是句柄，算符優(yōu)先分析中的可規(guī)約串是最左素短語7．（A∨B）∧（C∨?D∧E）的逆波蘭式是ＡＢ∨ＣＤ?Ｅ∧∨∧。8．在屬性文法中文法符號的兩種屬性分別稱為繼承屬性和綜合屬性（次序可換）。9．符號表的每一項為哪一項由名字欄和地址分派兩個欄目組成。在目標代碼生成階段，符號表是地址分派的依據(jù)。

10．一個過程的DISPLAY表的內(nèi)容是它的直接外層的DISPLAY表的內(nèi)容加上本過程的SP的地址

三有窮自動機M接受字母表?＝{0,1}上所有滿足下述條件的串：每個1都有0直接跟在右邊。構造一個最小的DFAM及和M等價的正規(guī)式。

第33頁共6頁

四證明正規(guī)式(ab)*a與正規(guī)式a(ba)*等價（用構造他們的最小的DFA方法）。

五寫一個文法，使其語言是：

L＝{1n0m1m0n|m,n≥0}

五文法G：S→1S0|A

A→0A1|ε

六對文法G[S]

S→aSb|P

P→bPc|bQc

第34頁共6頁

Q→Qa|a

(1)它是否是算符優(yōu)先文法？請構造算符優(yōu)先關系表

(2)文法G[S]消除左遞歸、提取左公因子后是否是LL（1）文法？請

證明。

1.求出G[S]的FIRSTVT集和LASTVT集：

FIERSTVT（S）={a,b}LASTBVT（S）={b,c}

FIERSTVT(P)=LASTBVT（P）={c}FIERSTVT(Q)={a}LASTBVT（Q）={a}構造優(yōu)先關系表為：

abcabc>>>由于在優(yōu)先關系中同時出現(xiàn)了aa以及bb，所以該文法不是算符優(yōu)先文法。

2.消除左遞歸和提取左公因子后的文法為：

S→aSb|PP→bP’P’→Pc|QcQ→aQ’Q’→aQ’|ε

求具有一致左部的兩個產(chǎn)生式的Select集的交集：

Select(S→aSb)∩Select(S→P)={a}∩First(P)={a}∩=Ф

Select(P’→Pc)∩Select(P’→Qc)=First(P)∩First(Q)=∩{a}=ФSelect(Q’→aQ’)∩Select(Q’→ε)={a}∩Follow(Q)={a}∩{c}=Ф所以修改后的文法是LL（1）文法。

七已知文法G為:

（0）S′→S（1）S→aAd（2）S→bAc（3）S→aec（4）S→bed（5）A→e

試構造它的LR（1）項目集、可歸前綴圖和LR（1）分析表。SI1：S′→S·,I0:#S′→·S,d#aAI4：S→aA·d,I8：S→aAd·,I2：S→·aAd,#S→a·Ad,##eI：S→ae·S→a·ec,#c,cI：5,9S→aec·S→·bAc,A→·e,d###A→e·,dS→·aec,I10：b#I3:S→b·Ac,#AS→bAc·,第35頁共6頁I6:S→bA·c,#cS→b·ed,#A→·e,c#eI7：S→be·d,

構造LR(1)分析表如下：

abcde#SA

S2S301

1ac

cS52S73

S84

S9r55

S106

r5S117

r18

r39

r210r411八已知源程序如下：prod:=0;i:=1;

whilei≤20dobegin

prod:=prod+a[i]*b[i];i:=i+1

end;

試按語法制導翻譯法將源程序翻譯成四元式序列（設A是數(shù)組a的起始地址，B是數(shù)組b的起始地址；機器按字節(jié)編址，每個數(shù)組元素占四個字節(jié)）。

狀態(tài)actiongoto第36頁共6頁

九設有以下程序段

procedureP(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

十對以下文法，請寫出關于括號嵌套層數(shù)的屬性文法。(為S,L引入屬性h,用來

記錄輸出配對的括號個數(shù))文法規(guī)則S→(T)S→iT→T,ST→S語義規(guī)則第37頁共6頁

答案：

十一對PL/0語言的while語句while條件BDO語句S的編譯程序，

請在空缺處填空，完成該語句的編譯算法：switch(SYM){??caseWHILESYM:

CX1=CX;

GetSym();

CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);

CX2=CX;

GEN(JPC,0,0);if(SYM==DOSYM)

elseError(18);

STATEMENT(FSYS,LEV,TX);GEN(JMP,0,CX1);

GetSym();

CODE[CX2].A=CX；break;??}

《編譯原理》期末試題（七）

一、回復以下問題：(30分)

1．什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關系？解答：

S-屬性文法是只含有綜合屬性的屬性文法。（2分）

L-屬性文法要求對于每個產(chǎn)生式A?X1X2…Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj的一個繼承屬性，且該屬性僅依靠于：

（1）產(chǎn)生式Xj的左邊符號X1,X2…Xj-1的屬性；

（2）A的繼承屬性。（2分）S-屬性文法是L-屬性文法的特例。（2分）