編譯原理第二版課后習(xí)答案

第

1

章引論第

1

題解釋下列術(shù)語：（1）編譯程序（2）源程序（3）目標(biāo)程序（4）編譯程序的前端（5）后端（6）遍答案：（1）

編譯程序：如果源語言為高級語言，目標(biāo)語言為某臺計算機上的匯編語言或機器語言，則此翻譯程序稱為編譯程序。（2）

源程序：源語言編寫的程序稱為源程序。（3）

目標(biāo)程序：目標(biāo)語言書寫的程序稱為目標(biāo)程序。（4）

編譯程序的前端：它由這樣一些階段組成：這些階段的工作主要依賴于源語言而與目標(biāo)機無關(guān)。通常前端包括詞法分析、語法分析、語義分析和中間代碼生成這些階段，某些優(yōu)化工作也可在前端做，也包括與前端每個階段相關(guān)的出錯處理工作和符號表管理等工作。（5）

后端：指那些依賴于目標(biāo)機而一般不依賴源語言，只與中間代碼有關(guān)的那些階段，即目標(biāo)代碼生成，以及相關(guān)出錯處理和符號表操作。（6）

遍：是對源程序或其等價的中間語言程序從頭到尾掃視并完成規(guī)定任務(wù)的過程。第

2

題一個典型的編譯程序通常由哪些部分組成？各部分的主要功能是什么？并畫出編譯程序的總體結(jié)構(gòu)圖。答案：一個典型的編譯程序通常包含

8

個組成部分，它們是詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和錯誤處理程序。其各部分的主要功能簡述如下。詞法分析程序：輸人源程序，拼單詞、檢查單詞和分析單詞，輸出單詞的機內(nèi)表達(dá)形式。語法分析程序：檢查源程序中存在的形式語法錯誤，輸出錯誤處理信息。語義分析程序：進(jìn)行語義檢查和分析語義信息，并把分析的結(jié)果保存到各類語義信息表中。中間代碼生成程序：按照語義規(guī)則，將語法分析程序分析出的語法單位轉(zhuǎn)換成一定形式的中間語言代碼，如三元式或四元式。中間代碼優(yōu)化程序：為了產(chǎn)生高質(zhì)量的目標(biāo)代碼，對中間代碼進(jìn)行等價變換處理。目標(biāo)代碼生成程序：將優(yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序。表格管理程序：負(fù)責(zé)建立、填寫和查找等一系列表格工作。表格的作用是記錄源程序的各類信息和編譯各階段的進(jìn)展情況，編譯的每個階段所需信息多數(shù)都從表格中讀取，產(chǎn)生的中間結(jié)果都記錄在相應(yīng)的表格中?？梢哉f整個編譯過程就是造表、查表的工作過程。需要指出的是，這里的“表格管理程序”并不意味著它就是一個獨立的表格管理模塊，而是指編譯程序具有的表格管理功能。錯誤處理程序：處理和校正源程序中存在的詞法、語法和語義錯誤。當(dāng)編譯程序發(fā)現(xiàn)源程序中的錯誤時，錯誤處理程序負(fù)責(zé)報告出錯的位置和錯誤性質(zhì)等信息，同時對發(fā)現(xiàn)的錯誤進(jìn)行適當(dāng)?shù)男Ｕㄐ迯?fù)），目的是使編譯程序能夠繼續(xù)向下進(jìn)行分析和處理。注意：如果問編譯程序有哪些主要構(gòu)成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。第

3

