編譯原理第4章

1、n詞法分析是翻譯的第一階段，是語法分析詞法分析是翻譯的第一階段，是語法分析的必要準備。詞法分析程序也稱為掃描程的必要準備。詞法分析程序也稱為掃描程序或掃描器（序或掃描器（scannerscanner）。）。n詞法分析是編譯過程中的一個階段，可以詞法分析是編譯過程中的一個階段，可以在語法分析前進行在語法分析前進行 。也可以和語法分析結(jié)。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當前單詞供語法分析詞法分析程序來獲得當前單詞供語法分析使用。使用。實現(xiàn)方式實現(xiàn)方式 作為單獨的一遍作為單獨的一遍 字符序列字符序列 單詞序列單詞序列掃描器掃

2、描器語法分析器語法分析器 . . .作為子程序作為子程序源程序詞法分析程序語法分析程序Tokenget tokenn詞法分析程序的主要任務：詞法分析程序的主要任務：- 讀源程序，產(chǎn)生單詞符號詞法分析程序的其他任務：詞法分析程序的其他任務：- 濾掉空格，跳過注釋、換行符- 追蹤換行標志，復制出錯源程序，- 宏展開， 單詞類別及其輸出形式單詞類別及其輸出形式 單詞可作各種分類，典型地分為類：單詞可作各種分類，典型地分為類：保留字保留字 AND,BEGIN,FOR,TYPE,VARAND,BEGIN,FOR,TYPE,VAR等等標識符標識符 用戶定義的常量、類型、變量、用戶定義的常量、類型、變量、過

3、程名過程名常量常量12, 1997, 4.14, 12, 1997, 4.14, A, A, 等等運算符，運算符， ，,!=,#,!=,#等等界限符；，（）等界限符；，（）等n詞法分析程序所輸出的單詞符號常常采用詞法分析程序所輸出的單詞符號常常采用以下二元式表示：以下二元式表示： ( (單詞種別，單詞自身的值單詞種別，單詞自身的值) )。n單詞的種別是語法分析需要的信息，而單單詞的種別是語法分析需要的信息，而單詞自身的值則是編譯其它階段需要的信息。詞自身的值則是編譯其它階段需要的信息。比如在PASCAL的語句const i=25, yes=1；中的單詞 25和1的種別都是常數(shù)，常數(shù)的值常數(shù)的值

4、2525和和1 1對于代碼生成來說，是必不可少的。對于代碼生成來說，是必不可少的。有時，對某些單詞來說，不僅僅需要它的值，還需有時，對某些單詞來說，不僅僅需要它的值，還需要其它一些信息以便編譯的進行。要其它一些信息以便編譯的進行。比如，對于標識符來說，還需要記載它的類別、層比如，對于標識符來說，還需要記載它的類別、層次還有其它屬性，如果這些屬性統(tǒng)統(tǒng)收集在符號次還有其它屬性，如果這些屬性統(tǒng)統(tǒng)收集在符號表中，那么可以將單詞的二元式表示設(shè)計成如下表中，那么可以將單詞的二元式表示設(shè)計成如下形式形式( (標識符，指向該標識符所在符號表中位置的指針標識符，指向該標識符所在符號表中位置的指針) )如上述語句

5、中的單詞i和yes的表示為：(標識符，指向i的表項的指針)(標識符，指向yes的表項的指針)詞法分析程序的輸出形式詞法分析程序的輸出形式-二元式二元式單詞類別單詞類別 單詞的屬性值單詞的屬性值單詞類別可以用整數(shù)編碼表示單詞類別可以用整數(shù)編碼表示: :一類一種或一字一種一類一種或一字一種單詞類別單詞類別關(guān)鍵字關(guān)鍵字標識符標識符常數(shù)常數(shù)運算符運算符分界符分界符編碼編碼1 12 23 34 45 5單詞類別單詞類別單詞的屬性值單詞的屬性值1int2指向指向x的符號表入口指針的符號表入口指針4=3105,2指向指向y的符號表入口指針的符號表入口指針4=3205,2指向指向sum的符號表入口指針的符號表

