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

第一章引論

第1題

解釋下列術(shù)語：

答案：

（1）編譯程序：如果源語言為高級(jí)語言，目標(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ò)處理工作和符

號(hào)表管理等工作。

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

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

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

第2題

答案：

一個(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)代碼，對(duì)中間代碼進(jìn)行等價(jià)變換處理。

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

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

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

中間結(jié)果都記錄在相應(yīng)的表格中?？梢哉f整個(gè)編譯過程就是造表、查表的工作過程。需要指

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

程序具有的表格管理功能。

錯(cuò)誤處理程序：處理和校正源程序中存在的詞法、語法和語義錯(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)行分析和處理。

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

就回答八部分。

第3題

答案：

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

序和匯編程序等。

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

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

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

源程序功能的實(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ù)。無論

是哪種方式，其加工結(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題

答案：

（1）語法分析

（2）語義分析

（3）語法分析

（4）詞法分析

第5題

答案：

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

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

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

譯

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

把語

言L1擴(kuò)充為L2,有LIL2,并用L1編寫L2的編譯程序T2,……，如此逐步擴(kuò)展下去,

好似滾雪球一樣，直到我們所要求的編譯程序。

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

第6題

答案：

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

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

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

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

總而言之，是邊翻譯邊執(zhí)行。

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

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

編譯型的高級(jí)語言比解釋型的高級(jí)語言更快。

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

第1題

答案：

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

varc,d;

procedurer;

vare,f;

begin(r)

callq;

end(r);

begin(s)

callr;

end(s);

begin(p)

calls;

end(p);

begin(main)

callp;

end(main).

答案：

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

第3題

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

name

kind

level/val

adr

size

答案：

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

name

kind

level/val

adr

size

x

variable

0

dx

y

variable

0

dx+1

procedure

0

過程p的入口（待填）

5

a

variable

1

dx

q

procedure

1

過程q的入口

4

s

procedure

1

過程s的入口（待填）

5

c

variable

2

dx

d

variable

2

procedure

2

過程r的入口

5

e

variable

3

dx

f

variable

3

dx+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與返回地址

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ī)的匯編語言，請(qǐng)說明該匯編語

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

(1)INTOA

(2)OPR00

(3)CALLA

答案：

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

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

INTOA

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

OPROO

在過程目標(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題

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

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

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

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

repeat〈語句〉｛；〈語句〉｝until〈條件〉

答案：

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

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

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

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

EBNF的語法描述為：〈重復(fù)語句〉：:=repeat〈語句〉｛；〈語句〉｝until〈條件〉

第3章文法和語言

第1題

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

S-*Ac|aB

A-*ab

B->bc

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

答案：

L(G[S])={abc}

第2題

文法G[N]為：

N-?D|ND

D-0|l|2|3|4|5|6|7|8|9

G[N]的語言是什么？

答案:

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

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

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

第3題

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

答案：

G[S]:

S->S+D|S-D|D

D->0|l|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...bbb

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

第5題

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

(1)允許0打頭；

⑵不允許0打頭。

答案：

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

E-*NT|D

T-NT|D

N-*D|1|3|5|7|9

D->0|2|4|6|8

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

E-NT|D

T-*FT|G

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

D-*2|4|6|8

FfN|0

G-D|O

第6題

已知文法G：

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

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

v因子》::二（〈表達(dá)式〉）Ii

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

（5）i+（i+i）

（6）i+i*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)

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

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

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

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

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

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

=＞＜項(xiàng)＞+由

=＞＜因子〉+i*i

=>i+i*i

〈表達(dá)式〉

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

〈因子〉

〈表達(dá)式〉

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

〈因子〉

〈項(xiàng)〉

〈因子〉

＜項(xiàng)＞

