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

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

3、的，常數(shù)是符合定義的各種類型的常數(shù)o 種別碼：是對(duì)能識(shí)別的單詞的分類編碼有多種編碼方式：o 標(biāo)識(shí)符一般統(tǒng)一為一種：一個(gè)編號(hào)o 常數(shù)按類型分別編碼：整數(shù)、實(shí)數(shù)、布爾、字符o 關(guān)鍵字一般一字一種o 運(yùn)算符一般一符一種o 界符一般一符一種某語(yǔ)言單詞的種別碼定義舉例某語(yǔ)言單詞的種別碼定義舉例類別單詞種別碼類別單詞種別碼類別單詞種別碼關(guān)鍵字program1關(guān)鍵字write18標(biāo)識(shí)符id34var2true19integer3false20bool4運(yùn)算符not21常數(shù)整常數(shù)35real5and22實(shí)常數(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串: 輸出源文件中各個(gè)有用有用的單詞n 格式： (單詞的種別碼，單詞符號(hào)的屬性值單詞的種別碼，單詞符號(hào)的屬性值)n 單詞種別：是對(duì)能識(shí)別的單詞的分類編碼n 單詞符號(hào)的屬性值：?jiǎn)卧~的某種特性或特征o 常數(shù)的值，標(biāo)識(shí)符的名字等常數(shù)的值，標(biāo)識(shí)符的名字等o 保留字、運(yùn)算符、分界符的屬性值可以省保留字、運(yùn)算符、分界符的屬性值可以省略略n 文件存放最好有格式，如每個(gè)單詞占一行方便“語(yǔ)法分析”程序調(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. 符號(hào)表n 各種常數(shù)和標(biāo)識(shí)符一般放在符號(hào)表中，在輸出的token文件中的單詞屬性值則存放單詞在符號(hào)表中的指針n 符號(hào)表的格式：字符串 if (ab2) test=3;格式格式1：(數(shù)組數(shù)組)入口單詞名及長(zhǎng)度類型種屬值內(nèi)存地址1a1整簡(jiǎn)單變量未知未知2b22整簡(jiǎn)單變量未知未知3test4實(shí)簡(jiǎn)單變量未知未知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.源程序源程序 符號(hào)表符號(hào)表舉例舉例o 3. 其它輸出：錯(cuò)誤信息和源程序清單n 錯(cuò)誤信息應(yīng)該詳細(xì)，準(zhǔn)確，指出出錯(cuò)的具體行、列位置，發(fā)生了哪類錯(cuò)誤等，方便用戶修改錯(cuò)誤處理錯(cuò)誤處理o 應(yīng)盡可能發(fā)現(xiàn)更多的錯(cuò)誤o 處理方式n 每個(gè)程序段單獨(dú)處理錯(cuò)誤n 統(tǒng)一處理錯(cuò)誤（商用軟件系統(tǒng)）o 記錄式的文件o 數(shù)據(jù)庫(kù)o 統(tǒng)計(jì)表明，現(xiàn)代軟件系統(tǒng)中， 75%的程序代碼都是用于處理錯(cuò)誤與錯(cuò)誤信息o 商業(yè)系統(tǒng)中錯(cuò)誤處理的特點(diǎn)是：統(tǒng)一錯(cuò)誤編號(hào)，編制文檔指出錯(cuò)誤信息的含義、應(yīng)對(duì)措施、解決方案詞法錯(cuò)誤類型詞法錯(cuò)誤類型n 非法字符非法字符

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

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

10、符相同，最后查表n 常數(shù)的識(shí)別n 界符和算符的識(shí)別超前搜索技術(shù)：如在讀取/* */時(shí)，當(dāng)讀到/時(shí)，如何判別是注釋還是除法運(yùn)算？識(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)換圖是一張有限方向圖。有限個(gè)狀態(tài)，用結(jié)點(diǎn)表示狀態(tài)，其中有一個(gè)初態(tài)有一個(gè)初態(tài)(初態(tài)用箭頭指出)，至少有一個(gè)終態(tài)至少有一個(gè)終態(tài)(終態(tài)用雙圈表示)。狀態(tài)之間用帶箭頭的弧線連結(jié)，弧線上標(biāo)記的字符表示在射出狀態(tài)下可能出現(xiàn)的輸入字符或字符類。識(shí)別標(biāo)識(shí)符的轉(zhuǎn)換圖012字母字母或數(shù)字其它*一個(gè)狀態(tài)圖可用于識(shí)別一定的字符串，大多數(shù)程序設(shè)計(jì)語(yǔ)言的單詞符號(hào)都可以用轉(zhuǎn)換圖來識(shí)別。識(shí)

11、別過程是識(shí)別過程是：從初始狀態(tài)0開始，若讀入一個(gè)字母，轉(zhuǎn)入1狀態(tài)，若再讀入字母或數(shù)字，仍處于1狀態(tài)，否則轉(zhuǎn)向2狀態(tài)，結(jié)束一個(gè)標(biāo)識(shí)符的識(shí)別過程。狀態(tài)上的*表示多讀入一個(gè)符號(hào)。012字母字母或數(shù)字其它*寫成寫成C語(yǔ)言的函數(shù)形式：語(yǔ)言的函數(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); 回退一個(gè)符號(hào)?；赝艘粋€(gè)符號(hào)。012字母字母或數(shù)字其它*012數(shù)字?jǐn)?shù)字其它識(shí)別整數(shù)的轉(zhuǎn)換圖*練練 習(xí)習(xí) 1o 畫出Pascal中無(wú)符號(hào)實(shí)數(shù)的狀態(tài)轉(zhuǎn)換圖 (不帶正負(fù)號(hào)，可表示整數(shù)、可表示小數(shù)，可帶指數(shù)部分)o 如：下面幾個(gè)數(shù)應(yīng)該是符合規(guī)則的數(shù)： 3，3.51，34E3,34.5E2,34.5E+2,34.5E-2練練 習(xí)習(xí) 2o 畫出識(shí)別標(biāo)識(shí)符和整常數(shù)(可帶正負(fù)號(hào))的狀態(tài)轉(zhuǎn)換圖 練練 習(xí)習(xí) 3o 以下狀態(tài)轉(zhuǎn)換圖接受的字符集合是什么？以下狀態(tài)轉(zhuǎn)換圖接受的字符集合是什么？XY001狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)：使用一個(gè)switch case 語(yǔ)句：每條分支對(duì)應(yīng)一個(gè)

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

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