6、入口指針5; int x=10,y=20,sum;詞法分析的結(jié)果詞法分析的結(jié)果 n程序段程序段 if i=5 then x=yif i=5 then x=y；在經(jīng)詞法分析器掃在經(jīng)詞法分析器掃描后輸出的單詞符號和它們的表示如下：描后輸出的單詞符號和它們的表示如下：- - 保留字保留字if(3if(3，if)if)- - 標識符標識符i(1i(1，指向指向i i的符號表入口的符號表入口) )- - 等號等號=(4=(4，=)=)- - 常數(shù)常數(shù)5(25(2，5)5)- - 保留字保留字then(3then(3，then)then)- - 標識符標識符x(1x(1，指向指向x x的符號表入口的符號表

7、入口) )- - 賦值號賦值號=(4=(4，=) =) - - 標識符標識符 y(1y(1，指向指向y y的符號表入口的符號表入口) )- - 分號；分號；(5(5， ；) ) 詞法分析在實際操作中：n 對于每種語言，保留字、運算符和界限符對于每種語言，保留字、運算符和界限符是固定的，可以是固定的，可以“一字一類一字一類”或或“一符一一符一類類”，預先造好標準單詞表。，預先造好標準單詞表。單詞單詞內(nèi)部編碼內(nèi)部編碼單詞單詞內(nèi)部編碼內(nèi)部編碼IF324THEN425ELSE5*26FOR1934例如：例如：n 常數(shù)雖然也是固定的，但個數(shù)太多，而每常數(shù)雖然也是固定的，但個數(shù)太多，而每個程序只用很少一部

8、分，不宜預先造表。個程序只用很少一部分，不宜預先造表。編譯只對源程序中出現(xiàn)的各類常量造表，編譯只對源程序中出現(xiàn)的各類常量造表，如整數(shù)表、實數(shù)表、字符串表等。如整數(shù)表、實數(shù)表、字符串表等。 例如，整數(shù)表例如，整數(shù)表IntTabIntTab存放源程序中的整常存放源程序中的整常數(shù)數(shù), ,掃描器拼出整數(shù)時，查掃描器拼出整數(shù)時，查IntTabIntTab表，若無表，若無此數(shù)，則填入表中；若已有此數(shù)，則不在此數(shù)，則填入表中；若已有此數(shù)，則不在填入，而把該數(shù)在表中的地址填入，而把該數(shù)在表中的地址intpintp作為其作為其機內(nèi)碼的一部分，由它聯(lián)系機內(nèi)碼和數(shù)值。機內(nèi)碼的一部分，由它聯(lián)系機內(nèi)碼和數(shù)值。 n標識符

9、的意義是由用戶定義的，與常量類標識符的意義是由用戶定義的，與常量類似，編譯器也構(gòu)造一個標識符表似，編譯器也構(gòu)造一個標識符表IdTabIdTab。每每識別出一個標識符，則查識別出一個標識符，則查IdTabIdTab表，若無則表，若無則填入，已有則不填，用其在表中的地址填入，已有則不填，用其在表中的地址idpidp作為聯(lián)系機內(nèi)碼和自身值的橋梁。作為聯(lián)系機內(nèi)碼和自身值的橋梁。 詞法分析工作從語法分析工作獨立出來的原因：詞法分析工作從語法分析工作獨立出來的原因：(P48)簡化設(shè)計簡化設(shè)計改進編譯效率改進編譯效率增加編譯系統(tǒng)的可移植性增加編譯系統(tǒng)的可移植性 PL/0詞法分析的設(shè)計與實現(xiàn)：PL/0PL/0

10、編譯程序的詞法分析編譯程序的詞法分析 nPL/0PL/0的詞法分析程序的詞法分析程序GETSYM(P15GETSYM(P15圖圖2.5)2.5)是一個獨立是一個獨立的過程，其功能是為語法分析提供單詞用的，是語的過程，其功能是為語法分析提供單詞用的，是語法分析的基礎(chǔ)，它把輸入的字符串形式的源程序分法分析的基礎(chǔ)，它把輸入的字符串形式的源程序分割成一個個單詞符號。為此割成一個個單詞符號。為此PL/0PL/0編譯程序設(shè)置了三編譯程序設(shè)置了三個全程量的公用單元如下個全程量的公用單元如下：SYMSYM：存放每個單詞的類別，用內(nèi)部編碼形式表示存放每個單詞的類別，用內(nèi)部編碼形式表示 IDID： 存放用戶所定義

11、的標識符的值。存放用戶所定義的標識符的值。NUMNUM：存放用戶定義的數(shù)。存放用戶定義的數(shù)。n單詞的種類有五種單詞的種類有五種?；咀郑夯咀郑阂部煞Q為保留字或關(guān)鍵字，如BEGIN，END，IF，THEN等。運算符：運算符：如：+、-、*、=、#、=、=等。標識符：標識符：用戶定義的變量名、常數(shù)名、過程名。常數(shù)：常數(shù)：如：10，25，100等整數(shù)。界符：界符：如：，、.、；、(、)等。圖圖 2.5 詞法分析過程詞法分析過程GETSYM nPL/0編譯程序文本中主程序開始對關(guān)鍵字表置初編譯程序文本中主程序開始對關(guān)鍵字表置初值如下（值如下（P304 P304 ） ：關(guān)鍵字表為關(guān)鍵字表為：word1

