第03章 有限自動機和詞法分析

第03章有限自動機和詞法分析主要內容：詞法分析過程涉及的幾個問題詞法分析器的生成技術有限自動機正則表達式3.1詞法分析有關詞法分析器的幾個問題和處理方法：

1)詞法分析器的功能、分類

2)單詞的分類、Token表示

3)字符串、保留字的處理

4)空格符、制表符和換行符

5)復合型符號

6)括號類匹配預檢

7)詞法錯誤校正

8) 詞法分析獨立化的意義3.1.1詞法分析器的功能詞法分析器功能：讀源程序的字符序列，逐個拼出單詞,并構造相應的內部表示TOKEN。同時檢查源程序中的詞法錯誤。引入Token的原因：編譯程序總是用某種程序語言書寫的程序，語言的操作對象只能是該語言規(guī)定的各種數據。而編譯程序的操作對象是程序中的各種語法單位，因此，必須把它們表示成某種數據結構形式。

詞法分析器的兩種形式:CharList

獨立詞法分析器語法分析TokenList

附屬詞法分析器語法分析callTokenCharList3.1.2單詞的內部表示Token定義：Token表示最小的語義單位--單詞的信息。即：單詞內部表示的數據結構形式。單詞不是程序設計語言中的語法概念，是編譯程序中引進的一個概念。是最小的語義單位，不能分割。Token中需要記錄有關單詞的信息：單詞的類別碼(Token.class)：標識單詞的種類---詞法信息單詞的特征屬性（Token.seman，標識符名，符號表地址等）：---語義信息Token設計示例程序表示ASC∏Token.classToken.semanIf9666019666Then478656E602478656E6Begin26567696E60326567696E6End56E6460456E646+B205B2(820682單詞的分類:標識符：字母打頭的字母/數字串整常數：數字打頭的數字串實常數：整數.整數保留字：begin，end，var，read，write，integer，real符號：+，*，(，)，:，:=，;控制：(換行符）字符串：

標識符的語義信息的表示方法有兩種：

a字符數組法：字符串空間中的地址被表示為對偶地址（head,leng），如下圖所示：

b指針數組法：字符串空間中的地址用指針表示，如下圖所示：(4,3)(2,2)

x1z12名表“x1”“z12”heighteofageeofx1eofyeof0123保留字的處理：兩種識別保留字的方法：

1.建立保留字表：順序、散列、散列＋順序2.拼寫的同時進行判斷：自動機

例：假設保留字只有begin和end的情況見下圖：beginndeNot(e)Not(g)Not(i)Not(n)Not(b,e)Not(n)Not(d)該方法的優(yōu)點：速度快；缺點：自動機太大。

運算符的處理：

1.不區(qū)分，統(tǒng)一成一類

2.區(qū)分，每個運算符為一類

空格符和制表符以及換行符的處理

1.無用的空格符和制表符要刪掉；2.字符串內的空格不能刪；

實現方法：進入字符串時令標志變量StringFlag為true,退出時為false。3.換行符不能刪，用于錯誤定位。括號類配對預檢括號類：

如：begin…end,if…then,[],{},()，record…end處理方法：

對每類括號設置一個計數器（初值=0）每當遇到開括號，則計數器加1每當遇到閉括號時，計數器減1詞法分析結束時，如果計數器0，則表明括號不匹配，報錯。向前看多個字符的處理對于復合型特殊符，如“:=”的處理方法：讀到“:”時不能判斷是否為冒號，必須讀下一字符。下圖是對枚舉類型如10..100和實數如3.14的處理：D.D..DD注：對于pascal和Ada等語言至多向前看兩個字符即名。例：錯誤單詞12.3e+q的處理方法：每當一個字符被掃描時，緩存并判斷已掃部分的類型或無效（Invalid），當不能進一步掃描時，進行倒退工作，返回最后Invalid前面的類型，如右表中返回RealConstant。BufferedTokenTokenFlag1IntegerConstant12IntegerConstant12.Invalid12.3RealConstant12.3eInvalid12.3e+Invalid詞法錯誤校正詞法錯誤種類：語言不允許的符號：#括號類配對錯誤：單詞的后繼符錯（偶爾）：詞法錯誤校正：

a刪除已被讀過的字符，并重新掃描未被讀過的字符

b刪除已讀過的第一個字符，重新掃描它的后繼部分的字符。校正后的標示詞法分析獨立化的意義1）使語法分析器和語義分析器的算法更加清晰和簡練；

2）便于利用自動機、正則表達式等理論技術加以自動化；3）更加有利于構造出高效的詞法分析器；

4）有利于編譯器的移植。3.2有限自動機描述程序設計語言中的單詞的識別過程。主要內容：確定有限自動機DFA的定義確定有限自動機DFA的實現非確定有限自動機NFANFA到DFA的轉換DFA的化簡一個確定的有窮自動機（DFA）M是一個五元組：M=（SS，Σ，，S0，Z）其中1.SS是一個有窮集，它的每個元素稱為一個狀態(tài)；2.Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱Σ為輸入符號字母表；3.是轉換函數，是在SS×Σ→SS上的映射，即:如（ki，a）=kj，（ki∈SS，kj∈SS）就意味著，當前狀態(tài)為ki，輸入符為a時，將轉換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4.S0∈SS,是唯一的一個初態(tài)；5.ZSS,是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結束狀態(tài)。3.2.1確定的有窮自動機（DFA）定義:DFA的兩種表示方式

狀態(tài)轉換圖：

結點表示狀態(tài)，轉換邊表示轉換函數，邊的箭頭方向指向轉換函數中定義的轉換方向。標識出初始狀態(tài)和終止狀態(tài)。

狀態(tài)轉換表：可用二維數組描述。標識出初始狀態(tài)和終止狀態(tài)。Trans（SI，a）＝SJDFA例1：DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QDFA的狀態(tài)圖表示:f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bbDFA的矩陣表示:f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QabSUVUQVVUQQQQ字符狀態(tài)0100DFA例2：整常數集：如16,135,258實常數集：如16.135,258.5S0dS1d0d.2d3dd1DFA例3：第二位為2的整數集(包括一位)：如x2ad標識符集：如x,ab3_7d2dL-L,DL,D∑*上的符號串t被M接受定義1：對于∑*中的任何字符串t，若存在一條從初態(tài)結到某一終態(tài)結的道路，且這條路上所有弧的標記符連接成的字符串等于t，則稱t可為DFAM所接受，若M的初態(tài)結同時又是終態(tài)結，則空字可為M所接受（識別）。定義2：若t∑*，f(S，t)=P，其中S為DFA

M的開始狀態(tài)，PZ，Z為終態(tài)集。

則稱t為DFAM所接受（識別）?！?上的符號串t（我們將輸入符號串t表示成t1tx的形式，其中t1∈∑，tx∈∑*）在M上在DFAM上運行的定義為：

f（Q,t1tx）=f（f（Q,t1）,tx）

其中Q∈K擴充轉換函數f，是K×Σ*→K上的映射，且：

f（Q，）=Q例：證明t=baab被如下的DFA所接受。DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba,bb證明：

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）

=QQ屬于終態(tài)。得證。3.2.2確定有窮自動機的實現DFA的確定性的特點：初始狀態(tài)唯一。轉換函數f:SSSS是一個單值函數，也就是說，對任何狀態(tài)SSS,和輸入符號a,f(S,a)唯一地確定了下一個狀態(tài)。即轉換函數至多確定一個狀態(tài)。沒有空邊。即沒有輸入為（）用DFA構造詞法分析器的方法1狀態(tài)轉換表的形式：（數組T存放轉換函數）

1.State(當前狀態(tài)):=初始狀態(tài) 2.讀一個字符CurrentChar 3.如果CurrentCharEof并且

T(State,CurrentChar)error

則State:=新的狀態(tài)T(State,Current)，

轉到第2步工作。4.如果CurrentChar=Eof并且State=終止狀態(tài)，則接受當前字符串，程序結束。否則報錯

特點：程序短小，但占用存儲空間多代碼如下：intScanner(charinput[]){S:=S0;in=0;ch=input[in++];While(TT(S,ch)undef&&chEof){S=TT(S,ch);ch=input[in++];};If(ch=EOF&&SFinalStates)return(1)elsereturn(0)}用DFA構造詞法分析器的方法2狀態(tài)轉換圖的形式：

每個狀態(tài):對應一個帶標號的case語句；

轉向邊:轉向對應狀態(tài)。特點：程序長，但占用存儲空間少。

Switch(satate){case

Si:Switch(ch){Casea：satate:=Sj;break;Caseb：satate:=Sk;break;other:Error;}}ajbki3.2.3非確定有限自動機NFA定義：一個非確定有限自動機(NFA)A是一個五元組A=(,SS,S0,f,TS).其中:

是字母表;SS:

是狀態(tài)集;

S0:

是初始狀態(tài)集;f:

是轉換函數，但不要求是單值的;

f:SS(∪{})SSTS:

是終止狀態(tài)集.NFA的特點：一個狀態(tài)的不同輸出邊可標有相同的符號。允許有多個開始狀態(tài)。允許輸出邊上標有空串符號。<<=:=:aa*3.2.4NFA到DFA的轉換定理：對于每一個非確定自動機A,存在一個確定自動機A’,使得L(A)=L(A’).相關算法：

1）-閉包：close_（SS）

2）nextstate函數：nextstate（SS,a)

一、close_（SS）計算方法：1.首先令close_:=SS;2.若在close_中存在狀態(tài)S，

1）它末被處理過；

2）它存在指向close_之外狀態(tài)S1的邊；則令：close_:=close_

{S1};3.重復2，直到close_不再變化為止。-閉包的例子：

iakdjcmbdci,j,k,mba則：close_(i)={i,j,k,m}二、nextstate的定義a0a2b1c則：nextstate(0,a)={1,2}定義：nextstate(SS,a)={s1|S(a)S1,SSS}如下圖所示：三、NFA到DFA的轉換過程:1.初始化：AllStateSet={SS0},UnHandledStateSet={SS0}；2.判斷結束：若UnHandledStateSet空，則結束，否則轉下；3.從UnHandledStateSet選擇一個狀態(tài)SS；4.對于每個符號a，做下面工作：

1）求SS1=Close(nextstate(SS,a)；

2）若SS1空，則TT[SS,a]=空；

3）否則，檢查AllStateSet中有無SS1，

①若無，則把SS1追加到UnHandledStateSet和AllStateSet中，并令TT[SS,a]=SS1；②否則，令TT[SS,a]=SS1。5.從UnHandledStateSet中刪除狀態(tài)SS，并轉向步驟2。NFA到DFA的轉換例子：a03a2a1bacbabc[0][1,2][1,2][3*][1,3*][2][3*][2][1,3*][2][1,3*][2][2][3*]31,201,32acaaaba|cb*3.2.5DFA的極小化

狀態(tài)等價:對DFA中的兩個狀態(tài)S1和S2，如果將它們看作是初始狀態(tài)，所接受的符號串相同，則定義S1和S2是等價的。

方法:

1)狀態(tài)合并法;

2)狀態(tài)分離法.

