編譯原理基礎(chǔ)課件

詞法分析2.1詞法分析中的若干問題2.1.1記號、模式與單詞自然語言中的句子通常由一個個單詞和標(biāo)點符號組成，可以根據(jù)其在句子中的作用，將它們劃分為動詞、名詞、形容詞、標(biāo)點符號等不同的種類。程式設(shè)計語言與此相類似，組成語句的基本單元也可根據(jù)其在句子中的作用分類。最基本分類有四類：

(1)關(guān)鍵字(保留字)：這類單詞在程式設(shè)計語言中有固定的意義，如begin、end、while等。若在程式設(shè)計語言中不允許用它們再表示其他的意思，則這類單詞也被稱為保留字。(2)識別字：識別字是程式設(shè)計語言中最大的一個類別，它的作用是為某個實體起一個名字，以便於今後稱呼(引用)，如draw_line、sort等?？梢杂米R別字來命名的實體包括類型、變數(shù)、過程、常量、類、對象、程式包、標(biāo)號等，即類型名、變數(shù)名、過程名、常量名等。(3)字面量：字面量是指直接以其字面所表示的常量，如25、true、"Thisisastring"等。值得注意的是，字面量與常量是兩個不同的概念，常量可以是一個字面量(直接表示)，也可以是一個常量名(命名表示)。例如可以在Pascal中聲明：constmax_length=25，顯然25是一個常量，max_length也是一個常量，我們稱25為字面量，而不稱max_length為字面量。根據(jù)字面量的內(nèi)容，可以將它們再進行更細(xì)的劃分，如常數(shù)字面量(包括整型字面量、實型字面量、枚舉字面量等)、字串字面量等。(4)特殊符號：程式設(shè)計語言中的特殊符號，類似於自然語言中的標(biāo)點符號，每個符號在程式設(shè)計語言中均有特殊用途?？梢愿鶕?jù)它們的用途，再細(xì)分為算符(如+、、*、/等)、分隔符號(如；、”、“等)。顯然，一個單詞究竟是識別字、關(guān)鍵字，還是特殊符號，需要根據(jù)一定的構(gòu)詞規(guī)則來產(chǎn)生和識別。我們將產(chǎn)生和識別單詞的規(guī)則稱為模式(patten)，按照某個模式(規(guī)則)識別出的元素稱為記號(token)，而單詞(lexeme)一詞是指被識別出元素自身的值。

例2.1

對於語句：position:=initial+rate*60，可以識別出下述序列：識別字特殊符號識別字特殊符號識別字特殊符號數(shù)字字面量其中position、initial、rate均被識別為識別字，因為它們均符合同一條規(guī)則，即以字母打頭的字母數(shù)字串。記號至少含有兩個資訊：一個是記號的類別，如“識別字”；另一個是記號的值，如“position”。顯然，如果把記號看作是一個類型的話，則單詞就是一個類型中的實例。由於我們總是說識別出一個識別字，而不說識別出一個position或rate，因而將詞法分析器識別出的序列稱為記號流。

記號的類別、模式以及單詞三者之間的關(guān)係可以用表2.1加以說明。其中，const和if分別是被細(xì)分的關(guān)鍵字，它們的特點是一個記號類別僅對應(yīng)一個單詞；relation表示關(guān)係運算符；id表示識別字；num表示數(shù)字字面量；literal表示字串字面量；comment表示注釋，它們的特點是一個記號類別可以對應(yīng)若干個單詞。由於語法分析及其後的階段並不對注釋進行分析，因而可在詞法分析階段中濾掉注釋，即詞法分析器可以不向語法分析器返回comment。而其他的記號，均是根源程式中的有效成分，需要返回給語法分析器。表2.1記號、模式與單詞2.1.2記號的屬性從例2.1中已經(jīng)知道，記號至少包含兩個部分：記號類別和記號的其他資訊?？梢钥闯觯浱柕念悇e唯一標(biāo)識一類記號，例如所有的關(guān)係運算符均可以由relation來標(biāo)識，而所有字串字面量均可以由literal來標(biāo)識。所以，記號的類別可以被認(rèn)為是記號的名字或記號的代表，在不引起混淆的情況下，將記號的類別簡稱為記號。記號的其他資訊被稱為記號的屬性。例如，num可以取值3.1416，則稱3.1416是num的屬性，而literal可以取值“coredumped”(不含引號)，則稱“coredumped”是literal的屬性。由此可見，記號的類別標(biāo)識一類記號，而記號的類別加屬性標(biāo)識一個記號實例。

在電腦內(nèi)部，可以有不同的方式來表示記號的類別和屬性。一般情況下，記號的類別可以用整型編碼或枚舉類型表示，如表2.1中每個記號類別可以用括弧中的整型編碼表示，如01表示const，82表示id等。根據(jù)記號類別的不同，記號的屬性的值可以有不同的表示方法。relation的屬性值是一個有限可枚舉集合，可以用每個屬性值在集合中的位置來表示它，如1表示<，2表示<=，依此類推。id的屬性值是一個無限可枚舉集合，因此，只能用每個識別字的原始輸入形式(字串)來表示，如pi、draw_line等。字面量的屬性根據(jù)情況，其表示方式也不同，如數(shù)字字面量可由轉(zhuǎn)義後的實際值表示，如表示為3.1416而不是“3.1416”，而字串字面量就無需轉(zhuǎn)義。

例2.2

運算式mycount>25由表2.2的三個記號組成。其中識別字的屬性值也可以由mycount在符號表中的入口(下標(biāo))來表示。表2.2記號的表示2.1.3詞法分析器的作用與工作方式詞法分析器是編譯器中唯一與根源程式打交道的部分，從某種意義說，也可以被認(rèn)為是整個編譯器的預(yù)處理器。它的主要工作包括：

(1)濾掉根源程式中的無用成分，如注釋、空格、回車等。例如，表2.1中記號的種類除了comment之外，均有一個編碼，表示需要遞交給語法分析器進行後繼的處理，而comment沒有對應(yīng)編碼，表示注釋成分可以過濾掉，不需要遞交，因為語法分析及其之後的各個階段已經(jīng)不再需要它們。(2)處理與具體平臺有關(guān)的輸入。不同的操作系統(tǒng)或相關(guān)軟體構(gòu)成的平臺，對某些特殊符號(如檔結(jié)束符等)可能有不同表示，因此需要在詞法分析階段分情況處理。

(3)識別記號，並交給語法分析器。這是詞法分析器的主要任務(wù)，本章將在各節(jié)中詳細(xì)討論。(4)調(diào)用符號表管理器或出錯處理器，進行相關(guān)處理。詞法錯誤是根源程式中常見的錯誤，如出現(xiàn)非法字元、拼錯關(guān)鍵字、多或少字元等。值得注意的是，詞法錯誤往往不是由詞法分析器檢查出來的，而是由語法分析器發(fā)現(xiàn)的。這是因為，根源程式中除了非法字元之外的大部分字元或字串，都可以被詞法分析器的某個模式所匹配，從而被識別成一個記號。而這些記號的正確與否，在沒有上下文對照的情況下，是很難判斷的。例如，12x被認(rèn)為是一個非法的Pascal的識別字，但是，由於12可以被識別整型數(shù)的模式匹配，而x可以被識別識別字的模式匹配，因而詞法分析器會分別識別出一個整型數(shù)和一個識別字，而不是報告一個錯誤。

根據(jù)編譯器的總體需求，詞法分析器在整個編譯器中可以有不同的工作方式。

(1)詞法分析器作為語法分析器的副程式。最常採用，也最容易實現(xiàn)的工作方式是將詞法分析器作為語法分析器的副程式，每當(dāng)語法分析器需要一個記號時，就調(diào)用詞法分析器，並得到一個識別出的記號。其工作方式如圖2.1所示。

