第4章詞法分析S.PO.P表格管理程序錯誤處理程序

本章將討論詞法分析程序的設計原則，單詞的描述技術，識別機制及詞法分析程序的自動構造原理。4.1詞法分析程序4.2正規表達式與正規集（正規語言）4.3有限自動機4.4正規文法和有限自動機的轉換4.5正規式和有限自動機的等價性2本章重點單詞的描述工具單詞的識別系統設計和實現詞法分析程序首先需要描述和刻畫程序設計語言中的原子單位——單詞，其次需要識別單詞和執行某些相關的動作。描述程序設計語言的詞法的機制是正規表達式，識別機制是有窮狀態自動機。34.1詞法分析程序實現詞法分析（lexicalanalysis）的程序逐個讀入源程序字符并按照構詞規則切分成一系列單詞。單詞是語言中具有獨立意義的最小單位，包括關鍵字(保留字)、標識符、常數、運算符、界符等。詞法分析是編譯過程中的一個階段，在語法分析前進行，也可以和語法分析結合在一起作為一遍，由語法分析程序調用詞法分析程序來獲得當前單詞供語法分析使用。4詞法分析的任務：主要任務：讀源程序，產生單詞符號其他任務：濾掉空格，跳過注釋、換行符刪除注釋進行詞法檢查，報告所發現的錯誤建立符號表5單詞的分類（1）關鍵字：或稱為保留字，是特定的字母序列，在相應的程序設計語言中表示特殊含義。（2）標識符：由用戶定義的串，在程序中常用做常量名、變量名、過程名等。（3）常數：各種類型的常數，包括整型、實型、布爾型、文字型等，如100，10.12，TRUE，“ABC”等。（4）運算符：包括算術運算符和邏輯運算符號，如+、*、<等。（5）界符：如逗號、分號等。6詞法分析程序的輸出詞法分析程序所輸出的單詞符號，常采用以下二元式表示：

（單詞種類，單詞自身值）其中，單詞種類是語法分析所需要的信息，而單詞自身值則是編譯的其他階段需要的信息。單詞種類，可以用整數編碼表示，例如：1-標識符，2-常數，3-關鍵字，4-運算符，5-界符語句例：if(a>0)b=b+1;

(1)關鍵字if(3,’if’)(2)左括號((4,’(’)(3)標識符a(1,指向a的符號表入口)(4)運算符>(4,’>’)(5)常數0(2,’0’)……(12)界符;(5,’;’)7不同分類方法的例子：

下述C++代碼段：while(i>=j)i--;經詞法分析器處理以后，它將被轉換為如下的單詞符號串。(while,_)((,_)(id,指向i的符號表指針)(>=,_)(id,指向j的符號表指針)(),_)(id,指向i的符號表指針)(--,_)(;,_)8詞法分析程序的實現方式詞法分析單獨作為一遍優點：結構簡單、各遍功能單一缺點：效率低9源程序詞法分析程序語法分析程序Tokengettoken….詞法分析程序作為單獨的子程序優點：無須在外存中保留整個源程序的內碼形式。10將詞法分析工作分離的原因簡化設計改進編譯效率增加編譯系統的可移植性114.2正規表達式與正規集（正規語言）程序設計語言中的單詞是基本語法成分,單詞符號的語法可以用有效的工具加以描述，并且基于這類描述工具，實現詞法分析程序的自動構造。12正規式正規式也稱正則表達式，正規表達式（regularexpression），是說明單詞的模式(pattern)的一種重要的表示法（記號），是定義正規集的數學工具。我們用以描述單詞符號。下面是正規式和它所表示的正規集的遞歸定義。13定義（正規式和它所表示的正規集）：設字母表為，輔助字母表’={，，，，，，}。1.和都是上的正規式，它們所表示的正規集分別為{}和{}；2.任何a，a是上的一個正規式，它所表示的正規集為{a}；143.假定e1和e2都是上的正規式，它們所表示的正規集分別為L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正規式，它們所表示的正規集分別為L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))。4.僅由有限次使用上述三步驟而定義的表達式才是上的正規式，僅由這些正規式所表示的集合才是上的正規集。15

