第2章詞法分析2.1詞法分析中的若干問題

2.2模式的形式化描述

2.3記號的識別——有限自動機(jī)

2.4從正規(guī)式到詞法分析器

2.5本章小結(jié)

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

(1)關(guān)鍵字(保留字)．

(2)標(biāo)識符：標(biāo)識符是程序設(shè)計(jì)語言中最大的一個類別，它的作用是為某個實(shí)體起一個名字，以便于今后稱呼(引用)可以用標(biāo)識符來命名的實(shí)體包括類型、變量、過程、常量、類、對象、程序包、標(biāo)號等，即類型名、變量名、過程名、常量名等。(3)字面量：字面量是指直接以其字面所表示的常量，如25、true、"Thisisastring"等。值得注意的是，字面量與常量是兩個不同的概念，常量可以是一個字面量(直接表示)，也可以是一個常量名(命名表示)。(4)特殊符號：程序設(shè)計(jì)語言中的特殊符號，類似于自然語言中的標(biāo)點(diǎn)符號，每個符號在程序設(shè)計(jì)語言中均有特殊用途?？梢愿鶕?jù)它們的用途，再細(xì)分為算符(如+、、*、/等)、分隔符。顯然，一個單詞究竟是標(biāo)識符、關(guān)鍵字，還是特殊符號，需要根據(jù)一定的構(gòu)詞規(guī)則來產(chǎn)生和識別。我們將產(chǎn)生和識別單詞的規(guī)則稱為模式(patten)，按照某個模式(規(guī)則)識別出的元素稱為記號(token)，而單詞(lexeme)一詞是指被識別出元素自身的值?！纠?.1】對于語句：position:=initial+rate*60，可以識別出下述序列：標(biāo)識符特殊符號標(biāo)識符特殊符號標(biāo)識符特殊符號數(shù)字字面量其中position、initial、rate均被識別為標(biāo)識符，因?yàn)樗鼈兙贤粭l規(guī)則，即以字母打頭的字母數(shù)字串。記號至少含有兩個信息：一個是記號的類別；另一個是記號的值。顯然，如果把記號看作是一個類型的話，則單詞就是一個類型中的實(shí)例。由于我們總是說識別出一個標(biāo)識符，而不說識別出一個position或rate，因而將詞法分析器識別出的序列稱為記號流。

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

在計(jì)算機(jī)內(nèi)部，可以有不同的方式來表示記號的類別和屬性。一般情況下，記號的類別可以用整型編碼或枚舉類型表示，。根據(jù)記號類別的不同，記號的屬性的值可以有不同的表示方法。relation的屬性值是一個有限可枚舉集合，可以用每個屬性值在集合中的位置來表示它，如1表示<，2表示<=，依此類推。id的屬性值是一個無限可枚舉集合，因此，只能用每個標(biāo)識符的原始輸入形式(字符串)來表示，如pi、draw_line等?！纠?.2】表達(dá)式mycount>25由表2.2的三個記號組成。其中標(biāo)識符的屬性值也可以由mycount在符號表中的入口(下標(biāo))來表示。表2.2記號的表示2.1.3詞法分析器的作用與工作方式詞法分析器是編譯器中唯一與源程序打交道的部分，從某種意義說，也可以被認(rèn)為是整個編譯器的預(yù)處理器。它的主要工作包括：

(1)濾掉源程序中的無用成分，如注釋、空格、回車等。(2)處理與具體平臺有關(guān)的輸入。不同的操作系統(tǒng)或相關(guān)軟件構(gòu)成的平臺，對某些特殊符號(如文件結(jié)束符等)可能有不同表示，因此需要在詞法分析階段分情況處理。

(3)識別記號，并交給語法分析器。這是詞法分析器的主要任務(wù)，本章將在各節(jié)中詳細(xì)討論。(4)調(diào)用符號表管理器或出錯處理器，進(jìn)行相關(guān)處理。詞法錯誤是源程序中常見的錯誤。值得注意的是，詞法錯誤往往不是由詞法分析器檢查出來的，而是由語法分析器發(fā)現(xiàn)的。這是因?yàn)?，源程序中除了非法字符之外的大部分字符或字符串，都可以被詞法分析器的某個模式所匹配，從而被識別成一個記號。而這些記號的正確與否，在沒有上下文對照的情況下，是很難判斷的。

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

