編譯原理課后習(xí)題答案解析+清華大學(xué)出版社第二版

第1章引論

第1題

解釋下列術(shù)語：

(1)編譯程序

(2)源程序

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

(4)編譯程序的前端

(5)后端

(6)遍

答案：

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

言'則此翻譯程序稱為編譯程序C

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

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

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

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

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

號表管理等工作。

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

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

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

第2題

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

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

答案：

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

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

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

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

語法分析程序：檢查源程序中存在的形式語法錯誤，揄出錯誤怒理信息。

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

中。

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

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

范文范例參考

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

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

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

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

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

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

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

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

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

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

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

就回答八部分。

第3題

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

答案：

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

序和匯編程序等。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第4題

對下列錯誤信息，請指出可能是編譯的哪個階段（詞法分析、語法分析、語義分析、代

碼生成）報告的。

（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)代碼。

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

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

再把語

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

去，

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

范文范例參考

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

第6題

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

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

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

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

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

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

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

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

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

范文范例參考

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

第1題

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

答案：

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

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

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

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

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

第2題

若PL/0編譯程序運行時的存儲分配策略采用棧式動態(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中當(dāng)程序編譯到r的過程體時的名字表table的

內(nèi)容。

namekindlevel/valadrsize

答案：

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

namekindlevel/valadrsize

Xvariable0dx

yvariable0dx+1

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

avariable1dx

qprocedure1過程q的入口4

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

cvariable2dx

dvariable2dx

范文范例參考

rprocedure2過程r的入口5

evariable3dx

fvariable3dx+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指出了當(dāng)前棧中最新分配的單元(T也是數(shù)組S的下標(biāo))。

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ù)空間時，恢復(fù)調(diào)用該過程前運行棧的狀態(tài)。

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

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

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

第5題

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

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

(1)INT0A

(2)OPR00

(3)CALLA

答案：

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

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

INT0A

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

OPR00

范文范例參考

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

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

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

CALLA

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

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

第6題

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

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

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

(2)擴(kuò)充repeat語句為：repeat〈語句〉｛；〈語句〉｝until〈條件〉

答案：

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

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

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

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+oy={0,1,2,3,4,5,6,7,8,9)

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

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

第3題

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

答案：

G[S]:

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

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

第4題

已知文法G[Z]：

Z->aZb|ab

完美Word格式整理版

范文范例參考

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

答案：

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

nn

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

第5題寫一文法，使其語言是偶正整數(shù)的集合。

要求：

(1)允許0打頭；(2)不允

許0打頭。

答案：(1)允許0開頭的偶正整數(shù)

集合的文法

E-*NT|D

T-NTID

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

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

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

E->NT|D

T->FT|G

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

D-2|4|6|8

FfNIO

G->D|O

第6題

已知文法G:

<表達(dá)式)：：=<項)|<表達(dá)式>+<項)

<項>::=<因子)|<項>*<因子)

〈因子)：：=(<表達(dá)式))Ii

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

(5)i+(i+i)

(6)i+i*i

范文范例參考

答案：

（5）〈表達(dá)式）

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

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

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

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

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

=＞＜表達(dá)式＞+（＜表達(dá)式＞+i）=＞＜表達(dá)式＞+（＜項）

+i）

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

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

=><項)+(i+i)

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

=>i+(i+i)

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

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

=＞＜表達(dá)式）+＜項＞*＜因子）

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

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

范文范例參考

=><表達(dá)式>+i*i

=><項>+i*i

=><因子>+i*i

=>i+i*i

第7題證明下述文法G［〈表達(dá)式〉］是

二義的。

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

〈運算符〉：：=+|-|*|/

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

推導(dǎo)1〈表達(dá)式〉=〈表達(dá)式〉〈運算符〉〈表達(dá)式〉

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

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

=>〈表達(dá)式〉〈運算符〉〈表達(dá)式〉*a

=?〈表達(dá)式〉〈運算符〉a*a

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

最右推導(dǎo)2〈表達(dá)式〉=〈表達(dá)式〉〈運算符〉〈表達(dá)式〉=?〈表達(dá)式〉〈運算

