清華大學(xué)編譯原理第二版課后習(xí)答案

清華大學(xué)編譯原理第二版課后習(xí)答案

清華大學(xué)第二版編譯原理答案

Lw.《編譯原理》課后習(xí)題答案第一章

第1章引論

第1題

解釋下列術(shù)語：

（1）編譯程序

（2）源程序

（3）目標(biāo)程序

（4）編譯程序的前端

（5）后端

（6）遍

答案：

（1）編譯程序：如果源語言為高級語言，目標(biāo)語言為某臺(tái)計(jì)算機(jī)上的匯編語言或機(jī)器

語言，則此翻譯程序稱為編譯程序。

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

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

（4）編譯程序的前端：它由這樣一些階段組成：這些階段的工作主要依賴于源語言而

與目標(biāo)機(jī)無關(guān)。通常前端包括詞法分析、語法分析、語義分析和中間代碼生成這些階

段，某些優(yōu)化工作也可在前端做，也包括與前端每個(gè)階段相關(guān)的出錯(cuò)處理工作和符號表

管理等工作。

（5）后端：指那些依賴于目標(biāo)機(jī)而一般不依賴源語言，只與中間代碼有關(guān)的那些階

段，即目標(biāo)代碼生成，以及相關(guān)出錯(cuò)處理和符號表操作。

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

第2題

一個(gè)典型的編譯程序通常由哪些部分組成？各部分的主要功能是什么？并畫出編譯程

序的總體結(jié)構(gòu)圖。

答案：

一個(gè)典型的編譯程序通常包含8個(gè)組成部分，它們是詞法分析程序、語法分析程序、

語義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理

程序和錯(cuò)誤處理程序。其各部分的主要功能簡述如下。

詞法分析程序：輸人源程序，拼單詞、檢查單詞和分析單詞，輸出單詞的機(jī)內(nèi)表達(dá)形

式。語法分析程序：檢查源程序中存在的形式語法錯(cuò)誤，輸出錯(cuò)誤處理信息。

語義分析程序：進(jìn)行語義檢查和分析語義信息，并把分析的結(jié)果保存到各類語義信息表

中。

中間代碼生成程序：按照語義規(guī)則，將語法分析程序分析出的語法單位轉(zhuǎn)換成一定形式

的中間語言代碼，如三元式或四元式。

中間代碼優(yōu)化程序：為了產(chǎn)生高質(zhì)量的目標(biāo)代碼，對中間代碼進(jìn)行等價(jià)變換處理。盛

威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站1

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

目標(biāo)代碼生成程序：將優(yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序。

表格管理程序：負(fù)責(zé)建立、填寫和查找等一系列表格工作。表格的作用是記錄源程序的

各類信息和編譯各階段的進(jìn)展情況，編譯的每個(gè)階段所需信息多數(shù)都從表格中讀取，產(chǎn)生

的中間結(jié)果都記錄在相應(yīng)的表格中。可以說整個(gè)編譯過程就是造表、查表的工作過程。

需要指出的是，這里的“表格管理程序”并不意味著它就是一個(gè)獨(dú)立的表格管理模塊，

而是指編譯程序具有的表格管理功能。

清華大學(xué)第二版編譯原理答案

錯(cuò)誤處理程序：處理和校正源程序中存在的詞法、語法和語義錯(cuò)誤。當(dāng)編譯程序發(fā)現(xiàn)源

程序中的錯(cuò)誤時(shí)，錯(cuò)誤處理程序負(fù)責(zé)報(bào)告出錯(cuò)的位置和錯(cuò)誤性質(zhì)等信息，同時(shí)對發(fā)現(xiàn)的錯(cuò)

誤進(jìn)行適當(dāng)?shù)男Ｕ?修復(fù))，目的是使編譯程序能夠繼續(xù)向下進(jìn)行分析和處理。

注意：如果問編譯程序有哪些主要構(gòu)成成分，只要回答六部分就可以。如果搞不清楚，

就回答八部分。

第3題

何謂翻譯程序、編譯程序和解釋程序？它們?nèi)咧g有何種關(guān)系？

答案:

翻譯程序是指將用某種語言編寫的程序轉(zhuǎn)換成另一種語言形式的程序的程序，如編譯程

序和匯編程序等。

編譯程序是把用高級語言編寫的源程序轉(zhuǎn)換(加工)成與之等價(jià)的另一種用低級語言編

寫的目標(biāo)程序的翻譯程序。

解釋程序是解釋、執(zhí)行高級語言源程序的程序。解釋方式一般分為兩種：一種方式是，

源程序功能的實(shí)現(xiàn)完全由解釋程序承擔(dān)和完成，即每讀出源程序的一條語句的第一個(gè)單

詞，則依據(jù)這個(gè)單詞把控制轉(zhuǎn)移到實(shí)現(xiàn)這條語句功能的程序部分，該部分負(fù)責(zé)完成這條

語句的功能的實(shí)現(xiàn)，完成后返回到解釋程序的總控部分再讀人下一條語句繼續(xù)進(jìn)行解

釋、執(zhí)行，如此反復(fù)；另一種方式是，一邊翻譯一邊執(zhí)行，即每讀由源程序的一條語

句，解釋程序就將其翻譯成一段機(jī)器指令并執(zhí)行之，然后再讀人下一條語句繼續(xù)進(jìn)行解

釋、執(zhí)行，如此反復(fù)。無論盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站2

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

是哪種方式，其加工結(jié)果都是源程序的執(zhí)行結(jié)果。目前很多解釋程序采取上述兩種方式

的綜合實(shí)現(xiàn)方案，即先把源程序翻譯成較容易解釋執(zhí)行的某種中間代碼程序，然后集中

解釋執(zhí)行中間代碼程序，最后得到運(yùn)行結(jié)果。

廣義上講，編譯程序和解釋程序都屬于翻譯程序，但它們的翻譯方式不同，解釋程序是

