編譯原理習(xí)題及答案1～3

章詞法分析章語法分析2021/6/271

第一章緒論

1.1完成下列選擇題：

(1)下面敘述中正確的是

。

A．編譯程序是將高級語言程序翻譯成等價的機(jī)器語言程序的程序

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

C．匯編語言是計算機(jī)唯一能夠直接識別并接受的語言

D．高級語言接近人們的自然語言，但其依賴具體機(jī)器的特性是無法改變的2021/6/272

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

。

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

B．使程序的結(jié)構(gòu)更加清晰

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

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

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

。

A．源程序 B．目標(biāo)語言

C．編譯方法 D．A～C項2021/6/273

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

上。

A．出錯處理 B．詞法分析

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

(5)編譯程序是對

。

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

C．機(jī)器語言的執(zhí)行D．高級語言的翻譯2021/6/274

【解答】

(1)編譯程序可以將用高級語言編寫的源程序轉(zhuǎn)換成與之在邏輯上等價的目標(biāo)程序，而目標(biāo)程序可以是匯編語言程序或機(jī)器語言程序。故選A。

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

(3)構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語言和編譯方法這三方面內(nèi)容。故選D。2021/6/275

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

(5)由(1)可知，編譯程序?qū)嶋H上實現(xiàn)了對高級語言程序的翻譯。故選D。2021/6/276

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

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

在解釋方式下，翻譯程序事先并不采用將高級語言程序全部翻譯成機(jī)器代碼程序，然后執(zhí)行這個機(jī)器代碼程序的方法，而是每讀入一條源程序的語句，就將其解釋(翻譯)成對應(yīng)其功能的機(jī)器代碼語句串并執(zhí)行，然后再讀入下一條源程序語句并解釋執(zhí)行，而所翻譯的機(jī)器代碼語句串在該語句執(zhí)行后并不保留。這種方法是按源程序中語句的動態(tài)執(zhí)行順序逐句解釋(翻譯)執(zhí)行的，如果一語句處于一循環(huán)體中，則每次循環(huán)執(zhí)行到該語句時，都要將其翻譯成機(jī)器代碼后再執(zhí)行。2021/6/277

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

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

這兩種途徑的主要區(qū)別在于：解釋方式下不生成目標(biāo)代碼程序，而編譯方式下生成目標(biāo)代碼程序。2021/6/278

1.3請畫出編譯程序的總框圖。如果你是一個編譯程序的總設(shè)計師，設(shè)計編譯程序時應(yīng)當(dāng)考慮哪些問題？

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

作為一個編譯程序的總設(shè)計師，首先要深刻理解被編譯的源語言其語法及語義；其次，要充分掌握目標(biāo)指令的功能及特點，如果目標(biāo)語言是機(jī)器指令，還要搞清楚機(jī)器的硬件結(jié)構(gòu)以及操作系統(tǒng)的功能；第三，對編譯的方法及使用的軟件工具也必須準(zhǔn)確化。總之，總設(shè)計師在設(shè)計編譯程序時必須估量系統(tǒng)功能要求、硬件設(shè)備及軟件工具等諸因素對編譯程序構(gòu)造的影響。2021/6/279圖1-1編譯程序總框圖2021/6/2710第二章詞法分析

2.1完成下列選擇題：

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

。

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

C．語法規(guī)則 D．等價變換規(guī)則

(2)詞法分析器的輸入是

。

A．單詞符號串 B．源程序

C．語法單位 D．目標(biāo)程序2021/6/2711

(3)詞法分析器的輸出是

。

A．單詞的種別編碼

B．單詞的種別編碼和自身的值

C．單詞在符號表中的位置

D．單詞自身值

(4)狀態(tài)轉(zhuǎn)換圖(見圖2-1)接受的字集為_______。

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

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

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

D．含偶數(shù)個0的二進(jìn)制數(shù)組成的集合2021/6/2712圖2-1習(xí)題2.1的DFAM2021/6/2713