(因子＞

()

〈表達(dá)式〉

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

＜項(xiàng)＞*＜因子＞

〈因子〉i

＜項(xiàng)＞

(因子＞

1

第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*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

第8題

文法G[S]為：

S-*Ac|aB

Afab

B->bc

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

答案：

對(duì)于串a(chǎn)bc

(l)S=>Ac=>abc(2)S=>aB=>abc

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

或者：

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

第9題

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

SfSS*|SS+|a

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

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

答案:

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

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

⑵該文法生成的語言是：*和+的后綴表達(dá)式，即逆波蘭式。

S

Ac

ab

S

aB

bc

S

SS*

SS+a

aa

第10題

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

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

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

答案:

(1)嵌套的括號(hào)

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

第11題

令文法G[E]為:

E-?T|E+T|E-T

T-*F|T*F|T/F

F-(E)|i

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

答案：

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

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

以E+T*F句型

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

有T*F

直接短語為：T*F

句柄為：T*F

第13題

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

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

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

⑶找出該句子的所有短語、直接短語、句柄。

B

a

S

ABS

a

SBA

￡bba

答案:

(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-SBB|b

可能元素有：￡aaababbaaaaabbaa.......

(3)該句子的短語有：

a是相對(duì)A的短語

e是相對(duì)S的短語

b是相對(duì)B的短語

ebb是相對(duì)B的短語

aa是相對(duì)S的短語

aebbaa是相對(duì)S的短語

直接短語有：aeb

句柄是：a

第14題

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

(1){anbnambm|n,m>=0)

(2){InOmlmOn|n,m>=0}

(3){WaWr|W屬于{O|a}*,Wr表示W(wǎng)的逆}

答案：

(1)

S-AA

A-*aAb|￡

(2)

S-*1SO|A

A->OA1|￡

(3)

S-*OSO|1S1|￡

第16題

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

(l){an|n>=0}

(2){anbm|n,m>=l}

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

答案:

(l)S-*aS|￡

(2)

S->aA

A-*aA|B

B->bB|b

(3)

A->aA|B

B-bB|C

C一cC|e

第17題

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

答案:

等價(jià)。

第18題

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

(1)字母表

(2)串、字和句子

(3)語言、語法和語義

答案：

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

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

字：字母表中的元素。

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

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

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

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

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

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

附加題

問題1:

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

S-*OA|1B

A-*1S|1

B-OS|O

答案:

R=(01|10)(01|10)*

問題2：

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

G[A]:A—OB|1C

Bf1|1A|OBB

Cf0|0A|lCC

答案:

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

問題3：

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

構(gòu)造一文法，其定義的語言是由算符+,*,(,)和運(yùn)算對(duì)象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

AfaA|a

Bfe|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-bC|b

也可為(觀察得來):G[S]:SfdAAfa|aA|aBB-bB|e

問題5：

已知文法G：

EfE+T|E-T|T

T-*T*F|T/F|F

F~(E)|i

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

⑴i；

(2)i*i+i

(3)i+i*i

(4)i+(i+i)

答案：

⑴E=>T=>F=>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)=>i+(i+F)=>i+(i+i)

⑵

⑶

(4)

E+T

i

T

F

i

F

i

E

E+T

E+T

T

F

F

(E)

T

Fi

F

問題6：

已知文法G[E]:

E-ET+|T

T-TF*|F

F-FA|a

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

答案：

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

該句型相對(duì)于E的短語有FFAA*

相對(duì)于T的短語有FFAA*,F

相對(duì)于F的短語有FA;FAA

簡單短語有F;P

句柄為F.

問題7：

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

SfSaS.SbS.ScS.d

答案：

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

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

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

SfSaS.A

A-AbA.C

CfCcC.d

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

SfSaA.A

AfAbC.C

CfCcF.F

Ffd

該文法為非二義的。

問題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,we{a,b)*A|u|=|w|)

答案：

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

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

是

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

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

S-AB

Af￡.aAbb

Bf￡.cB

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

該語

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

S~AB

Af￡.aA

Bf￡.bBcc

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

S-aSb.aS.￡

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

S—aSd.A.D

AfbAd.B

DfaDc.B

BfbBc.e

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

對(duì)應(yīng)A,后一種情形對(duì)應(yīng)Do

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

S-Ab

ABAB.a

Ba.b

問題9：

下面的文法G（S）描述由命題變量p、q,聯(lián)結(jié)詞A（合?。?、V（析?。?、.（否定）構(gòu)

成的命題公式集合：

SSVT.T

T—TAF.F

Ff.F.p.q

試指出句型.FV.q八p的直接短語（全部）以及句柄。

答案：

直接短語：p.q，.F

句柄：.F

問題10：

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

答案:

xO=(aaa)O=8|xO|=O

xx=aaaaaa|xx|=6

x5=aaaaaaaaaaaaaaa|x5|=15

A+=A1UA2U???.UAnU??,={a,aa,aaa,aaaa,aaaaa***}

A*=AOUAlUA2U….UAn□???={e,a,aa,aaa,aaaa,aaaaa***}

問題11：

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

(xy)3

答案:

xy=abcb|xy|=4

xyz=abcbaab|xyz|=7

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

問題12：

已知文法G[Z]：Z：：=UOIVI、U：：=Z111、V：：=ZOI0,請(qǐng)寫出全部由此文

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

答案:

Z=>uo=>z10=>U010=>1010

Z=>uo=>z10=>V110=>0110

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

Z=>V1=>Z00=>V100=>0100

問題13：

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

答案：

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

B：：=bBcIbe描述的語言:{,bncn|n>=l}

L(G[S])={anbmcm|n>=O,m>=l)

問題14：

己知文法E：：=TIE+TIE-T、T：：=FIT*FIT/F、F：：=(E)Ii,寫出該文法的開

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

答案：

開始符號(hào)：E

VT={+,(,),i}

VN={E,F,T}

問題15：

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

答案：

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

問題16：

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

答案:

A::=1|3|5|7|9|NA

N::=NO|N1|N2|N3|N4|N5|N6|N7|N8|N9|

N::=0|l|2|3|4|5|6|7|8|9

S

s*s

S+Sa

aa

S

S+S

aS*S

aa

第4章詞法分析

第1題

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

(1)1(0|1)*101

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

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

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

答案:

⑴先構(gòu)造NFA：

用子集法將NFA確定化

0

1

X

A

A

A

AB

AB

AC

AB

AC

A

ABY

ABY

AC

AB

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

（NFA

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

0

X

A

A

A

B

B

C

B

C

A

D

D

C

B

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

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

用子集法將NFA確定化

0

1

X

X

TO=X

A

A

ABFL

T1=ABFL

Y

CG

Y

Y

CG

CGJ

T2=Y

T3=CGJ

DH

K

DH

DH

ABFKL

T4=DH

EI

EI

ABEFIL

T5=ABFKL

Y

CG

T6=ABEFIL

EJY

CG

EJY

ABEFGJLY

T7=ABEFGJLY

EHY

CGK

EHY

ABEFHLY

CGK

ABCFGJKL

T8=ABEFHLY

EY

CGI

EY

ABEFLY

CGI

CGJI

T9=ABCFGJKL

DHY

CGK

DHY

DHY

T10=ABEFLY

EY

CG

T11=CGJI

DHJ

K

DHJ

DHJ

T12=DHY

EI

T13=DHJ

EIK

EIK

ABEFIKL

T14=ABEFIKL

EJY

CG

X1A

eB

1COD1E

0

F1GOH110J1K

L

e€

0

E

￡

e

將TO、Tl>T2、T3、T4、T5、T6>T7、T8、T9、T1O、TlkT12、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

1

0

1

1

2

3

2

3

4

5

4

6

5

2

3

6

7

3

7

8

9

8

10

11

9

12

9

10

10

3

11

13

5

12

6

13

14

14

7

3

010

12

12

7

108

3

4

5

6

9

111314

1

1

0

1

0

1

0

1

1

0

1

1

0

1

0

1

01

0

1

0

1

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

先構(gòu)造NFA：

用子集法將NFA確定化

€

a

b

X

X

TO=X

A

A

ABCD

T1=ABCD

BE

BY

BE

ABCDE

BY

ABCDY

T2=ABCDE

BEF

BEY

BEF

ABCDEF

BEY

ABCDEY

T3=ABCDY

BE

BY

T4=ABCDEF

BEF

BEY

T5=ABCDEY

BEF

BEY

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

含有Y,

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

a

b

0

1

1

2

3

2

4

5

3

2

3

4

4

5

5

4

5

XaA

￡B

a,b

g

DaEaF

C

€

Y

b

￡

b

Oa1b3

2

a

5

a4

b

a

b

a

b

a

b

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

用子集法將NFA確定化:

a

b

X

X

TO=X

A

A

ABDEF

T1=ABDEF

CI

G

CI

CI

G

G

T2=CI

DY

DY

ABDEFY

T3=G

H

H

ABEFH

T4=ABDEFY

CI

G

T5=ABEFH

CI

G

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

Y,

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

a

b

0

1

1

2

3

2

4

3

5

4

2

3

5

2

3

DFA的狀態(tài)圖:

XA

b

eB

a

FbGbH

E

€

Y

CDbe

lb

€

g

E

Obib

2

a

4

5

3

b

b

a

b

a

b

第2題

已知NFA=({x,y,z},{O,l},M,{x},{z}),其中:M(x,O)={z},M(y,O)={x,y},,M(z,O)={x,z},

M(x,l)={x},M(y,l)=d),M(z,l)={y},構(gòu)造相應(yīng)的DFA。

