編譯原理習(xí)題和答案市公開(kāi)課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

第一章緒論第二章詞法分析第三章語(yǔ)法分析第1頁(yè)

第一章緒論

1.1完成以下選擇題：

(1)下面敘述中正確是

。

A．編譯程序是將高級(jí)語(yǔ)言程序翻譯成等價(jià)機(jī)器語(yǔ)言程序程序

B．機(jī)器語(yǔ)言因其使用過(guò)于困難，所以現(xiàn)在計(jì)算機(jī)根本不使用機(jī)器語(yǔ)言

C．匯編語(yǔ)言是計(jì)算機(jī)唯一能夠直接識(shí)別并接收語(yǔ)言

D．高級(jí)語(yǔ)言靠近人們自然語(yǔ)言，但其依賴詳細(xì)機(jī)器特征是無(wú)法改變第2頁(yè)

(2)將編譯過(guò)程分成若干“遍”是為了

。

A．提升程序執(zhí)行效率

B．使程序結(jié)構(gòu)愈加清楚

C．利用有限機(jī)器內(nèi)存并提升機(jī)器執(zhí)行效率

D．利用有限機(jī)器內(nèi)存但降低了機(jī)器執(zhí)行效率

(3)結(jié)構(gòu)編譯程序應(yīng)掌握

。

A．源程序 B．目口號(hào)言

C．編譯方法 D．A～C項(xiàng)第3頁(yè)

(4)編譯程序絕大多數(shù)時(shí)間花在

上。

A．犯錯(cuò)處理 B．詞法分析

B．目標(biāo)代碼生成 D．表格管理

(5)編譯程序是對(duì)

。

A．匯編程序翻譯B．高級(jí)語(yǔ)言程序解釋執(zhí)行

C．機(jī)器語(yǔ)言執(zhí)行D．高級(jí)語(yǔ)言翻譯第4頁(yè)

【解答】

(1)編譯程序能夠?qū)⒂酶呒?jí)語(yǔ)言編寫源程序轉(zhuǎn)換成與之在邏輯上等價(jià)目標(biāo)程序，而目標(biāo)程序能夠是匯編語(yǔ)言程序或機(jī)器語(yǔ)言程序。故選A。

(2)分多遍完成編譯過(guò)程可使整個(gè)編譯程序邏輯結(jié)構(gòu)愈加清楚。故選B。

(3)結(jié)構(gòu)編譯程序應(yīng)掌握源程序、目口號(hào)言和編譯方法這三方面內(nèi)容。故選D。第5頁(yè)

(4)編譯各階段工作都包括到結(jié)構(gòu)、查找或更新相關(guān)表格，即編譯過(guò)程絕大部分時(shí)間都用在造表、查表和更新表格事務(wù)上。故選D。

(5)由(1)可知，編譯程序?qū)嶋H上實(shí)現(xiàn)了對(duì)高級(jí)語(yǔ)言程序翻譯。故選D。第6頁(yè)

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

【解答】計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫程序主要有兩種路徑：解釋和編譯。

在解釋方式下，翻譯程序事先并不采取將高級(jí)語(yǔ)言程序全部翻譯成機(jī)器代碼程序，然后執(zhí)行這個(gè)機(jī)器代碼程序方法，而是每讀入一條源程序語(yǔ)句，就將其解釋(翻譯)成對(duì)應(yīng)其功效機(jī)器代碼語(yǔ)句串并執(zhí)行，然后再讀入下一條源程序語(yǔ)句并解釋執(zhí)行，而所翻譯機(jī)器代碼語(yǔ)句串在該語(yǔ)句執(zhí)行后并不保留。這種方法是按源程序中語(yǔ)句動(dòng)態(tài)執(zhí)行次序逐句解釋(翻譯)執(zhí)行，假如一語(yǔ)句處于一循環(huán)體中，則每次循環(huán)執(zhí)行到該語(yǔ)句時(shí)，都要將其翻譯成機(jī)器代碼后再執(zhí)行。第7頁(yè)

在編譯方式下，高級(jí)語(yǔ)言程序執(zhí)行是分兩步進(jìn)行：第一步首先將高級(jí)語(yǔ)言程序全部翻譯成機(jī)器代碼程序，第二步才是執(zhí)行這個(gè)機(jī)器代碼程序。所以，編譯對(duì)源程序處理是先翻譯，后執(zhí)行。

從執(zhí)行速度上看，編譯型高級(jí)語(yǔ)言比解釋型高級(jí)語(yǔ)言要快，但解釋方式下人機(jī)界面比編譯型好，便于程序調(diào)試。

這兩種路徑主要區(qū)分在于：解釋方式下不生成目標(biāo)代碼程序，而編譯方式下生成目標(biāo)代碼程序。第8頁(yè)

1.3請(qǐng)畫出編譯程序總框圖。假如你是一個(gè)編譯程序總設(shè)計(jì)師，設(shè)計(jì)編譯程序時(shí)應(yīng)該考慮哪些問(wèn)題？

【解答】編譯程序總框圖如圖1-1所表示。

作為一個(gè)編譯程序總設(shè)計(jì)師，首先要深刻了解被編譯源語(yǔ)言其語(yǔ)法及語(yǔ)義；其次，要充分掌握目標(biāo)指令功效及特點(diǎn)，假如目口號(hào)言是機(jī)器指令，還要搞清楚機(jī)器硬件結(jié)構(gòu)以及操作系統(tǒng)功效；第三，對(duì)編譯方法及使用軟件工具也必須準(zhǔn)確化。總之，總設(shè)計(jì)師在設(shè)計(jì)編譯程序時(shí)必須估量系統(tǒng)功效要求、硬件設(shè)備及軟件工具等諸原因?qū)幾g程序結(jié)構(gòu)影響。第9頁(yè)圖1-1編譯程序總框圖第10頁(yè)第二章詞法分析

2.1完成以下選擇題：

(1)詞法分析所依據(jù)是

。

A．語(yǔ)義規(guī)則 B．構(gòu)詞規(guī)則

C．語(yǔ)法規(guī)則 D．等價(jià)變換規(guī)則

(2)詞法分析器輸入是

。

A．單詞符號(hào)串 B．源程序

C．語(yǔ)法單位 D．目標(biāo)程序第11頁(yè)

(3)詞法分析器輸出是

。

A．單詞種別編碼

B．單詞種別編碼和本身值

C．單詞在符號(hào)表中位置

D．單詞本身值

(4)狀態(tài)轉(zhuǎn)換圖(見(jiàn)圖2-1)接收字集為_(kāi)______。

A．以0開(kāi)頭二進(jìn)制數(shù)組成集合

B．以0結(jié)尾二進(jìn)制數(shù)組成集合

C．含奇數(shù)個(gè)0二進(jìn)制數(shù)組成集合

D．含偶數(shù)個(gè)0二進(jìn)制數(shù)組成集合第12頁(yè)圖2-1習(xí)題2.1DFAM第13頁(yè)

(5)對(duì)于任一給定NFAM，

一個(gè)DFAM′，使L(M)=L(M′)。

A．一定不存在 B．一定存在

C．可能存在 D．可能不存在

(6)?DFA適合用于

。

A．定理證實(shí) B．語(yǔ)法分析

C．詞法分析 D．語(yǔ)義加工第14頁(yè)

(7)下面用正規(guī)表示式描述詞法敘述中，不正確是

。

A．詞法規(guī)則簡(jiǎn)單，采取正規(guī)表示式已足以描述

B．正規(guī)表示式表示比上下文無(wú)關(guān)文法愈加簡(jiǎn)練、直觀和易于了解

C．正規(guī)表示式描述能力強(qiáng)于上下文無(wú)關(guān)文法

D．有限自動(dòng)機(jī)結(jié)構(gòu)比下推自動(dòng)機(jī)簡(jiǎn)單且分析效率高

(8)與(a|b)*(a|b)等價(jià)正規(guī)式是

。

A．(a|b)(a|b)* B．a(chǎn)*|b*

C．(ab)*(a|b)* D．(a|b)*第15頁(yè)

【解答】

(1)由教材第一章1.3節(jié)中詞法分析，可知詞法分析所遵照是語(yǔ)言構(gòu)詞規(guī)則。故選B。

(2)詞法分析器功效是輸入源程序，輸出單詞符號(hào)。故選B。