(2)詞法分析器進行單獨的一遍掃描。另一種常用的工作方式，是安排詞法分析器進行單獨的一遍掃描，它以根源程式為輸入，輸出是以記號流形式表示的根源程式。其工作方式如圖2.2所示。圖2.1作為副程式的詞法分析器

圖2.2詞法分析器進行單獨一遍掃描(3)與語法分析器並行工作的模式。上述兩種詞法分析器的工作模式與語法分析器的關(guān)係均被認(rèn)為是串行的。為了提高編譯器的效率，可以通過一個佇列，使詞法分析器和語法分析器以生產(chǎn)/消費的形式並行工作。詞法分析器將識別出的記號流輸出到佇列中，語法分析器從佇列中取得記號，只要佇列中有識別出的記號，則詞法分析器和語法分析器就可以同時工作。其工作方式如圖2.3所示。圖2.3並行工作模式2.1.4輸入緩衝區(qū)詞法分析器是編譯器中讀入根源程式字元序列的唯一階段，而相當(dāng)可觀的編譯時間又消耗在詞法分析階段，所以，加快詞法分析是設(shè)計編譯器時要考慮的重要問題之一?？梢酝ㄟ^設(shè)立輸入緩衝區(qū)來加快讀入根源程式字元序列的速度。如果使用詞法分析器生成器編寫詞法分析器，則生成器會提供讀入和緩沖輸入序列的例程；如採用通用程式設(shè)計語言編寫詞法分析器，就需要顯式地管理根源程式的讀取。

輸入緩衝區(qū)一般被設(shè)計為一塊與磁片扇區(qū)大小成倍數(shù)關(guān)係的記憶體。若一個扇區(qū)為1024位元組，則輸入緩衝區(qū)可以取1024、4096或8192位元組等。這樣可以保證對緩衝區(qū)的一次輸入所需的I/O操作次數(shù)盡可能少。輸入緩衝區(qū)的安排一般採用單緩衝區(qū)或雙緩衝區(qū)(緩衝區(qū)對)的方式。下邊所介紹的是單緩衝區(qū)方式，它也是詞法分析器生成器FLEX所採用的方式。