答案：

先構(gòu)造其矩陣

0

1

x

z

X

y

x,y

z

x,z

y

用子集法將NFA確定化:

0

1

x

z

X

Z

XZ

y

XZ

XZ

xy

y

xy

xy

xyz

x

xyz

xyz

xy

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

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

0

1

A

B

A

B

C

D

C

C

E

D

E

E

F

A

F

F

E

DFA的狀態(tài)圖:

A

01

0

F

E

D

0

B

1

0

1

0

1

0

1

c

第3題

將下圖確定化:

答案：

用子集法將NFA確定化:

0

1

S

VQ

QU

VQ

VZ

QU

QU

V

QUZ

VZ

z

z

V

z

QUZ

VZ

QUZ

Z

Z

Z

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

0

1

S

A

B

A

C

B

B

D

E

C

F

F

D

F

E

C

E

F

F

F

DFA的狀態(tài)圖:

第4題

將下圖的(a)和(b)分別確定化和最小化:

答案:

初始分劃得

no：終態(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}

V{4}a{0},所以得到新分劃

ni：{0},{4},{1,2,3,5)

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

V{l,5}b(4)

{2,3}b{1,2,3,5},故得到新分劃

H2：{0},{4},{1,5},{2,3}

{l15}a{l,5}

{2,3}a{1,3},故狀態(tài)2和狀態(tài)3不等價(jià)，得到新分劃

