編譯原理其次版

本文格式為Word版，下載可任意編輯——編譯原理其次版

編譯原理其次版_張素琴_課后習題解答

第1章引論

第1題

解釋以下術(shù)語：（1）編譯程序（2）源程序（3）目標程序

（4）編譯程序的前端（5）后端（6）遍

答案：

（1）編譯程序：假使源語言為高級語言，目標語言為某臺計算機上的匯編語言或機器語

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

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

（3）目標程序：目標語言書寫的程序稱為目標程序。

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

目標機無關(guān)。尋常前端包括詞法分析、語法分析、語義分析和中間代碼生成這些階段，某些優(yōu)化工作也可在前端做，也包括與前端每個階段相關(guān)的出錯處理工作和符號表管理等工作。

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

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

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

第2題

一個典型的編譯程序?qū)こＳ赡男┎糠纸M成？各部分的主要功能是什么？并畫出編譯程序的總體結(jié)構(gòu)圖。

答案：

一個典型的編譯程序?qū)こ０?個組成部分，它們是詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序、目標代碼生成程序、表格管理程序和錯誤處理程序。其各部分的主要功能簡述如下。

詞法分析程序：輸人源程序，拼單詞、檢查單詞和分析單詞，輸出單詞的機內(nèi)表達形式。語法分析程序：檢查源程序中存在的形式語法錯誤，輸出錯誤處理信息。語義分析程序：進行語義檢查和分析語義信息，并把分析的結(jié)果保存到各類語義信息表中。

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

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

課后

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

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

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

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

中間結(jié)果都記錄在相應(yīng)的表格中?？梢哉f整個編譯過程就是造表、查表的工作過程。需要指出的是，這里的“表格管理程序〞并不意味著它就是一個獨立的表格管理模塊，而是指編譯程序具有的表格管理功能。

錯誤處理程序：處理和校正源程序中存在的詞法、語法和語義錯誤。當編譯程序發(fā)現(xiàn)源程序中的錯誤時，錯誤處理程序負責報告出錯的位置和錯誤性質(zhì)等信息，同時對發(fā)現(xiàn)的錯誤進行適當?shù)男Ｕㄐ迯?fù)），目的是使編譯程序能夠繼續(xù)向下進行分析和處理。

案網(wǎng)

w

ww

注意：假使問編譯程序有哪些主要構(gòu)成成分，只要回復(fù)六部分就可以。假使搞不明白，就回復(fù)八部分。

第3題

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

答案：

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

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

解釋程序是解釋、執(zhí)行高級語言源程序的程序。解釋方式一般分為兩種：一種方式是，源程序功能的實現(xiàn)完全由解釋程序承受和完成，即每讀出源程序的一條語句的第一個單詞，

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

能的實現(xiàn)，完成后返回到解釋程序的總控部分再讀人下一條語句繼續(xù)進行解釋、執(zhí)行，如此反復(fù)；另一種方式是，一邊翻譯一邊執(zhí)行，即每讀出源程序的一條語句，解釋程序就將其翻譯成一段機器指令并執(zhí)行之，然后再讀人下一條語句繼續(xù)進行解釋、執(zhí)行，如此反復(fù)。無論

課后

答

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

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

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

（3）自展：首先確定一個十分簡單的核心語言L0，用機器語言或匯編語言書寫出它的編譯,并用L0編寫L1的編譯程序T1，再把語程序T0，再把語言L0擴展到L1，此時L0L1

言L1擴展為L2，有L1L2,并用L1編寫L2的編譯程序T2，……，如此逐步擴展下去，類似滾雪球一樣，直到我們所要求的編譯程序。

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

課后

是哪種方式，其加工結(jié)果都是源程序的執(zhí)行結(jié)果。目前好多解釋程序采取上述兩種方式的綜合實現(xiàn)方案，即先把源程序翻譯成較簡單解釋執(zhí)行的某種中間代碼程序，然后集中解釋執(zhí)行中間代碼程序，最終得到運行結(jié)果。

