研究生院第三章

第三章詞法分析詞法分析的作用記號的描述，正則式記號的識別有限狀態(tài)自動機(jī)正規(guī)式與有限狀態(tài)自動機(jī)的等價詞法分析程序的自動生成工具詞法分析的作用（1）編譯器的第一階段：讀輸入的字符流，產(chǎn)生用于語法分析的記號序列完成和用戶接口的一些任務(wù)：源程序行信息的記錄，為報錯提供支持注解、空白的剝離宏的預(yù)處理詞法分析的作用（2）分離詞法分析的理由簡化設(shè)計：分離詞法分析和語法分析，可以簡化語法分析的復(fù)雜性詞法和語法規(guī)則的分離可以方便程序設(shè)計語言的設(shè)計利于設(shè)計高效的詞法分析程序增加編譯器的可移植性：將輸入字符集的特殊性和其它與設(shè)備有關(guān)的不規(guī)則性限制在詞法分析程序中詞法分析的作用（3）基本概念：單詞：源程序中的字符序列模式：單詞的分類規(guī)則，程序中的單詞有很多，具有相同詞法屬性的單詞歸為一類記號token：不同的單詞類。記號是源語言語法的終結(jié)符通常，記號定義為枚舉型：關(guān)鍵字、算符、標(biāo)識符、常數(shù)、字符串、標(biāo)點符號等對于某些程序設(shè)計語言，可能要求某些特定的結(jié)構(gòu)出現(xiàn)在特定的位置，如FORTRAN語言的標(biāo)號，因此單詞對準(zhǔn)對詞法分析的正確性很重要，但現(xiàn)代語言一般采用自由格式，這類問題不重要了詞法分析的作用（4）分隔符：決定了單詞的分隔，一般以空白字符為分隔，但有些語言如FORTRAN語言，空白字符不是分隔符 如DO5I=1.25，只有讀入“.”時才能確認(rèn)DO5I是一個標(biāo)識符，而不是DO語句的一部分關(guān)鍵字是否為保留字：很多語言規(guī)定關(guān)鍵字是保留字，即其含義是預(yù)定義的，用戶不能改變，詞法分析較易實現(xiàn)；否則，詞法分析程序必須區(qū)分是關(guān)鍵字還是用戶自定義的標(biāo)識符 如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，整數(shù)值2>詞法分析的作用（7）詞法錯誤：詞法分析基本無法檢查出來錯誤但有時由于剩余輸入的前綴不能和任何記號的模式匹配而使得詞法分析器無法處理錯誤恢復(fù)策略：緊急方式：刪掉剩余輸入最前面的字符，直至發(fā)現(xiàn)一個正確的符考慮到大多數(shù)詞法錯誤是輸入錯誤，因此下列方法可能將錯誤進(jìn)行修補(bǔ)，但不是總有效的刪除一個多余的字符插入一個遺漏的字符用一個正確的字符代替一個不正確的字符交換兩個相臨的字符詞法分析的理論基礎(chǔ)正規(guī)式表示構(gòu)成程序設(shè)計語言的詞法結(jié)構(gòu)的串格式的標(biāo)準(zhǔn)表示法有限狀態(tài)自動機(jī)對由正規(guī)表達(dá)式給出的串格式的識別算法正規(guī)式（1）正規(guī)式：按照一組定義規(guī)則，由較簡單的正規(guī)式構(gòu)成的正規(guī)式與3型文法是等價的正規(guī)集：正規(guī)式表示的語言構(gòu)成規(guī)則：定義字母表∑上的正規(guī)式的規(guī)則ε是正規(guī)式，表示的語言是{ε}如果a是∑上的符號，則a是正規(guī)式，表示{a}如果r和s是正規(guī)式，分別表示語言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ī)則得到的表達(dá)式才是∑上的正規(guī)式正規(guī)式（2）構(gòu)成規(guī)則的優(yōu)先性閉包運(yùn)算(*)優(yōu)先于連結(jié)運(yùn)算連結(jié)運(yùn)算優(yōu)先于|這三種運(yùn)算都是左結(jié)合的“()”可以改變運(yùn)算的次序 有了上述優(yōu)先性的定義，可以化簡正規(guī)式： (a)|((b)*(c))可以化簡為a|b*c正規(guī)式（3）例1：令∑={a,b}，則：正規(guī)式a|b表示集合{a,b}正規(guī)式(a|b)(a|b)表示集合{aa,ab,ba,bb}，這個集合也可以由正規(guī)式aa|ab|ba|bb表示正規(guī)式a*表示零個或多個a的所有串的集合正規(guī)式（a|b)*表示零個或多個a或b的所有串的集合，這個集合也可以由正規(guī)式（a*|b*)*表示正規(guī)式a|a*b表示串a(chǎn)和零個或多個a后隨一個b的所有串的集合正規(guī)式（4）正規(guī)式的等價： 如果兩個正規(guī)式表示同樣的語言，則這兩個正規(guī)式等價正規(guī)式的代數(shù)性質(zhì)： 公理 描 述r|s=s|r |是可交換的r|(s|t)=(r|s)|t |是可結(jié)合的(rs)t=r(st) 連結(jié)是可結(jié)合的r(s|t)=rs|rt 連結(jié)對|可分配(s|t)r=sr|trεr=r ε是連結(jié)的恒等元素rε=rr*=(r|ε)* *和ε間的關(guān)系r**=r* *是冪等的正規(guī)式（5）正規(guī)定義為什么引入正規(guī)定義：正規(guī)式描述單詞符號簡潔、直觀

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

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

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

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

