編譯原理(第二版) 第2版課后習題答案詳解_第1頁
編譯原理(第二版) 第2版課后習題答案詳解_第2頁
編譯原理(第二版) 第2版課后習題答案詳解_第3頁
編譯原理(第二版) 第2版課后習題答案詳解_第4頁
編譯原理(第二版) 第2版課后習題答案詳解_第5頁
已閱讀5頁,還剩243頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

第一章引論

第1題

解釋下列術(shù)語:

答案:

(1)編譯程序:如果源語言為高級語言,目標語言為某臺計算機上的匯編語言或機器語

言,則此翻譯程序稱為編譯程序。

(2)源程序:源語言編寫的程序稱為源程序。

(3)目標程序:目標語言書寫的程序稱為目標程序。

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

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

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

號表管理等工作。

(5)后端:指那些依賴于目標機而一般不依賴源語言,只與中間代碼有關(guān)的那些階段,

即目標代碼生成,以及相關(guān)出錯處理和符號表操作。

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

第2題

答案:

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

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

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

詞法分析程序:輸人源程序,拼單詞、檢查單詞和分析單詞,輸出單詞的機內(nèi)表達形式。

語法分析程序:檢查源程序中存在的形式語法錯誤,輸出錯誤處理信息。

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

中。

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

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

中間代碼優(yōu)化程序:為了產(chǎn)生高質(zhì)量的目標代碼,對中間代碼進行等價變換處理。

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

表格管理程序:負責建立、填寫和查找等一系列表格工作。表格的作用是記錄源程序的

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

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

出的是,這里的“表格管理程序”并不意味著它就是一個獨立的表格管理模塊,而是指編譯

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

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

程序中的錯誤時,錯誤處理程序負責報告出錯的位置和錯誤性質(zhì)等信息,同時對發(fā)現(xiàn)的錯誤

進行適當?shù)男Uㄐ迯停?,目的是使編譯程序能夠繼續(xù)向下進行分析和處理。

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

就回答八部分。

第3題

答案:

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

序和匯編程序等。

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

寫的目標程序的翻譯程序。

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

源程序功能的實現(xiàn)完全由解釋程序承擔和完成,即每讀出源程序的一條語句的第一個單詞,

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

能的實現(xiàn),完成后返回到解釋程序的總控部分再讀人下一條語句繼續(xù)進行解釋、執(zhí)行,如此

反復;另一種方式是,一邊翻譯一邊執(zhí)行,即每讀出源程序的一條語句,解釋程序就將其翻

譯成一段機器指令并執(zhí)行之,然后再讀人下一條語句繼續(xù)進行解釋、執(zhí)行,如此反復。無論

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

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

中間代碼程序,最后得到運行結(jié)果。

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

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

程序翻譯成目標程序,輸出與源程序等價的目標程序,而目標程序的執(zhí)行任務由操作系統(tǒng)來

完成,即只翻譯不執(zhí)行。

第4題

答案:

(1)語法分析

(2)語義分析

(3)語法分析

(4)詞法分析

第5題

答案:

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

(2)交叉編譯:A機器上的編譯程序能產(chǎn)生B機器上的目標代碼。

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

程序TO,再把語言L0擴充到L1,此時L0.L1,并用L0編寫L1的編譯程序T1,再

把語

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

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

(4)移植:將A機器上的某高級語言的編譯程序搬到B機器上運行。

第6題

答案:

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

像Basic之類的語言,屬于解釋型的高級語言。它們的特點是計算機并不事先對高級語

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

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

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

像C,Pascal之類的語言,屬于編譯型的高級語言.它們的特點是計算機事先對高級語

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

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

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

第1題

答案:

PL/O語言允許過程嵌套定義和遞歸調(diào)用,它的編譯程序在運行時采用了棧式動態(tài)存儲

管理。(數(shù)組CODE存放的只讀目標程序,它在運行時不改變。)運行時的數(shù)據(jù)區(qū)S是由

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

