《編譯原理實踐及應用》第3章詞法分析3

1、詞法分析詞法分析第三章第三章 主要內(nèi)容主要內(nèi)容：詞法分析的任務，手工實現(xiàn)詞法分析的任務，手工實現(xiàn)詞法分析程序，詞法分析程序，正規(guī)式與正規(guī)式與有窮自動機，有窮自動機，詞法分析程序的自動生成詞法分析程序的自動生成 重點掌握：重點掌握：詞法分析器的功能和接口，詞法分析器的功能和接口，用狀態(tài)轉(zhuǎn)換圖設計和實現(xiàn)詞法分析程序，用狀態(tài)轉(zhuǎn)換圖設計和實現(xiàn)詞法分析程序，正規(guī)文法、正規(guī)式和有窮自動機的概念正規(guī)文法、正規(guī)式和有窮自動機的概念及相互轉(zhuǎn)換及相互轉(zhuǎn)換本章要求本章要求詞法分析詞法分析程序所處程序所處的位置：的位置：語法分析器詞法分析器符號表編譯程序的后續(xù)部分token取下一個單詞語法樹3.1 詞法分析器的功能詞

2、法分析器的功能 功能： 逐個讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞 主要任務： 讀入源程序，識別出各個單詞符號，并輸出 其他任務： 濾掉程序中的無用成分，如空格、注釋、換行符 調(diào)用符號管理程序，對識別出的符號進行管理 追蹤換行標志，指出源程序出錯的行列位置 關(guān)鍵：找出單詞的分隔符源程序詞法分析程序Token串語法分析程序 單詞單詞：是語言中具有獨立意義的最小單位，常用單詞分類： 保留字：具有固定意義的標識符 運算符 界符 標識符：表示各種名字 常數(shù) 對于一個程序設計語言，保留字、運算符和界符都是確定的，可以給以固定的編號(種別碼)。 標識符是根據(jù)構(gòu)詞規(guī)則定義的，常數(shù)是符合定義的各種類型的