(1)詞法分析器作為語法分析器的子程序。其工作方式如圖2.1所示。

(2)詞法分析器進(jìn)行單獨(dú)的一遍掃描。其工作方式如圖2.2所示。圖2.1作為子程序的詞法分析器

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

輸入緩沖區(qū)一般被設(shè)計(jì)為一塊與磁盤扇區(qū)大小成倍數(shù)關(guān)系的內(nèi)存。若一個扇區(qū)為1024字節(jié)，則輸入緩沖區(qū)可以取1024、4096或8192字節(jié)等。這樣可以保證對緩沖區(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)容讀進(jìn)緩沖區(qū)，最后加上特殊標(biāo)記。具體算法如下：圖2.4單緩沖區(qū)procedureget_next_buffer(buffer，start，length)is--start和length是需仍保留在緩沖區(qū)中字符串的起始位置和長度beginiflength>=buffer_size --buffer_size是緩沖區(qū)實(shí)際容量

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è)計(jì)語言通常采用開括號與閉括號的方式標(biāo)識注釋，如表2.1中的comment，如果程序員不小心忘記書寫閉括號，而詞法分析器的設(shè)計(jì)又將comment作為一個完整的記號識別，就會出現(xiàn)被掃描字符個數(shù)超過緩沖區(qū)長度的情況。2.2模式的形式化描述2.2.1字符串與語言從詞法分析的角度看，程序設(shè)計(jì)語言是由記號組成的集合，每個記號又是由若干字母按照一定規(guī)則組成的字符串。在下述的討論中，我們首先定義一個泛泛的“語言”，然后在此基礎(chǔ)上規(guī)定一個正規(guī)集，而程序設(shè)計(jì)語言就是一個正規(guī)集。

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

(2)字符串的長度是有限的，即字符串中字符個數(shù)是有限多個。這是由于計(jì)算機(jī)所能表示的字符個數(shù)和字符串的長度都是有限的。

由于字符串的有序性，使得以字符串作為元素的集合具有某些特性。字符串和集合的基本概念和特性，以表格的形式分別列在表2.3和表2.4中。其中，字符串的連接運(yùn)算是一種新形式的運(yùn)算，它表示兩個字符串首尾相接，形成一個新的集合。表2.3字符串的基本概念表2.4字符串集合上的基本運(yùn)算2.2.2正規(guī)式與正規(guī)集定義2.2令Σ是一個有限字母表，則Σ上的正規(guī)式及其表示的集合遞歸定義如下:(1)ε是正規(guī)式，它表示集合L(ε)=ε；

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

(3)若正規(guī)式r和s分別表示集合L(r)和L(s)，則①r|s是正規(guī)式，表示集合L(r)∪L(s)；②rs是正規(guī)式，表示集合L(r)L(s)；③r*是正規(guī)式，表示集合(L(r))*；④(r)是正規(guī)式，表示的集合仍然是L(r)?？捎谜?guī)式描述的語言稱為正規(guī)語言或正規(guī)集。

定義2.2中(1)和(2)規(guī)定了正規(guī)式的基本操作數(shù)或基本正規(guī)式。定義2.2的(3)給出了正規(guī)式上的三種運(yùn)算:或運(yùn)算①、連接運(yùn)算②和閉包運(yùn)算③。對于由多個操作數(shù)和多個操作符組成的正規(guī)式，可以利用④所給的括號規(guī)定運(yùn)算的先后次序。如果對或、連接和閉包運(yùn)算進(jìn)行如下約定:(1)三種運(yùn)算均具有左結(jié)合性質(zhì)；

(2)運(yùn)算的優(yōu)先級從高到低順序排列為:閉包運(yùn)算、連接運(yùn)算、或運(yùn)算。則正規(guī)式中不必要的括號可以被省略。【例2.3

】

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

