編譯原理期末復(fù)習(xí)題(含標(biāo)準(zhǔn)標(biāo)準(zhǔn)答案)-2

第八節(jié)習(xí)題-、單項(xiàng)選擇題

1、將編譯程序分成若T個(gè)“遍”是為了.

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

b.使程序地結(jié)構(gòu)更加清晰

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

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

2、構(gòu)造編譯程序應(yīng)掌握.

a.源程序b.目標(biāo)語(yǔ)言

C.編譯方法d.以上三項(xiàng)都是

3、變量應(yīng)當(dāng).

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

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

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

a.出錯(cuò)處理b.詞法分析

c.目標(biāo)代碼生成d.管理表格

5、不可能是口標(biāo)代碼.

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

c.絕對(duì)指令代碼d.中間代碼

6、使用可以定義一個(gè)程序地意義

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

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

7、詞法分析器地輸入是.

a.單詞符號(hào)串b.源程序

c.語(yǔ)法單位d.目標(biāo)程序

8、中間代碼生成時(shí)所遵循地是

.語(yǔ)法規(guī)則b.詞法規(guī)則

.語(yǔ)義規(guī)則d.等價(jià)變換規(guī)則

9、編譯程序是對(duì).

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

c.機(jī)器語(yǔ)言地執(zhí)行d.高級(jí)語(yǔ)言地翻譯

10、語(yǔ)法分析應(yīng)遵循.

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

c.構(gòu)詞規(guī)則d.等價(jià)變換規(guī)則

解答

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

2、構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語(yǔ)言及編譯方法等三方面地知識(shí)，故選d.

3、對(duì)編譯而言，變量既持有左值又持有右值，故選c.

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

5、目標(biāo)代碼包括匯編指令代碼、可重定位指令代碼和絕對(duì)指令代碼3種，因此不是目標(biāo)代碼地

只能選d.

6、詞法分析遵循地是構(gòu)詞規(guī)則，語(yǔ)法分析遵循地是語(yǔ)法規(guī)則，中間代螞生成遵循地是語(yǔ)義規(guī)則,

并且語(yǔ)義規(guī)則可以定義一個(gè)程序地意義.因此選a.

7、b8、c9、d10、c

二、多項(xiàng)選擇題

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

a.語(yǔ)法分析b.表格管理c.出錯(cuò)處理

d.語(yǔ)義分析e.詞法分析

2、編譯程序工作時(shí)，通常有階段.

a.詞法分析b.語(yǔ)法分析c.中間代碼生成

d.語(yǔ)義檢查e.目標(biāo)代碼生成

解答

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

三、填空題

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

2、編譯過(guò)程通?？煞譃?個(gè)階段，分別是、語(yǔ)法分析、代碼優(yōu)化和目標(biāo)代碼生成.3、編譯程序

工作過(guò)程中，第一段輸入是，最后階段地輸出為程序.

4、編譯程序是指將程序翻譯成程序地程用.解答

是否生成目標(biāo)程序2、詞法分析中間代碼生成3、源程序目標(biāo)代旦生成4、源程序目

標(biāo)語(yǔ)言

一、單項(xiàng)選擇題

1、文法G：S—xSx卜所識(shí)別地語(yǔ)言是.

a.xyxb.(xyx)*c.xnyxn(n^O)d.x*yx*

2、文法G描述地語(yǔ)言L(G)是指.

a.L(G)={a|S當(dāng)a,aGVT*)b.L(G)={a|S4a?aGVT*}

c.L(G)={a|S4a,ae(VTUVN*)}d.L(G)={a|S^a,ae(VTUVN*)}

3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別.

a.上下文無(wú)關(guān)文法b.上下文有關(guān)文法

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

4、設(shè)G為算符優(yōu)先文法，G地任■意終結(jié)符對(duì)a、b有以下關(guān)系成立.

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

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

5、如果文法G是無(wú)二義地，則它地任何句子a.

a.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)地語(yǔ)法樹(shù)必定相同

b.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)地語(yǔ)法樹(shù)可能不同

c.最左推導(dǎo)和最右推導(dǎo)必定相同

d.可能存在兩個(gè)不同地最左推導(dǎo)，但它們對(duì)應(yīng)地語(yǔ)法樹(shù)相同

6、由文法地開(kāi)始符經(jīng)0步或多步推導(dǎo)產(chǎn)生地文法符號(hào)序列是.

a.短語(yǔ)b.句柄c.句型d.句子

7、文法G：ETE+T|T