3、常數(shù) 種別碼：是對能識別的單詞的分類編碼有多種編碼方式： 標識符一般統(tǒng)一為一種：一個編號 常數(shù)按類型分別編碼：整數(shù)、實數(shù)、布爾、字符 關(guān)鍵字一般一字一種 運算符一般一符一種 界符一般一符一種某語言某語言單詞的單詞的種別碼種別碼定義舉定義舉例例單詞種別碼單詞種別碼單詞種別碼and1procedure21*41array2program22*/42begin3read23+43bool4real24，44call5repeat2545case6set26、46char7then27 47constant8to28/48do9true29/*49else10until30：50end11var31:

4、=51false12while32；52for13write3353if14標識符34=54input15整常數(shù)3555integer16實常數(shù)36=56not17字符常數(shù)3757of1838=58or19(3959output20)4060詞法分析器的輸出詞法分析器的輸出 1. Token串: 輸出源文件中各個有用有用的單詞 格式： (單詞的種別碼，單詞符號的屬性值單詞的種別碼，單詞符號的屬性值) 單詞種別：是對能識別的單詞的分類編碼(P42) 單詞符號的屬性值：單詞的某種特性或特征常數(shù)的值，標識符的名字等常數(shù)的值，標識符的名字等保留字、運算符、分界符的屬性值可以省略保留字、運算符、分界符的

5、屬性值可以省略 文件存放最好有格式，如每個單詞占一行方便“語法分析”程序調(diào)用this is a sample program writing in simple languageprogram example1;used for illustrating compiling processvara,b,c:integer;x:char;beginif (a+c*3 b) and (b3) then c:=3;gram example1 ; var a , b , c : integer ; x : char ; begin if (a +c * 3 b ) and ( b 3 )

6、 then c := 3 ; end.源程序源程序 token文件文件注意注意token文文件的格式件的格式舉例舉例 2. 符號表 各種常數(shù)和標識符一般放在符號表中，在輸出的token文件中的單詞屬性值則存放單詞在符號表中的指針 符號表的格式：字符串 if (ab2) test:=3;格式格式1：(數(shù)組數(shù)組)入口單詞名及長度類型種屬值內(nèi)存地址1a1整簡單變量未知未知2b22整簡單變量未知未知3test4實簡單變量未知未知 格式2：(用指針)this is a sample program writing in simple languageprogram example1;used for i

7、llustrating compiling processvara,b,c:integer;x:char;beginif (a+c*3 b) and (b3) then c:=3;End.源程序源程序 符號表符號表舉例舉例 3. 其它輸出：錯誤信息和源程序清單 錯誤信息應該詳細，準確，指出出錯的具體行、列位置，發(fā)生了哪類錯誤等，方便用戶修改錯誤處理錯誤處理 應盡可能發(fā)現(xiàn)更多的錯誤 處理方式 每個程序段單獨處理錯誤 統(tǒng)一處理錯誤（商用軟件系統(tǒng)） 記錄式的文件 數(shù)據(jù)庫 統(tǒng)計表明，現(xiàn)代軟件系統(tǒng)中， 75%的程序代碼都是用于處理錯誤與錯誤信息 商業(yè)系統(tǒng)中錯誤處理的特點是：統(tǒng)一錯誤編號，編制文檔指出錯誤

8、信息的含義、應對措施、解決方案詞法錯誤類型詞法錯誤類型非法字符非法字符單詞拼寫錯誤單詞拼寫錯誤難以發(fā)現(xiàn)下面的錯誤難以發(fā)現(xiàn)下面的錯誤fi (a = x ) 在實數(shù)是在實數(shù)是a.b格式下，可以發(fā)現(xiàn)下面的錯誤格式下，可以發(fā)現(xiàn)下面的錯誤123. 詞法分析是編譯過程中的一個階段，在語法分析前進行?？梢宰鳛橐粋€獨立的子程序，獨立出來的原因： 簡化設計 改進編譯效率 增加編譯系統(tǒng)的可移植性 可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當前單詞供語法分析使用。3.2 詞法分析程序的設計詞法分析程序的設計任務：任務：4組織源程序的輸入；組織源程序的輸入；4按規(guī)則拼單詞，并轉(zhuǎn)換成二元式形

9、式；按規(guī)則拼單詞，并轉(zhuǎn)換成二元式形式；4刪除注解行、空格及無用符號；刪除注解行、空格及無用符號；4行計數(shù)、列計數(shù)；行計數(shù)、列計數(shù)；4列表打印源程序；列表打印源程序；4發(fā)現(xiàn)并定位發(fā)現(xiàn)并定位詞法錯誤詞法錯誤；4如需要，還要建立關(guān)鍵字表、符號表、常數(shù)表如需要，還要建立關(guān)鍵字表、符號表、常數(shù)表等表格。等表格。詞法分析程序的接口詞法分析程序的接口 識別單詞前作如下假定： 關(guān)鍵字就是保留字 單詞中間不能有分界符(如空格、空白、界符和算符等) 單詞中間不能有注釋 單詞必須在一行內(nèi)寫完，換行后認為是另一個單詞 一個單詞不能超過規(guī)定長度識別單詞識別單詞 主要包括如下幾種單詞的識別： 標識符的識別：字母+(字母/

10、數(shù)字) 關(guān)鍵字的識別：與標識符相同，最后查表 常數(shù)的識別 界符和算符的識別超前搜索技術(shù)：如在讀取/* */時，當讀到/時，如何判別是注釋還是除法運算？識別單詞：掌握單詞的構(gòu)成規(guī)則單詞的構(gòu)成規(guī)則很重要單詞的構(gòu)成規(guī)則用狀態(tài)轉(zhuǎn)換圖表示單詞的構(gòu)成規(guī)則用狀態(tài)轉(zhuǎn)換圖表示狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。有限個狀態(tài)，用結(jié)點表示狀態(tài)，其中有一個初態(tài)有一個初態(tài)(初態(tài)用箭頭指出)，至少有一個終態(tài)至少有一個終態(tài)(終態(tài)用雙圈表示)。狀態(tài)之間用帶箭頭的弧線連結(jié)，弧線上標記的字符表示在射出狀態(tài)下可能出現(xiàn)的輸入字符或字符類。識別標識符的轉(zhuǎn)換圖012字母字母或數(shù)字其它*一個狀態(tài)圖可用于識別一定的字符串，大多數(shù)程序設計語言的單詞符號

