編譯原理-第三章

第三章詞法分析3.1詞法分析器的設(shè)計(jì)詞法分析的主要工作:

從源程序的第一個(gè)字符開始，從左到右掃描源程序，一次讀一個(gè)字符，根據(jù)詞法規(guī)則將有關(guān)字符組合成單詞，并識別各類單詞，當(dāng)確定單詞類別后，將單詞輸出。在詞法分析過程中還要完成其它任務(wù)，如：過濾掉源程序中的注釋和空白；記錄讀入字符的行號，以便發(fā)現(xiàn)錯(cuò)誤后能報(bào)告出錯(cuò)位置；進(jìn)行預(yù)編譯工作(對宏進(jìn)行展開等工作)；符號表操作。錯(cuò)誤處理等。詞法分析與語法分析的接口方式：(1)詞法分析作為一遍：將詞法分析器的輸出結(jié)果放入一個(gè)中間文件上(外存)或直接存放在內(nèi)存中，后面的語法分析程序?qū)⑺鳛檩斎脒M(jìn)行語法分析，這樣通過一遍加工就可以將以字符串形式的源程序加工成單詞串形式的源程序。LexicalanalyzerCharacterstreamTokenstreamErrormessages(2)詞法分析與語法分析安排在同一遍中：將詞法分析編成一個(gè)子程序，該子程序由語法分析程序調(diào)用。當(dāng)語法分析程序需要一個(gè)新單詞時(shí)，調(diào)用該程序，每調(diào)用一次，則從源程序中讀出一個(gè)單詞，這樣避免了中間文件的生成，可以提高編譯效率。CharacterstreamLexicalanalyzersyntaxanalyzerAbstractSyntax詞法分析的分離：

實(shí)際上，詞法也是語法的一部分，詞法描述完全可以歸并到語法描述中去，只不過詞法規(guī)則更簡單些。進(jìn)一步說，在編譯程序中可以將詞法分析包含在語法分析之中，那么為什么把編譯過程的分析工作劃分成詞法分析和語法分析兩個(gè)階段？主要考慮的因素為：(1)使整個(gè)編譯程序的結(jié)構(gòu)更簡潔、清晰和條理化；

(2)編譯程序的效率會改進(jìn)；(3)增強(qiáng)編譯程序的可移植性。

源程序的輸入：(1)一次性輸入：當(dāng)內(nèi)存較大時(shí)，把源程序一次性輸入到內(nèi)存的用戶數(shù)據(jù)區(qū)，每個(gè)字符占一個(gè)字節(jié)，詞法分析程序從數(shù)據(jù)區(qū)中依次讀入字符。………數(shù)據(jù)區(qū)詞法分析(2)分批次輸入：當(dāng)內(nèi)存不夠大時(shí)，在內(nèi)存開辟一個(gè)適當(dāng)大小的輸入緩沖區(qū)，輸入時(shí)，把源程序分批輸入到輸入緩沖區(qū)，詞法分析程序從緩沖區(qū)中讀取字符，當(dāng)緩沖區(qū)的字符全部讀完以后，再從外存上讀入下一批，直到全部源程序字符讀完為止?！彌_區(qū)詞法分析(3)超前搜索：詞法分析程序在組合單詞的時(shí)候，為了進(jìn)一步判明情況和確定下一步要做什么以及為了處理上的方便等，常采取超前搜索的辦法，即先向前讀取字符和判別字符是什么，不馬上處理，當(dāng)情況判明后，再回來處理已讀過的字符。例如：有源程序，function

example(input,output);在判別保留字function過程中，當(dāng)讀到字符n時(shí)，雖然前

面字符為function

，還要看是否結(jié)束，即后面字符是什么

(字母、數(shù)字還是空格)，所以不能馬上處理(斷定是保留

字)，而需要再向前讀一個(gè)字符，確定后再回來處理。在判別標(biāo)識符example過程中，當(dāng)讀到字符e時(shí)，雖然前

面字符為example，為了判別下一個(gè)字符是否是該標(biāo)識符

的一部分，也要判別下一個(gè)字符是否為字母或數(shù)字，所

以不能馬上處理，需要再向前讀一個(gè)字符。Ex:p40有時(shí)，為了判別讀進(jìn)字

符所組成的單詞的類別，

需向前讀若干字符！(4)掃描緩沖區(qū)的處理：顯然，無論緩沖區(qū)設(shè)定為多大，都不能保證單詞不會被它的邊界打斷，若有單詞TEST123，可能在緩沖區(qū)中成為：………….TES在這種情況下，即使搜索指針讀到緩沖區(qū)的最后一個(gè)字符，但仍不能找到該單詞的右邊界，這時(shí)，若從外存上再讀一部分源程序進(jìn)入緩沖區(qū)，則會將沒有處理過的字符(TES)沖掉。為此，我們可將緩沖區(qū)分成相等的兩個(gè)區(qū)域：起點(diǎn)指針?biāo)阉髦羔槂蓚€(gè)半?yún)^(qū)互補(bǔ)使用兩個(gè)指針協(xié)同工作單詞長度有無限制？單詞的輸出：(1)單詞的種類：保留字：如，programbeginendvarconstfor……標(biāo)識符：如，程序名、變量名、常量名、類型名、過程名等常數(shù)：如，125、0.745、15.2E+5算符：如，+、–、*、/、等界符：如，分號、逗號等(2)詞法分析器的輸出形式：為了便于編譯程序進(jìn)一步加工，單詞的輸出形式一般采用二元式：單詞類別單詞值用整數(shù)編碼表示，如何分類以處理方便為原則，如：標(biāo)識符歸為一類；常數(shù)按類型分類；保留字一字一類，或?qū)⑷w定位一類；界符可單獨(dú)作為一類，或一符一類。采用什么樣的輸出形式也是取決于后續(xù)處理的方便，如：標(biāo)識符用字符串編碼或?qū)?yīng)地址；常數(shù)用其自身值的二進(jìn)制形式；保留字(分界符)若將全體定位一類則需輸出其值，可用內(nèi)部整數(shù)編碼或串編碼表示。例如：程序段ifi=5thenx：=y；在經(jīng)過詞法分析器掃描后，輸出的單詞可表示如下：

保留字if(3，‘if’)

標(biāo)識符i(1，指向i的符號表入口)

等號=(4，‘=’)

常數(shù)5(2，‘5’的二進(jìn)制表示)

保留字then(3，‘then’)

標(biāo)識符x(1，指向x的符號表入口)

賦值號:=(4，‘：=’)

標(biāo)識符y(1，指向y的符號表入口)