(5)對于任一給定的NFAM，

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

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

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

(6)?DFA適用于

。

A．定理證明 B．語法分析

C．詞法分析 D．語義加工2021/6/2714

(7)下面用正規(guī)表達(dá)式描述詞法的論述中，不正確的是

。

A．詞法規(guī)則簡單，采用正規(guī)表達(dá)式已足以描述

B．正規(guī)表達(dá)式的表示比上下文無關(guān)文法更加簡潔、直觀和易于理解

C．正規(guī)表達(dá)式描述能力強于上下文無關(guān)文法

D．有限自動機(jī)的構(gòu)造比下推自動機(jī)簡單且分析效率高

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

。

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

C．(ab)*(a|b)* D．(a|b)*2021/6/2715

【解答】

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

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

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

(4)雖然選項A、B、D都滿足題意，但選項D更準(zhǔn)確。故選D。2021/6/2716

(5)?NFA可以有DFA與之等價，即兩者描述能力相同；也即，對于任一給定的NFAM，一定存在一個DFAM'，使L(M)=L(M′)。故選B。

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

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

(8)由于正則閉包R+=R*R=RR*，故(a|b)*(a|b)=(a|b)(a|b)*。故選A。2021/6/2717

2.2什么是掃描器？掃描器的功能是什么？

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

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

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

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

試構(gòu)造相應(yīng)的確定有限自動機(jī)M′。

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

先畫出NFAM相應(yīng)的狀態(tài)圖，如圖2-2所示。2021/6/2719圖2-2習(xí)題2.3的NFAM

2021/6/2720

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

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

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

2021/6/2721

將圖2-3所示的DFAM′最小化。首先，將M′的狀態(tài)分成終態(tài)組{1,2}與非終態(tài)組{0}。其次，考察{1,2}。由于{1,2}a={1,2}b={2}

{1,2}，因此不再將其劃分了，也即整個劃分只有兩組：{0}和{1,2}。令狀態(tài)1代表{1,2}，即把原來到達(dá)2的弧都導(dǎo)向1，并刪除狀態(tài)2。最后，得到如圖2-4所示的化簡了的DFAM′。圖2-3習(xí)題2.3的DFAM′其狀態(tài)轉(zhuǎn)換圖如圖2-3所示。2021/6/2722圖2-4圖2-3化簡后的DFAM′

2021/6/2723

2.4正規(guī)式(ab)*a與正規(guī)式a(ba)*是否等價？請說明理由。

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

用子集法將圖2-5和圖2-6分別確定化為如圖2-7(a)和(b)所示的狀態(tài)轉(zhuǎn)換矩陣，它們最終都可以得到最簡DFA，如圖2-8所示。因此，這兩個正規(guī)式等價。2021/6/2724圖2-5正規(guī)式(ab)*a對應(yīng)的NFA2021/6/2725圖2-6正規(guī)式a(ba)*對應(yīng)的NFA2021/6/2726圖2-7圖2-5和圖2-6確定化后的狀態(tài)轉(zhuǎn)換矩陣

—2021/6/2727圖2-8最簡DFA

2021/6/2728

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

2021/6/2730

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

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

(1)給出描述該語言的正規(guī)表達(dá)式；

(2)構(gòu)造識別該語言的確定有限自動機(jī)(可直接用狀態(tài)圖形式給出)。

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

2021/6/2731圖2-10習(xí)題2.5的NFA2021/6/2732用子集法將圖2-10確定化，如圖2-11所示。

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

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

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

2021/6/2733

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

2021/6/2734

2.6有語言L={w?|?w∈(0,1)+，并且w中至少有兩個1，又在任何兩個1之間有偶數(shù)個0}，試構(gòu)造接受該語言的確定有限狀態(tài)自動機(jī)(DFA)。