digit→0|1|…|9

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

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.正規(guī)式（10）表示的縮寫：某些頻繁出現(xiàn)的結(jié)構(gòu)可以簡便表示一個或多個實例：一元后綴算符+如果r是表示語言L(r)的正規(guī)式，則是r+表示語言(L(r))+的正規(guī)式(0|1)+是二進(jìn)制數(shù)的正規(guī)式+和*有同樣的優(yōu)先級和結(jié)合性r*=r+|ε，r+=rr*零個或一個實例：一元后綴算符？r?是r|ε的縮寫對于正規(guī)式r，r?表示語言L(r)|{ε}正規(guī)式（11）用+和？重寫例3

digit→0|1|…|9

digits→digit+

optional_fraction→(.digits)?

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

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

num→digitremainder1

remainder1→digitremainder1|.remainder2| Eremainder4|ε

remainder2→digitremainder3

remainder3→digitremainder3|Eremainder4|ε

remainder4→+digits|-digits|digitremainder5

digits→digit

remainder5

remainder5→digitremainder5|ε詞法分析程序的構(gòu)造（3）基本符號的識別狀態(tài)轉(zhuǎn)換圖狀態(tài)集合的構(gòu)成文法中的非終結(jié)符對應(yīng)一個狀態(tài)文法的開始符號是初態(tài)增加一個終態(tài)狀態(tài)間的轉(zhuǎn)換弧的表示：產(chǎn)生式中的終結(jié)符產(chǎn)生式A→aB，從狀態(tài)A到狀態(tài)B畫一條標(biāo)記a的弧產(chǎn)生式A→a，從狀態(tài)A到終態(tài)畫一條標(biāo)記a的弧

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

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

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

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

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

把T的所有狀態(tài)壓入棧

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

把棧頂元素t彈出棧

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

把u加入ε閉包(T)

把u壓入棧

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

輸出：一個接受同樣語言的DFAD,狀態(tài)集合Dstates ，轉(zhuǎn)換表Dtran

算法：

ε閉包(s0)是Dstates僅有的狀態(tài)，且尚未標(biāo)記

whileDstates有尚未標(biāo)記的狀態(tài)Tdobegin

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

把U作為尚未標(biāo)記的狀態(tài)加入Dstates中

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

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

forΠ中的每個組Gdobegin

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

，讓Πfinal:=Π

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