T->T+P|P

PT(E)|I

則句型P+T+i地句柄和最左素短語(yǔ)為.

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

8、設(shè)文法為：S-SA|A

A一a|b

則對(duì)句子aba,下面是規(guī)范推導(dǎo).

a.SnSAnSAAnAAA=aAAnabAnaba

b.SnSAnSAA=AAA=AAa=Aba=aba

c.SnSA=SAAnSAanSbanAba=aba

d.S=>SA=>Sa=>SAa=>Sba=>Aba=>aba

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

T—T,S|S

則FIRSTVT(T).

a.{b,A,(}b.{b,A,)Jc.{b,A,(,,}d.{b,A,),?}

10、產(chǎn)生正規(guī)語(yǔ)言地文法為.

U.0型b.1型c.2型d.3型

II、采用自上而下分析，必須.

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

12、在規(guī)范歸約中，用來(lái)刻畫(huà)可歸約串.

a.直接短語(yǔ)b.句柄c.最左素短語(yǔ)d.素短語(yǔ)

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

T-T+i|i

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

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

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

a.最左推導(dǎo)地逆過(guò)程b.最右推導(dǎo)地逆過(guò)程

c.規(guī)范推導(dǎo)d.最左歸約地逆過(guò)程

［解答］

1、選c.

2、選a.

3、選c.

4、雖然a與b沒(méi)有優(yōu)先關(guān)系，但構(gòu)造優(yōu)先函數(shù)后,a與b就一定存在優(yōu)先關(guān)系了.所以，由f(a)>g)(b)

或f(a)<g(b)并不能判定原來(lái)地a與b之間是否存在優(yōu)先關(guān)系：故選c.

5、如果文法G無(wú)二義性，則最左推導(dǎo)是先生長(zhǎng)右邊地枝葉：對(duì)于d,如果有兩個(gè)不同地是了左

推導(dǎo)，則必然有二義性.故選a.

6、選c.

7、由圖2-8-1地語(yǔ)法樹(shù)和優(yōu)先關(guān)系可以看出應(yīng)選b.

E

/1\

E+F

T

T

P

#<?+?>+<?!->#

圖2-8-1句型P+T+I地語(yǔ)法及優(yōu)先關(guān)系

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

9、由T-T,…和T->(…得FIRSTVT(T))=｛(,,)｝；