符〉〈表達(dá)式〉〈運算符〉〈表達(dá)式）

=〈表達(dá)式〉〈運算符〉〈表達(dá)式〉〈運算符〉a

=>〈表達(dá)式〉〈運算符〉〈表達(dá)式〉*a

二〈表達(dá)式〉〈運算符〉a*a

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

第8題

文法G［S］為：

S->Ac|aB

A-*ab

B->bc

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

范文范例參考

答案：

對于串a(chǎn)be

(1)S=>Ac=>abc(2)S=>aB=>abc即存在兩不同的最右推導(dǎo)。所以，該文法是二義的。

或者：

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

b

第9題

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

S->SS*|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*

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

第10題

文法S-S(S)S|e

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

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

完美Word格式整理版

范文范例參考

答案：

(1)嵌套的括號

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

第11題令文法

G[E]為:

E-TIE+TIE-TT->F|T*F|T/F

F->(E)|i

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

答案：

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

或者：因為存在推導(dǎo)序列：E=>E+T=>E+T*E?所以

E+T*F句型

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

短語

有T*F

直接短語為：T*F句柄為：T*F

第13題

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

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

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

索？

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

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)生式有：SfABS|Aa|￡A-aB-SBBIb可能元素有：

￡aaababbaaaaabbaa.

(3)該句子的短語有：a是

相對A的短語E是

相對S的短語b是相

對B的短語￡bb是

相對B的短語aa是

相對S的短語

aEbbaa是相對S的

短語

直接短語有：a￡b

句柄是：a

第14題

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

(1){aVaV|n*m>=0}

(2){IVIVIn，m>=0}

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

答案：(1)

S—AA

A-*aAb|E

(2)

S—1S0IA

A^OAl|￡

(3)

S->OSO|1S1|s

第16題給出生成下述語言的三型文

法：

(l){an|n>=0}

范文范例參考

(2){a*VIn,m>=l}

(3){anb'ck|n,m,k>=0}

答案：

(1)S-aSIe

(2)

S-*aA

A-aA|B

B-*bB|b

(3)

A—aAIB

B->bB|C

C—cC|t

第17題

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

答案：

等價。

第18題

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

字母表

（2）串、字和句子

（3）語言、語法和語義答案：

（1）字母表：是一個非空有窮集合。

（2）串：符號的有窮序列。字：字母表中的元素。句子：如果Zx,x

+eV*T■是文法G的一個句子。（3）語言：它是由句子組成

的集合，是由一組記號所構(gòu)成的集合。程序設(shè)計的語言就是所有該語

言的程序的全體。語言可以看成在一個基本符號集上定義的，按一定規(guī)則構(gòu)成

的一切基本符號串組成的集合。

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

范文范例參考

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

范文范例參考

附力口題

問題1:

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

S7AI1B

A-*1S|1

DSIO

答案：

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

問題2:

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

G[A]:AfOBIIC

Bf1I1AI0BB

C—0I0AI1CC

答案：

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

問題3:

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

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

答案一：

G[E]E->E+T|T

IfF|F

Ff(E)|a

答案二：

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

問題4:

范文范例參考

已知文法G[S]:S—dAB

A-*aA|aB-￡|bB

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

答案：

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

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

G[S]:S^dAA^alaBB^aB|a|b|bCC—bC|b也可為（觀察得

來）:G[S]:SfdAA-alaAlaBB-bB|￡

問題5:

已知文法G:

E-*E+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)

答案：

(l)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+(F4T)

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

范文范例參考

T1

I

F

I

(1)

i

(2)

⑶

問題6:

已知文法G[E]:

E->ET+|T

T->TF*|F

F—『Ia試證：FT'*是文法的句型，指出該句型的短語'簡單短語和句

柄.

答案：

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

于E的短語有相對于T的短語有

FF-*,F相對于F的短語有「；F"簡單

短語有F;F"句柄為F.

問題7:

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

SfSaSSbSScSd

答案：

范文范例參考

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

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

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

S—*SaSA

A-*AbAC

C—CcCd

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

S—?SsAA

A一AbCC

CfCcFF

Ffd

該文法為非二義的。

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