題何謂翻譯程序、編譯程序和解釋程序？它們?nèi)咧g有何種關(guān)系？答案：翻譯程序是指將用某種語言編寫的程序轉(zhuǎn)換成另一種語言形式的程序的程序，如編譯程序和匯編程序等。編譯程序是把用高級語言編寫的源程序轉(zhuǎn)換（加工）成與之等價的另一種用低級語言編寫的目標(biāo)程序的翻譯程序。解釋程序是解釋、執(zhí)行高級語言源程序的程序。解釋方式一般分為兩種：一種方式是，源程序功能的實現(xiàn)完全由解釋程序承擔(dān)和完成，即每讀出源程序的一條語句的第一個單詞，則依據(jù)這個單詞把控制轉(zhuǎn)移到實現(xiàn)這條語句功能的程序部分，該部分負(fù)責(zé)完成這條語句的功能的實現(xiàn)，完成后返回到解釋程序的總控部分再讀人下一條語句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)；另一種方式是，一邊翻譯一邊執(zhí)行，即每讀出源程序的一條語句，解釋程序就將其翻譯成一段機器指令并執(zhí)行之，然后再讀人下一條語句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。無論是哪種方式，其加工結(jié)果都是源程序的執(zhí)行結(jié)果。目前很多解釋程序采取上述兩種方式的綜合實現(xiàn)方案，即先把源程序翻譯成較容易解釋執(zhí)行的某種中間代碼程序，然后集中解釋執(zhí)行中間代碼程序，最后得到運行結(jié)果。廣義上講，編譯程序和解釋程序都屬于翻譯程序，但它們的翻譯方式不同，解釋程序是邊翻譯（解釋）邊執(zhí)行，不產(chǎn)生目標(biāo)代碼，輸出源程序現(xiàn)非數(shù)字字符答案：（1）

語法分析（2）

語義分析（3）

語法分析（4）

詞法分析第

5

題編譯程序大致有哪幾種開發(fā)技術(shù)？答案：（1）自編譯：用某一高級語言書寫其本身的編譯程序。（2）交叉編譯：A

機器上的編譯程序能產(chǎn)生B

機器上的目標(biāo)代碼。（3）自展：首先確定一個非常簡單的核心語言L0，用機器語言或匯編語言書寫出它的編譯程序T0，再把語言L0

擴充到L1，此時L0

?

L1

,并用L0

編寫L1

的編譯程序T1，再把語言L1

擴充為L2，有L1

L2

,并用L1

編寫L2

的編譯程序T2，……，如此逐步擴展下去，好似滾雪球一樣，直到我們所要求的編譯程序。（4）移植：將

A

機器上的某高級語言的編譯程序搬到

B

機器上運行。第６題計算機執(zhí)行用高級語言編寫的程序有哪些途徑?它們之間的主要區(qū)別是什么?答案：計算機執(zhí)行用高級語言編寫的程序主要途徑有兩種，即解釋與編譯。像Basic

之類的語言，屬于解釋型的高級語言。它們的特點是計算機并不事先對高級語言進(jìn)行全盤翻譯，將其變?yōu)闄C器代碼，而是每讀入一條高級語句，就用解釋器將其翻譯為一條機器代碼，予以執(zhí)行，然后再讀入下一條高級語句，翻譯為機器代碼，再執(zhí)行，如此反復(fù)?？偠灾?，是邊翻譯邊執(zhí)行。像C，Pascal

之類的語言，屬于編譯型的高級語言。它們的特點是計算機事先對高級語言進(jìn)行全盤翻譯，將其全部變?yōu)闄C器代碼，再統(tǒng)一執(zhí)行，即先翻譯，后執(zhí)行。從速度上看，編譯型的高級語言比解釋型的高級語言更快。《編譯原理》課后習(xí)題答案第二章第

2

章

PL/0

編譯程序的實現(xiàn)第

1

題PL/0

語言允許過程嵌套定義和遞歸調(diào)用，試問它的編譯程序如何解決運行時的存儲管理。答案：PL/0

語言允許過程嵌套定義和遞歸調(diào)用，它的編譯程序在運行時采用了棧式動態(tài)存儲管理。（數(shù)組CODE

存放的只讀目標(biāo)程序，它在運行時不改變。）運行時的數(shù)據(jù)區(qū)S

