编译原理基础课件

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

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

例2.1

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

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

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

例2.2

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

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

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

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

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

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

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

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

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

thenreturnerror；

elseforiinlow..low+length1 --low是緩衝區下界，假設從0開始

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

endloop； num_to_read:=buffer_sizelength；

ifnumber_to_read>block_size--block_size應是磁片扇區的整數倍

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

endif；endget_next_buffer；

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

定義2.1語言L是有限字母表∑上有限長度字串的集合。定義2.1明確指出，語言是一個集合，集合中的元素是字串，並且強調了兩個有限:①字母表是有限的，即字母表中元素是有限多個；②字串的長度是有限的，即字串中字元個數是有限多個。這是由於電腦所能表示的字元個數和字串的長度都是有限的。

由於字串的有序性，使得以字串作為元素的集合具有某些特性。字串和集合的基本概念和特性，以表格的形式分別列在表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正規式與正規集定義2.2令Σ是一個有限字母表，則Σ上的正規式及其表示的集合遞歸定義如下:①ε是正規式，它表示集合L(ε)=ε；②若a是Σ上的字元，則a是正規式，它表示集合L(a)=；③若正規式r和s分別表示集合L(r)和L(s)，則

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

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

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

(d)(r)是正規式，表示的集合仍然是L(r)。可用正規式描述的語言稱為正規語言或正規集。

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

例2.3

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

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

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

例2.5

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

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)*)

上述正規式給出了識別字的精確定義，用自然語言可以描述為“字母是英文26個字母大小寫中任何一個，數字是十進位阿拉伯數字中的任何一個，識別字是以字母打頭的、其後可跟隨0個或若干個字母或數字的字串”。1．簡化正規式描述為了簡化正規式的描述，通常可以採用如下的幾種正規式的縮寫形式。

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

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

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

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

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

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

例2.6

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

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)

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

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

例2.7

識別由正規式(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}

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

例2.8

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

用NFA識別輸入序列的方法是：從NFA的初態開始，對於輸入序列中的每一個字元，尋找它的下一狀態轉移，直到沒有下一狀態轉移為止。若此時所處狀態是終態，則從初態到終態路徑上的所有標記，構成了一個識別出的記號。否則沿原路返回，並在返回的每一個節點試探可能的下一條路徑，直到遇到第一個終態，或者一直返回到初態也沒有遇到終態。對於輸入序列，若試探了所有的路徑也找不到下一狀態轉移或不能到達一個終態，則NFA不接受該序列，說明它不是語言中的合法記號。若到達一個終態，則NFA接受該序列，說明它是語言中的一個合法記號。

例2.9

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

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

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

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

定義2.5DFA是NFA的一個特例，其中：①沒有狀態具有ε狀態轉移(ε-transition)，即狀態轉換圖中沒有標記ε的邊；②對每一個狀態s和每一個字元a，最多有一個下一狀態。

例2.10

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

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

演算法2.1模擬DFA

輸入

DFAD和輸入字串x。x由檔結束符eof終止，D的初態為s0，終態集為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統稱為有限自動機(FA)。所謂有限，是指自動機的狀態數是有限的，因此，有些教材中也稱為有限狀態自動機。與正規式的等價相似，FA之間也存在等價問題。

定義2.6

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

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

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

演算法2.2Thompson演算法

輸入字母表∑上的正規式r。

輸出接受L(r)的NFAN。

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

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

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

(c)對正規式p*，構造NFA如圖2.10(e)所示。其中，s0為初態，f為終態，該NFA接受L(p*)。④對於正規式(p)，使用p本身的NFA，不再構造新的NFA 圖2.10Thompson演算法中NFA的構造

例2.11

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

例2.12

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

c2 無路可走，退回甲

c1c3 無路可走，退回甲

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

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

c{1,2}c{3,乙}到達乙地，成功

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

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

c{1,2}b{3}。 由於在3處沒有通過乘車可以到達乙地的路徑，可以斷定上述要求無法從甲地到達乙地。

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

演算法2.3模擬NFA

輸入

NFAN和輸入字串x。x由檔結束符eof終止，N的初態為s0，終態集為F

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

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

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

表2.7演算法2.1與演算法2.3的區別DFA(演算法2.1)NFA(演算法2.3)區別初態初態集從初態s0出發改變為從初態集出發下一狀態下一狀態集當前狀態對字元a的下一狀態改變為下一狀態集sisinFS∩F≠Φ判斷輸入序列被接受的條件由最後一個狀態是否是終態集中的一個狀態，改變為最後一個狀態集與終態集的交集是否為空集定義2.7

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

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