由T—S得FIRSTVT(S)UFIRSTVT(T),而FIRSTVT(S尸｛b,A,(｝；即

riRSTVT(T)=｛b,A,(,,)；因此選c.

10、d11、c12、b13、b14、b

二、多項(xiàng)選擇題

1、下面哪些說(shuō)法是錯(cuò)誤地.

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

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

2、對(duì)無(wú)二義性文法來(lái)說(shuō),一棵語(yǔ)法樹(shù)往往代表了.

a.多種推導(dǎo)過(guò)程b.多種最左推導(dǎo)過(guò)程c.一種最左推導(dǎo)過(guò)程

d.僅一種推導(dǎo)過(guò)程e.一和最左推導(dǎo)過(guò)程

3、如果文法G存在一個(gè)句子，滿足下列條件之一時(shí)，則稱該文法是二義文法.

a.該句子地最左推導(dǎo)與最右推導(dǎo)相同

b.該句子有兩個(gè)不同地最左推導(dǎo)

c.該句子有兩棵不同地最右推導(dǎo)

d.該句子有兩棵不同地語(yǔ)法樹(shù)

c.該句子地語(yǔ)法樹(shù)只有一個(gè)

4、有一文法G：S—AB

A—>aAb|￡

B—>cBd|e

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

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

c.{anbmcmdn|n,m^O}d.1nd"in,m妾0}

e.{anbncndn|n>0)

5、自下而上地語(yǔ)法分析中,應(yīng)從開(kāi)始分析.

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

d.文法地開(kāi)始符e.句柄

6、對(duì)正規(guī)文法描述地語(yǔ)言，以下有能力描述它.

a.0型文法b.l型文法c.上下文無(wú)關(guān)文法d.右線性文法e.左線性文法

解答1、e、a、c2、a、c、e3、b、c、d4、a、c5、b、c6、a、b、c、d、e

三、填空題

1、文法中地終結(jié)符和非終結(jié)符地交集是.詞法分析器交給語(yǔ)法分析器地文法符號(hào)一定是，它一

定只出現(xiàn)在產(chǎn)生式地部.

2、最左推導(dǎo)是指每次都對(duì)句型中地非終結(jié)符進(jìn)行擴(kuò)展.

3、在語(yǔ)法分析中，最常見(jiàn)地兩種方法一定是分析法，另一是分析法.

4、采用語(yǔ)法分析時(shí)，必須消除文法地左遞歸.

5、樹(shù)代表推導(dǎo)過(guò)程，樹(shù)代表歸約過(guò)程.

6、自下而上分析法采用、歸約、錯(cuò)誤處理、等四種操作.

7、Chomsky把文法分為種類型，編譯器構(gòu)造中采用和文法，它們分別產(chǎn)生和語(yǔ)言，并分別用和

自動(dòng)機(jī)識(shí)別所產(chǎn)生地語(yǔ)言.

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

2、最左

3、自上而上自下而上

4、自上而上

5、語(yǔ)法分析

6、移進(jìn)接受

7、42型3型上下文無(wú)關(guān)語(yǔ)言正規(guī)語(yǔ)言下推自動(dòng)機(jī)有限

四、判斷題

1、文法S-aS|bR|￡描述地語(yǔ)言是（a|bc）*

R->cS

在自下而上地語(yǔ)法分析中，語(yǔ)法樹(shù)與分析樹(shù)一定相同.

3、二義文法不是上下文無(wú)關(guān)文法.

4、語(yǔ)法分析時(shí)必須先消除文法中地左遞歸.（）

5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆地兩個(gè)過(guò)程.（）

6、一個(gè)文法所有句型地集合形成該文法所能接受地語(yǔ)言.（）

解答1、對(duì)2、錯(cuò)3、錯(cuò)4、錯(cuò)5、錯(cuò)6、錯(cuò)

五、簡(jiǎn)答題

1、句柄2、素短語(yǔ)3、語(yǔ)法樹(shù)4、歸約5、推導(dǎo)

［解答］

口1、句柄：一個(gè)句型地最左直接短語(yǔ)稱為該句型地句柄.

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

3、語(yǔ)法樹(shù)：滿足下面4個(gè)條件地樹(shù)稱之為文法G［S］地一棵語(yǔ)法樹(shù).

①每一終結(jié)均有一標(biāo)記，此標(biāo)記為VNUVT中地一個(gè)符號(hào)；

②樹(shù)地根結(jié)點(diǎn)以文法G［S］地開(kāi)始符S標(biāo)記；

③若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上地標(biāo)記為VN中地一個(gè)符號(hào)；

④若一個(gè)以A為標(biāo)記地結(jié)點(diǎn)有K個(gè)直接后繼，且按從左至右地順序，這些結(jié)點(diǎn)地標(biāo)記分別

為Xi,X2,…,XK，則A—XI,X2,…,XK，必然是G地一個(gè)產(chǎn)生式.

4、歸約：我們稱aYB直接歸約出aAB,僅當(dāng)A->Y是一個(gè)產(chǎn)生式，且a、Be（VNUVT）*

歸約過(guò)程就是從輸入串開(kāi)始，反及用產(chǎn)生式右部地符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開(kāi)

始符.

5、推導(dǎo)：我們稱aAB直接推出。yB,即aABnayB,僅當(dāng)A-丫是一個(gè)產(chǎn)生式，且a、

NT

B￡（VUV）*.如果a）=>a2=>--=>an,則我們稱這個(gè)序列是從a｝至a2地一個(gè)推導(dǎo).若存在一

個(gè)從a?an地推導(dǎo)，則稱ai可推導(dǎo)出a皿推導(dǎo)是歸約地逆過(guò)程.

六、問(wèn)答題

1、給出上下文無(wú)關(guān)文法地定義.

［解答］

一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式（VT,VN,S,P）,其中：

?VT是一個(gè)非空有限集，它地每個(gè)元素稱為終結(jié)符號(hào)；

?VN是一個(gè)非空有限集，它地每個(gè)元素稱為非終結(jié)符號(hào)，vTnvN=o；

?S是一個(gè)非終結(jié)符號(hào)，稱為開(kāi)始符號(hào)；

?P是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式地形式是p—a,其中，P￡VN，

a￡（VTUVN）*.開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式地左部出現(xiàn)一次.

2、文法G［S］：

S->aSPQ|abQ

QP—PQ

bP—>bb

bQ—bc

CQTCC

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

（2）它生成地語(yǔ)言是什么？

［解答］

口（1）由于產(chǎn)生式左部存在終結(jié)符號(hào)，且所有產(chǎn)生式左部符號(hào)地長(zhǎng)度均小于等于產(chǎn)生式右部地符

號(hào)長(zhǎng)度，所以文法G［S］是Chomskyl型文法，即上下文有關(guān)文法.

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

SnabQnabc

S=aSPQ=aabQPQnaabPQQ=aabbQQ=aabbcQ=aabbcc

S=>aSPQ=>aaSPQPQ=>aaabQPQPQ=>aaabPQQPQ=>aaabPQPQQ=>aaaPPQQQ=>

aaabbPqqq=>aaabbQQQ=>aaabbbcQQ=>aaabbbccQ=>aaabbbccc

于是得到文法G［S］生成地語(yǔ)言LRaWininei}

3、按指定類型，給出語(yǔ)言地文法.

L={aibi［i>i21}地上下文無(wú)關(guān)文法.

【解答】

（1）由L={aibHj>iel}知，所求該語(yǔ)言對(duì)應(yīng)地上下文無(wú)關(guān)文法首先應(yīng)有S-aSb型產(chǎn)生式，以

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

a地個(gè)數(shù)；也即所求上下文無(wú)關(guān)文法G［S］為：

G［S］：S-*aSb|Sb|b

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

A-*AaB|c

B-*bScA|b

（1）試求句型aAaBcbbdcc和aAcbBdcc地句柄；

（2）寫(xiě)出句子acabcbbdcc地最左推導(dǎo)過(guò)程.

【解答】（1）分別畫(huà)出對(duì)應(yīng)兩句型地語(yǔ)法樹(shù)，如圖2-8-2所示

句柄:AaBBd

(b)

(a)

圖2-8-2語(yǔ)法樹(shù)

(2)句子acabcbbdcc地最左推導(dǎo)如下：

S=>aAcB=>aAaBcB=>acaBcB=>acabcB=>acabcbScA=>acabcbBdcA

zz?auabcbbduA=>acabcbbdcc

5、對(duì)于文法G[S]：

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

(1)畫(huà)出句型(S,(a))地語(yǔ)法樹(shù).(2)寫(xiě)出上述句型地所有短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ).

