研究生院第三章

第三章詞法分析詞法分析的作用記號的描述，正則式記號的識別有限狀態自動機正規式與有限狀態自動機的等價詞法分析程序的自動生成工具詞法分析的作用（1）編譯器的第一階段：讀輸入的字符流，產生用于語法分析的記號序列完成和用戶接口的一些任務：源程序行信息的記錄，為報錯提供支持注解、空白的剝離宏的預處理詞法分析的作用（2）分離詞法分析的理由簡化設計：分離詞法分析和語法分析，可以簡化語法分析的復雜性詞法和語法規則的分離可以方便程序設計語言的設計利于設計高效的詞法分析程序增加編譯器的可移植性：將輸入字符集的特殊性和其它與設備有關的不規則性限制在詞法分析程序中詞法分析的作用（3）基本概念：單詞：源程序中的字符序列模式：單詞的分類規則，程序中的單詞有很多，具有相同詞法屬性的單詞歸為一類記號token：不同的單詞類。記號是源語言語法的終結符通常，記號定義為枚舉型：關鍵字、算符、標識符、常數、字符串、標點符號等對于某些程序設計語言，可能要求某些特定的結構出現在特定的位置，如FORTRAN語言的標號，因此單詞對準對詞法分析的正確性很重要，但現代語言一般采用自由格式，這類問題不重要了詞法分析的作用（4）分隔符：決定了單詞的分隔，一般以空白字符為分隔，但有些語言如FORTRAN語言，空白字符不是分隔符 如DO5I=1.25，只有讀入“.”時才能確認DO5I是一個標識符，而不是DO語句的一部分關鍵字是否為保留字：很多語言規定關鍵字是保留字，即其含義是預定義的，用戶不能改變，詞法分析較易實現；否則，詞法分析程序必須區分是關鍵字還是用戶自定義的標識符 如PL/1語言：

IFTHENTHENTHEN=ELSE；ELSEELSE=THEN；詞法分析的作用（5）記號的屬性：指記號的特性或特征，而屬性的值則反映了特性或特征的值通常一個記號具有一個屬性值如果一個模式能匹配不止一個單詞，詞法分析器必須為記號提供附加的信息，但有些記號不需要附加的屬性值記號影響語法分析的決策，屬性影響記號的翻譯詞法分析的作用（6） 如FORTRAN語句：F=M*C**2

記號及屬性值：用二元組依次表示 <id，指向符號表中F條目的指針>

<assign_op，>

<id，指向符號表中M條目的指針>

<mult_op，>

<id，指向符號表中C條目的指針>

<exp_op>

<num，整數值2>詞法分析的作用（7）詞法錯誤：詞法分析基本無法檢查出來錯誤但有時由于剩余輸入的前綴不能和任何記號的模式匹配而使得詞法分析器無法處理錯誤恢復策略：緊急方式：刪掉剩余輸入最前面的字符，直至發現一個正確的符考慮到大多數詞法錯誤是輸入錯誤，因此下列方法可能將錯誤進行修補，但不是總有效的刪除一個多余的字符插入一個遺漏的字符用一個正確的字符代替一個不正確的字符交換兩個相臨的字符詞法分析的理論基礎正規式表示構成程序設計語言的詞法結構的串格式的標準表示法有限狀態自動機對由正規表達式給出的串格式的識別算法正規式（1）正規式：按照一組定義規則，由較簡單的正規式構成的正規式與3型文法是等價的正規集：正規式表示的語言構成規則：定義字母表∑上的正規式的規則ε是正規式，表示的語言是{ε}如果a是∑上的符號，則a是正規式，表示{a}如果r和s是正規式，分別表示語言L(r)和L(s)，則：r|s是正規式，表示L(r)∪L(s)rs是正規式，表示L(r)L(s)(r)是正規式，表示L(r)(r)*是正規式，表示(L(r))*僅由有限次使用上述規則得到的表達式才是∑上的正規式正規式（2）構成規則的優先性閉包運算(*)優先于連結運算連結運算優先于|這三種運算都是左結合的“()”可以改變運算的次序 有了上述優先性的定義，可以化簡正規式： (a)|((b)*(c))可以化簡為a|b*c正規式（3）例1：令∑={a,b}，則：正規式a|b表示集合{a,b}正規式(a|b)(a|b)表示集合{aa,ab,ba,bb}，這個集合也可以由正規式aa|ab|ba|bb表示正規式a*表示零個或多個a的所有串的集合正規式（a|b)*表示零個或多個a或b的所有串的集合，這個集合也可以由正規式（a*|b*)*表示正規式a|a*b表示串a和零個或多個a后隨一個b的所有串的集合正規式（4）正規式的等價： 如果兩個正規式表示同樣的語言，則這兩個正規式等價正規式的代數性質： 公理 描 述r|s=s|r |是可交換的r|(s|t)=(r|s)|t |是可結合的(rs)t=r(st) 連結是可結合的r(s|t)=rs|rt 連結對|可分配(s|t)r=sr|trεr=r ε是連結的恒等元素rε=rr*=(r|ε)* *和ε間的關系r**=r* *是冪等的正規式（5）正規定義為什么引入正規定義：正規式描述單詞符號簡潔、直觀