圖2.4是一個單緩衝區(qū)的示意圖。有效輸入序列從緩衝區(qū)的起始位置開始存放，最後添加一個特殊標(biāo)記(此處用#表示)：若緩衝區(qū)一次裝不下整個根源程式，它就表示緩衝區(qū)的結(jié)束，否則它緊跟在檔結(jié)束符(eof)之後，表示整個輸入根源程式的結(jié)束。用兩個指針c_ptr和f_ptr分別指向當(dāng)前被識別記號的第一個字元和向前掃描的字元。最初，兩個指針同時指向下一個被識別記號的第一個字元，f_ptr向前掃描，直到某個模式匹配成功。一旦這個記號被確定，f_ptr指向被識別出記號的右端字元，在此記號被處理後，兩個指針都移向該記號之後的下一個字元。在f_ptr向前掃描的過程中，如果遇到檔結(jié)束標(biāo)誌，則表示輸入序列已被處理完。如果遇到特殊標(biāo)記#，說明緩衝區(qū)中的內(nèi)容需要更新。這時，首先將c_ptr到f_ptr所指的內(nèi)容(不包括特殊標(biāo)記)移到緩衝區(qū)的起始位置，然後將新的內(nèi)容讀進緩衝區(qū)，最後加上特殊標(biāo)記。具體演算法如下：c_ptrf_ptr圖2.4單緩衝區(qū)procedureget_next_buffer(buffer，start，length)is--start和length是需仍保留在緩衝區(qū)中字串的起始位置和長度beginiflength>=buffer_size --buffer_size是緩衝區(qū)實際容量

thenreturnerror；

elseforiinlow..low+length1 --low是緩衝區(qū)下界，假設(shè)從0開始

loopbuffer(i):=buffer(start+ilow)； --把剩餘的輸入移到緩衝區(qū)頭部

endloop； num_to_read:=buffer_sizelength；

ifnumber_to_read>block_size--block_size應(yīng)是磁片扇區(qū)的整數(shù)倍

thennumber_to_read:=block_size;endif;read_buffer(buffer，length+low，num_to_read)；

endif；endget_next_buffer；

假設(shè)被掃描的輸入序列的最大長度不超過max_length，則可以選擇buffer_size=block_size+max_length，即緩衝區(qū)的大小是磁片扇區(qū)大小的整數(shù)倍加上一個最長可能被掃描的輸入序列。這種緩衝技術(shù)能勝任大多數(shù)情況，但在向前被掃描字元個數(shù)超過緩衝區(qū)長度的極端情況下會失效。早期的程式設(shè)計語言通常採用開括弧與閉括弧的方式標(biāo)識注釋，如表2.1中的comment，如果程式員不小心忘記書寫閉括弧，而詞法分析器的設(shè)計又將comment作為一個完整的記號識別，就會出現(xiàn)被掃描字元個數(shù)超過緩衝區(qū)長度的情況。因此，後來設(shè)計的程式設(shè)計語言大多採用僅有開括弧，而默認(rèn)換行標(biāo)誌為閉括弧的注釋方式，如上述演算法中的“--”(Ada的注釋方式)或者C++中的“//”，從根本上杜絕了這種極端情況。2.2模式的形式化描述2.2.1字串與語言從詞法分析的角度看，程式設(shè)計語言是由記號組成的集合，每個記號又是由若干字母按照一定規(guī)則組成的字串。為了討論的簡單性和準(zhǔn)確性，本章對常用的術(shù)語以定義的方式給出。有一點需要強調(diào)，編譯領(lǐng)域的很多名詞術(shù)語的使用並不統(tǒng)一，因此希望讀者掌握“是什麼”，而不是“叫什麼”。在下述的討論中，我們首先定義一個泛泛的“語言”，然後在此基礎(chǔ)上規(guī)定一個正規(guī)集，而程式設(shè)計語言就是一個正規(guī)集。

定義2.1語言L是有限字母表∑上有限長度字串的集合。定義2.1明確指出，語言是一個集合，集合中的元素是字串，並且強調(diào)了兩個有限:①字母表是有限的，即字母表中元素是有限多個；

②字串的長度是有限的，即字串中字元個數(shù)是有限多個。這是由於電腦所能表示的字元個數(shù)和字串的長度都是有限的。

由於字串的有序性，使得以字串作為元素的集合具有某些特性。字串和集合的基本概念和特性，以表格的形式分別列在表2.3和表2.4中。其中，字串的連接運算是一種新形式的運算，它表示兩個字串首尾相接，形成一個新的集合。例如，S1="pre"，S2="fix"，則S1S2="prefix"。值得注意的是，集合中連接運算所形成的新集合與交運算形成的新集合完全不同。例如，若L={"pre"，M={"fix"，則L∩M=Φ，而LM={"prefix"。表2.3字串的基本概念表2.4字串集合上的基本運算2.2.2正規(guī)式與正規(guī)集定義2.2令Σ是一個有限字母表，則Σ上的正規(guī)式及其表示的集合遞歸定義如下:①ε是正規(guī)式，它表示集合L(ε)=ε；

②若a是Σ上的字元，則a是正規(guī)式，它表示集合L(a)=；

③若正規(guī)式r和s分別表示集合L(r)和L(s)，則

(a)r|s是正規(guī)式，表示集合L(r)∪L(s)；

(b)rs是正規(guī)式，表示集合L(r)L(s)；

(c)r*是正規(guī)式，表示集合(L(r))*；

(d)(r)是正規(guī)式，表示的集合仍然是L(r)?？捎谜?guī)式描述的語言稱為正規(guī)語言或正規(guī)集。

定義2.2中①和②規(guī)定了正規(guī)式的基本運算元或基本正規(guī)式。定義2.2的③給出了正規(guī)式上的三種運算:(a)或運算、(b)連接運算和(c)閉包運算。對於由多個運算元和多個操作符組成的正規(guī)式，可以利用(d)所給的括弧規(guī)定運算的先後次序。如果對或、連接和閉包運算進行如下約定:①三種運算均具有左結(jié)合性質(zhì)；

②運算的優(yōu)先順序從高到低順序排列為:閉包運算、連接運算、或運算。則正規(guī)式中不必要的括弧可以被省略。例如，(a)|((b)*(c))可以簡化成a|b*c。

例2.3

設(shè)字母表∑={a，b，c}，部分∑上的正規(guī)式和正規(guī)式所表示的正規(guī)集如表2.5所示。表2.5正規(guī)式與它表示的正規(guī)集

正規(guī)集是一個集合，而正規(guī)式是表示正規(guī)集的一種方法。正如不同算術(shù)運算式可以表示同一個數(shù)(如3+5、5+3、2+6等均表示8)一樣，不同正規(guī)式也可以表示同一個正規(guī)集，即正規(guī)式與正規(guī)集之間是多對一的關(guān)係。例2.4令L(x)={a，b}，L(y)={c，d}，則

L(x|y)={a，b，c，d} L(y|x)={a，b，c，d}x|y和y|x表示同一個正規(guī)集。

定義2.3若正規(guī)式P和Q表示了同一個正規(guī)集，則稱P和Q是等價的，記為P=Q。正規(guī)式之間的一些恒等運算，被稱為正規(guī)式的代數(shù)性質(zhì)。表2.6給出了正規(guī)式的若干代數(shù)性質(zhì)。利用這些性質(zhì)，可以對複雜的正規(guī)式進行化簡，使得可以用最簡單形式的正規(guī)式表示一個集合。而簡單的正規(guī)式意味著其所對應(yīng)的識別器的構(gòu)造也是簡單的。表2.6正規(guī)式的代數(shù)性質(zhì)2.2.3記號的說明表2.1中用自然語言對模式進行了非形式化的描述，例如識別字模式的非形式化描述是“以字母打頭的字母數(shù)字串”。這一描述很不精確，存在一些問題，如哪些符號是字母，哪些符號是數(shù)字，字母數(shù)字串的長度可以是多少等等。由於正規(guī)式是嚴(yán)格的數(shù)學(xué)運算式，採用正規(guī)式來描述模式，解決了精確描述模式的問題。另外，從詞法分析器的角度上看程式設(shè)計語言，用正規(guī)式說明的記號是一個正規(guī)集。用正規(guī)式說明記號的公式為：記號=正規(guī)式，可以讀作為“(左邊)記號定義為(右邊)正規(guī)式”，或者“記號是正規(guī)式”。通常，在不引起混淆的情況下，也把說明記號的公式簡稱為正規(guī)式，或者規(guī)則。

例2.5

表2.1中的記號relation、id和num分別是Pascal的關(guān)係運算符、識別字和無符號數(shù)，它們的正規(guī)式表示如下所示：

relation=<|<=|<>|>|>=|=id=(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9)*num=(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)(ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)

上述正規(guī)式給出了識別字的精確定義，用自然語言可以描述為“字母是英文26個字母大小寫中任何一個，數(shù)字是十進位阿拉伯?dāng)?shù)字中的任何一個，識別字是以字母打頭的、其後可跟隨0個或若干個字母或數(shù)字的字串”。1．簡化正規(guī)式描述為了簡化正規(guī)式的描述，通?？梢話裼萌缦碌膸追N正規(guī)式的縮寫形式。

(1)正閉包。若r是表示L(r)的正規(guī)式，則r+是表示(L(r))+的正規(guī)式，且下述等式成立:r+=rr*=r*r，r*=r+|ε+與*具有相同的運算優(yōu)先順序和結(jié)合性。

(2)可缺省。若r是正規(guī)式，則(r)?是表示L(r)∪ε的正規(guī)式，且下述等式成立:r?=r|ε(3)字元組。字元組是或關(guān)係的縮寫形式，它把所有存在或關(guān)係的字元集中在[]裏面。其中的字元可以有如下兩種書寫方式:

枚舉方式:如[abc]，它等價於a|b|c

分段方式:如[0-9a-z]，它等價於 [0123456789abcdefghijklmnopqrstuvwxyz](4)非字元組。若[r]是一個字元組形式的正規(guī)式，則[^r]是表示∑L(r)的正規(guī)式。例如，若∑=，則L([^abc])={d,e,f,g}。

(5)串。若r是字元連接運算的正規(guī)式，則串"r"與r等價，即r="r"。特別地，ε="",?a="a"。引入串的表示可以避免與正規(guī)式中運算符的衝突。例如："a|b"=a"|"b≠a|b。

2．引入輔助定義式引入輔助定義式的主要目的是為較複雜、但需要重複書寫的正規(guī)式命名，並在定義式之後的引用中，用名字代替相應(yīng)的正規(guī)式。所以，輔助定義式實質(zhì)上仍然是正規(guī)式，唯一的區(qū)別是正規(guī)式與外部模式匹配，而輔助定義式不與任何模式匹配。

例2.6

引入正規(guī)式的縮寫形式和輔助定義式後，id和num的正規(guī)式可重寫如下。

char =[a-zA-Z]digit =[0-9]digits =digit+optional_fraction =(.digits)?optional_exponent =(E(+|)?digits)?id =char(char|digit)*num =digitsoptional_fractionoptional_exponent 2.3記號的識別——有限自動機2.3.1不確定的有限自動機(NondeterministicFiniteAutomata，NFA)

定義2.4NFA是一個五元組(5-tuple)M=(S，∑，move，s0，F(xiàn))

其中：

①S是有限個狀態(tài)(state)的集合；

②∑是有限個輸入字元(包括ε)的集合；③move是一個狀態(tài)轉(zhuǎn)移函數(shù)，move(si，ch)=sj表示當(dāng)前狀態(tài)si下若遇到輸入字元ch，則轉(zhuǎn)移到狀態(tài)sj；

④s0是唯一的初態(tài)(也稱開始狀態(tài))；

⑤F是終態(tài)集(也稱接受狀態(tài)集)，它是S的子集，包含了所有的終態(tài)。

有限自動機是一個抽象的概念，可以用兩種直觀的方式——狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換矩陣來表示，這兩種方式分別簡稱為轉(zhuǎn)換圖和轉(zhuǎn)換矩陣。轉(zhuǎn)換圖是一個有向圖，NFA中的每個狀態(tài)對應(yīng)轉(zhuǎn)換圖中的一個節(jié)點；NFA中的每個move函數(shù)對應(yīng)轉(zhuǎn)換圖中的一條有向邊，該有向邊從si節(jié)點出發(fā)，進入sj節(jié)點，字元ch(或ε)是邊上的標(biāo)記。顯然，NFA的初態(tài)是轉(zhuǎn)換圖中沒有前驅(qū)的節(jié)點，而NFA的終態(tài)在轉(zhuǎn)換圖中用有別於其他節(jié)點的方法表示。例如，若節(jié)點用一個圓圈表示，則終態(tài)節(jié)點可以用一個加粗的圓圈或者雙圈表示。轉(zhuǎn)換矩陣是一個二維數(shù)組，其中每個元素M[si,sj]中的內(nèi)容是從狀態(tài)si到狀態(tài)sj的邊上的標(biāo)記ch(或ε)。在轉(zhuǎn)換矩陣中，一般以矩陣第一行所對應(yīng)的狀態(tài)為初態(tài)，而終態(tài)需要特別指出。

例2.7

識別由正規(guī)式(a|b)*abb說明的記號的NFA定義如下：

S={0,1,2,3},Σ={a,b}，s0=0,F={3}move={move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,move(2,b)=3}

它的轉(zhuǎn)換圖和轉(zhuǎn)換矩陣表示如圖2.5所示。在轉(zhuǎn)換矩陣中，需指出0是初態(tài)，3是終態(tài)。圖2.5識別(a|b)*abb的NFA(a)轉(zhuǎn)換圖表示的NFA；(b)轉(zhuǎn)換矩陣表示的NFA

例2.8

識別表2.1中記號id、num和relation的轉(zhuǎn)換圖如圖2.6所示。id和num依據(jù)的是例2.6中簡化的正規(guī)式。不難看出，轉(zhuǎn)換圖識別的每一個記號實質(zhì)上是從初態(tài)開始到某個終態(tài)的路徑上的標(biāo)記。例如，在識別relation的轉(zhuǎn)換圖中，從0開始到2的路徑標(biāo)記是“<=”，表示在終態(tài)2處識別出一個關(guān)係運算符，語句return(relation,LE)表示此處可以返回記號的種類relation和關(guān)係運算符的值LE(小於等於號)。 圖2.6狀態(tài)轉(zhuǎn)換圖(a)relation的轉(zhuǎn)換圖；(b)id的轉(zhuǎn)換圖；(c)num的轉(zhuǎn)換圖NFA的特點是它的不確定性，即在當(dāng)前狀態(tài)下，對同一個字元ch，可能有多於一個的下一狀態(tài)轉(zhuǎn)移。不確定性反映在NFA的定義中，就是move函數(shù)是一對多的；反映在轉(zhuǎn)換圖中，就是從一個節(jié)點可通過多於一條標(biāo)記相同字元的邊轉(zhuǎn)移到不同的狀態(tài)；反映在轉(zhuǎn)換矩陣中，就是M[si,sj]中不是一個單一狀態(tài)，而是一個狀態(tài)的集合。

用NFA識別輸入序列的方法是：從NFA的初態(tài)開始，對於輸入序列中的每一個字元，尋找它的下一狀態(tài)轉(zhuǎn)移，直到?jīng)]有下一狀態(tài)轉(zhuǎn)移為止。若此時所處狀態(tài)是終態(tài)，則從初態(tài)到終態(tài)路徑上的所有標(biāo)記，構(gòu)成了一個識別出的記號。否則沿原路返回，並在返回的每一個節(jié)點試探可能的下一條路徑，直到遇到第一個終態(tài)，或者一直返回到初態(tài)也沒有遇到終態(tài)。對於輸入序列，若試探了所有的路徑也找不到下一狀態(tài)轉(zhuǎn)移或不能到達(dá)一個終態(tài)，則NFA不接受該序列，說明它不是語言中的合法記號。若到達(dá)一個終態(tài)，則NFA接受該序列，說明它是語言中的一個合法記號。

