編譯原理第3章

第三章詞法分析這一章將討論詞法分析程序的構(gòu)造。詞法分析的任務(wù)：從左至右逐個字符地對源程序進(jìn)行掃描，產(chǎn)生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號串的中間程序。前一部分討論手工構(gòu)造方法，后一部分討論自動構(gòu)造方法。3.1對于詞法分析器的要求

詞法分析器的功能和輸出形式詞法分析器的功能是輸入源程序，輸出單詞符號。單詞符號是一個程序語言的基本語法符號。程序語言的單詞符號一般可分為下列五種。(1)關(guān)鍵字（保留字或基本字）(2)標(biāo)識符(3)常數(shù)（整型、實型、布爾型、文字型等）(4)運算符。(5)界符(逗號、分號、括號、／*，*／等)。詞法分析器所輸出的單詞符號常常表示成如下的二元式：（單詞種別，單詞符號的屬性值）考慮下述c＋＋代碼段：while（i＞=j）i--;經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：＜while，-＞＜（，-＞＜id，指向i的符號表項的指針＞＜＞＝，-＞＜id,指向i的符號表項的指針＞＜），-＞＜id，指向i的符號表項的指針>＜--，-＞＜；，-＞詞法分析器作為一個獨立子程序可使整個編譯程序的結(jié)構(gòu)更簡沽、清晰和條理化。也可以把詞法分析器安排成一個子程序，每當(dāng)語法分析器需要一個單詞符號時就調(diào)用這個子程序。每一次調(diào)用，詞法分析器就從輸人串中識別出一個單詞符號，把它交給語法分析器。3.2詞法分析器的設(shè)計一、設(shè)計第一步：輸入、預(yù)處理詞法分析器工作的第一步是輸入源程序文本。輸入串一般是放在一個緩沖區(qū)中，這個緩沖區(qū)稱輸入緩沖區(qū)。預(yù)處理工作包括對空白符、跳格符、回車符和換行符等編輯性字符的處理，及刪除注解等。設(shè)想構(gòu)造一個預(yù)處理子程序，他完成上面的工作。每當(dāng)詞法分析器調(diào)用它時就處理出一串確定長度的輸入字符，并將其裝入詞法分析器所指定的緩沖區(qū)中（稱為掃描緩沖區(qū)）。這樣分析器就可以在此緩沖區(qū)中直接進(jìn)行單詞符號的識別工作。當(dāng)詞法分析器調(diào)用預(yù)處理子程序處理出一串輸入字符串放進(jìn)掃描緩沖區(qū)之后，分析器就從此緩沖區(qū)中逐一識別單詞符號。當(dāng)緩沖區(qū)里的字符串被處理完之后，它又調(diào)用預(yù)處理程序裝入新串。設(shè)計第二步：二、單詞符號的識別：超前搜索

分析器對掃描緩沖區(qū)進(jìn)行掃描時一般用兩個指示器，一個指向當(dāng)前正在識別的單詞的開始位置（指向新單詞的首字符），另一個用于向前搜索以尋找單詞的終點。起點指示器搜索指示器超前掃描關(guān)健字的識別：（如FORTRAN語言)1D099K＝1，102IF（5．EQ．M）I=103D099K＝1．104IF(5)＝55這四個語句都是正確的FORTRAN語句。語句1和2分別是DO和IF語句，它們都是以某基本字開頭的。語句3和4是賦值語句，它們都是以用戶自定義的標(biāo)識符開頭的?！魪?、2中識別出關(guān)鍵字DO和IF，我們必須要能夠區(qū)別1、3和區(qū)別2、4。※語句1、3的區(qū)別在于等號之后的第一個界符：一個為逗號，另個為句末符。※語句2、4的主要區(qū)別在于右括號后的第一個字符：一個為字母，另一個為等號。