H3：{0},{2},{3},{4},{1,5}

這是最后分劃了

最小DFA：

第5題

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

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

答案:

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

為

用子集法確定化：

I

10

II

{X,0』,3,Y}

[0,l,3,Y)

{2}

{L3,Y}

[0,l,3,Y)

{0,l,3,Y)

[1,3,Y)

{1,3,Y}

{2}

{2)

{2}

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

s

0

1

1

2

3

4

2

2

4

4

3

3

3

DFA的狀態(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)，可合并。

第6題

設(shè)無符號(hào)數(shù)的正規(guī)式為9：

0=dd*|dd*.dd*|.dd*|dd*lO(s|8)dd*

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

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

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

答案：

先構(gòu)造NFA：

用子集法將NFA確定化:

X

d

.B

d

FG

d

H

10

d

A

￡

c

10

d

D

Ed

Y

d

d

E

S

10

d

X

XA

T0=XA

B

F

A

B

B

F

FG

A

A

T1=B

C

C

c

T2=FG

G

H

G

G

H

T3=A

B

F

A

T4=C

D

C

D

DE

T5=G

H

T6=H

H

T7=DE

E

Y

E

E

Y

Y

T8=E

Y

T9=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、9o

s

10

d

0

1

2

3

1

4

2

5

6

3

1

2

3

4

7

4

5

6

6

6

7

8

9

9

9

DFA的狀態(tài)圖:

第7題

給文法G[S]：

S-*aA|bQ

A->aA|bB|b

B->bD|aQ

Q->aQ|bD|b

D-bB|aA

EfaB|bF

F—bD|aE|b

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

答案：

先構(gòu)造其NFA：

用子集法將NFA確定化:

d

6

25

d

3

d

d

47

8

9

0

1

10

d

10