12、:=begin ；word2:=call ；.word13:=write ；查到時找到關(guān)鍵字相應的內(nèi)部表示為：查到時找到關(guān)鍵字相應的內(nèi)部表示為：Wsym1:=beginsym; wsym2:=callsym；wsym13:=writesym；PL/0PL/0編譯程序文本中開始對類型的定義中給出單詞定義編譯程序文本中開始對類型的定義中給出單詞定義（見附錄）：（見附錄）：Type symbol=(nul,ident,number,plus,varsym, procsym)；定義單詞是純量/枚舉類型，又定義了3個全程量為： sym: symbol;id: alfa;num: integer; alf

13、a=packed array1.a1 of char;n因此詞法分析程序因此詞法分析程序GETSYMGETSYM將完成下列任務：將完成下列任務：(1) (1) 濾空格濾空格：空格在詞法分析時是一種不可：空格在詞法分析時是一種不可缺少的界符，而在語法分析時則是無用的，所以缺少的界符，而在語法分析時則是無用的，所以必須濾掉。必須濾掉。(2) (2) 識別保留字識別保留字：設(shè)有一張保留字表。對每：設(shè)有一張保留字表。對每個字母打頭后接字母或數(shù)字的字符串要查此表。個字母打頭后接字母或數(shù)字的字符串要查此表。若查著則為保留字，將對應的類別放在若查著則為保留字，將對應的類別放在SYMSYM中。中。如如IFIF

14、對應值對應值IFSYMIFSYM，THENTHEN對應值為對應值為THENSYMTHENSYM。若查若查不著，則認為是用戶定義的標識符。不著，則認為是用戶定義的標識符。(3) (3) 識別標識符識別標識符：對用戶定義的標識符將：對用戶定義的標識符將IDENTIDENT放在放在SYMSYM中，標識符本身的值放在中，標識符本身的值放在IDID中。中。(4) (4) 拼數(shù)拼數(shù)：當所取單詞是數(shù)字時，將數(shù)的類別：當所取單詞是數(shù)字時，將數(shù)的類別NUMBERNUMBER放在放在SYMSYM中，數(shù)值本身的值存放在中，數(shù)值本身的值存放在NUMNUM中。中。注意：注意：SYMSYM是純量是純量/ /枚舉類型枚舉類

