編譯原理課程之詞法分析

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

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

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

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

5、便“語法分析”程序調(diào)用 P38 例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 ) then c := 3 ; end.源程

6、序源程序 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 illustrating compiling

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

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

9、式形式；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ī)定長度識別單詞識別單詞 主要包括如下幾種單詞的識別： 標識符的識別：字母+(字母/數(shù)字) 關(guān)鍵字的識別：與標識符

10、相同，最后查表 常數(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ù)程序設(shè)計語言的單詞符號都可以用轉(zhuǎn)換圖來識別。識別過程

11、是識別過程是：從初始狀態(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 state = 2; break

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

13、見書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ù)都是正規(guī)文法：letter |

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

15、集的遞歸定義：（設(shè)字母正規(guī)式和正規(guī)集的遞歸定義：（設(shè)字母表表為為 ）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ī)式和相應(yīng)的正規(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的串程序設(shè)計語言的單詞都能用正規(guī)式來定義程序設(shè)計語言的單詞都能用正規(guī)式來定義. .例2：令=l，

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

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

19、交換律 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)造尋找特殊的方法和工具。 有窮自動機分為兩類： 確定的有窮自動機(Deterministic Finite Automata) 不確定

20、的有窮自動機(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是一個終態(tài)集集( (可空可空) )，也稱可接受狀態(tài)

21、或結(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é)點和若干個(可以是0個)終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“=”

22、 ，終態(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條條弧射出弧射出，而且每條弧以一個不同的輸入字符不同的輸入字符標記。 字可為DFA M所接受

23、（識別）： 對于* 中的任何字，若存在一條從初態(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)。文法和自動機的對比文法和自動機的對比 文法是語言的生成系統(tǒng)，

25、是從產(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) 輸入01SPS,ZPZZPP從NFA的矩陣表示中可以看出

26、，表項是狀態(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，若存在一條從某一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有

27、弧的標記字依序連接成的串(不理采那些標記為的弧)等于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所能接受的符號串的全體記為L(M)結(jié)論： 上一個符號串

28、集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轉(zhuǎn)換成接受同樣語言的DFA。 NFA確定化的基本

29、思路是： DFADFA的每一個狀態(tài)對的每一個狀態(tài)對應(yīng)應(yīng)NFA的一組狀態(tài). NFA的確定化的確定化 NFA確定化的基本步驟是： 第一步：對第一步：對NFA的狀態(tài)圖進行改造。的狀態(tài)圖進行改造。由于NFA可能有多個初態(tài)結(jié)點、多個終態(tài)結(jié)點、每條弧上的標記可能是上的一個字，因此首先將其改造，使之成為只有一個初態(tài)結(jié)點、一個終態(tài)結(jié)點、每條弧上的標記只能是單個輸入符號或者。 第二步：對上述改造后的第二步：對上述改造后的NFA進行確定化。進行確定化。去掉。NFA的確定化的確定化 第一步：對第一步：對NFA的狀態(tài)圖進行改造的狀態(tài)圖進行改造 (1)增加狀態(tài)X,Y,使之成為新的唯一的初態(tài)和終態(tài)。從X引弧到原初態(tài)結(jié)點,

30、 從原終態(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)*X2a8Y746351aaabbbbX2Y431(aa|bb)(a|b)*(a|b)*X2aaY46351aabbbbX2練練 習(xí)習(xí) 求下述NFA對應(yīng)的DFA（完成第一步）01(0|1)*002YX40130001 上述NFA帶有弧，稱為具有轉(zhuǎn)移的不確定的有窮自動機 對任何一個具有轉(zhuǎn)移的不確定的有窮自動機NFA N，一定存在一個不具有轉(zhuǎn)移的不確定的有窮自動機NFA ，使

31、得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 -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= -

32、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弧而到達的狀態(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, 構(gòu)造一個構(gòu)造一個k+1列的狀態(tài)轉(zhuǎn)換表，列的狀態(tài)轉(zhuǎn)換表，行為狀態(tài)，列為輸入字符，置該表的行為狀態(tài)，列為輸入字符，置該表

33、的首行首首行首列為列為 -closure(X)，(X為第一步完成后的唯一為第一步完成后的唯一的開始狀態(tài)的開始狀態(tài))。 -closure(X)列列1列列2(a1)列列3(a2).列列K+1(aK)2.若某行的第一列的狀態(tài)已確定為若某行的第一列的狀態(tài)已確定為I，則計算第，則計算第i+1（i=1,2,k）列的值）列的值為為Iai。 -closure(X)Ia1Ia2Iak列列1列列2(a1)列列3(a2).列列K+1(aK)3.檢查第檢查第2步所創(chuàng)建的該行上的所有狀態(tài)子集，步所創(chuàng)建的該行上的所有狀態(tài)子集，看它是否已在第一列出現(xiàn)，若未出現(xiàn)，將其看它是否已在第一列出現(xiàn)，若未出現(xiàn)，將其添加到后面的空行上添

34、加到后面的空行上作為新的一行作為新的一行。 -closure(X)Ia1 ？Ia2 ？Iak ？IIa1Ia2.Iak4.重復(fù)步驟重復(fù)步驟2，3，直到狀態(tài)不再增加，即直到狀態(tài)不再增加，即所有所有狀態(tài)子集均在第一列中出現(xiàn)。狀態(tài)子集均在第一列中出現(xiàn)。 -closure(X) ？ ？ IIa1Ia2.Iak5.將每個狀態(tài)子集視為一個新的狀態(tài)，就得到將每個狀態(tài)子集視為一個新的狀態(tài)，就得到一個確定的有窮自動機，一個確定的有窮自動機，初態(tài)初態(tài)就是首行首列就是首行首列的狀態(tài)，的狀態(tài)，終態(tài)終態(tài)是含有原有終態(tài)的所有狀態(tài)。是含有原有終態(tài)的所有狀態(tài)。S SABAABCDBCABCCAC D EBBEDAFFABC狀

35、態(tài)狀態(tài)a1a2.ak例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,fSABCDEFACACFFCBBDEDDEIIaIb等價的DFAaCDBAEFSbaaaaabbbbbabF練練 習(xí)習(xí) 求下述NFA對應(yīng)的DFA(完成第二步

36、，確定化)01(0|1)*0013012001001等價的DFA為：1DFA的化簡的化簡與某一NFA等價的DFA不一定唯一。不同的DFA識別的正規(guī)集可能是相同的。每一個正規(guī)集都可以由一個狀態(tài)數(shù)最少的DFA所識別，這個DFA是唯一的（因狀態(tài)名不同的同構(gòu)情況除外）。DFA的最小化的最小化 DFA的最小化的最小化就是尋求狀態(tài)數(shù)最少的DFA，即： 它沒有多余狀態(tài)；（消去）（消去） 它的狀態(tài)中沒有兩個是互相等價的。（合并）（合并） 多余狀態(tài)多余狀態(tài)是指：從開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。 狀態(tài)狀態(tài)S和和T等價等價的條件的條件 一致性條件 狀態(tài)S和T必須同時為

37、可接受狀態(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)不等價，則將其作為一個新的狀態(tài)子集，如果無法區(qū)分，則放在同一子集中； 從每個子集中選出一個狀態(tài)做代表，即可構(gòu)成簡化的DFA； 含有原來初態(tài)的子集仍為初態(tài)，各終態(tài)的子集仍為終態(tài)。

38、DBASaaabbbba,CDBAEFSbaaaaaabbbbbba例：化簡下圖的例：化簡下圖的DFA 合并狀態(tài)注意：a、由于一個子集中，各狀態(tài)等價，故只需將原進入該子集中各狀態(tài)的弧都改為進入所選的狀態(tài)，子集中各狀態(tài)射出的弧均改為從該狀態(tài)射出。b、含有原來初態(tài)的子集仍為初態(tài)，含原終態(tài)的子集仍為終態(tài)練練 習(xí)習(xí) 最小化下述DFA021abbaa01baa 正規(guī)集的各種描述工具及其相互間的轉(zhuǎn)換正規(guī)集的各種描述工具及其相互間的轉(zhuǎn)換正規(guī)文法正規(guī)式最小的DFANFADFA正規(guī)文法與有窮自動機的等價性正規(guī)文法與有窮自動機的等價性 定義：如果L(G)=L(M), 則正規(guī)文法正規(guī)文法G與有與有窮自動機窮自動機M

39、的等價。的等價。 結(jié)論： 對每一個右(左)線性正規(guī)文法G，都存在一個有窮自動機，使L(M)=L(G) 對每一個有窮自動機，都存在一個右(左)線性正規(guī)文法G ，使L(G)=L(M) 正規(guī)文法有窮自動機(P51)已知正規(guī)文法已知正規(guī)文法G=(VG=(VN N,V,VT T,P,S), ,P,S), 求相應(yīng)的求相應(yīng)的FAFA為為M =(Q,VM =(Q,VT T, ,S,F):,S,F):1.1.輸入字母表輸入字母表: : 文法的終結(jié)符號文法的終結(jié)符號VT2.2.初始狀態(tài)：初始狀態(tài)：就是開始符號就是開始符號S S3.3.狀態(tài)集合狀態(tài)集合: : 增設(shè)一個終態(tài)增設(shè)一個終態(tài)T T，以，以Q=TQ=TV V

40、N 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,a)=B,AaB,(A,a)=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) (3)對于對于V VT T中的每個中的每個a a，(T,a) =(T,a) =, ,即在

41、終態(tài)下無動作。即在終態(tài)下無動作。6. 6. 的計算方法的計算方法( (左線性文法左線性文法) ) (1)(1)對對P P中的產(chǎn)生式中的產(chǎn)生式ABa,(B,a)=A,ABa,(B,a)=A,畫從畫從B B到到A A的弧，標為的弧，標為a a；(2)(2)對對P P中的產(chǎn)生式中的產(chǎn)生式Aa,(R,a)=A,Aa,(R,a)=A,其中其中R R是新增的起始狀態(tài)，畫是新增的起始狀態(tài)，畫從從R R到到A A的弧，標為的弧，標為a a。例:練練 習(xí)習(xí) 已知正規(guī)文法如下： 求對應(yīng)的有窮自動機SaA | aAaA | bB | aB bB | bSABTaaababb已知已知DFADFA為為M =(S,M =

42、(S, ,S,S0 0,F),F),求相應(yīng)的正規(guī)文法求相應(yīng)的正規(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. 4. 產(chǎn)生式：產(chǎn)生式： 對任何對任何a a，A,BS,S,若有：若有：(A,a)=B(A,a)=B，則：，則：當當B B F, F, 令令A(yù)aBAaB；當當 B BF， Aa|aB;Aa|aB;若若S S0 0F，增加S S0 0 有窮自動機正規(guī)文法例:有窮自動機為：練習(xí)練習(xí) 給出定義下述自動機的正規(guī)文法SABC00110011S 0A | 1C| A 0 | 0S | 1B B 1A | 0CC 1 | 1S | 0B正規(guī)式與有限自動機的等價性正規(guī)式與有限自動機的等價性正規(guī)式和有窮自動機的等價性由以下兩點說明 ： 對于上的NFA M，可以構(gòu)造一個上的正規(guī)式