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

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

1

章引論第

1

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

編譯程序：如果源語(yǔ)言為高級(jí)語(yǔ)言，目標(biāo)語(yǔ)言為某臺(tái)計(jì)算機(jī)上得匯編語(yǔ)言或機(jī)器語(yǔ)言，則此翻譯程序稱為編譯程序。（2）

源程序：源語(yǔ)言編寫得程序稱為源程序。（3）

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

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

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

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

2

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

8

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

3

題何謂翻譯程序、編譯程序與解釋程序？它們?nèi)咧g有何種關(guān)系？答案：翻譯程序就是指將用某種語(yǔ)言編寫得程序轉(zhuǎn)換成另一種語(yǔ)言形式得程序得程序，如編譯程序與匯編程序等。編譯程序就是把用高級(jí)語(yǔ)言編寫得源程序轉(zhuǎn)換（加工）成與之等價(jià)得另一種用低級(jí)語(yǔ)言編寫得目標(biāo)程序得翻譯程序。解釋程序就是解釋、執(zhí)行高級(jí)語(yǔ)言源程序得程序。解釋方式一般分為兩種：一種方式就是，源程序功能得實(shí)現(xiàn)完全由解釋程序承擔(dān)與完成，即每讀出源程序得一條語(yǔ)句得第一個(gè)單詞，則依據(jù)這個(gè)單詞把控制轉(zhuǎn)移到實(shí)現(xiàn)這條語(yǔ)句功能得程序部分，該部分負(fù)責(zé)完成這條語(yǔ)句得功能得實(shí)現(xiàn)，完成后返回到解釋程序得總控部分再讀人下一條語(yǔ)句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)；另一種方式就是，一邊翻譯一邊執(zhí)行，即每讀出源程序得一條語(yǔ)句，解釋程序就將其翻譯成一段機(jī)器指令并執(zhí)行之，然后再讀人下一條語(yǔ)句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。無(wú)論就是哪種方式，其加工結(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)來(lái)完成，即只翻譯不執(zhí)行。第

4

題對(duì)下列錯(cuò)誤信息，請(qǐng)指出可能就是編譯得哪個(gè)階段（詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成）報(bào)告得。（1）

else

沒(méi)有匹配得if（2）

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

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

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

語(yǔ)法分析（2）

語(yǔ)義分析（3）

語(yǔ)法分析（4）

詞法分析第

5

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

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

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

擴(kuò)充到L1，此時(shí)L0

?

L1

,并用L0

編寫L1

得編譯程序T1，再把語(yǔ)言L1

擴(kuò)充為L(zhǎng)2，有L1

L2

,并用L1

編寫L2

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

A

機(jī)器上得某高級(jí)語(yǔ)言得編譯程序搬到

B

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

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

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

2

章

PL/0

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

1

題PL/0

語(yǔ)言允許過(guò)程嵌套定義與遞歸調(diào)用，試問(wèn)它得編譯程序如何解決運(yùn)行時(shí)得存儲(chǔ)管理。答案：PL/0

語(yǔ)言允許過(guò)程嵌套定義與遞歸調(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í)對(duì)數(shù)據(jù)空間S

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

2

題若PL/0

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

時(shí)運(yùn)行棧得布局示意圖。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í)行到賦值語(yǔ)句

b∶=10

時(shí)運(yùn)行棧得布局示意圖為：第

3

題寫出題

2

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

得過(guò)程體時(shí)得名字表table

得內(nèi)容。name

kind

level/val

adr

size答案：題

2

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

得過(guò)程體時(shí)得名字表table

得內(nèi)容為：name

kind

level/val

adr

sizex

variable

0

dxy

variable

0

dx+1p

procedure

0

過(guò)程p

得入口（待填）

5a

variable

1

dxq

procedure

1

過(guò)程q

得入口4s

procedure

1

過(guò)程s

得入口（待填）

5c

variable

2

dxd

variable

2

dxr

procedure

2

過(guò)程r

得入口5e

variable

3

dxf

variable

3

dx+1注意：q

與s

就是并列得過(guò)程，所以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

與返回地址RA

得用途說(shuō)明如下：T：

棧頂寄存器T

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

也就是數(shù)組S

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

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

地址，也稱基地址。SL：

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

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

返回地址，記錄調(diào)用該過(guò)程時(shí)目標(biāo)程序得斷點(diǎn)，即調(diào)用過(guò)程指令得下一條指令得地址，用以過(guò)程執(zhí)行結(jié)束后返回調(diào)用過(guò)程時(shí)得下一條指令繼續(xù)執(zhí)行。在每個(gè)過(guò)程被調(diào)用時(shí)在棧頂分配3

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

RA。第

5

題PL/0

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

INT

0

A（２）

OPR

0

0（３）

CAL

L

A答案：PL/0

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

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

條__________指令在code

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

0

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

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

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

0

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

與棧頂寄存器T

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

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

L

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

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

得值送指令地址寄存器P

中，使指令從A

開始執(zhí)行。第

6

題給出對(duì)

PL/0

語(yǔ)言作如下功能擴(kuò)充時(shí)得語(yǔ)法圖與EBNF

得語(yǔ)法描述。(1)

擴(kuò)充條件語(yǔ)句得功能使其為：if〈條件〉then〈語(yǔ)句〉[else〈語(yǔ)句〉](2)

擴(kuò)充repeat

語(yǔ)句為：repeat〈語(yǔ)句〉{；〈語(yǔ)句〉}until〈條件〉答案：對(duì)

PL/0

語(yǔ)言作如下功能擴(kuò)充時(shí)得語(yǔ)法圖與EBNF