15、型 sym: symbol; sym: symbol;Type symbol=(nul,ident,number,plus,Type symbol=(nul,ident,number,plus, varsym,procsym varsym,procsym)；(5) (5) 拼復合詞拼復合詞：對兩個字符組成的算符：對兩個字符組成的算符 如：如：= =、=、= = 等單詞，識別等單詞，識別 后將類別送后將類別送SYMSYM中。中。(6) (6) 輸出源程序輸出源程序：為邊讀入字符邊輸出：為邊讀入字符邊輸出( (可可輸出在文件中輸出在文件中) )。PL/0PL/0的詞法分析程序（見附錄）的詞法分析程

16、序（見附錄）單詞的描述工具n正規(guī)文法 多數(shù)程序設(shè)計語言的單詞語法都能用正規(guī)文法（3型文法）來描述例如：程序設(shè)計語言中的單詞可用下列規(guī)則描述：例如：程序設(shè)計語言中的單詞可用下列規(guī)則描述：程序設(shè)計語言中的幾類單詞可用下述規(guī)則描述：程序設(shè)計語言中的幾類單詞可用下述規(guī)則描述：標識符 l | l字母數(shù)字字母數(shù)字 l|d|l字母數(shù)字|d字母數(shù)無符號整數(shù) d|d無符號整數(shù)運算符+ | - | * | / | =| 界符 ，|；| ( | ) |其中l(wèi)表示az中的任何一英文字母， d表示09中的任一數(shù)字。n正規(guī)式正規(guī)式正規(guī)式也稱正則表達式,正規(guī)表達式也是用以描述單詞符號的方便工具。字母表字母表 , , 定義在

17、定義在 上的正規(guī)式和正規(guī)集遞歸定義如下上的正規(guī)式和正規(guī)集遞歸定義如下: :1.1. 和和 都是都是 上的正規(guī)式上的正規(guī)式, , 它們所表示的正規(guī)集分別為它們所表示的正規(guī)集分別為: 和和 ; ;2. 2. 任何任何a a , a , a是是 上的正規(guī)式上的正規(guī)式, ,它所表示的正規(guī)集為它所表示的正規(guī)集為:a; a; 3. 3. 假定假定e1e1和和e2e2是是 上的正規(guī)式上的正規(guī)式, , 它們所表示的正規(guī)集分別記為它們所表示的正規(guī)集分別記為L(e1)L(e1) 和和L(e2), L(e2), 那么那么e1|e2, e1e2e1|e2, e1e2和和e1e1* *也都是也都是 上的正規(guī)式上的正規(guī)式

18、, , 它們所表示的它們所表示的 正規(guī)集分別為正規(guī)集分別為L(e1) L(e1) L(e2)L(e2)、 L(e1) L(e2) L(e1) L(e2)和和( (L(e1)L(e1)* *4. 4. 任何任何 上的正規(guī)式和正規(guī)集均由上的正規(guī)式和正規(guī)集均由1 1、2 2和和3 3產(chǎn)生。產(chǎn)生。正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集正規(guī)式中的運算符：正規(guī)式中的運算符： | -或（選擇）或（選擇） -連接連接 * 或或 -重復重復 （）（） -括號括號運算符的優(yōu)先級：運算符的優(yōu)先級： 先先*, 后后 , 最后最后 | 在正規(guī)式中可以省略在正規(guī)式中可以省略.運算符的結(jié)合方向：運算符的結(jié)合方向： 從左到右結(jié)合。從左

19、到右結(jié)合。正規(guī)式相等正規(guī)式相等 這兩個正規(guī)式表示的語言相等這兩個正規(guī)式表示的語言相等例子正規(guī)式正規(guī)式正規(guī)集正規(guī)集ba*所有以所有以b為首后跟任意多個為首后跟任意多個a的符號串的符號串a(chǎn)(a|b)*所有以所有以a為首的符號串為首的符號串(a|b)*abb所有以所有以abb為尾的為尾的a，b符號串符號串(a|b)*(aa|bb) (a|b)*所有含有兩個相繼的所有含有兩個相繼的a或相繼的或相繼的b的符號串的符號串(aa|ab|ba|bb) *空串和任何長度為偶數(shù)的符號串空串和任何長度為偶數(shù)的符號串(a|b)(a|b)(a|b) *任何長度大于等于任何長度大于等于2的符號串的符號串 正規(guī)式 正規(guī)集(

20、ab) ,a,b,aa,ab 所有 由a和b組成的串(ab)(aabb)(ab) 上所有含有兩個相繼 的a或兩個相繼的b組 成的串n例：設(shè)=a，b，0，1 正規(guī)式 正規(guī)集 （a|b)(a|b|0|1) 上的“標識符的全體 （0|1)(0|1) 上的“數(shù)”的全體 例：令例：令 =l l，dd，則則 上的正規(guī)式上的正規(guī)式 r=l(l r=l(l d) d) 定義的正定義的正規(guī)集為規(guī)集為: : l,ll,ld,ldd, l,ll,ld,ldd, 其中其中l(wèi) l代表字母代表字母, ,d d代表數(shù)字代表數(shù)字, ,正規(guī)式即是正規(guī)式即是 字母字母( (字母字母| |數(shù)字數(shù)字) ) 。它表示的正規(guī)集中的每個元

21、素的模式是它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母字母打頭的字母數(shù)字串數(shù)字串”,”,就是就是PascalPascal和和 多數(shù)程序設(shè)計語言允許的的標識多數(shù)程序設(shè)計語言允許的的標識符的詞法規(guī)則符的詞法規(guī)則. .程序設(shè)計語言的單詞都能用正規(guī)式程序設(shè)計語言的單詞都能用正規(guī)式 來定義來定義. .若兩個正規(guī)式若兩個正規(guī)式e1和和e2所表示的正規(guī)集相同所表示的正規(guī)集相同,則說則說e1和和e2等價等價,寫作寫作e1=e2。例如： e1= (ab)， e2 = ba又如： e1= b(ab) , e2 =(ba)b e1= (ab) , e2 =(ab)設(shè)設(shè)r，s，t均是正規(guī)式，則有以下性質(zhì)：均是正

22、規(guī)式，則有以下性質(zhì)：（1）交換律：）交換律： r|s= s|r（2）結(jié)合律：結(jié)合律： r|(s|t)=(r|s)|t (rs)t=r(st) （3）分配律：分配律： (r|s)t=rt|st（4）同一律：同一律： r= r= r5、 r=r, r=r是“連接”的恒等元素零一律6、 rr=r r=rrr “或”的抽取律 正規(guī)文法與正規(guī)式n一個正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義。 對任意一個正規(guī)文法，存在一個定義同對任意一個正規(guī)文法，存在一個定義同一個正規(guī)語言的正規(guī)式；一個正規(guī)語言的正規(guī)式；反之，對每個正反之，對每個正規(guī)式，存在一個生成同一語言的正規(guī)文法。規(guī)式，存在一個生成同一語言的正

23、規(guī)文法。有些正規(guī)語言很容易用文法定義，有些語有些正規(guī)語言很容易用文法定義，有些語言更容易用正規(guī)式定義，現(xiàn)在介紹兩者間言更容易用正規(guī)式定義，現(xiàn)在介紹兩者間的轉(zhuǎn)換，從結(jié)構(gòu)上建立它們的等價性。的轉(zhuǎn)換，從結(jié)構(gòu)上建立它們的等價性。將將上的一個正規(guī)式轉(zhuǎn)換成正規(guī)文上的一個正規(guī)式轉(zhuǎn)換成正規(guī)文法法對已形成的形如對已形成的形如Ax*y的正規(guī)產(chǎn)生式，重寫為：的正規(guī)產(chǎn)生式，重寫為：AxBAyBxBBy 其中其中B為一新非終結(jié)符為一新非終結(jié)符。對形如對形如Ax|y的正規(guī)產(chǎn)生式，重寫為：的正規(guī)產(chǎn)生式，重寫為：Ax，Ay不斷利用上述規(guī)則做變換，直到每個產(chǎn)生式不斷利用上述規(guī)則做變換，直到每個產(chǎn)生式都符合三型文法的要求都符合三

24、型文法的要求。n例將R=a(a|d)*轉(zhuǎn)換成相應的正規(guī)文法，令S是文法的開始符號，首先形成SaA和A(a|d)*， 再重寫第二條產(chǎn)生式形成A(a|d)A|，進而變換為SaA A aA A dA A 2、將正規(guī)文法轉(zhuǎn)換成正規(guī)式。n基本上是上述過程的逆過程，最后只剩下一個開始符號定義的產(chǎn)生式，并且該產(chǎn)生式的右部不含非終結(jié)符。其轉(zhuǎn)換規(guī)則:.文法產(chǎn)生式正規(guī)式規(guī)則1規(guī)則2規(guī)則3AxB ByAxA|yAx AyA=xyA=x*yA=x|y n例：文法GSSaA Sa AaA AdA Aa Ad先有：S=aA|aA=(aA|dA)|(a|d)=(a|d)A|a|d=(a|d) * (a|d) S=aA|a=

25、a(a|d)* (a|d)|a = a(a|d)* 即即a(a|d)*為所求。為所求。有窮自動機有窮自動機 有窮自動機(也稱有限自動機)作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合。 有窮自動機分為兩類： 確定的有窮自動機和不確定的有窮自動機關(guān)于關(guān)于有窮自動機我們將討論如下問題有窮自動機我們將討論如下問題確定的有窮自動機DFA不確定的有窮自動機NFANFA的確定化DFA的最小化確定的有窮自動機確定的有窮自動機DFADFA定義：定義：一個確定的有窮自動機（一個確定的有窮自動機（DFA）M是一個五元是一個五元組：組：M=（K，f，S，Z）其中其中1.1.K

26、 K是一個有窮集，它的每個元素稱為一個狀態(tài)；是一個有窮集，它的每個元素稱為一個狀態(tài)；2.2.是一個有窮字母表，它的每個元素稱為一是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱個輸入符號，所以也稱為輸入符號表；為輸入符號表；DFA定義定義3. 3. f是轉(zhuǎn)換函數(shù)，是在是轉(zhuǎn)換函數(shù)，是在KK上的映射，即，上的映射，即，如如 f（ki，a）=kj，（，（kiK，kjK）就意味著，當前狀態(tài)為就意味著，當前狀態(tài)為ki，輸入符為輸入符為a時，將時，將轉(zhuǎn)換為下一個狀態(tài)轉(zhuǎn)換為下一個狀態(tài)kj，我們把我們把kj稱作稱作kiki的一的一個后繼狀態(tài)；個后繼狀態(tài)；4. SK K是唯一的一個初態(tài)；是唯一的一個初態(tài)

27、；5. 5. Z K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)或結(jié)束狀態(tài)。一個一個DFA 的例子：的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q一個一個DFADFA可以表示成一個狀態(tài)圖可以表示成一個狀態(tài)圖( (或稱狀態(tài)轉(zhuǎn)換或稱狀態(tài)轉(zhuǎn)換圖圖) )。假定。假定DFA MDFA M含有含有m m個狀態(tài)，個狀態(tài)，n n個輸入字符，個輸入字符，那么這個狀態(tài)圖含有那么這個狀態(tài)圖含有m m個結(jié)點，每個結(jié)點最多有個結(jié)點，每個