15、示上的正規(guī)式，表示 和和 ；2 、任何任何a ，則，則a是正規(guī)式，表示是正規(guī)式，表示a；3 、假定、假定r和和s都是都是 上的正規(guī)式，分別表示語(yǔ)言上的正規(guī)式，分別表示語(yǔ)言 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、有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集正規(guī)集。 或或； 連接；連接； 閉包閉包

16、 規(guī)定優(yōu)先順序?yàn)橐?guī)定優(yōu)先順序?yàn)椤?”、“ ”、“ ” (a)|(b)*(c)a|b*c例1：令=a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集有：正規(guī)式正規(guī)集aaba*所有以b開頭后跟任意多個(gè)a的串a(chǎn)ba,babab(ab)(ab)aa,ab,ba,bba ,a,aa, 任意個(gè)a的串(ab) ,a,b,aa,ab 所有由a 或b組成的串(a|b)*(aa|bb)(a|b)*所有含有兩個(gè)相繼的a或兩個(gè)相繼的b的串程序設(shè)計(jì)語(yǔ)言的單詞都能用正規(guī)式來定義程序設(shè)計(jì)語(yǔ)言的單詞都能用正規(guī)式來定義. .例2：令=l，d，l 代表字母,d 代表數(shù)字,則上的正規(guī)式: r = l(ld) 定義的正規(guī)集為: l,ll,ld,ll

17、l,ldd,就是Pascal和 多數(shù)程序設(shè)計(jì)語(yǔ)言允許的的標(biāo)識(shí)符的詞法規(guī)則。例3：令d， ，e，其中d為09中的數(shù)字。則上的正規(guī)式: d*(.dd*| )(e(+|-|)dd*|) 表示PASCAL語(yǔ)言中的無(wú)符號(hào)實(shí)數(shù)。 比如：2, 12.59, 3.6e2, 471.88e-1等都是正規(guī)式表示集合中的元素。練練 習(xí)習(xí)1、 =a,b，則，則 上所有以上所有以b開頭，后跟若開頭，后跟若干個(gè)干個(gè)ab的字的全體所對(duì)應(yīng)的正規(guī)式。的字的全體所對(duì)應(yīng)的正規(guī)式。2、 =a,b，寫出不以，寫出不以a開頭，但以開頭，但以aa結(jié)結(jié)尾的字符串集合的正規(guī)式。尾的字符串集合的正規(guī)式。b(a|b)*aab(ab)*o 思考題：

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

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* 三、有窮自動(dòng)機(jī)三、有窮自動(dòng)機(jī)o 有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語(yǔ)言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。 o 有窮自動(dòng)機(jī)分為兩類：n確定的有窮自動(dòng)機(jī)(DFA:Deterministic Finite Automata)n不確定的有窮自動(dòng)機(jī)(NFA:Nondeterministic Finite

20、 Automata)不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)NFAo 定義定義：不確定的有窮自動(dòng)機(jī)NFA也是一個(gè)五元組， M=S，s0，F(xiàn) ，其中： S為有窮有窮狀態(tài)集， 為有窮有窮輸入字母表， 為S * 到S的冪集冪集(2S)的一種映射:S * 2S s0 S是初始狀態(tài)集初始狀態(tài)集， F S為終止?fàn)顟B(tài)集(可空)。NFA的三種表示法o 1. 給出NFA的五個(gè)部分的具體值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)圖表示一個(gè)含有m個(gè)狀態(tài)，n個(gè)輸入字符的NFA的狀態(tài)轉(zhuǎn)換圖：有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可射出若干條若干條弧與別的結(jié)點(diǎn)相連接，每條弧用一個(gè)輸入符號(hào)或來標(biāo)記表示(這些字可以相同，也可以是)。整個(gè)圖至少有一個(gè)初始結(jié)點(diǎn)至少有一個(gè)初始結(jié)點(diǎn)以及若干個(gè)若干個(gè)(可以是可以是0個(gè)個(gè))終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn)，某些結(jié)點(diǎn)既可以是初態(tài)結(jié)點(diǎn)，又可以是終態(tài)結(jié)點(diǎn)。(S，0)=P(S，1)=S，Z(Z，0)=P(Z，1)=P(P，1)=ZSPZ00,1111NFA的特點(diǎn)是它的不確定性不確定性，即在當(dāng)前狀態(tài)下，讀入同一個(gè)符號(hào)，可能有多個(gè)下一狀態(tài)：n 在NFA的定義中，就是函數(shù)是一對(duì)多的；n 反映在狀態(tài)轉(zhuǎn)換圖中，就是從

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