是由解釋程序定義的一維整型數(shù)組，解釋執(zhí)行時對數(shù)據(jù)空間S

的管理遵循后進(jìn)先出規(guī)則，當(dāng)每個過程(包括主程序)被調(diào)用時，才分配數(shù)據(jù)空間，退出過程時，則所分配的數(shù)據(jù)空間被釋放。應(yīng)用動態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調(diào)用和非局部變量的引用問題。第

2

題若PL/0

編譯程序運行時的存儲分配策略采用棧式動態(tài)分配，并用動態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調(diào)用和非局部變量的引用問題，試寫出下列程序執(zhí)行到賦值語句b∶=10

時運行棧的布局示意圖。var

x,y;procedure

p;var

a;procedure

q;var

b;begin

(q)b∶=10;end

(q);procedure

s;var

c,d;procedure

r;var

e,f;begin

(r)call

q;end

(r);begin

(s)call

r;end

(s);begin

(p)call

s;end

(p);begin

(main)call

p;end

(main).答案：程序執(zhí)行到賦值語句

b∶=10

時運行棧的布局示意圖為：第

3

題寫出題

2

中當(dāng)程序編譯到r

的過程體時的名字表table

的內(nèi)容。name

kind

level/val

adr

size答案：題

2

中當(dāng)程序編譯到r

的過程體時的名字表table

的內(nèi)容為：name

kind

level/val

adr

sizex

variable

0

dxy

variable

0

dx+1p

procedure

0

過程p

的入口（待填）

5a

variable

1

dxq

procedure

1

過程q

的入口4s

procedure

1

過程s

的入口（待填）

5c

variable

2

dxd

variable

2

dxr

procedure

2

過程r

的入口5e

variable

3

dxf

variable

3

dx+1注意：q

和s

是并列的過程，所以q

定義的變量b

被覆蓋。第

4

題指出棧頂指針T，最新活動記錄基地址指針B，動態(tài)鏈指針DL，靜態(tài)鏈指針SL

與返回地址RA

的用途。答案：棧頂指針

T，最新活動記錄基地址指針B，動態(tài)鏈指針DL，靜態(tài)鏈指針SL

與返回地址RA

的用途說明如下：T：

棧頂寄存器T

指出了當(dāng)前棧中最新分配的單元(T

也是數(shù)組S

的下標(biāo))。B：基址寄存器，指向每個過程被調(diào)用時，在數(shù)據(jù)區(qū)S

中給它分配的數(shù)據(jù)段起始

地址，也稱基地址。SL：

靜態(tài)鏈，指向定義該過程的直接外過程（或主程序）運行時最新數(shù)據(jù)段的基地在每個過程被調(diào)用時在棧頂分配3

個聯(lián)系單元，用以存放SL，DL，

RA。第

5

題PL/0

編譯程序所產(chǎn)生的目標(biāo)代碼是一種假想棧式計算機的匯編語言，請說明該匯編語言中下列指令各自的功能和所完成的操作。（１）

INT

0

A（２）

OPR

0

0（３）

CAL

L

A答案：PL/0

編譯程序所產(chǎn)生的目標(biāo)代碼中有3

條非常重要的特殊指令，這3

條__________指令在code

中的位置和功能以及所完成的操作說明如下：INT

0

A在過程目標(biāo)程序的入口處，開辟A

個單元的數(shù)據(jù)段。A

為局部變量的個數(shù)+3。OPR

0

0在過程目標(biāo)程序的出口處，釋放數(shù)據(jù)段（退棧），恢復(fù)調(diào)用該過程前正在運行的過程的數(shù)據(jù)段基址寄存器B

和棧頂寄存器T

的值，并將返回地址送到指令地址寄存器P

中，以使調(diào)用前的程序從斷點開始繼續(xù)執(zhí)行。CAL

L