邊翻譯(解釋)邊執(zhí)行，不產(chǎn)生目標(biāo)代碼，輸出源程序的運(yùn)行結(jié)果。而編譯程序只負(fù)責(zé)把

源程序翻譯成目標(biāo)程序，輸出與源程序等價(jià)的目標(biāo)程序，而目標(biāo)程序的執(zhí)行任務(wù)由操作

系統(tǒng)來完成，即只翻譯不執(zhí)行。

第4題

對下列錯(cuò)誤信息，請指出可能是編譯的哪個(gè)階段(詞法分析、語法分析、語義分析、

代碼生成)報(bào)告的。

(1)else沒有匹配的if

(2)數(shù)組下標(biāo)越界

(3)使用的函數(shù)沒有定義

(4)在數(shù)中出現(xiàn)非數(shù)字字符

答案：

(1)語法分析

(2)語義分析

(3)語法分析

(4)詞法分析

第5題

編譯程序大致有哪幾種開發(fā)技術(shù)？

答案：

(1)自編譯：用某一高級語言書寫其本身的編譯程序。

(2)交叉編譯：A機(jī)器上的編譯程序能產(chǎn)生B機(jī)器上的目標(biāo)代碼。

清華大學(xué)第二版編譯原理答案

(3)自展：首先確定一個(gè)非常簡單的核心語言L0,用機(jī)器語言或匯編語言書寫出它的

編譯程序TO,再把語言L0擴(kuò)充到L1,此時(shí)LOCL1,并用L0編寫L1的編譯程序

T1,再把語言L1擴(kuò)充為L2,有LIL2，并用L1編寫L2的編譯程序T2,,,,,,如此逐步

擴(kuò)展下去，好似滾雪球一樣，直到我們所要求的編譯程序。

C

(4)移植：將A機(jī)器上的某高級語言的編譯程序搬到B機(jī)器上運(yùn)行。

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站3

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

第6題

計(jì)算機(jī)執(zhí)行用高級語言編寫的程序有哪些途徑?它們之間的主要區(qū)別是什么？

答案：

計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要途徑有兩種，即解釋與編譯。

像Basic之類的語言，屬于解釋型的高級語言。它們的特點(diǎn)是計(jì)算機(jī)并不事先對高級語

言進(jìn)行全盤翻譯，將其變?yōu)闄C(jī)器代碼，而是每讀入一條高級語句，就用解釋器將其翻譯

為一條機(jī)器代碼，予以執(zhí)行，然后再讀入下一條高級語句，翻譯為機(jī)器代碼，再執(zhí)行，

如此反復(fù)?？偠灾?，是邊翻譯邊執(zhí)行。

像C,Pascal之類的語言，屬于編譯型的高級語言。它們的特點(diǎn)是計(jì)算機(jī)事先對高級語

言進(jìn)行全盤翻譯，將其全部變?yōu)闄C(jī)器代碼，再統(tǒng)執(zhí)行，即先翻譯，后執(zhí)行。從速度上

看，編譯型的高級語言比解釋型的高級語言更快。

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站4

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

第2章PL/O編譯程序的實(shí)現(xiàn)

第1題

PL/O語言允許過程嵌套定義和遞歸調(diào)用，試問它的編譯程序如何解決運(yùn)行時(shí)的存儲(chǔ)管

理。

答案：

PL/O語言允許過程嵌套定義和遞歸調(diào)用，它的編譯程序在運(yùn)行時(shí)采用了棧式動(dòng)態(tài)存儲(chǔ)

管理。（數(shù)組CODE存放的只讀目標(biāo)程序，它在運(yùn)行時(shí)不改變。）運(yùn)行時(shí)的數(shù)據(jù)區(qū)S是由

解釋程序定義的一維整型數(shù)組，解釋執(zhí)行時(shí)對數(shù)據(jù)空間S的管理遵循后進(jìn)先出規(guī)則，當(dāng)每

個(gè)過程（包括主程序）被調(diào)用時(shí)，才分配數(shù)據(jù)空間，退出過程時(shí)，則所分配的數(shù)據(jù)空間被釋

放。應(yīng)用動(dòng)態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調(diào)用和非局部變量的引用問題。

第2題

若PL/O編譯程序運(yùn)行時(shí)的存儲(chǔ)分配策略采用棧式動(dòng)態(tài)分配，并用動(dòng)態(tài)鏈和靜態(tài)鏈的方

式分別解決遞歸調(diào)用和非局部變量的引用問題，試寫出下列程序執(zhí)行到賦值語句b:=10

時(shí)運(yùn)行棧的布局示意圖。

varx,y;

procedurep;

vara;

procedureq;

varb;

begin（q）

b：=10;

end（q）;

procedures;清華大學(xué)第二版編譯原理答案

varc,d;

procedurer;

vare,f;

begin(r)

callq;

end(r);

begin(s)

callr;

end(s);

begin(p)

calls;

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站1

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

end(p);

begin(main)

callp;

end(main).

答案：

程序執(zhí)行到賦值語句b：-10時(shí)運(yùn)行棧的布局示意圖為：

第3題

寫出題2中當(dāng)程序編譯到r的過程體時(shí)的名字表table的內(nèi)容。

namekindlevel/valadrsize

答案：

題2中當(dāng)程序編譯到r的過程體時(shí)的名字表table的內(nèi)容為:

namekindlevel/valadrsize

xvariable0dx

yvariable0dx+1

pprocedure0過程p的入口（待填）5

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站2

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

avariable1dx

qprocedure1過程q的入口4

sprocedure1過程s的入口（待填）5

cvariable2dx

dvariable2dx

rprocedure2過程r的入口5

evariable3dx

fvariable3dx+1

注意：q和s是并列的過程，所以q定義的變量b被覆蓋。

第4題

指出棧頂指針T,最新活動(dòng)記錄基地址指針B,動(dòng)態(tài)鏈指針DL,靜態(tài)鏈指針SL與返回

