第3章詞法分析

1、詞法分析詞法分析第三章第三章 o 主要內(nèi)容主要內(nèi)容：詞法分析的任務，手工實現(xiàn)詞法分析的任務，手工實現(xiàn)詞法分析程序，詞法分析程序，正規(guī)式與正規(guī)式與有窮自動機，有窮自動機，詞法分析程序的自動生成詞法分析程序的自動生成o 重點掌握：重點掌握：詞法分析器的功能和接口，詞法分析器的功能和接口，用狀態(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、功能詞法分析器的功能o 功能：n逐個讀入源程序字符并按照構詞規(guī)則切分成一系列單詞o 主要任務：n讀入源程序，識別出各個單詞符號，并輸出o 其他任務：n濾掉程序中的無用成分，如空格、注釋、換行符n調(diào)用符號管理程序，對識別出的符號進行管理n追蹤換行標志，指出源程序出錯的行列位置o 關鍵：找出單詞的分隔符源程序詞法分析程序Token串語法分析程序o 單詞單詞：是語言中具有獨立意義的最小單位，常用單詞分類：n 保留字：具有固定意義的標識符n 運算符n 界符n 標識符：表示各種名字n 常數(shù)o 對于一個程序設計語言，保留字、運算符和界符都是確定的，可以給以固定的編號(種別碼)。o 標識符是根據(jù)構詞規(guī)則定義

3、的，常數(shù)是符合定義的各種類型的常數(shù)o 種別碼：是對能識別的單詞的分類編碼有多種編碼方式：o 標識符一般統(tǒng)一為一種：一個編號o 常數(shù)按類型分別編碼：整數(shù)、實數(shù)、布爾、字符o 關鍵字一般一字一種o 運算符一般一符一種o 界符一般一符一種某語言單詞的種別碼定義舉例某語言單詞的種別碼定義舉例類別單詞種別碼類別單詞種別碼類別單詞種別碼關鍵字program1關鍵字write18標識符id34var2true19integer3false20bool4運算符not21常數(shù)整常數(shù)35real5and22實常數(shù)36char6or23字符常數(shù)37const7+24布爾常數(shù)38begin8-25界符=39if9*2

4、6;40then10/27,41else1129/*43do13=31:45to15=32(46end1633)47read17.48詞法分析器的輸出詞法分析器的輸出o 1. Token串: 輸出源文件中各個有用有用的單詞n 格式： (單詞的種別碼，單詞符號的屬性值單詞的種別碼，單詞符號的屬性值)n 單詞種別：是對能識別的單詞的分類編碼n 單詞符號的屬性值：單詞的某種特性或特征o 常數(shù)的值，標識符的名字等常數(shù)的值，標識符的名字等o 保留字、運算符、分界符的屬性值可以省保留字、運算符、分界符的屬性值可以省略略n 文件存放最好有格式，如每個單詞占一行方便“語法分析”程序調(diào)用this is a sa

5、mple 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.源程序源程序 token文件文件注意注意token文文件的格式

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

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

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

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

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

11、別過程是識別過程是：從初始狀態(tài)0開始，若讀入一個字母，轉(zhuǎn)入1狀態(tài)，若再讀入字母或數(shù)字，仍處于1狀態(tài)，否則轉(zhuǎn)向2狀態(tài)，結束一個標識符的識別過程。狀態(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; br

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

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

14、整數(shù)都是正規(guī)文法： | | | * | / a|b|c|z|A|B|Z 0|1|2|9o 結論：結論：每一種程序設計語言，都有它自己的字符集，語言中的每一個單詞或者是上的單個字符，或者是上的字符按一定方式組成的字符串。組成方式就是對字符或字符串進行(連接)“”、或“”(并)、或“”閉包運算。二、正規(guī)式二、正規(guī)式o 正規(guī)式也稱為正則表達式，是表示正規(guī)集的工具。o 正規(guī)式（regular expression）是說明單詞的pattern的一種重要的表示法，是單詞構成規(guī)則的描述工具。n正規(guī)式和正規(guī)集的遞歸定義：（設字母正規(guī)式和正規(guī)集的遞歸定義：（設字母表表為為 ）1、 和和 都是都是 上的正規(guī)式，表

15、示上的正規(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、有限次使用上述三步驟而定義的表達式才是上的正規(guī)式正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集正規(guī)集。 或或； 連接；連接； 閉包閉包

16、 規(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ī)式來定義程序設計語言的單詞都能用正規(guī)式來定義. .例2：令=l，d，l 代表字母,d 代表數(shù)字,則上的正規(guī)式: r = l(ld) 定義的正規(guī)集為: l,ll,ld,ll

17、l,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，寫出不以，寫出不以a開頭，但以開頭，但以aa結結尾的字符串集合的正規(guī)式。尾的字符串集合的正規(guī)式。b(a|b)*aab(ab)*o 思考題：

18、思考題： =d，. ，則，則 上表示上表示無符號數(shù)無符號數(shù)的正規(guī)式是的正規(guī)式是什么？（什么？（不考慮含不考慮含e的科學計數(shù)法，的科學計數(shù)法，其中其中d為為09的數(shù)字）的數(shù)字） 如：如：2 ，12.59 ，471.88等都是該集合中等都是該集合中的元素。的元素。 dddd* *(.(.dddd* *| | ) )正規(guī)式的等價正規(guī)式的等價o 若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則e1和e2等價等價,寫作e1=e2。o 設r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：n 1. rs=sr“或”服從交換律n 2. r(st)=(rs)t“或”的可結合律n 3. (rs)t=r(st)“連接”的可結

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

20、 Automata)不確定的有窮自動機不確定的有窮自動機NFAo 定義定義：不確定的有窮自動機NFA也是一個五元組， M=S，s0，F(xiàn) ，其中： S為有窮有窮狀態(tài)集， 為有窮有窮輸入字母表， 為S * 到S的冪集冪集(2S)的一種映射:S * 2S s0 S是初始狀態(tài)集初始狀態(tài)集， F S為終止狀態(tài)集(可空)。NFA的三種表示法o 1. 給出NFA的五個部分的具體值o 2.矩陣表示法（狀態(tài)轉(zhuǎn)換表）o 3.狀態(tài)轉(zhuǎn)換圖表示法NFA的矩陣表示o例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)=Zo 矩陣表示狀態(tài) 輸入0

21、1SPS,ZPZZPP狀態(tài)圖表示一個含有m個狀態(tài)，n個輸入字符的NFA的狀態(tài)轉(zhuǎn)換圖：有m個結點，每個結點可射出若干條若干條弧與別的結點相連接，每條弧用一個輸入符號或來標記表示(這些字可以相同，也可以是)。整個圖至少有一個初始結點至少有一個初始結點以及若干個若干個(可以是可以是0個個)終態(tài)結點終態(tài)結點，某些結點既可以是初態(tài)結點，又可以是終態(tài)結點。(S，0)=P(S，1)=S，Z(Z，0)=P(Z，1)=P(P，1)=ZSPZ00,1111NFA的特點是它的不確定性不確定性，即在當前狀態(tài)下，讀入同一個符號，可能有多個下一狀態(tài)：n 在NFA的定義中，就是函數(shù)是一對多的；n 反映在狀態(tài)轉(zhuǎn)換圖中，就是從

22、一個結點出發(fā)，可能有多于一條標記相同的弧轉(zhuǎn)移到不同的下一狀態(tài)；n 反映在轉(zhuǎn)換表中，就是Mi，a的值不是一個單一狀態(tài)，而是一個狀態(tài)集合。 4o 例例2：13a2a b接受串接受串a(chǎn)bb的移動序列的移動序列:-12424abb -1342424bba -轉(zhuǎn)換（轉(zhuǎn)換（ -transition）:是無需考慮輸入串是無需考慮輸入串就有可能發(fā)生的轉(zhuǎn)換。就有可能發(fā)生的轉(zhuǎn)換。*上的符號串t被NFA M接受（識別）:o 對于*中的任何一個串t，若存在一條從某一初態(tài)結點到某一終態(tài)結點的通路，且這條通路上所有弧的標記字依序連接成的串(不理采那些標記為的弧)等于t，則稱t可為NFA M所識別(讀出或接受)。o 若M的

23、某些結點既是初態(tài)結點又是終態(tài)結點；或者存在一條從某個初態(tài)結點到某個終態(tài)結點的道路,其上所有弧的標記均為，那么空字可為M所接受。o NFA M所能識別的符號串的全體記為L(M)。 有NFA M =(0,1,2,3,a,b,0,3)，為：(0,a) = 0，1 (0,b) = 0(1,b) = 2 (2,b) = 3該NFA M所識別的語言為L(M) = (a|b)*abb 下列下列NFA定義的語言是什么？定義的語言是什么？413b2 a ab4確定的有窮自動機確定的有窮自動機DFA一個確定的有窮自動機確定的有窮自動機(DFA) M是一個五元組：M=(S，s0，F(xiàn))，其中:1.S是一個有窮有窮集，

24、它的每個元素稱為一個狀態(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)或結束狀態(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)

25、 輸入ab012132213333行表示狀態(tài)，列表示輸入字符，矩陣元素表示 (s，a)的值，稱為狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣。DFA的矩陣表示一個DFA可以表示成一個狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。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) = 3o DFA的確定性表現(xiàn)在：的確定性表現(xiàn)在：n 對任何狀態(tài)s S，在讀入了輸入符號a 之后，能夠唯一地確定唯一地確定下一個狀態(tài)n 映射函數(shù)：SS是一個單值單值函數(shù)n 從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個輸入字符，那末任何一個狀態(tài)結點最多有

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

27、狀態(tài)轉(zhuǎn)移到下一個狀態(tài)在初始時，讀頭處于輸在初始時，讀頭處于輸入帶的開始位置，表示入帶的開始位置，表示準備讀入，狀態(tài)處于初準備讀入，狀態(tài)處于初始狀態(tài)始狀態(tài)整個模型由三部分組成：整個模型由三部分組成： 輸入帶：存放輸入符號輸入帶：存放輸入符號 讀頭：可以在輸入帶上向后移動讀頭：可以在輸入帶上向后移動 有窮控制器：控制狀態(tài)發(fā)生變化有窮控制器：控制狀態(tài)發(fā)生變化如果讀頭移動到最后一個符號后面，如果讀頭移動到最后一個符號后面，狀態(tài)正好是終結狀態(tài)，則稱輸入帶狀態(tài)正好是終結狀態(tài)，則稱輸入帶上的符號組成的字能被該有窮自動上的符號組成的字能被該有窮自動機所識別機所識別DFA與與NFA的主要區(qū)別的主要區(qū)別o （1）

28、DFA任何狀態(tài)都沒有轉(zhuǎn)換，即沒有任何狀態(tài)可以不進行輸入符號的匹配就直接進入下一個狀態(tài)；o （2）DFA對任何狀態(tài)s和任何輸入符號a，最多只有一條標記為a的邊離開s，即轉(zhuǎn)換函數(shù)：S S是一個單值部分函數(shù)。o （3）DFA的初態(tài)唯一，NFA的初態(tài)為一集合。o DFA是NFA的特例.對每個NFA N一定存在一個DFA ，使得 L(M)=L(N)。也就是說：對每個NFA N存在著與之等價的DFA M。o 方法：（子集法）方法：（子集法）將NFA轉(zhuǎn)換成接受同樣語言的DFA。o NFA確定化的基本思路是： DFADFA的每一個狀態(tài)對應的每一個狀態(tài)對應NFA的一組狀態(tài). o DFA使用它的狀態(tài)去記錄在NFA

29、讀入一個輸入符號后可能達到的所有狀態(tài).NFA的確定化的確定化v狀態(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) 。定義定義-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,812534

30、687aaav狀態(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=?NFA的確定化的步驟的確定化的步驟o 第一步：對狀態(tài)圖進行改造第一步：對狀態(tài)圖進行改造n (1)增加狀態(tài)X,Y,使之成為新的唯一的初態(tài)和終態(tài)。從X引弧到原初態(tài)結點, 從原終態(tài)結點引弧到Y結點。o 例5：有NFA如下：o 第二步：對第二步：對NFA NFA 進行確定化，構造狀態(tài)轉(zhuǎn)換進行確

31、定化，構造狀態(tài)轉(zhuǎn)換表：表：1. = a1ak, 則初始時該表有則初始時該表有k+1列，分別列，分別為為I、Ia1 Iak，首行首列為首行首列為 -closure(X)，(X為開始結點為開始結點)；2.每行的值每行的值Iak = -closure(move(I,a)，其，其行數(shù)未知；行數(shù)未知；3.將新產(chǎn)生的將新產(chǎn)生的Iak集合加入到集合加入到I中作為新的一行，并中作為新的一行，并求該集合求該集合I的的Ia1 Iak ，重復之，直到狀態(tài)不再，重復之，直到狀態(tài)不再增加；增加；4.初態(tài)初態(tài)就是首行首列的狀態(tài)，就是首行首列的狀態(tài)，終態(tài)終態(tài)是含有原終態(tài)的是含有原終態(tài)的集合。集合。例6：將下述NFA確定化x

32、,1,2 1,2,31,2,41,2,3 1,2,3,5,6,Y1,2,41,2,4 1,2,31,2,4,5,6,Y1,2,3,5,6,Y 1,2,3,5,6,Y1,2,4,6,Y1,2,4,5,6,Y 1,2,3,6,Y1,2,4,5,6,Y1,2,4,6,Y 1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y 1,2,3,5,6,Y1,2,4,6,YSABCDEFACACFFCBBDEDDEIIaIb等價的DFA練練 習習o 求下述NFA對應的DF價的DFA為：12YX40130001DFA的化簡的化簡與某一NFA等價的DFA不一定唯一.不同的DFA識別

33、的正規(guī)集可能是相同的每一個正規(guī)集都可以由一個狀態(tài)數(shù)最少的DFA所識別，這個DFA是唯一的（因狀態(tài)名不同的同構情況除外）。DFA的最小化的最小化o DFA的最小化的最小化就是尋求狀態(tài)數(shù)最少的DFA，即：n 它沒有多余狀態(tài)；（消去）（消去）n 它的狀態(tài)中沒有兩個是互相等價的。（合并）（合并）o 多余狀態(tài)多余狀態(tài)是指：從開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。o 狀態(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的最小化的方法的最小化的方法分

34、割法分割法o 分割法的核心n 把DFA的全部狀態(tài)劃分成一些互不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的（不等價），而同一子集中的任何兩個狀態(tài)都是等價的.o 算法算法：n 所有狀態(tài)分成兩個子集終態(tài)集和非終態(tài)集；n 運用判定狀態(tài)等價的原則分別對兩個子集的狀態(tài)進行分析和劃分，若發(fā)現(xiàn)某個狀態(tài)與其它狀態(tài)不等價，則將其作為一個新的狀態(tài)子集，如果無法區(qū)分，則放在同一子集中；n 從每個子集中選出一個狀態(tài)做代表，即可構成簡化的DFA；n 含有原來初態(tài)的子集仍為初態(tài)，各終態(tài)的子集仍為終態(tài)。例：化簡下圖的例：化簡下圖的DFAo 合并狀態(tài)注意：a、由于一個子集中，各狀態(tài)等價，故只需將原進入該子集中各狀態(tài)的弧

35、都改為進入所選的狀態(tài)，子集中各狀態(tài)射出的弧均改為從該狀態(tài)射出。b、含有原來初態(tài)的子集仍為初態(tài)，含原終態(tài)的子集仍為終態(tài)練練 習習o 最小化下述DFA021abbaa01baao 正規(guī)集的各種描述工具及其相互間的轉(zhuǎn)換正規(guī)文法正規(guī)式最小的DFANFADFA正規(guī)文法與有窮自動機的等價性正規(guī)文法與有窮自動機的等價性o 定義：如果L(G)=L(M), 則正規(guī)文法正規(guī)文法G與有與有窮自動機窮自動機M的等價。的等價。o 結論：n 對每一個右(左)線性正規(guī)文法G，都存在一個有窮自動機，使L(M)=L(G)n 對每一個有窮自動機，都存在一個右(左)線性正規(guī)文法G ，使L(G)=L(M)o 正規(guī)文法有窮自動機已知正

36、規(guī)文法已知正規(guī)文法G=(VG=(VN N,V,VT T,P,S), ,P,S), 求相應的求相應的FAFA為為M =(M =(Q,VQ,VT T, ,S,F,S,F):):1.1.輸入字母表輸入字母表: : 文法的終結符號文法的終結符號VT2.2.初始狀態(tài)：初始狀態(tài)：就是開始符號就是開始符號S S3.3.狀態(tài)集合狀態(tài)集合: : 增設一個終態(tài)增設一個終態(tài)T T，以，以Q=TQ=TV VN N 為狀態(tài)結點為狀態(tài)結點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)

37、生式中的產(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,aAa,(A,a)=T,)=T,畫從畫從A A到到T T的弧，標為的弧，標為a;a; (3) (3)對于對于V VT T中的每個中的每個a a，(T,a(T,a) =) =, ,即在終態(tài)下無動作即在終態(tài)下無動作例: 已知GR =(A,B,C,D,0,1,A,P)，其中P為：A0|0B|1D B0D|1C C0|0B|1D D0D|1D練練 習習o 已知正規(guī)文法如下： 求對應的有窮自動機SaA | aAaA | bB | aB

38、 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. 終結符號終結符號: V VT T=字母表2. 開始符號開始符號：S S=初始狀態(tài)S S0 03. 非終結符號：非終結符號：VN = S4. 4. 產(chǎn)生式：產(chǎn)生式： 對任何對任何a a，A,BS,S,若有：若有：(A,a(A,a)=B)=B，則：，則：當當B B F, F, 令令AaBAaB；當當 B BF， Aa|aBAa|aB; ;若若S S0 0F，增加S S0 0 有窮自動機正規(guī)文法例:有窮自動機為：GR=(A,B,C,D,0,1,A,P)，其中P為：A0|0B|1D B0D|1C C0|0B|1D D0D|1D練習練習o 給出定義下述自動機的正規(guī)文法SABC00110011S 0A | 1C| A 0 | 0S | 1B B 1A | 0CC 1 | 1S | 0B正規(guī)式與有限自動機的等價性正規(guī)式與有限自動機的等價性正規(guī)式和有窮自動機的等價性由以下兩點說明 ： 對于上的NFA M，可以構造一個上的正規(guī)式R，使得L(R)=L(M)。 對于上的每個正規(guī)式R，可以構造一個上的NFA M，使得L(M)=L(R)。方法：