編譯原理-第三章

第三章詞法分析3.1詞法分析器的設計詞法分析的主要工作:

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

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

(2)編譯程序的效率會改進；(3)增強編譯程序的可移植性。

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

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

面字符為function

，還要看是否結束，即后面字符是什么

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

字)，而需要再向前讀一個字符，確定后再回來處理。在判別標識符example過程中，當讀到字符e時，雖然前

面字符為example，為了判別下一個字符是否是該標識符

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

以不能馬上處理，需要再向前讀一個字符。Ex:p40有時，為了判別讀進字

符所組成的單詞的類別，

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

保留字if(3，‘if’)

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

等號=(4，‘=’)

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

保留字then(3，‘then’)

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

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

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

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

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

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

用表示終止狀態(tài)。

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

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

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

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

S→bB

S→ε

A→aB

A→bA

B→aS

B→bA

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

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

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

Z→U0|V1

U→Z1|1

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

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

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

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

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

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

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

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

a|b{a,b}

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

a*0個或多個a的串所組成的集合

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

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

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

分配律5．r=rrε=r

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

ε和*的關系

7．(r*)*=r*

*是冪等的

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

M=(S，Σ，f，S0，Z)，其中：(1)S是一個非空有限集，它的每個元素稱為一個狀態(tài)，S即表示DFA中包含的所有狀態(tài)組成的集合；(2)Σ是一個有限的輸入字母表，它的每個元素稱為一個輸入字符，所以Σ也稱為輸入符號字母表；(3)f是轉換函數(shù)，它是從S×Σ到S的映象，即，如果f(ki,a)=kj(ki∈S,kj∈S，a∈Σ)就意味著，當前狀態(tài)為ki，輸入字符為a時，將轉換到下一個狀態(tài)kj，kj成為新的當前狀態(tài)，我們把kj稱為ki的一個后繼狀態(tài)；(4)S0∈S是唯一的一個初始狀態(tài)；(5)ZS，是終止狀態(tài)(終態(tài))集合，終止狀態(tài)也稱可接受狀態(tài)或結束狀態(tài)。例如：為下圖所示的狀態(tài)圖構造確定的有限自動機。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}為終止狀態(tài)集合，即只有一個終態(tài)。事實上，狀態(tài)轉換圖是有限自動機的一種表示形式,假定DFAM含有m個狀態(tài)，n個輸入字符，那么這個狀態(tài)轉換圖含有m個狀態(tài)（結點），每個結點最多有n個弧射出，整個圖含有唯一一個初態(tài)結點(冠以“”)和若干個終態(tài)結點(用雙圈表示)，若有f(ki,a)=kj(ki∈K,kj∈K，a∈Σ)，則從狀態(tài)結點ki到狀態(tài)結點kj畫標記為a的弧。

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

00

0

1相應終態(tài)行在右端標以1，

非終態(tài)標以0

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

舉例：試證baab可被下面的DFA所接受。因為：f(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)，得證

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

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

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

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

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

(5)F

S，是終止狀態(tài)集合

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

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

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

begin

標記T；

for

每個輸入字母ado

begin

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

if（U不在C中）then

將U作為未標記的子集加入C中；

end；

end；

例:為下面的NFAN的狀態(tài)集K構造狀態(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)子集都已經被標記，算法結束子集族C由5個子集組成：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構造DFA的方法:假設NFAN=（K，Σ，f，K0，Kt），我們可以構造一個DFAM={S，Σ，D，S0，St}，使得L(M)=L(N)：(1)M的狀態(tài)集S由K的一些子集組成。我們用[S1,S2,…,Sj]表示S的一個元素，其中S1,S2,…,Sj是K中的狀態(tài)，NFA的若干個狀態(tài)構成DFA的一個狀態(tài)；(2)M和N的輸入字母表是相同的，即都是Σ；

(3)轉換函數(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構造DFAM并使L(M)=L(N)(1)由子集構造法得狀態(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]}，因為只有[T4]包含NFAN的終態(tài)10

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

)(3)轉換函數(shù)D其中轉換函數(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確定的有限自動機的最簡化(最小化)對任意一個DFAM構造另一個DFAM’，使L(M)=L(M’)，并且M’的狀態(tài)個數(shù)不多于M的狀態(tài)個數(shù)。首先我們介紹幾個有關的概念：(1)多余狀態(tài):對于一個狀態(tài)Si，若從開始狀態(tài)出發(fā)，不可能到達該狀態(tài)Si，則Si為多余(無用)狀態(tài)。S1，S5，S6為多余狀態(tài)(2)死狀態(tài):對于一個狀態(tài)Si，對任意輸入符號a，若轉到它本身后，不可能從它到達終止狀態(tài)，則稱Si為死狀態(tài)。多余狀態(tài)和死狀態(tài)又稱為無關狀態(tài)。b(3)等價狀態(tài):

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

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

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

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

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

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

在Π

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

Π:=Π

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

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

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

f(1,a)=6，f(2,a)=7(轉向終態(tài))；f(3,a)=1,f(4,a)=4(轉向非終態(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(轉向終態(tài)子集),而f(1,b)=f(2,b)=3,所以不可區(qū)別，不再進行劃分；

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

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

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

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

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

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

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

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

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

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

例如：將正規(guī)式R=a(a|b)*轉換成相應的正規(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的產生式，重寫成：A→xB，A→y，B→xB，B→y整理得變換結果G[S]：S→aA

A→aB

A→bB

A→ε

B→aB

B→bB

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

(2)由產生式③、④、⑤、⑥得正規(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詞法分析器的自動產生由狀態(tài)圖生成掃描器:

通過狀態(tài)轉換圖構造詞法分析程序

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

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

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

%%

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

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