狀態(tài)合并法（狀態(tài)吸收方法）

尋找等價狀態(tài)S1和S2，如果S2為初始狀態(tài)，則S1和S2對調，S2的出現修改為S1，刪除狀態(tài)S2。

狀態(tài)分離法

1）初始化為兩個不等價狀態(tài)集組：非終止狀態(tài)組和終止狀態(tài)組；2）對每組中的某個狀態(tài)分離出與之不等價的狀態(tài)組，直至所有狀態(tài)組內部狀態(tài)都等價為止。狀態(tài)合并法的例子：134a|dc2b134ac2b67c5bd化簡為：實現方法：134ac2b67c5bd第一步：畫FA的狀態(tài)轉換表；abcd10252334*4*5667*7*第二步：4吸收7；abcd10252334*4*5664*#####第三步：3吸收6；abcd10252334*4*53##########第四步：2吸收5；abcd10222334*4*###############第五步：畫出FA。abcd10222334*4*134a|dc2b3.3正則表達式主要內容：基本概念正則表達式定義及一些性質擴充的正則表達式及程序設計語言中單詞的定義正則表達式的局限性。正則定義

3.3.1正則符號串集的相關基本概念

字母表：非空有限集，其元素稱為符號或字母.

符號串：符號的有限序列，也稱為字?；虮硎究沾?空串集{}不同于空集。