n

(1)48diri'出20}

(2)由詼9/〃，山2勿

(3){a%血2A}

(4){aBbncpdQmin=p+q}

(5){uawbufw￡{a,b}*八I〃I=IvI}

答案：

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

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

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

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

SfAB

月一*￡aAbb6一￡cB

(2)同樣，要產(chǎn)生形如dZA產(chǎn)的串，可以分別產(chǎn)生形如"和形加次產(chǎn)的串。對于該語

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

SfAB

A->￡aA

范文范例參考

BfebBcc

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

S-aSb

（4）以下G[S]是一種解法：

SfaSdAD

AfbAdB

DfaDcB

BfbBce

注：a不多于d時，b不少于c；反之?a不少于d時，b不多于c。前一種情

形通過對應(yīng)A，后一種情形對應(yīng)D。

（5）以下G[S]是一種解法：

SfAb力—BABaBfab

問題9:

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

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

S-SVTT

T—T八FF

FffFpq

試指出句型fFVrqAp的直接短語（全部）以及句柄。

答案：

直接短語：p，q，-F句柄：-F

問題10:

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

答案：

x0=(aaa)0=￡|x°|=0

xx=aaaaaa|xxI=6

x5=aaaaaaaaaaaaaaaI

x5|=15

X=A'UA2UU???.AnUaa,aaa,aaaa,aaaaa---}

范文范例參考

A*=A0UA1UA2U….UAn□??,={e,a,aa,aaa,aaaa,aaaaa---j

問題11：

令￡=伯,b'c},又令x=abc,y=b,z=aab,寫出如下符號串及它們的長度：xy，xyz?

(xy)3

答案：

xy=abcbIxyI=4

xyz=abcbaabIxyz1=7

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

問題12：

已知文法G[Z]：Z：：=UO|VI、U：：=Z1|1、V：：=ZO|0,請寫出全部由此文法描述

的只含有四個符號的句子。

答案：

Z=>l)0=>Z10=>l)010=>1010

Z=>l)0=>Z10=>V110=>0110

Z=>Vl=>Z00=>l)000=>1000

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

問題13:

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

答案：

A：：=aAI￡描述的語言：匕)!1>=0}

B：：=bBcIbe描述的語言：{,9(川11>=1}

L(G[S])={a"b"c"|n>=0,m>=l}

問題14:

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

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

范文范例參考

答案：

開始符號：E

V尸{+,,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::=N0|Nl|N2|N3|N4|N5|N6|N7|N8|N9|

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

范文范例參考

第4章詞法分析

第1題

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

(1)1(011)*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，因為D含有Y（NFA

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

?01

X?A

AAB

BCB

CAD

DCB

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

0

范文范例參考

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

用子集法將NFA確定化

￡01

XX

To=XA

AABFL

T.=ABFLYCG

YY

CGCGJ

T2=Y

Ta=CGJDHK

DHDH

KABFKL

L=DHEl

EIABEFIL

Ts=ARFKLYCG

Tc=ABEFILEJYCG

EJYABEFGJLY

T?=ABEFGJLYEHYCGK

EHYABEFHLY

CGKABCFGJKL

Ts=ABEFHLYEYCGI

EYABEFLY

CGICGJI

Tg=ABCFGJKLDHYCGK

DHYDHY

Tio=ABEFLYEYCG

范文范例參考

Tu=CGJIDHJK

DHJDHJ

T12=DHYEI

T13=DHJEIK

EIKABEFIKL

TM=ABEFIKLEJYCG

將To'Ti'Ti'Ta'T<'Tf>'Ts'T?'Ts'To'Tio、Tn、T12'Ti3'Tu重新命名,分別用0、1'

2、3、4、5、6、7、8、9、10、11、12、13、14表示。因為2、7、8、10、12中含有Y，

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

01

01

123

2

345

46

523

673

789

81011

9129

10103

11135

126

1314

1473

范文范例參考

￡ab

XX

To=XA

AABCD

Ti=ABCDBEBY

BEABCDE

BYABCDY

T2=ABCDEBEFBEY

BEFABCDEF

BEYABCDEY

BE