11、都可以用轉(zhuǎn)換圖來識別。識別過程是識別過程是：從初始狀態(tài)0開始，若讀入一個字母，轉(zhuǎn)入1狀態(tài)，若再讀入字母或數(shù)字，仍處于1狀態(tài)，否則轉(zhuǎn)向2狀態(tài)，結(jié)束一個標識符的識別過程。狀態(tài)上的*表示多讀入一個符號。012字母字母或數(shù)字其它*寫成寫成C語言的函數(shù)形式：語言的函數(shù)形式：recog_id() char state = 0; ch = getch(); do switch(state) Case 0: if ch 是字母是字母 state = 1; ch = getch();break; Case 1: if ch 是字母或數(shù)字是字母或數(shù)字 state = 1; ch = getch(); else s

12、tate = 2; break; while (state != 2); 回退一個符號。回退一個符號。012字母字母或數(shù)字其它*012數(shù)字數(shù)字其它識別整數(shù)的轉(zhuǎn)換圖*練練 習習 1 畫出Pascal中無符號實數(shù)的狀態(tài)轉(zhuǎn)換圖 (不帶正負號，可表示整數(shù)、可表示小數(shù)，可帶指數(shù)部分) 如：下面幾個數(shù)應該是符合規(guī)則的數(shù)： 3，3.51，34E3,34.5E2,34.5E+2,34.5E-2練練 習習 2 畫出識別標識符和整常數(shù)(可帶正負號)的狀態(tài)轉(zhuǎn)換圖 練練 習習 3 以下狀態(tài)轉(zhuǎn)換圖接受的字符集合是什么？以下狀態(tài)轉(zhuǎn)換圖接受的字符集合是什么？XY001狀態(tài)轉(zhuǎn)換圖的實現(xiàn)：使用一個switch case 語句：

13、每條分支對應一個case語句段見書P45 例某簡單語言的詞法分析程序的實現(xiàn)詞法分析器的自動生成詞法分析器的自動生成 正規(guī)式正規(guī)式 正規(guī)文法正規(guī)文法 有窮自動機有窮自動機3.3 正規(guī)文法、正規(guī)式與有正規(guī)文法、正規(guī)式與有窮自動機窮自動機 本節(jié)要求1 能根據(jù)自然語言描述構(gòu)造NFA2 掌握NFA轉(zhuǎn)換為DFA，DFA的化簡3 掌握正規(guī)文法、正規(guī)式和有窮自動機間的轉(zhuǎn)換 為了討論詞法分析程序的自動生成問題，將狀態(tài)轉(zhuǎn)換圖加以形式化。一、正規(guī)文法一、正規(guī)文法 正規(guī)文法正規(guī)文法：文法G=(VN，VT，P，S)中的每個產(chǎn)生式的形式都是AaB或Aa，其中A和B都是非終結(jié)符，a是終結(jié)符串。下面定義的標識符和無符號整數(shù)都

14、是正規(guī)文法：letter | letter字母數(shù)字letter | digit | letter字母數(shù)字 | digit字母數(shù)字digit | digit無符號整數(shù) 結(jié)論：結(jié)論：每一種程序設計語言，都有它自己的字符集，語言中的每一個單詞或者是上的單個字符，或者是上的字符按一定方式組成的字符串。組成方式就是對字符 或 字 符 串 進 行 ( 連 接 ) “ ” 、 或“”(并)、或“”閉包運算。二、正規(guī)式二、正規(guī)式 正規(guī)式也稱為正則表達式，是表示正規(guī)集的工具。 正規(guī)式（regular expression）是說明單詞的pattern的一種重要的表示法，是單詞的描述工具。 下面是正規(guī)式和它所表示的

15、正規(guī)集的遞歸定義n正規(guī)式和正規(guī)集的遞歸定義：（設字母正規(guī)式和正規(guī)集的遞歸定義：（設字母表表為為 ）1、 和和 都是都是 上的正規(guī)式，表示上的正規(guī)式，表示 和和 ；2 、任何任何a ，則，則a是正規(guī)式，表示是正規(guī)式，表示a；3 、假定、假定r和和s都是都是 上的正規(guī)式，分別表示語言上的正規(guī)式，分別表示語言 L(r)和和L(s)： a） (r) | (s)是正規(guī)式，表示是正規(guī)式，表示L (r) U L (s) ；b） (r)(s)是正規(guī)式，表示是正規(guī)式，表示L (r)L (s)；c） (r)*是正規(guī)式，表示是正規(guī)式，表示(L (r) )*；d） (r)是正規(guī)式，表示是正規(guī)式，表示L (r)；4、有