【解答】S

(1)句型(S,(a))地語(yǔ)法樹(shù)如圖2-8-3所示/|\

(L)

(2)由圖2-8-3可知：S

①短語(yǔ)：S^a>(a)、S,(a)>(S,(a))；

②直接短語(yǔ)：a、S；圖283句型(S,(a))地語(yǔ)法樹(shù)

③句柄；S；

④素短語(yǔ)：素短語(yǔ)可由圖2?8-3中相鄰終結(jié)符之間地優(yōu)先關(guān)系求得，卻；

#<&,<(<a>)>)>#

因此索短語(yǔ)為a.

6、考慮文法G[T]：

T-*T*F1F

F-FtP|P

P-(T)|i

證明T*Pt(T*F)是該文法地一個(gè)句型，并指出直接短語(yǔ)和句柄.

【解答】

首先構(gòu)造T*Pt(T*F)地語(yǔ)法樹(shù)如圖2-8-4所示.

由圖2-8-4可知，T*Pt(T*F)是文法G[T]地一個(gè)句型.

直接短語(yǔ)有兩個(gè)，即P和T*F：句柄為P.

圖2-8~4句型T*Pf(T*F)地語(yǔ)法樹(shù)

一、單項(xiàng)選擇題

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

a.語(yǔ)義規(guī)則b.構(gòu)詞規(guī)則C.語(yǔ)法規(guī)則d.等價(jià)變換規(guī)則

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

a.單詞地種別編碼b.單詞在符號(hào)表中地位置

c.單詞地種別編碼和自身值d.單詞自身值

3、正規(guī)式Mi和M2等價(jià)是指.

a.Mi和M?地狀態(tài)數(shù)相等b.Mi和M2地有向弧條數(shù)相等

c.Mi和M2所識(shí)別地語(yǔ)言集相等d.Mi和M2狀態(tài)數(shù)和有向弧條數(shù)相等

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

圖361

a.以0開(kāi)頭地二進(jìn)制數(shù)組成地集合b.以0結(jié)尾地二進(jìn)制數(shù)組成地集合

c.含奇數(shù)個(gè)。地二進(jìn)制數(shù)組成地集合d.含偶數(shù)個(gè)。地二進(jìn)制數(shù)組成地集合

5、詞法分析器作為獨(dú)立地階段使整個(gè)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此，.