a(0|1|a)*正規文法描述單詞易于識別

S→a|aR R→0|1|a|0R|1R|aR所以可以先給出正規式的定義，再根據需要轉化為正規文法,正規定義為此提供了條件正規式（6）正規式的命名：為了表示方便，并進一步定義正規式如果有digit→0|1|2|…|9，則正規式digitdigit*與正規式(0|1|2|…|9)(0|1|2|…|9)*是等價的，都表示的是一個或多個數字的序列digit→0|1|2|…|9是對一個名字的定義這個名字本身是一個元符號，它可以出現在其它名字的定義中，但不能出現在對自身的定義中，也就是不能有遞歸正規式（7）正規定義：如果∑是基本符號的字母表，則正規定義的形式為如下的序列 d1→r1 d2→r2

… dn→rn 各個di的名字不同，且每個ri是∑∪{d1,d2,…,di-1}上的正規式。正規定義與正規文法的產生式是兩個不同概念：正規定義的左端是一個名字，右端是一個正規式正規文法的產生式左端是文法的一個非終結符，而右端是一個符合特定形式的文法符號串正規式（8）例2：Pascal語言的標識符集合是以字母開頭的字母數字串集合

letter→A|B|…|Z|a|b|…|z

digit→0|1|…|9

id→letter(letter|digit)*正規式（9）例3：Pascal語言中的無符號數的定義

digit→0|1|…|9

digits→digit

digit*

optional_fraction→.digits|ε

optional_exponent→(E(+|-|ε)digits)|ε

num→digitsoptional_fractionoptional_exponent

在上例中，可以合法的表示5280、29.235、6.23E4、12.234E-12、1.0

但不能合法表示1.正規式（10）表示的縮寫：某些頻繁出現的結構可以簡便表示一個或多個實例：一元后綴算符+如果r是表示語言L(r)的正規式，則是r+表示語言(L(r))+的正規式(0|1)+是二進制數的正規式+和*有同樣的優先級和結合性r*=r+|ε，r+=rr*零個或一個實例：一元后綴算符？r?是r|ε的縮寫對于正規式r，r?表示語言L(r)|{ε}正規式（11）用+和？重寫例3

digit→0|1|…|9

digits→digit+

optional_fraction→(.digits)?

optional_exponent→(E(+|-)?digits)?

num→digitsoptional_fractionoptional_exponent正規式（12）字符組：[abc]表示正規式a|b|c，[a-z]表示正規式a|b|…|zPascal的標識符可以用如下的正規式表示 [A-Za-z][A-Za-z0-9]+非正規集：正規式的描述能力相當于3型文法，只能表示給定結構的固定數目的重復或沒有指定數目的重復不能描述配對或嵌套的結構，也不能描述重復串 {wcw|w是a和b的串}詞法分析程序的構造（1）文法的分解將源語言的文法G分解為若干個子文法：G0,G1,…,Gn文法G1,…,Gn分別描述語言的標識符、常數、運算符、界符等基本符號（單詞符號），是詞法文法G0借助基本符號來描述語言結構的文法，是語法詞法的符號作為終結符出現在文法G0中詞法分析程序的構造（2）詞法文法的決定由正規式得到3型文法

num→digitremainder1

remainder1→digitremainder1|.remainder2| Eremainder4|ε

remainder2→digitremainder3

remainder3→digitremainder3|Eremainder4|ε

remainder4→+digits|-digits|digitremainder5

digits→digit

remainder5

remainder5→digitremainder5|ε詞法分析程序的構造（3）基本符號的識別狀態轉換圖狀態集合的構成文法中的非終結符對應一個狀態文法的開始符號是初態增加一個終態狀態間的轉換弧的表示：產生式中的終結符產生式A→aB，從狀態A到狀態B畫一條標記a的弧產生式A→a，從狀態A到終態畫一條標記a的弧