正規式中的符號

其中的“”讀為“或”（也有使用“+”代替“”的）；“

”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復連接）。在不致混淆時，括號可省去，但規定算符的優先順序為“”、“”、“”。連接符“”一般可省略不寫。“”、“”和“”都是左結合的。16例令={a，b}，上的正規式和相應的正規集的例子有：正規式 正規集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意個a的串}17

正規式 正規集

(ab) {,a,b,aa,ab……所有由a 和b組成的串}(ab)(aabb)(ab){上所有含有兩個相繼 的a或兩個相繼的b組成的串}18

討論下面兩個例子例4.1令={l，d}，則上的正規式r=l(ld)定義的正規集為:{l,ll,ld,ldd,……},其中l代表字母,d代表數字,正規式即是字母(字母|數字)

,它表示的正規集中的每個元素的模式是“字母打頭的字母數字串”,就是Pascal和多數程序設計語言允許的的標識符的詞法規則.例4.2={d，，e，+，-},則上的正規式d(dd)(e(+-)dd)表示的是無符號數的集合，其中d為09的數字。比如2、21.59、3.6e2、471.88e-1等都是該正規集中的元素。

程序設計語言的單詞都能用正規式來定義19正規式的等價若兩個正規式e1和e2所表示的正規集相同,則說e1和e2等價,寫作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab),e2=(ba)b

e1=(ab),e2

=(ab)20正規式服從的代數規律設r,s,t為正規式，正規式服從的代數規律有：1.rs=sr “或”服從交換律2.r(st)=(rs)t “或”的可結合律3.(rs)t=r(st) “連接”的可結合律4.r(st)=rsrt (st)r=srtr 分配律5.r=r,r=r 是“連接”的恒等元素 零一律6.rr=r r=rrr… “或”的抽取律

214.3有限自動機

有限自動機(也稱有窮自動機)作為一種識別裝置，它能準確地識別正規集，即識別正規文法所定義的語言和正規式所表示的集合，引入有限自動機這個理論，正是為詞法分析程序的自動構造尋找特殊的方法和工具。