符號串長度：符號串中字符的個數||,||=0,|ab|=2

符號串連接：和都是符號串，則為符號串的連接特別有：==

符號串集的乘積：A和B是符號串的集合，則稱

AB={|A，B}特別有：A=A=A，其中表示空集。符號串的方冪：設A是符號串的集合，則稱Ai為符號串集A的方冪，其中i是非負整數。

A0={}

A1=A,A2=AA

AK=AA......A(k個)

符號串集合的星閉包：

A*=A0A1A2A3......3.3.2正則表達式的定義若用RE表示上的正則表達式，用L(RE)表示RE所包含的字符串集合

，則：■

是正則表達式，即：RE

，其中L()={}?！?/p>

是正則表達式，即：RE

，其中L()={}?！鯽是正則表達式，即：aRE

，其中L(a)={a}?！?/p>

A和B是正則表達式，即ARE，BRE，則有：

(A)

RE

，L((A)) =L(A)

A|B

RE

，L(A|B) =L(A)L(B)

A·B

RE

，L(A·B) =L(A)L(B)

A*

RE

，L(A*) =L(A)*

例1：={a,b}.正則表達式eab*2.a(a|b)*

L(e)上所有以a為首后跟任意多個（包括0個）b的字符串集上所有以a為首的字符串集若D={0,1,2,，9}.則：RealC=D+.D+擴充的正則表達式：