詞法分析程序的構造（4）詞法分析程序的構造（5）詞法分析程序的構造狀態轉換圖的實現（可以參考陳火旺、杜淑敏）每個狀態可以通過一小段程序實現如果當前的狀態是終態，返回符號相關信息如果有邊離開該狀態，則讀入一個字符，并根據這個字符選擇后續的狀態，并將控制轉交那個狀態如果出邊沒有匹配的字符，且該狀態不是終態，則調用失敗子程序，把輸入指針撤回到開始指針的地方，啟動對下一個轉換圖的記號的搜索如果不存在下一個轉換圖，則調用錯誤恢復子程序詞法分析程序的構造（6）二義性的處理：如if、while等既可以是關鍵字，也可以是標識符，此時可采用關鍵字優先的處理串可以是單個記號也可以是若干記號的序列時（如<>,可以是<和>兩個記號，也可以是一個記號），則通常解釋為單個記號，稱作最長子串原理輸入緩沖區（1）輸入緩沖：需求：詞法分析程序可能要向前看若干個字符，才能決定單詞符號的確切性質緩沖區的選擇：只用一個單獨的緩沖區：無論緩沖區多大，都不能保證單詞符號不會被緩沖區的邊界截斷配對緩沖區：將一個緩沖區分為相同的兩個部分每引用一次系統的讀入命令，讀入填滿半個緩沖區的字符，若不足，用eof標志表明輸入緩沖區保持兩個指針：開始指針和向前指針開始時，兩個指針都指向下一個單詞符號的第一個字符輸入緩沖區（2）向前指針向前掃描，直至確定單詞符號單詞符號確定后，向前指針位于該單詞符號的右端當前的單詞符號處理完成后，兩個指針同時指向該符號的下一個字符向前指針將跨過邊界時，更新緩沖區的一半單詞符號的長度受到緩沖區的大小有限狀態自動機（1）有限狀態自動機：是更一般的轉換圖，最早可追溯到1943年McCulloch和Pitts的工作其輸入/輸出是離散的系統包含有限個內部狀態系統的當前狀態概括了有關過去輸入的信息（但不是包含所有過去的信息），這些信息對于在后來的輸入上確定系統的行為是必需的分為確定的有限狀態自動機和非確定的有限狀態自動機兩類正規式、正規文法、有限狀態自動機的描述能力是一樣的有限狀態自動機（2）不確定的有限狀態自動機(NFA)：定義： 一個NFAM是一個五元式M=(S,∑,δ,s0,F)，其中S是一個有限的狀態集合∑是一個有限的輸入符號的字母表s0是S的一個元素，為開始狀態，它是唯一的狀態集合F是接受（或終止）狀態的集合，它是S的子集δ是轉換函數：S×{∑∪{ε}}→2S，也是一個集合，2S表示S的冪集合有限狀態自動機（3）例：識別語言(a|b)*abb的NFA如下圖： 其中S={0，1，2，3}，∑={a，b}，s0是0， F={3}，在圖中，接受狀態用雙圈表示，開始狀態一般用一個箭頭指示有限狀態自動機（4）轉換函數的表示：函數集合的表示：δ：S×{∑∪{ε}}→2S是由狀態和輸入符號的二元組映射到狀態的集合，如δ(q,a)={q’，…}如果有δ(q,a)={q’，…}，表示如果當前狀態是q，輸入符號是a，在轉換后的狀態是一個集合{q’，…}在轉換圖中的表示是狀態q到集合{q’,…}中的每個狀態間有一條有向邊，邊上的標記是a 上圖的自動機的轉換函數：

δ(0,a)={0,1}，δ(0,b)={0}