正規(guī)集是一個集合，而正規(guī)式是表示正規(guī)集的一種方法。正如不同算術(shù)表達(dá)式可以表示同一個數(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ī)式之間的一些恒等運(yùn)算，被稱為正規(guī)式的代數(shù)性質(zhì)。表2.6給出了正規(guī)式的若干代數(shù)性質(zhì)。利用這些性質(zhì)，可以對復(fù)雜的正規(guī)式進(jìn)行化簡，使得可以用最簡單形式的正規(guī)式表示一個集合。而簡單的正規(guī)式意味著其所對應(yīng)的識別器的構(gòu)造也是簡單的。表2.6正規(guī)式的代數(shù)性質(zhì)2.2.3記號的說明表2.1中用自然語言對模式進(jìn)行了非形式化的描述，例如標(biāo)識符模式的非形式化描述是“以字母打頭的字母數(shù)字串”。由于正規(guī)式是嚴(yán)格的數(shù)學(xué)表達(dá)式，采用正規(guī)式來描述模式，解決了精確描述模式的問題。另外，從詞法分析器的角度上看程序設(shè)計(jì)語言，用正規(guī)式說明的記號是一個正規(guī)集。用正規(guī)式說明記號的公式為：記號=正規(guī)式，可以讀作為“(左邊)記號定義為(右邊)正規(guī)式”，或者“記號是正規(guī)式”。【例2.5】表2.1中的記號relation、id和num分別是Pascal的關(guān)系運(yùn)算符、標(biā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ī)式給出了標(biāo)識符的精確定義，用自然語言可以描述為“字母是英文26個字母大小寫中任何一個，數(shù)字是十進(jìn)制阿拉伯?dāng)?shù)字中的任何一個，標(biāo)識符是以字母打頭的、其后可跟隨0個或若干個字母或數(shù)字的字符串”。1．簡化正規(guī)式描述為了簡化正規(guī)式的描述，通常可以采用如下的幾種正規(guī)式的縮寫形式。

(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)系的縮寫形式，它把所有存在或關(guān)系的字符集中在[]里面。其中的字符可以有如下兩種書寫方式:①枚舉方式:如[abc]，它等價于a|b|c②分段方式:如[0-9a-z]，它等價于 [0123456789abcdefghijklmnopqrstuvwxyz](4)非字符組。若[r]是一個字符組形式的正規(guī)式，則[^r]是表示∑L(r)的正規(guī)式。

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

2．引入輔助定義式引入輔助定義式的主要目的是為較復(fù)雜、但需要重復(fù)書寫的正規(guī)式命名，并在定義式之后的引用中，用名字代替相應(yīng)的正規(guī)式。所以，輔助定義式實(shí)質(zhì)上仍然是正規(guī)式，唯一的區(qū)別是正規(guī)式與外部模式匹配，而輔助定義式不與任何模式匹配?！纠?.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記號的識別——有限自動機(jī)2.3.1不確定的有限自動機(jī)(NondeterministicFiniteAutomata，NFA)

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

其中：

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

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

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

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

有限自動機(jī)是一個抽象的概念，可以用兩種直觀的方式——狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換矩陣來表示，這兩種方式分別簡稱為轉(zhuǎn)換圖和轉(zhuǎn)換矩陣。轉(zhuǎn)換圖是一個有向圖，NFA中的每個狀態(tài)對應(yīng)轉(zhuǎn)換圖中的一個節(jié)點(diǎn)；NFA中的每個move函數(shù)對應(yīng)轉(zhuǎn)換圖中的一條有向邊，該有向邊從si節(jié)點(diǎn)出發(fā)，進(jìn)入sj節(jié)點(diǎn)，字符ch(或ε)是邊上的標(biāo)記。顯然，NFA的初態(tài)是轉(zhuǎn)換圖中沒有前驅(qū)的節(jié)點(diǎn)，而NFA的終態(tài)在轉(zhuǎn)換圖中用有別于其他節(jié)點(diǎn)的方法表示?！纠?.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)換圖識別的每一個記號實(shí)質(zhì)上是從初態(tài)開始到某個終態(tài)的路徑上的標(biā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)下，對同一個字符ch，可能有多于一個的下一狀態(tài)轉(zhuǎn)移。不確定性反映在NFA的定義中，就是move函數(shù)是一對多的；反映在轉(zhuǎn)換圖中，就是從一個節(jié)點(diǎn)可通過多于一條標(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é)點(diǎn)試探可能的下一條路徑，直到遇到第一個終態(tài)，或者一直返回到初態(tài)也沒有遇到終態(tài)。對于輸入序列，若試探了所有的路徑也找不到下一狀態(tài)轉(zhuǎn)移或不能到達(dá)一個終態(tài)，則NFA不接受該序列，說明它不是語言中的合法記號。若到達(dá)一個終態(tài)，則NFA接受該序列，說明它是語言中的一個合法記號?！纠?.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進(jìn)行識別，當(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)識別過程中需要進(jìn)行大量的回溯，時間復(fù)雜度與輸入序列成指數(shù)級增長，且算法復(fù)雜。造成這種情況的原因是NFA的不確定性，即在當(dāng)前的狀態(tài)下，遇到的下一個字符可能有多于一條的路徑可走，而在當(dāng)前狀態(tài)下，這些路徑中哪條路徑可以到達(dá)終態(tài)或者全部路徑均不能到達(dá)終態(tài)都是不可知的。2.3.2確定的有限自動機(jī)(DeterministicFiniteAutomata,DFA)

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

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