例2.9

用例2.7中的NFA來識別輸入序列abb和abab。識別過程如圖2.7所示。對於abb的識別，有兩條路徑。第一條路徑從狀態(tài)0出發(fā)，經(jīng)過字元a到達(dá)狀態(tài)0，經(jīng)過字元b到達(dá)狀態(tài)0，再經(jīng)過字元b到達(dá)狀態(tài)0，此時輸入序列已經(jīng)結(jié)束，但是NFA沒有到達(dá)終態(tài)，所以NFA不接受輸入序列abb。但是，由於在狀態(tài)0遇到字元a的下一狀態(tài)還可以是1，因此沿原路回退到狀態(tài)0。再試探另一路徑：從狀態(tài)0出發(fā)，經(jīng)過字元a到達(dá)狀態(tài)1，經(jīng)過字元b到達(dá)狀態(tài)2，最後經(jīng)過字元b到達(dá)狀態(tài)3。由於狀態(tài)3是一個終態(tài)，所以，字串a(chǎn)bb被NFA接受，或者說被NFA識別。該過程被稱為識別過程，其中的0123被稱為識別路徑，而標(biāo)記該路徑的字串a(chǎn)bb是NFA所識別的記號。再來看對abab的識別過程。從0狀態(tài)出發(fā)遇到第一個字元a可以選擇兩條路徑對abab進行識別，當(dāng)選擇了遇到第一個字元a沿路徑000到達(dá)第二個字元a時，又可以選擇兩條路徑。因此，NFA對abab的識別有圖2.7(b)所示的三條路徑可走。但是三條路徑均不能到達(dá)終態(tài)，且再無路徑可以試探,?所以NFA不接受輸入序列abab,?也就是說，abab不是一個合法的記號。圖2.7NFA識別輸入序列abb和abab(a)abb的識別過程；(b)abab的識別過程

從例2.9中可以看出，用NFA識別記號存在下述問題：

(1)只有嘗試了全部可能的路徑，才能確定一個輸入序列不被接受，而這些路徑的條數(shù)隨著路徑長度的增長成指數(shù)增長。

(2)識別過程中需要進行大量的回溯，時間複雜度與輸入序列成指數(shù)級增長，且演算法複雜。造成這種情況的原因是NFA的不確定性，即在當(dāng)前的狀態(tài)下，遇到的下一個字元可能有多於一條的路徑可走，而在當(dāng)前狀態(tài)下，這些路徑中哪條路徑可以到達(dá)終態(tài)或者全部路徑均不能到達(dá)終態(tài)都是不可知的。2.3.2確定的有限自動機(DeterministicFiniteAutomata,DFA)

定義2.5DFA是NFA的一個特例，其中：

①沒有狀態(tài)具有ε狀態(tài)轉(zhuǎn)移(ε-transition)，即狀態(tài)轉(zhuǎn)換圖中沒有標(biāo)記ε的邊；

②對每一個狀態(tài)s和每一個字元a，最多有一個下一狀態(tài)。

例2.10

識別由正規(guī)式(a|b)*abb說明的記號的DFA，其轉(zhuǎn)換圖和轉(zhuǎn)換矩陣表示如圖2.8所示。根據(jù)轉(zhuǎn)換圖，讀者不難寫出此DFA的定義。用它識別輸入序列abb和abab的過程如圖2.9所示。圖2.8識別(a|b)*abb的DFA(a)轉(zhuǎn)換圖表示的DFA；(b)轉(zhuǎn)換矩陣表示的DFA圖2.9DFA識別輸入序列abb和abab

與NFA相比，DFA的特點就是它的確定性，即在當(dāng)前狀態(tài)下，對同一個字元ch，最多有一個下一狀態(tài)轉(zhuǎn)移。確定性反映在DFA的定義中，就是move函數(shù)是一對一的；反映在轉(zhuǎn)換圖中，就是從一個節(jié)點出發(fā)的任何不同的邊上標(biāo)記的字元均不同；反映在轉(zhuǎn)換矩陣中，就是M[si,sj]中是一個單一狀態(tài)。由於在DFA上識別輸入序列時，在任何一個當(dāng)前狀態(tài)下遇到任何輸入字元，其下一狀態(tài)轉(zhuǎn)移均是唯一確定的，因此，無論是接受還是不接受，均經(jīng)歷一條確定的路徑，而無其他任何路徑可走。也就是說，在DFA上識別輸入序列無需回溯，從而大大簡化了記號的識別過程。DFA識別輸入序列的過程總結(jié)為演算法2.1，被稱為模擬器(模擬DFA的行為)，也被稱為驅(qū)動器(用DFA的數(shù)據(jù)驅(qū)動分析動作)。模擬DFA演算法的最大特點是方法與模式無關(guān)，它僅根據(jù)DFA的當(dāng)前狀態(tài)和狀態(tài)轉(zhuǎn)移進行一系列的動作，直到回答yes或者no。而所有與模式相關(guān)的資訊均包含在DFA中。