地址RA的用途。

答案：

棧頂指針T,最新活動(dòng)記錄基地址指針B,動(dòng)態(tài)鏈指針DL,靜態(tài)鏈指針SL與返回地址

清華大學(xué)第二版編譯原理答案

RA的用途說明如下：

T：棧頂寄存器T指出了當(dāng)前棧中最新分配的單元（T也是數(shù)組S的下標(biāo)）。

B：基址寄存器，指向每個(gè)過程被調(diào)用時(shí)，在數(shù)據(jù)區(qū)S中給它分配的數(shù)據(jù)段起始地址，

也稱基地址。

SL：靜態(tài)鏈，指向定義該過程的直接外過程（或主程序）運(yùn)行時(shí)最新數(shù)據(jù)段的基地

址，用以引用非局部（包圍它的過程）變量時(shí)，尋找該變量的地址。

DL：動(dòng)態(tài)鏈，指向調(diào)用該過程前正在運(yùn)行過程的數(shù)據(jù)段基地址，用以過程執(zhí)行結(jié)束釋

放數(shù)據(jù)空間時(shí)，恢復(fù)調(diào)用該過程前運(yùn)行棧的狀態(tài)。

RA：返回地址，記錄調(diào)用該過程時(shí)目標(biāo)程序的斷點(diǎn)，即調(diào)用過程指令的下一條指令的

地址，用以過程執(zhí)行結(jié)束后返回調(diào)用過程時(shí)的下一條指令繼續(xù)執(zhí)行。

在每個(gè)過程被調(diào)用時(shí)在棧頂分配3個(gè)聯(lián)系單元，用以存放SL,DL,RA。

第5題

PL/O編譯程序所產(chǎn)生的目標(biāo)代碼是--種假想棧式計(jì)算機(jī)的匯編語言，請說明該匯編語

言中下列指令各自的功能和所完成的操作。

（1）INT0A

（2）OPR00

（3）CALLA

答案：

PL/O編譯程序所產(chǎn)生的目標(biāo)代碼中有3條非常重要的特殊指令，這3條指

令在code中

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

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站3

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

INT0A

在過程目標(biāo)程序的入口處，開辟A個(gè)單元的數(shù)據(jù)段。A為局部變量的個(gè)數(shù)+3。

OPR00

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

數(shù)據(jù)段基址寄存器B和棧頂寄存器T的值，并將返回地址送到指令地址寄存器P中，以

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

CALLA

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

址寄存器B中，目標(biāo)程序的入口地址A的值送指令地址寄存器P中，使指令從A開始執(zhí)

行。第6題

給出對PL/O語言作如下功能擴(kuò)充時(shí)的語法圖和EBNF的語法描述。

(1)擴(kuò)充條件語句的功能使其為：

if〈條件〉then〈語句〉［else〈語句〉］

(2)擴(kuò)充repeat語句為：

repeat〈語句〉{；〈語句〉)until〈條件〉

答案：

對PL/O語言作如下功能擴(kuò)充時(shí)的語法圖和EBNF的語法描述如下：

(1)擴(kuò)充條件語句的語法圖為：

EBNF的語法描述為：〈條件語句〉：：=if〈條件〉then〈語句〉［else〈語句〉］

(2)擴(kuò)充repeat語句的語法圖為：

EBNF的語法描述為：〈重復(fù)語句〉：：=repeat〈語句＞{；〈語句〉}until〈條件〉

清華大學(xué)第二版編譯原理答案

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站4

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

第3章文法和語言

第1題

文法G=({A,B,S},{a,b,c},P,S)其中P為:

S-*Ac|aB

Afab

B-?be

寫出L(G[S])的全部元素。

答案：

L(G[S])={abc)

第2題

文法G[N]為：

N-D|ND

D-0|l|2|3|4|5|67|89

G[N]的語言是什么？

答案：

G[N]的語言是V+。V={0,1,2,3,4,5,6,1,8,9}

N=>ND=>NDD....=>NDDDD...D=>D.....D

或者：允許0開頭的非負(fù)整數(shù)？

第3題

為只包含數(shù)字、加號和減號的表達(dá)式，例如9-2+5,7等構(gòu)造一個(gè)文法。答案:

G[S]:

S->S+D|S-DD

D->0|l|2|34|5|67|8|9

第4題

已知文法G[Z]：

Z-*-aZb|ab

寫出L(G[Z])的全部元素。

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站1

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

答案：

Z=＞aZb=＞aaZbb=＞aaa..Z...bbb=＞aaa..ab...bbb

L(G[Z])={anbn|n＞=l}

第5題

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

(1)允許0打頭；

(2)不允許0打頭。

答案：

(1)允許0開頭的偶正整數(shù)集合的文法

E-NT|D

T-NT|D

N-*D|1|3|5719清華大學(xué)第二版編譯原理答案

D-0|2|4|68

(2)不允許0開頭的偶正整數(shù)集合的文法

E-NT|D

T-*FT|G

N-D|l|3|5|7|9

D-2|4|6|8

F-N|O

G-D|O

第6題

已知文法G：

〈表達(dá)式＞：：=＜項(xiàng)＞I＜表達(dá)式＞+＜項(xiàng)＞

〈項(xiàng)＞::=＜因子＞I＜項(xiàng)〉*〈因子＞

〈因子》::=(〈表達(dá)式》)Ii

試給出下述表達(dá)式的推導(dǎo)及語法樹。

(5)i+(i+i)

(6)i+i*i

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站2《編譯原理》課后習(xí)題答案第三章

答案：

〈表達(dá)式》

〈表達(dá)式〉+〈項(xiàng)〉

〈因子〉

〈表達(dá)式》

〈表達(dá)式〉+〈項(xiàng)〉

〈因子〉

1

＜項(xiàng)＞

〈因子＞

i

〈項(xiàng)〉

〈因子〉