(2)對每一個狀態(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的特點(diǎn)就是它的確定性，即在當(dāng)前狀態(tài)下，對同一個字符ch，最多有一個下一狀態(tài)轉(zhuǎn)移。確定性反映在DFA的定義中，就是move函數(shù)是一對一的；反映在轉(zhuǎn)換圖中，就是從一個節(jié)點(diǎn)出發(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算法的最大特點(diǎn)是方法與模式無關(guān)，它僅根據(jù)DFA的當(dāng)前狀態(tài)和狀態(tài)轉(zhuǎn)移進(jì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有限自動機(jī)的等價

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

定義2.6

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

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

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

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

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

(5)從優(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ī)則進(jìn)行構(gòu)造。每次構(gòu)造的新狀態(tài)都需重新命名，以使得所有狀態(tài)的名字均不同。

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

(2)對∑上的每一個字符a，構(gòu)造NFA如圖2.10(b)所示。其中，s0為初態(tài)，f為終態(tài)，該NFA接受；圖2.10Thompson算法中NFA的構(gòu)造圖2.11構(gòu)造正規(guī)式(a|b)*abb的NFA(a)分解正規(guī)式；(b)構(gòu)造NFA2.4.2從NFA到DFA1．NFA識別記號的“并行”方法用NFA識別記號的過程，是在NFA上順序地、一條路徑一條路徑試探的過程。由于需要進(jìn)行回溯，所以算法構(gòu)造復(fù)雜且工作效率低下。事實(shí)上，用NFA識別記號，并不采用這種“串行”的方法，而是采用一種“并行”的方法，從而可以消除識別時的不確定性，以避免回溯?！纠?.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á)地點(diǎn)的全體，再從第一站出發(fā)，第二站可以到達(dá)乘車所能到達(dá)地點(diǎn)的全體，依此類推，直到某一站中包含了乙地。按照這樣的方法，從甲地到乙地的過程與路徑如下所示：甲

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)來計(jì)算下一狀態(tài)集。S和T分別表示狀態(tài)的集合，a是一個非ε字符。與算法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針對的是狀態(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進(jìn)行識別。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)集，且滿足：

(1)?T中所有狀態(tài)屬于ε_閉包(T)；

(2)任何smove(ε_閉包(T)，ε)屬于ε_閉包(T)；

(3)再無其他狀態(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ù)ε_閉包的定義，不難得到計(jì)算ε_閉包的算法。由于ε_閉包是遞歸定義的，而反映遞歸的最佳數(shù)據(jù)結(jié)構(gòu)是棧，所以算法中用一個棧來存放所有可能需要計(jì)算ε狀態(tài)轉(zhuǎn)移的狀態(tài)。算法2.4求ε_閉包輸入狀態(tài)集T輸出狀態(tài)集T的ε_閉包方法用下面的函數(shù)計(jì)算ε_閉包

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①計(jì)算初態(tài)集：

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

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

ε_閉包(smove(B,b)={5,9,6,7,1,2,4}，令它為C。④計(jì)算從狀態(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上識別輸入序列的過程也是確定的，無需回溯，但是，它付出的代價是每走一步就要計(jì)算一次下一狀態(tài)轉(zhuǎn)移的集合。該計(jì)算分兩步走：首先計(jì)算當(dāng)前狀態(tài)集的smove函數(shù)，得到一個集合，然后計(jì)算此集合的ε_閉包。ε_閉包的計(jì)算是遞歸的，需耗費(fèi)大量時間，使得用NFA識別輸入序列的效率很低?！纠?.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。

算法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上，計(jì)算步驟如下所示。其中標(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的子集，它們接受不同的記號；圖2.15最小化DFA中選代表與修改狀態(tài)轉(zhuǎn)移②應(yīng)用下述過程構(gòu)造新的劃分Πnew：forΠ的每一個組Gloop

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

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

③若Πnew=Π，令Πfinal=Π，并轉(zhuǎn)向步驟④；否則，令Π=Πnew并重復(fù)步驟②；④在Π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進(jìn)行狀態(tài)化簡:(1)初始化劃分Π={{A，B，C，D}，{E}}。

(2)考察當(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}}(3)Π≠Πnew，令Π=Πnew，重復(fù)②。

(4)考察當(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}}(5)Π≠Πnew，令Π=Πnew，重復(fù)(2)。

(6)考察當(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}}(7)Π=Πnew，令Πfinal=Π，轉(zhuǎn)向(8)。

(8)在Π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的“短路”計(jì)算構(gòu)造DFA的“子集法”在時間和空間上都比較復(fù)雜。首先，從正規(guī)式構(gòu)造NFA的Thompson算法中引入大量的ε狀態(tài)轉(zhuǎn)移和轉(zhuǎn)移所到達(dá)的狀態(tài)，占用大量空間。其次，考察該算法中確定化的關(guān)鍵步驟ε_閉包(smove(S,a))，若smove(S,a)有m個狀態(tài)，則ε_閉包(smove(S,a))的最壞時間復(fù)雜度為O(m2)，而具有n個狀態(tài)的NFA，其等價DFA的狀態(tài)數(shù)最壞情況是2n個，每個新狀態(tài)又都是通過計(jì)算ε_閉包(smove(S,a))產(chǎn)生的。也就是說，最壞情況下可能進(jìn)行O(2n)次求ε_閉包(S)的計(jì)算，從而使得算法效率很低，并且需要大量的存儲空間存放中間結(jié)果。短路計(jì)算的基本思想是避開由于ε狀態(tài)轉(zhuǎn)移而產(chǎn)生的大量狀態(tài)和大量的ε_閉包計(jì)算，使得構(gòu)造DFA的時空復(fù)雜度降低，具體方法如下：

(1)構(gòu)造正規(guī)式的語法樹。

(2)通過遍歷語法樹計(jì)算構(gòu)造DFA所需的信息。

(3)根據(jù)所得到的信息構(gòu)造DFA。

1.正規(guī)式的語法樹

1)拓廣正規(guī)式與NFA的重要狀態(tài)我們稱正規(guī)式r與特殊結(jié)束標(biāo)記#連接所構(gòu)成的正規(guī)式r#為r的拓廣正規(guī)式。如果NFA上的狀態(tài)s具有非ε的向外狀態(tài)轉(zhuǎn)移(non-εout-transition)，就稱s是NFA的重要狀態(tài)。其他僅含ε向外狀態(tài)轉(zhuǎn)移的狀態(tài)被稱為NFA的非重要狀態(tài)。