(3)詞法分析器輸出單詞符號(hào)通常表示為二元式：(單詞種別，單詞本身值)。故選B。

(4)即使選項(xiàng)A、B、D都滿足題意，但選項(xiàng)D更準(zhǔn)確。故選D。第16頁(yè)

(5)?NFA能夠有DFA與之等價(jià)，即二者描述能力相同；也即，對(duì)于任一給定NFAM，一定存在一個(gè)DFAM'，使L(M)=L(M′)。故選B。

(6)?DFA便于識(shí)別，易于計(jì)算機(jī)實(shí)現(xiàn)，而NFA便于定理證實(shí)。故選C。

(7)本題即使是第二章題，但答案參見(jiàn)第三章3.1.3節(jié)。即選C。

(8)因?yàn)檎齽t閉包R+=R*R=RR*，故(a|b)*(a|b)=(a|b)(a|b)*。故選A。第17頁(yè)

2.2什么是掃描器？掃描器功效是什么？

【解答】掃描器就是詞法分析器，它接收輸入源程序，對(duì)源程序進(jìn)行詞法分析并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。通常把詞法分析器作為一個(gè)子程序，每當(dāng)語(yǔ)法分析器需要一個(gè)單詞符號(hào)時(shí)就調(diào)用這個(gè)子程序。每次調(diào)用時(shí)，詞法分析器就從輸入串中識(shí)別出一個(gè)單詞符號(hào)交給語(yǔ)法分析器。第18頁(yè)

2.3設(shè)M=({x,y},{a,b},f,x,{y})為一非確定有限自動(dòng)機(jī)，其中f定義以下：

f(x,a)={x,y} f{x,b}={y}

f(y,a)=Φ f{y,b}={x,y}

試結(jié)構(gòu)對(duì)應(yīng)確實(shí)定有限自動(dòng)機(jī)M′。

【解答】對(duì)照自動(dòng)機(jī)定義M=(S,Σ,f,?s0,?Z)，由f定義可知f(x,a)、f(y,b)均為多值函數(shù)，所以M是一非確定有限自動(dòng)機(jī)。

先畫出NFAM對(duì)應(yīng)狀態(tài)圖，如圖2-2所表示。第19頁(yè)圖2-2習(xí)題2.3NFAM

第20頁(yè)

用子集法結(jié)構(gòu)狀態(tài)轉(zhuǎn)換矩陣，如表2-1所表示。

表2-1狀態(tài)轉(zhuǎn)換矩陣

將轉(zhuǎn)換矩陣中全部子集重新命名，形成表2-2所表示狀態(tài)轉(zhuǎn)換矩陣，即得到

第21頁(yè)

將圖2-3所表示DFAM′最小化。首先，將M′狀態(tài)分成終態(tài)組{1,2}與非終態(tài)組{0}。其次，考查{1,2}。因?yàn)閧1,2}a={1,2}b={2}{1,2}，所以不再將其劃分了，也即整個(gè)劃分只有兩組：{0}和{1,2}。令狀態(tài)1代表{1,2}，即把原來(lái)抵達(dá)2弧都導(dǎo)向1，并刪除狀態(tài)2。最終，得到如圖2-4所表示化簡(jiǎn)了DFAM′。圖2-3習(xí)題2.3DFAM′其狀態(tài)轉(zhuǎn)換圖如圖2-3所表示。第22頁(yè)圖2-4圖2-3化簡(jiǎn)后DFAM′

第23頁(yè)

2.4正規(guī)式(ab)*a與正規(guī)式a(ba)*是否等價(jià)？請(qǐng)說(shuō)明理由。

【解答】正規(guī)式(ab)*a對(duì)應(yīng)NFA如圖2-5所表示，正規(guī)式a(ba)*對(duì)應(yīng)NFA如圖2-6所表示。

用子集法將圖2-5和圖2-6分別確定化為如圖2-7(a)和(b)所表示狀態(tài)轉(zhuǎn)換矩陣，它們最終都能夠得到最簡(jiǎn)DFA，如圖2-8所表示。所以，這兩個(gè)正規(guī)式等價(jià)。第24頁(yè)圖2-5正規(guī)式(ab)*a對(duì)應(yīng)NFA第25頁(yè)圖2-6正規(guī)式a(ba)*對(duì)應(yīng)NFA第26頁(yè)圖2-7圖2-5和圖2-6確定化后狀態(tài)轉(zhuǎn)換矩陣

—第27頁(yè)圖2-8最簡(jiǎn)DFA

第28頁(yè)

實(shí)際上，當(dāng)閉包*取0時(shí)，正規(guī)式(ab)*a與正規(guī)式a(ba)*由初態(tài)X到終態(tài)Y之間僅存在一條a弧。因?yàn)?ab)*在a之前，故描述(ab)*弧應(yīng)在初態(tài)結(jié)點(diǎn)X上；而(ba)*在a之后，故(ba)*對(duì)應(yīng)弧應(yīng)在終態(tài)結(jié)點(diǎn)Y上。所以，(ab)*a和a(ba)*所對(duì)應(yīng)NFA也可分別描述為如圖2-9(a)和(b)所表示形式，它們確定化并化簡(jiǎn)后仍可得到圖2-8所表示最簡(jiǎn)DFA。第29頁(yè)圖2-9(ab)*a和a(ba)*分別對(duì)應(yīng)NFA

第30頁(yè)

2.5設(shè)有L(G)={a2n+1b2ma2p+1|

n≥0,p≥0,m≥1}。

(1)給出描述該語(yǔ)言正規(guī)表示式；

(2)結(jié)構(gòu)識(shí)別該語(yǔ)言確實(shí)定有限自動(dòng)機(jī)(可直接用狀態(tài)圖形式給出)。

【解答】該語(yǔ)言對(duì)應(yīng)正規(guī)表示式為a(aa)*bb(bb)*a(aa)*，正規(guī)表示式對(duì)應(yīng)NFA如圖2-10所表示。

第31頁(yè)圖2-10習(xí)題2.5NFA第32頁(yè)用子集法將圖2-10確定化，如圖2-11所表示。

由圖2-11重新命名后狀態(tài)轉(zhuǎn)換矩陣可化簡(jiǎn)為(也可由最小化方法得到)

{0,2}{1}{3,5}{4,6}{7}

圖2-11習(xí)題2.5狀態(tài)轉(zhuǎn)換矩陣

第33頁(yè)

按次序重新命名為0、1、2、3、4后得到最簡(jiǎn)DFA，如圖2-12所表示。圖2-12習(xí)題2.5最簡(jiǎn)DFA

第34頁(yè)

2.6有語(yǔ)言L={w?|?w∈(0,1)+，而且w中最少有兩個(gè)1，又在任何兩個(gè)1之間有偶數(shù)個(gè)0}，試結(jié)構(gòu)接收該語(yǔ)言確實(shí)定有限狀態(tài)自動(dòng)機(jī)(DFA)。

【解答】對(duì)于語(yǔ)言L，w中最少有兩個(gè)1，且任意兩個(gè)1之間必須有偶數(shù)個(gè)0；也即在第一個(gè)1之前和最終一個(gè)1之后，對(duì)0個(gè)數(shù)沒(méi)有要求。據(jù)此我們求出L正規(guī)式為0*1(00(00)*1)*00(00)*10*，畫出與正規(guī)式對(duì)應(yīng)NFA，如圖2-13所表示。第35頁(yè)圖2-13習(xí)題2.6NFA第36頁(yè)

用子集法將圖2-13所表示NFA確定化，如圖2-14所表示

由圖2-14可看出非終態(tài)2和4下一狀態(tài)相同，終態(tài)6和8下一狀態(tài)相同，即得到最簡(jiǎn)狀態(tài)為

{0}{1}{2,4}{3}{5}{6,8}{7}

第37頁(yè)按次序重新命名為0、1、2、3、4、5、6，則得到最簡(jiǎn)DFA，如圖2-15所表示。圖2-15習(xí)題2.6最簡(jiǎn)DFA第38頁(yè)

2.7已知正規(guī)式((a?|?b)*|?aa)*b和正規(guī)式(a?|?b)*b。

(1)試用有限自動(dòng)機(jī)等價(jià)性證實(shí)這兩個(gè)正規(guī)式是等價(jià)；

(2)給出對(duì)應(yīng)正規(guī)文法。

【解答】(1)正規(guī)式((a?|?b)*|?aa)*b對(duì)應(yīng)NFA如圖2-16所表示。