個過程(包括主程序)被調(diào)用時,才分配數(shù)據(jù)空間,退出過程時,則所分配的數(shù)據(jù)空間被釋放。

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

第2題

若PL/O編譯程序運行時的存儲分配策略采用棧式動態(tài)分配,并用動態(tài)鏈和靜態(tài)鏈的方

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

運行棧的布局示意圖。

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時運行棧的布局示意圖為:

第3題

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

name

kind

level/val

adr

size

答案:

題2中當程序編譯到r的過程體時的名字表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,最新活動記錄基地址指針B,動態(tài)鏈指針DL,靜態(tài)鏈指針SL與返

回地址RA的用途。

答案:

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

RA的用途說明如下:

T:棧頂寄存器T指出了當前棧中最新分配的單元(T也是數(shù)組S的下標)。

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

也稱基地址。

SL:靜態(tài)鏈,指向定義該過程的直接外過程(或主程序)運行時最新數(shù)據(jù)段的基地址,

用以引用非局部(包圍它的過程)變量時,尋找該變量的地址。

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

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

RA:返回地址,記錄調(diào)用該過程時目標程序的斷點,即調(diào)用過程指令的下一條指令的

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

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

第5題

PL/O編譯程序所產(chǎn)生的目標代碼是一種假想棧式計算機的匯編語言,請說明該匯編語

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

(1)INTOA

(2)OPR00

(3)CALLA

答案:

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

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

INTOA

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

OPROO

在過程目標程序的出口處,釋放數(shù)據(jù)段(退棧),恢復調(diào)用該過程前正在運行的過程的

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

使

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

CALLA

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

址寄存器B中,目標程序的入口地址A的值送指令地址寄存器P中,使指令從A開始

執(zhí)行。

第6題

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

(1)擴充條件語句的功能使其為:

if〈條件〉then〈語句〉[else〈語句〉]

(2)擴充repeat語句為:

repeat〈語句〉{;〈語句〉}until〈條件〉

答案:

對PL/O語言作如下功能擴充時的語法圖和EBNF的語法描述如下:

(1)擴充條件語句的語法圖為:

EBNF的語法描述為:〈條件語句〉:kif〈條件〉then〈語句〉[else〈語句〉]

(2)擴充repeat語句的語法圖為:

EBNF的語法描述為:〈重復語句〉::=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開頭的非負整數(shù)?

第3題

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

答案:

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表達式>::=<項>I<表達式〉+〈項〉

V項〉::=v因子>I<項>*〈因子〉

v因子》::二(〈表達式〉)Ii

試給出下述表達式的推導及語法樹。

(5)i+(i+i)

(6)i+i*i

答案:

(5)〈表達式〉

二><表達式>+<項>

二〉<表達式〉+《因子)

二><表達式>+(〈表達式》)

二><表達式>+(〈表達式>+<項〉)

=><表達式>+(〈表達式〉+〈因子〉)

=><表達式>+(〈表達式〉+i)

=><表達式>+(〈項>+i)

=><表達式>+(〈因子〉+i)

二><表達式>+(i+i)

=><項>+(i+i)

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

=>i+(i+i)

(6)〈表達式〉

=><表達式>+<項>

=><表達式>+<項〉*<因子〉

=><表達式>+<項〉*i

=><表達式〉+<因子>*i

=><表達式>+i*i

=><項>+由

=><因子〉+i*i

=>i+i*i

〈表達式〉

〈表達式〉+<項>

〈因子〉

〈表達式〉

〈表達式〉+<項>

〈因子〉

〈項〉

〈因子〉

<項>