a.詞法分析器應(yīng)作為獨(dú)立地一遍b.詞法分析器作為子程序較好

c.詞法分析器分解為多個(gè)過(guò)程，由語(yǔ)法分析器選擇使用d.詞法分析器并不作為一個(gè)獨(dú)立地階段

解答1、b2、c3、c4、d5、b

二、多項(xiàng)選擇題

1、在詞法分析中，能識(shí)別出.

a.基本字b.四元式c.運(yùn)算符

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

2、令工=g白},則X上所有以b開(kāi)頭，后跟若干個(gè)ab地字地全體對(duì)應(yīng)地正規(guī)式為.

a.b(ab)*b.b(ab)+c.(ba)*b

d.(ba)+be.b(a|b)

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

三、煩空題

1、確定有限自動(dòng)機(jī)DFA是地一個(gè)特例.

2、若二個(gè)正規(guī)式所表示地相同，則認(rèn)為二者是等價(jià)地.

3、一個(gè)字集是正規(guī)地，當(dāng)且僅當(dāng)它可由所.

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

四、判斷題

1、一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一終態(tài).()

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

3、自動(dòng)機(jī)M和M'地狀態(tài)數(shù)不同，則二者必不等價(jià).()

4、確定地自動(dòng)機(jī)以及不確定地自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集.()

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

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

7、對(duì)任何正規(guī)表達(dá)式e,都存在一個(gè)NFAM,滿足L(G)=L(e).()

8、對(duì)任何正規(guī)表達(dá)式e,都存在一個(gè)DFAM,滿足L(G尸L(e).()

解答1、2、3、錯(cuò)4、5、6、7、8、正確

五、基本題

1、設(shè)乂=({x,y},{a,b},f,x,{y})為一非確定地有限自動(dòng)機(jī),其中f定義如下:

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

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

試構(gòu)造相應(yīng)地確定有限自動(dòng)機(jī)M

解答：對(duì)照自動(dòng)機(jī)地定義M=(SN,f,So.Z),由f地定義可知f(x,a)、f(y,b)均為多值函數(shù)，所以是一非

確定有限自動(dòng)機(jī)，先畫(huà)出NFAM相應(yīng)地狀態(tài)圖，如圖3-6-2所示.

圖3-6-2NFAM

用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示.

Ilalb

(X){x,y}ly)

(y)—{x,y}

{x,y}{x,y}{x.y}

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

表3-6-4狀態(tài)轉(zhuǎn)換矩陣

ab

021

1—2

222

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

Q

將圖3-6-5地DFA最小1,2考察

{1,2}.由于{1,2卜={1,22={2}『12],所以不再將其發(fā)：令

狀態(tài)1代表(1,2},即把原來(lái)到達(dá)2地孤都導(dǎo)向1,并制涂狀態(tài)2最后，得到加醫(yī)3-6-6所示化簡(jiǎn)DFA

M'.

圖3-6-6化簡(jiǎn)后地DFAM，

2、對(duì)給定正規(guī)式b*(d|ad)(b|ab)\構(gòu)造其NFAM；

解答：首先用A+=AA'改造正規(guī)式得：b4(d|ad)(b|ab)(b|ab)*；其次，構(gòu)造該正規(guī)式地NFAM,如圖367

所示.

X￡4￡123￡5￡Y

a

6da

7b8

圖3-6-7地NFAM

1、構(gòu)造下面文法地LL(1)分析表.

D一TL

T—?int|real

L-idR

R->,idR|￡

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

分析雖然這個(gè)文法很簡(jiǎn)單，我們還是從求開(kāi)始符號(hào)集合和后繼符號(hào)集合開(kāi)始.

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

FIRST(L)={id}FOLLOW(T)={id}

FIRST(R)={,,￡}FOLLOW(R)={#}

有了上面每個(gè)非終結(jié)符地FIRST集合，填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部a地FIRST(a)就

不是件難事了.

填表時(shí)唯一要小心地時(shí)，￡是產(chǎn)生式R-^右部地一個(gè)開(kāi)始符號(hào)，而#在FOLLOW(R)中，所

以R-e填在輸入符號(hào)#地欄目中.

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

非終結(jié)符輸入符號(hào)

intrealid9#

DD-TLD-TL

TT-*intT-*real

LL-*idR

RRf,：dRR--￡

2、下面文法G[S]是否為L(zhǎng)L(1)文法？說(shuō)明理由.

SfAB|PQxAfxyB-be

PfdP|8QfaQ|8

解答：該文法不是LL(1)文法，見(jiàn)下面分析中地說(shuō)明.

分析只有三個(gè)非終結(jié)符有兩個(gè)選擇.

1、P地兩個(gè)右部dP和￡地開(kāi)始符號(hào)肯定不相交.

2、Q地兩個(gè)右部aQ和E地開(kāi)始符號(hào)肯定不相交.

3、對(duì)S來(lái)說(shuō)，由于X￡FIRST(AB),同時(shí)也有X￡FIRST(PQX)(因?yàn)镻和Q都可能為空).

所以該文法不是LL(1)文法.

3、設(shè)有以下文法：

G[S]：S-aAbDe|d

A-*BSD|e

B-*SAc|cD|e

D-*Se|E

(1)求出該文法地每一個(gè)非終結(jié)符U地FOLLOW集.

(2)該文法是LL(1)文法嗎？

(3)構(gòu)造C[S]地LL(1)分析表.

解答：(1)求文法地每一個(gè)非終結(jié)符U地FOLLOW集地過(guò)程如下：

因?yàn)椋?/p>

