第二章詞法分析_第1頁
第二章詞法分析_第2頁
第二章詞法分析_第3頁
第二章詞法分析_第4頁
第二章詞法分析_第5頁
已閱讀5頁,還剩43頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

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

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

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

。 a.M1和M2的狀態(tài)數(shù)相等

b.M1和M2的有向邊條數(shù)相等 c.M1和M2所識別的語言集相等 d.M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等

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

。

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

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

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

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

圖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} 試構(gòu)造相應的確定有限自動機M′。 【解答】

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

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

B.直接短語

C.素短語

D.終結(jié)符號詞法分析器用于識別

。A.句子

B.句型

C.單詞

D.產(chǎn)生式在自底向上的語法分析方法中,分析的關(guān)鍵是

。A.尋找句柄

B.尋找句型

C.消除遞歸

D.選擇候選式文法G產(chǎn)生的

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

文法。A.短語結(jié)構(gòu)文法

B.前后文無關(guān)文法C.前后文有關(guān)文法

D.正規(guī)文法一個文法所描述的語言是

。A.唯一的

B.不唯一的 C.可能唯一,好可能不唯一

D.都不對

和代碼優(yōu)化部分不是每個編譯程序都必需的。A.語法分析

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

D.目標代碼生成

是兩類翻譯程序。A.高級語言程序和低級語言程序 B.解釋程序和編譯程序C.編譯程序和操作系統(tǒng) D.系統(tǒng)程序和應用程序一個上下文無關(guān)文法G包括四個組成部分,它們是:一組非終結(jié)符號,一組終結(jié)符號,一個開始符號,以及一組

。A.句子B.句型 C.單詞D.產(chǎn)生式詞法分析器用于識別

。

A.字符串

B.語句 C.單詞D.標識符與編譯系統(tǒng)相比,解釋系統(tǒng)

。A.比較簡單,可移植性好,執(zhí)行速度快B.比較復雜,可移植性好,執(zhí)行速度快C.比較簡單,可移植性差,執(zhí)行速度慢D.比較簡單,可移植性好,執(zhí)行速度慢用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫

。A.源程序

B.目標程序

C.連接程序D.解釋程序詞法分析器的輸出結(jié)果是

。A.單詞的種別編碼B.單詞在符號表中的位置 C.單詞的種別編碼和自身值D.單詞自身值 用子集法構(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-3所示。

表2-2狀態(tài)轉(zhuǎn)換矩陣 將圖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},即把原來到達2的弧都導向1,并刪除狀態(tài)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)給出描述該語言的正規(guī)表達式; (2)構(gòu)造識別該語言的確定有限自動機(可直接用狀態(tài)圖形式給出)。 【解答】

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

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

圖2-10習題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-11所示。

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

圖2-12習題2.6的狀態(tài)轉(zhuǎn)換矩陣

由圖2-12可看出非終態(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-13所示。

圖2-13習題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-14所示。圖2-14正規(guī)式((a|b)*|aa)*b對應的NFA 用子集法將圖2-14所示的NFA確定化為DFA,如圖2-15所示。

圖2-15圖2-14確定化后的狀態(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)相同也不能合并)。 由此得到最簡DFA,如圖2-16所示。

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

表2-3合并后的狀態(tài)轉(zhuǎn)換矩陣

圖2-16習題2.7的最簡DFA

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

圖2-18圖2-17確定化后的狀態(tài)轉(zhuǎn)換矩陣

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

【解答】

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

圖2-20習題2.9的狀態(tài)轉(zhuǎn)換矩陣

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

圖2-21習題2.9的DFA圖2-22習題2.9的最簡DFA 對圖2-21的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)集,故將其化為分{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-22所示。 2.10有一臺自動售貨機,接收1分和2分硬幣,出售3分錢一塊的硬糖。顧客每次向機器中投放≥3分的硬幣,便可得到一塊糖(注意:只給一塊并且不找錢)。 (1)寫出售貨機售糖的正規(guī)表達式; (2)構(gòu)造識別上述正規(guī)式的最簡DFA。 【解答】

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論