【解答】對于語言L，w中至少有兩個1，且任意兩個1之間必須有偶數(shù)個0；也即在第一個1之前和最后一個1之后，對0的個數(shù)沒有要求。據(jù)此我們求出L的正規(guī)式為0*1(00(00)*1)*00(00)*10*，畫出與正規(guī)式對應(yīng)的NFA，如圖2-13所示。2021/6/2735圖2-13習(xí)題2.6的NFA2021/6/2736

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

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

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

2021/6/2737按順序重新命名為0、1、2、3、4、5、6，則得到最簡DFA，如圖2-15所示。圖2-15習(xí)題2.6的最簡DFA2021/6/2738

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

(1)試用有限自動機(jī)的等價性證明這兩個正規(guī)式是等價的；

(2)給出相應(yīng)的正規(guī)文法。

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

用子集法將圖2-16所示的NFA確定化為DFA，如圖2-17所示。2021/6/2739圖2-16正規(guī)式((a?|?b)*|aa)*b對應(yīng)的NFA

2021/6/2740圖2-17圖2-16確定化后的狀態(tài)轉(zhuǎn)換矩陣2021/6/2741

由于對非終態(tài)的狀態(tài)1、2來說，它們輸入a、b的下一狀態(tài)是一樣的，故狀態(tài)1和狀態(tài)2可以合并，將合并后的終態(tài)3命名為2，則得到表2-3(注意，終態(tài)和非終態(tài)即使輸入a、b的下一狀態(tài)相同也不能合并)。

由此得到最簡DFA，如圖2-18所示。

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

用子集法將圖2-19所示的NFA確定化為如圖2-20所示的狀態(tài)轉(zhuǎn)換矩陣。2021/6/2742表2-3合并后的狀態(tài)轉(zhuǎn)換矩陣

2021/6/2743圖2-18習(xí)題2.7的最簡DFA2021/6/2744圖2-19正規(guī)式(a?|?b)*b對應(yīng)的NFA2021/6/2745

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

2021/6/27462.8構(gòu)造一個DFA，它接收Σ

={a,b}上所有不含abb的字符串。

解：Σ

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

2021/6/27472.9構(gòu)造一個DFA，它接收Σ

={a,b}上所有含偶數(shù)個a的字符串。

解：Σ

={a,b}上所有含偶數(shù)個a的字符串可表示為(b|ab*a)*2021/6/2748

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

I=1;

while(I<=n)

{

sun=sun+a[I];

I=I+1;

}

請用正規(guī)表達(dá)式表示這個程序段可能的執(zhí)行序列。

【解答】用正規(guī)表達(dá)式表示程序段可能的執(zhí)行序列為AT(BIT)*。2021/6/2749

2.9將圖2-21所示的非確定有限自動機(jī)(NFA)變換成等價的確定有限自動機(jī)(DFA)。

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

【解答】用子集法將NFA確定化，如圖2-22所示。2021/6/2750圖2-21習(xí)題2.9的NFA2021/6/2751圖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}2021/6/2752

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

對圖2-23所示的DFA進(jìn)行最小化。首先將狀態(tài)分為非終態(tài)集和終態(tài)集兩部分：{0,1,2,5}和{3,4,6,7}。由終態(tài)集可知，對于狀態(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}

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

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

按順序重新命名為0、1、2、3、4、5，得到最簡DFA如圖2-24所示。2021/6/2753圖2-23習(xí)題2.9的DFA2021/6/2754

圖2-24習(xí)題2.9的最簡DFA2021/6/2755

2.10有一臺自動售貨機(jī)，接收1分和2分硬幣，出售3分錢一塊的硬糖。顧客每次向機(jī)器中投放大于等于3分的硬幣，便可得到一塊糖(注意：只給一塊并且不找錢)。

(1)寫出售貨機(jī)售糖的正規(guī)表達(dá)式；

(2)構(gòu)造識別上述正規(guī)式的最簡DFA。

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

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

用子集法將圖2-25所示的NFA確定化，如圖2-26所示。2021/6/2756圖2-25習(xí)題2.10的NFA2021/6/2757