i

()

(5)〈表達(dá)式〉

=＞＜表達(dá)式＞+〈項(xiàng)〉

=＞〈表達(dá)式》+〈因子〉

=＞＜表達(dá)式＞+（〈表達(dá)式》）

=＞＜表達(dá)式＞+（〈表達(dá)式＞+＜項(xiàng)＞）

X表達(dá)式＞+（〈表達(dá)式〉+〈因子》）

=＞〈表達(dá)式》+（〈表達(dá)式〉+i）

=＞＜表達(dá)式＞+（〈項(xiàng)〉+i）

=＞〈表達(dá)式＞十（〈因子〉+i）

=＞〈表達(dá)式＞+(i+i)

=＞〈項(xiàng)＞+（i+i）清華大學(xué)第二版編譯原理答案

=><因子>+(i+i)

=>i+(i+i)

〈表達(dá)式》

〈表達(dá)式＞+＜項(xiàng)＞

＜項(xiàng)〉*〈因子〉

〈因子》i

〈項(xiàng)〉

〈因子〉

1

1

（6）〈表達(dá)式》

=＞〈表達(dá)式＞+〈項(xiàng)〉

=＞＜表達(dá)式＞+＜項(xiàng)＞*〈因子＞

=＞＜表達(dá)式＞+＜項(xiàng)＞*i

=＞〈表達(dá)式〉+〈因子〉*i

=＞＜表達(dá)式＞+i*i

=＞＜項(xiàng)＞+i*i

=＞〈因子〉+i*i

=＞i+i*i

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站3

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

第7題

證明下述文法G［〈表達(dá)式〉］是二義的。

〈表達(dá)式〉：：=a|（〈表達(dá)式〉）|〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉：：=+1

*1/

答案：

可為句子a+a*a構(gòu)造兩個(gè)不同的最右推導(dǎo)：

最右推導(dǎo)1〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉a

〈表達(dá)式〉*a

〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉*a

〈表達(dá)式〉〈運(yùn)算符〉a*a

〈表達(dá)式〉+a*a

a+a*a

最右推導(dǎo)2〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈表達(dá)式〉〈運(yùn)算符〉〈表

達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉

〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉a

〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉*a

〈表達(dá)式〉〈運(yùn)算符〉a*a

〈表達(dá)式〉+a*a

a+a*a

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站4

《編譯原理》課后習(xí)題答案第二章第8題

清華大學(xué)第二版編譯原理答案

文法G[S]為:

S-Ac|aB

A-*ab

B-?be

該文法是否為二義的？為什么？

答案：

對于串a(chǎn)bc

(1)S=〉A(chǔ)c=>abc(2)S=>aB=>abc

即存在兩不同的最右推導(dǎo)。所以，該文法是二義的。

或者：

對輸入字符串a(chǎn)bc,能構(gòu)造兩棵不同的語法樹，所以它是二義的。S

aB

bc

S

Ac

ab

第9題

考慮下面上下文無關(guān)文法:

S-*SS*|SS+|a

(1)表明通過此文法如何生成串a(chǎn)a+a*,并為該串構(gòu)造語法樹。S

SS*

SS+a

aa

(2)G[S]的語言是什么？

答案：

(1)此文法生成串a(chǎn)a+a*的最右推導(dǎo)如下

S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

(2)該文法生成的語言是：*和+的后綴表達(dá)式，即逆波蘭式。盛威網(wǎng)(snwei)專業(yè)的

計(jì)算機(jī)學(xué)習(xí)網(wǎng)站5

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

第10題

文法S-*S(S)S|e

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

(2)該文法是二義的嗎？說明理由。

答案：

(1)嵌套的括號

(2)是二義的，因?yàn)閷τ?)()可以構(gòu)造兩棵不同的語法樹。第11題

令文法G[E]為：

E-T|E+T|E-T

T-*F|T*F|T/FF-(E)|i

清華大學(xué)第二版編譯原理答案

證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語、直接短語和句柄。答案:

此句型對應(yīng)語法樹如右，故為此文法一個(gè)句型。

或者：因?yàn)榇嬖谕茖?dǎo)序列：E=>E+T=〉E+T*F,所

以E+T*F句型

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

有T*F

直接短語為：T*F

句柄為：T*F

第13題

一個(gè)上下文無關(guān)文法生成句子abbaa的推導(dǎo)樹如下:

(1)給出串a(chǎn)bbaa最左推導(dǎo)、最右推導(dǎo)。

(2)該文法的產(chǎn)生式集合P可能有哪些元素？

(3)找出該句子的所有短語、直接短語、句柄。

B

a

S

ABS

a

SBA

ebba

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站6

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

答案:

(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|eA-*aB-SBBb

可能元素有：eaaababbaaaaabbaa??

(3)該句子的短語有：

a是相對A的短語

e是相對S的短語

b是相對B的短語

ebb是相對B的短語

aa是相對S的短語

aebbaa是相對S的短語

直接短語有：aeb

句柄是：a

第14題

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

(1){anbnambmn,m>=0}

(2){InOmItnOnn,m>=0}

(3){WaWrW屬于{0a}*,Wr表示W(wǎng)的逆}清華大學(xué)第二版編譯原理答案

答案：

(1)

S-AA

A-*aAb|￡

(2)

S-lSOlA

A-OA11e

(3)

S-OSOllSle

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站7

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

第16題

給出生成下述語言的三型文法：

(1){an|n>=0}

(2){anbmn,m>=l}

(3){anbmckn,m,k>=0}

答案：

(1)S-aSe

(2)

S-aA

A-aA|B

B-*bB|b

(3)

A^aA|B

C-cCe

第17題

習(xí)題7和習(xí)題11中的文法等價(jià)嗎？

答案：

等價(jià)。

第18題

解釋下列術(shù)語和概念：

(1)字母表

(2)串、字和句子

(3)語言、語法利語義

答案：

(1)字母表：是一個(gè)非空有窮集合。

(2)串：符號的有窮序列。

字：字母表中的元素。

句子：如果Zx,xGV*T則稱x是文法G的一個(gè)句子。+

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站8

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

(3)語言：它是由句子組成的集合，是由一組記號所構(gòu)成的集合。程序設(shè)計(jì)的語言就

是所有該語言的程序的全體。語言可以看成在一個(gè)基本符號集上定義的，按一定規(guī)清華

大學(xué)第二版編譯原理答案

則構(gòu)成的一切基本符號串組成的集合。

語法：表示構(gòu)成語言句子的各個(gè)記號之間的組合規(guī)律。程序的結(jié)構(gòu)或形式。

語義：表示按照各種表示方法所表示的各個(gè)記號的特定含義。語言所代表的含義。盛

威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站9

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

附加題

問題1:

給出下述文法所對應(yīng)的正規(guī)式：

S-0AI1B

A-*1S|1

B-?OS|O

答案：

R=(01|10)(0110)*

問題2：

已知文法G[A],寫出它定義的語言描述

G[A]:A-OB|1C

B-1|1AOBB

C-0|0AICC

答案：

G[A]定義的語言由0、1符號串組成，串中0和1的個(gè)數(shù)相同.

問題3：

給出語言描述，構(gòu)造文法.

構(gòu)造一文法，其定義的語言是由算符+,*,(,)和運(yùn)算對象a構(gòu)成的算術(shù)表達(dá)式的集合.

答案一：

G[E]E-E+T|T

T-T*F|F

F-(E)|a

答案二:

G[E]E-E+E|E*E(E)|a

問題4：

己知文法G[S]:

S-dAB

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站10

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

A-*aA)a

B-*e|bB

相應(yīng)的正規(guī)式是什么？G[S]能否改寫成為等價(jià)的正規(guī)文法?

答案：

正規(guī)式是daa*b*；

相應(yīng)的正規(guī)文法為(由自動(dòng)機(jī)化簡來)：

G[S]:S-dAA-a|aBB-aB,a|b|bCC-bCb

也可為(觀察得來)：G[S]:S-dAAfa為A|aBB-bBe

問題5：

已知文法G：

清華大學(xué)第二版編譯原理答案

E-E+T|E-TT

T-T*F|T/FF

F-(E)|i

試給出下述表達(dá)式的推導(dǎo)及語法樹

(1)i；

(2)i*i+i

(3)i+i*i

(4)i+(i+i)

答案：

⑴-i

(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i

(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)

=>i+(i+T)=M+(i+F)=>i+(i+i)

EE

E+T

T

T*F

Fi

i

E+T

i

T

F

i

F

i

E

E+T

E+T

T

F

F

(E)

i

T

Fi

F

T

F

i

Fi

清華大學(xué)第二版編譯原理答案

(1)

(2)

(3)

(4)

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站11

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

問題6：

已知文法G[E]:

E-ET+lT

ATF*|F

Ff|a

試證：FF~~*是文法的句型，指出該句型的短語、簡單短語和句柄.

答案：

該句型對應(yīng)的語法樹如下：

該句型相對于E的短語有FF"*

相對于T的短語有FF"*,F

相對于F的短語有F\F~

簡單短語有F;廠

句柄為F.

問題7：

適當(dāng)變換文法，找到下列文法所定義語言的一個(gè)無二義的文法：

S-SaS□SbS□ScS□d

答案：

該文法的形式很典型，可以先采用優(yōu)先級聯(lián)規(guī)則變換文法，然后再規(guī)定結(jié)合性對文法做

進(jìn)一步變換，即可消除二義性。

設(shè)a、b和c的優(yōu)先級別依次增高，根據(jù)優(yōu)先級聯(lián)規(guī)則將文法變換為：

SfSaS□A

A-*AbA□C

C-CcC□d

規(guī)定結(jié)合性為左結(jié)合，進(jìn)步將文法變換為：

S-*SaADA

A-AbCDC

C-*CcF□F

F-d

該文法為非二義的。

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站12

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

問題8：

構(gòu)造產(chǎn)生如下語言的上下文無關(guān)文法：

(1){anb2ncm|n,m20}

(2){anbmc2m|n,m20)

(3){ambn□m'n}

(4){ambncpdq口m+n=p+q}

(5){uawb口u,wC{a,b}*八|u|=|w}清華大學(xué)第二版編譯原理答案

答案：

(1)根據(jù)上下文無關(guān)文法的特點(diǎn)，要產(chǎn)生形如anb2ncm的串，可以分別產(chǎn)生形如

anb2n和形如cm的串。設(shè)計(jì)好的文法是否就是該語言的文法？嚴(yán)格地說，應(yīng)該給出證

明。但若不是特別指明，通?？梢院雎赃@一點(diǎn)。

對于該語言，存在一個(gè)由以下產(chǎn)生式定義的上下文無關(guān)文法G[S]：

S-AB

A-e□aAbb

B-*e□cB

(2)同樣，要產(chǎn)生形如anbmc2m的串，可以分別產(chǎn)生形如an和形如bmc2m的串。對

于該語

言，存在一個(gè)由以下產(chǎn)生式定義的上下文無關(guān)文法G[S]：

SfAB

A-*￡□aA

B-*e□bBcc

(3)考慮在先產(chǎn)生同樣數(shù)目的a,b,然后再生成多余的a。以下G[S]是一種解法：S

faSb□aS□e

(4)以下G[S]是一種解法：

S-aSd□A□D

AfbAd□B

DfaDc□B

B—bBc□￡

注：a不多于d時(shí)，b不少于c；反之，a不少于d時(shí)，b不多于c。前一種情形通過

對應(yīng)A,后一種情形對應(yīng)D。

(5)以下G[S]是一種解法:

SfAb

A-*BAB□a

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站13

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

B-a□b

問題9：

下面的文法G(S)描述由命題變量p、q,聯(lián)結(jié)詞A(合取)、V(析取)、「(否定)

構(gòu)成的命題公式集合：

SSVT□T

TfTAF□F

F->",FOpnq

試指出句型rFVrq八P的直接短語(全部)以及句柄。

答案：

直接短語：P，q,中

句柄：-F

問題10：

設(shè)字母表4=缶},符號串x=aaa,寫出下列符號串及其長度：x0,xx,x5以及A+.

答案：

x0=(aaa)0=e|xO|=0

xx=aaaaaaxx|=6清華大學(xué)第二版編譯原理答案

x5=aaaaaaaaaaaaaaax5|=15

A+=A1UA2UUAnU?={a,aa,aaa,aaaa,aaaaa,,}

A*=AOUA1UA2UUAnU,,={e,a,aa,aaa,aaaa,aaaaa”}

問題11：

令2={a,b,c},又令x=abc,y=b,z=aab,寫出如下符號串及它們的長度：xy,

xyz,(xy)3

答案：

xy=abcb|xy|=4

xyz=abcbaab|xyz=7

(xy)3=(abcb)3=abcbabcbabcb|(xy)31=12

問題12：

已知文法法Z］：Z：：=UO|VI、U：：=Z1門、V：：=ZO|0，請寫出全部由此文

法描述的只含有四個(gè)符號的句子。

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站14

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

答案：

Z=>U0=>Z10=>U010=>1010

Z=>U0=>Z10=>V110=>0110

Z=>V1=>ZOO=>UOOO=>1000

Z=>Vl=>Z00=>V100=>0100

問題13：

已知文法G[S]：S：：=ABA：：=aAIeB：：=bBcIbe,寫出該文法描述的語言。

答案：

A：：=aA|￡描述的語言：{an|n>=0}

B：：=bBc|be描述的語言:{,bncnn>=l}

L(G[S])={anbmem|n>=0,m>=l}

問題14：

已知文法E：：=T|E+T|E-T、T：：=F|T*F|T/F、F：：=(E)|i,寫出該文法的開

始符號、終結(jié)符號集合VT、非終結(jié)符號集合VN。

答案：

開始符號：E

VT={+,),i)