28、結(jié)點最多有n n個弧射出，整個圖含有唯一一個初態(tài)結(jié)點和若個弧射出，整個圖含有唯一一個初態(tài)結(jié)點和若干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“=”“=”或標或標以以“-”“-”，終態(tài)結(jié)點用雙圈表示或標以，終態(tài)結(jié)點用雙圈表示或標以“+”“+”，若，若 f(kf(ki i ,a)=k,a)=kj j，則從狀態(tài)結(jié)點則從狀態(tài)結(jié)點k ki i到狀態(tài)結(jié)點到狀態(tài)結(jié)點k kj j畫畫標記為標記為a a的??；的弧； DFA 的狀態(tài)圖表示的狀態(tài)圖表示bSUVQaaaba，bb一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應狀態(tài)行和輸入字符列下的新狀態(tài)，即k行

29、a列為f(k,a)的值。用雙箭頭“=”標明初態(tài)；否則第一行即是初態(tài)，相應終態(tài)行在表的右端標以1，非終態(tài)標以0。DFA 的矩陣表示的矩陣表示abSUVUQVVUQQQQ字符字符狀態(tài)狀態(tài)0001n對于對于* *中的任何符號串中的任何符號串t t，若存在一條從初態(tài)到若存在一條從初態(tài)到某一終態(tài)的道路，且這條道路上所有弧的標記連某一終態(tài)的道路，且這條道路上所有弧的標記連接成的字符串等于接成的字符串等于t,t,則稱則稱t t可為可為DFA M DFA M 所接受，所接受，若若M M的初態(tài)同時又是終態(tài)，則空字可為的初態(tài)同時又是終態(tài)，則空字可為M M所識別所識別（接受）。（接受）。即：若即：若t t * *，