A的正閉包：A+=A1A2A3......，即一次或多次重復任何符號:“…”在字母表中任何符號.符號范圍:[0--9]{0,1,2,3,4,5,6,7,8,9}

[a--zA--Z]

[a—z]|[A--Z]

[abc]

(a|b|c)不在給定范圍內的符號:~(a|b|c)或[^

a]可選:

（＋|-）?

//可選+或-或不選正則表達式的性質：

A|B=B|A 選擇的可交換性

A|(B|C)=(A|B)C 選擇的可結合性

A(BC)=(AB)C 連接的可結合性

A(B|C)=AB|AC 連接的可分配性(A|B)C=AC|BC連接的可分配性

A**=A*

冪的等價性例2：整常數集：IntC=D+實常數集：RealC=D+.D+標識符集：IDE=L(L|D|_)*3.3.3正則表達式的局限性：1）正則表達式不能用于描述配對或嵌套的結構；例：A={anban|n>0}2）正則表達式不能用于描述重復串。例：{wcw|w是a和b的串}無法用正則表達式表示（保證兩邊w是相同的）。原因是：正則表達式中沒有變量。3.3.4正則定義正則定義：Mr//本質是為正則表達式命名功能：為較長的正則表達式提供一個簡化了的名字

如：E=((a+bc)+(a+bc)(a+bc))(ab+c)+(ab+c)

其中a+bc出現了三次，ab+c出現了二次，如用正則定義可表示如下：

E1

a+bcE2