用子集法將圖2-16所表示NFA確定化為DFA，如圖2-17所表示。第39頁(yè)圖2-16正規(guī)式((a?|?b)*|aa)*b對(duì)應(yīng)NFA

第40頁(yè)圖2-17圖2-16確定化后狀態(tài)轉(zhuǎn)換矩陣第41頁(yè)

因?yàn)閷?duì)非終態(tài)狀態(tài)1、2來(lái)說(shuō)，它們輸入a、b下一狀態(tài)是一樣，故狀態(tài)1和狀態(tài)2能夠合并，將合并后終態(tài)3命名為2，則得到表2-3(注意，終態(tài)和非終態(tài)即使輸入a、b下一狀態(tài)相同也不能合并)。

由此得到最簡(jiǎn)DFA，如圖2-18所表示。

正規(guī)式(a?|?b)*b對(duì)應(yīng)NFA如圖2-19所表示。

用子集法將圖2-19所表示NFA確定化為如圖2-20所表示狀態(tài)轉(zhuǎn)換矩陣。第42頁(yè)表2-3合并后狀態(tài)轉(zhuǎn)換矩陣

第43頁(yè)圖2-18習(xí)題2.7最簡(jiǎn)DFA第44頁(yè)圖2-19正規(guī)式(a?|?b)*b對(duì)應(yīng)NFA第45頁(yè)

比較圖2-20與圖2-17，重新命名后轉(zhuǎn)換矩陣是完全一樣，也即正規(guī)式(a?|?b)*b能夠一樣得到化簡(jiǎn)后DFA如圖2-18所表示。所以，兩個(gè)自動(dòng)機(jī)完全一樣，即兩個(gè)正規(guī)文法等價(jià)。圖2-20圖2-19確定化后狀態(tài)轉(zhuǎn)換矩陣

第46頁(yè)2.8結(jié)構(gòu)一個(gè)DFA，它接收Σ

={a,b}上全部不含abb字符串。

解：Σ

={a,b}上全部不含abb字符串可表示為b*(a*b)a*。

第47頁(yè)2.9結(jié)構(gòu)一個(gè)DFA，它接收Σ

={a,b}上全部含偶數(shù)個(gè)a字符串。

解：Σ

={a,b}上全部含偶數(shù)個(gè)a字符串可表示為(b|ab*a)*第48頁(yè)

2.10以下程序段以B表示循環(huán)體，A表示初始化，I表示增量，T表示測(cè)試：

I=1;

while(I<=n)

{

sun=sun+a[I];

I=I+1;

}

請(qǐng)用正規(guī)表示式表示這個(gè)程序段可能執(zhí)行序列。

【解答】用正規(guī)表示式表示程序段可能執(zhí)行序列為AT(BIT)*。第49頁(yè)

2.9將圖2-21所表示非確定有限自動(dòng)機(jī)(NFA)變換成等價(jià)確實(shí)定有限自動(dòng)機(jī)(DFA)。

其中，X為初態(tài)，Y為終態(tài)。

【解答】用子集法將NFA確定化，如圖2-22所表示。第50頁(yè)圖2-21習(xí)題2.9NFA第51頁(yè)圖2-22習(xí)題2.9狀態(tài)轉(zhuǎn)換矩陣

{2}{2,Y}{2,4}{2}{2,Y}{2,4}{2,4}{2,4}{2,4,Y}{2,4,Y}{2,4,Y}第52頁(yè)

圖2-22所對(duì)應(yīng)DFA如圖2-23所表示。

對(duì)圖2-23所表示DFA進(jìn)行最小化。首先將狀態(tài)分為非終態(tài)集和終態(tài)集兩部分：{0,1,2,5}和{3,4,6,7}。由終態(tài)集可知，對(duì)于狀態(tài)3、6、7，不論輸入字符是a還是b下一狀態(tài)均為終態(tài)集，而狀態(tài)4在輸入字符b下一狀態(tài)落入非終態(tài)集，故將其劃分為

{0,1,2,5}，{4}，{3,6,7}

對(duì)于非終態(tài)集，在輸入字符a、b后按其下一狀態(tài)落入狀態(tài)集不一樣而最終劃分為

{0}，{1}，{2}，{5}，{4}，{3,6,7}

按次序重新命名為0、1、2、3、4、5，得到最簡(jiǎn)DFA如圖2-24所表示。第53頁(yè)圖2-23習(xí)題2.9DFA第54頁(yè)

圖2-24習(xí)題2.9最簡(jiǎn)DFA第55頁(yè)

2.10有一臺(tái)自動(dòng)售貨機(jī)，接收1分和2分硬幣，出售3分錢一塊硬糖。用戶每次向機(jī)器中投放大于等于3分硬幣，便可得到一塊糖(注意：只給一塊而且不找錢)。

(1)寫出售貨機(jī)售糖正規(guī)表示式；

(2)結(jié)構(gòu)識(shí)別上述正規(guī)式最簡(jiǎn)DFA。

【解答】(1)設(shè)a=1，b=2，則售貨機(jī)售糖正規(guī)表示式為a(b?|?a(a?|?b))?|?b(a?|?b)。

(2)畫出與正規(guī)表示式a(b?|?a(a?|?b))?|?b(a?|?b)對(duì)應(yīng)NFA，如圖2-25所表示。

用子集法將圖2-25所表示NFA確定化，如圖2-26所表示。第56頁(yè)圖2-25習(xí)題2.10NFA第57頁(yè)

由圖2-26可看出，非終態(tài)2和非終態(tài)3面對(duì)輸入符號(hào)a或b下一狀態(tài)相同，故合并為一個(gè)狀態(tài)，即最簡(jiǎn)狀態(tài){0}、{1}、{2，3}、{4}。圖2-26習(xí)題2.10狀態(tài)轉(zhuǎn)換矩陣第58頁(yè)

按次序重新命名為0、1、2、3，則得到最簡(jiǎn)DFA，如圖2-27所表示。圖2-27習(xí)題2.10最簡(jiǎn)DFA第59頁(yè)第三章語(yǔ)法分析

3.1完成以下選擇題：

(1)程序語(yǔ)言語(yǔ)義需要

用來(lái)描述。

A．上下文無(wú)關(guān)文法B．上下文相關(guān)文法

C．正規(guī)文法 D．短語(yǔ)文法

(2)2型文法對(duì)應(yīng)

。

A．圖靈機(jī) B．有限自動(dòng)機(jī)

C．下推自動(dòng)機(jī) D．線性界限自動(dòng)機(jī)第60頁(yè)

(3)下述結(jié)論中，

是正確。

A．1型語(yǔ)言

0型語(yǔ)言 B．2型語(yǔ)言

1型語(yǔ)言

C．3型語(yǔ)言

2型語(yǔ)言 D．A～C均不成立

(4)有限狀態(tài)自動(dòng)機(jī)能識(shí)別_________。

A．上下文無(wú)關(guān)文法 B．上下文相關(guān)文法

C．正規(guī)文法 D．短語(yǔ)文法

(5)文法G[S]：S→xSx|y所識(shí)別語(yǔ)言是

。

A．xyx B．(xyx)*

C．xnyxn(n≥0) D．x*yx*第61頁(yè)

(6)只含有單層分枝子樹(shù)稱為“簡(jiǎn)單子樹(shù)”，則句柄直觀解釋是

。

A．子樹(shù)末端結(jié)點(diǎn)(即樹(shù)葉)組成符號(hào)串

B．簡(jiǎn)單子樹(shù)末端結(jié)點(diǎn)組成符號(hào)串

C．最左簡(jiǎn)單子樹(shù)末端結(jié)點(diǎn)組成符號(hào)串

D．最左簡(jiǎn)單子樹(shù)末端結(jié)點(diǎn)組成符號(hào)串且該符號(hào)串必須含有終止符第62頁(yè)

(7)下面對(duì)語(yǔ)法樹(shù)錯(cuò)誤描述是

。

A．根結(jié)點(diǎn)用文法G[S]開(kāi)始符S標(biāo)識(shí)

B．每個(gè)結(jié)點(diǎn)用G[S]一個(gè)終止符或非終止符標(biāo)識(shí)

C．假如某結(jié)點(diǎn)標(biāo)識(shí)為ε，則它必為葉結(jié)點(diǎn)

D．內(nèi)部結(jié)點(diǎn)能夠是非終止符

