編譯原理課程之詞法分析

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

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

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

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

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

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

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

10、符相同，最后查表 常數(shù)的識(shí)別 界符和算符的識(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ì)語言的單詞符號(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語言的函數(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; brea

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

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

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

15、規(guī)集的遞歸定義：（設(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、達(dá)式才是上的正規(guī)式正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集正規(guī)集。 或或； 連接；連接； 閉包閉包 規(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ì)語言的單詞都能用正規(guī)式來定義程序設(shè)計(jì)語言的單詞都能用正規(guī)式來定義. .例2：令=l

17、，d，l 代表字母,d 代表數(shù)字,則上的正規(guī)式: r = l(ld) 定義的正規(guī)集為: l,ll,ld,lll,ldd,就是Pascal和 多數(shù)程序設(shè)計(jì)語言允許的的標(biāo)識(shí)符的詞法規(guī)則。例3：令d， ，e，其中d為09中的數(shù)字。則上的正規(guī)式: d*(.dd*| )(e(+|-|)dd*|) 表示PASCAL語言中的無符號(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開頭，但以

18、開頭，但以aa結(jié)結(jié)尾的字符串集合的正規(guī)式。尾的字符串集合的正規(guī)式。b(a|b)*aab(ab)* 思考題：思考題： =d，. ，則，則 上表示上表示無符號(hào)數(shù)無符號(hào)數(shù)的正規(guī)式是的正規(guī)式是什么？（什么？（不考慮含不考慮含e的科學(xué)計(jì)數(shù)法，的科學(xué)計(jì)數(shù)法，其中其中d為為09的數(shù)字）的數(shù)字） 如：如：2 ，12.59 ，471.88等都是該集等都是該集合中的元素。合中的元素。 dd dd* *(.dd(.dd* *| | ) )正規(guī)式的等價(jià)正規(guī)式的等價(jià) 若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同,則e1和e2等價(jià)等價(jià),寫作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* 三、有窮自動(dòng)機(jī)三、有窮自動(dòng)機(jī) 有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。 有窮自動(dòng)機(jī)分為兩類： 確定的有窮自動(dòng)機(jī)(Deterministic Finite Automata) 不確

20、定的有窮自動(dòng)機(jī)(Nondeterministic Finite Automata)確定的有窮自動(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è)有窮有窮集，它的每個(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)集集( (可空可空) )，也稱可接受狀

21、態(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的矩陣表示一個(gè)DFA可以表示成一個(gè)狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。假定DFA M含有m個(gè)狀態(tài)，n個(gè)輸入字符，那么這個(gè)狀態(tài)圖含有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有n個(gè)弧射出，整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)(可以是0個(gè))終態(tài)結(jié)點(diǎn)，初態(tài)結(jié)點(diǎn)冠以雙箭頭“=

22、” ，終態(tài)結(jié)點(diǎn)用雙圈表示，若 (ki,a) =kj，則從狀態(tài)結(jié)點(diǎn)ki到狀態(tài)結(jié)點(diǎn)kj畫標(biāo)記為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)在： 對(duì)任何狀態(tài)s S，在讀入了輸入符號(hào)a 之后，能夠唯一地確定唯一地確定下一個(gè)狀態(tài) 映射函數(shù)：SS是一個(gè)單值單值函數(shù) 從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有最多有n條條弧射出弧射出，而且每條弧以一個(gè)不同的輸入字符不同的輸入字符標(biāo)記。 字可為DFA M所接

23、受（識(shí)別）： 對(duì)于* 中的任何字，若存在一條從初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符號(hào)連接成的字等于。 若M的初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，則空字可為M所識(shí)別。 DFA M所能識(shí)別的符號(hào)串的全體記為L(M). 對(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è)狀態(tài)轉(zhuǎn)移到下一個(gè)狀態(tài)在初始時(shí)，讀頭處于輸在初始時(shí)，讀頭處于輸入帶的開始位置，表示入帶的開始位置，表示準(zhǔn)備讀

24、入，狀態(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í)別 結(jié)論： 上一個(gè)符號(hào)串集V 是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的確定有窮自動(dòng)機(jī)M，使得V=L(M)。文法和自動(dòng)機(jī)的對(duì)比文法和自動(dòng)機(jī)的對(duì)比 文法是語言的生成系統(tǒng)

25、，是從產(chǎn)生的觀點(diǎn)來描述語言的。 自動(dòng)機(jī)是語言的識(shí)別系統(tǒng)，是從識(shí)別的觀點(diǎn)來描述語言的不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)NFA 定義定義：不確定的有窮自動(dòng)機(jī)NFA也是一個(gè)五元組， M=S，s0，F(xiàn) ，其中： S為狀態(tài)的有窮有窮狀態(tài)集， 為有窮有窮輸入字母表， 為S * 到S的冪集冪集(2S)的一種映射:S * 2S s0 S是初始狀態(tài)集初始狀態(tài)集， F S為終止?fàn)顟B(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、出，表項(xiàng)是狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)狀態(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è)字來表示(這些字可以相同，也可以是)。整個(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,1111*上的符號(hào)串t被NFA M接受（識(shí)別）: 對(duì)于*中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所

27、有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為的弧)等于t，則稱t可為NFA M所識(shí)別(讀出或接受)。 若M的某些結(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所接受。4 例例2：13a2a b接受串接受串a(chǎn)bb的移動(dòng)序列的移動(dòng)序列:-12424abb -1342424bba -轉(zhuǎn)換（轉(zhuǎn)換（ -transition）:是無需考慮輸入串是無需考慮輸入串就有可能發(fā)生的轉(zhuǎn)換。就有可能發(fā)生的轉(zhuǎn)換。例例3:下列下列NFA定義的語言是什么？定義的語言是什么？413b2 a ab4NFA M所能接受的符號(hào)串的全體記為L(M)結(jié)論： 上一個(gè)符號(hào)

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

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

30、, 從原終態(tài)結(jié)點(diǎn)引弧到Y(jié)結(jié)點(diǎn)。 (2) 對(duì)狀態(tài)圖進(jìn)一步進(jìn)行如下形式的改變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對(duì)應(yīng)的DFA（完成第一步）01(0|1)*002YX40130001 上述NFA帶有弧，稱為具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī) 對(duì)任何一個(gè)具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFA N，一定存在一個(gè)不具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)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)任意條 弧而能到達(dá)的狀態(tài)q -closure(I) 。 第二步：對(duì)上述改造后的第二步：對(duì)上述改造后的NFA進(jìn)行確定化進(jìn)行確定化-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弧而到達(dá)的狀態(tài)的全體。I=1, J=move(I,a) = 5, 4 ; Ia= -closure(5, 4)=2,4,5,6,7I=1,2, Ia=?v對(duì)對(duì)NFA NFA 進(jìn)行確定化，構(gòu)造狀態(tài)轉(zhuǎn)換表：進(jìn)行確定化，構(gòu)造狀態(tài)轉(zhuǎn)換表：對(duì)對(duì) = a1ak, 構(gòu)造一個(gè)構(gòu)造一個(gè)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)若某行的第一列的狀態(tài)已確定為若某行的第一列的狀態(tài)已確定為I，則計(jì)算第，則計(jì)算第i+1（i=1,2,k）列的值）列的值為為Iai。 -closure(X)Ia1Ia2Iak列列1列列2(a1)列列3(a2).列列K+1(aK)檢查第檢查第2步所創(chuàng)建的該行上的所有狀態(tài)子集，步所創(chuàng)建的該行上的所有狀態(tài)子集，看它是否已在第一列出現(xiàn)，若未出現(xiàn)，將其看它是否已在第一列出現(xiàn)，若未出現(xiàn)，將其添加到后面的空行上添加到后面的

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

