編譯原理第二版課后習答案

編譯原理第二版課后習答案《編譯原理》課后習題答案第一章第

1

章引論第

1

題解釋下列術語：（1）編譯程序（2）源程序（3）目標程序（4）編譯程序得前端（5）后端（6）遍答案：（1）

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

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

目標程序：目標語言書寫得程序稱為目標程序。（4）

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

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

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

2

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

8

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

3

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

4

題對下列錯誤信息，請指出可能就是編譯得哪個階段（詞法分析、語法分析、語義分析、代碼生成）報告得。（1）

else

沒有匹配得if（2）

數(shù)組下標越界（3）

使用得函數(shù)沒有定義（4）

在數(shù)中出現(xiàn)非數(shù)字字符答案：（1）

語法分析（2）

語義分析（3）

語法分析（4）

詞法分析第

5

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

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

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

擴充到L1，此時L0

?

L1

,并用L0

編寫L1

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

擴充為L2，有L1

L2

,并用L1

編寫L2

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

A

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

B

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

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

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

2

章

PL/0

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

1

題PL/0

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

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

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

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

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

2

題若PL/0

編譯程序運行時得存儲分配策略采用棧式動態(tài)分配，并用動態(tài)鏈與靜態(tài)鏈得方式分別解決遞歸調用與非局部變量得引用問題，試寫出下列程序執(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

中當程序編譯到r

得過程體時得名字表table

得內容。name

kind

level/val

adr

size答案：題

2

中當程序編譯到r

得過程體時得名字表table

得內容為：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

指出了當前棧中最新分配得單元(T

也就是數(shù)組S

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

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

地址，也稱基地址。SL：

靜態(tài)鏈，指向定義該過程得直接外過程（或主程序）運行時最新數(shù)據(jù)段得基地址，用以引用非局部（包圍它得過程）變量時，尋找該變量得地址。DL：

動態(tài)鏈，指向調用該過程前正在運行過程得數(shù)據(jù)段基地址，用以過程執(zhí)行結束釋放數(shù)據(jù)空間時，恢復調用該過程前運行棧得狀態(tài)。RA：

返回地址，記錄調用該過程時目標程序得斷點，即調用過程指令得下一條指令得地址，用以過程執(zhí)行結束后返回調用過程時得下一條指令繼續(xù)執(zhí)行。在每個過程被調用時在棧頂分配3

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

RA。第

5

題PL/0

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

INT

0

A（２）

OPR

0

0（３）

CAL

L

A答案：PL/0

編譯程序所產(chǎn)生得目標代碼中有3

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

條__________指令在code

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

0

A在過程目標程序得入口處，開辟A

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

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

0

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

與棧頂寄存器T

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

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

L

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

中，目標程序得入口地址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

得語法描述為：

〈

重復語句〉::=

repeat〈語句〉{；〈語句〉}until〈條件〉《編譯原理》課后習題答案第三章第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

開頭得非負整數(shù)？第３題為只包含數(shù)字、加號與減號得表達式，例如9-2＋5，3-1，７等構造一個文法。答案：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：<表達式>::=<項>｜<表達式>＋<項><項>::=<因子>｜<項>*<因子><因子>::=（<表達式>）｜i試給出下述表達式得推導及語法樹。（５）i+(i+i)（６）i+i*i答案：<表達式><表達式>

+

<項><因子><表達式><表達式>

+

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

)(5)

<表達式>=><表達式>＋<項>=><表達式>＋<因子>=><表達式>＋（<表達式>）=><表達式>＋（<表達式>＋<項>）=><表達式>＋（<表達式>＋<因子>）=><表達式>＋（<表達式>＋i）=><表達式>＋（<項>＋i）=><表達式>＋（<因子>＋i）=><表達式>＋（i＋i）=><項>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）<表達式><表達式>

+

<項><項>

*

<因子><因子>

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

<表達式>=><表達式>＋<項>=><表達式>＋<項>*<因子>=><表達式>＋<項>*i=><表達式>＋<因子>*i=><表達式>＋i*i=><項>＋i*i=><因子>＋i*i=>i＋i*i第7

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

構造兩個不同得最右推導:最右推導1

〈表達式〉〈表達式〉〈運算符〉〈表達式〉〈表達式〉〈運算符〉a〈表達式〉*

a〈表達式〉〈運算符〉〈表達式〉*

a〈表達式〉〈運算符〉a

*

a〈表達式〉+

a

*

aa

+

a

*

a最右推導2

〈表達式〉〈表達式〉〈運算符〉〈表達式〉〈表達式〉〈運算符〉〈表達式〉〈運算符〉〈表達式〉〈表達式〉〈運算符〉〈表達式〉〈運算符〉

a〈表達式〉〈運算符〉〈表達式〉

*

a〈表達式〉〈運算符〉a

*

a〈表達式〉+

a

*

aa

+

a

*

a第8

題文法G[S]為：S→Ac|aBA→abB→bc該文法就是否為二義得？為什么？答案：對于串a(chǎn)bc(1)S=>Ac=>abc

(2)S=>aB=>abc即存在兩不同得最右推導。所以，該文法就是二義得?；蛘撸簩斎胱址產(chǎn)bc，能構造兩棵不同得語法樹，所以它就是二義得。Sa

Bb

cSA

ca

b第9

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

S

*S

S

+

aa

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

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

生成得語言就是什么？(2)

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

嵌套得括號（２）

就是二義得，因為對于（）（）可以構造兩棵不同得語法樹。第11

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

就是它得一個句型，指出這個句型得所有短語、直接短語與句柄。答案：此句型對應語法樹如右，故為此文法一個句型?；蛘撸阂驗榇嬖谕茖蛄?

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

E+T*F

句型此句型相對于E

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

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

題一個上下文無關文法生成句子abbaa

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

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

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

B

SaS

B

Aε

b

b

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

最左推導:S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推導：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

題給出生成下述語言得上下文無關文法：（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

題習題７與習題11

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

題解釋下列術語與概念：（１）

字母表（２）

串、字與句子（３）

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

Z

x

,

x

∈V

*T

則稱

x

就是文法

G

得一個句子。

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

章

詞法分析第1

題構造下列正規(guī)式相應得DFA、（１）

1(0|1)*101（２）

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

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

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

先構造NFA：用子集法將NFA

確定化、

0

1X

、

AA

A

ABAB

AC

ABAC

A

ABYABY

AC

AB除X，A

外，重新命名其她狀態(tài)，令AB

為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)先構造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