由圖2-26可看出，非終態(tài)2和非終態(tài)3面對輸入符號a或b的下一狀態(tài)相同，故合并為一個狀態(tài)，即最簡狀態(tài){0}、{1}、{2，3}、{4}。圖2-26習(xí)題2.10的狀態(tài)轉(zhuǎn)換矩陣2021/6/2758

按順序重新命名為0、1、2、3，則得到最簡DFA，如圖2-27所示。圖2-27習(xí)題2.10的最簡DFA2021/6/2759第三章語法分析

3.1完成下列選擇題：

(1)程序語言的語義需要

用來描述。

A．上下文無關(guān)文法B．上下文有關(guān)文法

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

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

。

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

C．下推自動機(jī) D．線性界限自動機(jī)2021/6/2760

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

是正確的。

A．1型語言

0型語言 B．2型語言

1型語言

C．3型語言

2型語言 D．A～C均不成立

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

A．上下文無關(guān)文法 B．上下文有關(guān)文法

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

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

。

A．xyx B．(xyx)*

C．xnyxn(n≥0) D．x*yx*2021/6/2761

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

。

A．子樹的末端結(jié)點(即樹葉)組成的符號串

B．簡單子樹的末端結(jié)點組成的符號串

C．最左簡單子樹的末端結(jié)點組成的符號串

D．最左簡單子樹的末端結(jié)點組成的符號串且該符號串必須含有終結(jié)符2021/6/2762

(7)下面對語法樹錯誤的描述是

。

A．根結(jié)點用文法G[S]的開始符S標(biāo)記

B．每個結(jié)點用G[S]的一個終結(jié)符或非終結(jié)符標(biāo)記

C．如果某結(jié)點標(biāo)記為ε，則它必為葉結(jié)點

D．內(nèi)部結(jié)點可以是非終結(jié)符

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

。

A．短語B．句柄 C．句型 D．句子2021/6/2763

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

A→a|b

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

。

A．S

SA

SAA

AAA

aAA

abA

aba

B．S

SA

SAA

AAA

AAa

Aba

aba

C．S

SA

SAA

SAa

Sba

Aba

aba

D．S

SA

Sa

SAa

Sba

Aba

aba

2021/6/2764

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

。

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

B．最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同

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

D．可能存在兩個不同的最右推導(dǎo)，但它們對應(yīng)的語法樹相同

(11)一個句型的分析樹代表了該句型的

。

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

C．生成過程 D．翻譯過程2021/6/2765

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

定義。

A．直接短語 B．最右直接短語

C．最左直接短語 D．最左素短語

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

。

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

C．規(guī)范推導(dǎo) D．最左歸約的逆過程2021/6/2766

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

A→AaB|c

B→bScA|b

則句型aAcbBdcc的短語是

。

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的句柄和最左素短語是

。

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

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

2021/6/2767

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

。

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

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

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

S→S*F|F

F→(E)|i

則FIRST(S)=

。

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

C．{i} D．{(,)}2021/6/2768

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

。

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

C．無回溯 D．A～C項

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

。

A．一個終結(jié)符B．一個非終結(jié)符

C．多個終結(jié)符D．多個非終結(jié)符

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

。

A．FIRST和FOLLOWB．FIRSTVT和FOLLOW

C．FIRST和LASTVTD．FIRSTVT和LASTVT2021/6/2769

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

。

A．必有ac B．必有ca

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

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

。

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

B．文法不存在…QR…的句型且任何終結(jié)符對(a,b)至多滿足ab、a?b和a?b三種關(guān)系之一2021/6/2770

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

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

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

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

A．有一個 B．沒有

C．有若干個 D．可能有若干個

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

來刻畫可歸約串。

A．句柄 B．直接短語

C．素短語 D．最左素短語2021/6/2771

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

。

A．至少包含一個終結(jié)符

B．至少包含一個非終結(jié)符

C．除自身外不再包含其他素短語

D．在句型中具有最左性

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

T→T，S|S

其FIRSTVT(T)為

