《編譯原理教程》習題解析與上機指導-課件3

第二章詞法分析2.1完成下列選擇題：

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

。

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

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

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

。

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

C．語法單位 D．目標程序

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

。

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

C．單詞在符號表中的位置 D．單詞自身值(4)狀態(tài)轉(zhuǎn)換圖(見圖2-1)接受的字集為_______。

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

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

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

D．含偶數(shù)個0的二進制數(shù)組成的集合

圖2-1習題2.1的DFAM(5)對于任一給定的NFAM，

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

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

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

(6)?DFA適用于

。

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

C．詞法分析 D．語義加工(7)下面用正規(guī)表達式描述詞法的論述中，不正確的是

。

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

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

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

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

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

。

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

C．(ab)*(a|b)* D．(a|b)*(9)在狀態(tài)轉(zhuǎn)換圖的實現(xiàn)中，

一般對應一個循環(huán)語句。

A．不含回路的分叉結(jié)點 B．含回路的狀態(tài)結(jié)點

C．終態(tài)結(jié)點 D．A～C都不是

(10)已知DFAMd=?({s0,?s1,?s2},?{a,?b},?f,?s0,?{s2})，且有：

f(?s0,?a?)?=s1f(?s1,?a?)?=s2

f(?s2,?a?)?=s2f(?s2,?b?)?=s2

則該DFAM所能接受的語言可以用正規(guī)表達式表示為

。

A．(?a∣b?)*

B．a(chǎn)a?(?a∣b?)*

C．(?a∣b?)*aa

D．a(chǎn)?(?a∣b?)*a

【解答】

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

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

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

(4)雖然選項A、B、D都滿足題意，但選項D更準確。故選D。

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

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

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

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

(9)含回路的狀態(tài)結(jié)點一般對應一個循環(huán)語句。故選B。

(10)?DFAMd所對應的DFA如圖2-2所示。故選B。圖2-2DFAM

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

【解答】

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

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

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

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

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

【解答】

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

先畫出NFAM相應的狀態(tài)圖，如圖2-3所示。圖2-3習題2.3的NFAM用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如表2-1所示。表2-1狀態(tài)轉(zhuǎn)換矩陣將轉(zhuǎn)換矩陣中的所有子集重新命名，形成表2-2所示的狀態(tài)轉(zhuǎn)換矩陣，即得到M′=({0,1,2},{a,b},f,0,{1,2})，其狀態(tài)轉(zhuǎn)換圖如圖2-4所示。圖2-4習題2.3的DFAM′表2-2重命名后的狀態(tài)轉(zhuǎn)換矩陣將圖2-4所示的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}，即把原來到達2的弧都導向1，并刪除狀態(tài)2。最后，得到如圖2-5所示的化簡了的DFAM′。圖2-5圖2-3化簡后的DFAM′

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

【解答】

正規(guī)式(ab)*a對應的NFA如圖2-6所示，正規(guī)式a(ba)*對應的NFA如圖2-7所示。圖2-6正規(guī)式(ab)*a對應的NFA圖2-7正規(guī)式a(ba)*對應的NFA用子集法將圖2-6和圖2-7分別確定化為如圖2-8(a)和(b)所示的狀態(tài)轉(zhuǎn)換矩陣，它們最終都可以得到最簡DFA，如圖2-9所示。因此，這兩個正規(guī)式等價。圖2-8圖2-6和圖2-7確定化后的狀態(tài)轉(zhuǎn)換矩陣圖2-9最簡DFA實際上，當閉包*取0時，正規(guī)式(ab)*a與正規(guī)式a(ba)*由初態(tài)X到終態(tài)Y之間僅存在一條a弧。由于(ab)*在a之前，故描述(ab)*的弧應在初態(tài)結(jié)點X上；而(ba)*在a之后，故(ba)*對應的弧應在終態(tài)結(jié)點Y上。因此，(ab)*a和a(ba)*所對應的NFA也可分別描述為如圖2-10(a)和(b)所示的形式，它們確定化并化簡后仍可得到圖2-9所示的最簡DFA。圖2-10(ab)*a和a(ba)*分別對應的NFA

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

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

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

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

【解答】

該語言對應的正規(guī)表達式為a(aa)*bb(bb)*a(aa)*，正規(guī)表達式對應的NFA如圖2-11所示。圖2-11習題2.5的NFA用子集法將圖2-11確定化，如圖2-12所示。圖2-12習題2.5的狀態(tài)轉(zhuǎn)換矩陣由圖2-12重新命名后的狀態(tài)轉(zhuǎn)換矩陣可以看出：狀態(tài)0和狀態(tài)2面對輸入字符a、b的下一狀態(tài)相同，狀態(tài)3和狀態(tài)5面對輸入字符a、b的下一狀態(tài)相同，即得到劃分后的狀態(tài)子集為

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

按順序重新命名為0、1、2、3、4、5后得到最簡的DFA如圖2-13所示。圖2-13習題2.5的最簡DFA注意，如果將狀態(tài)4和狀態(tài)6作為等價狀態(tài)，即得到劃分后的狀態(tài)子集為

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

按順序重新命名為0、1、2、3、4后得到最簡的DFA'?如圖2-14所示。由圖2-14可以看出，由狀態(tài)4輸入a可以到達狀態(tài)3，由狀態(tài)3輸入b可以到達狀態(tài)2，即可形成如下的字符串：

aa…abb…baa…abb…baa…abb…baa…a