(8)由文法開(kāi)始符S經(jīng)過(guò)零步或多步推導(dǎo)產(chǎn)生符號(hào)序列是

。

A．短語(yǔ)B．句柄 C．句型 D．句子第63頁(yè)

(9)設(shè)文法G[S]：S→SA|A

A→a|b

則對(duì)句子aba規(guī)范推導(dǎo)是

。

A．SSASAAAAA

aAAabAaba

B．SSASAAAAAAAaAbaaba

C．SSASAASAaSbaAbaaba

D．SSASaSAaSbaAbaaba

第64頁(yè)

(10)假如文法G[S]是無(wú)二義，則它任何句子α其

。

A．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)語(yǔ)法樹(shù)必定相同

B．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)語(yǔ)法樹(shù)可能不一樣

C．最左推導(dǎo)和最右推導(dǎo)必定相同

D．可能存在兩個(gè)不一樣最右推導(dǎo)，但它們對(duì)應(yīng)語(yǔ)法樹(shù)相同

(11)一個(gè)句型分析樹(shù)代表了該句型

。

A．推導(dǎo)過(guò)程 B．歸約過(guò)程

C．生成過(guò)程 D．翻譯過(guò)程第65頁(yè)

(12)規(guī)范歸約中“可歸約串”由

定義。

A．直接短語(yǔ) B．最右直接短語(yǔ)

C．最左直接短語(yǔ) D．最左素短語(yǔ)

(13)規(guī)范歸約是指

。

A．最左推導(dǎo)逆過(guò)程B．最右推導(dǎo)逆過(guò)程

C．規(guī)范推導(dǎo) D．最左歸約逆過(guò)程第66頁(yè)

(14)文法G[S]：S→aAcB|Bd

A→AaB|c

B→bScA|b

則句型aAcbBdcc短語(yǔ)是

。

A．Bd B．cc C．a(chǎn) D．b

(15)文法G[E]：E→E+T|T

T→T*P|P

P→(E)|i

則句型P+T+i句柄和最左素短語(yǔ)是

。

A．P+T和T B．P和P+T

C．i和P+T+i D．P和P

第67頁(yè)

(16)采取自頂向下分析，必須

。

A．消除左遞歸 B．消除右遞歸

C．消除回朔 D．提取公共左因子

(17)對(duì)文法G[E]：E→E+S|S

S→S*F|F

F→(E)|i

則FIRST(S)=

。

A．{(} B．{(,i}

C．{i} D．{(,)}第68頁(yè)

(18)確定自頂向下分析要求文法滿足

。

A．不含左遞歸 B．不含二義性

C．無(wú)回溯 D．A～C項(xiàng)

(19)遞歸下降分析器由一組遞歸函數(shù)組成，且每一個(gè)函數(shù)對(duì)應(yīng)文法

。

A．一個(gè)終止符B．一個(gè)非終止符

C．多個(gè)終止符D．多個(gè)非終止符

(20)?LL(1)分析表需要預(yù)先定義和結(jié)構(gòu)兩族與文法相關(guān)集合

。

A．FIRST和FOLLOWB．FIRSTVT和FOLLOW

C．FIRST和LASTVTD．FIRSTVT和LASTVT第69頁(yè)

(21)設(shè)a、b、c是文法終止符且滿足優(yōu)先關(guān)系ab和bc,則

。

A．必有ac B．必有ca

C．必有ba D．A～C都不一定成立

(22)算符優(yōu)先分析法要求

。

A．文法不存在…QR…句型且任何終止符對(duì)(a,b)滿足ab、a?b和a?b三種關(guān)系

B．文法不存在…QR…句型且任何終止符對(duì)(a,b)至多滿足ab、a?b和a?b三種關(guān)系之一第70頁(yè)

C．文法可存在…QR…句型且任何終止符對(duì)(a,b)至多滿足ab、a?b和a?b三種關(guān)系之一

D．文法可存在…QR…句型且任何終止符對(duì)(a,b)滿足ab、a?b和a?b三種關(guān)系

(23)任何算符優(yōu)先文法

優(yōu)先函數(shù)。

A．有一個(gè) B．沒(méi)有

C．有若干個(gè) D．可能有若干個(gè)

(24)在算符優(yōu)先分析中，用

來(lái)刻畫可歸約串。

A．句柄 B．直接短語(yǔ)

C．素短語(yǔ) D．最左素短語(yǔ)第71頁(yè)

(25)下面最左素短語(yǔ)必須具備條件中有錯(cuò)誤是

。

A．最少包含一個(gè)終止符

B．最少包含一個(gè)非終止符

C．除本身外不再包含其它素短語(yǔ)

D．在句型中含有最左性

(26)對(duì)文法G[S]：S→b|∧|(T)

T→T，S|S

其FIRSTVT(T)為

。

A．{b,∧,(} B．{b,∧,)}

C．{，,b,∧,(} D．{，,b,∧,)}第72頁(yè)

(27)對(duì)文法G[E]：E→E*T|T

T→T+i|i

句子1+2*8+6歸約值為

。

A．23 B．42 C．30 D．17

(28)下述FOLLOW集結(jié)構(gòu)方法中錯(cuò)誤是

。

A．對(duì)文法開(kāi)始符S有#∈FOLLOW(S)

B．若有A→αBβ，則有FIRST(β)\{ε}FOLLOW(B)

C．若有A→αB，則有FOLLOW(B)FOLLOW(A)

D．若有A→αB，則有FOLLOW(A)FOLLOW(B)第73頁(yè)

(29)若文法G[S]產(chǎn)生式有…AB…出現(xiàn)，則對(duì)A求FOLLOW集正確是

。

A．FOLLOW(B)FOLLOW(A)

B．FIRSTVT(B)FOLLOW(A)

C．FIRST(B)\{ε}FOLLOW(A)

D．LASTVT(B)FOLLOW(A)

(30)下面

是自底向上分析方法。

A．預(yù)測(cè)分析法 B．遞歸下降分析法

C．LL(1)分析法 D．算符優(yōu)先分析法第74頁(yè)

(31)下面

是采取句柄進(jìn)行歸約。

A．算符優(yōu)先分析法 B．預(yù)測(cè)分析法

C．SLR(1)分析法 D．LL(1)分析法

(32)一個(gè)

指明了在分析過(guò)程中某時(shí)刻能看到產(chǎn)生式多大一部分。

A．活前綴 B．前綴

C．項(xiàng)目 D．項(xiàng)目集

(33)若B為非終止符，則A→α·Bβ為

項(xiàng)目。

A．接收 B．歸約

C．移進(jìn) D．待約第75頁(yè)

(34)在LR(0)ACTION子表中，假如某一行中存在標(biāo)識(shí)為“rj”欄，則

。

A．該行必定填滿rj B．該行未填滿rj

C．其它行也有rj D．GOTO子表中也有rj

(35)?LR分析法處理“移進(jìn)—?dú)w約”沖突時(shí)，左結(jié)合意味著

。

A．打斷聯(lián)絡(luò)實(shí)施移進(jìn) B．打斷聯(lián)絡(luò)實(shí)施歸約

C．建立聯(lián)絡(luò)實(shí)施移進(jìn) D．建立聯(lián)絡(luò)實(shí)施歸約第76頁(yè)

(36)?LR分析法處理“移進(jìn)—?dú)w約”沖突時(shí)，右結(jié)合意味著

。

A．打斷聯(lián)絡(luò)實(shí)施歸約 B．建立聯(lián)絡(luò)實(shí)施歸約

C．建立聯(lián)絡(luò)實(shí)施移進(jìn) D．打斷聯(lián)絡(luò)實(shí)施移進(jìn)第77頁(yè)

【解答】

(1)參見(jiàn)第四章4.1.1節(jié)，語(yǔ)義分析不像詞法分析和語(yǔ)法分析那樣能夠分別用正規(guī)文法和上下文無(wú)關(guān)文法描述，因?yàn)檎Z(yǔ)義是上下文相關(guān)，所以語(yǔ)義分析須用上下文相關(guān)文法描述。即選B。

(2)2型文法對(duì)應(yīng)下推自動(dòng)機(jī)。故選C。

(3)因?yàn)椴淮嬖冢?型語(yǔ)言

2型語(yǔ)言

1型語(yǔ)言

0型語(yǔ)言。故選D。