VN={E,F,T}

問題15：

設(shè)有文法G[S]：S：：=S*SS+S|(S)|a,該文法是二義性文法嗎？

答案:

根據(jù)所給文法推導(dǎo)出句子a+a*a,畫出了兩棵不同的語法樹，所以該文法是二義性文

法。盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站15

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

S

S*S

S+Sa

aaS

清華大學(xué)第二版編譯原理答案

S+S

aS*S

aa

問題16：

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

答案：

A::=1|3|57|9|NA

N::=NO|N1|N2|N3|N4|N5|N6N7|N8N9|

N::=0|l|23|4|5|6|78|9

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站16

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

第4章詞法分析

第1題

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

(1)1(01)*101

(2)1(1010*11(010)*1)*0

(3)a((a|b)*|ab*a)*b

(4)b((ab)*|bb)*ab

答案：

(1)先構(gòu)造NFA：

用子集法將NFA確定化

.01

X.A

AAAB

ABACAB

ACAABY

ABYACAB

除X,A外，重新命名其他狀態(tài)，令A(yù)B為B、AC為C、ABY為D,因?yàn)镈含有Y(NFA

的終態(tài))，所以D為終態(tài)。

.01

X.A

AAB

BCB

CAD

DCB

DFA的狀態(tài)圖：：

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站1

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

⑵先構(gòu)造NFA：

X1A

eB

1C0D1Ee

清華大學(xué)第二版編譯原理答案

F1G0H1I0J1K

L

ee

Y

用子集法將NFA確定化

e01

XX

TO=XA

AABFL

Tl=ABFLYCG

YY

CGCGJ

T2二Y

T3=CGJDllK

DHDH

KABFKL

T4=DHEI

EIABEFIL

T5=ABFKLYCG

T6=ABEFILEJYCG

EJYABEFGJLY

T7=ABEFGJLYEHYCGK

EHYABEFHLY

CGKABCFGJKL

T8=ABEFHLYEYCGI

EYABEFLY

CGICGJI

T9=ABCFGJKLDHYCGK

DHYDHY

T10=ABEFLYEYCG

Tll=CGJIDHJK

DHJDHJ

T12=DIIYEI

T13=DIIJEIK

EIKABEFIKL

T14=ABEFIKLEJYCG

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站2

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

將TO、Tl、T2、T3、T4、T5、T6、T7、T8、T9、T10>Tll、T12、T13、T14重新命名，

分別清華大學(xué)第二版編譯原理答案

用0、

1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因?yàn)?、7、8、10、12中含

有Y,所以它們都為終態(tài)。

01

01

123

2

345

46

523

673

789

81011

9129

10103

11135

126

1314

1473

010

12

12

7

108

3

4

5

6

9

111314

1

1

1

1

1

1

1

11

清華大學(xué)第二版編譯原理答案

1

01

1

1

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站3

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

(3)先構(gòu)造NFA：

先構(gòu)造NFA：

XaA

￡B

a,b

€

DaEaF

C

Y

e

￡

b

e

b

用子集法將NFA確定化

eab

XX

TO=XA

AABC!)

T1=ABCDBEBY

BEABCDE

BYABCDY

T2=ABCDEBEFBEY

BEFABCDEF

BEYABCDEY

T3=ABCDYBEBY

T4=ABCDEFBEFBEY

T5=ABCDEYBEFBEY

將TO、Tl、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5表示。因?yàn)?、5中

含有Y,

所以它們都為終態(tài)。

ab

01123

清華大學(xué)第二版編譯原理答案

245

323

445

545

0a1b3

2

a

5

a4

b

a

b

a

b

a

b

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站4《編譯原理》課后習(xí)題答案第四章

(4)先構(gòu)造NFA：