得語(yǔ)法描述如下：(1)

擴(kuò)充條件語(yǔ)句得語(yǔ)法圖為：EBNF

得語(yǔ)法描述為：

〈條件語(yǔ)句〉::=

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

擴(kuò)充repeat

語(yǔ)句得語(yǔ)法圖為：EBNF

得語(yǔ)法描述為：

〈

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

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

章

文法與語(yǔ)言第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]得語(yǔ)言就是什么？答案:G[N]得語(yǔ)言就是V+。V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD、、

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

開頭得非負(fù)整數(shù)？第３題為只包含數(shù)字、加號(hào)與減號(hào)得表達(dá)式，例如9-2＋5，3-1，７等構(gòu)造一個(gè)文法。答案：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

題寫一文法，使其語(yǔ)言就是偶正整數(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á)式>::=<項(xiàng)>｜<表達(dá)式>＋<項(xiàng)><項(xiàng)>::=<因子>｜<項(xiàng)>*<因子><因子>::=（<表達(dá)式>）｜i試給出下述表達(dá)式得推導(dǎo)及語(yǔ)法樹。（５）i+(i+i)（６）i+i*i答案：<表達(dá)式><表達(dá)式>

+

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

+

<項(xiàng)><因子>i<項(xiàng)><因子>i<項(xiàng)><因子>i（

)(5)

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

+

<項(xiàng)><項(xiàng)>

*

<因子><因子>

i<項(xiàng)><因子>ii(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第7

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

*

aa

+

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

*

aa

+

a

*

a第8

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

(2)S=>aB=>abc即存在兩不同得最右推導(dǎo)。所以，該文法就是二義得?；蛘撸簩?duì)輸入字符串a(chǎn)bc，能構(gòu)造兩棵不同得語(yǔ)法樹，所以它就是二義得。Sa

Bb

cSA

ca

b第9

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

S

*S

S

+

aa

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

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

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

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

嵌套得括號(hào)（２）

就是二義得，因?yàn)閷?duì)于（）（）可以構(gòu)造兩棵不同得語(yǔ)法樹。第11

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

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

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

E+T*F

句型此句型相對(duì)于E

得短語(yǔ)有:E+T*F；相對(duì)于T

得短語(yǔ)有T*F直接短語(yǔ)為：T*F句柄為：T*F第13

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

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

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

可能有哪些元素？(3)找出該句子得所有短語(yǔ)、直接短語(yǔ)、句柄。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)該句子得短語(yǔ)有：a

就是相對(duì)A

得短語(yǔ)ε

就是相對(duì)S

得短語(yǔ)b

就是相對(duì)B

得短語(yǔ)εbb

就是相對(duì)B

得短語(yǔ)aa

就是相對(duì)S

得短語(yǔ)aεbbaa

就是相對(duì)S

得短語(yǔ)直接短語(yǔ)有：a

ε

b句柄就是：a第14

題給出生成下述語(yǔ)言得上下文無(wú)關(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

題給出生成下述語(yǔ)言得三型文法：(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

中得文法等價(jià)嗎？答案：等價(jià)。第18

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

字母表（２）

串、字與句子（３）

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

Z

x

,

x

∈V

*T

則稱

x

就是文法

G

得一個(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，因?yàn)镈

含有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

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

表示。因?yàn)?、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)

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

表示。因?yàn)?、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

表示。因?yàn)?

中含有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}，構(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

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

1A

B

AB

C

DC

C

ED

EE

F

AF

F

EDFA

得狀態(tài)圖：A0

10FED0BC《編譯原理》課后習(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}對(duì)非終態(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}對(duì){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

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

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

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

都有0

直接跟在右邊。并給出該語(yǔ)言得正規(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

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

為等價(jià)狀態(tài)，可合并。第６題設(shè)無(wú)符號(hào)數(shù)得正規(guī)式為θ：θ=dd*|dd*、dd*|、dd*|dd*10(s|ε)dd*|10(s|ε)dd*|、dd*10(s|ε)dd*|dd*、dd*10(s|ε)dd*化簡(jiǎn)θ，畫出θ得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

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構(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、2、3、4、5、6

表示。因?yàn)?、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進(jìn)行分割：P1＝（｛0,5,

6｝,｛1,2｝,｛3,4｝）再用b進(jìn)行分割：P2＝（｛0｝,｛5,

6｝,｛1,2｝,｛3,4｝）再用a、b

進(jìn)行分割，仍不變。再令｛０｝為A，｛1，2｝為B，｛3，4｝為C，｛5，6｝為D。最小化為：Aa

,

bD

CaaBbabb第８題給出下述文法所對(duì)應(yīng)得正規(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ī)式描述它所識(shí)別得語(yǔ)言。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

章

自頂向下語(yǔ)法分析方法第1

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

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

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

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

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

得句子。答案：(1)

對(duì)(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))對(duì)(((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

{,,ε}、

{)}、、對(duì)左部為N

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

（→,

S

N）={，}FIRST

（→ε）={ε}FOLLOW

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

→,

S

N)∩SELECT(N

→ε)

={，}∩

{

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

Analysis

Table）a

∧

(

)

,

#S

→a

→∧

→(T)T

→S

N

→S

N

→S

NN

→ε

→,

S

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

對(duì)輸入串（a,a）#得分析過(guò)程為：棧（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→ε可見(jià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}、、、對(duì)相同左部得產(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)得。預(yù)測(cè)分析表：a

o

d

e

f

b

#S

→a

→MH

→MH

→MH

→MH

→MHM

→K

→K

→K

→bLM

→KH

→ε

→LSo

→ε

→εL

→eH