A調(diào)用過程，完成填寫靜態(tài)鏈、動態(tài)鏈、返回地址，給出被調(diào)用過程的基地址值，送入基址寄存器B

中，目標(biāo)程序的入口地址A

的值送指令地址寄存器P

中，使指令從A

開始執(zhí)行。第

6

題給出對

PL/0

語言作如下功能擴充時的語法圖和EBNF

的語法描述。(1)

擴充條件語句的功能使其為：if〈條件〉then〈語句〉[else〈語句〉](2)

擴充repeat

語句為：repeat〈語句〉{；〈語句〉}until〈條件〉答案：對

PL/0

語言作如下功能擴充時的語法圖和EBNF

的語法描述如下：(1)

擴充條件語句的語法圖為：EBNF

的語法描述為：

〈條件語句〉::=

if〈條件〉then〈語句〉[else〈語句〉](2)

擴充repeat

語句的語法圖為：EBNF

的語法描述為：

〈

重復(fù)語句〉::=

repeat〈語句〉{；〈語句〉}until〈條件〉《編譯原理》課后習(xí)題答案第三章第3

章

文法和語言第1

題文法G＝({A,B,S},{a,b,c},P,S)其中P

為：S→Ac|aBA→abB→bc寫出L(G[S])的全部元素。答案：L(G[S])={abc}第2

題文法G[N]為：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的語言是什么？答案:G[N]的語言是V+。V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD....

=>NDDDD...D=>D......D或者：允許0

開頭的非負(fù)整數(shù)？第３題為只包含數(shù)字、加號和減號的表達(dá)式，例如9-2＋5，3-1，７等構(gòu)造一個文法。答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4

題已知文法G[Z]：Z→aZb|ab寫出L(G[Z])的全部元素。答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=>

aaa..ab...bbbL(G[Z])={anbn|n>=1}第5

題寫一文法，使其語言是偶正整數(shù)的集合。

要求：(1)

允許0

打頭；(2)不允許0

打頭。答案：(1)允許0

開頭的偶正整數(shù)集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允許0

開頭的偶正整數(shù)集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6

題已知文法G：<表達(dá)式>::=<項>｜<表達(dá)式>＋<項><項>::=<因子>｜<項>*<因子><因子>::=（<表達(dá)式>）｜i試給出下述表達(dá)式的推導(dǎo)及語法樹。（５）i+(i+i)（６）i+i*i答案：<表達(dá)式><表達(dá)式>

+

<項><因子><表達(dá)式><表達(dá)式>

+

<項><因子>i<項><因子>i<項><因子>i（

)(5)

<表達(dá)式>=><表達(dá)式>＋<項>=><表達(dá)式>＋<因子>=><表達(dá)式>＋（<表達(dá)式>）=><表達(dá)式>＋（<表達(dá)式>＋<項>）=><表達(dá)式>＋（<表達(dá)式>＋<因子>）=><表達(dá)式>＋（<表達(dá)式>＋i）=><表達(dá)式>＋（<項>＋i）=><表達(dá)式>＋（<因子>＋i）=><表達(dá)式>＋（i＋i）=><項>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）<表達(dá)式><表達(dá)式>

+

<項><項>

*

<因子><因子>

i<項><因子>ii(6)

<表達(dá)式>=><表達(dá)式>＋<項>=><表達(dá)式>＋<項>*<因子>=><表達(dá)式>＋<項>*i=><表達(dá)式>＋<因子>*i=><表達(dá)式>＋i*i=><項>＋i*i=><因子>＋i*i=>i＋i*i第7

題證明下述文法G[〈表達(dá)式〉]是二義的?！幢磉_(dá)式〉∷=a|(〈表達(dá)式〉)|〈表達(dá)式〉〈運算符〉〈表達(dá)式〉〈運算符〉∷=+|-|*|/答案：可為句子a+a*a

構(gòu)造兩個不同的最右推導(dǎo):最右推導(dǎo)1

