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

(1)詞法分析器的輸出結果是

。 a.單詞的種別編碼b.單詞在符號表中的位置 c.單詞的種別編碼和自身值d.單詞自身值 (2)正規式M1和M2等價是指

。 a.M1和M2的狀態數相等

b.M1和M2的有向邊條數相等 c.M1和M2所識別的語言集相等 d.M1和M2狀態數和有向邊條數相等

(3)DFAM(見圖2-1)接受的字集為

。

a.以0開頭的二進制數組成的集合

b.以0結尾的二進制數組成的集合

c.含奇數個0的二進制數組成的集合

d.含偶數個0的二進制數組成的集合

圖2-1習題2.1的DFAM 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} 試構造相應的確定有限自動機M′。 【解答】

對照自動機的定義M=(S,Σ,f,So,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數，因此M是一非確定有限自動機。 先畫出NFAM相應的狀態圖，如圖2-2所示。圖2-2習題2.3的NFAM一個句型中的最左

稱為該句型的句柄。A．短語

B．直接短語

C．素短語

D．終結符號詞法分析器用于識別

。A．句子

B．句型

C．單詞

D．產生式在自底向上的語法分析方法中，分析的關鍵是

。A．尋找句柄

B．尋找句型

C．消除遞歸

D．選擇候選式文法G產生的

的全體是該文法描述的語言。A．句型B．終結符集C．非終結符集D．句子四種形式語言文法中，1型文法又稱為

文法。A．短語結構文法

B．前后文無關文法C．前后文有關文法

D．正規文法一個文法所描述的語言是

。A．唯一的

B．不唯一的 C．可能唯一，好可能不唯一

D．都不對

和代碼優化部分不是每個編譯程序都必需的。A．語法分析

B．中間代碼生成 C．詞法分析

D．目標代碼生成

是兩類翻譯程序。A．高級語言程序和低級語言程序 B．解釋程序和編譯程序C．編譯程序和操作系統 D．系統程序和應用程序一個上下文無關文法G包括四個組成部分，它們是：一組非終結符號，一組終結符號，一個開始符號，以及一組

。A．句子B．句型 C．單詞D．產生式詞法分析器用于識別

。

A．字符串

B．語句 C．單詞D．標識符與編譯系統相比，解釋系統

。A．比較簡單,可移植性好,執行速度快B．比較復雜,可移植性好,執行速度快C．比較簡單,可移植性差,執行速度慢D．比較簡單,可移植性好,執行速度慢用高級語言編寫的程序經編譯后產生的程序叫

。A．源程序

B．目標程序

C．連接程序D．解釋程序詞法分析器的輸出結果是

。A．單詞的種別編碼B．單詞在符號表中的位置 C．單詞的種別編碼和自身值D．單詞自身值 用子集法構造狀態轉換矩陣，如表2-1所示。

表2-1狀態轉換矩陣

將轉換矩陣中的所有子集重新命名，形成表2-2所示的狀態轉換矩陣，即得到 M′=({0,1,2},{a,b},f,0,{1,2})，其狀態轉換圖如圖2-3所示。

表2-2狀態轉換矩陣 將圖2-3所示的DFAM′最小化。首先，將M′的狀態分成終態組{1,2}與非終態組{0}。其次，考察{1,2}，由于{1,2}a={1,2}b={2}{1,2}，所以不再將其劃分了，也即整個劃分只有兩組：{0}和{1,2}。令狀態1代表{1,2}，即把原來到達2的弧都導向1，并刪除狀態2。最后，得到如圖2-4所示的化簡了的DFAM′。圖2-3習題2.3的DFAM′圖2-4圖2-3化簡后的DFAM′ 2.4設有L(G)={a2n+1b2ma2p+1|

n≥0,p≥0,m≥1}。 (1)給出描述該語言的正規表達式； (2)構造識別該語言的確定有限自動機(可直接用狀態圖形式給出)。 【解答】

該語言對應的正規表達式為a(aa)*bb(bb)*a(aa)*，正規表達式對應的NFA如圖2-8所示。圖2-8習題2-5的NFA 用子集法將圖2-8確定化，如圖2-9所示。 由圖2-9重新命名后的狀態轉換矩陣可化簡為(也可由最小化方法得到){0,2}{1}{3,5}{4,6}{7} 按順序重新命名為0、1、2、3、4后得到最簡的DFA，如圖2-10所示。

圖2-9習題2.5的狀態轉換矩陣

圖2-10習題2.5的最簡DFA 2.6有語言L={w|w∈(0,1)+，并且w中至少有兩個1，又在任何兩個1之間有偶數個0}，試構造接受該語言的確定有限狀態自動機(DFA)。 【解答】對于語言L，w中至少有兩個1，且任意兩個1之間必須有偶數個0；也即在第一個1之前和最后一個1之后，對0的個數沒有要求。據此我們求出L的正規式為0*1(00(00)*1)*00(00)*10*，畫出與正規式對應的NFA，如圖2-11所示。

圖2-11習題2.6的NFA 用子集法將圖2-11的NFA確定化，如圖2-12所示。

圖2-12習題2.6的狀態轉換矩陣

由圖2-12可看出非終態2和4的下一狀態相同，終態6和8的下一狀態相同，即得到最簡狀態為{0}、{1}、{2,4}、{3}、{5}、{6,8}、{7} 按順序重新命名為0、1、2、3、4、5、6，則得到最簡DFA，如圖2-13所示。

圖2-13習題2.6的最簡DFA 2.7已知正規式((a|b)*|aa)*b和正規式(a|b)*b。 (1)試用有限自動機的等價性證明這兩個正規式是等價的； (2)給出相應的正規文法。 【解答】

(1)正規式((a|b)*|aa)*b對應的NFA如圖2-14所示。圖2-14正規式((a|b)*|aa)*b對應的NFA 用子集法將圖2-14所示的NFA確定化為DFA，如圖2-15所示。

圖2-15圖2-14確定化后的狀態轉換矩陣

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

正規式(a|b)*b對應的NFA如圖2-17所示。

表2-3合并后的狀態轉換矩陣

圖2-16習題2.7的最簡DFA

圖2-17正規式(a|b)*b對應的NFA 用子集法將圖2-17所示的NFA確定化為如圖2-18所示的狀態轉換矩陣。

圖2-18圖2-17確定化后的狀態轉換矩陣

比較圖2-18與圖2-15，重新命名后的轉換矩陣是完全一樣的，也即正規式(a|b)*b可以同樣得到化簡后的DFA如圖2-16所示。因此，兩個自動機完全一樣，即兩個正規文法等價。 (2)對圖2-16，令A對應狀態1，B對應狀態2，則相應的正規文法G[A]為G[A]：A→aA|bB|bB→aA|bB|b G[A]可進一步化簡為G[S]：S→aS|bS|b(非終結符B對應的產生式與A對應的產生式相同，故兩非終結符等價，即可合并為一個產生式)。 2.8下列程序段以B表示循環體，A表示初始化，I表示增量，T表示測試： I=1; while(I<=n) { sun=sun+a[I]; I=I+1; } 請用正規表達式表示這個程序段可能的執行序列。 【解答】用正規表達式表示程序段可能的執行序列為A(TBI)*。 2.9將圖2-19所示的非確定有限自動機(NFA)變換成等價的確定有限自動機(DFA)。圖2-19習題2.9的NFA 其中，X為初態，Y為終態。

【解答】

用子集法將NFA確定化，如圖2-20所示。

圖2-20習題2.9的狀態轉換矩陣

圖2-20所對應的DFA如圖2-21所示。

圖2-21習題2.9的DFA圖2-22習題2.9的最簡DFA 對圖2-21的DFA進行最小化。首先將狀態分為非終態集和終態集兩部分：{0,1,2,5}和{3,4,6,7}。由終態集可知，對于狀態3、6、7，無論輸入字符是a還是b的下一狀態均為終態集，而狀態4在輸入字符b的下一狀態落入非終態集，故將其化為分{0,1,2,5},{4},{3,6,7} 對于非終態集，在輸入字符a、b后按其下一狀態落入的狀態集不同而最終劃分為{0},{1},{2},{5},{4},{3,6,7} 按順序重新命名為0、1、2、3、4、5，得到最簡DFA如圖2-22所示。 2.10有一臺自動售貨機，接收1分和2分硬幣，出售3分錢一塊的硬糖。顧客每次向機器中投放≥3分的硬幣，便可得到一塊糖(注意：只給一塊并且不找錢)。 (1)寫出售貨機售糖的正規表達式； (2)構造識別上述正規式的最簡DFA。 【解答】

(1)設a=1，b=2，則售貨機售糖的正規表達式為a(b|a(a|b))|b(a|b)。 (2)畫出與正規表達式a(b|a(a|b))|b(a|b)對應的NFA