。

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

C．{，,b,∧,(} D．{，,b,∧,)}2021/6/2772

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

T→T+i|i

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

。

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

(28)下述FOLLOW集構(gòu)造方法中錯誤的是

。

A．對文法開始符S有#∈FOLLOW(S)

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

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

D．若有A→αB，則有FOLLOW(A)FOLLOW(B)2021/6/2773

(29)若文法G[S]的產(chǎn)生式有…AB…出現(xiàn)，則對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ù)測分析法 B．遞歸下降分析法

C．LL(1)分析法 D．算符優(yōu)先分析法2021/6/2774

(31)下面

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

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

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

(32)一個

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

A．活前綴 B．前綴

C．項目 D．項目集

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

項目。

A．接受 B．歸約

C．移進(jìn) D．待約2021/6/2775

(34)在LR(0)的ACTION子表中，如果某一行中存在標(biāo)記為“rj”的欄，則

。

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

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

(35)?LR分析法解決“移進(jìn)—歸約”沖突時，左結(jié)合意味著

。

A．打斷聯(lián)系實行移進(jìn) B．打斷聯(lián)系實行歸約

C．建立聯(lián)系實行移進(jìn) D．建立聯(lián)系實行歸約2021/6/2776

(36)?LR分析法解決“移進(jìn)—歸約”沖突時，右結(jié)合意味著

。

A．打斷聯(lián)系實行歸約 B．建立聯(lián)系實行歸約

C．建立聯(lián)系實行移進(jìn) D．打斷聯(lián)系實行移進(jìn)2021/6/2777

【解答】

(1)參見第四章4.1.1節(jié)，語義分析不像詞法分析和語法分析那樣可以分別用正規(guī)文法和上下文無關(guān)文法描述，由于語義是上下文有關(guān)的，因此語義分析須用上下文有關(guān)文法描述。即選B。

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

(3)由于不存在：3型語言

2型語言

1型語言

0型語言。故選D。

(4)3型文法即正規(guī)文法，它的識別系統(tǒng)是有限狀態(tài)自動機(jī)。故選C。2021/6/2778

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

(6)最左簡單子樹的末端結(jié)點組成的符號串為句柄。故選C。

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

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

(9)規(guī)范推導(dǎo)即最右推導(dǎo)，也即每一步推導(dǎo)都是對句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換。故選D。2021/6/2779

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

(11)一個句型的分析樹代表了該句型的歸約過程。故選B。

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

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

(14)由圖3-1可知應(yīng)選A。2021/6/2780圖3-1句型aAcbBdcc對應(yīng)的語法樹2021/6/2781

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

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

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

FIRST(S)，即FIRST(S)={(,i}。故選B。

(18)左遞歸和二義性將無法實現(xiàn)自頂向下分析，回溯則使自頂向下分析效率下降。故選D。2021/6/2782圖3-2句型P+T+i對應(yīng)的語法樹及優(yōu)先關(guān)系示意2021/6/2783

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

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

(21)由于ab和bc并不能使選項A、B、C成立。故選D。

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

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

(24)在算符優(yōu)先分析中是以“最左素短語”來刻畫可歸約串的。故選D。2021/6/2784

(25)最左素短語必須具備的三個條件是：①至少包含一個終結(jié)符；②除自身外不得包含其他素短語；③在句型中具有最左性。故選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)，即選項C錯。故選C。

(29)若文法G[S]的產(chǎn)生式有…AB…出現(xiàn)，則有FIRST(B)\{ε}

FOLLOW(A)。故選C。2021/6/2785圖3-3句子1+2*8+6的語法樹及值變化示意2021/6/2786

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

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

(32)在LR分析中，一個項目指明了在分析過程的某個時刻所看到產(chǎn)生式的多大一部分。故選C。

(33)對文法G[S’]，S'→α·稱為“接受”項目；形如A→α·aβ的項目(其中a為終結(jié)符)稱為“移進(jìn)”項目；形如A→α·Bβ的項目(其中B為非終結(jié)符)稱為“待約”項目。故選D。2021/6/2787

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