XA

b

￡B

a

FbGbH

E

e

Y

a

e

CDbe

Ib

e

用子集法將NFA確定化：

￡ab

XX

TO=XA

AABDEF

T1=ABDEFCIG

CICI

GGT2=CIDY

清華大學(xué)第二版編譯原理答案

DYABDEFY

T3二GH

HABEFII

T4=ABDEFYCIG

T5=ABEFHCIG

將TO、Tl、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5表示。因?yàn)?中含

有Y,所以它為終態(tài)。

ab

01

123

24

35

423

523

DFA的狀態(tài)圖：

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站5

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

0b1b

2

a

4

5

3

b

b

a

b

a

b

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站6

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

第2題

已知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,l)={x},M(y,1)=4),M(z,l)={y},構(gòu)造相應(yīng)的

DFAo

答案:

先構(gòu)造其矩陣

01

xzx

yx,y

zx,zy

用子集法將NFA確定化：

01

xzxzxzy

清華大學(xué)第二版編譯原理答案

xzxzxy

yxy

xyxyzx

xyzxyzxy

將x、z、xz、y、xy、xyz重新命名，分別用A、B、C>D、E、F表不。因?yàn)锽、C、F

中含有z,所以它為終態(tài)。

01

ABA

BCD

CCE

DE

EFA

FFE

DFA的狀態(tài)圖：

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站7

A

01

F

E

D

B

1

1

1

1

C

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

第3題

將下圖確定化：

答案：

用子集法將NFA確定化：

.01

SVQQU

VQVZQU

QUVQUZ

VZZZ

VZ.

QUZVZQUZZZZ

清華大學(xué)第二版編譯原理答案

重新命名狀態(tài)子集，令VQ為A、QU為B、VZ為C、V為D、QUZ為E、Z為F。

.01

SAB

ACB

BDE

CFF

DF.

ECE

FFF

DFA的狀態(tài)圖：

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站8

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

第4題

將下圖的（a）和（b）分別確定化和最小化：

答案：

初始分劃得

H0：終態(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},所以得到新分劃

ni：{0},⑷，{1,2,3,5}

對{1,2,3,5}進(jìn)行審查：

V{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不等價(jià)，得到新分劃

口3：⑻,{2},⑶，⑷,{1,5}

這是最后分劃了

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站9

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

最小DFA：

第5題

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

在右邊。并給出該語言的正規(guī)式。

答案：

按題意相應(yīng)的正規(guī)表達(dá)式是(0*10)*0*,或0*(010)*0*構(gòu)造相應(yīng)的DFA,首先構(gòu)造

NFA為用子集法確定化：

I10II

{X,0,1,3,Y}

(0,1,3,Y)

⑵{1,3,Y}

清華大學(xué)第二版編譯原理答案

{0,1,3,Y)

(0,1.3.Y}

{1,3,Y}

⑵

{2}

{2}

重新命名狀態(tài)集：

S01

1

2

3

4

2

2

4

4

3

3

3

DFA的狀態(tài)圖：

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站10

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

可將該DFA最小化:

終態(tài)組為為,2,4},非終態(tài)組為{3},{1,2,4}0{1,2,4},{1,2,4}1{3},所以1,2,4為

等價(jià)狀態(tài)，可合并。

第6題

設(shè)無符號數(shù)的正規(guī)式為0：

0=dd*|dd*.dd*|.dd*|dd*10(s|￡)dd*

|10(s|￡)dd*|.dd*10(s|e)dd*

|dd*.dd*10(s|￡)dd*

化簡0,畫出0的DFA,其中d={0,1,2,,,,9},s={+,-}

答案：

先構(gòu)造NFA：

X

d

.B

d

FG

d

H

10

dA

清華大學(xué)第二版編譯原理答案

￡

C

10

d

D

s

e

Ed

Y

d

s

e

d

用子集法將NFA確定化：

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站11

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

e?s10d

XXA

TO=XABFA

BB

FFG

AA

T1=BC

CC

T2=FGGH

GG

HH

T3=ABFA

T4=CDC

DDE

T5=GH

T6=HH

T7=DEEY

EE

YY

T8=EY

T9=YY

將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。

?s10d

0123

14

2563123

清華大學(xué)第二版編譯原理答案

474

56

66

789

89

99

DFA的狀態(tài)圖：

盛威網(wǎng)（snwei）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站12《編譯原理》課后習(xí)題答案第四章

*

d

6

25

d

3

d

d

47

8

9

1

10

d

s

?

10

10

d

d

s

d

d

d

第7題

給文法G[S]：

S-aA|bQ

A-*aAbB|b

B-bDjaQ

Q-aQbD|b

D-bB|aA

E-*aB|bF

F-bDaE|b

構(gòu)造相應(yīng)的最小的DFA,

清華大學(xué)第二版編譯原理答案

答案：

先構(gòu)造其NFA：

S

a

A

a

Z

Q

b

B

D

a

E

b

F

b

b

a

b

a

a

b

bb

b

a

b

用子集法將NFA確定化：

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站13

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

ab

SAQ

AABZ

QQDZ

BZQD

DZAB

DAB

BQD

將S、A、Q、BZ、DZ、D、B重新命名，分別用0、1、2、3、4、5、6表示。因?yàn)?、4

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

ab

012

113

224325

清華大學(xué)第二版編譯原理答案

416

516

625

DFA的狀態(tài)圖：

a

a

5

2

b

3

a

a

b

4

1

6

b

a

a

b

b

b

a

b

令P0=({0,1,2,5,6),{3,4})用b進(jìn)行分割：

Pl=({0,5,6},{1,2},{3,4})再用b進(jìn)行分割:

P2=({0},{5,6},{1,2},{3,4})再用a、b進(jìn)行分割，仍不變。再令{0}

為A,{1,2}為B,{3,4}為C,{5,6)為D。最小化為：

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站14

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

A

DC

a

a

B