30、f(Sf(S，t)=Pt)=P，其中其中S S為為 M M的開始狀態(tài)，的開始狀態(tài)，P P Z Z，Z Z為終態(tài)集。為終態(tài)集。則稱則稱t t為為DFA MDFA M所接受（識別）所接受（識別）. . 將轉(zhuǎn)換函數(shù)進行擴充將轉(zhuǎn)換函數(shù)進行擴充一個輸入符號串t，（將它表示成Tt1的形式，其中T，t1 *）在DFA M=（K，f，S，Z）上運行運行的定義為：f（Q， Tt1）=f（f（Q，T），t1） 其中QK 例例：證明證明t=baab被下圖的被下圖的DFA所接受所接受。f（S，baab）=f（f（S，b），），aab） = f（V，aab）= f（f（V，a），），ab） =f（U，ab）=f（f（U

31、，a），），b） =f（Q，b）=QQ屬于終態(tài)。屬于終態(tài)。得證。得證。bSUVQaba, baabDFA M所能接受的符號串的全體記為L(M).對于任何兩個有窮自動機M和M，如果L(M)=L(M)，則稱M與M是等價的.結(jié)論： 上一個符上一個符號號串集串集V V 是正規(guī)的，當且僅當是正規(guī)的，當且僅當存在一個存在一個 上的確定有窮自動機上的確定有窮自動機M M，使得使得V=L(M)V=L(M)。DFA的確定性的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:KK是一個單值函數(shù)單值函數(shù)，也就是說，對任何狀態(tài)kK，和輸入符號a，f(k,a)唯一地確定了下一個狀態(tài)。DFA的行為很容易用程序來模擬的行為很容易用程序來模擬.DFA

32、 M=（K，f，S，Z）的行為的模擬程序的行為的模擬程序K:=S；c:=getchar;while ceof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes) else return (no)不確定的有窮自動機不確定的有窮自動機NFA定義定義NFA M= K， ，f，S，Z ，（1）其中）其中K為狀態(tài)的有窮非空集，為狀態(tài)的有窮非空集，（2） 為有窮輸入字母表為有窮輸入字母表（3）f為為K * 到到K的子集的一種映射，的子集的一種映射， * 說明存在遇到說明存在遇到的情況，的情況， f(ki , a)是一個多值是一個多值函數(shù)。函數(shù)