(35)?LR分析法解決“移進(jìn)—歸約”沖突時，左結(jié)合意味著打斷聯(lián)系而實行歸約，右結(jié)合意味著維持聯(lián)系而實行移進(jìn)。故選B。

(36)由(35)可知應(yīng)選C。2021/6/2788

3.2令文法G[N]為

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

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

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

(2)給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)。2021/6/2789

【解答】

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

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

最右推導(dǎo)：

2021/6/2790

3.3已知文法G[S]為S→aSb?|?Sb?|?b，試證明文法G[S]為二義文法。

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

因此，文法G[S]為二義文法(對句子abbb也可畫出兩棵不同的語法樹)。2021/6/2791圖3-4句子aabbbb對應(yīng)的兩棵不同語法樹2021/6/2792

3.4已知文法G[S]為S→SaS?|?ε，試證明文法G[S]為二義文法。

【解答】由文法G[S]：S→SaS?|?ε，句子aa的語法樹如圖3-5所示。

由圖3-5可知，文法G[S]為二義文法。2021/6/2793圖3-5句子aa對應(yīng)的兩棵不同的語法樹2021/6/2794

3.5按指定類型，給出語言的文法。

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

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

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

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

G[S]：S→aSb?|?Sb?|?b2021/6/2795

(2)為了構(gòu)造字母表Σ={a,b}上同時只有奇數(shù)個a和奇數(shù)個b的所有串集合的正規(guī)式，我們畫出如圖3-6所示的DFA，即由開始符S出發(fā)，經(jīng)過奇數(shù)個a到達(dá)狀態(tài)A，或經(jīng)過奇數(shù)個b到達(dá)狀態(tài)B；而由狀態(tài)A出發(fā)，經(jīng)過奇數(shù)個b到達(dá)狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)經(jīng)過奇數(shù)個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?|?ε2021/6/2796圖3-62021/6/2797

(3)我們用一個非終結(jié)符A代表一個a(即有A→a)，用一個非終結(jié)符B代表一個b(即有B→b)；為了保證a和b的個數(shù)相同，則在出現(xiàn)一個a時應(yīng)相應(yīng)地出現(xiàn)一個B，出現(xiàn)一個b時則相應(yīng)出現(xiàn)一個A。假定已推導(dǎo)出bA，如果下一步要推導(dǎo)出連續(xù)兩個b，則應(yīng)有bA

bbAA。也即為了保證b和A的個數(shù)一致，應(yīng)有A→bAA；同理有B→aBB。此外，為了保證遞歸地推出所要求的ab串，應(yīng)有S→aBS和S→bAS。由此得到無二義文法G[S]為

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

A→bAA?|?a

B→aBB?|?b2021/6/2798

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

A→AaB?|?c

B→bScA?|?b

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

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

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

對樹(a)，直接短語有3個：AaB、b和c，而AaB為最左直接短語(即為句柄)。對樹(b)，直接短語有兩個：Bd和c，而Bd為最左直接短語。2021/6/2799能否不畫出語法樹，而直接由定義(即在句型中)尋找滿足某個產(chǎn)生式的候選式這樣一個最左子串(即句柄)呢？例如，對句型aAaBcbbdcc，我們可以由左至右掃描找到第一個子串AaB，它恰好是滿足A→AaB右部的子串；與樹(a)對照，AaB的確是該句型的句柄。是否這一方法始終正確呢？我們繼續(xù)檢查句型aAcbBdcc，由左至右找到第一個子串c，這是滿足A→c右部的子串，但由樹(b)可知，c不是該句型的句柄。由此可知，畫出對應(yīng)句型的語法樹然后尋找最左直接短語是確定句柄的好方法。2021/6/27100圖3-7習(xí)題3.6的語法樹(a)?aAaBcbbdcc;(b)?aAcbBdcc2021/6/27101