①S是識(shí)別符號(hào)，且有A-BSD、B-SAc、D-Se,所以FOLLOW(S)應(yīng)包含

FIRST(D)UHRST(Ac)UFIRST(e)U(#)

={a,d}U{a,d,c,e}U{e}U[#}

={a,c,d,e#)

②又因?yàn)锳-BSD和D-￡,所以FOLLOW中還包含F(xiàn)OLLOW(A).

因?yàn)镾-aAbDe和B~SAc,所以

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

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

因?yàn)锳fBSD,所以FOLLOW(B)=FIRST(SD)={a,d}

因?yàn)镾faAbDc|d、A-BSD|e和B-SAc|cD,所以

FOLLOW(D):FIRST(e)UFOLLOW(A)UFOLLOW(B)

={e}U{b,c}U{a,d}={a,b,c,d,e}

(2)G[S]不是LL(1)文法.

因?yàn)楫a(chǎn)生式B-SAc|cD|￡中

FIRST(SAc)nFOLLOW(B)={a,d}#0

(3)構(gòu)造G[S]地LL(1)分析表.

按照LL(1)分析表地構(gòu)造算法構(gòu)造方法G[S]地LL(1)分析表如表4-3-2所示.

表4-3-2G[S]地LL(1)分析表

abCde#

SaAbDcd

ABSDBSDBSDe

BSac/ecDSac/e

DSe/￡￡￡Se/￡￡

4、將文法G[V]改造成為L(zhǎng)L(1)地.

G[V]：V-N|N[E]

E-*V|V+E

N-i

解答：對(duì)文法G[V]提取公共左因子后得到文法：

G'[V]：V~NA

A-el[E]

E-VB

B-*el+E

N-i

求出文法G'[V]中每一個(gè)非終結(jié)符號(hào)地FIRST集：

FIRST(V)={i}HRST(A)={[,e)

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

HRST(N)={i)

求出文法G'[V]中每一個(gè)非終結(jié)符號(hào)地FOLLOW集：

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

FOLLOW(A)=FOLLOW(V)={+?#}

FOLLOW(E)=FIRST(1)\[￡]UFOLLOW(B)=HRST(])\{e}UFOLLOW(E)={])

FOLLOW(B)=FOLLOW(E)=(]}

FOLLOW(N)=HRST(A)\{￡}UFOLLOW(V)={[,],+,#)

可以看到，對(duì)文法G'[V]地產(chǎn)生式A-￡|[E],有

FIRST([E])DFOLLOW(A)={[)n{+,],#)=0

對(duì)產(chǎn)生式B->￡l+E,有

FIRST(+E)ClFOLLOW(B)={+}0{])=0

而文法地其他產(chǎn)生式都只有個(gè)不為￡地右部，所以文法G'[V]是LL(1)文法.

5、已知文法：

G[A]：A-aAal8

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

(2)若采用LL(1)方法進(jìn)行語(yǔ)法分析，如何得到該文法地LL(1)分析表？

(3)若輸入符號(hào)串“aaaa”，請(qǐng)給出語(yǔ)法分析過(guò)程.

解答：(1)因?yàn)楫a(chǎn)生式A-aAa2有空產(chǎn)生式右部，而