演算法2.1模擬DFA

輸入

DFAD和輸入字串x。x由檔結(jié)束符eof終止，D的初態(tài)為s0，終態(tài)集為F。

輸出若D接受x，回答“yes”，否則回答“no”。

方法用下述過程識別x：

s:=s0；a:=nextchar；

whilea≠eofloops:=move(s，a)；a:=nextchar;endloop；

ifsisinFthenreturn"yes"；elsereturn"no"；endif；2.3.3有限自動機的等價

NFA和DFA統(tǒng)稱為有限自動機(FA)。所謂有限，是指自動機的狀態(tài)數(shù)是有限的，因此，有些教材中也稱為有限狀態(tài)自動機。與正規(guī)式的等價相似，F(xiàn)A之間也存在等價問題。

定義2.6

若有限自動機M和M'識別同一個正規(guī)集，則稱M和M'是等價的，記為M=M'。

圖2.5和圖2.8所示的FA均識別以正規(guī)式(a|b)*abb所表示的正規(guī)集，兩個FA是等價的。由於DFA上識別記號的確定性和簡單性，往往希望用DFA而不是NFA來識別記號。很幸運，對於任何一個NFA，均可以找到一個與它等價的DFA。這一結(jié)果意味著，對任何正規(guī)集，均可以構(gòu)造一個DFA去識別它。2.4從正規(guī)式到詞法分析器DFA和模擬DFA的演算法2.1，實際上已經(jīng)構(gòu)成了詞法分析器的基礎(chǔ)，從而得到構(gòu)造詞法分析器的一般方法與步驟:①用正規(guī)式對模式進行描述；

②為每個正規(guī)式構(gòu)造一個NFA，它識別正規(guī)式所表示的正規(guī)集；

③將構(gòu)造出的NFA轉(zhuǎn)換成等價的DFA，這一過程也被稱為確定化；

④優(yōu)化DFA，使其狀態(tài)數(shù)最少，這一過程也被稱為最小化；

⑤從優(yōu)化後的DFA構(gòu)造詞法分析器。2.4.1從正規(guī)式到NFA

對任何的正規(guī)式，可以用下述的Thompson演算法構(gòu)造一個NFA，它識別正規(guī)式所表示的正規(guī)集。

演算法2.2Thompson演算法

輸入字母表∑上的正規(guī)式r。

輸出接受L(r)的NFAN。

方法首先，將r分解成最基本的正規(guī)式。由於分解是構(gòu)造的逆過程，因此分解從正規(guī)式的最右端開始。然後按如下規(guī)則進行構(gòu)造。每次構(gòu)造的新狀態(tài)都需重新命名，以使得所有狀態(tài)的名字均不同。

①對ε，構(gòu)造NFA如圖2.10(a)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受ε；

②對∑上的每一個字元a，構(gòu)造NFA如圖2.10(b)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受；③若N(p)和N(q)是正規(guī)式p和q的NFA，則：

(a)對正規(guī)式p|q，構(gòu)造NFA如圖2.10(c)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受L(p)∪L(q)；

(b)對正規(guī)式pq，構(gòu)造NFA如圖2.10(d)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受L(p)L(q)；

(c)對正規(guī)式p*，構(gòu)造NFA如圖2.10(e)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受L(p*)。

④對於正規(guī)式(p)，使用p本身的NFA，不再構(gòu)造新的NFA 圖2.10Thompson演算法中NFA的構(gòu)造

例2.11

用Thompson演算法構(gòu)造正規(guī)式r=(a|b)*abb的N(r)。首先把正規(guī)式分解為如圖2.11(a)所示的樹結(jié)構(gòu)，然後自下而上構(gòu)造整個正規(guī)式的NFA，如圖2.11(b)所示。具體步驟為：運用演算法2.2方法中的②分別為正規(guī)式r1=a、r2=b、r6=a、r8=b、r10=b構(gòu)造NFAN(r1)、N(r2)、N(r6)、N(r8)、N(r10)，運用③(a)為正規(guī)式r3=r1|r2構(gòu)造N(r3)，運用④得到N(r4)=N(r3)，運用③(c)為正規(guī)式r5=r4*構(gòu)造N(r5)，運用③(b)分別為正規(guī)式r7=r5r6、r9=r7r8、r11=r9r10構(gòu)造N(r7)、N(r9)、N(r11)。N(r11)是最終的NFA，其中0為初態(tài)，10為終態(tài)。圖2.11構(gòu)造正規(guī)式(a|b)*abb的NFA(a)分解正規(guī)式；(b)構(gòu)造NFA2.4.2從NFA到DFA1．NFA識別記號的“並行”方法用NFA識別記號的過程，是在NFA上順序地、一條路徑一條路徑試探的過程。由於需要進行回溯，所以演算法構(gòu)造複雜且工作效率低下。事實上，用NFA識別記號，並不採用這種“串行”的方法，而是採用一種“並行”的方法，從而可以消除識別時的不確定性，以避免回溯。

例2.12

從甲地到乙地，可以乘小汽車也可以騎自行車，具體路線如圖2.12所示，其中c表示乘車，b表示騎自行車?，F(xiàn)在要求從甲地到乙地，只許乘車而不許騎自行車，該如何走？此問題抽象在圖2.12上，就是如何找到一條從甲地到乙地的路徑，上邊的標(biāo)記均由c組成。首先，按照常規(guī)一條路徑一條路徑地試探：甲

c2 無路可走，退回甲

c1c3 無路可走，退回甲

c1c乙 到達(dá)乙地，成功圖2.12甲地到乙地的所有路徑

為了避免回溯，設(shè)想有足夠多的小汽車同時走若干條路。假設(shè)從甲地出發(fā)，第一站可以到達(dá)乘車所能到達(dá)地點的全體，再從第一站出發(fā)，第二站可以到達(dá)乘車所能到達(dá)地點的全體，依此類推，直到某一站中包含了乙地。按照這樣的方法，從甲地到乙地的過程與路徑如下所示：甲

c{1,2}c{3,乙}到達(dá)乙地，成功

從識別由c組成的路徑標(biāo)記的角度看，兩種方法的效果是一樣的，但是第二種方法僅有一條確定的路徑，所付出的代價是需要有足夠的小汽車。第二種方法的基本思想是將不確定的下一狀態(tài)確定化：如果從當(dāng)前狀態(tài)出發(fā)經(jīng)c可能到達(dá)不止一個狀態(tài)，則將所有這些狀態(tài)組成一個集合，而虛擬地認(rèn)為到達(dá)這一狀態(tài)集。顯然從當(dāng)前狀態(tài)出發(fā)經(jīng)c到達(dá)這一狀態(tài)集的路徑是唯一確定的。

將這種確定化的思想應(yīng)用於例2.12中特定交通工具的任何一種組合方式，從甲地出發(fā)的一條路徑或者達(dá)到乙地，或者不能到達(dá)乙地，均是確定的，無需也再無其他路徑可以試探。例如，若要求從甲地到乙地，先乘車，再騎自行車，然後再乘車，即在圖2.12上找到一條標(biāo)記為cbc的路徑。則用這種確定化的方法可以找到這樣一條路徑：甲

c{1,2}b{3}。

由於在3處沒有通過乘車可以到達(dá)乙地的路徑，可以斷定上述要求無法從甲地到達(dá)乙地。