10

d

d

s

d

d

d

S

a

A

a

Z

Q

b

B

D

a

E

b

F

b

b

a

b

a

a

b

bb

b

a

b

a

b

S

A

Q

A

A

BZ

Q

Q

DZ

BZ

Q

D

DZ

A

B

D

A

B

B

Q

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

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

a

b

0

1

2

1

1

3

2

2

4

3

2

5

4

6

5

1

6

6

2

5

DFA的狀態(tài)圖:

令P0=({03,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。

最小化為：

0

a

a

5

2

b

3

a

a

b

4

1

6

b

a

a

b

b

b

a

b

第8題

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

SfOA|lB

A-1S|1

B-OSIO

答案：

解方程組S的解:

S=OA|1B

A=1S|1

B=OS|O

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

S=01S|01|10S|10=(01|10)S|(01|10)

所以：S=(01110)*(01110)

第9題

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

A

a,b

DC

a

a

B

b

a

b

b

1

a

2

6

c

3

c

b

5

47

b

b

ab

b

b

d

d

a

答案：

令P0=({1,2,345},{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。

最小化為：

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

A

a

CD

b

d

B

b

c

a

b

附加題

問題1:

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

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

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

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

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

e)包含ab子串的所有串

0不包含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：

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

a)0*(10+)*0*

b)(0|1)*(00111)(0|1)*

c)1(0|1)*0

答案：

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

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

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

問題3：

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

a)構(gòu)造一個(gè)DFA,接受字母表.(0,1)上的以01結(jié)尾的所有串

b)構(gòu)造一個(gè)DFA,接受字母表.{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

答案:

b)

c)

最小化的DFA

問題4：

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

問題5：

已知正規(guī)式：

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

(2)(a|b)*b.

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

分析：

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

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

答案:

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

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

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

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

a

b

X124

1234

124Y

1234

1234

124Y

124Y

1234

124Y

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

a

B

1

2

3

2

2

3

3

2

3

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

a

b

1

2

3

2

3

a

b

X12

12

12Y

12

12

12Y

12Y

12

12Y

可化簡得下表

a

b

1

2

3

2

2

3

得DFA圖

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

對(duì)相應(yīng)正規(guī)文法，令A(yù)對(duì)應(yīng)1,B對(duì)應(yīng)2

故為：

A->aA|bB|b

BfaA|bB|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,Sfb(a|b),AfaA,Afb(a|b)

變換為SfaA,SfbB,B-(a|b),A-aA,AfbC,Cf(a|b)

變換為S-aA,SfbB,Bfa,B-b,AfaA,AfbC,Cfa,Cfb

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

SfaA,SfbB,B—a,Bfb,AaA,A-*bC,Cfa,Cfb

或表示為：

SfaA|bB,B-*a|b,A—■aA|bC,Cfa|b

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

問題7：

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

答案：

G[P]：

PfOP.lP.lQ

QfOR.lR

Rf￡

問題8：

考慮如下文法G[S]：

SfOS.1S.1A

AfOB.IB

Bf￡

a)試構(gòu)造語言為L(G)的一個(gè)正規(guī)表達(dá)式。

b)試構(gòu)造語言為L(G)的一個(gè)有限自動(dòng)機(jī)。

答案：

a)

由A-OB,B￡得Af0;

由AfIB,B—e得A-1;

由Af0,Af1得A-0.1;

由Sf1A,Af0.1得S-1(0.1);

由Sf1A,A-0.1得Sf1(0.1);

由SfOS,Sf1(0.1)得Sf0*1(0.1);

由SfIS,Sf1(0.1)得Sf1*1(0.1);

由Sf0*1(0.1),Sf1*1(0.1)得Sf0*1(0.1).1*1(0.1);

所以，一個(gè)可能的正規(guī)表達(dá)式為：

0*1(0.1).1*1(0.1)

b)

第5章自頂向下語法分析方法

第1題

對(duì)文法G[S]

S-a|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ù)測分析表。

(4)給出輸入串(a,a)#的分析過程，并說明該串是否為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),A,S),S)

(((a,a),A,(T)),S)

(((a,a),A,(S)),S)

(((a,a),A,(a)),S)