b

a

b

b

第8題

給出下述文法所對應(yīng)的正規(guī)式：

清華大學(xué)第二版編譯原理答案

S-OA|1B

A-*1S|1

B-OS|O

答案：

解方程組S的解：

S=OA|1B

A=1S|1

B=OS|O

將A、B產(chǎn)生式的右部代入S中

S=O1S|O1|1OS|1O=(01|10)S|(01|10)

所以：S=(01110)*(01|10)

第9題

將下圖的DFA最小化，并用正規(guī)式描述它所識(shí)別的語言。

1

a

2

6

c

3

c

b

5

47

b

b

ab

b

b

d

d

a

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站15

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

答案：

令P0=({1,2,3,4,5},{6,7})用b進(jìn)行分割:

Pl=({1,2},{3,4},{5},{6,7})再用a、b、c、d進(jìn)行分割，仍不變。再令

{1,2}為A,{3,4}為B,{5}為C,{6,7}為D。

最小化為：

A

a

CD

b

dB

清華大學(xué)第二版編譯原理答案

b

c

a

b

r=b*a(c|da)*bb*=b*a(c|da)*b+

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站16

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

附加題

問題1：

為下邊所描述的串寫正規(guī)式，字母表是{a,b}.

a)以ab結(jié)尾的所有串

b)包含偶數(shù)個(gè)b但不含a的所有串

c)包含偶數(shù)個(gè)b且含任意數(shù)目a的所有串

d)只包含一個(gè)a的所有串

e)包含ab子串的所有串

f)不包含ab子串的所有串

答案：

注意正規(guī)式不唯一

a)(a|b)*ab

b)(bb)*

c)(a*ba*ba*)*

d)b*ab*

e)(a|b)*ab(a|b)*

f)b*a*

問題2：

請描述下面正規(guī)式定義的串.字母表{0,1}.

a)0*(10+)*0*

b)(0|1)*(00|11)(01)*

c)1(011)*0

答案：

a)每個(gè)1至少有一個(gè)0跟在后邊的串

b)所有含兩個(gè)相繼的0或兩個(gè)相繼的1的串

c)必須以1開頭和。結(jié)尾的串

問題3：

構(gòu)造有窮自動(dòng)機(jī).

a)構(gòu)造一個(gè)DFA,接受字母表

b)構(gòu)造一個(gè)DFA,接受字母表｛0,1｝上的以01結(jié)尾的所有串｛0,1｝上的不包含01

子串的所有串.

c)構(gòu)造一個(gè)NFA,接受字母表｛x,y｝上的正規(guī)式x(x|y)*x描述的集合

d)構(gòu)造一個(gè)NFA,接受字母表｛a,b｝上的正規(guī)式(ab|a)*b+描述的集合并將其轉(zhuǎn)換為等

價(jià)的DFA.以及最小狀態(tài)DFA

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站17

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

答案：

b)

清華大學(xué)第二版編譯原理答案

c)

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站18

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

最小化的DFA

問題4：

設(shè)有如圖所示狀態(tài)轉(zhuǎn)換圖，求其對應(yīng)的正規(guī)表達(dá)式。

可通過消結(jié)法得出正規(guī)式

R=(01)*((00|1)(01)*|0)

也可通過轉(zhuǎn)換為正則文法，解方程得到正規(guī)式。

問題5：

已知正規(guī)式：

⑴((a|b)*aa)*b;

(2)(a|b)*b.

試用有限自動(dòng)機(jī)的等價(jià)性證明正規(guī)式(1)和(2)是等價(jià)的，并給出相應(yīng)的正規(guī)文法。分

析：

基本思路是對兩個(gè)正規(guī)式，分別經(jīng)過確定化、最小化、化簡為兩個(gè)最小DFA,如這兩個(gè)

最小DFA一樣，也就證明了這兩個(gè)正規(guī)式是等價(jià)的。

答案：

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站19

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

狀態(tài)轉(zhuǎn)換表1

ab

X1241234124Y

12341234124Y

124Y1234124Y

狀態(tài)轉(zhuǎn)換表2

aB

123

223

323

由于2與3完全一樣，將兩者合并，即見下表

ab

123

23

而對正規(guī)式(2)可畫NFA圖，如圖所示。

ab

X121212Y

121212Y

12Y1212Y

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站20

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

可化簡得下表

abl23

清華大學(xué)第二版編譯原理答案

223

得DFA圖

兩圖完全一樣，故兩個(gè)自動(dòng)機(jī)完全一樣，所以兩個(gè)正規(guī)文法等價(jià)。對相應(yīng)正規(guī)文法，令

A對應(yīng)1,B對應(yīng)2

故為：

A-*aAbB|b

B-*aAbB|b

即為S-aS|bS|B,此即為所求正規(guī)文法。

問題6：

考慮正規(guī)表達(dá)式r=a*b(a|b),構(gòu)造可以生成語言L(r)的一個(gè)正規(guī)文法。答案：

Sfa*b(a|b)

變換為SfaA,S-*b(a|b),A-aA,A-b(aib)

變換為SfaA,SbB,B-(a|b),AaA,A-bC,C-(a|b)

變換為SfaA,S-bB,B~a,B-b,A-aA,AfbC,C-a,C-b

所以，一個(gè)可能的正規(guī)文法為G[S]：

SfaA,SfbB,Ba,B—b,A-*aA,AbC,Cfa,Cb

或表示為：

SfaA|bB,B-*a|b,A-*aA|bC,C-a|b

(適當(dāng)?shù)葍r(jià)變換也可以，但要作說明，即要有步驟)

盛威網(wǎng)(snwei)專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站21

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

問題7：

考慮下圖所示的NFAN,構(gòu)造可以生成語言L(N)的一個(gè)正規(guī)文法。答案:

G[P]:

P0P口1P口1Q

Q-0R口1R

R-e

問題8：

考慮如下文法G[S]：

s-