將確定化的思想用於NFA上記號的識別，可得到下述與演算法2.1相似的模擬NFA的演算法2.3。該演算法中利用了兩個函數(shù)smove(S,a)和ε_閉包(T)來計算下一狀態(tài)集。S和T分別表示狀態(tài)的集合，a是一個非ε字元。與演算法2.1中的狀態(tài)轉(zhuǎn)移函數(shù)move(s,a)比較，smove(S,a)將狀態(tài)擴大到了狀態(tài)集，它表示從當(dāng)前狀態(tài)集S中的任何狀態(tài)s出發(fā)，經(jīng)字元a可直接到達(dá)狀態(tài)的全體。即move針對的是狀態(tài)，而smove針對的是狀態(tài)集。ε_閉包(T)表示從狀態(tài)集T出發(fā)，經(jīng)ε所能到達(dá)狀態(tài)的全體，更精確的定義在演算法2.3之後給出。

演算法2.3模擬NFA

輸入

NFAN和輸入字串x。x由檔結(jié)束符eof終止，N的初態(tài)為s0，終態(tài)集為F

輸出若N接受x，回答“yes”，否則回答“no”

方法用下邊的過程對x進行識別。S是一個狀態(tài)的集合。S:=ε_閉包({s0}); --所有可能初態(tài)的集合a:=nextchar;whilea≠eofloopS:=ε_閉包(smove(S，a))； --所有下一狀態(tài)的集合

a:=nextchar;endloop;ifS∩F≠Φthenreturn"yes";elsereturn"no";endif;

表2.7演算法2.1與演算法2.3的區(qū)別DFA(演算法2.1)NFA(演算法2.3)區(qū)別初態(tài)初態(tài)集從初態(tài)s0出發(fā)改變?yōu)閺某鯌B(tài)集出發(fā)下一狀態(tài)下一狀態(tài)集當(dāng)前狀態(tài)對字元a的下一狀態(tài)改變?yōu)橄乱粻顟B(tài)集sisinFS∩F≠Φ判斷輸入序列被接受的條件由最後一個狀態(tài)是否是終態(tài)集中的一個狀態(tài)，改變?yōu)樽钺嵋粋€狀態(tài)集與終態(tài)集的交集是否為空集定義2.7

狀態(tài)集T的ε_閉包(T)是一個狀態(tài)集，且滿足：①?T中所有狀態(tài)屬於ε_閉包(T)；②任何smove(ε_閉包(T)，ε)屬於ε_閉包(T)；

③再無其他狀態(tài)屬於ε_閉包(T)。

有關(guān)定義2.7中的三個條件的說明如下：狀態(tài)集T自身在閉包中；若某狀態(tài)已在閉包中，則從此狀態(tài)出發(fā)的任何經(jīng)ε狀態(tài)轉(zhuǎn)移所到達(dá)的下一狀態(tài)也在閉包中。由此可知，ε_閉包(T)就是從狀態(tài)集T出發(fā)，經(jīng)ε所能達(dá)到的狀態(tài)的全體。根據(jù)ε_閉包的定義，不難得到計算ε_閉包的演算法。由於ε_閉包是遞歸定義的，而反映遞歸的最佳數(shù)據(jù)結(jié)構(gòu)是棧，所以演算法中用一個棧來存放所有可能需要計算ε狀態(tài)轉(zhuǎn)移的狀態(tài)。演算法2.4求ε_閉包輸入狀態(tài)集T輸出狀態(tài)集T的ε_閉包方法用下麵的函數(shù)計算ε_閉包

functionε_閉包(T)isbeginforT中每個狀態(tài)tloop加入t到U;push(t);endloop;while棧不空

looppop(t);for每個u=move(t,ε)loopifu不在U中then加入u到U;push(u);endif;endloop;endloop;returnU;endε_閉包;

例2.13

用演算法2.3在圖2.11(b)所示的NFA上識別記號abb和abab的過程分別如下。識別abb①計算初態(tài)集：

ε_閉包({0})={0,1,2,4,7}，令初態(tài)集為A。②計算從狀態(tài)集A出發(fā)，經(jīng)a所到達(dá)的下一狀態(tài)集：