(因子>

()

〈表達式〉

〈表達式〉+〈項〉

<項>*<因子>

〈因子〉i

<項>

(因子>

1

第7題

證明下述文法G[〈表達式〉]是二義的。

〈表達式〉::=a|(〈表達式〉)|〈表達式〉〈運算符〉〈表達式〉

〈運算符〉::=+卜|*|/

答案:

可為句子a+a*a構(gòu)造兩個不同的最右推導:

最右推導1〈表達式〉〈表達式〉〈運算符〉〈表達式〉

〈表達式〉〈運算符〉a

〈表達式〉*a

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

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

〈表達式〉+a*a

a+a*a

最右推導2〈表達式〉〈表達式〉〈運算符〉〈表達式〉

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

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

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

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

〈表達式〉+a*a

a+a*a

第8題

文法G[S]為:

S-*Ac|aB

Afab

B->bc

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

答案:

對于串a(chǎn)bc

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

即存在兩不同的最右推導。所以,該文法是二義的。

或者:

對輸入字符串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*的最右推導如下

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

⑵該文法生成的語言是:*和+的后綴表達式,即逆波蘭式。

S

Ac

ab

S

aB

bc

S

SS*

SS+a

aa

第10題

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

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

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

答案:

(1)嵌套的括號

(2)是二義的,因為對于()()可以構(gòu)造兩棵不同的語法樹。

第11題

令文法G[E]為:

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

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

F-(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題

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

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

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

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

B

a

S

ABS

a

SBA

£bba

答案:

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

可能元素有:£aaababbaaaaabbaa.......

(3)該句子的短語有:

a是相對A的短語

e是相對S的短語

b是相對B的短語

ebb是相對B的短語

aa是相對S的短語

aebbaa是相對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題

習題7和習題11中的文法等價嗎?

答案:

等價。

第18題

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

(1)字母表

(2)串、字和句子

(3)語言、語法和語義

答案:

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

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

字:字母表中的元素。

句子:如果Zx,xeV*T則稱x是文法G的一個句子。+

(3)語言:它是由句子組成的集合,是由一組記號所構(gòu)成的集合。程序設計的語言就是所

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

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

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

語義:表示按照各種表示方法所表示的各個記號的特定含義。語言所代表的含義。

附加題

問題1:

給出下述文法所對應的正規(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符號串組成,串中0和1的個數(shù)相同.

問題3:

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

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

答案一:

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

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

答案:

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

相應的正規(guī)文法為(由自動機化簡來):

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

試給出下述表達式的推導及語法樹

⑴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“*是文法的句型,指出該句型的短語、簡單短語和句柄.

答案:

該句型對應的語法樹如下:

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

相對于T的短語有FFAA*,F

相對于F的短語有FA;FAA

簡單短語有F;P

句柄為F.

問題7:

適當變換文法,找到下列文法所定義語言的一個無二義的文法:

SfSaS.SbS.ScS.d

答案:

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

進一步變換,即可消除二義性。

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

SfSaS.A

A-AbA.C

CfCcC.d

規(guī)定結(jié)合性為左結(jié)合,進一步將文法變換為:

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)文法的特點,要產(chǎn)生形如anb2ncm的串,可以分別產(chǎn)生形如anb2n和

形如cm的串。設計好的文法是否就是該語言的文法?嚴格地說,應該給出證明。但若不

特別指明,通??梢院雎赃@一點。

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

S-AB

Af£.aAbb

Bf£.cB

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

該語

言,存在一個由以下產(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時,b不少于c;反之,a不少于d時,b不多于co前一種情形通過

對應A,后一種情形對應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:

設字母表A={a},符號串x=aaa,寫出下列符號串及其長度: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,寫出如下符號串及它們的長度: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,請寫出全部由此文

法描述的只含有四個符號的句子。

答案:

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,寫出該文法的開

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

答案:

開始符號:E

VT={+,(,),i}

VN={E,F,T}

問題15:

設有文法G[S]:S::=S*S|S+S|(S)|a,該文法是二義性文法嗎?

答案:

根據(jù)所給文法推導出句子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ī)式相應的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),令AB為B、AC為C、ABY為D,因為D含有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表示。因為2、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表示。因為3、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表示。因為4中含有

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)造相應的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表示。因為B、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}