ab+cE

(E1+E1E1)E2+E2例3：標識符：

letter[a-zA-Z] digit[0-9] identifierletter(letter|digit)*數字：

整數Int[1-9]Digit*|0實數realInt.Int特殊符號：運算符ch+|-|…3.3.5正則表達式與有限自動機等價定理：對任一確定有限自動機A，存在一正則表達式e,使得L(A)=L(e),反之亦然。關系圖：DFA正則表達式NFA正則表達式到FA的轉換規(guī)則：13ab12a|b13b*123ab12ab123bR=(a|b)*abbxiy(a|b)*abbxjyεabbiεa|bxjyεabbiεab例：為R=(a|b)*abb構造NFA，使得L(N)=L(R)。xjyεbεiabklab123ab12ab12313ab12a|b13ab*

cabcDFA到正則表達式的轉換規(guī)則：例：03124a,baaa,ba,bbb求正規(guī)式R03124a,baaa,ba,bbbxyεεε024a|baaa|ba|bbbxyεεε024a|baaa|ba|bbbxyεεε0a|baa(a|b)*bb(a|b)*xyε0a|baa(a|b)*bb(a|b)*xyε0a|bxyεaa(a|b)*|bb(a|b)*xy(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*習題作業(yè)

S={a,b,c}，試給出S一個不包含連續(xù)兩個b的所有符號串集合的正則定義。

S={a,b,c}，敘述正則式((b|c)*a(b|c)*a)*(b|c)*

描述的符號串。S＝{0,1}，敘述正則式(00|11)

((01|10)(00|11)

(01|10)

)

(00|11)

描述的符號串。給出能被5整除的二進制數表示形式的正則定義。*3.4詞法分析器的構造詞法分析器（Scanner）輸入流詞法描述（正則表達式）NFADFATokenListerror詞法分析器的構造方法用DFA人工構造：1.確定詞法分析器的接口，即確定詞法分析器是作為語法分析的一個子程序還是作為獨立一遍。2.確定單詞分類和Token結構。3.根據2步，構造每一類單詞的描述：正則表達式NFADFA。4.根據3步設計算法實現DFA。利用工具自動生成：ScanGen、Lex3.4.1用DFA人工構造詞法分析器單詞的TOKEN輸出表如下：

identifier($id,Name)

number($int,Numb)

+($plus,‘‘);($semi,‘‘):=($assi,‘‘):($colon,‘‘)<=($le,‘‘)<($lt,‘‘)單詞的一個DFA15L023L|DD4869710D+;:<==otherother狀態(tài)(0)的代碼：Ls0:string:=‘‘;ReadChar(CurrentChar);caseCurrentCharof‘A’..’Z’|‘a’..’z’:gotoLs1;‘0’..’9’:gotoLs2;’+’:gotoLs3;’;’:gotoLs4;’:’:gotoLs5;’<’:gotoLs8;end;狀態(tài)(1)的代碼：Ls1:beginstring:=Append(string,CurrentChar);ReadChar(CurrentChar);caseCurrentCharof‘A’..’Z’|‘a’..’z’|‘0’..’9’:gotoLs1;other:beginBACK;return($id,string)endendend;狀態(tài)(2)的代碼：Ls2:beginstring:=Append(string,CurrentChar);ReadChar(CurrentChar);caseCurrentCharof‘0’..’9’:gotoLs2;other:beginBACK;return($int,string)endendend;狀態(tài)(3)(4)(5)(6)的代碼：Ls3:return($plus,’’);Ls4:return($semi,’’);Ls5:beginReadChar(CurrentChar);caseCurrentCharof‘=’:gotoLs6;other:gotoLs7;endend;Ls6:return($assi,’’);狀態(tài)(7)(8)(9)(10)的代碼：Ls7:beginBACK;return($plus,’’)endLs8:beginReadChar(CurrentChar);caseCurrentCharof‘=’:gotoLs9;other:gotoLs10;endend;Ls9:return($le,’’);Ls10:beginBACK;return($lt,’’)end3.4.2詞法分析器的生成器Lex功能：依據語言的正則表達式，自動生成該語言的詞法分析程序。執(zhí)行過程：正則表達式文件Lex.lLex詞法分析器lexyy.cC編譯器a.out輸入流Token序列Lex的常規(guī)表達式（1）字符

含義

A-Z,0-9,a-z構成了部分模式的字符和數字。.匹配任意字符，除了

\n。-用來指定范圍。例如：A-Z指從

A到

Z之間的所有字符。[]一個字符集合。匹配括號內的

任意

字符。如果第一個字符是

^那么它表示否定模式。例如：[abC]匹配

a,b和

C中的任何一個。

*匹配

0個或者多個上述的模式。

+匹配

1個或者多個上述模式。

?匹配

0個或1個上述模式。

$作為模式的最后一個字符匹配一行的結尾。Lex的常規(guī)表達式（2）字符

含義

{}指出一個模式可能出現的次數。

例如：A{1,3}表示

A可能出現1次或3次。\用來轉義元字符。同樣用來覆蓋字符在此表中定義的特殊意義，只取字符的本意。^否定。|表達式間的邏輯或。"<一些符號>"

字符的字面含義。元字符具有。/向前匹配。如果在匹配的模版中的“/”后跟有后續(xù)表達式，只匹配模版中“/”前面的部分。如：如果輸入

A01，那么在模版

A0/1中的

A0是匹配的。()將一系列常規(guī)表達式分組。常規(guī)表達式舉例常規(guī)表達式

含義

joke[rs]匹配

jokes或

joker。A{1,2}shis+匹配

AAshis,Ashis,Ashiss,Ashisss。(A[b-e])+匹配在

A出現位置后跟隨的從

b到

e的所有字符中的

1個或多個。標記聲明舉例標記

相關表達式

含義

數字(number)([0-9])+1個或多個數字字符(chars)[A-Za-z]任意字符空格(blank)""一個空格字(word)(chars)+1個或多個

chars

變量(variable)(字符)+(數字)*(字符)*(數字)*Lex輸入文件的格式輸入文件格式：{declarations}

%%{rules}

%%{auxiliaryprocedures}%{聲明變量,常量%}正則定義p{action}Lex編程

Lex編程可以分為三步：以Lex可以理解的格式指定模式相關的動作。在這一文件上運行Lex，生成掃描器的C代碼。編譯和鏈接C代碼，生成可執(zhí)行的掃描器。Lex的輸入格式

一個Lex程序分為三個段：第一段：是C和Lex的全局聲明第二段：包括模式（C代碼）第三段：是補充的C函數。這些段以%%來分界。（1）C和Lex的全局聲明這一段中我們可以增加C變量聲明。

%{intwordCount=0;/*保存統(tǒng)計出來的字數

*/

%}

chars[A-Za-z]numbers([0-9])+delim[""\n\t]whitespace{delim}+

words{chars}+

%%兩個百分號標記指出了Lex程序中這一段的結束和三段中第二段的開始。

（2）Lex的模式匹配規(guī)則{words}{wordCount++;/*increasethewordcountbyone*/}{whitespace}{/*donothing*/}{numbers}{/*onemaywanttoaddsomeprocessinghere*/}%%

（3）C代碼

Lex編程的第三段，也就是最后一段覆蓋了C的函數聲明（有時是主函數）。Lex有一套可供使用的函數和變量。其中之一就是yywrap。一般來說，yywrap()的定義如下例。

voidmain(){yylex();/*starttheanalysis*/printf("Noofwords:%d\n",wordCount);}intyywrap(){return1;}例：識別PL/0單詞的LEX程序%{#include<stdio.h>#include“code.h”#include“symbol.h”#include“y.tab.h”externintlevel;int