ε_閉包(smove(A,a)={3,8,6,7,1,2,4}，令它為B。③計算從狀態(tài)集B出發(fā)，經(jīng)b所到達(dá)的下一狀態(tài)集：

ε_閉包(smove(B,b)={5,9,6,7,1,2,4}，令它為C。④計算從狀態(tài)集C出發(fā)，經(jīng)b所到達(dá)的下一狀態(tài)集：

ε_閉包(smove(C,b)={5,10,6,7,1,2,4}，令它為D。⑤輸入序列已經(jīng)結(jié)束，且D∩{10}={10}，abb被接受。故abb的識別路徑為：AaBbCbD。識別abab:ε_閉包(s0)={0,1,2,4,7}Aε_閉包(smove({0,1,2,4,7},a))={3,8,6,7,1,2,4}Bε_閉包(smove({3,8,6,7,1,2,4},b))={5,9,6,7,1,2,4}Cε_閉包(smove({5,9,6,7,1,2,4},a))={3,8,6,7,1,2,4}Bε_閉包(smove({3,8,6,7,1,2,4},b))={5,9,6,7,1,2,4}C故abab的識別路徑為：AaBbCaBbC。由於C∩{10}=Φ，所以序列abab不被接受。2．“子集法”構(gòu)造DFA

雖然用演算法2.3在NFA上識別輸入序列的過程也是確定的，無需回溯，但是，它付出的代價是每走一步就要計算一次下一狀態(tài)轉(zhuǎn)移的集合。該計算分兩步走：首先計算當(dāng)前狀態(tài)集的smove函數(shù)，得到一個集合，然後計算此集合的ε_閉包。ε_閉包的計算是遞歸的，需耗費大量時間，使得用NFA識別輸入序列的效率很低。事實上，演算法2.3的每次識別都是將一條路徑確定化。延伸這一觀點，預(yù)先將NFA上的全部路徑均確定化，並且把它們記錄下來，形成一個與NFA等價的DFA。而對記號的識別在DFA上進行，從而省去計算狀態(tài)集的時間，以提高識別效率。

例2.14

將圖2.12中的所有路徑確定化得到圖2.13。圖2.13中從甲地到乙地允許的合法走法為cc，ccb和cbb三條路徑，與圖2.12中的合法路徑完全相同，所以二者是等價的。用圖2.13分別識別cc和cbc的過程為：甲

c{1,2}c{3,乙}，接受甲

c{1,2}b{3}c?，不接受與用圖2.12識別的結(jié)果完全相同。圖2.13確定化後的甲地到乙地的所有路徑

將所有路徑確定化以構(gòu)造DFA的演算法被歸納在演算法2.5中。由於新構(gòu)造的DFA中的每個狀態(tài)是原NFA所有狀態(tài)的一個子集，所以也將此演算法稱為構(gòu)造DFA的“子集法”。演算法中用Dstates存放DFA的狀態(tài)，Dstates中每個狀態(tài)是NFA全體狀態(tài)的一個子集；smove(T,a)與演算法2.3中的smove(S,a)意義相同；Dtran是一個狀態(tài)轉(zhuǎn)換矩陣，用它存放DFA的狀態(tài)轉(zhuǎn)移，即若ε_閉包(smove(T,a))=U，則Dtran[T，a]中存放U。值得注意的是，由於DFA的一個狀態(tài)是NFA全體狀態(tài)的一個子集，所以在最壞情況下，有n個狀態(tài)的NFA，其等價DFA的狀態(tài)數(shù)可能是O(2n)級的。當(dāng)遇到這種特殊情況且n很大時，往往不將NFA確定化為DFA，而是直接利用NFA和演算法2.3對輸入序列進行分析，也就是每分析一次，僅確定一條路徑，從而減少了對存儲空間的需求。

演算法2.5從NFA構(gòu)造DFA(子集法)

輸入一個NFAN

輸出一個接受同一正規(guī)集的DFAD。其中，含有NFA初態(tài)的DFA狀態(tài)為DFA的初態(tài)，所有含有NFA終態(tài)的DFA狀態(tài)構(gòu)成DFA的終態(tài)集。方法用下述過程構(gòu)造DFA：

ε_閉包({s0})是Dstates僅有的狀態(tài)，且尚未標(biāo)記;whileDstates有尚未標(biāo)記的狀態(tài)Tloop標(biāo)記T;

for每一個輸入字元aloopU:=ε_閉包(smove(T，a));ifU不在Dstates中

thenU作為尚未標(biāo)記的狀態(tài)加入Dstates;endif;Dtran[T，a]:=U;endloop;endloop;

例2.15

將演算法2.5應(yīng)用於圖2.11(b)所示的NFA上，計算步驟如下所示。其中標(biāo)有*的集合是第一次出現(xiàn)，在演算法中需要被標(biāo)記並處理。所得的DFA如圖2.14所示，其中A是初態(tài)，E是終態(tài)集中僅有的終態(tài)。圖2.14識別(a|b)*abb的DFA(a)轉(zhuǎn)換圖表示的DFA；(b)轉(zhuǎn)換矩陣表示的DFAε_閉包({0})={0,1,2,4,7}*Aε_閉包(smove({0,1,2,4,7}, a))={3,8,6,7,1,2,4}* Bε_閉包(smove({0,1,2,4,7}, b))={5,6,7,1,2,4}* Cε_閉包(smove({3,8,6,7,1,2,4}, a))={3,8,6,7,1,2,4} Bε_閉包(smove({3,8,6,7,1,2,4}, b))={5,9,6,7,1,2,4}* Dε_閉包(smove({5,6,7,1,2,4}, a))={3,8,6,7,1,2,4} Bε_閉包(smove({5,6,7,1,2,4}, b))={5,6,7,1,2,4} Cε_閉包(smove({5,9,6,7,1,2,4}, a))={3,8,6,7,1,2,4} Bε_閉包(smove({5,9,6,7,1,2,4}, b))={5,10,6,7,1,2,4}* Eε_閉包(smove({5,10,6,7,1,2,4}, a))={3,8,6,7,1,2,4} Bε_閉包(smove({5,10,6,7,1,2,4}, b))={5,6,7,1,2,4} C

例2.16

在圖2.14的DFA上識別輸入序列abb和abab，其結(jié)果與在NFA上識別的結(jié)果完全相同。步驟如下：識別abb:AaBbDbE 接受識別abab:AaBbDaBbD 不接受2.4.3最小化DFA

比較圖2.8和圖2.14所示的DFA，它們接受相同的正規(guī)集，說明兩個DFA是等價的，但是它們的狀態(tài)數(shù)不同。一般來說，對於若干個等價的DFA，總是希望由狀態(tài)數(shù)最少的DFA構(gòu)造詞法分析器。將一個DFA等價變換為另一個狀態(tài)數(shù)最少的DFA的過程被稱為最小化DFA，相應(yīng)DFA稱為最小DFA。

定義2.8

對於任何兩個狀態(tài)t和s，若從一狀態(tài)出發(fā)接受輸入字串ω，而從另一狀態(tài)出發(fā)不接受ω，或者從t出發(fā)和從s出發(fā)到達(dá)不同的接受狀態(tài)，則稱ω對狀態(tài)t和s是可區(qū)分的。 反方向思考定義2.8，設(shè)想任何輸入序列ω對s和t均是不可區(qū)分的，則說明分別從s出發(fā)和從t出發(fā)來分析任何輸入序列ω，均得到相同結(jié)果。因此，s和t可以合併成一個狀態(tài)。演算法2.6用來最小化DFA的狀態(tài)數(shù)，它的基本思想就是反向利用可區(qū)分的概念。一開始，僅有非終態(tài)和各終態(tài)是可區(qū)分的，經(jīng)過一系列劃分，把可區(qū)分的狀態(tài)分離出來，直到不可再分離為止。根據(jù)可區(qū)分的概念可知，所有不可區(qū)分的狀態(tài)可以合併成一個狀態(tài)。

演算法2.6最小化DFA的狀態(tài)數(shù)輸入一個DFAD={S，∑，move，s0，F(xiàn)}

輸出一個DFAD'={S'，∑，move'，s0'，F(xiàn)'}，它和D接受同樣的正規(guī)集，但是狀態(tài)數(shù)最少方法

①構(gòu)造狀態(tài)集的初始劃分Π={S-F，F(xiàn)1，F(xiàn)2，...}，其中F1，F(xiàn)2，……均是F的子集，它們接受不同的記號；②應(yīng)用下述過程構(gòu)造新的劃分Πnew：forΠ的每一個組Gloop

對G進行劃分，G中的兩個狀態(tài)s和t被劃分在同一個組中的充要條件是:

任何輸入字元a，move(s,a)和move(t,a)在Π的同一個組中；用新劃分的組替代G，形成新的劃分Πnew；endloop；

③若Πnew=Π，令Πfinal=Π，並轉(zhuǎn)向步驟④；否則，令Π=Πnew並重複步驟②；

④在Πfinal的每個組Gi中選一個代表si'，使得D中從Gi中所有狀態(tài)出發(fā)的狀態(tài)轉(zhuǎn)移在D'中均從si出發(fā)，D中所有轉(zhuǎn)向Gi中狀態(tài)的狀態(tài)轉(zhuǎn)移在D'中均轉(zhuǎn)向si'；含有D中s0的狀態(tài)組G0的代表s0'稱為D的初態(tài)，D中所有含F(xiàn)中狀態(tài)的Gj的代表sj'構(gòu)成D'的終態(tài)集F?'；

⑤若D'中有狀態(tài)d，它不是終態(tài)且對於所有輸入字元均轉(zhuǎn)向其自身，則稱d為死狀態(tài)；將d從D'中刪除，同時也刪除所有從初態(tài)不可到達(dá)的狀態(tài)，從其他狀態(tài)到d的任何狀態(tài)轉(zhuǎn)移被認(rèn)為無意義。

例2.17

用演算法2.6對圖2.14中的DFA進行狀態(tài)化簡:①初始化劃分Π={{A，B，C，D}，{E}}。

②考察當(dāng)前劃分Π。E自身一個組，不能再分，ABCD在一個組，查看它們的狀態(tài)轉(zhuǎn)移：

move(A,a)=B, move(A,b)=Cmove(B,a)=B, move(B,b)=Dmove(C,a)=B, move(C,b)=Cmove(D,a)=B, move(D,b)=E

其中move(D,b)=E使得D與ABC不能在同一組中，分離D形成新的劃分:Πnew={{A，B，C}，{D}，{E}}③Π≠Πnew，令Π=Πnew，重複②。

②考察當(dāng)前劃分Π。ABC在一個組，查看它們的狀態(tài)轉(zhuǎn)移：

move(A,a)=B, move(A,b)=Cmove(B,a)=B, move(B,b)=Dmove(C,a)=B, move(C,b)=C

其中move(B,b)=D使得B與AC不能在同一組中，分離B形成新的劃分:Πnew={{A，C}，{B}，{D}，{E}}③Π≠Πnew，令Π=Πnew，重複②。

②考察當(dāng)前劃分Π。AC在一個組，查看它們的狀態(tài)轉(zhuǎn)移：

move(A,a)=B, move(A,b)=Cmove(C,a)=B, move(C,b)=C顯然A和C是不可區(qū)分的，使得

Πnew={{A，C}，{B}，{D}，{E}}③Π=Πnew，令Πfinal=Π，轉(zhuǎn)向④。

④在Πfinal的每個組中選一個代表，用A代表{A，C}，其餘均自己代表自己，最後形成僅有4個狀態(tài)的最小DFAD'；如果將狀態(tài)A、B、D、E分別編號為0、1、2、3，則D'如圖2.8所示。2.4.4由DFA構(gòu)造詞法分析器1．表驅(qū)動型詞法分析器如果將DFA用狀態(tài)轉(zhuǎn)換矩陣表示，則它與模擬DFA的演算法(演算法2.1)構(gòu)成了一個表驅(qū)動型的詞法分析器，其中轉(zhuǎn)換矩陣是分析器的分析表，而演算法2.1就是分析器的驅(qū)動器。表驅(qū)動型詞法分析器的一般工作模式如圖2.15所示，它實際上就是有限自動機的工作模型。圖2.15表驅(qū)動型詞法分析器

演算法2.1是一個簡化了的概念模式，實際的驅(qū)動器需要根據(jù)情況進行修改。最大的修改是關(guān)於輸入序列。演算法2.1假設(shè)僅識別以eof結(jié)束的一個記號，而實際的根源程式是由許多記號組成的記號流。例如result:=expr就是由識別字、賦值號、識別字三個記號組成的。對於驅(qū)動器來說，判定是否識別出一個記號的條件不應(yīng)是遇到eof，而是一個更合理的方法。一般採用的方法是所謂的最長匹配原則，即對於任何輸入序列，總是儘量匹配，直到?jīng)]有下一狀態(tài)轉(zhuǎn)移為止。例如，abbabb被識別為一個而不是兩個記號，而abbab不被接受。使用最長匹配原則，對上述result:=expr的第一個識別字的匹配一直要遇到冒號時才會因找不到下一狀態(tài)轉(zhuǎn)移而識別出一個屬性為result的識別字，不應(yīng)誤識別出r、re、或res等。2．直接編碼型詞法分析器另一類詞法分析器無需分析表指導(dǎo)分析動作，而直接將DFA轉(zhuǎn)換為程式，即直接用程式代碼模擬DFA的行為。將DFA用直觀的狀態(tài)轉(zhuǎn)換圖表示，它實質(zhì)上就是一個抽象的程式流圖。轉(zhuǎn)換圖忽略了程式的實現(xiàn)細(xì)節(jié)，著力刻劃了記號識別的本質(zhì)。轉(zhuǎn)換圖與程式結(jié)構(gòu)之間存在下述對應(yīng)關(guān)係，並可據(jù)此構(gòu)造相應(yīng)的程式：

①初態(tài)對應(yīng)程式的開始；

②終態(tài)對應(yīng)程式的結(jié)束，一般是一條返回語句，且不同的終態(tài)對應(yīng)不同的返回語句；

③狀態(tài)轉(zhuǎn)移對應(yīng)分情況或者條件語句；

④轉(zhuǎn)換圖中的環(huán)對應(yīng)程式中的迴圈語句；

⑤終態(tài)返回時，應(yīng)滿足最長匹配原則。

例2.18

根據(jù)上述轉(zhuǎn)換圖與程式結(jié)構(gòu)的簡單對應(yīng)關(guān)係，可以將圖2.8所示的DFA轉(zhuǎn)換為下述示意性的詞法分析器。其中的標(biāo)號s0、s1、s2、s3分別表示語句與狀態(tài)的對應(yīng)，除了s0和s1之外，其餘的標(biāo)號均無實際意義。beginch:=getchar；s0:loopwhilech=bloopch:=getchar；endloop；s1:whilech=aloopch:=getchar；endloop；

?casechis a:null;s2:b:ch:=getchar；

casechisa:gotos1;s3:b:ch:=getchar;casechisa:gotos1;b:gotos0;eof:return(yes)；others:return(no);endcase;others:return(no)；

endcase；

others:return(no)；

endcase；

endloop；end；3．兩類分析器的比較直接編碼詞法分析器和表驅(qū)動詞法分析器的工作原理完全相同，它們的基本依據(jù)都是DFA。但是，二者在與模式的關(guān)係、分析器的構(gòu)造以及分析器的分析效率諸方面均有很大差別。從分析器與模式之間的關(guān)係講，表驅(qū)動型分析器的驅(qū)動器僅對分析表的內(nèi)容進行操作，而與所識別的記號無關(guān)，具體識別什麼記號，由分析表中與模式密切相關(guān)的數(shù)據(jù)來控制，是一種典型的數(shù)據(jù)與操作分離的工作模式，構(gòu)造不同的詞法分析器實質(zhì)上成為構(gòu)造不同的分析表。而直接編碼型的詞法分析器，是通過程式的控制流轉(zhuǎn)移來完成對輸入字串的回應(yīng)，可以說程式的每一條語句都與模式密切相關(guān)，一旦模式改變，則程式必須改變。

從分析器的構(gòu)造方法講，表驅(qū)動型詞法分析器的數(shù)據(jù)與操作分離的模式，為詞法分析器的自動生成提供了極大的方便。因為，從正規(guī)式到DFA的轉(zhuǎn)換矩陣表示，均可以通過成熟的演算法由電腦來自動完成。而對於直接編碼的詞法分析器，需要將狀態(tài)轉(zhuǎn)換圖變?yōu)槌淌酱a，即便有一般的對應(yīng)關(guān)係，但轉(zhuǎn)換圖的複雜性和程式代碼的多樣性均使得這一過程並不容易。從例2.18可以看出，即使處理這樣一個簡單的模式，其程式設(shè)計也並不簡單，更何況構(gòu)造分析多個複雜模式的分析器了。一般來講，直接編碼型的詞法分析器適用於詞法比較簡單的情況，並且也無需教條地按照正規(guī)式、NFA、DFA、程式代碼的步驟去構(gòu)造，而是直接由正規(guī)式手工構(gòu)造狀態(tài)轉(zhuǎn)換圖，然後翻譯為程式代碼，或者乾脆直接根據(jù)正規(guī)式編寫程式代碼。

