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

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

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

例2.1

對(duì)於語(yǔ)句：position:=initial+rate*60，可以識(shí)別出下述序列：識(shí)別字特殊符號(hào)識(shí)別字特殊符號(hào)識(shí)別字特殊符號(hào)數(shù)字字面量其中position、initial、rate均被識(shí)別為識(shí)別字，因?yàn)樗鼈兙贤粭l規(guī)則，即以字母打頭的字母數(shù)字串。記號(hào)至少含有兩個(gè)資訊：一個(gè)是記號(hào)的類別，如“識(shí)別字”；另一個(gè)是記號(hào)的值，如“position”。顯然，如果把記號(hào)看作是一個(gè)類型的話，則單詞就是一個(gè)類型中的實(shí)例。由於我們總是說(shuō)識(shí)別出一個(gè)識(shí)別字，而不說(shuō)識(shí)別出一個(gè)position或rate，因而將詞法分析器識(shí)別出的序列稱為記號(hào)流。

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

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

例2.2

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

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

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

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

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

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

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

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

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

thenreturnerror；

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

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

定義2.1語(yǔ)言L是有限字母表∑上有限長(zhǎng)度字串的集合。定義2.1明確指出，語(yǔ)言是一個(gè)集合，集合中的元素是字串，並且強(qiáng)調(diào)了兩個(gè)有限:①字母表是有限的，即字母表中元素是有限多個(gè)；②字串的長(zhǎng)度是有限的，即字串中字元個(gè)數(shù)是有限多個(gè)。這是由於電腦所能表示的字元個(gè)數(shù)和字串的長(zhǎng)度都是有限的。

由於字串的有序性，使得以字串作為元素的集合具有某些特性。字串和集合的基本概念和特性，以表格的形式分別列在表2.3和表2.4中。其中，字串的連接運(yùn)算是一種新形式的運(yùn)算，它表示兩個(gè)字串首尾相接，形成一個(gè)新的集合。例如，S1="pre"，S2="fix"，則S1S2="prefix"。值得注意的是，集合中連接運(yùn)算所形成的新集合與交運(yùn)算形成的新集合完全不同。例如，若L={"pre"，M={"fix"，則L∩M=Φ，而LM={"prefix"。表2.3字串的基本概念表2.4字串集合上的基本運(yùn)算2.2.2正規(guī)式與正規(guī)集定義2.2令Σ是一個(gè)有限字母表，則Σ上的正規(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ī)式描述的語(yǔ)言稱為正規(guī)語(yǔ)言或正規(guī)集。

定義2.2中①和②規(guī)定了正規(guī)式的基本運(yùn)算元或基本正規(guī)式。定義2.2的③給出了正規(guī)式上的三種運(yùn)算:(a)或運(yùn)算、(b)連接運(yùn)算和(c)閉包運(yùn)算。對(duì)於由多個(gè)運(yùn)算元和多個(gè)操作符組成的正規(guī)式，可以利用(d)所給的括弧規(guī)定運(yùn)算的先後次序。如果對(duì)或、連接和閉包運(yùn)算進(jìn)行如下約定:①三種運(yùn)算均具有左結(jié)合性質(zhì)；②運(yùn)算的優(yōu)先順序從高到低順序排列為:閉包運(yùn)算、連接運(yùn)算、或運(yùn)算。則正規(guī)式中不必要的括弧可以被省略。例如，(a)|((b)*(c))可以簡(jiǎn)化成a|b*c。

例2.3

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

正規(guī)集是一個(gè)集合，而正規(guī)式是表示正規(guī)集的一種方法。正如不同算術(shù)運(yùn)算式可以表示同一個(gè)數(shù)(如3+5、5+3、2+6等均表示8)一樣，不同正規(guī)式也可以表示同一個(gè)正規(guī)集，即正規(guī)式與正規(guī)集之間是多對(duì)一的關(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表示同一個(gè)正規(guī)集。

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

例2.5

表2.1中的記號(hào)relation、id和num分別是Pascal的關(guān)係運(yùn)算符、識(shí)別字和無(wú)符號(hào)數(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ī)式給出了識(shí)別字的精確定義，用自然語(yǔ)言可以描述為“字母是英文26個(gè)字母大小寫(xiě)中任何一個(gè)，數(shù)字是十進(jìn)位阿拉伯?dāng)?shù)字中的任何一個(gè)，識(shí)別字是以字母打頭的、其後可跟隨0個(gè)或若干個(gè)字母或數(shù)字的字串”。1．簡(jiǎn)化正規(guī)式描述為了簡(jiǎn)化正規(guī)式的描述，通?？梢話?cǎi)用如下的幾種正規(guī)式的縮寫(xiě)形式。

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

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

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

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

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

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

例2.6

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

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記號(hào)的識(shí)別——有限自動(dòng)機(jī)2.3.1不確定的有限自動(dòng)機(jī)(NondeterministicFiniteAutomata，NFA)

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

其中：①S是有限個(gè)狀態(tài)(state)的集合；②∑是有限個(gè)輸入字元(包括ε)的集合；③move是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)，move(si，ch)=sj表示當(dāng)前狀態(tài)si下若遇到輸入字元ch，則轉(zhuǎn)移到狀態(tài)sj；④s0是唯一的初態(tài)(也稱開(kāi)始狀態(tài))；⑤F是終態(tài)集(也稱接受狀態(tài)集)，它是S的子集，包含了所有的終態(tài)。

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