★為了識別1、2句中的關(guān)鍵字，我們必須超前掃描許多個字符，超前到能夠肯定詞性的地方為止。對于1、3來說，盡管都以‘D’和‘O’兩個字母開頭，但不能一見‘DO’就認(rèn)定是DO語句。我們們必須超前搜索，跳過所有的字母和數(shù)字，看看是否有等號。如果有，再向前搜索。若下一個界符是逗號，則可以肯定DO應(yīng)為關(guān)鍵字。否則，DO不構(gòu)成關(guān)鍵字，它只是用戶標(biāo)識符的頭兩個字母。所以為了區(qū)別1和3，我們必須超前掃描到等號后的第一個界符處?！飳τ?和4來說，必須超前掃描到與IF后的左括號相對應(yīng)的那個右括號之后的第一個字符為止。若此字符是字母，則得邏輯IF。若此字符為數(shù)字，則得算術(shù)IF。否則，應(yīng)認(rèn)為是用戶自定義標(biāo)識符IF.

標(biāo)識符的識別、常數(shù)的識別及算符和界符的識別相類似可以參考課本P40,P41這里就不再多述。標(biāo)識符的識別常數(shù)的識別算符和界符的識別

三、狀態(tài)轉(zhuǎn)換圖

轉(zhuǎn)換圖是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中，結(jié)點代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連結(jié)。箭弧上的標(biāo)記（字符）代表在射出結(jié)點（即箭弧始結(jié)點）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。一張轉(zhuǎn)換圖只包含有限個狀態(tài)（即有限個結(jié)點），其中有一個被認(rèn)為是初態(tài)，而且實際上至少要有一個終態(tài)（用雙圈表示）。一個狀態(tài)轉(zhuǎn)換圖可用于識別（或接受）一定的字符串。123XY012字母字母或數(shù)字其它012數(shù)字?jǐn)?shù)字其它06123457.數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字E或DE或D+或-其它*其它.四、狀態(tài)轉(zhuǎn)換圖的實現(xiàn)(1)ch

字符變量，存放最新讀進(jìn)的源程序字符。(2)strToken

字符數(shù)組，存放構(gòu)成單詞符號的字符串。(3)GetChar

子程序過程，將下一輸入字符讀到ch中，搜索指示器前移一字符位置。(4)GetBC

子程序討程．檢杳ch中的字符是否為空白。若是，則調(diào)用GetChar直至ch中進(jìn)入一個非空白字符(5)Concat

子程序過程，將ch中的字符連接到strToken之后。(6)IsLetter和IsDigit

布爾函數(shù)過程，它們分別判斷ch中的字符是否為字母和數(shù)字。(7)Reserve

整型函數(shù)過程，對strToken中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返回0值（假定0不是保留字的編碼）。(8)Retract

子程序過程，將搜索指示器回調(diào)一個字符位置，將ch置為空白字符。(9)InsertId