從分析器的工作效率講，表驅(qū)動詞法分析器在工作中需要查表確定分析器的動作，每一步分析多了至少一次間接訪問的工作，在分析輸入序列的效率上比直接編碼分析器的效率要低。但是隨著電腦技術(shù)的發(fā)展，軟體的損失已被硬體速度的提高彌補。歸納起來，兩類分析器的特點如表2.8所示。表2.8兩類分析器的比較

分析器速度程式與模式的關(guān)係分析器的規(guī)模適合的編寫方法表驅(qū)動慢無關(guān)較大工具生成直接編碼快相關(guān)較小手工編寫2.4.5詞法分析器生成器簡介回顧詞法分析器的構(gòu)造過程：正規(guī)式—NFA—DFA—最小化DFA—詞法分析器(分析表)，每一步都可以借助於成熟的演算法來構(gòu)造，無需人工干預(yù)。詞法分析器生成器，就是將這些演算法組合起來所形成的軟體，利用這樣的軟體，只需將所需的詞法分析器識別的記號用正規(guī)式的方式描述出來，生成器就會自動生成相應(yīng)的詞法分析器。當(dāng)前最成熟、最被廣泛應(yīng)用的詞法分析器生成器是LEX和與LEX相似的工具，不妨統(tǒng)稱為LEX。

例2.19

例2.6中關(guān)於id和num的說明，可以用LEX的形式表示如下，其中的輔助定義和規(guī)則以LEX提供的形式書寫，而語義動作也僅是示意性的。需要指出，此處{}是重載的，它既可以用來標(biāo)記對輔助定義名字的引用，如{char}、{digit}等，也可以用來界定用戶書寫的相關(guān)語義動作，如{printf("id:%s",yytext);return(ID);}等。

%{#include<stdio.h>%}char[a-zA-Z]digit [0-9]digits {digit}+optional_fracti