【例2.18】

仍然考慮正規(guī)式r=(a|b)*abb，它的拓廣正規(guī)式為r#。利用Thompson算法為r#構(gòu)造的NFA如圖2.16所示。其中所有標(biāo)記為數(shù)字的狀態(tài)是NFA的重要狀態(tài)，因?yàn)閺拿總€狀態(tài)出發(fā)，至少有一個非ε的向外狀態(tài)轉(zhuǎn)移；而標(biāo)記為英文字母的狀態(tài)是NFA的非重要狀態(tài)，因?yàn)樗鼈儍H有ε的向外狀態(tài)轉(zhuǎn)移。狀態(tài)6在為r構(gòu)造的NFA中是一個終態(tài)，而在為r#構(gòu)造的NFA中是一個重要狀態(tài)，因?yàn)樗?的向外狀態(tài)轉(zhuǎn)移。圖2.16正規(guī)式(a|b)*abb#的NFA

2)正規(guī)式的語法樹正規(guī)式的語法樹與算術(shù)表達(dá)式的語法樹是相似的，區(qū)別僅在于運(yùn)算對象和運(yùn)算符的不同。構(gòu)成正規(guī)式的三個基本運(yùn)算的語法樹如圖2.17所示。三個運(yùn)算對應(yīng)的節(jié)點(diǎn)分別被稱為連接節(jié)點(diǎn)（cat-node）、或節(jié)點(diǎn)（or-node）和星節(jié)點(diǎn)（star-node）。注意：連接運(yùn)算的運(yùn)算符“.”在正規(guī)式中被省略。