δ(1,b)={2}，δ(2,b)={3}有限狀態自動機（5）轉換表：二維數組每個輸入符號（如果需要，可以包括ε）占一列每個狀態占一行表中狀態q的行和輸入符號a的列交叉點的內容是在狀態q、輸入符號a時，所能達到的狀態的集合有限狀態自動機（6）轉換表的優點是可以快速查找狀態轉換轉換表的缺點是浪費空間，實現時可以采用稀疏矩陣表示NFA接受的語言：NFA接受的串：NFA接受輸入串x的充分必要條件是存在從開始狀態到某個接受狀態的路徑，使沿著該路徑的邊的標記拼成x，NFA接受一個輸入串的路徑不都是唯一的由NFA定義的語言是它接受的輸入串的集合有時，考慮到NFA中是否有ε轉換，從而將NFA細分為兩類：具有ε轉換的NFA，和不具有ε轉換的NFA有限狀態自動機（7）有限狀態自動機（8）確定的有限狀態自動機（DFA）：定義：是NFA的特殊情況，其中：沒有一個狀態有ε轉換對每個狀態q和輸入符號a，最多只有一條標記為a的有向邊是離開 即有δ：S×∑→S確定性：DFA從任何狀態出發，對于任何輸入符號，最多只有一個轉換對于一個DFA接受的輸入串，從開始狀態起，最多只有一條到達終態的路徑可由這個串標記有限狀態自動機（9）DFA的模擬：輸入：輸入串x，由文件結束符eof結尾；一個DFAD，開始狀態s0，接受狀態集合F輸出：如果D接受x，則回答“yes”，否則回答“no”方法：將下述算法施加于串x，其中用函數move(s,c)代替δ(s,c)，函數nextchar返回輸入串x的下一個字符

s:=s0; c:=nextchar; whilec≠eofdo s:=move(s,c) c:=nextchar; end; ifs∈Fthen return“yes” elsereturn“no”有限狀態自動機（10）有限狀態自動機（11）有限狀態自動機的等價性：設M和M’是兩個有限狀態自動機，如果二者接受相同的語言，即L(M)=L(M’)，則稱這兩個有限狀態自動機M和M’是等價的存在有判定兩個有限狀態自動機是否等價的算法有限狀態自動機（12）NFA到DFA的變換：ε閉包（ε-closure）：關于狀態s的ε閉包：定義：從NFA的狀態s出發，只用ε轉換能達到的NFA的狀態集合在求得只用ε轉換能達到的狀態時，ε轉換可連續多次使用，成為只含有ε標記的路徑由于路徑可以沒有邊，所以狀態s也是它的ε閉包的元素NFA在讀入第一個輸入符號前，它可處于集合ε閉包(s0)的任何狀態關于狀態集合T的ε閉包：定義：從NFA的任何一個狀態s∈T出發，只用ε轉換能達到的NFA的狀態集合有限狀態自動機（13）轉換函數的ε閉包：對NFA轉換函數的擴充：δ：2S×∑→2S

δ(T,a)表示從NFA的某個狀態s∈T出發，經輸入符號a轉換能達到的NFA狀態的集合它表明了：當T中的狀態都是從NFA的開始狀態面臨給定輸入串可達的，令a是下一個輸入符號，NFA讀入a后可以移動到集合δ(T,a)中的任何狀態ε閉包(δ(T,a))：是集合δ(T,a)中的任何一個狀態經ε轉換后能達到的NFA狀態集有限狀態自動機（14）關于狀態集合T的ε閉包的計算

把T的所有狀態壓入棧

ε閉包(T)的初值置為T while棧非空dobegin

把棧頂元素t彈出棧

for從t到u且標記為ε的每個狀態udo ifu不在ε閉包(T)中then

把u加入ε閉包(T)

把u壓入棧

endifendfor endwhile有限狀態自動機（15）下圖是接受語言(a|b)*abb，則有：ε閉包(0)是集合A={0,1,2,4,7}ε閉包(δ(A,a))=ε閉包({3,8})={1,2,3,4,6,7,8}有限狀態自動機（16）NFA到DFA轉換的基本思想：DFA轉換表中每個條目只有一個狀態，而NFA轉換表中，每個條目是一個狀態集合，因此NFA到DFA的轉換就是構造一個DFA，使它的每個狀態代表NFA的狀態集合DFA用它的狀態記錄NFA在讀輸入符號后到達的所有狀態在讀了輸入a1a2…an后，DFA到達一個代表NFA的狀態子集T的狀態，這個子集T是從NFA的開始狀態沿著標記為a1a2…an的路徑能到達的所有狀態的集合（特別地，包含ε轉換）由于NFA轉換函數的值域是其狀態集合的冪集合，因此在最壞的情況下，構造出來的DFA的狀態數和NFA的狀態數成指數變化，但實際上很少發生有限狀態自動機（17）子集構造法：從NFA構造DFA 輸入：一個NFAN，開始符號s0，

輸出：一個接受同樣語言的DFAD,狀態集合Dstates ，轉換表Dtran

算法：

ε閉包(s0)是Dstates僅有的狀態，且尚未標記

whileDstates有尚未標記的狀態Tdobegin

標記T for每個輸入符號adobegin U:=ε閉包(δ(T,a)) ifU不在Dstates中then