〈表達(dá)式〉〈表達(dá)式〉〈運算符〉〈表達(dá)式〉〈表達(dá)式〉〈運(1)S=>Ac=>abc

(2)S=>aB=>abc即存在兩不同的最右推導(dǎo)。所以，該文法是二義的。或者：對輸入字符串a(chǎn)bc，能構(gòu)造兩棵不同的語法樹，所以它是二義的。Sa

Bb

cSA

ca

b第9

題考慮下面上下文無關(guān)文法：S→SS*|SS+|a(1)表明通過此文法如何生成串a(chǎn)a+a*，并為該串構(gòu)造語法樹。SS

S

*S

S

+

aa

a(2)G[S]的語言是什么？答案：(1)此文法生成串a(chǎn)a+a*的最右推導(dǎo)如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)該文法生成的語言是：*和+的后綴表達(dá)式，即逆波蘭式。第10

題文法S→S(S)S|ε(1)

生成的語言是什么？(2)

該文法是二義的嗎？說明理由。答案：（１）

嵌套的括號（２）

是二義的，因為對于（）（）可以構(gòu)造兩棵不同的語法樹。第11

題令文法G[E]為：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i證明E+T*F

是它的一個句型，指出這個句型的所有短語、直接短語和句柄。答案：此句型對應(yīng)語法樹如右，故為此文法一個句型?；蛘撸阂驗榇嬖谕茖?dǎo)序列:

E=>E+T=>E+T*F，所以

E+T*F

句型此句型相對于E

的短語有:E+T*F；相對于T

的短語有T*F直接短語為：T*F句柄為：T*F第13

題一個上下文無關(guān)文法生成句子abbaa

的推導(dǎo)樹如下：(1)給出串a(chǎn)bbaa

最左推導(dǎo)、最右推導(dǎo)。(2)該文法的產(chǎn)生式集合P

可能有哪些元素？(3)找出該句子的所有短語、直接短語、句柄。BaSA

B

SaS

B

Aε

b

b

a答案：(1)串a(chǎn)bbaa

最左推導(dǎo):S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推導(dǎo)：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)產(chǎn)生式有：S→ABS

|Aa|ε

A→a

B→SBB|b可能元素有：ε

aa

ab

abbaa

aaabbaa

……(3)該句子的短語有：a

是相對A

的短語ε

是相對S

的短語b

是相對B

的短語εbb

是相對B

的短語aa

是相對S

的短語aεbbaa

是相對S

的短語直接短語有：a

ε

b句柄是：a第14

題給出生成下述語言的上下文無關(guān)文法：（1）{

anbnambm|

n，m>=0}（2）{

1n0m

1m0n|

n，m>=0}（3）{WaWr|W

屬于{0|a}*，Wr

表示W(wǎng)的逆}答案：（１）S→AAA→aAb|ε（２）S→1S0|AA→0A1|ε（３）S→0S0|1S1|ε第16

題給出生成下述語言的三型文法：(1){an|n

>=0

}(2)

{

anbm|n,m>=1

}(3){anbmck|n,m,k>=0

}答案：(1)

S→aS|ε(2)S→aAA→aA|BB→bB|b(3)A→aA|BB→bB|CC→cC|ε第17

題習(xí)題７和習(xí)題11

中的文法等價嗎？答案：等價。第18

題解釋下列術(shù)語和概念：（１）

字母表（２）

串、字和句子（３）

語言、語法和語義答案：（１）字母表：是一個非空有窮集合。（２）串：符號的有窮序列。字：字母表中的元素。句子：如果

Z

x

,

x

∈V

*T

則稱

x

是文法

G

的一個句子。

+《編譯原理》課后習(xí)題答案第四章第4

章

詞法分析第1

題構(gòu)造下列正規(guī)式相應(yīng)的DFA.（１）

1(0|1)*101（２）