(2)句子acabcbbdcc的最左推導(dǎo)如下：2021/6/27102

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

L→L,S?|?S

(1)畫出句型(S,(a))的語法樹；

(2)寫出上述句型的所有短語、直接短語、句柄、素短語和最左素短語。2021/6/27103

【解答】(1)句型(S,(a))的語法樹如圖3-8所示。

(2)由圖3-8可知：

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

直接短語：a、S；

句柄：S；

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

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

因此，素短語為a。2021/6/27104圖3-8句型(S,(a))的語法樹2021/6/27105

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

G[D]:D→TL

T→int?|?long?|?short

L→id?|?L,id

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

(2)分別以上述文法G[D]和改造后的文法G′[D]為輸入序列inta,b,c構(gòu)造分析樹。2021/6/27106

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

D→TL

T→int?|?long?|?short

L→idL′

L′→,idL′|?ε

(2)未消除左遞歸的文法G(D)和消除左遞歸的文法G′[D]為輸入序列inta,b,c構(gòu)造的分析樹分別如圖3-9的(a)、(b)所示。2021/6/27107圖3-9兩種文法為inta,b,c構(gòu)造的分析樹

(a)文法G(D)；(b)文法G′(D)2021/6/27108

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

T→T,S|S

消除文法的左遞歸及提取公共左因子，然后對每個非終結(jié)符寫出不帶回溯的遞歸子程序。

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

S→(T)|a+S|a

T→ST′

T′→,ST′|ε2021/6/27109

提取公共左因子：

S→(T)|aS′

S′→+S|ε

T→ST′

T′→,ST′|ε2021/6/27110

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

voidmatch(tokent)

{

if(lookahead==t)

lookahead=nexttoken;

elseerror();

}

voidS()2021/6/27111