分號；(5，‘；’)其中，類別碼：“1”表示標(biāo)識符；“2”表示常數(shù)；

“3”表示保留字；“4”表示算符；“5”表示界符。3.2正則文法與狀態(tài)轉(zhuǎn)換圖一、狀態(tài)轉(zhuǎn)換圖許多程序設(shè)計(jì)語言的單詞，可以用正則文法來描述。對于這樣的語言，使用狀態(tài)轉(zhuǎn)換圖可以設(shè)計(jì)詞法分析程序（掃描器）。狀態(tài)轉(zhuǎn)換圖TG（簡稱狀態(tài)圖或轉(zhuǎn)換圖）是一張定義在字母表Σ上的有限方向圖。在狀態(tài)轉(zhuǎn)換圖中:結(jié)點(diǎn)代表狀態(tài)，用圓圈表示；狀態(tài)之間用有向弧連結(jié)；有向弧上的標(biāo)記（字符）表示在射出結(jié)點(diǎn)（有向弧的開始結(jié)點(diǎn)）所代表的狀態(tài)下可能出現(xiàn)的輸入符號或符號串。字母表Σ={0,1}上的一個(gè)轉(zhuǎn)換圖

用帶有符號“”的圓圈表示狀態(tài)轉(zhuǎn)換圖的初始狀態(tài)

用表示終止?fàn)顟B(tài)。

一個(gè)狀態(tài)轉(zhuǎn)換圖可用于接受（或識別）一定的符號串。在狀態(tài)轉(zhuǎn)換圖中從初始狀態(tài)到某一終止?fàn)顟B(tài)的序列為路。對于某一符號串β，在狀態(tài)轉(zhuǎn)換圖中，若存在一條路產(chǎn)生β，則稱狀態(tài)轉(zhuǎn)換圖接受（或識別）該符號串β，否則符號串β不能被接受。能被狀態(tài)轉(zhuǎn)換圖TG接受的符號串的集合記為L(TG)，稱為狀態(tài)轉(zhuǎn)換圖所能識別的語言。字母表Σ={0,1}上的一個(gè)轉(zhuǎn)換圖

由以上狀態(tài)轉(zhuǎn)換圖可見，字母表Σ上的符號串：1001010001111011010011011100……都能被上述轉(zhuǎn)換圖所接受。即有：L(TG)={01，10，0100，0111，1011，010011，011100，…

…}再如，設(shè)有字母表Σ={a,b}，則有字母表Σ上的一個(gè)狀態(tài)轉(zhuǎn)換圖如下：由轉(zhuǎn)換圖可見，字母表Σ={a,b}上的符號串：

a，b，ab，ba，aaa，bbb，aab，bba，…均能被這個(gè)轉(zhuǎn)換圖所接受。從而有：L(TG)={a，b，ab，ba，aaa，bbb，aab，bba，…}P41ex例：識別一個(gè)簡單語言的所有單詞符號的狀態(tài)圖見p43圖3.3二、正則文法的狀態(tài)轉(zhuǎn)換圖表示許多程序設(shè)計(jì)語言的單詞可以用正則文法來表示，而對于正則文法所描述的語言又可以用狀態(tài)轉(zhuǎn)換圖來非形式的表示。對于右線性文法G[S]，狀態(tài)轉(zhuǎn)換圖的表示方法如下：U→xV|y(1)用狀態(tài)表示G[S]中的非終結(jié)符，G[S]的開始符號S對應(yīng)狀態(tài)轉(zhuǎn)換圖的開始狀態(tài)S；(2)增加一個(gè)新狀態(tài)Z，作為狀態(tài)轉(zhuǎn)換圖的終止?fàn)顟B(tài)；(3)對于G[S]中形如U→xV的每條產(chǎn)生式，畫一條從狀態(tài)U到狀態(tài)V的方向弧，弧上的標(biāo)記為x；(4)對于G[S]中形如U→y的每條產(chǎn)生式，畫一條從狀態(tài)U到終態(tài)Z的方向弧，弧上的標(biāo)記為y例如：給出與正則文法G(S)等價(jià)的狀態(tài)轉(zhuǎn)換圖。G[S]：S→aA

S→bB

S→ε

A→aB

A→bA

B→aS

B→bA

B→εASBZabεababε正則文法與狀態(tài)轉(zhuǎn)換圖等價(jià)，是指正則文法所確定的語言L(G)，與狀態(tài)轉(zhuǎn)換圖所接受的語言L(TG)相同：

L(G)=L(TG)對于左線性文法G[Z]，狀態(tài)轉(zhuǎn)換圖的表示方法如下：U→Vx|y(1)用狀態(tài)表示G[Z]中的非終結(jié)符，G[Z]的開始符號Z對應(yīng)狀態(tài)轉(zhuǎn)換圖的終止?fàn)顟B(tài)Z(2)增加一個(gè)新狀態(tài)S，作為狀態(tài)轉(zhuǎn)換圖的初始狀態(tài)；(3)對于G[Z]中形如U→Vx的每條產(chǎn)生式，畫一條從狀態(tài)V到狀態(tài)U的方向弧，弧上的標(biāo)記為x；(4)對于G[Z]中形如U→y的每條產(chǎn)生式，畫一條從初態(tài)S到狀態(tài)U的方向弧，弧上的標(biāo)記為y

例如：給出與正則文法G[Z]等價(jià)的狀態(tài)轉(zhuǎn)換圖G[Z]:

Z→U0|V1

U→Z1|1

V→Z0|0三、狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)（p42-46)例：識別一個(gè)簡單語言的所有單詞符號的狀態(tài)圖見圖3.3右線性文法狀態(tài)圖的識別過程，是為串w建立

一個(gè)推導(dǎo)Sw的過程。舉例說明；?左線性文法狀態(tài)圖的識別過程，是從串w出發(fā)的歸約過程，最后歸約為開始符號S（終態(tài)）。舉例說明；*3.3.1正規(guī)式和正規(guī)集為了識別正則語言，我們引入了狀態(tài)轉(zhuǎn)換圖和有限自動機(jī)，有限自動機(jī)所接受的語言正是正則文法產(chǎn)生的語言(正則語言)，程序設(shè)計(jì)語言中的單詞也大多是由正則文法產(chǎn)生的。作為單詞的語法除了用正則文法描述外，我們還可以用一種更有效的工具——正規(guī)式加以描述。