算術(shù)表達(dá)式的語法樹見定義3.6?，F(xiàn)階段可以將正規(guī)式的語法樹通俗地理解為運(yùn)算符作為父節(jié)點(diǎn)、運(yùn)算對象作為子節(jié)點(diǎn)的樹。圖2.17正規(guī)式基本運(yùn)算的語法樹

【例2.19】

為拓廣正規(guī)式r#=(a|b)*abb#構(gòu)造的語法樹如圖2.18(a)所示。圖2.18正規(guī)式(a|b)*abb#的語法樹(a)語法樹；(b)葉子上的標(biāo)記

3)語法樹葉子上的標(biāo)記和NFA的重要狀態(tài)在圖2.18(a)所示的語法樹中，a出現(xiàn)了兩次，b出現(xiàn)了三次。出現(xiàn)在不同位置的字符表示了它在輸入串中出現(xiàn)的不同位置，例如語法樹中左下角的b可以出現(xiàn)在串頭，而右上角的b只能出現(xiàn)在串尾。為了區(qū)分字符在語法樹中的不同出現(xiàn)位置，需要對每個葉子節(jié)點(diǎn)編上不同的編號，且稱此編號為葉子的標(biāo)記。例如圖2.18(b)就是對應(yīng)語法樹的一個可能的標(biāo)記。標(biāo)記的實(shí)際意義是表示字符在串中的位置，我們可以將語法樹中葉子的標(biāo)記i和葉子a的關(guān)系理解為“在當(dāng)前位置i上遇到了輸入字符a”。與DFA中“在當(dāng)前狀態(tài)i下遇到字符a轉(zhuǎn)向下一狀態(tài)j”比較，得出從語法樹構(gòu)造DFA的關(guān)鍵就是如何根據(jù)語法樹和葉子的標(biāo)記找到在當(dāng)前位置i上遇到a時所能到達(dá)的下一位置j的全體。對照圖2.16和圖2.18(b)不難看出，NFA上重要狀態(tài)和語法樹上葉子的標(biāo)記是一一對應(yīng)的，而且從重要狀態(tài)出發(fā)的邊上的字符正好就是葉子標(biāo)記所標(biāo)記的字符。這不是一個偶然的巧合。用Thompson算法構(gòu)造的NFA中，每個狀態(tài)最多有一個非ε的向外狀態(tài)轉(zhuǎn)移，即一個重要狀態(tài)i最多對應(yīng)一個字符a（不對應(yīng)字符的顯然是非重要狀態(tài)），它表示在i狀態(tài)下可以經(jīng)a轉(zhuǎn)向下一狀態(tài)，恰好與語法樹中“在當(dāng)前位置i上遇到了輸入字符a”一致。由于語法樹中的葉子僅對應(yīng)NFA中的重要狀態(tài)，因而短路掉了僅有ε的向外狀態(tài)轉(zhuǎn)移的非重要狀態(tài)。

2.從正規(guī)式構(gòu)造DFA（Short-circuitConstruction）

1)語法樹上的四個函數(shù)從語法樹構(gòu)造DFA的過程是：首先從語法樹中獲取構(gòu)造DFA所必需的信息，然后根據(jù)這些信息構(gòu)造DFA。為此需要引入下述四個函數(shù)，其中函數(shù)名的后綴pos是英文position(位置)的縮寫，參數(shù)n是正規(guī)式對應(yīng)語法樹的根節(jié)點(diǎn)，參數(shù)i是字符在語法樹中的標(biāo)記。