CGT11=

CGJI

DHJ

KDHJ

DHJT12=

DHY

EIT13=

DHJ

EIKEIK

ABEFIKLT14=

ABEFIKL

EJY

CG將T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分別用0、1、2、3、4、5、6、7、8、9、10、11、12、13、14

表示。因為2、7、8、10、12

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

10

11

2

323

4

54

65

2

36

7

37

8

98

10

119

12

910

10

311

13

512

613

1414

7

30

1

0121

2710

83456911

1101101010

10101(3)

先構造NFA：先構造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)

先構造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

DFA

得狀態(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}，構造相應得DFA。答案：先構造其矩陣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

10FED0BC《編譯原理》課后習題答案第四章第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)組進行審查：{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}進行審查：∵{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

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

都有0

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

|

10)*0*

構造相應得DFA，首先構造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

112342DFA

得狀態(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ù)得正規(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={＋，－}答案：先構造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

3

45

66

67

DFA

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

5d3ddds?1010ddsddd第7

題給文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b構造相應得最小得DFA。答案：先構造其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、2、3、4、5、6

表示。因為3、4

中含有z，所以它們?yōu)榻K態(tài)。a

b0

1

21

5

1

66

2

5DFA

得狀態(tài)圖：0aa52b3aab416baabbbab令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。最小化為：Aa

,

bD

CaaBbabb第８題給出下述文法所對應得正規(guī)式：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進行分割：P1＝（｛1,2｝,｛3,4｝,｛5｝,｛6,7｝）再用a、b、c、d進行分割，仍不變。再令｛1,2｝為A，｛3，4｝為B，｛5｝為C，｛6，7｝為D。最小化為：AaC

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

章

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

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

給出(a,(a,a))與(((a,a),∧,(a)),a)得最左推導。(2)

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

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

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

得句子。答案：(1)

對(a,(a,a)得最左推導為：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)

得最左推導為：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→ε非終結符

FIRST

集

FOLLOW

集S

{a,∧,(}

{#,,,)}T

{a,∧,(}

{)}、、N

{,,ε}、

{)}、、對左部為N

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

（→,

S

N）={，}FIRST

（→ε）={ε}FOLLOW

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

→,

S

N)∩SELECT(N

→ε)

={，}∩

{

)}=所以文法就是LL(1)得。預測分析表（Predicting

Analysis

Table）a

∧

(

)

,

#S

→a

→∧

→(T)T

→S

N

→S

N

→S

NN

→ε

→,

S

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

對輸入串（a,a）#得分析過程為：棧（STACK）當前輸入符（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)文法，如果就是，構造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非終結符

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)∩SELECT(K→ε)

={

d

}∩

{

e,#,o

}=SELECT(M→K)∩SELECT(M→b

L

M)

={

d，e,#,o

}∩

{

b

}=所以文法就是LL(1)得。預測分析表：a

o

d

e

f

b

#S

→a

→MH

→MH

→MH

→MH

→MHM

→K

→K

→K

→bLM

→KH

→ε

→LSo

→ε

→εL

→eH