{

if(lookahead==′a′)

{match(′a′);

S′();

}

elseif(lookahead==′(′)

{

match(′(′);

T();

if(lookahead==′)′)

match(′)′);

elseerror();

}2021/6/27112

voidS′()

{

if(lookahead==′+′)

{

match(′+′);

S();

}

}

voidT()

{

S();

T′();

}2021/6/27113

voidT′?()

{

if(lookahead==′,′)

{

match(′,′);

S();

T′?();

}

}2021/6/27114

對于文法G[S]中的產(chǎn)生式：T→T,S|S，即將非終結(jié)符T由下面的正規(guī)表達(dá)式定義：

T→S{,S}

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

這個狀態(tài)轉(zhuǎn)換圖的作用就如同一個遞歸過程(函數(shù))，并借助于這種轉(zhuǎn)換圖來得到遞歸過程(函數(shù))下降分析器。因此，前面的遞歸下降分析器程序可刪除函數(shù)T(?)和T'(?)，而將T(?)和T'(?)改為2021/6/27115圖3-10非終結(jié)符T的狀態(tài)轉(zhuǎn)換圖2021/6/27116

voidT(?)

{

S(?);

while(lookahead==‘,’)

{

match(‘,’);

S(?);

}

}2021/6/27117

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

B→Bb?|?d

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

(2)構(gòu)造G[A′]的LL(1)分析表；

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

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

P→βP′

P→αP′|ε2021/6/27118來消除左遞歸。由此，將產(chǎn)生式B→Bb?|?d改造為

B→dB′

B′→bB′|ε

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

A→aA′

A′→ABl|ε

最后得到改造后的文法為

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

A′→ABl|ε

B→dB′

B′→bB′|ε2021/6/27119

求得：

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

FIRST(B)=ialhlltFIRST(B′)={b,ε}

對文法開始符號A，有FOLLOW(A)={#}。

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

FOLLOW(A)，

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

由A′→ABl得FIRST(′l′)FOLLOW(B)，即FOLLOW(B)={l}；2021/6/27120

由A→aA′得FOLLOW(A)

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

由B→dB′得FOLLOW(B)

FOLLOW(B′)，即FOLLOW(B′)={l}。

對A′→ABl來說，F(xiàn)IRST(A)∩FOLLOW(A′)={a}∩{#,d}=Φ，所以文法G′[A]為所求等價的LL(1)文法。2021/6/27121

(2)構(gòu)造預(yù)測分析表的方法如下：

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

②對每個終結(jié)符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α為含有首字符a的候選式或為唯一的候選式。

③若ε∈FIRST(A)，則對任何屬于FOLLOW(A)的終結(jié)符b，將A→ε加入到M[A,b]中。把所有無定義的M[A,a]標(biāo)記上“出錯”。

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

(3)輸入串a(chǎn)adl的分析過程見表3-2。2021/6/27122表3-1預(yù)?測?分?析?表

2021/6/27123表3-2輸入串a(chǎn)adl的分析過程

2021/6/27124

3.11將下述文法改造為LL(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→i2021/6/27125一個LL(1)文法的充要條件是：對每一個終結(jié)符A的任何兩個不同產(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)={#}2021/6/27126

由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′)={]}；2021/6/27127則，對V′→ε|[E]有：FIRST(ε)∩FIRST(′[′)=Φ；

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

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

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

故文法G′[V]為LL(1)文法。2021/6/27128

3.12對文法G[E]:E→E+T?|?T

T→T*P?|?P

P→i

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

(2)構(gòu)造文法G[E]的優(yōu)先函數(shù)。2021/6/27129

【解答】(1)?FIRSTVT集構(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}。2021/6/27130

LASTVT集構(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}。2021/6/27131由②得：由T→P得LASTVT(P)

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

由E→T得LASTVT(T)

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

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

①對P→…ab…或P→…aQb…，有ab；

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

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

解之無①。2021/6/27132由②得：E→…+T，即+?FIRSTVT(T)，有+?*，+?i；

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

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

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

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

由于該文法的任何產(chǎn)生式的右部都不含兩個相繼并列的非終結(jié)符，故屬算符文法，且該文法中的任何終結(jié)符對(見優(yōu)先關(guān)系表)至多滿足、??和??三種關(guān)系之一，因而是算符優(yōu)先文法。2021/6/27133表3-3習(xí)題3.12的優(yōu)先關(guān)系表

2021/6/27134

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

得到優(yōu)先函數(shù)見表3-4。2021/6/27135圖3-11習(xí)題3.12021/6/27136表3-4習(xí)題3.12的優(yōu)先函數(shù)表2021/6/27137該優(yōu)先函數(shù)表經(jīng)檢查與優(yōu)先關(guān)系表沒有矛盾，故為所求優(yōu)先函數(shù)。

也可由定義直接構(gòu)造優(yōu)先函數(shù)，其方法是：對每個終結(jié)符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ù)上述過程，直到每個終結(jié)符的函數(shù)值不再變化為止。如果有一個函數(shù)值大于2n(n為終結(jié)符個數(shù))，則不存在優(yōu)先函數(shù)。

優(yōu)先函數(shù)的計算過程如表3-5所示。2021/6/27138表3-5優(yōu)先函數(shù)的計算過程

2021/6/27139

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

A→SdA?|?S

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

(2)給出句型(SdSdS)的短語、簡單短語、句柄、素短語和最左素短語；

(3)給出輸入串(adb)#的分析過程。2021/6/27140

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

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

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

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

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

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

LASTVT(A)，即LASTVT(A)={d,a,b,)}。2021/6/27141構(gòu)造優(yōu)先關(guān)系表方法如下：

①對P→…ab…或P→…aQb…，有ab；

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

③對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?(；2021/6/27142③由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)系表，見表3-6。

由表3-6可以看出，任何兩個終結(jié)符之間至多只滿足、?、?三種優(yōu)先關(guān)系之一，故G[S]為算符優(yōu)先文法。2021/6/27143表3-6習(xí)題3.13的算符優(yōu)先關(guān)系表

2021/6/27144 (2)為求出句型(SdSdS)的短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