3.3正規(guī)表達(dá)式與有限自動機(jī)正規(guī)式和正規(guī)集的定義多數(shù)程序設(shè)計(jì)語言的單詞的語法都能用正規(guī)文法來表示。即文法G=(VN,VT,S,Z)中的規(guī)則P都有下述形式：A→aB或A→a，其中A,B∈VN，a∈VT。實(shí)際上，正規(guī)文法所描述的是字母表Σ上的一些特殊子集，稱為正規(guī)集。例如，標(biāo)識符可用下述規(guī)則描述：

<標(biāo)識符>→l|l<字母數(shù)字>

<字母數(shù)字>→l|d|l<字母數(shù)字>|d<字母數(shù)字>

其中l(wèi)表示a～z中的任何一英文字母，d表示0～9中的任一數(shù)字。從中我們可以知道標(biāo)識符是由一個(gè)字母之后跟隨若干個(gè)字母或數(shù)字組成。正規(guī)式也稱正則表達(dá)式，是用于描述單詞的另外一個(gè)工具，也是表示正規(guī)集的工具。下面我們給出正規(guī)式和它所表示的正規(guī)集的遞歸定義：P46

設(shè)有字母表為Σ，(1)ε和ф是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和ф;(2)若a∈Σ，則a是Σ上的正規(guī)式，它所表示的正規(guī)集為{a};(3)若e1和e2都是Σ上的正規(guī)式，且它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么：

(e1)

是正規(guī)式，表示的正規(guī)集為L(e1)；

e1|e2

是正規(guī)式，表示的正規(guī)集為L(e1)∪L(e2)；

e1·e2

是正規(guī)式，表示的正規(guī)集為L(e1)L(e2)；

e1*

是正規(guī)式，表示的正規(guī)集為(L(e1))*。(4)僅由有限次使用上述三步驟而定義的表達(dá)式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的字集(符號串集合)才是Σ上的正規(guī)集。其中:“|”讀為“或”；“·”讀為“連接”；“*”讀為“閉包”(即，任意有限次的自重復(fù)連接)。算符的優(yōu)先級為先“*”，再“·”最后“|”,都是左結(jié)合的，它們滿足結(jié)合律，規(guī)定了算符的優(yōu)先級后，可以省去一些不必要的括號:例如，正規(guī)式(a)|((b)*(c))可以表示成a|b*c，它所表示的正規(guī)集為：串a(chǎn)或者是零個(gè)或多個(gè)b后跟隨一個(gè)c例如：令Σ={a,b},Σ上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：

正規(guī)式正規(guī)集

a|b{a,b}

(a|b)(a|b){aa,ab,ba,bb}

a*0個(gè)或多個(gè)a的串所組成的集合

(a|b)*{a,b}*即a和b所能構(gòu)成的所有串的集合

exP47想一想：正規(guī)式(a*b*)*所對應(yīng)的正規(guī)集是什么例如：令Σ={d,e,+,,}，其中d為0～9中的數(shù)字，問：Σ上的正規(guī)式

d*(.dd*|ε)(e(+|-|ε)dd*|ε)表示的語言是什么？它所表示的語言(正規(guī)集)為無符號數(shù)。如果兩個(gè)正規(guī)式r和s表示同樣的正規(guī)集，我們稱兩個(gè)正規(guī)式r和s等價(jià)，寫作r=s。例如，若Σ={a,b}，則它上面的正規(guī)式a|b和b|a表示的正規(guī)集都是{a,b}，因此是等價(jià)的正規(guī)式。而對某個(gè)正規(guī)式來說，可以對其進(jìn)行變換并使它表示的正規(guī)集不變，這樣的變換稱為等價(jià)變換，在等價(jià)變換的過程中，正規(guī)式服從以下代數(shù)定律：設(shè)r，s，t為正規(guī)式，則:1．r|s=s|r“|”運(yùn)算滿足交換律2．r|(s|t)=(r|s)|t“|”運(yùn)算的可結(jié)合律3．(rs)t=r(st)“連接”運(yùn)算的可結(jié)合律4．r(s|t)=rs|rt(s|t)r=sr|tr

分配律5．r=rrε=r

ε是“連接”的恒等元素6．r*=(r|)*

ε和*的關(guān)系

7．(r*)*=r*

*是冪等的

3.3.2有限自動機(jī)正則文法可以用狀態(tài)轉(zhuǎn)換圖非形式的進(jìn)行表示，這就表明正則文法所對應(yīng)的語言(正則語言)可以用狀態(tài)轉(zhuǎn)換圖來接受(識別)。我們將看到，有限自動機(jī)正是對狀態(tài)轉(zhuǎn)換圖進(jìn)一步形式化的結(jié)果，它對于掃描器的構(gòu)造，特別是掃描器自動生成將帶來很大的方便。確定的有限自動機(jī)(DeterministicFiniteAutomata)定義：一個(gè)確定有限自動機(jī)（DFA）M是一個(gè)五元組：

M=(S，Σ，f，S0，Z)，其中：(1)S是一個(gè)非空有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)，S即表示DFA中包含的所有狀態(tài)組成的集合；(2)Σ是一個(gè)有限的輸入字母表，它的每個(gè)元素稱為一個(gè)輸入字符，所以Σ也稱為輸入符號字母表；(3)f是轉(zhuǎn)換函數(shù)，它是從S×Σ到S的映象，即，如果f(ki,a)=kj(ki∈S,kj∈S，a∈Σ)就意味著，當(dāng)前狀態(tài)為ki，輸入字符為a時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)kj，kj成為新的當(dāng)前狀態(tài)，我們把kj稱為ki的一個(gè)后繼狀態(tài)；(4)S0∈S是唯一的一個(gè)初始狀態(tài)；(5)ZS，是終止?fàn)顟B(tài)(終態(tài))集合，終止?fàn)顟B(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。例如：為下圖所示的狀態(tài)圖構(gòu)造確定的有限自動機(jī)。DFAM

=({S,U,V,Q},{a,b},f,S,{Q})其中：

{S,U,V,Q}為DFAM的狀態(tài)集K；{a,b}為輸入符號字母表；f定義為：

f(S,a)=Uf(S,b)=V

f(V,a)=Uf(V,b)=Q

f(U,a)=Qf(U,b)=V

f(Q,a)=Qf(Q,b)=QS為初始狀態(tài);{Q}為終止?fàn)顟B(tài)集合，即只有一個(gè)終態(tài)。事實(shí)上，狀態(tài)轉(zhuǎn)換圖是有限自動機(jī)的一種表示形式,假定DFAM含有m個(gè)狀態(tài)，n個(gè)輸入字符，那么這個(gè)狀態(tài)轉(zhuǎn)換圖含有m個(gè)狀態(tài)（結(jié)點(diǎn)），每個(gè)結(jié)點(diǎn)最多有n個(gè)弧射出，整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)(冠以“”)和若干個(gè)終態(tài)結(jié)點(diǎn)(用雙圈表示)，若有f(ki,a)=kj(ki∈K,kj∈K，a∈Σ)，則從狀態(tài)結(jié)點(diǎn)ki到狀態(tài)結(jié)點(diǎn)kj畫標(biāo)記為a的弧。