33、。 （4）S K是初始狀態(tài)集，是初始狀態(tài)集， （5）Z K為終止狀態(tài)集為終止狀態(tài)集.例子例子 NFA M=NFA M=（SS，P P，ZZ，00，11，f f，SS，PP，ZZ）其中其中 f f（S S，0 0）=P=Pf f（Z Z，0 0）=P=Pf f（P P，1 1）=Z=Zf f（Z Z，1 1）=P=Pf f（S S，1 1）=S=S，ZZ狀態(tài)圖表示SPZ00,1111矩陣表示矩陣表示矩陣表示01SPS,Z0PZ0ZPP1簡化為01SPS,Z0P.Z0ZPP1具有具有 轉(zhuǎn)移的不確定的有窮自動機轉(zhuǎn)移的不確定的有窮自動機 123abc類似類似DFA, 對對NFA M= K， ，f，S，

34、Z 也有如也有如下定義下定義*上的符號串t在NFA M上運行.一個輸入符號串t，（我們將它表示成Tt1的形式，其中T，t1 *）在NFA M上運行運行的定義為：f（Q， Tt1）=f（f（Q，T），t1） 其中QK.*上的符號串t被NFA M接受若t *，f(S0，t)=P，其中S0 S，P Z，則稱t為NFA M所接受接受（識別識別）*上的符號串上的符號串t被被NFA M接受也可以這樣理解接受也可以這樣理解 對于中的任何一個串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標記字依序連接成的串(不理采那些標記為的弧)等于t，則稱t可為NFA M所識別(讀出或接受)。若M的某

35、些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的道路,其上所有弧的標記均為，那么空字可為M所接受。00011110100011100000010001100 DFA是是NFA的特例的特例.對每個對每個NFA N一定存一定存在一個在一個DFA ，使得，使得 L(M)=L(N)。對對每個每個NFA N存在著與之等價的存在著與之等價的DFA M。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法子集法.與某一與某一NFA等價的等價的DFA不唯一不唯一.NFA到相應的DFA的構(gòu)造的基本思路是： DFADFA的每一個狀態(tài)對應的每一個狀態(tài)對應NFA的一組狀態(tài). 定義對狀態(tài)集

36、合定義對狀態(tài)集合I的幾個有關(guān)運算：的幾個有關(guān)運算：1. 狀態(tài)集合狀態(tài)集合I的的-閉包閉包，表示為表示為-closure(I)，定定義為一狀態(tài)集，是狀態(tài)集義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)中的任何狀態(tài)S經(jīng)任意條經(jīng)任意條弧弧而能到達的狀態(tài)的集合。而能到達的狀態(tài)的集合。 2. 狀態(tài)集合狀態(tài)集合I的的a弧轉(zhuǎn)換，弧轉(zhuǎn)換，表示為表示為move(I,a)定義為定義為狀態(tài)集合狀態(tài)集合J，其中其中J是所有那些可從是所有那些可從I中的某一狀態(tài)經(jīng)過中的某一狀態(tài)經(jīng)過一條一條a弧而到達的狀態(tài)的全體?；《竭_的狀態(tài)的全體。狀態(tài)集合狀態(tài)集合I的有關(guān)運算的例子的有關(guān)運算的例子I=1, -closure(I)=1,2；I=5

37、, -closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa NFA確定化算法確定化算法: 假設(shè)NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造一個DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：1. M的狀態(tài)集S由K K的一些子集的一些子集組成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的狀態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即對于子集S1, S2= S2, S1,來說，S的狀態(tài)就是S1 S2；2、 M和N的輸入字母表是相同的，即是

38、；3、轉(zhuǎn)換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4、S0=-closure(K0)為M的開始狀態(tài)；5、 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKt例：P55 圖4.4的NFADFA T Ta Tb0,1,2,4T01,2,3,4,6,7,8T11,2,4,5,6,7 T21,2,3,4,6,7,8T11,2,3,4,6,7,8T11,2,4,5,6,7,9 T31,2,4,5,6,7 T21,2,3,4,6,7,8T11,2,4,