例2.7

識(shí)別由正規(guī)式(a|b)*abb說(shuō)明的記號(hào)的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識(shí)別(a|b)*abb的NFA(a)轉(zhuǎn)換圖表示的NFA；(b)轉(zhuǎn)換矩陣表示的NFA

例2.8

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

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

例2.9

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

從例2.9中可以看出，用NFA識(shí)別記號(hào)存在下述問(wèn)題：

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

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

定義2.5DFA是NFA的一個(gè)特例，其中：①?zèng)]有狀態(tài)具有ε狀態(tài)轉(zhuǎn)移(ε-transition)，即狀態(tài)轉(zhuǎn)換圖中沒(méi)有標(biāo)記ε的邊；②對(duì)每一個(gè)狀態(tài)s和每一個(gè)字元a，最多有一個(gè)下一狀態(tài)。

例2.10

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

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

演算法2.1模擬DFA

輸入

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

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

方法用下述過(guò)程識(shí)別x：

s:=s0；a:=nextchar；

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

ifsisinFthenreturn"yes"；elsereturn"no"；endif；2.3.3有限自動(dòng)機(jī)的等價(jià)

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

定義2.6

若有限自動(dòng)機(jī)M和M'識(shí)別同一個(gè)正規(guī)集，則稱M和M'是等價(jià)的，記為M=M'。

圖2.5和圖2.8所示的FA均識(shí)別以正規(guī)式(a|b)*abb所表示的正規(guī)集，兩個(gè)FA是等價(jià)的。由於DFA上識(shí)別記號(hào)的確定性和簡(jiǎn)單性，往往希望用DFA而不是NFA來(lái)識(shí)別記號(hào)。很幸運(yùn)，對(duì)於任何一個(gè)NFA，均可以找到一個(gè)與它等價(jià)的DFA。這一結(jié)果意味著，對(duì)任何正規(guī)集，均可以構(gòu)造一個(gè)DFA去識(shí)別它。2.4從正規(guī)式到詞法分析器DFA和模擬DFA的演算法2.1，實(shí)際上已經(jīng)構(gòu)成了詞法分析器的基礎(chǔ)，從而得到構(gòu)造詞法分析器的一般方法與步驟:①用正規(guī)式對(duì)模式進(jìn)行描述；②為每個(gè)正規(guī)式構(gòu)造一個(gè)NFA，它識(shí)別正規(guī)式所表示的正規(guī)集；③將構(gòu)造出的NFA轉(zhuǎn)換成等價(jià)的DFA，這一過(guò)程也被稱為確定化；④優(yōu)化DFA，使其狀態(tài)數(shù)最少，這一過(guò)程也被稱為最小化；⑤從優(yōu)化後的DFA構(gòu)造詞法分析器。2.4.1從正規(guī)式到NFA

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

演算法2.2Thompson演算法

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

輸出接受L(r)的NFAN。

方法首先，將r分解成最基本的正規(guī)式。由於分解是構(gòu)造的逆過(guò)程，因此分解從正規(guī)式的最右端開(kāi)始。然後按如下規(guī)則進(jìn)行構(gòu)造。每次構(gòu)造的新?tīng)顟B(tài)都需重新命名，以使得所有狀態(tài)的名字均不同。①對(duì)ε，構(gòu)造NFA如圖2.10(a)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受ε；②對(duì)∑上的每一個(gè)字元a，構(gòu)造NFA如圖2.10(b)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受；③若N(p)和N(q)是正規(guī)式p和q的NFA，則：

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

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