(((a,a),A,(a)),a)

(2)改寫文法為:

O)S-a

l)Sf八

2)S-(T)

3)TfSN

4)N-,SN

5)N-e

非終結(jié)符

FIRST集

FOLLOW集

S

{a,A,()

(#,?)}

T

(a,A,()

{)}-..

N

{?￡).

對(duì)左部為N的產(chǎn)生式可知：

FIRST(-,SN)={,}

FIRST(-￡)={￡}

FOLLOW(N)={)}

由于SELECT(N-,SN)nSELECT(N-e)={,}D{)}=

所以文法是LL(1)的。

預(yù)測分析表(PredictingAnalysisTable)

a

A

(

)

#

s

-a

一八

一⑴

T

一SN

-SN

一SN

N

一,SN

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

(3)對(duì)輸入串(a,a)#的分析過程為:

棧(STACK)

當(dāng)前輸入符

(CUR_CHAR)

剩余輸入符

(INOUT_STRING)

所用產(chǎn)生式

(OPERATION)

#S

#)T(

#)T

#)NS

#)Na

#)N

#)NS,

#)NS

#)Na

#)N

#)

#

a

a

a

>

*

a

a

)

)

#

a,a)#…

a,a)#...

,a)#…

,a)#…

a)#...

a)#...

)#...

)#...

#...

#...

Sf(T)

T-*SN

S-*a

N一,SN

S-a

N-e

可見輸入串（a,a）#是文法的句子。

第3題

已知文法G[S]：

S->MH|a

H->LSo|￡

K->dML|￡

L-eHf

M-*K|bLM

判斷G是否是LL(1)文法，如果是，構(gòu)造LL(1)分析表。

答案：

文法展開為：

0)SfMH

1)S-*a

2)H-LSo

3)H-*e

4)K-*dML

5)”e

6)L-eHf

7)M-K

8)M-bLM

非終結(jié)符

FIRST集

FOLLOW集

S

{a,d,b,8,e}

{#,。}.?……

M

{d,8,b}....

{e,#,o}……

H

￡e}……

{#,f,o}……

L

{e}........

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

K

{d間……

{e,#,o}……

對(duì)相同左部的產(chǎn)生式可知：

SELECT(S-MH)ASELECT(S^a)={d,b,e,#,o}n{a}=

SELECT*LSo)nSELECT(H-e)={e}P{#,f,o}=

SELECT("dML)CSELECT("e)={d)D{e,#,o}=

SELECT(M-K)ASELECT(M-*bLM)={d,e,#,o}C=

所以文法是LL(1)的。

預(yù)測分析表:

a

0

d

e

f

b

#

S

-*a

一MH

fMH

一MH

fMH

fMH

M

一K

一K

-K

bLM

一K

H

fE

fLSo

f￡

fE

L

feHf

fdML

f€

f￡

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

第7題

對(duì)于一個(gè)文法若消除了左遞歸，提取了左公共因子后是否一定為LL(1)文法?試對(duì)下面

文法進(jìn)行改寫，并對(duì)改寫后的文法進(jìn)行判斷。

(1)A-baB|￡

B->Abb|a

(2)A-*aABe|a

BfBb|d

(3)S-*Aa|b

AfSB

Bfab

答案：

(1)先改寫文法為:

0)A-*baB

1)A—e

2)BfbaBbb

3)B-*bb

4)B-*a

再改寫文法為:

0)A-*baB

1)A一e

2)B-bN

3)B~*a

4)N-aBbb

5)N-b

FIRST

FOLLOW

A



{#}

B

{b,a}

優(yōu)b}

N

{b,a}

{#，b}

預(yù)測分析表:

a

b

#

A

fbaB

f￡

B

-a

fbN

N

faBbb

fb

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

(2)文法：

A-*aABe|a

B-Bb|d

提取左公共因子和消除左遞歸后文法變?yōu)椋?/p>

0)A-*aN

l)N-ABe

2)N—s

3)B-dNl

4)NLbNl

5)N1-e

非終結(jié)符

FIRST集

FOLLOW集

A

{a}-

{禮d}

B

lxondcc…

{e}..

N