16、限次使用上述三步驟而定義的表達式才是上的正規(guī)式正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集正規(guī)集。 或或； 連接；連接； 閉包閉包 規(guī)定優(yōu)先順序為規(guī)定優(yōu)先順序為“ ”、“ ”、“ ” (a)|(b)*(c)a|b*c例1：令=a，b， 上的正規(guī)式和相應的正規(guī)集有：正規(guī)式正規(guī)集aaba*所有以b開頭后跟任意多個a的串a(chǎn)ba,babab(ab)(ab)aa,ab,ba,bba ,a,aa, 任意個a的串(ab) ,a,b,aa,ab 所有由a 或b組成的串(a|b)*(aa|bb)(a|b)* 所有含有兩個相繼的a或兩個相繼的b的串程序設計語言的單詞都能用正規(guī)式來定義程序設計語言的單詞都能用正

17、規(guī)式來定義. .例2：令=l，d，l 代表字母,d 代表數(shù)字,則上的正規(guī)式: r = l(ld) 定義的正規(guī)集為: l,ll,ld,lll,ldd,就是Pascal和 多數(shù)程序設計語言允許的的標識符的詞法規(guī)則。例3：令d， ，e，其中d為09中的數(shù)字。則上的正規(guī)式: d*(.dd*| )(e(+|-|)dd*|) 表示PASCAL語言中的無符號實數(shù)。 比如：2, 12.59, 3.6e2, 471.88e-1等都是正規(guī)式表示集合中的元素。練練 習習1、 =a,b，則，則 上所有以上所有以b開頭，后跟若開頭，后跟若干個干個ab的字的全體所對應的正規(guī)式。的字的全體所對應的正規(guī)式。2、 =a,b，寫

18、出不以，寫出不以a開頭，但以開頭，但以aa結(jié)結(jié)尾的字符串集合的正規(guī)式。尾的字符串集合的正規(guī)式。b(a|b)*aab(ab)* 思考題：思考題： =d，. ，則，則 上表示上表示無符號數(shù)無符號數(shù)的正規(guī)式是的正規(guī)式是什么？（什么？（不考慮含不考慮含e的科學計數(shù)法，的科學計數(shù)法，其中其中d為為09的數(shù)字）的數(shù)字） 如：如：2 ，12.59 ，471.88等都是該集等都是該集合中的元素。合中的元素。 dd dd* *(.dd(.dd* *| | ) )正規(guī)式的等價正規(guī)式的等價 若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則e1和e2等價等價,寫作e1=e2。 設r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有

19、： 1. rs=sr“或”服從交換律 2. r(st)=(rs)t “或”的可結(jié)合律 3. (rs)t=r(st)“連接”的可結(jié)合律 4. r(st)=rsrt (st)r=srtr 分配律 5. r=r=r是“連接”的恒等元素 零一律 6. e*e+ 7. e+=e*e=ee*8. (e*)*=e* 三、有窮自動機三、有窮自動機 有窮自動機(也稱有限自動機)作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。 有窮自動機分為兩類： 確定的有窮自動機(DFA:Deterministic

20、Finite Automata) 不確定的有窮自動機(NFA:Nondeterministic Finite Automata)確定的有窮自動機確定的有窮自動機DFA一個確定的有窮自動機確定的有窮自動機(DFA) M是一個五元組：M=(S，s0，F(xiàn))，其中:1.S是一個有窮有窮集，它的每個元素稱為一個狀態(tài)；2.是一個有窮有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號表；3.是轉(zhuǎn)換函數(shù)，是在SS上的單值單值映射， (s，a)=s (sS，sS) ，就意味著，當前狀態(tài)為s，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)s，我們把s稱作s的一個后繼狀態(tài)；4. s0 S是唯一唯一的一個初態(tài)；5.FS是

21、一個終態(tài)集集( (可空可空) )，也稱可接受狀態(tài)或結(jié)束狀態(tài)。例3：有DFA M =(0,1,2,3,a,b, ,0,3) 為：(0,a) = 1 (0,b) = 2(1,a) = 3 (1,b) = 2(2,a) = 1 (2,b) = 3(3,a) = 3 (3,b) = 3狀態(tài) 輸入ab012132213333行表示狀態(tài)，列表示輸入字符，矩陣元素表示 (s，a)的值，稱為狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣。DFA的矩陣表示一個DFA可以表示成一個狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。假定DFA M含有m個狀態(tài)，n個輸入字符，那么這個狀態(tài)圖含有m個結(jié)點，每個結(jié)點最多有n個弧射出，整個圖含有唯一一個初態(tài)結(jié)點和若干個

