編譯原理期末復習題(含答案)

編譯原理期末復習題（含答案）

第八節(jié)習題一、單項選擇題

1、將編譯程序分成若干個“遍”是為了。

a.提高程序的執(zhí)行效率

b.使程序的結(jié)構更加清晰

c.利用有限的機器內(nèi)存并提高機器的執(zhí)行效率

d.利用有限的機器內(nèi)存但降低了機器的執(zhí)行效率

2、構造編譯程序應掌握

a.源程序b.目標語言

c.編譯方法d.以上三項都是

3、變量應當。

a.持有左值b.持有右值

c.既持有左值又持有右值d.既不持有左值也不持有右值

4、編譯程序絕大多數(shù)時間花在

a.出錯處理b.詞法分析

c.目標代碼生成d.管理表格

5、不可能是目標代碼。

a.匯編指令代碼b.可重定位指令代碼

c.絕對指令代碼d.中間代碼

6、使用

a.語義規(guī)則b.詞法規(guī)則

c.產(chǎn)生規(guī)則d.詞法規(guī)則

7、詞法分析器的輸入是

a.單詞符號串b.源程序

c.語法單位d.目標程序

8、中間代碼生成時所遵循的是。

a.語法規(guī)則b.詞法規(guī)則

c.語義規(guī)則d.等價變換規(guī)則

9、編譯程序是對

a.匯編程序的翻譯b.高級語言程序的解釋執(zhí)行

c.機器語言的執(zhí)行d.高級語言的翻譯

10、語法分析應遵循

a.語義規(guī)則b.語法規(guī)則

c.構詞規(guī)則d.等價變換規(guī)則

解答

1、將編譯程序分成若干個“遍”是為了使編譯程序的結(jié)構更加清晰，故選b。

2、構造編譯程序應掌握源程序、目標語言及編譯方法等三方面的知識，故選d。

3、對編譯而言，變量既持有左值又持有右值，故選c?

4、編譯程序打交道最多的就是各種表格，因此選d。

5、目標代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是目

標代碼的只能選d。

6、詞法分析遵循的是構詞規(guī)則，語法分析遵循的是語法規(guī)則，中間代碼生成遵循的是

語義規(guī)則，并且語義規(guī)則可以定義一個程序的意義。因此選a。

7、b8、c9、d10、c二、多項選擇題

1、編譯程序各階段的工作都涉及到

a.語法分析b.表格管理c.HI錯處理

d.語義分析e.詞法分析

2、編譯程序工作時，通常有階段。

a.詞法分析b.語法分析c.中間代碼生成

d.語義檢查e.目標代碼生成

解答

1.b、c2.a、b、c、e

三、填空題

1、解釋程序和編譯程序的區(qū)別在于

2、編譯過程通常可分為5個階段，分別是、語法分析、代碼優(yōu)化和目標代碼生成。

3、編譯程序工作過程中，第一段輸入是，最后階段的輸出為程序。

4、編譯程序是指將

解答

是否生成目標程序2、詞法分析中間代碼生成3、源程序目標代碼生成4、源程序

目

標語言

一、單項選擇題

1、文法G；S-xSx|y所識別的語言是na.xyxb.(xyx)*c.xyx(n2O)d.x*yx*