35、k例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等價(jià)的DFAaCDBAEFSbaaaaabbbbbabF練練 習(xí)習(xí) 求下述NFA對(duì)應(yīng)的DFA(完成第二步，確定化)01(0

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

37、受狀態(tài)。 蔓延性條件 對(duì)于所有輸入符號(hào)，狀態(tài)S和狀態(tài)T必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。DFA的最小化的方法的最小化的方法分割法分割法分割法的核心 把DFA的全部狀態(tài)劃分成一些互不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的（不等價(jià)），而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的. 算法算法： 所有狀態(tài)分成兩個(gè)子集終態(tài)集和非終態(tài)集； 運(yùn)用判定狀態(tài)等價(jià)的原則分別對(duì)兩個(gè)子集的狀態(tài)進(jìn)行分析和劃分，若發(fā)現(xiàn)某個(gè)狀態(tài)與其它狀態(tài)不等價(jià)，則將其作為一個(gè)新的狀態(tài)子集，如果無法區(qū)分，則放在同一子集中； 從每個(gè)子集中選出一個(gè)狀態(tài)做代表，即可構(gòu)成簡化的DFA； 含有原來初態(tài)的子集仍為初態(tài)，各終態(tài)的子集仍為終態(tài)。DBASaaabb

38、bba,CDBAEFSbaaaaaabbbbbba例：化簡下圖的例：化簡下圖的DFA 合并狀態(tài)注意：a、由于一個(gè)子集中，各狀態(tài)等價(jià)，故只需將原進(jìn)入該子集中各狀態(tài)的弧都改為進(jìn)入所選的狀態(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ī)文法與有窮自動(dòng)機(jī)的等價(jià)性正規(guī)文法與有窮自動(dòng)機(jī)的等價(jià)性 定義：如果L(G)=L(M), 則正規(guī)文法正規(guī)文法G與有與有窮自動(dòng)機(jī)窮自動(dòng)機(jī)M的等價(jià)。的等價(jià)。

39、結(jié)論： 對(duì)每一個(gè)右(左)線性正規(guī)文法G，都存在一個(gè)有窮自動(dòng)機(jī)，使L(M)=L(G) 對(duì)每一個(gè)有窮自動(dòng)機(jī)，都存在一個(gè)右(左)線性正規(guī)文法G ，使L(G)=L(M) 正規(guī)文法有窮自動(dòng)機(jī)(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é)符號(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)

40、為狀態(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)生式中的產(chǎn)生式AaB,(A,a)=B,AaB,(A,a)=B, 畫從畫從A A到到B B的弧，標(biāo)為的弧，標(biāo)為a a； (2)(2)對(duì)對(duì)P P中的產(chǎn)生式中的產(chǎn)生式Aa,(A,a)=T,Aa,(A,a)=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)下無動(dòng)作。即在

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

42、 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)=B(A,a)=B，則：，則：當(dāng)當(dāng)B B F, F, 令令A(yù)aBAaB；當(dāng)當(dāng) B BF， Aa|aB;Aa|aB;若若S S0 0F，增加S S0 0 有窮自動(dòng)機(jī)正規(guī)文法例:有窮自動(dòng)機(jī)為：練習(xí)練習(xí) 給出定義下述自動(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