(4)3型文法即正規(guī)文法，它識(shí)別系統(tǒng)是有限狀態(tài)自動(dòng)機(jī)。故選C。第78頁(yè)

(5)由S→xSx|y可知該文法所識(shí)別語(yǔ)言一定是：y左邊出現(xiàn)x與y右邊出現(xiàn)x相等。故選C。

(6)最左簡(jiǎn)單子樹(shù)末端結(jié)點(diǎn)組成符號(hào)串為句柄。故選C。

(7)內(nèi)部結(jié)點(diǎn)(指非樹(shù)葉結(jié)點(diǎn))一定是非終止符。故選D。

(8)由文法開(kāi)始符S經(jīng)過(guò)零步或多步推導(dǎo)產(chǎn)生符號(hào)序列一定是句型，僅當(dāng)推導(dǎo)產(chǎn)生符號(hào)序列全部由終止符組成時(shí)才是句子，即句子是句型陣列。故選C。

(9)規(guī)范推導(dǎo)即最右推導(dǎo)，也即每一步推導(dǎo)都是對(duì)句型中最右非終止符用對(duì)應(yīng)產(chǎn)生式右部進(jìn)行替換。故選D。第79頁(yè)

(10)文法G[S]一個(gè)句子假如能找到兩種不一樣最左推導(dǎo)(或最右推導(dǎo))，或存在兩棵不一樣語(yǔ)法樹(shù)，則它任何句子α其最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)語(yǔ)法樹(shù)必定相同。故選A。

(11)一個(gè)句型分析樹(shù)代表了該句型歸約過(guò)程。故選B。

(12)規(guī)范歸約中“可歸約串”即為句柄，也就是最左直接短語(yǔ)。故選C。

(13)規(guī)范歸約逆過(guò)程是規(guī)范推導(dǎo)，而規(guī)范推導(dǎo)即為最右推導(dǎo)。故選B。

(14)由圖3-1可知應(yīng)選A。第80頁(yè)圖3-1句型aAcbBdcc對(duì)應(yīng)語(yǔ)法樹(shù)第81頁(yè)

(15)由圖3-2可知，句柄(最左直接短語(yǔ))為P，最左素短語(yǔ)為P+T。故選B。

(16)回溯使自頂向下分析效率降低，左遞歸使得自頂向下分析無(wú)法實(shí)現(xiàn)；二者相比消除左遞歸更為主要。故選A。