一個(gè)DFA還可以用一個(gè)矩陣(狀態(tài)矩陣）表示：矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)。例如：上例的DFA的矩陣表示如下：第一行表示初態(tài)

00

0

1相應(yīng)終態(tài)行在右端標(biāo)以1，

非終態(tài)標(biāo)以0

對于Σ*中的任何字符串α,若DFAM中存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的路,且這條路上所有弧的標(biāo)記連接成的字符串等于α，則稱α可以被DFAM所接受(識別)。若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空串ε可被M所接受（識別）。DFAM所能識別的所有字符串的全體（字的全體）稱為DFAM所能接受的語言，記為L(M)若α∈Σ*，f(S0,α)=P，其中S0為DFAM的初始狀態(tài)，P∈Z，Z為終態(tài)集。則稱字符串α可以被DFAM所接受(識別)為了加深對上述定義的理解，我們給出擴(kuò)充的轉(zhuǎn)換函數(shù)的定義：f(q,ε)=q，其中q∈S，即q為任意狀態(tài)；f(q,Tα)=f(f(q,T),α),其中T∈Σ,α∈Σ*。

舉例：試證baab可被下面的DFA所接受。因?yàn)椋篺(S,baab)

=f(f(S,b),aab)

=f(V,aab)

=f(f(V,a),ab)

=f(U,ab)

=f(f(U,a),b)

=f(Q,b)

=Q

Q屬于終態(tài)，得證

可以看出：這個(gè)定義使得轉(zhuǎn)換函數(shù)的定義域從原來的S×Σ擴(kuò)充到S×Σ*上，即f成為從S×Σ*到

S的映象。DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:S×Σ→S是一個(gè)單值函數(shù)，也就是說對任何狀態(tài)k∈S,和輸入符號a∈Σ，f(k,a)唯一地確定了下一個(gè)狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個(gè)輸入字符，那么任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符進(jìn)行標(biāo)記。非確定的有限自動機(jī)(NondeterministicFiniteAutomata)一個(gè)非確定的有限自動機(jī)(NFA)M是一個(gè)五元組：

M=(S，Σ，f，S0，F(xiàn))，其中(1)S是一個(gè)非空有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)；(2)Σ是一個(gè)有限的輸入字母表，它的每個(gè)元素稱為一個(gè)輸入字符;

(3)f是轉(zhuǎn)換函數(shù)，它是從S×Σ*到2S的映象

(4)S0S是一個(gè)非空的初始狀態(tài)集；

(5)F

S，是終止?fàn)顟B(tài)集合

與DFA相同與DFA相同對某個(gè)輸入，可以到達(dá)多個(gè)狀態(tài)初態(tài)可以是多個(gè)與DFA相同所以，一個(gè)含有m個(gè)狀態(tài)和n個(gè)輸入字符的NFA可表示成如下的一張狀態(tài)轉(zhuǎn)換圖：這張狀態(tài)轉(zhuǎn)換圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可射出若干條箭弧與別的結(jié)點(diǎn)相連接，每條弧用Σ*中的一個(gè)串作標(biāo)記(可相同)，整個(gè)圖至少含有一個(gè)初態(tài)結(jié)點(diǎn)以及若干個(gè)終態(tài)結(jié)點(diǎn)。例如：一個(gè)NFAM=({0,1,2,3,4},{a,b},f,{0},{2,4})f(0,a)={0,3}f(0,b)={0,1}

f(1,b)={2}f(2,a)={2}

f(2,b)={2}f(3,a)={4}

f(4,a)={4}f(4,b)={4}

其中：那么，它的狀態(tài)轉(zhuǎn)換圖表示為：它的矩陣表示為：跟DFA有相似的結(jié)論：對于Σ*中的任何一個(gè)串α，若NFAM中存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的路，且這條路上所有弧的標(biāo)記依次連接成的串（不理睬那些標(biāo)記為ε的?。┑扔讦?，則稱α可以被NFAM所接受（識別）。若M的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的ε路，那么空串ε可被M所接受（識別）?？梢钥闯?，DFA是NFA的一個(gè)特例。并且可以證明，對于每個(gè)NFAM存在一個(gè)DFAM’使得L(M)=L(M’)。對于任何兩個(gè)有限自動機(jī)M和M’，如果L(M)=L(M’)，則稱M與M’是等價(jià)的。非確定的有限自動機(jī)的確定化將有限自動機(jī)用計(jì)算機(jī)程序表示出來，就能實(shí)現(xiàn)對詞法的分析；在前例所示的NFA中，在狀態(tài)0下，面對輸入a有兩個(gè)轉(zhuǎn)換，也就是可能進(jìn)入狀態(tài)0或3，而輸入b也有兩個(gè)轉(zhuǎn)換。這些轉(zhuǎn)換函數(shù)多值的情況，使得很難用計(jì)算機(jī)程序模擬NFA。前面說過：“對于每個(gè)NFAM存在一個(gè)DFAM’使得L(M)=L(M’)”就是說：設(shè)L為一個(gè)由非確定有限自動機(jī)接受的集合（語言），則存在一個(gè)接受L的確定的有限自動機(jī)。下面給出從NFA構(gòu)造識別同樣語言的DFA的算法。子集構(gòu)造法：——將NFA的一個(gè)狀態(tài)子集在DFA中用一個(gè)狀態(tài)表示出來。從NFA的矩陣表示中可以看出，表項(xiàng)通常是一個(gè)狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)。NFA到相應(yīng)的DFA的構(gòu)造的基本想法是讓DFA的每個(gè)狀態(tài)代表NFA的一個(gè)狀態(tài)集合。即在轉(zhuǎn)換后的DFA中，使用它的狀態(tài)去記錄在NFA中讀入一個(gè)輸入符號后可能到達(dá)的所有狀態(tài)。換句話說，在得到的DFA中若輸入符號串a(chǎn)1a2…an后，到達(dá)某個(gè)狀態(tài)，那么該狀態(tài)表示對應(yīng)的NFA的狀態(tài)集的一個(gè)子集，這個(gè)子集是NFA在輸入符號串a(chǎn)1a2…an后可以到達(dá)的那些狀態(tài)組成的集合。首先介紹兩個(gè)重要運(yùn)算：(1)狀態(tài)集的ε-閉包：狀態(tài)集I中的任何狀態(tài)s經(jīng)任意條ε弧而能到達(dá)的所有狀態(tài)的集合，定義為狀態(tài)集I的ε-閉包，表示為ε-closure(I)。(2)狀態(tài)集的a弧轉(zhuǎn)換：狀態(tài)集I中的任何狀態(tài)s經(jīng)過一條a弧而能到達(dá)的所有狀態(tài)的集合，定義為狀態(tài)集I的a弧轉(zhuǎn)換，表示為move(I,a)。對于任意NFAM=(K，Σ，f，S，F(xiàn))，IK，a∈Σ不妨設(shè)I={s1,s2,…sj}，則move(I,a)=f(s1,a)∪f(s2,a)∪…∪f(sj,a)(3)狀態(tài)集的a弧轉(zhuǎn)換的閉包IaIa=ε-closure(move(I,a))例如：有下圖所示的NFA,我以它為例來說明以上兩個(gè)運(yùn)算。對于I={0}，ε-closure(I)=ε-closure({0})={0,1,2,4,7}；令A(yù)={0,1,2,4,7}同理若I={2,3},ε-closure(I)=ε-closure({2,3})={1,2,3,4,6,7}；則move(A,a)={3,8}move(A,b)={5}同樣可以求出其它狀態(tài)集的ε-閉包和a弧轉(zhuǎn)換?NFA確定化為DFA的子集法：P50ex3.3εP49，圖3.6非確定優(yōu)先自動機(jī)補(bǔ)充例題注：幻燈片p34-38不講，這部分按書例3.3上講。算法：有了以上所述兩個(gè)運(yùn)算，我們就可以構(gòu)造NFAN的狀態(tài)集K的子集從而與DFAM的狀態(tài)對應(yīng)，即構(gòu)造若干個(gè)狀態(tài)集T1,T2,…,Ti，且Ti