把U作為尚未標記的狀態加入Dstates中

endif Dtran[T,a]:=U endfor endwhile有限狀態自動機（18）D的轉換表Dtran中的每個狀態都是N的狀態的集合，它是N讀了某個輸入符號序列后所能到達的全部狀態，包括所有ε的轉換D并行地模擬N面對輸入串的所有可能的移動D的開始狀態：ε閉包(s0)對應的D的狀態D的接受狀態的確定：如果D的狀態是至少包含一個接受狀態的N的狀態集，則它是D的一個接受狀態NFA與DFA的等價性：對于任意一個DFA，由于它本身是一個特殊的NFA，所以必然存在一個NFA，它接受的語言是這個DFA接受的語言對于任意一個NFA，按照上述子集構造法構造一個DFA，使得DFA接受的語言是NFA接受的語言（此命題的證明請課下考慮）有限狀態自動機（19）ε閉包(0)是集合A={0,1,2,4,7}ε閉包(δ(A,a))是集合B=ε閉包({3,8})={1,2,3,4,6,7,8}ε閉包(δ(A,b))是集合C=ε閉包({5})={1,2,4,5,6,7}ε閉包(δ(B,a))就是集合Bε閉包(δ(B,b))是集合D=ε閉包({5,9})={1,2,4,5,6,7,9}ε閉包(δ(C,a))就是集合B，ε閉包(δ(C,b))就是集合Cε閉包(δ(D,a))就是集合Bε閉包(δ(D,b))是集合E=ε閉包({5,10})={1,2,4,5,6,7,10}ε閉包(δ(E,a))就是集合B，ε閉包(δ(E,b))就是集合C有限狀態自動機（20）開始狀態是A接受狀態是EDFA的轉換表有限狀態自動機（21）下圖是構造出來的DFA，它的最小化將在后面介紹正規式與有限狀態自動機的等價（1）正規式與FA的等價性：對于任意一個正規式r，存在一個NFAN，使得L(N)=L(r)若語言L被一個DFA接受，則存在一個正規式r，使得L=L(r)從正規式到NFA：構造算法從簡單到復雜逐步根據正規式的語法構造出對應的自動機首先構造識別ε和字母表中任何符號的自動機然后構造分別含一個選擇、并置和閉包算符的正規式對應的NFA在構造過程中，每步最多引入兩個新的狀態，NFA最終的狀態數最多是正規式中符號和算符數的兩倍正規式與有限狀態自動機的等價（2）輸入：字母表∑上的正規式輸出：接受L(r)的NFAN方法：Thompson構造將r分解為子表達式，對r中的每個基本符號（ε和字母表中任何符號）構造NFA：此時r含有0個算符對于ε，如下構造NFA，i是新的開始狀態，f是新的接受狀態，這個NFA識別{ε}對于字母表中的每個符號a，構造NFA，i,f的解釋同上，這個NFA識別{a}正規式與有限狀態自動機的等價（3）如果N(s)和N(t)是正規式s和t的NFA，則二者的運算對應的NFA是：此時已經假設r中包含的算符少于n個時命題（L(N)=L(r)）成立，求證算符個數為n時，命題成立對于正規式s|t，如下構造NFAN(s|t)，i是新的開始狀態，f是新的接受狀態，但N(s)和N(t)的開始和接受狀態不是N(s|t)的開始和接受狀態。這個NFA識別L(s)∪L(t)正規式與有限狀態自動機的等價（4）對于正規式st，如下構造NFAN(st)，N(s)的開始狀態成為N(st)的開始狀態，N(t)的接受狀態成為N(st)的接受狀態，N(s)的接受狀態和N(t)的開始狀態合并，但不是N(st)的開始和接受狀態，合并是指從N(t)的開始狀態的所有轉換成為從N(s)的接受狀態的轉換。這個NFA識別L(s)L(t)