(17)?FIRST(F)={(,i}，而由S→F可知FIRST(F)\{ε}FIRST(S)，即FIRST(S)={(,i}。故選B。

(18)左遞歸和二義性將無(wú)法實(shí)現(xiàn)自頂向下分析，回溯則使自頂向下分析效率下降。故選D。第82頁(yè)圖3-2句型P+T+i對(duì)應(yīng)語(yǔ)法樹(shù)及優(yōu)先關(guān)系示意第83頁(yè)

(19)遞歸下降分析器由一組遞歸函數(shù)組成，且每一個(gè)函數(shù)對(duì)應(yīng)文法一個(gè)非終止符。故選B。

(20)?LL(1)分析表需要預(yù)先定義和結(jié)構(gòu)兩族與文法相關(guān)集合FIRST和FOLLOW。故選A。

(21)因?yàn)閍b和bc并不能使選項(xiàng)A、B、C成立。故選D。

(22)由算法優(yōu)先文法可知應(yīng)選B。

(23)有些算符優(yōu)先文法不存在優(yōu)先函數(shù)；有些算符優(yōu)先文法存在優(yōu)先函數(shù)，且只要存在一對(duì)優(yōu)先函數(shù)，就存在無(wú)窮多對(duì)優(yōu)先函數(shù)。故選D。

(24)在算符優(yōu)先分析中是以“最左素短語(yǔ)”來(lái)刻畫可歸約串。故選D。第84頁(yè)

(25)最左素短語(yǔ)必須具備三個(gè)條件是：①最少包含一個(gè)終止符；②除本身外不得包含其它素短語(yǔ)；③在句型中含有最左性。故選B。

(26)?FIRSTVT(T)={，}，F(xiàn)IRSTVT(S)={b,∧,(}；由T→S可知FIRSTV(S)FIRSTVT(T)，即FIRSTVT(T)={，,b,∧,(}。故選C。

(27)由圖3-3可知應(yīng)選B。

(28)若有A→αB則有FOLLOW(A)FOLLOW(B)，即選項(xiàng)C錯(cuò)。故選C。

(29)若文法G[S]產(chǎn)生式有…AB…出現(xiàn)，則有FIRST(B)\{ε}FOLLOW(A)。故選C。第85頁(yè)圖3-3句子1+2*8+6語(yǔ)法樹(shù)及值改變示意第86頁(yè)

(30)自底向上分析方法有算符優(yōu)先分析法和LR分析法。故選D。

(31)自底向上分析采取歸約方法，但算符優(yōu)先分析用“最左素短語(yǔ)”歸約，而LR分析用“句柄”歸約。SLR(1)是LR分析法一個(gè)，故選C。

(32)在LR分析中，一個(gè)項(xiàng)目指明了在分析過(guò)程某個(gè)時(shí)刻所看到產(chǎn)生式多大一部分。故選C。

(33)對(duì)文法G[S’]，S'→α·稱為“接收”項(xiàng)目；形如A→α·aβ項(xiàng)目(其中a為終止符)稱為“移進(jìn)”項(xiàng)目；形如A→α·Bβ項(xiàng)目(其中B為非終止符)稱為“待約”項(xiàng)目。故選D。第87頁(yè)

(34)在LR(0)ACTION子表中，假如某一行存在標(biāo)注為“rj”欄，則該行必定填滿rj，而在SLR(1)ACTION子表中，假如某一行存在標(biāo)注為“rj”欄，則該行可能未填滿rj。所以選A。

(35)?LR分析法處理“移進(jìn)—?dú)w約”沖突時(shí)，左結(jié)合意味著打斷聯(lián)絡(luò)而實(shí)施歸約，右結(jié)合意味著維持聯(lián)絡(luò)而實(shí)施移進(jìn)。故選B。

(36)由(35)可知應(yīng)選C。第88頁(yè)

3.2令文法G[N]為

G[N]:N→D?|?ND

D→0?|?1?|?2?|?3?|?4?|?5?|?6?|?7?|?8?|?9

(1)?G[N]語(yǔ)言L(G)是什么?

(2)給出句子0127、34和568最左推導(dǎo)和最右推導(dǎo)。第89頁(yè)

【解答】

(1)?G[N]語(yǔ)言L(G[N])是非負(fù)整數(shù)。

(2)最左推導(dǎo)：

最右推導(dǎo)：

第90頁(yè)

3.3已知文法G[S]為S→aSb?|?Sb?|?b，試證實(shí)文法G[S]為二義文法。

【解答】由文法G[S]：S→aSb?|?Sb?|?b，對(duì)句子aabbbb可對(duì)應(yīng)如圖3-4所表示兩棵語(yǔ)法樹(shù)。

所以，文法G[S]為二義文法(對(duì)句子abbb也可畫出兩棵不一樣語(yǔ)法樹(shù))。第91頁(yè)圖3-4句子aabbbb對(duì)應(yīng)兩棵不一樣語(yǔ)法樹(shù)第92頁(yè)

3.4已知文法G[S]為S→SaS?|?ε，試證實(shí)文法G[S]為二義文法。

【解答】由文法G[S]：S→SaS?|?ε，句子aa語(yǔ)法樹(shù)如圖3-5所表示。

由圖3-5可知，文法G[S]為二義文法。第93頁(yè)圖3-5句子aa對(duì)應(yīng)兩棵不一樣語(yǔ)法樹(shù)第94頁(yè)

3.5按指定類型，給出語(yǔ)言文法。

(1)?L={aibj?|?j＞i≥0}上下文無(wú)關(guān)文法；

(2)字母表Σ={a,b}上同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b全部串集合正規(guī)文法；

(3)由相同個(gè)數(shù)a和b組成句子無(wú)二義文法。

【解答】(1)由L={aibj?|?j＞i≥0}知，所求該語(yǔ)言對(duì)應(yīng)上下文無(wú)關(guān)文法首先應(yīng)有S→aSb型產(chǎn)生式，以確保b個(gè)數(shù)不少于a個(gè)數(shù)；其次，還需有S→Sb或S→b型產(chǎn)生式，用以確保b個(gè)數(shù)多于a個(gè)數(shù)。所以，所求上下文無(wú)關(guān)文法G[S]為

G[S]：S→aSb?|?Sb?|?b第95頁(yè)

(2)為了結(jié)構(gòu)字母表Σ={a,b}上同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b全部串集合正規(guī)式，我們畫出如圖3-6所表示DFA，即由開(kāi)始符S出發(fā)，經(jīng)過(guò)奇數(shù)個(gè)a抵達(dá)狀態(tài)A，或經(jīng)過(guò)奇數(shù)個(gè)b抵達(dá)狀態(tài)B；而由狀態(tài)A出發(fā)，經(jīng)過(guò)奇數(shù)個(gè)b抵達(dá)狀態(tài)C(終態(tài))；一樣，由狀態(tài)B出發(fā)經(jīng)過(guò)奇數(shù)個(gè)a抵達(dá)終態(tài)C。

由圖3-6可直接得到正規(guī)文法G[S]以下：

G[S]：S→aA?|?bB

A→aS?|?bC?|?b

B→bS?|?aC?|?a

C→bA?|?aB?|?ε第96頁(yè)圖3-6第97頁(yè)

(3)我們用一個(gè)非終止符A代表一個(gè)a(即有A→a)，用一個(gè)非終止符B代表一個(gè)b(即有B→b)；為了確保a和b個(gè)數(shù)相同，則在出現(xiàn)一個(gè)a時(shí)應(yīng)對(duì)應(yīng)地出現(xiàn)一個(gè)B，出現(xiàn)一個(gè)b時(shí)則對(duì)應(yīng)出現(xiàn)一個(gè)A。假定已推導(dǎo)出bA，假如下一步要推導(dǎo)出連續(xù)兩個(gè)b，則應(yīng)有bAbbAA。也即為了確保b和A個(gè)數(shù)一致，應(yīng)有A→bAA；同理有B→aBB。另外，為了確保遞歸地推出所要求ab串，應(yīng)有S→aBS和S→bAS。由此得到無(wú)二義文法G[S]為

G[S]：S→aBS?|?bAS?|?ε

A→bAA?|?a

B→aBB?|?b第98頁(yè)

3.6有文法G[S]:S→aAcB?|?Bd

A→AaB?|?c

B→bScA?|?b

(1)試求句型aAaBcbbdcc和aAcbBdcc句柄；

(2)寫出句子acabcbbdcc最左推導(dǎo)過(guò)程。

【解答】(1)分別畫出對(duì)應(yīng)句型aAaBcbbdcc和aAcbBdcc語(yǔ)法樹(shù)如圖3-7(a)、(b)所表示。

對(duì)樹(shù)(a)，直接短語(yǔ)有3個(gè)：AaB、b和c，而AaB為最左直接短語(yǔ)(即為句柄)。對(duì)樹(shù)(b)，直接短語(yǔ)有兩個(gè)：Bd和c，而B(niǎo)d為最左直接短語(yǔ)。第99頁(yè)能否不畫出語(yǔ)法樹(shù)，而直接由定義(即在句型中)尋找滿足某個(gè)產(chǎn)生式候選式這么一個(gè)最左子串(即句柄)呢？比如，對(duì)句型aAaBcbbdcc，我們能夠由左至右掃描找到第一個(gè)子串AaB，它恰好是滿足A→AaB右部子串；與樹(shù)(a)對(duì)照，AaB確實(shí)是該句型句柄。是否這一方法一直正確呢？我們繼續(xù)檢驗(yàn)句型aAcbBdcc，由左至右找到第一個(gè)子串c，這是滿足A→c右部子串，但由樹(shù)(b)可知，c不是該句型句柄。由此可知，畫出對(duì)應(yīng)句型語(yǔ)法樹(shù)然后尋找最左直接短語(yǔ)是確定句柄好方法。第100頁(yè)圖3-7習(xí)題3.6語(yǔ)法樹(shù)(a)?aAaBcbbdcc;(b)?aAcbBdcc第101頁(yè)

(2)句子acabcbbdcc最左推導(dǎo)以下：第102頁(yè)

3.7對(duì)于文法G[S]:S→(L)?|?aS?|?a

L→L,S?|?S

(1)畫出句型(S,(a))語(yǔ)法樹(shù)；

(2)寫出上述句型全部短語(yǔ)、直接短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)。第103頁(yè)

【解答】(1)句型(S,(a))語(yǔ)法樹(shù)如圖3-8所表示。

(2)由圖3-8可知：

短語(yǔ)：S、a、(a)、S,(a)、(S,(a))；

直接短語(yǔ)：a、S；

句柄：S；

素短語(yǔ)：素短語(yǔ)可由圖3-8中相鄰終止符之間優(yōu)先關(guān)系求得，即：

#?(?，?(?a?)?)?#

所以，素短語(yǔ)為a。第104頁(yè)圖3-8句型(S,(a))語(yǔ)法樹(shù)第105頁(yè)

3.8下述文法描述了C語(yǔ)言整數(shù)變量申明語(yǔ)句：

G[D]:D→TL

T→int?|?long?|?short

L→id?|?L,id

(1)改造上述文法，使其接收相同輸入序列，但文法是右遞歸；

(2)分別以上述文法G[D]和改造后文法G′[D]為輸入序列inta,b,c結(jié)構(gòu)分析樹(shù)。第106頁(yè)

【解答】(1)消除左遞歸后，文法G′[D]以下：

D→TL

T→int?|?long?|?short

L→idL′

L′→,idL′|?ε

(2)未消除左遞歸文法G(D)和消除左遞歸文法G′[D]為輸入序列inta,b,c結(jié)構(gòu)分析樹(shù)分別如圖3-9(a)、(b)所表示。第107頁(yè)圖3-9兩種文法為inta,b,c結(jié)構(gòu)分析樹(shù)

(a)文法G(D)；(b)文法G′(D)第108頁(yè)

3.9考慮文法G[S]:S→(T)|a+S|a

T→T,S|S

消除文法左遞歸及提取公共左因子，然后對(duì)每個(gè)非終止符寫出不帶回溯遞歸子程序。

【解答】消除文法G[S]左遞歸：

S→(T)|a+S|a

T→ST′

T′→,ST′|ε第109頁(yè)

提取公共左因子：

S→(T)|aS′

S′→+S|ε

T→ST′

T′→,ST′|ε第110頁(yè)

改造后文法已經(jīng)是LL(1)文法，不帶回溯遞歸子程序以下：

voidmatch(tokent)

{

if(lookahead==t)

lookahead=nexttoken;

elseerror();

}

voidS()第111頁(yè)

{

if(lookahead==′a′)

{match(′a′);

S′();

}

elseif(lookahead==′(′)

{

match(′(′);

T();

if(lookahead==′)′)

match(′)′);

elseerror();

}第112頁(yè)

voidS′()

{

if(lookahead==′+′)

{

match(′+′);

S();

}

}

voidT()

{

S();

T′();

}第113頁(yè)

voidT′?()

{

if(lookahead==′,′)

{

match(′,′);

S();

T′?();

}

}第114頁(yè)

對(duì)于文法G[S]中產(chǎn)生式：T→T,S|S，即將非終止符T由下面正規(guī)表示式定義：

T→S{,S}

然后將其用狀態(tài)轉(zhuǎn)換圖表示為圖3-10。

這個(gè)狀態(tài)轉(zhuǎn)換圖作用就如同一個(gè)遞歸過(guò)程(函數(shù))，并借助于這種轉(zhuǎn)換圖來(lái)得到遞歸過(guò)程(函數(shù))下降分析器。所以，前面遞歸下降分析器程序可刪除函數(shù)T(?)和T'(?)，而將T(?)和T'(?)改為第115頁(yè)圖3-10非終止符T狀態(tài)轉(zhuǎn)換圖第116頁(yè)

voidT(?)

{

S(?);

while(lookahead==‘,’)

{

match(‘,’);

S(?);

}

}第117頁(yè)

3.10已知文法G[A]:A→aABl?|?a

B→Bb?|?d

(1)試給出與G[A]等價(jià)LL(1)文法G′[A]；

(2)結(jié)構(gòu)G[A′]LL(1)分析表；

(3)給出輸入串a(chǎn)adl#分析過(guò)程。

【解答】(1)文法G[A]存在左遞歸和回溯，故其不是LL(1)文法。要將G[A]改造為L(zhǎng)L(1)文法，首先要消除文法左遞歸，即將形如P→Pα|β產(chǎn)生式改造為

P→βP′

P→αP′|ε第118頁(yè)來(lái)消除左遞歸。由此，將產(chǎn)生式B→Bb?|?d改造為

B→dB′

B′→bB′|ε

其次，應(yīng)經(jīng)過(guò)提取公共左因子方法來(lái)消除G[A]中回溯，即將產(chǎn)生式A→aABl?|?a改造為

A→aA′

A′→ABl|ε

最終得到改造后文法為

G′[A]：??A→aA′

A′→ABl|ε

B→dB′

B′→bB′|ε第119頁(yè)

求得：

FIRST(A)={a}FIRST(A′)={a,ε}

FIRST(B)=7fryag2FIRST(B′)={b,ε}

對(duì)文法開(kāi)始符號(hào)A，有FOLLOW(A)={#}。

由A′→ABl得FIRST(B)\{ε}

FOLLOW(A)，

即FOLLOW(A)={#,d}；

由A′→ABl得FIRST(′l′)FOLLOW(B)，即FOLLOW(B)={l}；第120頁(yè)

由A→aA′得FOLLOW(A)FOLLOW(A′)，即FOLLOW(A′)={#,d}；

由B→dB′得FOLLOW(B)FOLLOW(B′)，即FOLLOW(B′)={l}。

對(duì)A′→ABl來(lái)說(shuō)，F(xiàn)IRST(A)∩FOLLOW(A′)={a}∩{#,d}=Φ，所以文法G′[A]為所求等價(jià)LL(1)文法。第121頁(yè)

(2)結(jié)構(gòu)預(yù)測(cè)分析表方法以下：

①對(duì)文法G′[A]每個(gè)產(chǎn)生式A→α執(zhí)行②、③步。

②對(duì)每個(gè)終止符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α為含有首字符a候選式或?yàn)槲ㄒ缓蜻x式。

③若ε∈FIRST(A)，則對(duì)任何屬于FOLLOW(A)終止符b，將A→ε加入到M[A,b]中。把全部沒(méi)有定義M[A,a]標(biāo)識(shí)上“犯錯(cuò)”。

由此得到G′[A]預(yù)測(cè)分析表，見(jiàn)表3-1。

(3)輸入串a(chǎn)adl分析過(guò)程見(jiàn)表3-2。第122頁(yè)表3-1預(yù)?測(cè)?分?析?表

第123頁(yè)表3-2輸入串a(chǎn)adl分析過(guò)程

第124頁(yè)

3.11將下述文法改造為L(zhǎng)L(1)文法：

G[V]:?V→N|N[E]

E→V|V+E

N→i

【解答】LL(1)文法基本條件是不含左遞歸和回溯(公共左因子)，而文法G[V]中含有回溯，所以先消除回溯，得到文法G′[V]：

G′[V]：V→NV′

V′→ε|[E]

E→VE′

E′→ε|+E

N→i第125頁(yè)一個(gè)LL(1)文法充要條件是：對(duì)每一個(gè)終止符A任何兩個(gè)不一樣產(chǎn)生式A→α?|?β有下面條件成立：

(1)?FIRST(α)∩FIRST(β)=Φ；

(2)?假若β→ε，則有FIRST(α)∩FOLLOW(A)=Φ。

即求出G′[V]FIRST和FOLLOW集以下：

FIRST(N)=FIRST(V)=FIRST(E)={i}

FIRST(V′)={[,ε}

FIRST(E′)={+,ε}

FOLLOW(V)={#}第126頁(yè)

由V′→…E]得FIRST(‘]’)FOLLOW(E)，即FOLLOW(E)={]}；

由V→NV′得FIRST(V′)\{ε}FOLLOW(N)，即FOLLOW(N)={[}；

由E→VE′得FIRST(E′)\{ε}

FOLLOW(V)，即FOLLOW(V)={#,+}；

由V→NV′得FOLLOW(V)FOLLOW(V′)，即FOLLOW(V′)={#,+}；

由V→NV′且V′→ε得FOLLOW(V)FOLLOW(N)，

即FOLLOW(N)={[,#,+}；

由E→VE′得FOLLOW(E)FOLLOW(E′)，即FOLLOW(E′)={]}；第127頁(yè)則，對(duì)V′→ε|[E]有：FIRST(ε)∩FIRST(′[′)=Φ；

對(duì)E′→ε|+E有：FIRST(ε)∩FIRST(′+′)=Φ；

對(duì)V′→ε|[E]有：FIRST('[')∩FOLLOW(V′)={[}∩{#,+}=Φ；

對(duì)E′→ε|+E有：FIRST('+')∩FOLLOW(E′)={+}∩{]}=Φ。

故文法G′[V]為L(zhǎng)L(1)文法。第128頁(yè)

3.12對(duì)文法G[E]:E→E+T?|?T

T→T*P?|?P

P→i

(1)結(jié)構(gòu)該文法優(yōu)先關(guān)系表(不考慮語(yǔ)句括號(hào)#)，并指出此文法是否為算符優(yōu)先文法；

(2)結(jié)構(gòu)文法G[E]優(yōu)先函數(shù)。第129頁(yè)

【解答】(1)?FIRSTVT集結(jié)構(gòu)方法：

①由P→a…或P→Qa…，則a∈FIRSTVT(P)。

②若a∈FIRSTVT(Q)，且P→Q…，則a∈FIRSTVT(P)，也即FIRSTVT(Q)

FIRSTVT(P)。

由①得：由E→E+…得FIRSTVT(E)={+}；

由T→T*…得FIRSTVT(T)={*}；

由P→i得FIRSTVT(P)={i}。

由②得：由T→P得FIRSTVT(P)

FIRSTVT(T)，即FIRSTVT(T)={*，i}；

由E→T得FIRSTVT(T)

FIRSTVT(E)，即FIRSTVT(E)={+，*，i}。第130頁(yè)

LASTVT集結(jié)構(gòu)方法：

①由P→…a或P→…aQ,則a∈LASTVT(P)。

②若a∈LASTVT(Q)，且P→…Q，則a∈LASTVT(P)，也即LASTVT(Q)

LASTVT(P)。

由①得：E→…+T，得LASTVT(E)={+}；

T→…*P，得LASTVT(T)={*}；

P→i，得LASTVT(P)={i}。第131頁(yè)由②得：由T→P得LASTVT(P)

LASTVT(T)，即LASTVT(T)={*，i}；

由E→T得LASTVT(T)

LASTVT(E)，即LASTVT(E)={+，*，i}。

優(yōu)先關(guān)系表結(jié)構(gòu)方法：

①對(duì)P→…ab…或P→…aQb…，有ab；

②對(duì)P→…aR…而b∈FIRSTVT(R)，有a?b；

③對(duì)P→…Rb…而a∈LASTVT(R)，有a?b。

解之無(wú)①。第132頁(yè)由②得：E→…+T，即+?FIRSTVT(T)，有+?*，+?i；

T→…*P，即*?FIRSTVT(P)，有*?i。

由③得：E→E+…，即LASTVT(E)?+，有+?+，*?+，i?+；

T→T*…，即LASTVT(T)?*，有*?*，i?*。

得到優(yōu)先關(guān)系表見(jiàn)表3-3。

因?yàn)樵撐姆ㄈ魏萎a(chǎn)生式右部都不含兩個(gè)相繼并列非終止符，故屬算符文法，且該文法中任何終止符對(duì)(見(jiàn)優(yōu)先關(guān)系表)至多滿足、??和??三種關(guān)系之一，因而是算符優(yōu)先文法。第133頁(yè)表3-3習(xí)題3.12優(yōu)先關(guān)系表

第134頁(yè)

(2)用關(guān)系圖結(jié)構(gòu)優(yōu)先函數(shù)方法是：對(duì)全部終止符a用有下腳標(biāo)fa、ga為結(jié)點(diǎn)名畫出全部終止符所對(duì)應(yīng)結(jié)點(diǎn)。若存在優(yōu)先關(guān)系a?b或ab，則畫一條從fa到ga有向??；若a?b或ab，則畫一條從gb到fa有向弧。最終，對(duì)每個(gè)結(jié)點(diǎn)都賦一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能抵達(dá)結(jié)點(diǎn)(包含出發(fā)結(jié)點(diǎn))個(gè)數(shù)，賦給fa數(shù)作為f(a)，賦給gb數(shù)作為g(b)。用關(guān)系圖法結(jié)構(gòu)本題優(yōu)先函數(shù)，如圖3-11所表示。

得到優(yōu)先函數(shù)見(jiàn)表3-4。第135頁(yè)圖3-11習(xí)題3.1第136頁(yè)表3-4習(xí)題3.12優(yōu)先函數(shù)表第137頁(yè)該優(yōu)先函數(shù)表經(jīng)檢驗(yàn)與優(yōu)先關(guān)系表沒(méi)有矛盾，故為所求優(yōu)先函數(shù)。

也可由定義直接結(jié)構(gòu)優(yōu)先函數(shù)，其方法是：對(duì)每個(gè)終止符a，令f(a)=g(a)=1；假如a?b，而f(a)≤g(b)，則令f(a)=g(b)+1；假如a?b，而f(a)≥g(b)，則令g(b)=f(a)+1；假如ab，而f(a)≠g(b)，則令min{f(a),g(b)}=max{f(a),g(b)}。重復(fù)上述過(guò)程，直到每個(gè)終止符函數(shù)值不再改變?yōu)橹埂＜偃缬幸粋€(gè)函數(shù)值大于2n(n為終止符個(gè)數(shù))，則不存在優(yōu)先函數(shù)。

優(yōu)先函數(shù)計(jì)算過(guò)程如表3-5所表示。第138頁(yè)表3-5優(yōu)先函數(shù)計(jì)算過(guò)程

第139頁(yè)

3.13設(shè)有文法G[S]:S→a?|?b?|?(A)

A→SdA?|?S

(1)結(jié)構(gòu)算符優(yōu)先關(guān)系表；

(2)給出句型(SdSdS)短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)；

(3)給出輸入串(adb)#分析過(guò)程。第140頁(yè)

【解答】(1)先求文法G[S]FIRSTVT集和LASTVT集：

由S→a?|?b?|?(A)得FIRSTVT(S)={a,b,(}；

由A→Sd…得FIRSTVT(A)=u8q8ovd，又由A→S…得FIRSTVT(S)

FIRSTVT(A)，即FIRSTVT(A)={d,a,b,(}；

由S→a?|?b?|?(A)得LASTVT(S)={a,b,)}；

由A→…dA得LASTVT(A)=kmtxioq，又由A→S得LASTVT(S)

LASTVT(A)，即LASTVT(A)={d,a,b,)}。第141頁(yè)結(jié)構(gòu)優(yōu)先關(guān)系表方法以下：

①對(duì)P→…ab…或P→…aQb…，有ab；

②對(duì)P→…aR…而b∈FIRSTVT(R)，有a?b；

③對(duì)P→…Rb…而a∈FIRSTVT(R)，有a?b。

由此得到：

①由S→(A)得()；

②由S→(A…得(?FIRSTVT(A)，即(?d,(?a,(?b,(?(；

由A→…dA得d?FIRSTVT(A)，即d?d,d?a,d?b,d?(；第142頁(yè)③由S→…A)得LASTVT(A)?)，即d?),a?),b?),)?)；

由A→Sd…得LASTVT(S)?d，即a?d,b?d,)?d；

另外，由?#S#得##；

由#?FIRSTVT(S)得#?a,#?b,#?(；

由LASTVT(S)?#得a?#,b?#,)?#。

最終得到算符優(yōu)先關(guān)系表，見(jiàn)表3-6。

由表3-6能夠看出，任何兩個(gè)終止符之間至多只滿足、?、?三種優(yōu)先關(guān)系之一，故G[S]為算符優(yōu)先文法。第143頁(yè)表3-6習(xí)題3.13算符優(yōu)先關(guān)系表

第144頁(yè) (2)為求出句型(SdSdS)短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄，我們先畫出該句型對(duì)應(yīng)語(yǔ)法樹(shù)，如圖3-12所表示。

由圖3-12得到：

短語(yǔ)：S，SdS，SdSdS，(SdSdS)

簡(jiǎn)單短語(yǔ)(即直接短語(yǔ))：S

句柄(即最左直接短語(yǔ))：S

能夠經(jīng)過(guò)分析圖3-12所表示語(yǔ)法樹(shù)來(lái)求素短語(yǔ)和最左素短語(yǔ)，即找出語(yǔ)法樹(shù)中全部相鄰終止符(中間可有一個(gè)非終止符)之間優(yōu)先關(guān)系。確定優(yōu)先關(guān)系標(biāo)準(zhǔn)是：第145頁(yè)圖3-12句型(SdSdS)語(yǔ)法樹(shù)

第146頁(yè) ①同層優(yōu)先關(guān)系為；

②不一樣層時(shí)，層次離樹(shù)根遠(yuǎn)者優(yōu)先級(jí)高，層次離樹(shù)根近者優(yōu)先級(jí)低(恰好驗(yàn)證了優(yōu)先關(guān)系表結(jié)構(gòu)算法)；

③在句型ω兩側(cè)加上語(yǔ)句括號(hào)“#”，即#ω#，則有#?ω和ω?#，由此我們得到句型(SdSdS)優(yōu)先關(guān)系如圖3-13所表示。

注意，句型中素短語(yǔ)含有以下形式：第147頁(yè)圖3-13句型(SdSdS)優(yōu)先關(guān)系第148頁(yè)而最左素短語(yǔ)就是該句型中所找到最左邊那個(gè)素短語(yǔ)，即最左素短語(yǔ)必須具備三個(gè)條件：

①最少包含一個(gè)終止符(是否包含非終止符則按短語(yǔ)要求確定)；

②除本身外不得包含其它素短語(yǔ)(最小性)；

③在句型中含有最左性。

所以，由圖3-13得到SdS為句型(SdSdS)素短語(yǔ)，它同時(shí)也是該句型最左素短語(yǔ)。

(3)輸入串(adb)#分析過(guò)程見(jiàn)表3-7。

為便于分析，同時(shí)給出了(adb)#語(yǔ)法樹(shù)，如圖3-14所表示。第149頁(yè)表3-7輸入串(adb)#分析過(guò)程

第150頁(yè)圖3-14(adb)語(yǔ)法樹(shù)第151頁(yè)

3.14在算符優(yōu)先分析法中，為何要在找到最左素短語(yǔ)尾時(shí)才返回來(lái)確定其對(duì)應(yīng)頭？能否按掃描次序先找到頭后再找到對(duì)應(yīng)尾，為何？

【解答】設(shè)句型普通形式為N1a1N2a2…NnanNn+1。其中，每個(gè)ai都是終止符，而Ni則是可有可無(wú)非終止符。對(duì)上述句型能夠找出該句型中全部素短語(yǔ)，每個(gè)素短語(yǔ)都含有以下形式：第152頁(yè)假如某句型得到優(yōu)先關(guān)系以下：

則當(dāng)從左至右掃描到第一個(gè)“?”時(shí)，再由此從右至左掃描到第一個(gè)“?”，它們之間(當(dāng)然不包含第一個(gè)“?”前一個(gè)終止符和第一個(gè)“?”后一個(gè)終止符)即為最左素短語(yǔ)。第153頁(yè)假如由左至右掃描到第一個(gè)“?”，能夠看出這并不一定是最左素短語(yǔ)開(kāi)頭，因?yàn)橛伤_(kāi)始并不一定是素短語(yǔ)(在其內(nèi)部還可能包含其它更小素短語(yǔ))。所以，在算符優(yōu)先分析算法中，只有先找到最左素短語(yǔ)尾(即“?”)，才返回來(lái)確定與其對(duì)應(yīng)頭(即“?”)；而不能按掃描次序先找到頭然后再找到對(duì)應(yīng)尾。第154頁(yè)

3.15試證實(shí)在算符文法中，任何句型都不包含兩個(gè)相鄰非終止符。

【解答】設(shè)文法G[S]=(VT,VN,S,ξ)，其中VT是終止符集；VN是非終止符集；ξ為產(chǎn)生式集合；S是開(kāi)始符號(hào)。

對(duì)句型推導(dǎo)長(zhǎng)度n作以下歸納：

(1)當(dāng)n=1時(shí)，S?α，則存在一條產(chǎn)生式S→α屬于ε，其中a∈(VT∪VN)*。因?yàn)槲姆ㄊ撬惴姆?，所以α中沒(méi)