對非終態(tài)組進行審查:

(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)

對{1,2,3,5}進行審查:

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不等價,得到新分劃

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

這是最后分劃了

最小DFA:

第5題

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

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

答案:

按題意相應的正規(guī)表達式是(0*10)*0*,或0*(0|10)*0*構(gòu)造相應的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為等價狀

態(tài),可合并。

第6題

設無符號數(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)造相應的最小的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表示。因為3、

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進行分割:

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

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

再令{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題

給出下述文法所對應的正規(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ī)式描述它所識別的語言。

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進行分割:

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

再令{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ù)個b但不含a的所有串

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

d)只包含一個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:

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

a)0*(10+)*0*

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

c)1(0|1)*0

答案:

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

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

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

問題3:

構(gòu)造有窮自動機.

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

b)構(gòu)造一個DFA,接受字母表.{0,1)上的不包含01子串的所有串.

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

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

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

答案:

b)

c)

最小化的DFA

問題4:

設有如圖所示狀態(tài)轉(zhuǎn)換圖,求其對應的正規(guī)表達式。

問題5:

已知正規(guī)式:

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

(2)(a|b)*b.

試用有限自動機的等價性證明正規(guī)式(1)和(2)是等價的,并給出相應的正規(guī)文法。

分析:

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

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

答案:

可通過消結(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圖

兩圖完全一樣,故兩個自動機完全一樣,所以兩個正規(guī)文法等價。

對相應正規(guī)文法,令A對應1,B對應2

故為:

A->aA|bB|b

BfaA|bB|b

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

問題6:

考慮正規(guī)表達式r=a*b(a|b),構(gòu)造可以生成語言L(r)的一個正規(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

所以,一個可能的正規(guī)文法為G[S]:

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

或表示為:

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

(適當?shù)葍r變換也可以,但要作說明,即要有步驟)

問題7:

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

答案:

G[P]:

PfOP.lP.lQ

QfOR.lR

Rf£

問題8:

考慮如下文法G[S]:

SfOS.1S.1A

AfOB.IB

Bf£

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

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

答案:

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);

所以,一個可能的正規(guī)表達式為:

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

b)

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

第1題

對文法G[S]

S-a|A|(T)

T-T,S|S

(1)給出(a,(a,a))和(((a,a),八,(a)),a)的最左推導。

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

(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),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

{?£).

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

FIRST(-,SN)={,}

FIRST(-£)={£}

FOLLOW(N)={)}

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

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

a

A

(

)

#

s

-a

一八

一⑴

T

一SN

-SN

一SN

N

一,SN

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

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

棧(STACK)

當前輸入符

(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}……

對相同左部的產(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)的。

預測分析表:

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£

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

第7題

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

文法進行改寫,并對改寫后的文法進行判斷。

(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}

預測分析表:

a

b

#

A

fbaB

f£

B

-a

fbN

N

faBbb

fb

由預測分析表中無多重入口判定文法是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

0t0rsy2…

{e}..

N

{a同

{#,d}

N1

{b同

{e}-

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

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

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

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

iNq一

31*-

IN

INP一

a

N?一

V

#

P

q

9

N

fABe

也可由預測分析表中無多重入口判定文法是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}

[#)

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

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

所以文法是LL(1)的。

預測分析表(PredictingAnalysisTable)

a

b

#

S

fbN

B

—ab

N

fBaN

也可由預測分析表中無多重入口判定文法是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}

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

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

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

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

預測分析表:

a

b

#

S

fAa..

fb....

A

->bBN

B

-*ab..

N

aBN

fe...

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

附加題

問題1:

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

寫)

G[A]:A-[B

B—X]{A}

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

答案:

不妨約定:在進入一個非終結(jié)符號相應的子程序前,已讀到一個單詞.word:存放當前讀

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

程序.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:

設有文法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:

試驗證如下文法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')={]}

對于E'

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論