１(1010*|1(010)*1）*0（３）

a((a|b)*|ab*a)*b（４）

b((ab)*|bb)*ab答案：(1)

先構(gòu)造NFA：用子集法將NFA

確定化.

0

1X

.

AA

A

ABAB

AC

ABAC

A

ABYABY

AC

AB除X，A

外，重新命名其他狀態(tài)，令A(yù)B

為B、AC

為C、ABY

為D，因為D

含有Y（NFA的終態(tài)），所以D

為終態(tài)。.

0

1X

.

AA

A

BB

C

BC

A

DD

C

BDFA

的狀態(tài)圖：:(2)先構(gòu)造NFA：X

1

Aε

B1

C

0

D

1

E0εF

1

G

0

H

1

I

0

J

1

KLε

ε0Yεεεε用子集法將NFA

確定化ε

0

1X

XT0=X

AA

ABFLT1=

ABFL

Y

CGY

YCG

CGJT2=

YT3=

CGJ

DH

KDH

DHK

ABFKLT4=

DH

EIEI

ABEFILT5=

ABFKL

Y

CGT6=

ABEFIL

EJY

CGEJY

ABEFGJLYT7=

ABEFGJLY

EHY

CGKEHY

ABEFHLYCGK

ABCFGJKLT8=

ABEFHLY

EY

CGIEY

ABEFLYCGI

CGJIT9=

ABCFGJKL

DHY

CGKDHY

DHYT10=

ABEFLY

EY

CG構(gòu)造NFA：先構(gòu)造NFA：X

a

Aε

Ba,bεD

a

E

a

FCεYεεbεb用子集法將NFA

確定化ε

a

bX

XT0=X

AA

ABCDT1=ABCD

BE

BYBE

ABCDEBY

ABCDYT2=ABCDE

BEF

BEYBEF

ABCDEFBEY

ABCDEYT3=ABCDY

BE

BYT4=ABCDEF

BEF

BEYT5=ABCDEY

BEF

BEY將T0、T1、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5

表示。因為3、5

中含有Y，所以它們都為終態(tài)。a

b0

11

2

32

4

53

2

34

4

55

4

50

a

1

b

32a5a

4bababab(4)

先構(gòu)造NFA：X

Abε

BaF

b

G

b

HEεYaεC

D

b

εI

bεεεε用子集法將NFA

確定化：ε

a

bX

XT0=X

AA

ABDEFT1=ABDEF

CI

GCI

CIG

GT2=CI

DYDY

ABDEFYT3=G

HH

ABEFHT4=ABDEFY

CI

GT5=ABEFH

CI

G將T0、T1、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5

表示。因為4

中含有Y，所以它為終態(tài)。a

b0

11

2

32

43

54

2

35

2

3DFA

的狀態(tài)圖：0

b

1

b2a453bbabab第２題已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，構(gòu)造相應(yīng)的DFA。答案：先構(gòu)造其矩陣0

1x

z

xy

x,yz

x,z

y用子集法將NFA

確定化：0

1x

z

xz

xz

yxz

xz

xyy

xyxy

xyz

xxyz

xyz

xy將x、z、xz、y、xy、xyz

重新命名，分別用A、B、C、D、E、F

表示。因為B、C、F中含有z，所以它為終態(tài)。0

1A

B

AB

C

DC

C

ED

EE

F

AF

F

EDFA

的狀態(tài)圖：A0

10FED0B1010101C《編譯原理》課后習(xí)題答案第四章第3

題將下圖確定化：答案：用子集法將NFA

確定化：.

0

1S

VQ

QUVQ

VZ

QUQU

V

QUZVZ

Z

ZV

Z

.QUZ

VZ

QUZZ

Z

Z重新命名狀態(tài)子集，令VQ

為A、QU

為B、VZ

為C、V

為D、QUZ

為E、Z

為F。.

0

1S

A

BA

C

BB

D

EC

F

FD

F

.E

C

EF

F

FDFA

的狀態(tài)圖：第4

題將下圖的（a）和（b）分別確定化和最小化：答案：初始分劃得Π0：終態(tài)組{0}，非終態(tài)組{1,2,3,4,5}對非終態(tài)組進(jìn)行審查：{1,2,3,4,5}a

{0,1,3,5}而{0,1,3,5}既不屬于{0}，也不屬于{1,2,3,4,5}∵{4}

a

{0}，所以得到新分劃Π1：{0}，{4}，{1,2,3,5}對{1,2,3,5}進(jìn)行審查：∵{1,5}

b

{4}{2,3}

b

{1,2,3,5}，故得到新分劃Π2：{0}，{4}，{1,

5}，{2,3}{1,

5}

a

{1,

5}{2,3}

a

{1,3}，故狀態(tài)2

和狀態(tài)3

不等價，得到新分劃Π3：{0}，{2}，{3}，{4}，{1,

5}這是最后分劃了最小DFA：第5

題構(gòu)造一個DFA，它接收Σ={0,1}上所有滿足如下條件的字符串：每個1

都有0

直接跟在右邊。并給出該語言的正規(guī)式。答案：按題意相應(yīng)的正規(guī)表達(dá)式是(0*10)*0*，或0*(0

|

10)*0*

構(gòu)造相應(yīng)的DFA，首先構(gòu)造NFA

為用子集法確定化：I

I0

I1{X,0,1,3,Y}{0,1,3,Y}{2}{1,3,Y}{0,1,3,Y}{0,1,3,Y}{1,3,Y}{1,3,Y}{2}{2}{2}重新命名狀態(tài)集：S

0

112342244333DFA

的狀態(tài)圖：可將該DFA

最小化：終態(tài)組為{1,2,4}，非終態(tài)組為{3}，{1,2,4}0

{1,2,4}，{1,2,4}1

{3}，所以1,2,4

為等價狀態(tài)，可合并。第６題設(shè)無符號數(shù)的正規(guī)式為θ：θ=dd*|dd*.dd*|.dd*|dd*10(s|ε)dd*|10(s|ε)dd*|.dd*10(s|ε)dd*|dd*.dd*10(s|ε)dd*化簡θ，畫出θ的DFA，其中d={0,1,2,…,9}，s={＋，－}答案：先構(gòu)造NFA：Xd.

BdF

GdH10dAεC10dDsεE

dYdsεd用子集法將NFA

確定化：ε

?

s

10

dX

XAT0=XA

B

F

AB

BF

FGA

AT1=B

CC

CT2=FG

G

HG

GH

HT3=A

B

F

AT4=C

D

CD

DET5=G

HT6=H

HT7=DE

E

YE

EY

YT8=E

YT9=Y

Y將XA、B、FG、A、C、G、H、DE、E、Y

重新命名，分別用0、1、2、3、4、5、6、7、8、9

表示。終態(tài)有0、3、4、6、9。?

s

10

d0

1

2

31

42

5

63

1

2

34

7

45

66

67

8

98

99

9DFA

的狀態(tài)圖：?d62

5d3dd4

7890110ds?1010ddsddd第7

題給文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b構(gòu)造相應(yīng)的最小的DFA。答案：先構(gòu)造其NFA：SaAaZQbBDaEbFbbabaabb

bbab用子集法將NFA

確定化：a

bS

A

QA

A

BZQ

Q

DZBZ

Q

DDZ

A

BD

A

BB

Q

D將S、A、Q、BZ、DZ、D、B

重新命名，分別用0、1、式：S→0A|1BA→1S|1B→0S|0答案：解方程組S

的解：S=0A|1BA=1S|1B=0S|0將A、B

產(chǎn)生式的右部代入S

中S=01S|01|10S|10=（01|10）S|（01|10）所以：S=

(01|10)*(01|10)第9

題將下圖的DFA

最小化，并用正規(guī)式描述它所識別的語言。1a26c3cb54

7bba

bbbdda答案：令P0＝（｛1,2,3,4,5｝,｛6,7｝）用b進(jìn)行分割：P1＝（｛1,2｝,｛3,4｝,｛5｝,｛6,7｝）再用a、b、c、d進(jìn)行分割，仍不變。再令｛1,2｝為A，｛3，4｝為B，｛5｝為C，｛6，7｝為D。最小化為：AaC

DbdBbcabr=b*a(c|da)*bb*=b*a(c|da)*b+《編譯原理》課后習(xí)題答案第五章第5

章

自頂向下語法分析方法第1

題對文法G[S]S→a|∧|(T)T→T,S|S(1)

給出(a,(a,a))和(((a,a),∧,(a)),a)的最左推導(dǎo)。(2)

對文法G，進(jìn)行改寫，然后對每個非終結(jié)符寫出不帶回溯的遞歸子程序。(3)

經(jīng)改寫后的文法是否是LL(1)的?給出它的預(yù)測分析表。(4)

給出輸入串(a,a)#的分析過程，并說明該串是否為G

的句子。答案：(1)

對(a,(a,a)的最左推導(dǎo)為：S

(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))對(((a,a),∧,(a)),a)

的最左推導(dǎo)為：S

(T)(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T),S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),∧,S),S)(((a,a),∧,(T)),S)(((a,a),∧,(S)),S)(((a,a),∧,(a)),S)(((a,a),∧,(a)),a)(2)