有限自動機分為兩類：確定的有限自動機(DeterministicFiniteAutomata)不確定的有限自動機(NondeterministicFiniteAutomata)22關于有限自動機我們將討論如下題目確定的有限自動機DFA不確定的有限自動機NFANFA的確定化DFA的最小化23確定的有限自動機DFADFA定義：一個確定的有限自動機（DFA）M是一個五元組：M=（K，Σ，f，S，Z）其中1.K是一個有窮集，它的每個元素稱為一個狀態；2.Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱Σ為輸入符號表；24DFA定義(續）3.f是轉換函數，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味著，當前狀態為ki，輸入符為a時，將轉換為下一個狀態kj，我們把kj稱作ki的一個后繼狀態；4.S∈K是唯一的一個初態；5.ZK是一個終態集，終態也稱可接受狀態或結束狀態。25一個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）=Q26DFA可以表示成一個狀態圖一個DFA可以表示成一個狀態圖(或稱狀態轉換圖)。假定DFAM含有m個狀態，n個輸入字符，那么這個狀態圖含有m個結點，每個結點最多有n個弧射出，整個圖含有唯一一個初態結點和若干個終態結點，初態結點冠以雙箭頭“=>”或標以“-”，終態結點用雙圈表示或標以“+”，若f(ki,a)=kj，則從狀態結點ki到狀態結點kj畫標記為a的弧；27

DFA的狀態圖表示bSUVQaaaba，bb28DFA還可以用一個矩陣表示一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態，列表示輸入字符，矩陣元素表示相應狀態行和輸入字符列下的新狀態，即k行a列為f(k,a)的值。用雙箭頭“=>”標明初態；否則第一行即是初態，相應終態行在表的右端標以1，非終態標以0。29DFA的矩陣表示字符狀態0001以后我們用*表示終態書上：用0表示非終態用1表示終態30

為了說明DFA如何作為一種識別機制，我們還要理解下面的定義

∑*上的符號串t在DFA

M上運行一個輸入符號串t，（將它表示成Tt1的形式，其中T∈∑，t1∈∑*）在DFAM=（K，Σ，f，S，Z）上運行的定義為：f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K擴充轉換函數f為K×Σ*→K上的映射，且：

f（ki，）=ki31∑*上的符號串t被DFA

M接受M=（K，Σ，f，S，Z）若t∑*，f(S，t)=P，其中S為

M的開始狀態，PZ，Z為終態集。則稱t為DFAM所接受（識別）.32例：證明t=baab被下圖的DFA所接受。bSUVQabba,baaf（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屬于終態。得證。33

DFAM所能接受的符號串的全體記為L(M)，對于任何兩個有限自動機M和M′，如果L(M)=L(M′)，則稱M與M′是等價的。

結論：

上一個符號串集V是正規的，當且僅當存在一個上的確定有限自動機M，使得V=L(M)。34DFA的確定性表現在：轉換函數f:K×Σ→K是一個單值函數，也就是說，對任何狀態k∈K，和輸入符號a∈Σ，f(k,a)唯一地確定了下一個狀態。從狀態轉換圖來看，若字母表Σ含有n個輸入字符，那末任何一個狀態結點最多有n條弧射出，而且每條弧以一個不同的輸入字符標記。35例：DFAM=({0,1,2,3},{a,b},f,0,{3})其中：f（0,a)=1;f（0,b)=2f（1,a)=3;f（1,b)=2f（2,a)=1;f（2,b)=3f（3,a)=3;f（3,b)=3問：有幾個狀態,幾個輸入字符？并畫出其轉換圖。該自動機可識別符號串abaab和abab嗎？36解：有0，1，2，3共四個狀態。輸入字符為a,b兩個。其狀態轉換圖如下：012abababa,b3對于符號串abaab，可被識別。對于符號串abab，不能被識別。37不確定的有限自動機NFA定義NFAM=K，，f，S，Z，其中K為狀態的有窮非空集，為有窮輸入字母表，f為K*到K的子集（2K）的一種映射（即K×*2k），SK是非空初始狀態集，ZK為終止狀態集.顯然，NFA也可以表示成一張狀態轉換圖。假定NFA含有m個狀態、n個輸入字符，那么，這張圖含有m個狀態結點，每個結點可以射出若干條箭弧和別的結點相連接，每條箭弧用*上的一個字（不一定要不同的字而且可以是空字）作標記（稱為輸入字），整張圖至少含有一個初態和若干個（可以是0個）終態結點。某些結點既可以是初態也可以是終態結點。38例子NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}），其中：

f（S，0）={P}f（Z，0）={P}f（P，1）={Z}f（Z，1）={P}f（S，1）={S，Z}SPZ00111139矩陣表示01S{P}{S,Z}P{}{Z}*Z{P}{P}40f為K*到K的子集（2K）的一種映射具有轉移的不確定的有限自動機

123abc41有如下定理:對任何一個具有轉移的不確定的有限自動機NFAN，一定存在一個不具有轉移的不確定的有限自動機NFAＭ，使得L(M)=L(N)。

與上例等價的一個NFA:2acbb31acacbb123abc42類似DFA,對NFAM=K，，f，S，Z也有如下定義:∑*上的符號串t在NFA

M上運行一個輸入符號串t，（我們將它表示成Tt1的形式，其中T∈∑，t1∈∑*）在NFAM上運行的定義為：f(Q，Tt1)=f(f(Q，T)，t1)其中Q∈K，∑*上的符號串t被NFA

M接受若t∑*，f(S0，t)=P，其中S0∈S，P∈

Z，則稱t為NFAM所接受（識別）43

∑*上的符號串t被NFA