23、某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)；或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的道路,其上所有弧的標(biāo)記均為，那么空字可為M所接受。o NFA M所能識(shí)別的符號(hào)串的全體記為L(zhǎng)(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所識(shí)別的語(yǔ)言為L(zhǎng)(M) = (a|b)*abb 下列下列NFA定義的語(yǔ)言是什么？定義的語(yǔ)言是什么？413b2 a ab4確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)DFA一個(gè)確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)(DFA) M是一個(gè)五元組：M=(S，s0，F(xiàn))，其中:1.S是一個(gè)有窮有窮集，

24、它的每個(gè)元素稱為一個(gè)狀態(tài)；2.是一個(gè)有窮有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為輸入符號(hào)表；3.是轉(zhuǎn)換函數(shù)，是在SS上的單值單值映射， (s，a)=s (sS，sS) ，就意味著，當(dāng)前狀態(tài)為s，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)s，我們把s稱作s的一個(gè)后繼狀態(tài)；4. s0 S是唯一唯一的一個(gè)初態(tài)；5.FS是一個(gè)終態(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)

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

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

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

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

29、讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(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)任意條 弧而能到達(dá)的狀態(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弧而到達(dá)的狀態(tài)的全體。I=1, J=move(I,a) = 5, 4 ; Ia= -closure(5, 4)=2,4,5,6,7I=1,2, Ia=?NFA的確定化的步驟的確定化的步驟o 第一步：對(duì)狀態(tài)圖進(jìn)行改造第一步：對(duì)狀態(tài)圖進(jìn)行改造n (1)增加狀態(tài)X,Y,使之成為新的唯一的初態(tài)和終態(tài)。從X引弧到原初態(tài)結(jié)點(diǎn), 從原終態(tài)結(jié)點(diǎn)引弧到Y(jié)結(jié)點(diǎn)。o 例5：有NFA如下：o 第二步：對(duì)第二步：對(duì)NFA NFA 進(jìn)行確定化，構(gòu)造狀態(tài)轉(zhuǎn)換進(jìn)行確

31、定化，構(gòu)造狀態(tài)轉(zhuǎn)換表：表：1. = a1ak, 則初始時(shí)該表有則初始時(shí)該表有k+1列，分別列，分別為為I、Ia1 Iak，首行首列為首行首列為 -closure(X)，(X為開始結(jié)點(diǎn)為開始結(jié)點(diǎn))；2.每行的值每行的值Iak = -closure(move(I,a)，其，其行數(shù)未知；行數(shù)未知；3.將新產(chǎn)生的將新產(chǎn)生的Iak集合加入到集合加入到I中作為新的一行，并中作為新的一行，并求該集合求該集合I的的Ia1 Iak ，重復(fù)之，直到狀態(tài)不再，重復(fù)之，直到狀態(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等價(jià)的DFA練練 習(xí)習(xí)o 求下述NFA對(duì)應(yīng)的DF價(jià)的DFA為：12YX40130001DFA的化簡(jiǎn)的化簡(jiǎn)與某一NFA等價(jià)的DFA不一定唯一.不同的DFA識(shí)別

33、的正規(guī)集可能是相同的每一個(gè)正規(guī)集都可以由一個(gè)狀態(tài)數(shù)最少的DFA所識(shí)別，這個(gè)DFA是唯一的（因狀態(tài)名不同的同構(gòu)情況除外）。DFA的最小化的最小化o DFA的最小化的最小化就是尋求狀態(tài)數(shù)最少的DFA，即：n 它沒有多余狀態(tài)；（消去）（消去）n 它的狀態(tài)中沒有兩個(gè)是互相等價(jià)的。（合并）（合并）o 多余狀態(tài)多余狀態(tài)是指：從開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。o 狀態(tài)狀態(tài)S和和T等價(jià)等價(jià)的條件的條件 一致性條件 狀態(tài)S和T必須同時(shí)為可接受狀態(tài)或不可接受狀態(tài)。 蔓延性條件 對(duì)于所有輸入符號(hào)，狀態(tài)S和狀態(tài)T必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。DFA的最小化的方法的最小化的方法分

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

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

36、規(guī)文法已知正規(guī)文法G=(VG=(VN N,V,VT T,P,S), ,P,S), 求相應(yīng)的求相應(yīng)的FAFA為為M =(M =(Q,VQ,VT T, ,S,F,S,F):):1.1.輸入字母表輸入字母表: : 文法的終結(jié)符號(hào)文法的終結(jié)符號(hào)VT2.2.初始狀態(tài)：初始狀態(tài)：就是開始符號(hào)就是開始符號(hào)S S3.3.狀態(tài)集合狀態(tài)集合: : 增設(shè)一個(gè)終態(tài)增設(shè)一個(gè)終態(tài)T T，以，以Q=TQ=TV VN N 為狀態(tài)結(jié)點(diǎn)為狀態(tài)結(jié)點(diǎn)4.4.終態(tài)集合：終態(tài)集合：若若P P中含有中含有S S的產(chǎn)生式，則的產(chǎn)生式，則F=T,SF=T,S，否則，否則F=TF=T5. 5. 的計(jì)算方法的計(jì)算方法 (1)(1)對(duì)對(duì)P P中的產(chǎn)

37、生式中的產(chǎn)生式AaB,(A,aAaB,(A,a)=B,)=B, 畫從畫從A A到到B B的弧，標(biāo)為的弧，標(biāo)為a a； (2)(2)對(duì)對(duì)P P中的產(chǎn)生式中的產(chǎn)生式Aa,(A,aAa,(A,a)=T,)=T,畫從畫從A A到到T T的弧，標(biāo)為的弧，標(biāo)為a;a; (3) (3)對(duì)于對(duì)于V VT T中的每個(gè)中的每個(gè)a a，(T,a(T,a) =) =, ,即在終態(tài)下無(wú)動(dòng)作即在終態(tài)下無(wú)動(dòng)作例: 已知GR =(A,B,C,D,0,1,A,P)，其中P為：A0|0B|1D B0D|1C C0|0B|1D D0D|1D練練 習(xí)習(xí)o 已知正規(guī)文法如下： 求對(duì)應(yīng)的有窮自動(dòng)機(jī)SaA | aAaA | bB | aB

38、 bB | bSABTaaababb已知已知DFADFA為為M =(S,M =(S, ,S,S0 0,F),F),求相應(yīng)的正規(guī)文法求相應(yīng)的正規(guī)文法( (右線性右線性) ) G=(G=(,S,S,S,S0 0,P),P)的方法的方法: :1. 1. 終結(jié)符號(hào)終結(jié)符號(hào): V VT T=字母表2. 開始符號(hào)開始符號(hào)：S S=初始狀態(tài)S S0 03. 非終結(jié)符號(hào)：非終結(jié)符號(hào)：VN = S4. 4. 產(chǎn)生式：產(chǎn)生式： 對(duì)任何對(duì)任何a a，A,BS,S,若有：若有：(A,a(A,a)=B)=B，則：，則：當(dāng)當(dāng)B B F, F, 令令A(yù)aBAaB；當(dāng)當(dāng) B BF， Aa|aBAa|aB; ;若若S S0 0F，增加S S0 0 有窮自動(dòng)機(jī)正規(guī)文法例:有窮自動(dòng)機(jī)為：GR=(A,B,C,D,0,1,A,P)，其中P為：A0|0B|1D B0D|1C C0|0B|1D D0D|1D練習(xí)練習(xí)o 給出定義下述自動(dòng)機(jī)的正規(guī)文法SABC00110011S 0A | 1C| A 0 | 0S | 1B B 1A | 0CC 1 | 1S | 0B正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性由以下兩點(diǎn)說明 ： 對(duì)于上的NFA M，可以構(gòu)造一個(gè)上的正規(guī)式R，使得L(R)=L(M)。 對(duì)于上的每個(gè)正規(guī)式R，可以構(gòu)造一個(gè)上的NFA M，使得L(M)=L(R)。方法：