(c)對(duì)正規(guī)式p*，構(gòu)造NFA如圖2.10(e)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受L(p*)。④對(duì)於正規(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)所示的樹(shù)結(jié)構(gòu)，然後自下而上構(gòu)造整個(gè)正規(guī)式的NFA，如圖2.11(b)所示。具體步驟為：運(yùn)用演算法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)，運(yùn)用③(a)為正規(guī)式r3=r1|r2構(gòu)造N(r3)，運(yùn)用④得到N(r4)=N(r3)，運(yùn)用③(c)為正規(guī)式r5=r4*構(gòu)造N(r5)，運(yùn)用③(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識(shí)別記號(hào)的“並行”方法用NFA識(shí)別記號(hào)的過(guò)程，是在NFA上順序地、一條路徑一條路徑試探的過(guò)程。由於需要進(jìn)行回溯，所以演算法構(gòu)造複雜且工作效率低下。事實(shí)上，用NFA識(shí)別記號(hào)，並不採(cǎi)用這種“串行”的方法，而是採(cǎi)用一種“並行”的方法，從而可以消除識(shí)別時(shí)的不確定性，以避免回溯。

例2.12

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

c2 無(wú)路可走，退回甲

c1c3 無(wú)路可走，退回甲

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

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

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

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

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

c{1,2}b{3}。?由於在3處沒(méi)有通過(guò)乘車可以到達(dá)乙地的路徑，可以斷定上述要求無(wú)法從甲地到達(dá)乙地。

將確定化的思想用於NFA上記號(hào)的識(shí)別，可得到下述與演算法2.1相似的模擬NFA的演算法2.3。該演算法中利用了兩個(gè)函數(shù)smove(S,a)和ε_(tái)閉包(T)來(lái)計(jì)算下一狀態(tài)集。S和T分別表示狀態(tài)的集合，a是一個(gè)非ε字元。與演算法2.1中的狀態(tài)轉(zhuǎn)移函數(shù)move(s,a)比較，smove(S,a)將狀態(tài)擴(kuò)大到了狀態(tài)集，它表示從當(dāng)前狀態(tài)集S中的任何狀態(tài)s出發(fā)，經(jīng)字元a可直接到達(dá)狀態(tài)的全體。即move針對(duì)的是狀態(tài)，而smove針對(duì)的是狀態(tài)集。ε_(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”

方法用下邊的過(guò)程對(duì)x進(jìn)行識(shí)別。S是一個(gè)狀態(tài)的集合。S:=ε_(tái)閉包({s0}); --所有可能初態(tài)的集合a:=nextchar;whilea≠eofloopS:=ε_(tái)閉包(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)對(duì)字元a的下一狀態(tài)改變?yōu)橄乱粻顟B(tài)集sisinFS∩F≠Φ判斷輸入序列被接受的條件由最後一個(gè)狀態(tài)是否是終態(tài)集中的一個(gè)狀態(tài)，改變?yōu)樽钺嵋粋€(gè)狀態(tài)集與終態(tài)集的交集是否為空集定義2.7

狀態(tài)集T的ε_(tái)閉包(T)是一個(gè)狀態(tài)集，且滿足：①?T中所有狀態(tài)屬於ε_(tái)閉包(T)；②任何smove(ε_(tái)閉包(T)，ε)屬於ε_(tái)閉包(T)；③再無(wú)其他狀態(tài)屬於ε_(tái)閉包(T)。

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

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

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

例2.13

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

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

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

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

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

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

例2.14

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

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

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

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

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

輸入一個(gè)NFAN

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

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