而不是本題正規(guī)表達式可形成的字符串：aa…abb…baa…a。圖2-14習題2.5的最簡DFA'

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

【解答】

對于語言L，w中至少有兩個1，且任意兩個1之間必須有偶數(shù)個0；也即在第一個1之前和最后一個1之后，對0的個數(shù)沒有要求。據(jù)此我們求出L的正規(guī)式為0*1(00(00)*1)*00(00)*10*，畫出與正規(guī)式對應的NFA，如圖2-15所示。圖2-15習題2.6的NFA用子集法將圖2-15所示的NFA確定化，如圖2-16所示。圖2-16習題2.6的狀態(tài)轉(zhuǎn)換矩陣由圖2-16可看出非終態(tài)2和4的下一狀態(tài)相同，終態(tài)6和8的下一狀態(tài)相同，即得到最簡狀態(tài)為

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

按順序重新命名為0、1、2、3、4、5、6，則得到最簡DFA，如圖2-17所示。圖2-17習題2.6的最簡DFA

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

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

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

【解答】(1)正規(guī)式((a?|?b)*|?aa)*b對應的NFA如圖2-18所示。圖2-18正規(guī)式((a?|?b)*|aa)*b對應的NFA用子集法將圖2-18所示的NFA確定化為DFA，如圖2-19所示。圖2-19圖2-18確定化后的狀態(tài)轉(zhuǎn)換矩陣由于對非終態(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)相同也不能合并)。表2-3合并后的狀態(tài)轉(zhuǎn)換矩陣由此得到最簡DFA，如圖2-20所示。圖2-20習題2.7的最簡DFA正規(guī)式(a?|?b)*b對應的NFA如圖2-21所示。圖2-21正規(guī)式(a?|?b)*b對應的NFA用子集法將圖2-21所示的NFA確定化為如圖2-22所示的狀態(tài)轉(zhuǎn)換矩陣。圖2-22圖2-21確定化后的狀態(tài)轉(zhuǎn)換矩陣比較圖2-22與圖2-19，重新命名后的轉(zhuǎn)換矩陣是完全一樣的，也即正規(guī)式(a?|?b)*b可以同樣得到化簡后的DFA如圖2-20所示。因此，兩個自動機完全一樣，即兩個正規(guī)文法等價。

(2)對圖2-20，令A對應狀態(tài)1，B對應狀態(tài)2，則相應的正規(guī)文法G[A]為

G[A]：A→aA?|?bB?|?b

B→aA?|?bB?|?b

G[A]可進一步化簡為G[S]：S→aS?|?bS?|?b(非終結(jié)符B對應的產(chǎn)生式與A對應的產(chǎn)生式相同，故兩非終結(jié)符等價，即可合并為一個產(chǎn)生式)。

2.8構(gòu)造一個DFA，它接收Σ={a,?b}上所有不含子串a(chǎn)bb的字符串。

【解答】

本題對應的正規(guī)表達式為b*(?a∣ab?)*，對應的NFA如圖2-23所示。圖2-23正規(guī)式b*(?a|ab?)*對應的NFA用子集法將圖2-23所示的NFA確定化為DFA，如圖2-24所示。圖2-24圖2-23確定化后的狀態(tài)轉(zhuǎn)換矩陣由圖2-24重新命名后的轉(zhuǎn)換矩陣可以看出：狀態(tài)0、狀態(tài)1和狀態(tài)2對輸入字符b的下一狀態(tài)都是不一樣的，故狀態(tài)0、狀態(tài)1和狀態(tài)2已為最簡狀態(tài)。由此得到最簡DFA，如圖2-25所示。圖2-25習題2.8的最簡DFA注意，諸如a*b*這類正規(guī)式簡化的NFA只能畫成圖2-26的形式，而不能畫成圖2-27的形式，圖2-27對應的是正規(guī)式(a∣b)*。本題對應的另一個正規(guī)表達式為b*(a∣ba)*(?ab?)*。圖2-26a*b*的NFA圖2-27(?a∣b?)*的NFA

2.9構(gòu)造一個DFA，它接收Σ={a,?b}上所有含偶數(shù)個a的字符串。

【解答】

根據(jù)題意可以構(gòu)造出字符串中含偶數(shù)個a的正規(guī)表達式：(?b∣ab*a?)*。根據(jù)此正規(guī)表達式畫出相應的NFAM如圖2-28所示。圖2-28習題2.9的NFAM用子集法將圖2-28所示的NFA確定化為DFA，如圖2-29所示。圖2-29圖2-28確定化后的狀態(tài)轉(zhuǎn)換矩陣由圖2-29重新命名后的轉(zhuǎn)換矩陣可以看出：狀態(tài)0和狀態(tài)2對輸入字符a、b的下一狀態(tài)都是一樣的，故狀態(tài)0和狀態(tài)2可合并為一個狀態(tài)。最終得到最簡DFA如圖2-30所示。

當然，我們也可以將圖2-28中的狀態(tài)X和狀態(tài)Y與狀態(tài)1合并而直接得到圖2-30。圖2-30習題2.9的最簡DFAM圖2-31習題2.11的NFA

【解答】

用子集法將NFA確定化，如圖2-32所示。圖2-32習題2.11的狀態(tài)轉(zhuǎn)換矩陣圖2-32所對應的DFA如圖2-33所示。

對圖2-33所示的DFA進行最小化。首先將狀態(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)集，故將其劃分