22、(可以是0個)終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“=” ，終態(tài)結(jié)點用雙圈表示，若 (ki,a) =kj，則從狀態(tài)結(jié)點ki到狀態(tài)結(jié)點kj畫標記為a的弧。b0123aaaba，bb(0,a) = 1 (0,b) = 2(1,a) = 3 (1,b) = 2(2,a) = 1 (2,b) = 3(3,a) = 3 (3,b) = 3 DFA的確定性表現(xiàn)在：的確定性表現(xiàn)在： 對任何狀態(tài)s S，在讀入了輸入符號a 之后，能夠唯一地確定唯一地確定下一個狀態(tài) 映射函數(shù)：SS是一個單值單值函數(shù) 從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個輸入字符，那末任何一個狀態(tài)結(jié)點最多有最多有n條條弧射出弧射出，而且每條弧以一個不同的輸入

23、字符不同的輸入字符標記。 字可為DFA M所接受（識別）： 對于* 中的任何字，若存在一條從初態(tài)結(jié)點到某個終態(tài)結(jié)點的通路，且這條通路上所有弧的標記符號連接成的字等于。 若M的初態(tài)結(jié)點又是終態(tài)結(jié)點，則空字可為M所識別。 DFA M所能識別的符號串的全體記為L(M). 對于任何兩個有窮自動機M和M，如果L(M)=L(M)，則稱M與M是等價等價的. 有窮自動機模型電梯控制系統(tǒng)，人腦都是有窮自動機文本編輯程序有窮狀態(tài)系統(tǒng)每讀入一個符號，讀每讀入一個符號，讀頭向后移動一個位置，頭向后移動一個位置，有窮控制器控制狀態(tài)有窮控制器控制狀態(tài)轉(zhuǎn)移到下一個狀態(tài)轉(zhuǎn)移到下一個狀態(tài)在初始時，讀頭處于輸在初始時，讀頭處于輸

24、入帶的開始位置，表示入帶的開始位置，表示準備讀入，狀態(tài)處于初準備讀入，狀態(tài)處于初始狀態(tài)始狀態(tài)整個模型由三部分組成：整個模型由三部分組成： 輸入帶：存放輸入符號輸入帶：存放輸入符號 讀頭：可以在輸入帶上向后移動讀頭：可以在輸入帶上向后移動 有窮控制器：控制狀態(tài)發(fā)生變化有窮控制器：控制狀態(tài)發(fā)生變化如果讀頭移動到最后一個符號后面，如果讀頭移動到最后一個符號后面，狀態(tài)正好是終結(jié)狀態(tài)，則稱輸入帶狀態(tài)正好是終結(jié)狀態(tài)，則稱輸入帶上的符號組成的字能被該有窮自動上的符號組成的字能被該有窮自動機所識別機所識別 結(jié)論： 上一個符號串集V 是正規(guī)的，當且僅當存在一個上的確定有窮自動機M，使得V=L(M)。文法和自動機

25、的對比文法和自動機的對比 文法是語言的生成系統(tǒng)，是從產(chǎn)生的觀點來描述語言的。 自動機是語言的識別系統(tǒng)，是從識別的觀點來描述語言的不確定的有窮自動機不確定的有窮自動機NFA 定義定義：不確定的有窮自動機NFA也是一個五元組， M=S，s0，F(xiàn) ，其中： S為狀態(tài)的有窮有窮狀態(tài)集， 為有窮有窮輸入字母表， 為S * 到S的冪集冪集(2S)的一種映射:S * 2S s0 S是初始狀態(tài)集初始狀態(tài)集， F S為終止狀態(tài)集(可空)。NFA的矩陣表示 例4：NFA M=(S，P，Z，0，1，S，P，Z)其中： (S，0)=P(S，1)=S，Z(Z，0)=P(Z，1)=P(P，1)=Z 矩陣表示狀態(tài) 輸入01

