版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第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ǔ)
言'則此翻譯程序稱為編譯程序C
(2)源程序:源語(yǔ)言編寫(xiě)的程序稱為源程序。
(3)目標(biāo)程序:目標(biāo)語(yǔ)言書(shū)寫(xiě)拘程序稱為目標(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è)典型的編譯程序通常由哪些部分組成?各部分的主要功能是什么?并畫(huà)出編譯程序
的思體結(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é)建立、填寫(xiě)和查找等一系列表格工作。表格的作用是圮錄源程序的
各類信息和編譯各階段的進(jìn)展情況,編譯的每個(gè)階段所需信息多數(shù)都從表格中讀取,產(chǎn)生的
中間結(jié)果都記錄在相應(yīng)的表格中。可以說(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ù)男Uㄐ迯?fù)),目的是使編譯程序能夠繼續(xù)向下進(jìn)行分析和欠理。
注意:如果問(wèn)編譯程序有哪些主要構(gòu)成成分,只要回答六部分就可以。如果搞不清楚,
就回答八部分。
第3題
何謂翻譯程序、編譯程序和解釋程序?它們?nèi)咧g有何種關(guān)系?
答案:
翻譯程序是指將用某種語(yǔ)言編寫(xiě)的程序轉(zhuǎn)換成另一種語(yǔ)言形式的程序的程序,如編譯程
序和匯編程序等。
編譯程序是把用高級(jí)語(yǔ)言編寫(xiě)的源程序轉(zhuǎn)換(加工)成與之等價(jià)的另一種用低級(jí)語(yǔ)言編
寫(xiě)的目標(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題
編譯程序大致有哪幾種開(kāi)發(fā)技術(shù)?
答案:
(1)自編譯:用某一高級(jí)語(yǔ)言書(shū)寫(xiě)其本身的編譯程序。
(2)交叉編譯:A機(jī)器上的編譯程序能產(chǎn)生B機(jī)器上的目標(biāo)代碼。
(3)自展:首先確定一個(gè)非常簡(jiǎn)單的核心語(yǔ)言L0,用機(jī)器語(yǔ)言或匯編語(yǔ)言書(shū)寫(xiě)出它的編譯
程序TO,再把語(yǔ)言L0擴(kuò)充到L1,此時(shí)LOuLl,并用L0編寫(xiě)L1的編譯程序T1,
再把語(yǔ)
言L1擴(kuò)充為L(zhǎng)2,有LIcL2,并用L1編寫(xiě)L2的編譯程序T2,……,如此逐步擴(kuò)展下
去,
好似滾雪球一樣,直到我們所要求的編譯程序。
范文范例參考
(4)移植:將A機(jī)器上的某高級(jí)語(yǔ)言的編譯程序搬到B機(jī)器上運(yùn)行。
第6題
計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序有哪些途徑?它們之間的主要區(qū)別是什么?
答案:計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要途徑有兩種,即解釋與編譯。
像Basic之類的語(yǔ)言,屬于解釋型的高級(jí)語(yǔ)言。它們的特點(diǎn)是計(jì)算機(jī)并不事先對(duì)高級(jí)語(yǔ)
言進(jìn)行全盤(pán)翻譯,將其變?yōu)闄C(jī)器代碼,而是每讀入一條高級(jí)語(yǔ)句,就用解釋器將其翻譯為一
條機(jī)器代碼,予以執(zhí)行,然后再讀入下一條高級(jí)語(yǔ)句,翻譯為機(jī)器代碼,再執(zhí)行,如此反復(fù)。
總而言之,是邊翻譯邊執(zhí)行。
像C,Pascal之類的語(yǔ)言,屬于編譯型的高級(jí)語(yǔ)言。它們的特點(diǎn)是計(jì)算機(jī)事先對(duì)高級(jí)語(yǔ)
言進(jìn)行全盤(pán)翻譯,將其全部變?yōu)闄C(jī)詈代碼,再統(tǒng)一執(zhí)行,即先翻譯,后執(zhí)行。從速度上看,
編譯型的高級(jí)語(yǔ)言比解釋型的高級(jí)語(yǔ)言更快。
范文范例參考
第2章PL/O編譯程序的實(shí)現(xiàn)
第1題
PL/O語(yǔ)言允許過(guò)程嵌套定義和遞歸調(diào)用,試問(wèn)它的編譯程序如何解決運(yùn)行時(shí)的存儲(chǔ)管理。
答案:
PL/O語(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)題,試寫(xiě)出下列程序執(zhí)行到賦值語(yǔ)句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í)行到賦值語(yǔ)句b:=10時(shí)運(yùn)行棧的布局示意圖為:
范文范例參考
第3題
寫(xiě)出題2中當(dāng)程序編譯到r的過(guò)程體時(shí)的名字表table的
內(nèi)容。
namekindlevel/valadrsize
答案:
趣2中當(dāng)程序編譯到r的過(guò)程體時(shí)的名字表table的內(nèi)容為:
namekindlevel/valadrsize
Xvariable0dx
yvariable0dx+1
pprocedure0過(guò)程p的入口(待填)5
avariable1dx
qprocedure1過(guò)程q的入口4
sprocedure1過(guò)程s的入口(待填)5
cvariable2dx
dvariable2dx
范文范例參考
rprocedure2過(guò)程r的入口5
evariable3dx
fvariable3dx+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/O編譯程序所產(chǎn)生的目標(biāo)代碼是一種假想棧式計(jì)算機(jī)的匯編語(yǔ)言,請(qǐng)說(shuō)明該匯編語(yǔ)
言中下列指令各自的功能和所完成的操作。
(1)INT0A
(2)OPR00
(3)CALLA
答案:
PL/O編譯程序所產(chǎn)生的目標(biāo)代碼中有3條非常重要的特殊指令,這3條指令在code
中的位置和功能以及所完成的操作說(shuō)明如下:
INT0A
在過(guò)程目標(biāo)程序的人口火,開(kāi)辟A個(gè)單元的數(shù)據(jù)段。A為局部變量的個(gè)數(shù)+3。
OPR00
范文范例參考
在過(guò)程目標(biāo)程序的出口欠,釋放數(shù)據(jù)段(退棧),恢復(fù)調(diào)用該過(guò)程前正在運(yùn)行的過(guò)程的數(shù)
據(jù)段基址寄存器B和棧頂寄存器T的值,并將返回地址送到指令地址寄存器P中,以使
調(diào)用前的程序從慚點(diǎn)開(kāi)始繼續(xù)執(zhí)行v
CALLA
調(diào)用過(guò)程,完成填寫(xiě)好態(tài)鏈、動(dòng)態(tài)鏈、返回地址,給出被調(diào)用過(guò)程的基地址值,送入基址
寄存器B中,目標(biāo)程序的入口地址A的值送指令地址寄存器P中,使指令從A開(kāi)始執(zhí)行。
第6題
給出對(duì)PL/O語(yǔ)言作如下功能擴(kuò)充時(shí)的語(yǔ)法圖和EBNF的語(yǔ)法描述。
(1)擴(kuò)充條件語(yǔ)句的功能使其為:
if<條件〉then〈語(yǔ)句〉[else〈語(yǔ)句〉]
(2)擴(kuò)充repeat語(yǔ)句為:repeat〈語(yǔ)句〉{;〈語(yǔ)句〉}until〈條件〉
答案:
對(duì)PL/O語(yǔ)言作如下功能擴(kuò)充時(shí)的語(yǔ)法圖和EBNF的語(yǔ)法描述如下:
(1)擴(kuò)充條件語(yǔ)句的語(yǔ)法圖為:
EBNF的語(yǔ)法描述為:〈條件語(yǔ)句〉::=if(條件〉then〈語(yǔ)句》[else〈語(yǔ)句〉]
EBNF的語(yǔ)法描述為:〈重復(fù)語(yǔ)句〉::=repeat〈語(yǔ)句〉{;〈語(yǔ)句〉}until〈條件〉
范文范例參考
第3章文法和語(yǔ)言
第1題
文法G=({A,B,S},{a,b,c},P,S)其中P為:
S-?Ac|aB
A-*ab
B->bc寫(xiě)出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]的語(yǔ)言是什么?
答案:
G[N]的語(yǔ)言是V+oy={0,1,2,3,4,5,6,7,8,9)
N=>ND=>NDD....=>NDDDD...D=>D..........D
或者:允許0開(kāi)頭的非負(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|1|2|3|4|5|6|7|8|9
第4題
已知文法G[Z]:
Z->aZb|ab
完美Word格式整理版
范文范例參考
寫(xiě)出L(G[Z])的全部元素。
答案:
Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb
nn
L(G[Z])={ab|n>=l}
第5題寫(xiě)一文法,使其語(yǔ)言是偶正整數(shù)的集合。
要求:
(1)允許0打頭;(2)不允
許0打頭。
答案:(1)允許0開(kāi)頭的偶正整數(shù)
集合的文法
E-*NT|D
T-NTID
N->D|1|3|5|7|9
D->0|2|4|6|8
(2)不允許0開(kāi)頭的偶正整數(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á)式)::=<項(xiàng))|<表達(dá)式>+<項(xiàng))
<項(xiàng)>::=<因子)|<項(xiàng)>*<因子)
〈因子)::=(<表達(dá)式))Ii
試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹(shù)。
(5)i+(i+i)
(6)i+i*i
范文范例參考
答案:
(5)〈表達(dá)式)
=><表達(dá)式>+〈項(xiàng)〉
=><表達(dá)式〉+〈因子〉
=><表達(dá)式>+(<表達(dá)式))
=><表達(dá)式>+(〈表達(dá)式>+c頁(yè)))
=><表達(dá)式>+(<表達(dá)式〉+〈因子〉)
=><表達(dá)式>+(<表達(dá)式>+i)=><表達(dá)式>+(<項(xiàng))
+i)
=X表達(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+i*i
第7題證明下述文法G[〈表達(dá)式〉]是
二義的。
〈表達(dá)式〉::=a|(〈表達(dá)式〉)1〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉
〈運(yùn)算符〉::=+|-|*|/
答案:可為句子a+a*a構(gòu)造兩個(gè)不同的最右推導(dǎo):最右
推導(dǎo)1〈表達(dá)式〉=〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉
n〈表達(dá)式〉〈運(yùn)算符》a
n〈表達(dá)式〉*a
=>〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉*a
=?〈表達(dá)式〉〈運(yùn)算符〉a*a
n〈表達(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
A-*ab
B->bc
該文法是否為二義的?為什么?
范文范例參考
答案:
對(duì)于串a(chǎn)be
(1)S=>Ac=>abc(2)S=>aB=>abc即存在兩不同的最右推導(dǎo)。所以,該文法是二義的。
或者:
對(duì)輸入字符串a(chǎn)bc,能構(gòu)造兩棵不同的語(yǔ)法樹(shù),所以它是二義的。
b
第9題
考慮下面上下文無(wú)關(guān)文法:
S->SS*|SS+|a
(1)表明通過(guò)此文法如何生成串a(chǎn)a+a*,并為該串構(gòu)造
語(yǔ)法樹(shù)。
(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|e
(1)生成的語(yǔ)言是什么?
(2)該文法是二義的嗎?說(shuō)明理由。
完美Word格式整理版
范文范例參考
答案:
(1)嵌套的括號(hào)
(2)是二義的,因?yàn)閷?duì)于()()可以構(gòu)造兩棵不同的語(yǔ)法樹(shù)。
第11題令文法
G[E]為:
E-TIE+TIE-TT->F|T*F|T/F
F->(E)|i
證明E+T*F是它的一個(gè)句型,指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。
答案:
此句型對(duì)應(yīng)語(yǔ)法樹(shù)如右,故為此文法一個(gè)句型。
或者:因?yàn)榇嬖谕茖?dǎo)序列:E=>E+T=>E+T*E?所以
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)樹(shù)如下:
(1)給出串a(chǎn)bbaa最左推導(dǎo)、最右推導(dǎo)。
(2)該文法的產(chǎn)生式集合P可能有哪些元
索?
(3)找出該句子的所有短語(yǔ)、直接短語(yǔ)、句
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)該句子的短語(yǔ)有:a是
相對(duì)A的短語(yǔ)E是
相對(duì)S的短語(yǔ)b是相
對(duì)B的短語(yǔ)£bb是
相對(duì)B的短語(yǔ)aa是
相對(duì)S的短語(yǔ)
aEbbaa是相對(duì)S的
短語(yǔ)
直接短語(yǔ)有:a£b
句柄是:a
第14題
給出生成下述語(yǔ)言的上下文無(wú)關(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題給出生成下述語(yǔ)言的三型文
法:
(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中的文法等價(jià)嗎?
答案:
等價(jià)。
第18題
解釋下列術(shù)語(yǔ)和概念:(1)
字母表
(2)串、字和句子
(3)語(yǔ)言、語(yǔ)法和語(yǔ)義答案:
(1)字母表:是一個(gè)非空有窮集合。
(2)串:符號(hào)的有窮序列。字:字母表中的元素。句子:如果Zx,x
+eV*T■是文法G的一個(gè)句子。(3)語(yǔ)言:它是由句子組成
的集合,是由一組記號(hào)所構(gòu)成的集合。程序設(shè)計(jì)的語(yǔ)言就是所有該語(yǔ)
言的程序的全體。語(yǔ)言可以看成在一個(gè)基本符號(hào)集上定義的,按一定規(guī)則構(gòu)成
的一切基本符號(hào)串組成的集合。
語(yǔ)法:表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律。程序的結(jié)構(gòu)或形式。
范文范例參考
語(yǔ)義:表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含義。語(yǔ)言所代表的含義。
范文范例參考
附力口題
問(wèn)題1:
給出下述文法所對(duì)應(yīng)的正規(guī)式:
S7AI1B
A-*1S|1
DSIO
答案:
R=(01|10)(01I10)*
問(wèn)題2:
已知文法G[A],寫(xiě)出它定義的語(yǔ)言描述
G[A]:AfOBIIC
Bf1I1AI0BB
C—0I0AI1CC
答案:
G[A]定義的語(yǔ)言由0、1符號(hào)串組成,串中0和1的個(gè)數(shù)相同.
問(wèn)題3:
給出語(yǔ)言描述,構(gòu)造文法.
構(gòu)造一文法,其定義的語(yǔ)言是由算符+,*,(,)和運(yùn)算對(duì)象a構(gòu)成的算術(shù)表達(dá)式的集合.
答案一:
G[E]E->E+T|T
IfF|F
Ff(E)|a
答案二:
G[E]E-E+EIE*E|(E)|a
問(wèn)題4:
范文范例參考
已知文法G[S]:S—dAB
A-*aA|aB-£|bB
相應(yīng)的正規(guī)式是什么?G[S]能否改寫(xiě)成為等價(jià)的正規(guī)文法?
答案:
正規(guī)式是daa*b*;
相應(yīng)的正規(guī)文法為(由自動(dòng)機(jī)化簡(jiǎn)來(lái)):
G[S]:S^dAA^alaBB^aB|a|b|bCC—bC|b也可為(觀察得
來(lái)):G[S]:SfdAA-alaAlaBB-bB|£
問(wèn)題5:
已知文法G:
E-*E+T|E-T|T
T-T*F|T/F|F
F->(E)|i
試給出下述表達(dá)式的推導(dǎo)及語(yǔ)法樹(shù)
⑴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)
⑶
問(wèn)題6:
已知文法G[E]:
E->ET+|T
T->TF*|F
F—『Ia試證:FT'*是文法的句型,指出該句型的短語(yǔ)'簡(jiǎn)單短語(yǔ)和句
柄.
答案:
該句型對(duì)應(yīng)的語(yǔ)法樹(shù)如下:該句型相對(duì)
于E的短語(yǔ)有相對(duì)于T的短語(yǔ)有
FF-*,F相對(duì)于F的短語(yǔ)有「;F"簡(jiǎn)單
短語(yǔ)有F;F"句柄為F.
問(wèn)題7:
適當(dāng)變換文法,找到下列文法所定義語(yǔ)言的一個(gè)無(wú)二義的文法:
SfSaSSbSScSd
答案:
范文范例參考
該文法的形式很典型,可以先采用優(yōu)先級(jí)聯(lián)規(guī)則變換文法,然后再規(guī)定結(jié)合性對(duì)文法做
進(jìn)一步變換,即可消除二義性。
設(shè)a、力和c的優(yōu)先級(jí)別依次增高,根據(jù)優(yōu)先級(jí)聯(lián)規(guī)則將文法變換為:
S—*SaSA
A-*AbAC
C—CcCd
規(guī)定結(jié)合性為左結(jié)合,進(jìn)一步將文法變換為:
S—?SsAA
A一AbCC
CfCcFF
Ffd
該文法為非二義的。
問(wèn)題8:構(gòu)造產(chǎn)生如下語(yǔ)言的上下文無(wú)關(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ù)上下文無(wú)關(guān)文法的特點(diǎn),要產(chǎn)生形如4片c”的串,可以分別產(chǎn)生形如產(chǎn)和
形如的串。設(shè)計(jì)好的文法是否就是該語(yǔ)言的文法?嚴(yán)格地說(shuō),應(yīng)該給出證明。但若不是
特別指明,通??梢院雎赃@一點(diǎn)。
對(duì)于該語(yǔ)言,存在一個(gè)由以下產(chǎn)生式定義的上下文無(wú)關(guān)文法G[S]:
SfAB
月一*£aAbb6一£cB
(2)同樣,要產(chǎn)生形如dZA產(chǎn)的串,可以分別產(chǎn)生形如"和形加次產(chǎn)的串。對(duì)于該語(yǔ)
言,存在一個(gè)由以下產(chǎn)生式定義的上下文無(wú)關(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時(shí),b不少于c;反之?a不少于d時(shí),b不多于c。前一種情
形通過(guò)對(duì)應(yīng)A,后一種情形對(duì)應(yīng)D。
(5)以下G[S]是一種解法:
SfAb力—BABaBfab
問(wèn)題9:
下面的文法G(S)描述由命題變量p、q,聯(lián)結(jié)詞A(合取)、V(析?。?、「(否定)
構(gòu)成的命題公式集合:
S-SVTT
T—T八FF
FffFpq
試指出句型fFVrqAp的直接短語(yǔ)(全部)以及句柄。
答案:
直接短語(yǔ):p,q,-F句柄:-F
問(wèn)題10:
設(shè)字母表A={a},符號(hào)串x=aaa■寫(xiě)出下列符號(hào)串及其長(zhǎng)度: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
問(wèn)題11:
令£=伯,b'c},又令x=abc,y=b,z=aab,寫(xiě)出如下符號(hào)串及它們的長(zhǎng)度:xy,xyz?
(xy)3
答案:
xy=abcbIxyI=4
xyz=abcbaabIxyz1=7
(xy)3=(abcb)3=abcbabcbabcbI(xy)3|=12
問(wèn)題12:
已知文法G[Z]:Z::=UO|VI、U::=Z1|1、V::=ZO|0,請(qǐng)寫(xiě)出全部由此文法描述
的只含有四個(gè)符號(hào)的句子。
答案:
Z=>l)0=>Z10=>l)010=>1010
Z=>l)0=>Z10=>V110=>0110
Z=>Vl=>Z00=>l)000=>1000
Z=>Vl=>Z00=>V100=>0100
問(wèn)題13:
已知文法G[S]:S::-ABA::-aAIeB::-bBcIbe,寫(xiě)出該文法描述的語(yǔ)言。
答案:
A::=aAI£描述的語(yǔ)言:匕)!1>=0}
B::=bBcIbe描述的語(yǔ)言:{,9(川11>=1}
L(G[S])={a"b"c"|n>=0,m>=l}
問(wèn)題14:
已知文法E::=T|E+T|E-T、T::=FIT*FIT/F、F::=(E)|i,寫(xiě)出該文法的開(kāi)始
符號(hào)、終結(jié)符號(hào)集合W、非終結(jié)符號(hào)集合VN。
范文范例參考
答案:
開(kāi)始符號(hào):E
V尸{+,,i)
VN={E,F,T)
問(wèn)題15:
設(shè)有文法G[S]:S::=S*S|S+S|(S)|a,該文法是二義性文法嗎?
答案:
根據(jù)所給文法推導(dǎo)出句子a+a*a,畫(huà)出了兩棵不同的語(yǔ)法樹(shù),所以該文法是二義性文法。
問(wèn)題16:
寫(xiě)一文法,使其語(yǔ)言是奇正整數(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,因?yàn)镈含有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表示。因?yàn)?、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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度智能農(nóng)業(yè)農(nóng)藥化肥供應(yīng)及服務(wù)合同3篇
- 2025年度年度城市經(jīng)濟(jì)適用房購(gòu)置合同3篇
- 2025年度股東借款及股權(quán)激勵(lì)計(jì)劃合同3篇
- 2025年農(nóng)村個(gè)人承包土地經(jīng)營(yíng)權(quán)與農(nóng)村信息化建設(shè)合同3篇
- 二零二五年度農(nóng)業(yè)機(jī)械租賃與農(nóng)業(yè)人才培養(yǎng)合作合同3篇
- 二零二五年度醫(yī)療耗材研發(fā)與創(chuàng)新合作合同3篇
- 二零二五年度合伙經(jīng)營(yíng)中式快餐店合同書(shū)2篇
- 個(gè)人承包城市照明設(shè)施維護(hù)2025年度合同3篇
- 2025年度綠色生態(tài)豬肉直供基地合作協(xié)議合同3篇
- 公墓墓位買(mǎi)賣(mài)及墓園墓碑售后服務(wù)保障協(xié)議3篇
- 便利店轉(zhuǎn)讓簡(jiǎn)單合同范本
- 腦卒中后吞咽障礙患者進(jìn)食護(hù)理試題及答案
- 中草藥產(chǎn)業(yè)園規(guī)劃方案
- 護(hù)理文書(shū)書(shū)寫(xiě)規(guī)范
- MOOC 計(jì)量經(jīng)濟(jì)學(xué)-西南財(cái)經(jīng)大學(xué) 中國(guó)大學(xué)慕課答案
- 無(wú)人機(jī)測(cè)試與評(píng)估標(biāo)準(zhǔn)
- 2024版國(guó)開(kāi)電大法學(xué)本科《國(guó)際經(jīng)濟(jì)法》歷年期末考試總題庫(kù)
- 2023-年2月山東公務(wù)員錄用考試《申論B》考試真題
- 中國(guó)人壽保險(xiǎn)培訓(xùn)
- 2024年國(guó)家電投五凌電力限公司招聘歷年高頻考題難、易錯(cuò)點(diǎn)模擬試題(共500題)附帶答案詳解
- 陪診服務(wù)培訓(xùn)課件模板
評(píng)論
0/150
提交評(píng)論