廣義上講，編譯程序和解釋程序都屬于翻譯程序，但它們的翻譯方式不同，解釋程序是邊翻譯（解釋）邊執(zhí)行，不產(chǎn)生目標代碼，輸出源程序的運行結(jié)果。而編譯程序只負責把源程序翻譯成目標程序，輸出與源程序等價的目標程序，而目標程序的執(zhí)行任務(wù)由操作系統(tǒng)來完成，即只翻譯不執(zhí)行。

第4題

對以下錯誤信息，請指出可能是編譯的哪個階段（詞法分析、語法分析、語義分析、代碼生成）報告的。

（1）else沒有匹配的if（2）數(shù)組下標越界

（3）使用的函數(shù)沒有定義（4）在數(shù)中出現(xiàn)非數(shù)字字符

答案：

（1）語法分析（2）語義分析（3）語法分析（4）詞法分析

第5題

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

答案：

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

第６題

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

答案：

計算機執(zhí)行用高級語言編寫的程序主要途徑有兩種，即解釋與編譯。像Basic之類的語言，屬于解釋型的高級語言。它們的特點是計算機并不事先對高級語言進行全盤翻譯，將其變?yōu)闄C器代碼，而是每讀入一條高級語句，就用解釋器將其翻譯為一條機器代碼，予以執(zhí)行，然后再讀入下一條高級語句，翻譯為機器代碼，再執(zhí)行，如此反復(fù)。

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

像C，Pascal之類的語言，屬于編譯型的高級語言。它們的特點是計算機事先對高級語言進行全盤翻譯，將其全部變?yōu)闄C器代碼，再統(tǒng)一執(zhí)行，即先翻譯，后執(zhí)行。從速度上看，編譯型的高級語言比解釋型的高級語言更快。

課后

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

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

第1題

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

答案：

PL/0語言允許過程嵌套定義和遞歸調(diào)用，它的編譯程序在運行時采用了棧式動態(tài)存儲管理。（數(shù)組CODE存放的只讀目標程序，它在運行時不改變。）運行時的數(shù)據(jù)區(qū)S是由解釋程序定義的一維整型數(shù)組，解釋執(zhí)行時對數(shù)據(jù)空間S的管理遵循后進先出規(guī)則，當每個過程(包括主程序)被調(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;

課后

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

end(p);begin(main)callp;end(main).

答案：

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

案網(wǎng)

第3題

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

namekind

答案：

題2中當程序編譯到r的過程體時的名字表table的內(nèi)容為：namekindlevel/valxvariableyvariablepprocedure

000

adrdxdx+1

size

課

后

答

w

ww

level/valadrsize

.k

過程p的入口（待填）5

hd

aw

.

com

編譯原理其次版_張素琴_課后習題解答

avariableqproceduresprocedurecvariabledvariablerprocedureevariablefvariable

11122233

dx

過程q的入口4

dxdxdxdx+1

過程s的入口（待填）5

過程r的入口5

注意：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í)行終止釋放數(shù)據(jù)空間時，恢復(fù)調(diào)用該過程前運行棧的狀態(tài)。

RA：返回地址，記錄調(diào)用該過程時目標程序的斷點，即調(diào)用過程指令的下一條指令的地址，用以過程執(zhí)行終止后返回調(diào)用過程時的下一條指令繼續(xù)執(zhí)行。

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

第5題

PL/0編譯程序所產(chǎn)生的目標代碼是一種假想棧式計算機的匯編語言，請說明該匯編語言中以下指令各自的功能和所完成的操作。（１）INT0A（２）OPR00（３）CALLA答案：

PL/0編譯程序所產(chǎn)生的目標代碼中有3條十分重要的特別指令，這3條指令在code中的位置和功能以及所完成的操作說明如下：

課后

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

INT0A

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