(1)計(jì)算串的首字符集的函數(shù)firstpos：

firstpos(n)={j|j是n對應(yīng)正規(guī)式所產(chǎn)生的字符串的首字符在語法樹中的標(biāo)記}

(2)計(jì)算串的尾字符集的函數(shù)lastpos：

lastpos(n)={j|j是n對應(yīng)正規(guī)式所產(chǎn)生的字符串的尾字符在語法樹中的標(biāo)記}

(3)計(jì)算后續(xù)字符集的函數(shù)followpos：

followpos(i)={j|存在輸入串…cd…，位置i對應(yīng)c，j對應(yīng)d}

(4)判定是否可產(chǎn)生空串的函數(shù)nullable：

nullable(n)=if以n為根的子樹子表達(dá)式可以產(chǎn)生空串thentrueelsefalse

2)函數(shù)的計(jì)算規(guī)則函數(shù)firstpos和nullable在語法樹上的計(jì)算規(guī)則歸納在表2.8中。表2.8函數(shù)firstpos和nullable的計(jì)算規(guī)則函數(shù)lastpos(n)的計(jì)算規(guī)則與firstpos(n)的計(jì)算規(guī)則幾乎相同，唯一區(qū)別是當(dāng)n是一個cat-node時，參數(shù)中的c1和c2需互換。再來考慮followpos(i)的計(jì)算規(guī)則，注意參數(shù)是葉子節(jié)點(diǎn)的標(biāo)記i而不是根節(jié)點(diǎn)n。根據(jù)函數(shù)followpos(i)可知，僅當(dāng)節(jié)點(diǎn)n的子節(jié)點(diǎn)之間有前后關(guān)系時才需要計(jì)算followpos(i)，而或運(yùn)算節(jié)點(diǎn)的子節(jié)點(diǎn)之間沒有前后關(guān)系，故無需計(jì)算or-node的followpos函數(shù)。

cat-node和star-node的followpos(i)的計(jì)算規(guī)則如下：

(1)若n是一個cat-node，它的左右孩子分別是c1和c2且i是lastpos(c1)中的一個元素，則所有在firstpos(c2)中的元素應(yīng)在followpos(i)中。

(2)若n是一個star-node且i是lastpos(n)中的一個元素，則所有在firstpos(n)中的元素應(yīng)在followpos(i)中。

3)從正規(guī)式構(gòu)造DFA首先對每個正規(guī)式進(jìn)行拓廣，且為每個拓廣正規(guī)式構(gòu)造一棵語法樹，并用or-node把所有的子樹合并成一棵樹。然后對語法樹進(jìn)行兩次遍歷。先后序遍歷語法樹，自下而上計(jì)算nullable、firstpos和lastpos；再先序遍歷語法樹，自上而下計(jì)算followpos。由于遍歷樹的時間復(fù)雜度與樹上節(jié)點(diǎn)的個數(shù)成線性關(guān)系，所以獲取信息的時間復(fù)雜度是O(cn)，其中c是常數(shù)，n是正規(guī)式中字符的個數(shù)，顯然算法的效率是很高的。兩次遍歷的程序如下：(a)post-order(n)isbeginifn.left≠nullthenpost-order(n.left);endif;ifn.right≠nullthenpost-order(n.right);endif;nullable(n);firstpos(n);lastpos(n)--先遍歷孩子后計(jì)算自己

endpost-order;(b)pre-order(n)isbeginfollowpos(n); --先計(jì)算自己后遍歷孩子

ifn.left≠nullthenpre-order(n.left);endif;ifn.left≠nullthenpre-order(n.left);endif;endpre-order;算法2.7構(gòu)造DFA輸入以n為根語法樹上的firstpos(n)和所有的followpos(p)。輸出DFA=(Dstates,Dtran,s0=firstpos(n),F={si|si中存在接受位置j})。方法用下述過程構(gòu)造DFA。beginfirstpos(root)作為唯一未標(biāo)記狀態(tài)加入到Dstates中；

--初態(tài)

whileDstate中還有未標(biāo)記的狀態(tài)T ?--考察所有未標(biāo)記狀態(tài)

loop標(biāo)記T；