K，這樣就可以構(gòu)成由若干個(gè)狀態(tài)集

組成的子集族C，C=(T1,T2,…,Ti)，具體如下：(1)首先，令T=ε-closure(K0)作為C中的唯一成員(開始以前C中為空)，并且它是未標(biāo)記的，其中K0為NFAN的初態(tài)集(2)While（C中存在尚未標(biāo)記的子集T）do

begin

標(biāo)記T；

for

每個(gè)輸入字母ado

begin

U:=ε-closure(move(T,a))；//顯然U是一個(gè)狀態(tài)集

if（U不在C中）then

將U作為未標(biāo)記的子集加入C中；

end；

end；

例:為下面的NFAN的狀態(tài)集K構(gòu)造狀態(tài)子集族C。在此NFAN中，狀態(tài)集K={0,1,2,3,4,5,6,7,8,9,10}，初態(tài)集K0={0}，開始前C不包含任何狀態(tài)集(1)T0=ε-closure(K0)=ε-closure({0})={0,1,2,4,7}，C=(T0)(2)C=(T0)T1=ε-closure(move(T0,a))={1,2,3,4,6,7,8}

C=(T0,T1)T2=ε-closure(move(T0,b))={1,2,4,5,6,7}

C=(T0,T1,T2)(3)C=(T0,T1,T2)T3=ε-closure(move(T1,a))={1,2,3,4,6,7,8}=T1舍棄T3=ε-closure(move(T1,b))={1,2,4,5,6,7,9}

C=(T0,T1,T2,T3)(4)C=(T0,T1,T2,T3)T4=ε-closure(move(T2,a))={1,2,3,4,6,7,8}=T1

舍棄T4=ε-closure(move(T2,b))={1,2,4,5,6,7}=T2舍棄(5)C=(T0,T1,T2,T3)T4=ε-closure(move(T3,a))={1,2,3,4,6,7,8}=T1舍棄T4=ε-closure(move(T3,b))={1,2,4,5,6,7,10}

C=(T0,T1,T2,T3,T4)(6)C=(T0,T1,T2,T3,T4)T5=ε-closure(move(T4,a))={1,2,3,4,6,7,8}=T1舍棄T5=ε-closure(move(T4,b))={1,2,4,5,6,7}=T2舍棄C中所有狀態(tài)子集都已經(jīng)被標(biāo)記，算法結(jié)束子集族C由5個(gè)子集組成：T0={0,1,2,4,7}

T1={1,2,3,4,6,7,8}

T2={1,2,4,5,6,7}

T3={1,2,4,5,6,7,9}

T4={1,2,4,5,6,7,10}由NFA構(gòu)造DFA的方法:假設(shè)NFAN=（K，Σ，f，K0，Kt），我們可以構(gòu)造一個(gè)DFAM={S，Σ，D，S0，St}，使得L(M)=L(N)：(1)M的狀態(tài)集S由K的一些子集組成。我們用[S1,S2,…,Sj]表示S的一個(gè)元素，其中S1,S2,…,Sj是K中的狀態(tài)，NFA的若干個(gè)狀態(tài)構(gòu)成DFA的一個(gè)狀態(tài)；(2)M和N的輸入字母表是相同的，即都是Σ；

(3)轉(zhuǎn)換函數(shù)D是這樣定義的：D([S1,S2,…,Sj],a)=[R1,R2,…,Ri]

其中:[R1,R2,…,Ri]=ε-closure(move([S1,S2,…,Sj],a))

(4)S0=ε-closure(K0)，即M的開始狀態(tài)等于N的初態(tài)集的ε-閉包；(5)St={[Sj,Sk,…,Se]，其中[Sj,Sk,…,Se]∈S，且[Sj,Sk,…,Se]∩Kt≠

ф}例如：為下面的NFAN構(gòu)造DFAM并使L(M)=L(N)(1)由子集構(gòu)造法得狀態(tài)集S={[T0]，[T1]，[T2]，[T3]，[T4]}(2)字母表Σ={a,b}

(4)初態(tài)S0=ε-closure(K0)

=ε-closure({0})={0,1,2,4,7}=[T0](5)終態(tài)集{[T4]}，因?yàn)橹挥衃T4]包含NFAN的終態(tài)10

(T4={1,2,4,5,6,7,10}

)(3)轉(zhuǎn)換函數(shù)D其中轉(zhuǎn)換函數(shù)D如下：