26、SPS,ZPZZPP從NFA的矩陣表示中可以看出，表項是狀態(tài)的集合，而在DFA的矩陣表示中，表項是一個狀態(tài)狀態(tài)圖表示一個含有m個狀態(tài)，n個輸入字符的NFA的狀態(tài)轉(zhuǎn)換圖：有m個結(jié)點，每個結(jié)點可射出若干條若干條弧與別的結(jié)點相連接，每條弧用* 上的一個字來表示(這些字可以相同，也可以是)。整個圖至少有一個初始結(jié)點至少有一個初始結(jié)點以及若干個若干個(可以是可以是0個個)終態(tài)結(jié)點終態(tài)結(jié)點，某些結(jié)點既可以是初態(tài)結(jié)點，又可以是終態(tài)結(jié)點。(S，0)=P(S，1)=S，Z(Z，0)=P(Z，1)=P(P，1)=ZSPZ00,1111*上的符號串t被NFA M接受（識別）: 對于*中的任何一個串t，若存在一條從某

27、一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標記字依序連接成的串(不理采那些標記為的弧)等于t，則稱t可為NFA M所識別(讀出或接受)。 若M的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點；或者存在一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的道路,其上所有弧的標記均為，那么空字可為M所接受。4 例例2：13a2a b接受串接受串a(chǎn)bb的移動序列的移動序列:-12424abb -1342424bba -轉(zhuǎn)換（轉(zhuǎn)換（ -transition）:是無需考慮輸入串是無需考慮輸入串就有可能發(fā)生的轉(zhuǎn)換。就有可能發(fā)生的轉(zhuǎn)換。例例3:下列下列NFA定義的語言是什么？定義的語言是什么？413b2 a ab4NFA M所能接

28、受的符號串的全體記為L(M)結(jié)論： 上一個符號串集V 是正規(guī)的，當且僅當存在一個上的不確定的有窮自動機M，使得V=L(M)。DFA與與NFA的主要區(qū)別的主要區(qū)別 （1）DFA任何狀態(tài)都沒有轉(zhuǎn)換，即沒有任何狀態(tài)可以不進行輸入符號的匹配就直接進入下一個狀態(tài)； （2）DFA對任何狀態(tài)s和任何輸入符號a，最多只有一條標記為a的邊離開s，即轉(zhuǎn)換函數(shù)：S S是一個單值部分函數(shù)。 （3）DFA的初態(tài)唯一，NFA的初態(tài)為一集合。 DFA是NFA的特例.對每個NFA N一定存在一個DFA ，使得 L(M)=L(N)。也就是說：對每個NFA N存在著與之等價的DFA M。 方法：（子集法）方法：（子集法）將NFA

29、轉(zhuǎn)換成接受同樣語言的DFA。 NFA確定化的基本思路是： DFADFA的每一個狀態(tài)對的每一個狀態(tài)對應應NFA的一組狀態(tài). DFA使用它的狀態(tài)去記錄在NFA讀入一個輸入符號后可能達到的所有狀態(tài).NFA的確定化的確定化NFA的確定化的確定化 第一步：對狀態(tài)圖進行改造第一步：對狀態(tài)圖進行改造 (1)增加狀態(tài)X,Y,使之成為新的唯一的初態(tài)和終態(tài)。從X引弧到原初態(tài)結(jié)點, 從原終態(tài)結(jié)點引弧到Y(jié)結(jié)點。 (2) 對狀態(tài)圖進一步進行如下形式的改變ijABikAjBijA|BiAjBijA*ikjA 例5：有NFA如下：21(a|b)*(aa|bb)(a|b)*Y1(a|b)*(aa|bb)(a|b)*X2a8Y

30、746351aaabbbbX2Y431(aa|bb)(a|b)*(a|b)*X2aaY46351aabbbbX2練練 習習 求下述NFA對應的DFA（完成第一步）01(0|1)*002YX40130001 上述NFA帶有弧，稱為具有轉(zhuǎn)移的不確定的有窮自動機 對任何一個具有轉(zhuǎn)移的不確定的有窮自動機NFA N，一定存在一個不具有轉(zhuǎn)移的不確定的有窮自動機NFA ，使得L(M)=L(N)。2acbb31acacbb2123abcv狀態(tài)集合狀態(tài)集合I I的的-閉包閉包-closure(I)，是一狀態(tài)集 v任何狀態(tài)q I，則q -closure(I)；v任何狀態(tài)q I，則q經(jīng)任意條 弧而能到達的狀態(tài)q -