functionε_閉包(T)isbeginforT中每個狀態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①計算初態集：

ε_閉包({0})={0,1,2,4,7}，令初態集為A。②計算從狀態集A出發，經a所到達的下一狀態集：

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

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

ε_閉包(smove(C,b)={5,10,6,7,1,2,4}，令它為D。⑤輸入序列已經結束，且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．“子集法”構造DFA

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

例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識別的結果完全相同。圖2.13確定化後的甲地到乙地的所有路徑

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

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

輸入一個NFAN

輸出一個接受同一正規集的DFAD。其中，含有NFA初態的DFA狀態為DFA的初態，所有含有NFA終態的DFA狀態構成DFA的終態集。方法用下述過程構造DFA：

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

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

thenU作為尚未標記的狀態加入Dstates;endif;Dtran[T，a]:=U;endloop;endloop;

例2.15

將演算法2.5應用於圖2.11(b)所示的NFA上，計算步驟如下所示。其中標有*的集合是第一次出現，在演算法中需要被標記並處理。所得的DFA如圖2.14所示，其中A是初態，E是終態集中僅有的終態。圖2.14識別(a|b)*abb的DFA(a)轉換圖表示的DFA；(b)轉換矩陣表示的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，其結果與在NFA上識別的結果完全相同。步驟如下：識別abb:AaBbDbE 接受識別abab:AaBbDaBbD 不接受2.4.3最小化DFA

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

定義2.8

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

演算法2.6最小化DFA的狀態數輸入一個DFAD={S，∑，move，s0，F}

輸出一個DFAD'={S'，∑，move'，s0'，F'}，它和D接受同樣的正規集，但是狀態數最少方法①構造狀態集的初始劃分Π={S-F，F1，F2，...}，其中F1，F2，……均是F的子集，它們接受不同的記號；②應用下述過程構造新的劃分Πnew：forΠ的每一個組Gloop

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

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

③若Πnew=Π，令Πfinal=Π，並轉向步驟④；否則，令Π=Πnew並重複步驟②；④在Πfinal的每個組Gi中選一個代表si'，使得D中從Gi中所有狀態出發的狀態轉移在D'中均從si出發，D中所有轉向Gi中狀態的狀態轉移在D'中均轉向si'；含有D中s0的狀態組G0的代表s0'稱為D的初態，D中所有含F中狀態的Gj的代表sj'構成D'的終態集F '；⑤若D'中有狀態d，它不是終態且對於所有輸入字元均轉向其自身，則稱d為死狀態；將d從D'中刪除，同時也刪除所有從初態不可到達的狀態，從其他狀態到d的任何狀態轉移被認為無意義。

例2.17

用演算法2.6對圖2.14中的DFA進行狀態化簡:①初始化劃分Π={{A，B，C，D}，{E}}。②考察當前劃分Π。E自身一個組，不能再分，ABCD在一個組，查看它們的狀態轉移：

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，重複②。②考察當前劃分Π。ABC在一個組，查看它們的狀態轉移：

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，重複②。②考察當前劃分Π。AC在一個組，查看它們的狀態轉移：

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

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

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

例2.18

根據上述轉換圖與程式結構的簡單對應關係，可以將圖2.8所示的DFA轉換為下述示意性的詞法分析器。其中的標號s0、s1、s2、s3分別表示語句與狀態的對應，除了s0和s1之外，其餘的標號均無實際意義。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．兩類分析器的比較直接編碼詞法分析器和表驅動詞法分析器的工作原理完全相同，它們的基本依據都是DFA。但是，二者在與模式的關係、分析器的構造以及分析器的分析效率諸方面均有很大差別。從分析器與模式之間的關係講，表驅動型分析器的驅動器僅對分析表的內容進行操作，而與所識別的記號無關，具體識別什麼記號，由分析表中與模式密切相關的數據來控制，是一種典型的數據與操作分離的工作模式，構造不同的詞法分析器實質上成為構造不同的分析表。而直接編碼型的詞法分析器，是通過程式的控制流轉移來完成對輸入字串的回應，可以說程式的每一條語句都與模式密切相關，一旦模式改變，則程式必須改變。

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

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

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

例2.19

例2.6中關於id和num的說明，可以用LEX的形式表示如下，其中的輔助定義和規則以LEX提供的形式書寫，而語義動作也僅是示意性的。需要指出，此處{}是重載的，它既可以用來標記對輔助定義名字的引用，如{char}、{digit}等，也可以用來界定用戶書寫的相關語義動作，如{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})*