D([T0]，a)=[T1](ε-closure(move(T0,a))={1,2,3,4,6,7,8}=T1)[R1,R2,…,Ri]=ε-closure(move([S1,S2,…,Sj],a))D([T0]，b)=[T2](ε-closure(move(T0,b))={1,2,4,5,6,7}=T2)D([T1]，a)=[T1](ε-closure(move(T1,a))={1,2,3,4,6,7,8}=T1)D([T1]，b)=[T3](ε-closure(move(T1,b))={1,2,4,5,6,7,9}=T3)D([T2]，a)=[T1](ε-closure(move(T2,a))={1,2,3,4,6,7,8}=T1)D([T2]，b)=[T2](ε-closure(move(T2,b))={1,2,4,5,6,7}=T2)D([T3]，a)=[T1](ε-closure(move(T3,a))={1,2,3,4,6,7,8}=T1)D([T3]，b)=[T4](ε-closure(move(T3,b))={1,2,4,5,6,7,10}=T4)D([T4]，a)=[T1](ε-closure(move(T4,a))={1,2,3,4,6,7,8}=T1)D([T4]，b)=[T2](ε-closure(move(T4,b))={1,2,4,5,6,7}=T2)將[T0]，[T1]，[T2]，[T3]，[T4]用A，B，C，D，E表示3.3.6確定的有限自動機(jī)的最簡化(最小化)對任意一個(gè)DFAM構(gòu)造另一個(gè)DFAM’，使L(M)=L(M’)，并且M’的狀態(tài)個(gè)數(shù)不多于M的狀態(tài)個(gè)數(shù)。首先我們介紹幾個(gè)有關(guān)的概念：(1)多余狀態(tài):對于一個(gè)狀態(tài)Si，若從開始狀態(tài)出發(fā)，不可能到達(dá)該狀態(tài)Si，則Si為多余(無用)狀態(tài)。S1，S5，S6為多余狀態(tài)(2)死狀態(tài):對于一個(gè)狀態(tài)Si，對任意輸入符號a，若轉(zhuǎn)到它本身后，不可能從它到達(dá)終止?fàn)顟B(tài)，則稱Si為死狀態(tài)。多余狀態(tài)和死狀態(tài)又稱為無關(guān)狀態(tài)。b(3)等價(jià)狀態(tài):

若Si為自動機(jī)的一個(gè)狀態(tài)，我們把從Si出發(fā)能導(dǎo)出的所有符號串集合記為L(Si)

設(shè)有兩個(gè)狀態(tài)Si和Sj,若有L(Si)=L(Sj),則稱Si和Sj是等價(jià)狀態(tài)。從S1和S2能導(dǎo)出相同的符號串集合：L(S1)=L(S2)=，所以S1和S2等價(jià)(4)可區(qū)別狀態(tài):自動機(jī)中兩個(gè)狀態(tài)Si和Sj，如果它們不等價(jià)，則稱它們是可區(qū)別的。(5)兩個(gè)狀態(tài)(Si和Sj)等價(jià)的判斷條件:

①狀態(tài)Si和Sj必須同時(shí)為終止?fàn)顟B(tài)或同時(shí)為非終止?fàn)顟B(tài)。即終止?fàn)顟B(tài)和非終止?fàn)顟B(tài)是可區(qū)別的；如，S0，S1，S2肯定與S3不等價(jià)②狀態(tài)Si和Sj對于任意輸入符號a∈Σ，必須轉(zhuǎn)到等價(jià)的狀態(tài)里，否則Si和Sj是可區(qū)別的。因f(S0,b)=S2，f(S2,b)=S3，而S2和S3不等價(jià)，故S0和S2也不等價(jià)DFA的化簡算法：對于DFAM=(S,Σ,f,S0,Z)

(1)首先將DFA的狀態(tài)集進(jìn)行初始化，分成Π=(Z,S-Z);(2)用下面的過程對Π構(gòu)造新的劃分Πnew

for(Π中每個(gè)組G)do//每個(gè)組都是一個(gè)狀態(tài)集

begin把G劃分成小組，G中的任意兩個(gè)狀態(tài)Si和Sj在同一組中，當(dāng)且僅當(dāng)對于Σ中任意輸入符號a，Si和Sj的a轉(zhuǎn)換是到同一組中，move(Si,a)∈Gi，move(Sj,a)∈Gi。這樣，只要Si和Sj的a轉(zhuǎn)換是到不同的組中，則說明Si和Sj是可區(qū)別的，可進(jìn)行劃分。

在Π

new中用剛完成的對G的劃分代替原來的G。end;

Π:=Π

new；(3)重復(fù)執(zhí)行(2)，直到Π中每個(gè)狀態(tài)集不能再劃分(Π

new=Π)為止;(4)合并等價(jià)狀態(tài),在每個(gè)G中，取任意狀態(tài)作為代表，刪去其它狀態(tài);(5)刪去無關(guān)狀態(tài)，從其它狀態(tài)到無關(guān)狀態(tài)的轉(zhuǎn)換都成為無定義。例題：將下圖所示的DFAM最小化(P58)①首次劃分:Π0=({1,2,3,4},{5,6,7})

②在G={1,2,3,4}中:

f(1,a)=6，f(2,a)=7(轉(zhuǎn)向終態(tài))；f(3,a)=1,f(4,a)=4(轉(zhuǎn)向非終態(tài))，故{1,2}和{3,4}是可區(qū)別的，得Π1=({1,2}，{3,4}，{5,6,7})；

③在G={1,2}中，f(1,a)=6,f(2,a)=7(轉(zhuǎn)向終態(tài)子集),而f(1,b)=f(2,b)=3,所以不可區(qū)別，不再進(jìn)行劃分；

④考察G={3,4}，f(3,a)=1,f(4,a)=4,可見它們轉(zhuǎn)向Π1的不同組，故得新的劃分Π2=({1,2},{3,},{4}{5,6,7})；

⑤對{1,2}重新進(jìn)行考察，發(fā)現(xiàn)它不能進(jìn)行劃分，而{3}和{4}已經(jīng)最小也不能劃分了；

⑥考察G={5,6,7}，因f(5,b)轉(zhuǎn)向{3}，而f(6,b)和f(7,b)轉(zhuǎn)向{1,2}，可得新劃分

Π3=({1,2},{3},{4},{5},{6,7})；

⑦進(jìn)一步進(jìn)行考察，可以發(fā)現(xiàn)每個(gè)子集都不能再劃分了；

⑧消去等價(jià)狀態(tài)：{1,2}用1表示，{6,7}用6表示，得到得新DFAM’如右圖所示⑨去掉無關(guān)狀態(tài)，因DFAM’中沒有無關(guān)狀態(tài)，所以右圖即為最后結(jié)果。