31、closure(I) 。 第二步：對上述改造后的第二步：對上述改造后的NFA進行確定化進行確定化-closure(I)=5,4,6,2,712534687aaa例： I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2；I=5,4, -closure(I)=？I=1,2, J=move(I,a)= 5,3,4 ; Ia= -closure(5,3,4)=2,3,4,5,6,7,812534687aaav狀態(tài)集合狀態(tài)集合I I的的a a弧轉(zhuǎn)換弧轉(zhuǎn)換，I Ia = -closure(J) ,其中J=move(I,a)，即所有可從I中的某一狀態(tài)經(jīng)過一條a弧而到達的

32、狀態(tài)的全體。I=1, J=move(I,a) = 5, 4 ; Ia= -closure(5, 4)=2,4,5,6,7I=1,2, Ia=?v對對NFA NFA 進行確定化，構(gòu)造狀態(tài)轉(zhuǎn)換表：進行確定化，構(gòu)造狀態(tài)轉(zhuǎn)換表：1. = a1ak, 則初始時該表有則初始時該表有k+1列，分別為列，分別為I、Ia1 Iak，首行首列為首行首列為 -closure(X)，(X為開始結(jié)點為開始結(jié)點)；2.每行的值每行的值Iak = -closure(move(I,a)，其，其行數(shù)未行數(shù)未知；知；3.將新產(chǎn)生的將新產(chǎn)生的Iak集合加入到集合加入到I中作為新的一行，中作為新的一行，并求該集合并求該集合I的的Ia

33、1 Iak ，重復之，直到狀態(tài)，重復之，直到狀態(tài)不再增加；不再增加；4.初態(tài)初態(tài)就是首行首列的狀態(tài)，就是首行首列的狀態(tài)，終態(tài)終態(tài)是含有原終是含有原終態(tài)的集合。態(tài)的集合。例6：將下述NFA確定化4f35621iaaaabbbbi,1,2 1,2,31,2,41,2,3 1,2,3,5,6,f1,2,41,2,4 1,2,31,2,4,5,6,f1,2,3,5,6,f 1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f 1,2,3,6,f1,2,4,5,6,f1,2,4,6,f 1,2,3,6,f1,2,4,5,6,f1,2,3,6,f 1,2,3,5,6,f1,2,4,6,fSABC

34、DEFACACFFCBBDEDDEIIaIb等價的DFAaCDBAEFSbaaaaabbbbbabF練練 習習 求下述NFA對應的DFA(完成第二步，確定化)01(0|1)*0013012001001等價的DFA為：1確定有窮自動機的化簡確定有窮自動機的化簡與某一NFA等價的DFA不一定唯一.不同的DFA識別的正規(guī)集可能是相同的每一個正規(guī)集都可以由一個狀態(tài)數(shù)最少的DFA所識別，這個DFA是唯一的（因狀態(tài)名不同的同構(gòu)情況除外）。DFA的最小化的最小化 DFA的最小化的最小化就是尋求狀態(tài)數(shù)最少的DFA，即： 它沒有多余狀態(tài)；（消去）（消去） 它的狀態(tài)中沒有兩個是互相等價的。（合并）（合并） 多余狀

35、態(tài)多余狀態(tài)是指：從開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。 狀態(tài)狀態(tài)S和和T等價等價的條件的條件 一致性條件 狀態(tài)S和T必須同時為可接受狀態(tài)或不可接受狀態(tài)。 蔓延性條件 對于所有輸入符號，狀態(tài)S和狀態(tài)T必須轉(zhuǎn)換到等價的狀態(tài)里。DFA的最小化的方法的最小化的方法分割法分割法分割法的核心 把DFA的全部狀態(tài)劃分成一些互不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的（不等價），而同一子集中的任何兩個狀態(tài)都是等價的. 算法算法： 所有狀態(tài)分成兩個子集終態(tài)集和非終態(tài)集； 運用判定狀態(tài)等價的原則分別對兩個子集的狀態(tài)進行分析和劃分，若發(fā)現(xiàn)某個狀態(tài)與其它狀態(tài)不等價，

36、則將其作為一個新的狀態(tài)子集，如果無法區(qū)分，則放在同一子集中； 從每個子集中選出一個狀態(tài)做代表，即可構(gòu)成簡化的DFA； 含有原來初態(tài)的子集仍為初態(tài)，各終態(tài)的子集仍為終態(tài)。例：化簡下圖的例：化簡下圖的DFACDBAEFSbaaaaaabbbbbbaDBASaaabbbba, 合并狀態(tài)注意：a、由于一個子集中，各狀態(tài)等價，故只需將原進入該子集中各狀態(tài)的弧都改為進入所選的狀態(tài)，子集中各狀態(tài)射出的弧均改為從該狀態(tài)射出。b、含有原來初態(tài)的子集仍為初態(tài)，含原終態(tài)的子集仍為終態(tài)練練 習習 最小化下述DFA021abbaa01baa 正規(guī)集的各種描述工具及其相互間的轉(zhuǎn)換正規(guī)文法正規(guī)式最小的DFANFADFA正規(guī)

37、文法與有窮自動機的等價性正規(guī)文法與有窮自動機的等價性 定義：如果L(G)=L(M), 則正規(guī)文法正規(guī)文法G與有與有窮自動機窮自動機M的等價。的等價。 結(jié)論： 對每一個右(左)線性正規(guī)文法G，都存在一個有窮自動機，使L(M)=L(G) 對每一個有窮自動機，都存在一個右(左)線性正規(guī)文法G ，使L(G)=L(M) 正規(guī)文法有窮自動機已知正規(guī)文法已知正規(guī)文法G=(VG=(VN N,V,VT T,P,S), ,P,S), 求相應的求相應的FAFA為為M =(Q,VM =(Q,VT T, ,S,F):,S,F):1.1.輸入字母表輸入字母表: : 文法的終結(jié)符號文法的終結(jié)符號VT2.2.初始狀態(tài)：初始狀

38、態(tài)：就是開始符號就是開始符號S S3.3.狀態(tài)集合狀態(tài)集合: : 增設一個終態(tài)增設一個終態(tài)T T，以，以Q=TQ=TV VN N 為狀態(tài)結(jié)點為狀態(tài)結(jié)點4.4.終態(tài)集合：終態(tài)集合：若若P P中含有中含有S S的產(chǎn)生式，則的產(chǎn)生式，則F=T,SF=T,S，否則，否則F=TF=T5. 5. 的計算方法的計算方法 (1)(1)對對P P中的產(chǎn)生式中的產(chǎn)生式AaB,(A,aAaB,(A,a)=B,)=B, 畫從畫從A A到到B B的弧，標為的弧，標為a a； (2)(2)對對P P中的產(chǎn)生式中的產(chǎn)生式Aa,(A,a)=T,Aa,(A,a)=T,畫從畫從A A到到T T的弧，標為的弧，標為a;a; (3)

39、 (3)對于對于V VT T中的每個中的每個a a，(T,a(T,a) =) =, ,即在終態(tài)下無動作即在終態(tài)下無動作例:練練 習習 已知正規(guī)文法如下： 求對應的有窮自動機SaA | aAaA | bB | aB bB | bSABTaaababb已知已知DFADFA為為M =(S,M =(S, ,S,S0 0,F),F),求相應的正規(guī)文法求相應的正規(guī)文法( (右右線性線性) G=() G=(,S,S,S,S0 0,P),P)的方法的方法: :1. 1. 終結(jié)符號終結(jié)符號: V VT T=字母表2. 開始符號開始符號：S S=初始狀態(tài)S S0 03. 非終結(jié)符號：非終結(jié)符號：VN = S4.

40、4. 產(chǎn)生式：產(chǎn)生式： 對任何對任何a a，A,BS,S,若有：若有：(A,a)=B(A,a)=B，則：，則：當當B B F, F, 令令AaBAaB；當當 B BF， Aa|aBAa|aB; ;若若S S0 0F，增加S S0 0 有窮自動機正規(guī)文法例:有窮自動機為：練習練習 給出定義下述自動機的正規(guī)文法SABC00110011S 0A | 1C| A 0 | 0S | 1B B 1A | 0CC 1 | 1S | 0B正規(guī)式與有限自動機的等價性正規(guī)式與有限自動機的等價性正規(guī)式和有窮自動機的等價性由以下兩點說明 ： 對于上的NFA M，可以構(gòu)造一個上的正規(guī)式R，使得L(R)=L(M)。 對于上的每個正規(guī)式R，可以構(gòu)造一個上的NFA M，使得L(M)=L(R)。方法：方法