{a同

{#,d}

N1

{b同

{e}-

對(duì)相同左部的產(chǎn)生式可知：

SELECT(NfABe)nSELECT(N-e)={a}C{和d}=

SELECT(N1bN1)ASELECT(N1-e)=A{e}=

所以文法是LL(1)的。

預(yù)測分析表(PredictingAnalysisTable)

iNq一

31*-

IN

INP一

a

N?一

V

#

P

q

9

N

fABe

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

(3)文法:

S-Aa|b

A-SB

B->ab

第1種改寫:

用A的產(chǎn)生式右部代替S的產(chǎn)生式右部的A得:

S-SBa|b

B-ab

消除左遞歸后文法變?yōu)椋?/p>

O)S-*bN

l)N-BaN

2)N-e

3)B-ab

非終結(jié)符

FIRST集

FOLLOW集

S

…

{#}

B

{al-

ia)

N

{￡，a}

[#)

對(duì)相同左部的產(chǎn)生式可知：

SELECTIN'BaN)ASELECT(N-e)={a}C{#}=

所以文法是LL(1)的。

預(yù)測分析表(PredictingAnalysisTable)

a

b

#

S

fbN

B

—ab

N

fBaN

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

第2種改寫:

用S的產(chǎn)生式右部代替A的產(chǎn)生式右部的S得:

S-Aa|b

A-AaB|bB

B-*ab

消除左遞歸后文法變?yōu)椋?/p>

O)S-Aa

l)S-*b

2)AfbBN

3)N-aBN

4)N-￡

5)B-*ab

非終結(jié)符

FIRST集

FOLLOW集

S

-

{#}

A

…

{a}

B

{a}…

{a}

N

{a,G

{a}

對(duì)相同左部的產(chǎn)生式可知：

SELECT(S-Aa)ASELECT(S-b)=D=#

SELECT(N-*aBN)nSELECT(N->e)={a}C{a}={a}W

所以文法不是LL(1)的。

預(yù)測分析表:

a

b

#

S

fAa..

fb....

A

->bBN

B

-*ab..

N

aBN

fe...

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

附加題

問題1:

已知文法G[A]如下，試用類C或類PASCAL語言寫出其遞歸下降子程序.(主程序不需

寫)

G[A]:A-[B

B—X]{A}

X-(a|b){a|b}

答案：

不妨約定:在進(jìn)入一個(gè)非終結(jié)符號(hào)相應(yīng)的子程序前，已讀到一個(gè)單詞.word：存放當(dāng)前讀

到的單詞，Getsym()為一子程序，每調(diào)用一次，完成讀取一單詞的工作。error。為出錯(cuò)處理

程序.FIRST(A)為終結(jié)符A的FIRST集.

類C程序如下：

voidA()

(

ifword=='['

(

Getsym();

B()；

elseerror();

voidB()

(x()；

ifword==']'

(

Getsym();

while(wordin

FIRST(A))

A();

)

elseerror();

)

voidX()

(

if(word==,a,||word==,b')

(

Getsym();

while(word==,a'||word==,b,)

Getsym();

)

elseerror();

)

問題2：

設(shè)有文法G[A]的產(chǎn)生式集為：

A—BaC|CbB

B-*Ac|c

C-Bb|b

試消除G[A]的左遞歸。

答案：

提示：不妨以A、B、C排序.先將A代入B中，然后消除B中左遞歸；再將A、B代

入C中。再消除C中左遞歸。

最后結(jié)果為:G[A]:

A-*BaC|CbBB-CbBcB'|cB'B」aCcB'le

C-*cB'bC'IbCC'fbBcB'bC'l￡

問題3：

試驗(yàn)證如下文法G[E]是LL(1)文法:

Ef[F]E,

E'fE.e

FfaF'

F'faF'.e

其中E,F,E',F'為非終結(jié)符

答案：

各非終結(jié)符的FIRST集和FOLLOW集如下：

FIRST(E)={[}FOLLOW(E)={#}

FIRST(E')={[,E}FOLLOW(E')={#}

FIRST(F)={a}FOLLOW(F)={]}

FIRST(F‘)={a,e)FOLLOW(F')={]}

對(duì)于E'