補(bǔ)充例題正規(guī)式與有限自動機(jī)

正規(guī)式是單詞的一種描述工具，而有限自動機(jī)是單詞的識別裝置，正規(guī)式和有限自動機(jī)之間可以相互轉(zhuǎn)換，也就是說它們之間存在著等價(jià)性，主要表現(xiàn)在以下兩個(gè)方面：(1)對于Σ上的NFAM，可以構(gòu)造一個(gè)Σ上的正規(guī)式R，使得：L(R)=L(M)；(2)對于Σ上的每個(gè)正規(guī)式R，可以構(gòu)造一個(gè)Σ上的NFAM，使得：L(M)=L(R)。

NFAM轉(zhuǎn)化為正規(guī)式R：為了實(shí)現(xiàn)為Σ上的NFAM構(gòu)造一個(gè)等價(jià)的正規(guī)式R，我們把狀態(tài)轉(zhuǎn)換圖的概念拓廣，使?fàn)顟B(tài)轉(zhuǎn)換圖的每條弧可以用一個(gè)正規(guī)式作標(biāo)記，具體如下：(1)在NFAM的狀態(tài)轉(zhuǎn)換圖上加進(jìn)兩個(gè)結(jié)點(diǎn)x、y，從x結(jié)點(diǎn)用ε弧連接到M的所有初態(tài)結(jié)點(diǎn)，同時(shí)從M的所有終態(tài)結(jié)點(diǎn)用ε弧連接到y(tǒng)結(jié)點(diǎn)，形成一個(gè)與M等價(jià)的NFAM’，M’只有一個(gè)初態(tài)結(jié)點(diǎn)x，一個(gè)終態(tài)結(jié)點(diǎn)y;(2)逐步消去M’的結(jié)點(diǎn)，直至只剩下x和y兩個(gè)結(jié)點(diǎn)為止。在消結(jié)點(diǎn)過程中，逐步使用正規(guī)式來標(biāo)記弧。使用的規(guī)則如下：按以上規(guī)則消結(jié)直到最后成為：xyR例:對下圖所示的NFAM求正規(guī)式R，使L(R)=L(M)。(1)對NFAM的狀態(tài)轉(zhuǎn)換圖加上x和y兩個(gè)結(jié)點(diǎn)，形成下圖所示的NFAM’消去結(jié)點(diǎn)1和3后NFAM’如圖所示消去結(jié)點(diǎn)2和4后NFAM’如圖所示正規(guī)式R轉(zhuǎn)化為NFAM

：在這個(gè)方法中按正規(guī)式的語法結(jié)構(gòu)指引構(gòu)造過程，將正規(guī)式分解為一系列子表達(dá)式，然后將子表達(dá)式對應(yīng)的NFA依次連接而成，構(gòu)造規(guī)則如下：1.(a)對正規(guī)式ф，對應(yīng)的NFA為：(b)對正規(guī)式ε，對應(yīng)的NFA為：(c)對正規(guī)式a，對應(yīng)的NFA為：2.正規(guī)式R，首先表示成拓廣狀態(tài)轉(zhuǎn)換圖：例如：設(shè)有正規(guī)式R=(a|b)*abb，試構(gòu)造NFAN，使得L(N)=L(R)(不講）正規(guī)式與正規(guī)文法一個(gè)正規(guī)（正則）語言可以由正規(guī)（正則）文法定義，也可以由正規(guī)式定義，對任意一個(gè)正規(guī)文法，存在一個(gè)定義同一語言的正規(guī)式；反之，對每個(gè)正規(guī)式，存在一個(gè)生成同一語言的正規(guī)文法，正規(guī)文法和正規(guī)式之間可以相互轉(zhuǎn)換。正規(guī)式轉(zhuǎn)換成正規(guī)文法：將Σ上的一個(gè)正規(guī)式R轉(zhuǎn)換成文法G=(VN，VT，S，P)的方法如下：(1)VT=Σ；(2)對于正規(guī)式R，選擇一符號S，SVN，生成產(chǎn)生式S→R，并將S定為文法G的開始符號；(3)對已有的產(chǎn)生式，按以下原則進(jìn)行變換，直到每個(gè)產(chǎn)生式最多含有一個(gè)終結(jié)符號為止：設(shè)x,y是正規(guī)式，則①對于形如A→xy的產(chǎn)生式，重寫成：A→xB，B→y兩產(chǎn)生式，其中，B∈VN；②對于形如A→x|y的產(chǎn)生式，重寫成：A→x，A→y兩產(chǎn)生式；③對于形如A→x*y的產(chǎn)生式，重寫成：A→xB，A→y，B→xB，B→y四個(gè)產(chǎn)生式，其中，B∈VN；(4)按(2)和(3)所確定的產(chǎn)生式組成文法的產(chǎn)生式集合P，而(2)和(3)中所選定的非終結(jié)符號組成文法的非終結(jié)符號集VN

例如：將正規(guī)式R=a(a|b)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法G，并使L(G)=L(R)(1)根據(jù)正規(guī)式R可以確定Σ={a，b}，所以VT={a，b}；(2)S→a(a|b)*，S∈VN；(3)S→a(a|b)*符合A→xy的形式，分解成：S→aAA→(a|b)*

(4)對A→(a|b)*

再利用規(guī)則分解為：A→(a|b)BA→εB→(a|b)BB→ε形如A→x*y的產(chǎn)生式，重寫成：A→xB，A→y，B→xB，B→y整理得變換結(jié)果G[S]：S→aA

A→aB

A→bB

A→ε

B→aB

B→bB

B→ε可以看出，VN={S，A，B}。正規(guī)文法轉(zhuǎn)換成正規(guī)式：將正規(guī)文法G=(VN，VT，S，P)轉(zhuǎn)換成正規(guī)式R，并使L(R)=L(G)的方法如下：使用轉(zhuǎn)換規(guī)則合并文法的產(chǎn)生式，最后只剩下一個(gè)開始符號定義的產(chǎn)生式，并且產(chǎn)生式的右部不含非終結(jié)符號。轉(zhuǎn)換規(guī)則如下：(1)若有產(chǎn)生式A→xBB→y則轉(zhuǎn)換成正規(guī)式：A=xy(2)若有產(chǎn)生式A→xA|y則轉(zhuǎn)換成正規(guī)式：A=x*y(3)若有產(chǎn)生式A→xA→y則轉(zhuǎn)換成正規(guī)式：A=x|y例如：設(shè)有文法G[S]①S→aA②S→a③A→aA④A→dA⑤A→a⑥A→d試求正規(guī)式R，使L(R)=L(G[S])(1)產(chǎn)生式①和②得正規(guī)式：S=aA|a

(2)由產(chǎn)生式③、④、⑤、⑥得正規(guī)式：A=aA|dA|a|d

=(a|d)A|(a|d)=(a|d)*(a|d)將A代入S得：S=a((a|d)*(a|d))|a

=a((a|d)*(a|d)|ε)A={a,b},A*A=?=a((a|d)+|ε)

A+{}=?=a(a|d)*

3.4詞法分析器的自動產(chǎn)生由狀態(tài)圖生成掃描器:

通過狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析程序

設(shè)有以下用BNF表示的關(guān)于某語言的單詞的文法：<標(biāo)識符>→字母|<標(biāo)識符>字母|<標(biāo)識符>數(shù)字<無符號整數(shù)>→數(shù)字|<無符號整數(shù)>數(shù)字<單分隔符號>→+|-|*|/|（|）|：<雙分隔符號>→<斜豎>*|<冒號>=<斜豎>→/<冒號>→：實(shí)際上，無論用正規(guī)文法還是用正規(guī)式來表示單詞，我們都可以得到與之對應(yīng)的狀態(tài)轉(zhuǎn)換圖，即能夠識別單詞的有限自動機(jī)，以上文法對應(yīng)的狀態(tài)轉(zhuǎn)換圖如下：設(shè)有以下某語言的單詞的文法：<標(biāo)識符>→字母|<標(biāo)識符>字母|<標(biāo)識符>數(shù)字<無符號整數(shù)>→數(shù)字|<無符號整數(shù)>數(shù)字<單分隔符號>→+|-|*|/|（|）|：<雙分隔符號>→<斜豎>*|<冒號>=<斜豎>→/<冒號>→：為了設(shè)計(jì)出一個(gè)能夠識別各類單詞的掃描器，可把上述各狀態(tài)轉(zhuǎn)換圖合并為一個(gè)狀態(tài)轉(zhuǎn)換圖：一個(gè)共同的入口一個(gè)共同的出口加上出錯(cuò)狀態(tài)等處理從開始狀態(tài)出發(fā)，對于不同的輸入字符，所經(jīng)過的路徑不同，但只要能夠到達(dá)終態(tài)，所經(jīng)過的弧上的標(biāo)記組成的串，都是該語言的單詞。狀態(tài)轉(zhuǎn)換圖可以理解為詞法分析程序的一張?jiān)硇钥驁D。只要在此基礎(chǔ)上，加上語義處理等方面的工作，就可以形成掃描器的算法框圖:Class存放類別碼，用Token表示單詞值“讀字符”子程序?qū)⑾乱粋€(gè)字符讀到工作單元Char中P=1時(shí)為真讀P=0時(shí)為假讀“組合標(biāo)識符”子程序，把該標(biāo)識符組合完畢，并將單詞值送Token“查保留字表”子程序通過查預(yù)先準(zhǔn)備好的保留字表，判明該單詞是否為保留字“組數(shù)”子程序，把該無符號整數(shù)組合完畢，并將單詞值送Token分類原則：保留字和分隔符號采用一字(符)一類的分類方法，所有標(biāo)識符作為一類，取類型碼為1；所有無符號整數(shù)作為一類，取類型碼為2