改寫文法為：0)

S→a1)

S→∧2)

S→(

T

)3)

T→S

N4)

N→,

S

N5)

N→ε非終結(jié)符

FIRST

集

FOLLOW

集S

{a,∧,(}

{#,,,)}T

{a,∧,(}

{)}....N

{,,ε}.

{)}....對左部為N

的產(chǎn)生式可知：FIRST

（→,

S

N）={，}FIRST

（→ε）={ε}FOLLOW

（N）={)}由于SELECT(N

→,

S

N)∩SELECT(N

→ε)

={，}∩

{

)}=所以文法是LL(1)的。預(yù)測分析表（Predicting

Analysis

Table）a

∧

(

)

,

#S

→a

→∧

→(T)T

→S

N

→S

N

→S

NN

→ε

→,

S

N也可由預(yù)測分析表中無多重入口判定文法是LL(1)的。(3)

對輸入串（a,a）#的分析過程為：棧（STACK）當(dāng)前輸入符（CUR_CHAR）剩余輸入符（INOUT_STRING）所用產(chǎn)生式（OPERATION）#S#)T(#)T#)NS#)Na#)N#)NS,#)NS#)Na#)N#)#((aaa,,aa))#a,a)#...a,a)#...,a)#...,a)#...,a)#...a)#...a)#...)#...)#...#...#...S→(T).T→SNS→a.N→,SN.S→a.N→ε可見輸入串（a,a）#是文法的句子。第3

題已知文法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLM判斷G

是否是LL(1)文法，如果是，構(gòu)造LL(1)分析表。答案：文法展開為：0）

S→M

H1）

S→a2）

H→L

S

o3）

H→ε4）

K→d

M

L5）

K→ε6）

L→e

H

f7）

M→K8）

M→b

L

M非終結(jié)符

FIRST

集

FOLLOW

集S

{a,d,b,ε,e}

{#,o}........M

{d,ε,b}....

{e,#,o}......H

{ε,e}......

{#,f,o}......L

{e}.........

{a,d,b,e,o,#}K

{d,ε}......

{e,#,o}......對相同左部的產(chǎn)生式可知：SELECT(S→M

H)∩SELECT(S→a)

={

d,b

,e，#,o

}∩

{

a

}=SELECT(H→L

S

o)∩SELECT(H→ε)

={

e

}∩

{

#,f,o

}=SELECT(K→d

M

L)∩SELEC