在過程目標程序的出口處，釋放數(shù)據(jù)段（退棧），恢復(fù)調(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/0語言作如下功能擴展時的語法圖和EBNF的語法描述。(1)擴展條件語句的功能使其為：

if〈條件〉then〈語句〉[else〈語句〉](2)擴展repeat語句為：

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

答案：

對PL/0語言作如下功能擴展時的語法圖和EBNF的語法描述如下：

(1)擴展條件語句的語法圖為：

(2)擴展repeat語句的語法圖為：

課后

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

答

案網(wǎng)

w

ww

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

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

第3章文法和語言

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

D→0|1|2|3|4|5|6|7|8|9G[N]的語言是什么？

答案:

G[N]的語言是V+。V={0,1,2,3,4,5,6,7,8,9}N=ND=NDD=NDDDD...D=DD

0開頭的非負整數(shù)？

第３題

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

G[S]:

S-S+D|S-D|D

第4題

已知文法G[Z]：Z→aZb|ab

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

課后

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

答案：

nn

b|n=1}

第5題

寫一文法，使其語言是偶正整數(shù)的集合。要求：(1)允許0打頭；

(2)不允許0打頭。

答案：

(1)允許0E→NT|DT→NT|D

N→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：

表達式::=項｜表達式＋項項::=因子｜項*因子因子::=（表達式）｜i

試給出下述表達式的推導(dǎo)及語法樹。（５）i+(i+i)（６）i+i*i

課后

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

答案：

=表達式＋因子

=表達式＋（表達式）

=表達式＋（表達式＋項）=表達式＋（表達式＋因子）=表達式＋（表達式＋i）=表達式＋（項＋i）=表達式＋（因子＋i）=表達式＋（i＋i）=項＋（i＋i）=因子＋（i＋i）=i＋（i＋i）

(6)表達式

=表達式＋項

=表達式＋項*因子=表達式＋項*i=表達式＋因子*i=表達式＋i*i=項＋i*i=因子＋i*i=i＋i*i

課后

答

案網(wǎng)

w

ww

.

編譯原理其次版_張素琴_課后習題解答

第7題

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

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

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

答案：

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

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

〈表達式〉〈運算符〉a

〈表達式〉*a

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

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

〈表達式〉+a*a

a+a*a

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

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

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

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

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

〈表達式〉+a*a

a+a*a

課后

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

或者：

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

第9題

考慮下面上下文無關(guān)文法：S→SS*|SS+|a

(1)說明通過此文法如何生成串a(chǎn)a+a*

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

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

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

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

hd

aw.

S

課后

答

案w

ww

.com

第8題

文法G[S]為：S→Ac|aBA→abB→bc

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

答案：

對于串a(chǎn)bc

(1)S=Ac=abc(2)S=aB=abc

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

編譯原理其次版_張素琴_課后習題解答

此句型對應(yīng)語法樹如右，故為此文法一個句型。或者：由于存在推導(dǎo)序列:E=E+T=E+T*F，所以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)

課后

答

案網(wǎng)

w

ww

.k

第10題

文法S→S(S)S|ε

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

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

答案：

（１）嵌套的括號

（２）是二義的，由于對于（）（）可以構(gòu)造兩棵不同的語法樹。

第11題

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

證明E+T*F

是它的一個句型，指出這個句型的所有短語、直接短語和句柄。

答案：

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

答案：

(1)串a(chǎn)bbaa最左推導(dǎo):

最右推導(dǎo)：

S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa

(2)產(chǎn)生式有：S→ABS|Aa|εA→aB→SBB|b

可能元素有：ε

(3)該句子的短語有：

aA是相對Sb是相對Bεbb是相對B的短語aa是相對S的短語aεbbaa是相對S的短語

直接短語有：aεb

句柄是：a

答案：（１）S→AAA→aAb|ε（２）

S→1S0|AA→0A1|ε（３）

S→0S0|1S1|ε

課后

第14題

給出生成下述語言的上下文無關(guān)文法：（1）{anbnambm|n，m=0}（2）{1n0m1m0n|n，m=0}

（3）{WaWr|W屬于{0|a}*，Wr表示W(wǎng)的逆}

答

案網(wǎng)

w

ww

.k

hd

aw.

com

編譯原理其次版_張素琴_課后習題解答

第16題

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

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

習題７和習題11中的文法等價嗎？

答案：

等價。

第18題

解釋以下術(shù)語和概念：（１）字母表

（２）串、字和句子

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

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

（２）串：符號的有窮序列。

字