掃描器的自動生成把一個(gè)正規(guī)式編譯（或稱轉(zhuǎn)換）為一個(gè)NFA進(jìn)而轉(zhuǎn)換為DFA，而這個(gè)NFA或DFA正是識別該正規(guī)式所表示的語言(正規(guī)集)的識別器?；谶@種方法可以構(gòu)造出詞法分析程序(掃描器)，這就是掃描器的自動生成原理。LEX是一個(gè)廣泛使用的工具，它用于構(gòu)造各種各樣語言的詞法分析程序。LEX編譯系統(tǒng)的作用如圖:LEX源程序是用一種面向問題的語言寫成的，這個(gè)語言的核心是正規(guī)式，正規(guī)式用于描述輸入串的詞法結(jié)構(gòu)LEX程序由三部分組成：說明部分、轉(zhuǎn)換規(guī)則和輔助過程，它們之間用%%做間隔，其一般格式為：{輔助定義部分}%%{識別規(guī)則部分}%%{用戶子程序部分}(1)輔助定義部分包括變量的說明、常量說明和正規(guī)式定義，所謂正規(guī)式定義是形如如下形式的一系列定義：d1→r1d2→r2…dn→rn其中，di是代表這個(gè)正規(guī)式的簡名，ri是Σ∪{d1,d2,…,di-1}上的正規(guī)式，即在ri中允許出現(xiàn)字母表Σ中的字符和前面定義的簡名（d1,d2,…,di-1）例如，標(biāo)識符（ident）可表示為：letter→A|B|…|Zdigit→0|1|…|9ident→letter(letter|digit)*(2)識別規(guī)則部分是LEX源程序的核心。它是一張表，左邊一列是正規(guī)式，右邊一列是相應(yīng)的動作。P1{action1}P2{action2}…Pm{actionm}其中，每個(gè)Pi是Σ∪{d1,d2,…,di-1}上的正規(guī)式，稱之為詞形integerprintf(“foundkeywordINT”)；(3)用戶子程序部分是在action的執(zhí)行過程中用到的過程或函數(shù)IDENT[a－zA－Z][a－zA－Z0－9]*

//輔助定義部分，定義名字IDENT和NUMBERNUMBER[0－9][0－9]*

//各代表一個(gè)正規(guī)式，[]、－和*為正規(guī)式運(yùn)算符，%{//[]表示字符的集合，－表示范圍，*表示閉包運(yùn)算。#include<stdio.h>#include“code.H”#include“symbol.H”//%{與%}之間的部分為直接照抄的代碼部分。#include“y.tab.H”externintlevel;intcc=0;%}說明部分

%%

""{cc++;}轉(zhuǎn)換規(guī)則

"\t"{tablize();}//將cc調(diào)整到tab的位置"\n"{cc=0;line_copy();}//換行"<"{cc++;returnLT;}">"{cc++;returnGT;}"="{cc++;returnEQ;}"#"{cc++ireturnNE;}","{cc++;returnColon;}一個(gè)LEX源程序片段："."{cc++;returnPeriod;}"("{cc++;returnLparen;}")"{cc++;returnRparen;}"<="{cc++;cc++;returnLE;}">="{cc++;cc++;returnGE;}":="{cc++;cc++;returnASGN;}";"{cc++;