整型函數(shù)過程，將strToken中的標(biāo)識符插入符號表，返回符號表指針。(10）InsertConst

整型函數(shù)過程，將strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針。對于不含回路的分叉結(jié)點來說，可讓它對應(yīng)一個switch語句或一組if...then...else語句。例如，下圖狀態(tài)結(jié)點i所對應(yīng)的程序段可表示為：

GetChar(）；

if（IsLetter（））{…狀態(tài)J的對應(yīng)程序段…；｝

elseif（IsDigit（））{…狀態(tài)k的對應(yīng)程序段…；｝

elseif（ch＝‘／’）{…狀態(tài)I的對應(yīng)程序段…；｝

else{…錯誤處理…；｝ijkl字母數(shù)字/對于含回路的狀態(tài)結(jié)點來說，可讓它對應(yīng)一個由while語句和if語句構(gòu)成的程序段。例如，下圖的狀態(tài)結(jié)點i所對應(yīng)的程序段可為：

CetChar(）；

while（IsLetter(）orIsDigit(））

CetChar（）；

…狀態(tài)j的對應(yīng)程序段…ij字母或數(shù)字其它終態(tài)結(jié)點一般對應(yīng)一個形如return（code，value）的語句。其中，code為單詞種別編碼；value或是單詞符號的屬性值，或無定義。3.3正規(guī)表達(dá)式與有限自動機(jī)一、正規(guī)式與正規(guī)集

正規(guī)式和正規(guī)集的遞歸定義：（1）ε和φ都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和φ(2)任何a€Σ，a是Σ上的一個正規(guī)式，它所表示的正規(guī)集為{a}；(3)假定U和V都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別記為L(U)和L(V)，那么，(U|V)、(U·V)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(U)UL(V),L(U)L（V）（連接積）和（L（U））*（閉包）。僅由有限次使用上述三步驟而得到的表達(dá)式才是Σ上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集。正規(guī)式的運算符，’|”讀為“或”，“·”讀為“連接”，“*”讀為“閉包”（即，任意有限次的自重復(fù)連接）。規(guī)定算符的優(yōu)先順序為：先“*”，，次“·”．最后”|”。連接符”·”一般可省略不寫。例3.1:令Σ=｛a,b}，下面是Σ上的正規(guī)式和相應(yīng)的正規(guī)集：正規(guī)式正規(guī)集

ba*Σ上所有以b為首后跟任意多個a的字。

a(a|b)*Σ上所有以a為首的字。

(a|b)*（aa|bb)（a|b)*Σ上所有含有兩個相繼的a或兩個相繼的b的字。例3.2令Σ={A，B，0，1｝，則正規(guī)式正規(guī)集

(A|B）（A|B|0|1)*Σ上的“標(biāo)識符”的全體

(0|1)(0|1)*Σ上的“數(shù)”的全體。若兩個正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價。兩個等價的正規(guī)式U和V記為

U=V。例如，b（ab）*=（ba）*b，（a|b）*=（a*b*）*。令U、V和W均為正規(guī)式，顯而易見，下列關(guān)系普遍成立：（1）U|V=V|U（交換律）；

(2）U|（V|W）=（U|V）|W（結(jié)合律）

(3)U（VW）=（UV）W（結(jié)合律）；

(4）U（V|W）＝UV|UW（分配律）

(V|W)U＝VU|WU；

(5）εU=Uε＝U二、確定有限自動機(jī)（DFA)1、定義：

一個確定有限自動機(jī)（DFA）M是一個五元式

M＝（S，Σ,δ,s0，F(xiàn))其中（1)S是一個有限集，它的每個元素稱為一個狀態(tài)。

(2)Σ是一個有窮字母表，它的每個元素稱為一個輸入字符。

(3)δ是一個從SxΣ至S的單值部分映射。δ(s，a)＝s’意味著：當(dāng)現(xiàn)行狀態(tài)為s、輸入字符為a時，將轉(zhuǎn)換到下一狀態(tài)s’。我們稱s’為s的一個后繼狀態(tài)。

(4)s0∈S,是唯一的初態(tài)。

(5)F?S,是一個終態(tài)集（可空）.2、狀態(tài)轉(zhuǎn)換矩陣：顯然，DFA可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元表示δ(s,a）的值，該矩陣稱為狀態(tài)轉(zhuǎn)換矩陣。例如，有DFAM=({0,1,2,3}，{a,b}，δ，0，{3})其中δ為δ(0,a)＝1δ(0,b)＝2δ(1,a)＝3δ(1,b)=2δ(2,a)＝lδ(2,b）=3δ(3,a)＝3δ(3,b）=3它所對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如表所列狀態(tài)ab0121322133333、一個DFA也可表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖。假定DFAM

含有m個狀態(tài)n個輸入字符，那末，這張圖含有m個狀態(tài)結(jié)點，每個結(jié)點頂多有n條箭弧射出和別的結(jié)點相連接，每條箭弧用上的一個不同字符作標(biāo)記，整張圖含有唯一的初態(tài)和若干個（可以是0個）終態(tài)結(jié)點。1203aaabbba/b對于∑*中的任何字α，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標(biāo)記符連接成的字等于α，則稱α可為DFAM所識別（讀出或接受）。若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字ε可為M所識別（或接受）。DFAM所能識別的字的全體記為L(M）。如果一個DFAM的輸入字母表為∑，則我們也稱M是∑上的一個DFA?？梢宰C明：∑上的一個字集V?∑*是正規(guī)的，當(dāng)且僅當(dāng)存在∑上的DFAM,使得V＝L(M)。[例]有DFAM=({0,1,2,3},{a,b},,0,{3})其中：（0,a)=1;（0,b)=2

（1,a)=3;（1,b)=2

（2,a)=1;（2,b)=3

（3,a)=3;（3,b)=3問：有幾個狀態(tài)？幾個輸入字符？并畫出其轉(zhuǎn)換圖。L(M)=?解：有0，1，2，3共四個狀態(tài)。輸入字符為a,b兩個。其狀態(tài)轉(zhuǎn)換圖如右L(M)為在上所有含相繼兩個a或相繼兩個b的字。三、非確定有限自動機(jī)（NFA)一個非確定有限自動機(jī)（NFA)M是一個五元式

M＝（S，∑，δ，S0,F)