2、文法G描述的語言L(G)是指。+a,aGV*}*a,aGV*}a.L(G)={a|S今b.

L(G)={a|S今TT*+c.L(G)={a|S0a,aC(VTUVN*)}d.L(G)={aS0a,

ae(VTUVN*)}

3、有限狀態(tài)自動機能識別。

a.上下文無關文法b.上下文有關文法

c.正規(guī)文法d.短語文法

4、設G為算符優(yōu)先文法，G的任意終結(jié)符對a、b有以下關系成立

a.若f(a)>g(b),則a>bb.若f(a)<g(b),則a〈b

c.a-b都不一"定成立d.a~b一定成立

5、如果文法G是無二義的，則它的任何句子a

a.最左推導和最右推導對應的語法樹必定相同

b.最左推導和最右推導對應的語法樹可能不同

c.最左推導利最右推導必定相同

d.可能存在兩個不同的最左推導，但它們對應的語法樹相同

6、由文法的開始符經(jīng)0步或多步推導產(chǎn)生的文法符號序列是。

a.短語b.句柄c.句型d.句子

7、文法G：E-E+T|T

T-T*P|P

P-(E)11

則句型P+T+i的句柄和最左素短語為。

a.P+T和ib.P和P+Tc.i和P+T+id.P和T

8、設文法為:S-SA|A

A-*a|b

則對句子aba,下面是規(guī)范推導。

a.SSASAAAAAaAAabAaba

b.SSASAAAAAAAaAbaaba

c.SSASAASAaSbaAbaaba

d.SSASaSAaSbaAbaaba

9、文法G：S-b|A(T)

TT,S|S

則FIRSTVT(T)。

a.{b,A,(}b.{b,A,))

10、產(chǎn)生正規(guī)語言的文法為c.{b,八，(,，}d,{b,八,)，，}a.0型b.1型c.2型d.

3型

11、采用自上而下分析，必須。

a.消除左遞歸b.消除右遞歸c.消除回溯d.提取公共左因子

12、在規(guī)范歸約中，用

a.直接短語b.句柄c.最左素短語d.素短語

13、有文法G：E-E*T|T

T-T+i|i

句子1+2*8+6按該文法G歸約，其值為。

a.23B.42c.30d.17

14、規(guī)范歸約指。

a.最左推導的逆過程b.最右推導的逆過程

c.規(guī)范推導d.最左歸約的逆過程

［解答］

1、選c。

2、選a。

3、選Co

4、雖然a與b沒有優(yōu)先關系，但構造優(yōu)先函數(shù)后，a與b就一定存在優(yōu)先關系了。所

以，由f(a)>g)(b)或f(a)<g(b)并不能判定原來的a與b之間是否存在優(yōu)先關系：故選

Co

5、如果文法G無二義性，則最左推導是先生長右邊的枝葉：對于d,如果有兩個不同的

是了左推導，則必然有二義性。故選a。

6、選Co

7、由圖2-8-1的語法樹和優(yōu)先關系可以看出應選b。

8、規(guī)范推導是最左推導，故選d。

9、由T-T,”和T-(,,得FIRSTVT(T))={(,,)}；

由TfS得FIRSTVT(S)CFIRSTVT(T),而FIRSTVT(S)={b,A,(}；即

FIRSTVT(T)={b,A,(,,)；因此選c。

10、d11、c12、b13、b14、b

二、多項選擇題

1、下面哪些說法是錯誤的。

a.有向圖是一個狀態(tài)轉(zhuǎn)換圖b.狀態(tài)轉(zhuǎn)換圖是一個有向圖

c.有向圖是一個DFAd.DFA可以用狀態(tài)轉(zhuǎn)換圖表示

2、對無二義性文法來說，一棵語法樹往往代表了

a.多種推導過程b.多種最左推導過程c.一種最左推導過程

d.僅一種推導過程e.一種最左推導過程

3、如果文法G存在一個句子，滿足下列條件之一?時，則稱該文法是二義文法。a.該

句子的最左推導與最右推導相同

b.該句子有兩個不同的最左推導

c.該句子有兩棵不同的最右推導

d.該句子有兩棵不同的語法樹

#v+xvi>#

圖2-8-1句型P+T+I的講法及優(yōu)先關系

e.該句子的語法樹只有一個

4、有一文法G：S-AB

A-aAb|￡

B-cBd|E

它不產(chǎn)生下面集合。

a.{anbmcndm|n,m^O}b.{anbncmdm)n,m>0)

c.{anbmcmdn|n,m>0}d.{anbncmdm|n,m^O)

e.{anbncndn|n20}

5、自下而上的語法分析中，應從

a.句型b.句子c.以單詞為單位的程序

d.文法的開始符e.句柄

6、對正規(guī)文法描述的語言，以下

a.0型文法b.1型文法c.上下文無關文法d.右線性文法e.左線性文法解答1、e、

a、c2、a、c、e3、b、c、d4、a、c5、b、c6、a、b、c>d、e

三、填空題

1、文法中的終結(jié)符利非終結(jié)符的交集是是，它一定只出現(xiàn)在產(chǎn)生式的部。

2、最左推導是指每次都對句型中的

3、在語法分析中，最常見的兩種方法一定是分析法。

4、采用

5、樹代表推導過程，樹代表歸約過程。

6、自下而上分析法采用等四種操作。

7、Chomsky把文法分為和生和語言，并分別用和自動機識別所產(chǎn)生的語言。

解答1、空集終結(jié)符右

2、最左

3^自上而上自下而上

4、自上而上

5、語法分析

6、移進接受

7、42型3型上下文無關語言正規(guī)語言下推自動機有限

四、判斷題

1、文法SfaS|bR|＞描述的語言是（a|be）*（）

R-cS

2、在自下而上的語法分析中，語法樹與分析樹一定相同。（）

3、二義文法不是上下文無關文法。（）

4、語法分析時必須先消除文法中的左遞歸。（）

5、規(guī)范歸約和規(guī)范推導是互逆的兩個過程。（）

6、一個文法所有句型的集合形成該文法所能接受的語言。（）

解答1、對2、偌3、錯4、錯5、錯6、錯

五、簡答題

1、句柄2、素短語3、語法樹4、歸約5、推導

［解答］

1、句柄：一個句型的最左直接短語稱為該句型的句柄。

2、素短語：至少含有一個終結(jié)符的素短語，并且除它自身之外不再含任何更小的素短

語。

3、語法樹：滿足下面4個條件的樹稱之為文法G［S］的一棵語法樹。

①每一終結(jié)均有一標記，此標記為VNUVT中的一個符號；

②樹的根結(jié)點以文法G［S］的開始符S標記；

③若一結(jié)點至少有一個直接后繼，則此結(jié)點上的標記為VN中的一個符號；

④若一個以A為標記的結(jié)點有K個直接后繼，且按從左至右的順序，這些結(jié)點的標記分

別為X1,X2,,,,XK,則A-X1,X2,,,,XK,必然是G的一個產(chǎn)生式。

4、歸約：我們稱aY3直接歸約出aAB,僅當A-Y是一個產(chǎn)生式，且a、

BG(VNUVT)*。歸約過程就是從輸入串開始，反復用產(chǎn)生式右部的符號替換成產(chǎn)生式左

部符號，直至文法開始符。

5、推導：我們稱aAB直接推出a丫B,即aABay6,僅當A-Y是一個產(chǎn)生

式，且a、BG(VNUVT)*。如果a1a2?an,則我們稱這個序列是從a1至a2

的一個推導。若存在一個從alan的推導，則稱a1可推導出an。推導是歸約的逆過

程。

六、問答題

1、給出上下文無關文法的定義。

［解答］

一個上下文無關文法G是一個四元式(VT,VN,S,P),其中：

?VT是一個非空有限集，它的每個元素稱為終結(jié)符號；

?VN是一個非空有限集，它的每個元素稱為非終結(jié)符號，VTAVN=①；

?S是一個非終結(jié)符號，稱為開始符號;

?P是一個產(chǎn)生式集合（有限），每個產(chǎn)生式的形式是P-a,其中，PSVN,

a6（VTUVN）*o開始符號S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。

2、文法G［S］：

S-aSPQ|abQ

QP-PQ

bP-bb

bQ-be

cQ-cc

（1）它是Chomsky哪一型文法？

（2）它生成的語言是什么？

［解答］

（1）由于產(chǎn)生式左部存在終結(jié)符號，且所有產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式

右部的符號長度，所以文法G［S］是Chomskyl型文法，即上下文有關文法。

（2）按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低（否則無法推出句子），我們可以得

到：

SabQabc

SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc

SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQ

aaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc

，，，，

于是得到文法G［S］生成的語言L={anbnen|n>l}

3、按指定類型，給出語言的文法。

L={aibj|的上下文無關文法。

【解答】

(1)由1=卜18仃＞121｝知，所求該語言對應的上下文無關文法首先應有S-aSb型產(chǎn)

生式，以保證b的個數(shù)不少于a的個數(shù)；其次，還需有S-Sb或S-bS型的產(chǎn)生式，用以

保證b的個數(shù)多于a的個數(shù)；也即所求上下文無關文法G[S]為：

G[S]：S-aSb|Sb|b

4、有文法G：S-aAcB)Bd

A-*AaB|c

B-bScA|b

(1)試求句型aAaBcbbdcc和aAcbBdcc的句柄：

(2)寫出句子acabcbbdcc的最左推導過程。

【解答】(1)分別畫出對應兩句型的語法樹，如圖2-8-2所示

句柄:AaBBd

s

dC

(b)

s

//、

aAcB

/l\/N

Bd

b

(a)

圖2-8-2語法樹

(2)句子acabcbbdcc的最左推導如下：

SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA

acabcbbdcAacabcbbdcc

5、對于文法G[S]：

S-(L)|aS|aL-L,S|S

(1)畫出句型(S,(a))的語法樹。(2)寫出上述句型的所有短語、直接短語、句

柄和素短語。

【解答】(1)句型(S,(a)(2)由圖2-8-3可知：

①短語：S、a、(a)、S,(a)>②直接短語:a、S；

r接短語和句柄e

/\

/K

,句型。f\

P7[<

T*F

圖2-8-4句型T*Pt(T*F)的語法樹

③句柄：s；

#<?,<(<a>)>)>#

因此素短語為a。

6、考慮文法G[T]：

T-T*F|F

F-FtP|P

P-(T)|i

證明T*Pt(T*F【解答】首先構造T*Pt(T*F)的語法樹如圖2-8-4由圖2-8-4可

知，T*Pt(T*F)是文法G[T]直接短語有兩個，即P和T*F；句柄為P。

一、單項選擇題

1、詞法分析所依據(jù)的是

a.語義規(guī)則b.構詞規(guī)則c.語法規(guī)則d.等價變換規(guī)則

2、詞法分析器的輸出結(jié)果是。

a.單詞的種別編碼b.單詞在符號表中的位置

C.單詞的種別編碼和自身值d.單詞自身值

3、正規(guī)式Ml和M2等價是指。

a.Ml和M2的狀態(tài)數(shù)相等b.Ml和M2的有向弧條數(shù)相等

S

9283所示/|\

(L)

s小

I

S

;I

a

圖2-8-3句型(S,(a))的語法樹

c.Ml和M2所識別的語言集相等d.Ml和M2狀態(tài)數(shù)和有向弧條數(shù)相等

4、狀態(tài)轉(zhuǎn)換圖(見圖3-6-1)接受的字集為

a.以0開頭的二進制數(shù)組成的集合b.以0結(jié)尾的二進制數(shù)組成的集合

c.含奇數(shù)個0的二進制數(shù)組成的集合d.含偶數(shù)個0的二進制數(shù)組成的集合

5、詞法分析器作為獨立的階段使整個編譯程序結(jié)構更加簡潔、明確，因此，。

a.詞法分析器應作為獨立的一遍b.詞法分析器作為子程序較好

c.詞法分析器分解為多個過程，由語法分析器選擇使用d.詞法分析器并不作為一個

獨立的階段解答1、b2、c3、c4、d5、b

二、多項選擇題

1、在詞法分析中，能識別出。

a.基本字b.四元式c.運算符

d.逆波蘭式e.常數(shù)

2、令E={a,b},則E上所有以b開頭，后跟若干個ab的字的全體對應的正規(guī)式為。a.

b(ab)*b.b(ab)+c.(ba)*b+d.(ba)be.b(a|b)

解答1、a、c^e2、a、b、d

三、填空題

1、確定有限自動機DFA是

2、若二個正規(guī)式所表示的

3、一個字集是正規(guī)的，當且僅當它可由所

解答1、NFA2、正規(guī)集3、DFA(NFA)所識別

四、判斷題

1、一個有限狀態(tài)自動機中，有且僅有一個唯一終態(tài)。()

2、設r和s分別是正規(guī)式，則有L(r|s)=L(r)|L(s).()

3、自動機M和M'的狀態(tài)數(shù)不同，則二者必不等價。()

4、確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。()

5、對任意一個右線性文法G,都存在一個NFAM,滿足L(G)=L(M)。()

6、對任意一個右線性文法G,都存在一個DFAM,滿足L(G)=L(M)。()

7、對任何正規(guī)表達式e,都存在一個NFAM,滿足L(G)=L(e)。()

8、對任何正規(guī)表達式e,都存在一個DFAM,滿足L(G)=L(e)。()

解答1、2、3、錯4、5、6、7、8、正確

五、基本題

1、設吊=({x,y},{a,b},f,x,{y})為一非確定的有限自動機,其中f定義如下:

f(x,a)={x,y}f(x,b)={y}

f(y,a)=4>f(y,b)={x,y}

試構造相應的確定有限自動機M'。

解答：對照自動機的定義M=(S,E,f,SO,Z),由f的定義可知f(x,a)、f(y,b)均為多值

函數(shù)，所以是一非確定有限自動機，先畫出NFAM相應的狀態(tài)圖，如圖3-6-2所示。

W_________________M

bl二

圖3-6-2NFAM

將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。表3-6-4狀

態(tài)轉(zhuǎn)換矩陣

圖3-6-6化簡后的DFAM'

即得到M'={0,1,2},{a,b},f,0,{1,2}),其狀態(tài)轉(zhuǎn)換圖如圖3-6-5所示。

將圖3-6-5的DFAM'最小化。首先，招M'的狀態(tài)分成終態(tài)組{1,2}與非終態(tài)組{0}；

其次,考察{1,2}。由于{l,2}a={l,2}b={2}U{l,2},所以不再將其劃分了,也即整個劃

分只有兩組{0},{1,2}：令狀態(tài)1代表{1,2},即把原來到達2的弧都導向1,并刪除狀態(tài)

2。最后，得到如圖3-6-6所示化簡DFAM'。

2、對給定正規(guī)式b*(dad)(b|ab)+,構造其NFAM；

解答:首先用A+=AA*改造正規(guī)式得:b*(d|ad)(b|ab)(b|ab)*;其次，構造該正規(guī)式的

NFAM,如圖3-6-7所示。

{x，y}{x,y}

a

02

1—

22

圖3-6-7的NFAM

1、構造下面文法的LL(1)分析表。

D-TL

T-*int|realL-*idRR-?,idR|e

解答：LL(1)分析表見表4-3-1

分析雖然這個文法很簡單，我們還是從求開始符號集合和后繼符號集合開始。

FIRST(D)=FIRST(T)={int,real}FOLLOW(D)=FOLLOW(L)={#}

FIRST(L)={id}FOLLOW(T)={id}FIRST(R)={,,e}FOLLOW(R)={#}

有了上面每個非終結(jié)符的FIRST集合，填分析表時要計算一個產(chǎn)生式右部。的FIRST

(a)就不是件難事了。

填表時唯一要小心的時，￡是產(chǎn)生式R-e右部的一個開始符號，而#在FOLLOW(R)

中，所以R-e填在輸入符號#的欄目中。

表4-3-1LL(1)分析表

非終結(jié)符輸入符號

hitrealid

DDTLDTL

TT-intT-*real

LL-idR

RR-*,ic

2、下面文法G[S]是否為LL(1)文法？說明理由。

SABPQxA->xyB->bcP->dPsQ-*aQ￡

解答：該文法不是LL(1)文法，見下面分析中的說明。分析只有三個非終結(jié)符有兩

個選擇。

1、P的兩個右部dP和e的開始符號肯定不相交。

2、Q的兩個右部aQ和e的開始符號肯定不相交。

3、對S來說，由于xCFIRST(AB),同時也有xGFIRST(PQx)(因為P和Q都可

能為空)。所以該文法不是LL(1)文法。3、設有以下文法：

G[S]：S-aAbDe|dA-BSD|eB--SAc|cDeD-See

(1)求出該文法的每個非終結(jié)符U的FOLLOW集。(2)該文法是LL(1)文法嗎？

(3)構造C[S]的LL(1)分析表。

解答：(1)求文法的每一個非終結(jié)符U的FOLLOW集的過程如下：因為：

①S是識別符號，且有A-BSD、BfSAc、D-Se,所以FOLLOW(S)應包含

FIRST(D)UFIRST(Ac)UFIRST(e)U{#}={a,d}U{a,d,c,e}U{e}U{#}={a,c,d,e#}

②又因為A-BSD和D-e,所以FOLLOW中還包含F(xiàn)OLLOW(A)?因為S-aAbDe和

BfSAc,所以

=FIRST(bDe)UFIRST(c)={b,c}

綜合①、②得FOLLOW(S)={a,d,c,e,#}U{a,b,c,d,e,#}

因為AfBSD,所以FOLLOW(B)-FIRST(SD)={a,d}因為SfaAbDe|d、A-*BSDe

和B-SAc|cD,所以=FIRST(e)UFOLLOW(A)UFOLLOW(B)

={e}U{b,c}U{a,d}={a,b,c,d,e}(2)G[S]不是LL(1)文法。因為產(chǎn)生式

B-'-SAc|cD|e中

FIRST(SAc)nFOLLOW(B)={a,d}W0(3)構造G[S]的LL(1)分析表。

按照LL(1)分析表的構造算法構造方法G[S]的LL(1)分析表如表4-3-2所示。

abc(1e

saAbDed

ABSDBSDBSDe

BSac/gcDSac/c

DSe/eeeSe/￡￡

G[V]：V-N|N[E]E-V|V+EN-i

解答：對文法G[V]提取公共左因子后得到文法：G'[V]：V-NA

A-e[E]E-*VBB-e|+EN-i

求出文法G'[V]中每一個非終結(jié)符號的FIRST集：FIRST(V)={i}FIRST(A)={[,e}

FIRST(E)={i}FIRST(B)={+,e}FIRST(N)={i}

求出文法G'[V]中每一個非終結(jié)符號的FOLLOW集：

FOLLOW(V)={#}UFIRST(B)\{e}UFOLLOW(E)={#,+,]}FOLLOW(A)=FOLLOW(V)={+,,#}

FOLLOW(E)=FIRST(])\{e}UFOLLOW(B)=FIRST(])\{e}UFOLLOW(E)={]}FOLLOW(B)=

FOLLOW(E)={]}FOLLOW(N)=FIRST(A)\{e}UFOLLOW(V)={[,],+,#}可以看到,對文法

G'[V]的產(chǎn)生式Afe|[E],有FIRST([E])nFOLLOW(A)={[}G{+,],#}=0對產(chǎn)生式

Bfe|+E,有FIRST(+E)BFOLLOW(B)={+}Cl{]}=0

而文法的其他產(chǎn)生式都只有一個不為￡的右部，所以文法G，［V］是LL(1)文法。5、

已知文法：G［A］：A-*aAa|e

(1)該文法是LL(1)文法嗎？為什么？

(2)若采用LL(1)方法進行語法分析，如何得到該文法的LL(1)分析表？(3)若

輸入符號串“aaaa”，請給出語法分析過程。解答：(1)因為產(chǎn)生式A~aAa|￡有空產(chǎn)

生式右部，而FOLLOW(A)=悔}UFIRST(a)={a,#}

造成FIRST(A)AFOLLOW(A)={A,e}n{a,#}#0所以該文法不是LL(1)文法。

(2)若采用LL(1)方法進行語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)(可以

為0)個a,所以得到文法G'[A]：A-aaAle

此時對產(chǎn)生式AfaaAle,有FOLLOW(A)={#}UFOLLOW(A)={#},因而

FIRST(A)AFOLLOW(A)={a,e}Cl{#}=0所以文法G'[A]是LL(1)文法，按LL(1)分析

表構造算法構造該文法的LL(1)分析表如表4-3-3所示。

A

AA-aaA/

(3)若采用LL(1)方法進行語法分析，對符號串“aaaa”的分析過程如表4-3-4所示。

步驟分析棧輸入串j

1#Aaaaa#

2#Aaaaaaa#

3#Aaaaa#

4#Aaa#

5#Aaaaa#

6#Aaa#

7#A#

8##

第七節(jié)習題

設有文法G[S]為：S-*ajb|(A)

A-*SdA|S

(1)完成下列算符優(yōu)先關系表，見表5-7-1,并判斷G[S]是否為算符優(yōu)先文法。

表5-7T算符優(yōu)先關系表(2)給出句型(SdSdS)的短語、簡單短語、句柄、索短語和

最左素短語。(3)給出輸入串(adb)#的分析過程。解答：

(1)先求文法G[S]的FIRSTVT集和LASTVT集:

由S-ab|(A)得：FIRSTVT(S)={a,b,();

由A-Sd,,得：FIRSTVT(A)=wbqso56;又由AfS”得:FIRSTVT(S)CFIRSTVT(A),即

FIRSTVT(A)={d,a,b,(};

由Sfa|b|(A)得;LASTVT(S)={a,b,});

由A—,,dA得:LASTVT(A)=pxt5fcl,又由A-S得：LASTVT(S)CLASTVT(A),即

LASTVT(A)={d,a,b,)}。

構造優(yōu)先關系表方法如下：

①對Pfab”,或P-,,aQb”,有a五b;②對P-?aR”,而beFIRSTVT(R),有a?b;③

對Pf,,Rb”,rfnaGFIRSTVT(R),有a?b。由此得到：

①由S-(A)得：仁)；

②由Sf(A,,得:(<FIRSTVT(A),即:(?d,(?a,(?b,(?(;由A-,,dA得：

d<FIRSTVT(A),即：d<d,d?a,d?b,d<(;

③由SfA)得,LASTVT(A)>),即：d?),a>),b?),)>);由AfSd,,得：LASTVT(S)>d,

即：a>d,b>d,)>d;

止匕外，由#S#得：肘#;

由#?FIRSTVT(S)得：脂由LASTVT(S)>#得：d>#,a>#,b>#,)>#?

最后得到算符優(yōu)先關系表，見表5-7-2。

表5-7-2算符優(yōu)先關系表

ab()d#

a>>>

b>>>

(<<<3K

)>>>

d<<<><>

#<<<3K

由表5-7-2可以看出，任何兩個終結(jié)符之間至少只滿足、《、》三種優(yōu)先關系之一，故

G[S]為算符優(yōu)先文法。

（2）為求出句型（SdSdS）的短語、簡單短語、句柄，我們先畫出該句型對應的語法

樹，如圖5-7-3所示。由圖如7-3得到:短語：S,SdS,SdSdS,（SdSdS）

簡單短語（即直接短語）：S句柄（即最左直接短語）：S

素短語：SdS,它同時也是該句型的最左素短語。

ab)d#

a>>

b>>

(<<<工

1>>

d

#<<<3K

（3）輸入串（adb）#的分析過程見表5-7-4

符號棧輸入串

#(adb)#

#(adb)#

#(adb)#

#(Sdb)#

#(Sdb}#

#(Sdb)#

#(SdS)#

#(SdA)#

#(A)#

#(A)#

#S#

第四節(jié)習題

一、單項選擇題

1、若a為終結(jié)符，貝IJA-a?aP為a.歸約b.移進c.接受d.待約

2、若項目集Ik含有A-a?，則在狀態(tài)k時，僅當面臨的輸入符號aGFOLLOW(A)時:

才采取“A-a?”動作的一定是。

a.LALR文法b.LR(0)文法c.LR(1)文法d.SLR(1)文法3、就文法的描述能力來

說，有。

a.SLR(1)CLR(0)b.LR(1)CLR(0)c.SLR(1)CLR(1)d.無二義文法ULR

(1)4、在LR(0)的ACTION子表中，如果某一行中存在標記“rj”的欄，則。a.該

行必定填滿rjb.該行未填滿rj

c.其他行也有rjd.goto子表中也有rj

5、一個指明了在分析過程中的某時刻所能看到產(chǎn)生式多大一部分。a.活前綴b.前綴

c.項目d.項目集解答：

1、A-a?稱為歸約項目，對?文法開始符S'的歸約項目，如S，-a?稱為接受項

目，A-a?aP(a為終結(jié)符)稱為移進項目。在此選b.

2、當用產(chǎn)生式A-a歸約時，LR(0)無論面臨什么輸入符號都進行歸約；SLR(1)則

僅當面臨的輸入符號aWFOLLOW(A)時進行歸約；LR(1)則當在把a歸約為A的規(guī)范句型

的前綴BAa前提下，當a后跟終結(jié)符a時，才進行歸約；因此選d。

3、由于LR(0)CSLR(1)CLR(1)U無二義文法，故選c。4、選a。5、選c。

二、多項選擇題

1、一個LR分析器包括

a.一個總控程序b.一個項目集c.一個活前綴

d.一張分析表e.一個分析棧

2、LR分析器核心部分是一張分析表，該表包括等子表。a.LL(l)分析b.優(yōu)先關系

c.GOTOd.LRe.ACT10N3,每一項ACTIONSa］所規(guī)定的動作包括。

a,移進b.比較c.接受d.歸約e.報錯

4、對LR分析表的構造，有可能存在

a.移進b.歸約c.移進/歸約d.移進/移進e.歸約/歸約

5、就文法的描述能力來說，有。

a.SLR(1)ULR(1)b.LR(1)CSLR(1)c.LR(0)ULR(1)

d.LR(1)U無二義文法e.SLR(1)U無二義文法

6、對LR分析器來說，存在

a.LALRb.LR(0)c.SLR(1)d.SLR(0)e.LR(1)

7、自上而下的語法分析方法有。

a.算符優(yōu)先分析法b.LL(1)分析法c.SLR(1)分析法

d.LR(0)分析法e.LALR(1)分析法

解答：

1、一個LR分析器包括一個總控程序和一張分析表，選a、d?

2、選c、e。

3、選a、c、d^e。

4、在LR分析表的構造中有可能存在“移進”/“歸約”和“歸約”/“歸約”沖突；故

選c、e。

5、選a、b、c、d、e。

6^選a、b^c、e。

7、選a,c、d、e。

三、填空題

1、對于一個文法，如果能夠構造使得它的則稱該文法為LR文法。

2、字的前綴是指該字的

3、活前綴是指的一個前綴，這種前綴不含

4、在LR分析過程中，只要

5、將識別NFA確定化，使其成為以為狀態(tài)的DFA,這個DFA就是建立的基礎。

6、A-a?稱為S，-a?為項目；若a為終結(jié)符，則稱A-a?a6為項目；若B為

非終結(jié)符，則稱A-a為項目。

7、LR(0)分析法的名字中“L”表示，“R”表示，“0”表示。解答：

1、一張分析表每個入口

2、任意首部

3、規(guī)范句型句柄

4、輸入串活前綴

5、活前綴項目集合LR分析算法

6、歸約接受移進待約

7、自左至右分析采用最右推導的逆過程即最左歸約向右查看0個字符

四、綜合題

1、對于文法G[S]：S->AS|b

A-SA|a

(1)列出所有LR(0)項目

(2)列出構成文法LR(0)項目集規(guī)范族。

解答：

首先將文法G拓廣為G[S']：

S'-S

S-*AS|b

A-SA|a

(1)文法G[S']的1^(0)項目是：

1、S'-?S5、SfAS?9、A-S?A

2、S'fS?6、S-?b10、A-SA?

3、S->*AS7、S-*b,11、A->*a

4、S-*A?S8、A-?SA12、A-a?

2、列出構成文法LR(0)項目集規(guī)范族。

用￡-CLOSURE(閉包)辦法構造文法G'的LR(0)項目集規(guī)范族如下:

10：1、S'f?S13：9、A-S?A16：12、A-a?

3、S->?AS8、A-?SA17：7、Si-

8、A一?SA3、S-?AS11>A-?a6、S-?b

6、Sf?b11、Af?a

II：2、S'fS?14：10、AfSA?

9、AfS?A4、S-A?S

8、A-?SA3、S--AS

11、A-*?a6、S->?b

3、S一?AS8、Af?SA

6、Sf?b11、A-**a

12：4、SfA?S15：5、S-AS?

3、S一?AS9、A-S?A

6、Sf?b8>A-?SA

8、Af?SA11、A->?a

11、Af?a3、Sf?AS

6、S一?b

注意：Il中的S，-S?和A-?SA是由狀態(tài)10中的1和3讀入一個S字符后得到的下

一個項目；，而14中的AfSA和AfA則是由13中的9和3讀入一個A字符后得到的

下一個項目；15中的S-AS?和A-S?A則是由14中的4和8讀入一個S字符后得到的

下一個項目。

狀態(tài)全體構成了文法G'的LR(0)規(guī)范族。

第八節(jié)習題

一、單項選擇題

1、中間代碼生成所依據(jù)的是。

a.語法規(guī)則b.詞法規(guī)則c.語義規(guī)則d.等價變換規(guī)則

2、四元式之間的聯(lián)系是通過實現(xiàn)的。

a.指示器b.臨時變量c.符號表d.程序變量

3、后綴式ab+cd+/可用表達式

a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d

4、表達式(rAVB)A(CVD)的逆波蘭表示為

a.nABVACDVb.A-|BVCDVA

c.ABV-iCDVA

5

所對應的表達式為。d.A-iBVACDV

a.A+B+C+Db.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)

6、四元式表示法的優(yōu)點為

a.不便于優(yōu)化處理，但便于表的更動b.不便于優(yōu)化處理，但節(jié)省存儲空間

c.便于優(yōu)化處理，也便于表的更動d.便于我的更動，也節(jié)省存儲空間

7、終結(jié)符具有屬性。

a.傳遞b.繼承c.抽象d.綜合

解答

1、選c。

2、四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的，故選b。

3、選bo

4、選b(>

5、選d。

6、四元式表示法的優(yōu)點與間接三元式相同，故選c。

7、選d。

二、多頂選擇題

1、中間代碼主要有

a.四元式b.二元式c.三元式d.后綴式e.間接三元式

2、下面中間代碼形式中，能正確表示算術表達式a+b+c的有a.ab+c+b.e.a+b+c

3、在下面的-回填技術。

a.賦值語句b.goto語句c.條件語句d.循環(huán)語句

4、下列中間代碼形式有益于優(yōu)化處理。

a.三元式b.四元式c.間接三元式d.逆波蘭表示法e,樹形表示法

5、在編譯程序中安排中間代碼生成的目的是。

a.便于進行存儲空間的組織b.利于目標代碼的優(yōu)化

c.利于編譯程序的移植d.利于目標代碼的移植

e.利于提高目標代碼的質(zhì)量

6、下面的中間代碼形式中，

a.ab+c*b.abc*+

c.

7、二地址代碼語句具體實現(xiàn)通常有表示方法。

a.逆波蘭表示b.三元式c.間接三元式d.樹形表示e.四元式

解答

1、選a、c、d、e。

2、b、d的中間代碼不能正確表示a+b+c,而e不是中間代碼：故選a、c?

3、凡涉及到跳轉(zhuǎn)的語句都需要采用拉鏈——回填技術，故選b、c、d?

4、選b、Co

5、選b、do

6、選b、e。

7、選b、c、e。

三、填空題

1、中間代碼有等形式，生成中間代碼主要是為了使

2、語法制導翻譯既可以用來產(chǎn)生入串進行。3、當源程序中的標號出現(xiàn)''先引用后定

義”時，中間代碼的轉(zhuǎn)移地址須持因而要進行。

4、文法符號的屬性有兩種，一種稱為，另一種稱為。5、后綴式abc-/所代表的表達式

是，表達式(a-b)*c可用后綴式

6、用一張輔以的辦法來表示中間代碼，這種表示法稱為間接三元式。解答

1、逆波蘭記號、樹形表示、三元式、四元式目標代碼的優(yōu)化容易實現(xiàn)

2、中間目標解釋執(zhí)行

3、標號定義回填

4、繼承屬性綜合屬性

5、a/(b-c)ab-c*

6、間接碼表三元式表

四、綜合題

1、給出下列表達式的逆波蘭表示(后綴式)：

①a*(-b+c)

②(AVB)A(CV-iDAE)

2、寫出算術表達式:A+B*(C-D)+E/(C-D)tN的

①四元式序列；②三元式序列；③間接三元式序列

解答1、

①ab@c+*;

②ABVCD-iEAVA

2、①表達式的四元式序列：

(1)(-,C,D,T1)