M接受也可以這樣理解

對于Σ﹡中的任何一個串t，若存在一條從某一初態結點到某一終態結點的道路，且這條道路上所有弧的標記字依序連接成的串(不理采那些標記為ε的弧)等于t，則稱t可為NFAM所識別(讀出或接受)。若M的某些結既是初態結點又是終態結點，或者存在一條從某個初態結點到某個終態結點的道路，其上所有弧的標記均為ε，那么空字可為M所接受。44舉例0001111010001110000001不能識別：000110045

NFAM所能接受的符號串的全體記為L(M)結論：

上一個符號串集V是正規的，當且僅當存在一個上的不確定的有限自動機M，使得V=L(M)。46例：(0|1)*(000|111)(0|1)*47定理：DFA是NFA的特例，對每個NFAN一定存在一個DFAＭ，使得L(M)=L(N)。對每個NFAN存在著與之等價的DFAM。有一種算法，將NFA轉換成接受同樣語言的DFA，這種算法稱為子集法。

與某一NFA等價的DFA不唯一。48從NFA的矩陣表示中可以看出，表項通常是一狀態的集合，而在DFA的矩陣表示中，表項是一個狀態，NFA到相應的DFA的構造的基本思路是：DFA的每一個狀態對應NFA的一組狀態.DFA使用它的狀態去記錄在NFA讀入一個輸入符號后可能達到的所有狀態。49定義對狀態集合I的幾個有關運算：1.狀態集合I的ε-閉包：表示為ε-closure(I)，定義為一狀態集，是狀態集I中的任何狀態S經任意條ε弧而能到達的狀態的集合。狀態集合I的任何狀態S都屬于ε-closure(I)。2.Ia：從I中的狀態經過一條a弧(前后可跳過任意條ε弧)而到達的狀態的全體。50狀態集合I的有關運算的例子若I={1},則

-closure(I)={1,2}；若I={5},則

-closure(I)={5,6,2}；若I={1,2},則Ia={2,3,4,5,6,7,8}；(備注：不需要掌握書上講的move集合)12534678aaa51NFA轉換為DFA的思想：將從狀態S出發經過任意條弧所能到達的狀態作為DFA的初態S'；從S'出發，把遇到輸入符號a所轉移到的后繼狀態集作為DFA的新狀態；如此重復，直到不再有新的狀態出現為止。52

NFA確定化算法:

假設NFAN=(K,,f,K0,Kt)，按如下辦法構造一個DFAM=(S,,d,S0,St)，使得L(M)=L(N)：531.M的狀態集S由K的一些子集組成。用[S1S2...

Sj]表示S的元素，其中S1,S2,,...

Sj是K的狀態。并且約定，狀態S1,S2,,...

Sj是按某種規則排列的，即對于子集{S1,S2}={S2,S1,}來說，S的狀態就是[S1S2]；

2.M和N的輸入字母表是相同的，即是；3.

轉換函數是這樣定義的：d([S1S2,...

Sj],a)=[R1R2...

Rt]

其中{R1,R2,...,Rt}

=

{S1,S2,,...

Sj}a4.

S0=-closure(K0)為M的開始狀態；5.St={[SiSk...

Se]，其中[Si

Sk...

Se]S且{Si

,Sk,,...

Se}Kt}54

NFA的確定化例子47356210aaaabbbb55若要將上圖的NFA轉換為DFA，步驟如下：（1）構造一張表，它共有｜Σ｜+1列；（2）第一行第一列為-closure({0})；（3）求Ia、Ib并檢查，未在第一列出現過者，填入下行首列；（4）重復步驟（3）；（5）將狀態子集重新命名。5647356210aaaabbbb-closure(0)I

S

A

B

A

C

B

B

A

D

*C

C

E

*D

F

D

*E

F

D

*F

C

E