其中（1）S同3.3.2的1；

(2）∑同3．3．2的2；

(3)δ是一個從S×∑*到S的子集的映照，即δ:S×∑*→2的s次方

(4)S0?S，是一個非空初態(tài)集；

(5)F?S，是一個終態(tài)集（可空）。一個含有m個狀態(tài)和n個輸入字符的NFA可表示成如下的狀態(tài)轉(zhuǎn)換圖：該圖含有m個狀態(tài)結(jié)點，每個結(jié)點可射出若干條箭弧與別的結(jié)點相連接，每條弧用∑*中的一個字（不一定要不同的字而且可以是空字ε）作標(biāo)記（稱為輸入字），整張圖至少含有一個初態(tài)結(jié)點以及若干個（可以是0個）終態(tài)結(jié)點。某些結(jié)點既可以是初態(tài)結(jié)點也可以是終態(tài)結(jié)點。對于∑*中的任何一個字α，若存在一條從某一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字（忽略那些標(biāo)記為ε的弧）等于α,則稱α可為NFAM所識別（讀出或接受）。若M的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或者存在一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的ε通路，那么，空字ε可為M所接受。顯然DFA式NFA的特例。對于每個NFAM存在一個DFAM”，使L(M)=L(M”)。其證明如下（略）（這個證明需要掌握）在這個證明中我想特別強(qiáng)調(diào)的是課本P49頁下邊提到的對M的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行圖3。7所示的替換，其中k是新引入的狀態(tài)。

書中的這個圖3。7同時也是從正規(guī)式畫有限自動機(jī)狀態(tài)轉(zhuǎn)換圖的重要方法。對于正規(guī)式中的連接可按1式畫其轉(zhuǎn)換圖，對于或可用2式，對于閉包可用3式將正規(guī)式轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換圖靈活使用這些規(guī)則非常重要的。如：正規(guī)式：R=(a*b)*ba(a|b)*

可以畫為：

例如，下圖就是一個NFA,這個NFA所能識別的也是所有含有相繼兩個a或相繼兩個b的字5XYaabε62431ababbεεε四、DFA與NFA的等價顯然,DFA是NFA的特例。但是，對于每個NFAM存在一個DFAM'',使L(M)=L(M''）。證明過程如下：(1)假定NFAM＝＜S,∑,δ,s0,F＞，對M的狀態(tài)轉(zhuǎn)換圖進(jìn)行以下改造：

①引進(jìn)新的初態(tài)結(jié)點X和終態(tài)結(jié)點Y，

X，Y∈S,從X到s0中任意狀態(tài)結(jié)點連一條ε箭弧，從F中任意狀態(tài)結(jié)點連一條ε箭弧到Y(jié)。②對M的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行圖3.7所示的替換．其中k是新引入的狀態(tài)。重復(fù)這種分裂過程直至狀態(tài)轉(zhuǎn)換圖中的每條箭弧上的標(biāo)記或為ε，或為∑中的單個字母。將最終得到的NFA記為M'，

顯然L(M'）=L(M）。ijABijA/BijA*ikjABijABikiAεε(2)將M'進(jìn)一步變換為DFA，方法如下：①假定I是M'的狀態(tài)集的子集，定義I的ε閉包=CLOSURE(I)為:(a)若q∈I,則q∈CLOSURE(I)；(b)若q∈I,那么從q出發(fā)經(jīng)任意條ε弧而能到達(dá)的任何狀態(tài)q‘都屬于ε_CLOSURE（I)；②假定I是M'的狀態(tài)集的子集，a∈∑，

定義Ia＝ε_CLOSURE(J)

其中，J是那些可從I中的某一狀態(tài)結(jié)點出發(fā)經(jīng)過一條a弧而到達(dá)的狀態(tài)結(jié)點的全體。③假定∑＝｛a1，…，ak｝。我們構(gòu)造一張表，此表的每一行含有k十1列。置該表的首行首列為ε_CLOSURE(X)。一般而言，如果某一行的第一列的狀態(tài)子集已經(jīng)確定，例如記為I，那么，置該行的i十1列為Iai（i＝1，…，k)。然后，檢查該行上的所有狀態(tài)子集，看它們是否已在表的第一列中出現(xiàn)．將未曾出現(xiàn)者填入到后面空行的第一列。重復(fù)上述過程，直至出現(xiàn)在第i＋1列（i＝1，....k)上的所有狀態(tài)子集均已在第一列上出現(xiàn)。因為M'的狀態(tài)子集的個數(shù)是有限的，所以上述過程必定在有限步內(nèi)終止。例3.3：正規(guī)式(a|b)*(aa|bb)(a|b)*對應(yīng)的NFA5XYaabε62431ababbεεε子集法構(gòu)造出的狀態(tài)轉(zhuǎn)換矩陣IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,3,1,2,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}對上表所有狀態(tài)子集重新命名．得到以下狀態(tài)轉(zhuǎn)換矩陣sab012132215334465565634相對應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖1052634aaaaaabbbbbba五、正規(guī)文法與有限自動機(jī)的等價性對于正規(guī)文法G和有限自動機(jī)M,如果L(G)=L(M),則稱G和M是等價的。關(guān)于正規(guī)文法和有限自動機(jī)的等價性，有以下結(jié)論：

(1)對每一個右線性正規(guī)文法G或左線性正規(guī)文法M，都存在一個有限自動機(jī)(FA)M，使得L(M）=L(G）。

(2）對每一個FAM,都存在一個右線性文法Gr和左線性正規(guī)文法Gl，使得L(M)=L(Gr)=L(Gl)六、正規(guī)式與有限自動機(jī)的等價性（1)對任何FAM,都存在一個正規(guī)式r,使得L(r)=L(M）。

(2）對任何正規(guī)式r,都存在一個FAM,使得L(M)=L(r)。說明正規(guī)文法、正規(guī)式、確定有限自動機(jī)和非確定有限自動機(jī)在接收語言的能力上是互相等價的。由正規(guī)式構(gòu)造等價的NFAM

由正規(guī)式構(gòu)造等價的NFAM的方法：

(1)將正規(guī)式R表示為拓廣轉(zhuǎn)換圖。X2YR

(2)采用下述三條轉(zhuǎn)換規(guī)則構(gòu)造NFAM。

sisjr1|r2*1.r1r2ee2.3.sjsjsisir1r2sisisir1r1r1r2sjsjsjsksk對正規(guī)式R,先將其表示為拓廣轉(zhuǎn)換圖,其中X為初態(tài),Y為終態(tài),再逐步運用三條轉(zhuǎn)換規(guī)則不斷加入新結(jié)點,直至每條有向邊上僅標(biāo)識Σ的一個字母或ε為止,至此NFAM構(gòu)造完成。例2.6構(gòu)造b*(d|ad)(b|ab)+對應(yīng)的NFA。解:首先用R+=RR*把正規(guī)式改造為

b*(d|ad)(b|ab)(b|ab)*

然后構(gòu)造其NFAM，如下圖所示：b*(d|ad)(b|ab)(b|ab)*XY(b|ab)*d|adb*b|ababadεεbεεdb|abb41235εεbX41d26εεbb3578adbaabXX132YYY確定有限自動機(jī)的化簡

NFA確定化所得的DFA可能含有多余的狀態(tài),需化簡。所謂DFAM的化簡：是指尋找一個狀態(tài)數(shù)比M少的DFAM'，使得L(M)=L(M')。

化簡后的DFAM'滿足下述條件：

(1)無多余狀態(tài)；

(2)狀態(tài)集中無相互等價的狀態(tài)。假定s和t是M的兩個不同狀態(tài)，我們稱s和t是等價的：如果從狀態(tài)s出發(fā)能讀出某個字w而停于終態(tài)，那么同樣從t出發(fā)也能讀出同樣的字w而停于終態(tài)；反之，若從t出發(fā)能讀出某個字w而停于終態(tài)，則從s出發(fā)也能讀出同樣的w而停于終態(tài)。如果DFAM的兩個狀態(tài)s和t不等價，則稱這兩個狀態(tài)是可區(qū)別的。例如，終態(tài)與非終態(tài)是可區(qū)別的。因為，終態(tài)能讀出空字ε，非終態(tài)則不能讀出空字ε。一個DFAM的狀態(tài)最少化過程旨在將M的狀態(tài)集分割成一些不相交的子集，使得任何不同的兩子集中的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的。最后，在每個子集中選出一個代表，同時消去其它等價狀態(tài)。DFAM的化簡方法：(1)首先將DFAM的狀態(tài)集S中的終態(tài)與非終態(tài)分開,形成兩個子集,得到基本劃分。(2)對當(dāng)前已劃分出的I(1),I(2),…,I(m)子集,看每個I是否能進(jìn)一步劃分。對某個I(i)={s1,s2,…,sk},若存在輸入字符a∈Σ使得Ia(i)不全包含在當(dāng)前劃分的某個子集I(j)中,即跨越兩個子集,則將I(i)一分為二。(3)重復(fù)(2),直到每個子集均不能再分。

不能再分是指子集要么僅有一個狀態(tài)，要么有多個狀態(tài)但這些狀態(tài)不可區(qū)分。如何進(jìn)行子集的劃分呢？

假定當(dāng)前子集I(i)={s1,s2,…},其中s1和s2經(jīng)過有向邊a分別到達(dá)狀態(tài)t1和t2,而t1和t2分屬于當(dāng)前已劃出的兩個不同子集I(j)和I(k),則應(yīng)將I(i)分為兩部分：

I(i1)={s|s∈I(i)且s經(jīng)有向邊a到達(dá)t1}I(i2)=I(i)?I(i1)

由于t1和t2可區(qū)分，因此I(i1)中的狀態(tài)與I(i2)中的狀態(tài)可區(qū)分。劃分結(jié)束后,子集個數(shù)不再增加,從每個子集中選一個狀態(tài)形成新的DFA。

例如，I(i)={s1,s2,s3}

若挑選s1作為I(i)的代表，則原來指向s2和s3的有向邊均改為指向新DFA中的s1。若I(i)中含原來的初態(tài)，則s1為新初態(tài)；

若I(i)中含原來的終態(tài)，則s1為新終態(tài)。例3．6圖3．8所示的DFAM的化簡過程是：首先，把M的狀態(tài)分成兩組：終態(tài)組{3,4,5，6}，非終態(tài)組{0,1,2｝。其次，考察{3,4,5,6}，由于{3,4,5,6}a?{3,4,5,6}和{3,4,5,6}b?{3,4,5,6}，所以，它不能再分劃。再考察{0,1,2}，由于{0,1,2}a=｛1，3}．它既不包含在{3,4,5,6}之中也不包含在{0,1,2}之中，因此，應(yīng)把{0,1,2｝一分為二。由于狀態(tài)1經(jīng)a弧到達(dá)狀態(tài)3，而狀態(tài)0,2經(jīng)a弧都到達(dá)狀態(tài)1，因此，應(yīng)把1分出來，形成{1｝、{0,2｝?，F(xiàn)在，整個分劃中含有三組：｛3,4,5,6}、{1｝和{0,2}.由于{0,2}b={2,5}未包含在上述三組中的任一組之中，故{0,2}也應(yīng)一分為二：{0}，{2}.化簡下圖,使其最小化CDBAEFSbaaaaabbbbbabFa∏0:

{S,A,B}

{C,D,E,F}CDBAEFSbaaaaaabbbbbba∏1:

∏2:b{S},{B}a{A}，{S,B}{S,A,B}DBASaaabbbba3.4詞法分析器的自動產(chǎn)生--LEX

由于不同高級語言中單詞的結(jié)構(gòu)大致相同,基本上都可用一組正規(guī)式描述,因而希望構(gòu)造一自動生成系統(tǒng):只要給出某高級語言單詞的一組正規(guī)式及識別各類單詞時應(yīng)采取的語義動作,該系統(tǒng)便可自動產(chǎn)生該語言的詞法分析程序。

LEX源程序LEX編譯系統(tǒng)詞法分析程序L輸入串詞法分析程序L單詞符號串

LEX是美國Bell實驗室研制的一個詞法分析程序的自動生成工具。對任一高級程序語言，用戶必須用正規(guī)式描述該語言的各個詞法類(LEX的源程序)，LEX就可自動生成該語言的詞法分析程序。LEX及其編譯系統(tǒng)作用如下:

LEX所產(chǎn)生的目標(biāo)程序L（詞法分析器）工作原理：書59頁

LEX可用兩種方式來使用：一種是將LEX作為一個單獨的工具，用以生成所需的識別程序；另一種是將LEX和語法分析器自動生成工具(如YACC)結(jié)合起來使用，用以生成一個編譯程序的掃描器和語法分析器。[例3.1]寫能被5整除的十進(jìn)制整數(shù)的文法及正則表達(dá)式。[例3.2]寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。[例3.3]寫出能被3整除十進(jìn)制整數(shù)的文法和正則表達(dá)式：[例3.4]請構(gòu)造與正則式R=(a*b)*ba(a|b)*等價的狀態(tài)最少的DFA（確定有限自動機(jī)）例題與習(xí)題解答[例3.1]解：能被5整除的文法：

G[Z]:Z→(+|-

)A(0|5)

A→0|1|2|3|4|5|6|7|8|9|AA如果要求：除零以外不以0開頭，責(zé)文法為：

G[Z]:Z→(+|-)A(0|5)A→AB|CB→0|C|BBC→0|1|2|3|4|5|6|7|8|9正則表達(dá)式：G[Z]:Z=(+|-)A*(0|5)A∈(0,1,2,3,4,5,6,7,8,9)

[例3.2]解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D

[例3.3]解：能被3整除的文法：

G=({0,1,2,3,4,5,6,7,8,9},{S,A,B},S,P,)其中P為：S->(0|3|6|9)S|εS->(1|4|7)A|(2|5|8)BA->(0|3|6|9)A|(1|4|7)B|(2|5|8)SB->(0|3|6|9)B|(2|5|8)A|(1|4|7)S正則表達(dá)式：

Z=a*|(bc)*|(cb)*|(a|cibi)*|(ciabi)*(i>=1)a∈(0,3,6,9)b∈(1,4,7)c∈(2,5,8)

[例3.4]解：（1）首先構(gòu)造轉(zhuǎn)換系統(tǒng)圖：（2）由系統(tǒng)轉(zhuǎn)換圖構(gòu)造DFA（NFA確定化）

設(shè)初態(tài)為[S,A,B,G,F]

NFA確定化為DFA的過程：

IIa

Ib(1)[S,A,B,G,F](2)[G,F](3)[A,B,C,G,F](2)[G,F](2)[G,F](4)[A,B,G,F](3)[A,B,C,G,F](5)[D,F,G,E,Z](3)[A,B,C,G,F](4)[A,B,G,F](2)[G,F](3)[A,B,C,G,F](5)[D,F,G,E,Z](6)[G,F,E,Z](7)[A,B,E,Z,G,F](6)[G,F,E,Z](6)[G,F,E,Z](7)[A,B,E,Z,G,F](7)[A,B,E,Z,G,F](6)[G,F,E,Z](8)[A,B,C,E,Z,G,F](8)[A,B,C,E,Z,G,F](5)[D,F,G,E,Z](8)[A,B,C,E,Z,G,F]

DFA這狀態(tài)圖如下：

確定有限自動機(jī)圖如下：（3）將DFA最小化：先將終態(tài)和非終態(tài)分成兩個集:K1={1,2,3,4},K2={5,6,7,8}對于K1中的3態(tài)輸入a則進(jìn)入K2集，而1，2，4態(tài)輸入a仍然在K1中，故K1可一分為二K11={1,2,4}和K12={3};考察K11對于1，4態(tài)輸入b到達(dá)3態(tài)而2態(tài)輸入b到達(dá)4態(tài)。故K11可一分為二K111={1,4};K112={2}最后考察K2輸入a或b都到達(dá)K2集。則DFA化簡為{1，4}，{2}，{3}，{5，6，7，8}四個子集。其狀態(tài)圖如下：[例3.5]：已知有限自動機(jī)如圖(1)以上狀態(tài)轉(zhuǎn)換圖表示的語言有什么特征？(2)寫出其正規(guī)式與正規(guī)文法.(3)構(gòu)造識別該語言的有限自動機(jī)DFA.

[例3.5]

解：（1）L={W|W{0,1