上述構造的一個等價形式是：正規式與有限狀態自動機的等價（5）對于正規式s*，如下構造NFAN(s*)，i和f是新的開始和接受狀態。這個NFA識別(L(s))*對于正規式(s)，使NFAN(s)本身作為它的NFA正規式與有限狀態自動機的等價（6）上述方法構造的NFA具有如下的性質：N(r)的狀態數最多是r中符號和算符個數的兩倍N(r)只有一個開始狀態和一個接受狀態，接受狀態沒有向外的轉換N(r)的每個非接受狀態有一個用字母表中的符號標記的向外的轉換，或者最多有兩個向外的ε轉換正規式與有限狀態自動機的等價（7）例：構造正規式r=(a|b)*abb的N(r)DFA的化簡（1）每一個正規集都可以由一個狀態數最少的DFA識別，且這個DFA是唯一的（狀態名不同的同構情況除外）DFA的化簡：基本假設：DFAM，狀態集合S，輸入符號表∑假定每個狀態對每個輸入符號都有轉換如果不是這樣，引入一個“死狀態”d，d對所有輸入符號都轉換到d，如果狀態s對符號a沒有轉換，則加上從s到d的a轉換串w區別狀態s和t：指如果DFAM從狀態s出發，面臨輸入串w，最后停在某個接受狀態，但是從t出發，面對同樣的輸入，停在一個非接受狀態，或者反過來如幻燈片50中，A和B由輸入bb區別，因為對于輸入bb，A到達非接受狀態C，而B對同樣的輸入到達接受狀態EDFA的化簡（2）化簡的基本思路：將DFA的狀態分成一些不相交的子集每個子集中的狀態是不可區別的，而不同的子集的狀態是可區別的每個子集合并成一個狀態基本的步驟：首先是將所有狀態劃分為接受狀態組和非接受狀態組取某個狀態組，檢查其中的狀態是否面對某些輸入是可區別的，如果是可區別的，則將這個狀態組化分成兩個或多個狀態組重復上述步驟，直至不再有新的狀態組出現由上述步驟構造得到的最終的狀態組，如果兩個狀態仍然留在同一個狀態組中，則它們對任意的輸入都是不可區別的對于最終的狀態組，每個組分別以一個狀態代表，去掉死狀態和從開始狀態不可打的狀態，則上述的DFA是接受同樣語言的狀態數最少的DFADFA的化簡（3）輸入：一個DFAM，它的狀態集合S，輸入符號集合為∑，轉換函數δ：S×∑→S，開始狀態s0，接受狀態集合F輸出：一個DFAM’，它和M接受同樣的語言，且狀態數最少方法：構造狀態集合的初始劃分Π：分成兩組，接受狀態組F和非接受狀態組S-F應用下面的過程對Π構造新的劃分Πnew：

forΠ中的每個組Gdobegin

把G劃分成小組，G的兩個狀態s和t在同一小組中，當且僅當 對任意輸入符號a，s和t的a轉換都在Π的同一組中； 在Πnew中，用G的劃分代替G； endfor如果Πnew=Π

，讓Πfinal:=Π

，在執行步驟4)；否則，令Π:=Πnew，轉步驟2)在Πfinal的每個狀態組中選一個狀態代表它，它對應了這個組中所有狀態的轉換。包含s0的狀態組的代表是M’的開始狀態，M’的接受狀態是那些原先從屬于F集合的代表，Πfinal的每個狀態組或者僅含F中的狀態，或者不含F中的狀態刪除死狀態和不可達的狀態，與之相關的轉換置為無定義DFA的化簡（4）開始：Π中只有兩個組：接受狀態組{E}和非接受狀態組{ABCD}考慮{E}，由于其中只有一個狀態，不可分，所以Π中維持兩個組考慮{ABCD}，對輸入a，都轉換到B；對輸入b，分成了{ABC}和{D}，此時Π中由三個組：{ABC}、{D}和{E}同樣，由于輸入符號b，{ABC}被劃分成了{AC}和{B}，此時Π中由四個組：{AC}、{B}、{D}和{E}{AC}不再可分DFA的化簡（5）選擇A、B、D和E作為各個狀態組的代表化簡后的自動機的開始狀態是A，接受狀態是E，轉換表如下：詞法分析程序的自動生成工具（1）Lex的簡介：工作方式：Lex程序的構成：3個部分，中間以%%分割聲明：變量、常量的聲明，正規定義翻譯規則：形式如下，其中pi是正規式p1 {動作1}p2 {動作2}……輔助過程詞法分析程序的自動生成工具（2）由Lex建立的詞法分析器和語法分析器的聯系：詞法分析器被語法分析器激活詞法分析器每次總是試圖發現與正規式匹配的最長前綴，然后執行對應的動作，典型的動作是將控制返回語法分析器如果這個動作不返回控制，詞法分析器將繼續尋找下面的單詞，直到由一個動作引起控制的返回語法分析器詞法分析程序的自動生成工具（3）/*聲明部分*/%{ /*常量LT,LE,EQ,NE,GT,GE,IF,THEN,ELSE,ID,NUMBER,RELOP的定義