FOLLOW(A)={#)UFIRST(a)={a,#)

造成FIRST(A)DFOLLOW(A)={A,￡)n{a,#}W0

所以該文法不是LL(1)文法.

(2)若采用LL(1)方法進(jìn)行語(yǔ)法分析，必須修改該文法.

因該文法產(chǎn)生偶數(shù)(可以為0)個(gè)a,所以得到文法

G[A]：A->aaA|8

此時(shí)對(duì)產(chǎn)生式A-aaA|w,有FOLLOW(A)={#}UFOLLOW(A)=(#),因而

FIRST(A)nFOLLOW(A)={a,E)n{#}=0

所以文法G'[A]是LL(1)文法，按LL(1)分析表構(gòu)造算法構(gòu)造該文法地LL(1)分析表如表4-3-3

所示.

表4-3-3文法G'[A]地LL⑴分析表

A#

AA—aaAAf￡

(3)若采用LL(1)方法進(jìn)行語(yǔ)法分析，對(duì)符號(hào)串“aaaa”地分析過(guò)程如表4-3-4所示.

表4.3?4對(duì)符號(hào)串“aaaa”地分析過(guò)程

步驟分析棧輸入串產(chǎn)生式/動(dòng)作

1#Aaaaa#A-*aaA

2#Aaaaaaa#匹配

3#Aaaaa#匹配

4#Aaa#A-*aaA

5#Aaaaa#匹配

6#Aaa#匹配

7#A#A-*￡

8##接受

第七節(jié)習(xí)題

設(shè)有文法G[S]為：

S-a|b|(A)

ATdA|S

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

表5-7-1算符優(yōu)先關(guān)系表

ah()d#

a>>

b>>

(<<<工

)>>

d

#<<<3E

(2)給出句型(SdSdS)地短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ).

(3)給出輸入串(adb)#地分析過(guò)程.

解答：

(1)先求文法G[S]地FIRSTVT集和LASTVT集：

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

由A-Sd…得：r1^1'丫1'(人戶{(1};又由A-S…得：HRSTVT(S)cFIRSTVT(A),即

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

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

由A-…dA得：LASTVT(A)=kawaewa,又由A-S得：LASTVT(S)uLASTVT(A),即

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

構(gòu)造優(yōu)先關(guān)系表方法如下：

①對(duì)P--…ab…，或P->…aQb…，有a=b:

②對(duì)Pf???aR…，而beFIRSTVT(R),有a《b;

③對(duì)P—??Rb…,而aWFIRSTVT(R),有a?b.

由此得到：

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

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

即：d<d,d<a,d<b,d<(;

③由S—A)得，LASTVT(A)A),即：d>),a>),b>),)>);SAfSd…得：LASTVT(S)”,即：a>d,b>d,)>

d;

此外，由#5#得：#=#；

由#《FIRSTVT(S)得：#<a.#<b,#<(；脂由LASTVT(S)卻得：d>#,a>#,b>#,)>#.

最后得到算符優(yōu)先關(guān)系表，見(jiàn)表5-7-2.

表5?7?2算符優(yōu)先關(guān)系表

ab()d#

a>>>

b>>>

(<<<3E

)>>>

d<<<><>

#<<<SEE

由表5-7-2可以看出，任何兩個(gè)終結(jié)符之間至少只滿足衣、《、》三種優(yōu)先關(guān)系之一，故G[S]為

算符優(yōu)先文法.

（2）為求出句型（SdSdS）地短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄，1戈們先畫(huà)出該句型對(duì)應(yīng)地語(yǔ)法樹(shù)，如圖

5-7-3所示.由圖5-7-3得到：

短語(yǔ)：S,SdS,SdSdS,（SdSdS）

簡(jiǎn)單短語(yǔ)（即直接短語(yǔ)）：S/K

句柄（即最左直接短語(yǔ)）：S

素短語(yǔ)：SdS,它同時(shí)也是該句型地最左素短語(yǔ).

八

s/R

SdA

S

rmlrc/~~tUli,c、1Ila*HJr」

(3)輸入串(adb)#地分析過(guò)程見(jiàn)表5-7-4

表5-7-4輸入串(adb)#地分析過(guò)程

符號(hào)棧輸入串說(shuō)明

#(adb)#移進(jìn)

#(adb)#移進(jìn)

#(adb)#用S-a歸約

#(Sdb)#移進(jìn)

#(Sdb)#移進(jìn)

#(Sdb)#用S-b歸約

#(SdS)#用A-S歸約

#(SdA)#用A-SdA歸約

#(A)#移進(jìn)

#(A)#用S-(A)歸約

#S#分析成功

第四節(jié)習(xí)題