39、5,6,7 T21,2,4,5,6,7,9 T31,2,3,4,6,7,8T11,2,4,5,6,7,10T41,2,4,5,6,7,10T41,2,3,4,6,7,8T11,2,4,5,6,7 T2bT1bT0T2T3T4aaabbaab構(gòu)造NFA N的狀態(tài)狀態(tài)K K的子集的子集的算法：假定所構(gòu)造的子集族為C，即C= (T1, T2,. TI),其中T1, T2,. TI為狀態(tài)K的子集。1、 開始，令-closure(K0)為C中唯一成員，并且它是未被標記的。2 while （C中存在尚未被標記的子集T）do 標記T； for 每個輸入字母a do U:= -closure(move(T,a

40、)； if U不在C中 then 將U作為未標記的子集加在C中 NFA的確定化的確定化 例子4f35621iaaaabbbbIaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fSABACBBADCCEDFDEFDFCE4f35621iaaaabbbb 等價的等價的DFAaCDBAEFSba

41、aaaabbbbbabF確定有窮自動機的化簡確定有窮自動機的化簡 尋找一個狀態(tài)數(shù)最少尋找一個狀態(tài)數(shù)最少DFA M,使得使得L(M)=L(M) 說一個有窮自動機是化簡了的，即是說，它沒有說一個有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有窮自動機可以通過一個有窮自動機可以通過消除多余狀態(tài)和合并等消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有窮自動價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有窮自動機。機。 所謂有窮自動機的所謂有窮自動機的多余狀態(tài)，是指這樣的狀態(tài)：多余狀態(tài)，是指這樣的狀態(tài)：從自動機的開始狀態(tài)出發(fā)，

42、任何輸入串也不能到從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。態(tài)。 DFA的最小化就是尋求最小狀態(tài)的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別）兩個狀態(tài)s和t等價的條件：兼容性（一致性）條件同是終態(tài)或同是非終態(tài)傳播性（蔓延性）條件從s出發(fā)讀入某個aa和從t出發(fā)讀入某個a到達的狀態(tài)等價。例：b02bb1a3baa4ab狀態(tài)狀態(tài)0和狀態(tài)和狀態(tài)4是可區(qū)別狀態(tài)，狀態(tài)是可區(qū)別狀態(tài)，狀態(tài)2和狀態(tài)和狀態(tài)3也是也是可區(qū)別狀態(tài)，因為：可區(qū)別狀態(tài)，因為：2狀態(tài)輸入狀態(tài)

43、輸入b 到達到達2狀態(tài)（非狀態(tài)（非終態(tài)），而終態(tài)），而3狀態(tài)輸入狀態(tài)輸入b 到達到達4狀態(tài)（終態(tài)）狀態(tài)（終態(tài)） C和D同是終態(tài),讀入a到達C和F, C和F同是終態(tài), C和F讀入a都到達C,讀入b都到達E. C和D等價aCDBAEFSbaaaaabbbbbabF最小狀態(tài)最小狀態(tài)DFA對于一個DFA M =（K,f, k0,kt)，存在一個最小狀態(tài)DFA M =（K,f, k0,kt)，,使L(M)=L(M). 結(jié)論接受L的最小狀態(tài)有窮自動機不計同構(gòu)是唯一的?！胺指罘ǚ指罘ā盌FA的最小化算法的核心的最小化算法的核心 把一個把一個DFA的狀態(tài)分成一些不相交的子集，的狀態(tài)分成一些不相交的子集，使得任

44、何不同的兩子集的狀態(tài)都是可區(qū)別使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等的，而同一子集中的任何兩個狀態(tài)都是等價的價的.最后每個子集中選出一個代表，同時最后每個子集中選出一個代表，同時消除其他等價狀態(tài)。消除其他等價狀態(tài)。 DFA的最小化的最小化例子例子1 1、將、將M M的狀態(tài)分為兩個子集的狀態(tài)分為兩個子集一個由終態(tài)一個由終態(tài) C,D,E,FC,D,E,F組成一個由非終態(tài)組成一個由非終態(tài) S,A,BS,A,B組成組成: :2 2、考察考察 S,A,BS,A,B是否可分是否可分。 CDBAEFSbaaaaaabbbbbbaaAaa C因為因為A S,A,B,而而C C,D,E,F是兩個不等價狀態(tài)，所以可分為是兩個不等價狀態(tài)，所以可分為A和和S,B兩個集合。兩個集合。3 3、考察、考察 S,BS,B是否可再分：是否可再分：bBbD因為因為B S,B,D C,D,E,F所所以，可再分為以，可再分為S和和B兩個集合。兩個集合。CDBAEFSbaaaaaabbbbbba4、考察、考察C,D,E,F是否可分：是否可分：因為因為C，D，E，F(xiàn)輸入輸入a和和b到到達的狀態(tài)都達的狀態(tài)都C,D,E,F,所所以，不可分。以，不可分。所以所以DFA 最后的狀態(tài)為：