for每一個(gè)輸入字元aloopU:=ε_(tái)閉包(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上，計(jì)算步驟如下所示。其中標(biāo)有*的集合是第一次出現(xiàn)，在演算法中需要被標(biāo)記並處理。所得的DFA如圖2.14所示，其中A是初態(tài)，E是終態(tài)集中僅有的終態(tài)。圖2.14識(shí)別(a|b)*abb的DFA(a)轉(zhuǎn)換圖表示的DFA；(b)轉(zhuǎn)換矩陣表示的DFAε_(tái)閉包({0})={0,1,2,4,7}*Aε_(tái)閉包(smove({0,1,2,4,7}, a))={3,8,6,7,1,2,4}* Bε_(tái)閉包(smove({0,1,2,4,7}, b))={5,6,7,1,2,4}* Cε_(tái)閉包(smove({3,8,6,7,1,2,4}, a))={3,8,6,7,1,2,4} Bε_(tái)閉包(smove({3,8,6,7,1,2,4}, b))={5,9,6,7,1,2,4}* Dε_(tái)閉包(smove({5,6,7,1,2,4}, a))={3,8,6,7,1,2,4} Bε_(tái)閉包(smove({5,6,7,1,2,4}, b))={5,6,7,1,2,4} Cε_(tái)閉包(smove({5,9,6,7,1,2,4}, a))={3,8,6,7,1,2,4} Bε_(tái)閉包(smove({5,9,6,7,1,2,4}, b))={5,10,6,7,1,2,4}* Eε_(tái)閉包(smove({5,10,6,7,1,2,4}, a))={3,8,6,7,1,2,4} Bε_(tái)閉包(smove({5,10,6,7,1,2,4}, b))={5,6,7,1,2,4} C

例2.16

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

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

定義2.8

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

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

輸出一個(gè)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的子集，它們接受不同的記號(hào)；②應(yīng)用下述過(guò)程構(gòu)造新的劃分Πnew：forΠ的每一個(gè)組Gloop

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

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

③若Πnew=Π，令Πfinal=Π，並轉(zhuǎn)向步驟④；否則，令Π=Πnew並重複步驟②；④在Πfinal的每個(gè)組Gi中選一個(gè)代表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)且對(duì)於所有輸入字元均轉(zhuǎn)向其自身，則稱d為死狀態(tài)；將d從D'中刪除，同時(shí)也刪除所有從初態(tài)不可到達(dá)的狀態(tài)，從其他狀態(tài)到d的任何狀態(tài)轉(zhuǎn)移被認(rèn)為無(wú)意義。

例2.17

用演算法2.6對(duì)圖2.14中的DFA進(jìn)行狀態(tài)化簡(jiǎn):①初始化劃分Π={{A，B，C，D}，{E}}。②考察當(dāng)前劃分Π。E自身一個(gè)組，不能再分，ABCD在一個(gè)組，查看它們的狀態(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在一個(gè)組，查看它們的狀態(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在一個(gè)組，查看它們的狀態(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的每個(gè)組中選一個(gè)代表，用A代表{A，C}，其餘均自己代表自己，最後形成僅有4個(gè)狀態(tài)的最小DFAD'；如果將狀態(tài)A、B、D、E分別編號(hào)為0、1、2、3，則D'如圖2.8所示。2.4.4由DFA構(gòu)造詞法分析器1．表驅(qū)動(dòng)型詞法分析器如果將DFA用狀態(tài)轉(zhuǎn)換矩陣表示，則它與模擬DFA的演算法(演算法2.1)構(gòu)成了一個(gè)表驅(qū)動(dòng)型的詞法分析器，其中轉(zhuǎn)換矩陣是分析器的分析表，而演算法2.1就是分析器的驅(qū)動(dòng)器。表驅(qū)動(dòng)型詞法分析器的一般工作模式如圖2.15所示，它實(shí)際上就是有限自動(dòng)機(jī)的工作模型。圖2.15表驅(qū)動(dòng)型詞法分析器

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

例2.18

根據(jù)上述轉(zhuǎn)換圖與程式結(jié)構(gòu)的簡(jiǎn)單對(duì)應(yīng)關(guān)係，可以將圖2.8所示的DFA轉(zhuǎn)換為下述示意性的詞法分析器。其中的標(biāo)號(hào)s0、s1、s2、s3分別表示語(yǔ)句與狀態(tài)的對(duì)應(yīng)，除了s0和s1之外，其餘的標(biāo)號(hào)均無(wú)實(shí)際意義。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ū)動(dòng)詞法分析器的工作原理完全相同，它們的基本依據(jù)都是DFA。但是，二者在與模式的關(guān)係、分析器的構(gòu)造以及分析器的分析效率諸方面均有很大差別。從分析器與模式之間的關(guān)係講，表驅(qū)動(dòng)型分析器的驅(qū)動(dòng)器僅對(duì)分析表的內(nèi)容進(jìn)行操作，而與所識(shí)別的記號(hào)無(wú)關(guān)，具體識(shí)別什麼記號(hào)，由分析表中與模式密切相關(guān)的數(shù)據(jù)來(lái)控制，是一種典型的數(shù)據(jù)與操作分離的工作模式，構(gòu)造不同的詞法分析器實(shí)質(zhì)上成為構(gòu)造不同的分析表。而直接編碼型的詞法分析器，是通過(guò)程式的控制流轉(zhuǎn)移來(lái)完成對(duì)輸入字串的回應(yīng)，可以說(shuō)程式的每一條語(yǔ)句都與模式密切相關(guān)，一旦模式改變，則程式必須改變。

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

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

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

例2.19

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

%{#include<stdio.h>%}char[a-zA-Z]digit [0-9]digits {digit}+optional_fraction(\.{digits})?optional_exponent(E(?\?+?|?–?)?{digits})?%%{char}({char}|{digit})*