一、單項(xiàng)選擇題

1、若a為終結(jié)符，則A-a-a0為項(xiàng)目

a.歸約b.移進(jìn)c.接受d.待約

2、若項(xiàng)目集k含有Af(x?，則在狀態(tài)k時(shí)，僅當(dāng)面臨地輸入符號(hào)aeFOLLOW(A)時(shí)，才采取“A

-*a?”動(dòng)作地一定是.

a.LALR文法b.LR(0)文法c.LR(1)文法d.SLR(1)文法

3、就文法地描述能力來(lái)說(shuō)，有.

a.SLR(1)CLR(0)b.LR(1)uLR(0)c.SLR(1)uLR(1)d.無(wú)二義文法＜=LR(1)

4、在LR(0)地ACTION子表中，如果某一行中存在標(biāo)記“丁地欄，則.

a.該行必定填滿rjb.該行未填滿G

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

5、一個(gè)指明了在分析過(guò)程中地某時(shí)刻所能看到產(chǎn)生式多大一部分.

a.活前綴b.前綴c.項(xiàng)目d.項(xiàng)目集

解答：

1、A-a?稱為歸約項(xiàng)目，對(duì)文法開(kāi)始符S，地歸約項(xiàng)目，如S，-a?稱為接受項(xiàng)目，A~a?鄧

(a為終結(jié)符)稱為移進(jìn)項(xiàng)目.在此選b.

2、當(dāng)用產(chǎn)生式A-a歸約時(shí):LR(0)無(wú)論面臨什么輸入符號(hào)都進(jìn)行歸約；SLR(1)則僅當(dāng)面

臨地輸入符號(hào)awFOLLOW(A)時(shí)進(jìn)行歸約；LR(1)則當(dāng)在把a(bǔ)歸約為A地規(guī)范句型地前綴pAa前

提下，當(dāng)a后跟終結(jié)符a時(shí)，才進(jìn)行歸約；因此選d.

3、由于LR(0)uSLR(1)uLR(1)u無(wú)二義文法，故選c.

4、選a.

5^選c.

二、多項(xiàng)選擇題

1、一個(gè)LR分析器包括.

a.一個(gè)總控程序b.一個(gè)項(xiàng)目集c.一個(gè)活前綴

d.一派芬析表個(gè)分析棧

2、LR分析器核心部分是一張分析表，該表包括等子表.

a.LL(l)分析b.優(yōu)先關(guān)系c.GOTO

d.LRe.ACTION

3、每一項(xiàng)ACTION[S,a]所規(guī)定地動(dòng)作包括.

a.移進(jìn)b.比較c.接受d.歸約e.報(bào)錯(cuò)

4、對(duì)LR分析表地構(gòu)造，有可能存在動(dòng)作沖突.

a.移進(jìn)b.歸約c.移進(jìn)/歸約d.移進(jìn)/移進(jìn)e.歸約明約

5、就文法地描述能力來(lái)說(shuō)，侑.

a.SLR(1)CLR(1)b.LR(1)(=SLR(1)c.LR(0)uLR(1)

d.LR(1)u無(wú)二義文法e.SLR(1)u無(wú)二義文法

6、對(duì)LR分析器來(lái)說(shuō)，存在等分析表地構(gòu)造方法.

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

7、自上而下地語(yǔ)法分析方法有.

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

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

解答：

1.一個(gè)LR分析器包括一個(gè)總控程序和一張分析表，選a、d.

2、選c、e.

3、選a、c、d、e.

4、在LR分析表地構(gòu)造中有可能存在“移進(jìn)”/“歸約”和“歸約”/“歸約”沖突；故選c、e.

5、選a、b^c^d、e.

6、選a、b、c、e.

7、選a>c、d、e.

三、填空題

1、對(duì)于一個(gè)文法，如果能夠構(gòu)造.使得它地均是唯一確定地，則稱該文法為L(zhǎng)R文法.

2、字地前綴是指該字地.

3、活前綴是指地一個(gè)前綴，這種前綴不含之后地任何符號(hào).

4、在LR分析過(guò)程中，只要地已掃描部分保持可歸約成一個(gè)，則掃描過(guò)地部分正確.

5、將識(shí)別地NFA確定化，使其成為以為狀態(tài)地DFA,這個(gè)DFA就是建立地基礎(chǔ).

6、A-a?稱為項(xiàng)目；對(duì)文法開(kāi)始符卜一a?為項(xiàng)目；若a為終結(jié)符，則稱A-a-