57等價的DFAaCDBAEFSbaaaaabbbbbabF58確定有限自動機的化簡說一個有限自動機是化簡了的，即是說，它沒有多余狀態并且它的狀態中沒有兩個是互相等價的。一個有限自動機可以通過消除多余狀態和合并等價狀態而轉換成一個最小的與之等價的有限自動機。所謂有限自動機的多余狀態，是指這樣的狀態：從自動機的開始狀態出發，任何輸入串也不能到達的那個狀態；或者從這個狀態沒有通路到達終態。59

DFA的最小化就是尋求最小狀態DFA最小狀態DFA的含義:沒有多余狀態(死狀態)沒有兩個狀態是互相等價（不可區別）兩個狀態s和t等價，滿足：(或可區別：不滿足）一致性(或兼容性)——同是終態或同是非終態；蔓延性(或傳播性)——從s出發讀入某個aa和從 t出發讀入某個a到達的狀態等價。60

例：C和F是等價的。因為C和F同是終態,C和F讀入a都到達C,讀入b都到達E，所以C和F等價。aCDBAEFSbaaaaabbbbbabF61最小狀態DFA對于一個DFAM=（K,∑,f,

k0,kt)，存在一個最小狀態DFAM’=（K’,∑,f’,

k0’,,kt’)，使L(M’)=L(M).62“分割法”DFA的最小化算法的核心把一個DFA的狀態分成一些不相交的子集，使得任何不同的兩子集的狀態都是可區別的，而同一子集中的任何兩個狀態都是等價的。結論：終態和非終態是可區別的（不等價），因為從終態可以識別到達終態，而從非終態則不能識別到達終態。

63

DFA的最小化算法

DFAM=（K,∑,f,k0,,kt）,最小狀態DFAM’

1.構造狀態的一初始劃分：終態kt和非終態K-kt兩組(group)

2.對∏根據最小化原則，構造新劃分∏new

3.如∏new=∏,則令∏final=∏并繼續步驟4，否則∏:=∏new重復2.

4.