for每一個輸入字符a --對T狀態(tài)下所有aloop對T中對應(yīng)字符a的位置p --p可能不唯一U:={j|j∈followpos(p)}; --計(jì)算T狀態(tài)下經(jīng)a的狀態(tài)轉(zhuǎn)移ifU非空thenDtran(T,a):=U; --記錄狀態(tài)轉(zhuǎn)移endif;ifU不在Dstates中then加入U到Dstates中; --記錄新狀態(tài)endif; endloop;endloop;end;與“子集法”的DFA構(gòu)造算法比較，不難看出這兩種方法的基本框架相同，區(qū)別僅在于構(gòu)造DFA所需信息的獲取方法。

【例2.20】

用“短路”計(jì)算的方法構(gòu)造拓廣正規(guī)式r#?=?(a|b)*abb#的DFA。第一步：構(gòu)造r的語法樹并為葉子節(jié)點(diǎn)做標(biāo)記，得到有標(biāo)記的語法樹，如圖2.18(b)所示。第二步：遍歷語法樹并根據(jù)函數(shù)的計(jì)算規(guī)則計(jì)算四個函數(shù)。得到節(jié)點(diǎn)上附加了firstpos和lastpos集合的語法樹如圖2.19所示。其中，節(jié)點(diǎn)左邊是firstpos，右邊是lastpos。語法樹中僅有star-node上的nullable為真，其他均為假。根的firstpos與各葉子節(jié)點(diǎn)的followpos如下：firstpos(root)={1,2,3}followpos(1)={1,2,3}followpos(2)={1,2,3}followpos(3)={4}followpos(4)={5}followpos(5)={6}圖2.19(a|b)*abb#的語法樹與firstpos和lastpos第三步：根據(jù)firstpos和followpos信息，用算法2.7構(gòu)造DFA。具體步驟如下：

(1)?DFA的初態(tài)s0=firstpos(root)={1,2,3}，記為A，加入到Dstates。

(2)取出A并標(biāo)記，計(jì)算A狀態(tài)下經(jīng)a和b的下一狀態(tài)轉(zhuǎn)移(注意，1和3對應(yīng)a，2對應(yīng)b)：followpos(1)∪followpos(3)={1,2,3,4}新狀態(tài)，令其為Bfollowpos(2)={1,2,3} 原有狀態(tài)AB是新狀態(tài)，加入B到Dstates。記錄狀態(tài)轉(zhuǎn)移：Dtran(A,a)=B Dtran(A,b)=A

(3)取出B并標(biāo)記，計(jì)算B狀態(tài)下經(jīng)a和b的下一狀態(tài)轉(zhuǎn)移：

followpos(1)∪followpos(3)={1,2,3,4}原有狀態(tài)B

followpos(2)∪followpos(4)={1,2,3,5}新狀態(tài)，令其為C

C是新狀態(tài)，加入C到Dstates。記錄狀態(tài)轉(zhuǎn)移：

Dtran(B,a)=B Dtran(B,b)=C

(4)取出C并標(biāo)記，計(jì)算C狀態(tài)下經(jīng)a和b的下一狀態(tài)轉(zhuǎn)移：

followpos(1)∪followpos(3)={1,2,3,4}原有狀態(tài)B

followpos(2)∪followpos(5)={1,2,3,6}新狀態(tài)，令其為D

D是新狀態(tài)，加入D到Dstates。記錄狀態(tài)轉(zhuǎn)移：

Dtran(C,a)=B Dtran(C,b)=D

(5)取出D并標(biāo)記，計(jì)算D狀態(tài)下經(jīng)a和b的下一狀態(tài)轉(zhuǎn)移：

followpos(1)∪followpos(3)={1,2,3,4} 原有狀態(tài)B

followpos(2)={1,2,3} 原有狀態(tài)A沒有新狀態(tài)可以加入到Dstates中。記錄狀態(tài)轉(zhuǎn)移：

Dtran(C,a)=B Dtran(C,b)=D

(6)再沒有未標(biāo)記的狀態(tài)，算法結(jié)束。因?yàn)镈狀態(tài)中包含6，它對應(yīng)結(jié)束標(biāo)記#，因此D是DFA的終態(tài)，初態(tài)是A。將所有的狀態(tài)轉(zhuǎn)移