為∏final中的每一組選一代表，這些代表構成M’的狀態。若k是一代表且f(k,a)=t,令r是t組的代表，則M’中有一轉換f’(k,a)=r，M’的開始狀態是含有S0的那組的代表，M’的終態是含有F的那組的代表5.去掉M’中的死狀態.64DFA最小化算法的核心——分割法。步驟如下：（1）將所有狀態分成兩個子集：終態集和非終態集；（2）把等價的狀態構成一個子集，若不等價繼續劃分；（3）結束后，重新標號或從每個子集中選一個狀態做代表。65IIaIbSABACBBAD*CCE*DFD*EFD*FCEDFA的最小化—例子M={S,A,B}∪{C,D,E,F}∵{S,A,B}a={A,C}不包含于第1次劃分出的任意集合∴{S,A,B}不等價，繼續得到第2次劃分為：{S,B}∪{A}∵{S,B}b={B,D}不包含于第2次劃分出的任意集合∴{S,B}不等價，繼續得到第3次劃分為：{S}∪{A}∪{B}∵{C,D,E,F}a={C,F}{C,D,E,F}b={D,E}∴{C,D,E,F}等價故最后結果為：M={S}∪{A}∪{B}{C,D,E,F}aCDBAEFSbaaaaabbbbbabF66IIaIbSABACBBAC*CCCDFA的最小化—例子(續)因{C,D,E,F}等價，故從{C,D,E,F}中選C作為代表，出現D,E,F的地方一律用C代替，如下：aCDBAEFSbaaaaabbbbbabF最小化后DFA的為：CBASaaabbbba67例子畫出能夠識別C語言注釋/**/的DFA狀態1：注釋開始狀態。狀態2：進入注釋體前的中間狀態。狀態3：表明目前正在注釋體中的狀態。狀態4：離開注釋前的中間狀態。狀態5：注釋結束狀態，即接受狀態。1/2534/**othersothers有限自動機的一些應用用于某些重要軟件的設計和構造設計和檢查數字電路行為的軟件;掃描如網頁族等大規模文本以發現字、詞或其它結構的出現頻率的軟件;驗證所有只有有限多個不同狀態的系統的軟件，這類系統包括通信協議和信息安全交換協議。文獻舉例：基于協議分析狀態機的入侵檢測系統有限自動機在BBS信息監測系統中的運用定理：

由任意正規文法G定義的語言必然能被一個NFAM所接受。即L（G）＝L（M）

4.4正規文法和有限自動機的轉換70定理：由任意正規文法G定義的語言必然能被一個NFAM所接受。即L（G）＝L（M）構造方法：

設正規文法G＝（VN，VT，P，S），構造一個與G等價的有限自動機NFA

M＝（K，∑，f，S，Z），其中：(1)K＝VNU{Z}，Z為一個新增加的終態；(2)∑=VT(即字母表與G的終結符集相同)；(3)開始符號S作為開始狀態S；f的定義為：當AaBP，則構造：f（A，a）=B當AaP,則構造：f（A，a）=Z當A

P,則構造：f（A，）=Z一、正規文法＝>有限自動機71正規文法＝>有限自動機（例）例：設有正規文法G=({S,A},{a,b},P,S)，其中 P：SaAAaA|bS|a

試構造與G等價的有限自動機M。解：

設NFAM=(K,∑,f,S,Z)K={S,A,Z}∑={a,b}S

=SZ={Z}轉換函數：對于產生式SaA，有f(S,a)={A}對于產生式AaA，有f(A,a)={A}對于產生式AbS，有f(A,b)={S}對于產生式Aa，有f(A,a)={Z}SAZ開始aaab72課堂練習

設正規文法G＝({S，A，B}，{a，b}，P，S)P： S

aA|bB|a AaA|aS|bB BbB|b|a 構造相應的NFAM。73二、有限自動機＝>正規文法定理：設有限自動機M接受的語言為L(M)則存在正規文法G，它產生的語言L(G)＝L(M)。證明思路：構造一個正規文法G，使它接受由NFAM定義的語言。構造方法：

設M＝（K，∑，f，S，Z），構造一個正規文法G＝（VN，VT，P，S），其中VN＝K，S＝SP定義為：若f（A，a）＝B，則AaB在P中

對終態Z，增加一產生式：

Z

74有限自動機＝>正規文法（例）例：設有DFAM=({A,B,C,D},{a,b},f,A,{D})

其中轉換函數如圖所示，

試構造與之等價的正規文法G。解：構造正規文法G=(VN,VT,P,S)VN={A,B,C,D}VT={a,b}S=A產生式集合Pf(A,a)=B，AaBf(A,b)=C，AbCf(B,a)=D，BaDf(B,b)=B，BbBf(C,a)=C，CaCf(C,b)=D，CbDDZ，DABCDaaabbb開始構造的文法G:G[A]:AaB|bCBaD|bBCaC|bDD75課堂練習構造同NFAM等價的正規文法G。解：bAaBbCDabbaG[A]：A→aB|bDB→bCC→aA|bD|εD→aB|bD|ε764.5正規式和有限自動機的等價性

詞法分析程序的自動構造方法，基于有限自動機和正規表達式的等價性，即：1.對于∑上的一個NFAM，可以構造一個∑上的正規式R,使得L(R)=L(M)。2.對于∑上的一個正規式R，可以構造一個∑上的NFAM，使的L(M)=L(R)。771、在M上加兩個結點S、Z，從S結點用ε弧到M的所有初態，從M的所有終態用ε到Z結成與M等價的M’，M’只有一個初態S和一個終態Z。03214a,ba,ba,bbbaaS03412Zεεεaa,ba,ba,babb一、自動機＝>正規式（狀態消去法）2、逐步消去M’中的所有結點，直至剩下S和Z結點，在消去過程中，逐步用正規式來標記弧，消去規則如下：R1R2123R1R21312R1R2R1|R2121R1R323R2R1R2*R313繼續消去S03412Zεεεaa,ba,ba,babbS042Zεεεaaa|b