第04章、詞法分析

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

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

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

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

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

正規(guī)式中的符號

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

”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復(fù)連接）。在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為“”、“”、“”。連接符“”一般可省略不寫?！啊薄ⅰ啊焙汀啊倍际亲蠼Y(jié)合的。16例令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意個a的串}17

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

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

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

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

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

e1=(ab),e2

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

214.3有限自動機

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

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

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

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

∑*上的符號串t在DFA

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

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

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

M的開始狀態(tài)，PZ，Z為終態(tài)集。則稱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屬于終態(tài)。得證。33

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

結(jié)論：

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

123abc41有如下定理:對任何一個具有轉(zhuǎn)移的不確定的有限自動機NFAN，一定存在一個不具有轉(zhuǎn)移的不確定的有限自動機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ài)結(jié)點到某一終態(tài)結(jié)點的道路，且這條道路上所有弧的標記字依序連接成的串(不理采那些標記為ε的弧)等于t，則稱t可為NFAM所識別(讀出或接受)。若M的某些結(jié)既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或者存在一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的道路，其上所有弧的標記均為ε，那么空字可為M所接受。44舉例0001111010001110000001不能識別：000110045

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

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

與某一NFA等價的DFA不唯一。48從NFA的矩陣表示中可以看出，表項通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項是一個狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造的基本思路是：DFA的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài).DFA使用它的狀態(tài)去記錄在NFA讀入一個輸入符號后可能達到的所有狀態(tài)。49定義對狀態(tài)集合I的幾個有關(guān)運算：1.狀態(tài)集合I的ε-閉包：表示為ε-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達的狀態(tài)的集合。狀態(tài)集合I的任何狀態(tài)S都屬于ε-closure(I)。2.Ia：從I中的狀態(tài)經(jīng)過一條a弧(前后可跳過任意條ε弧)而到達的狀態(tài)的全體。50狀態(tài)集合I的有關(guān)運算的例子若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轉(zhuǎn)換為DFA的思想：將從狀態(tài)S出發(fā)經(jīng)過任意條弧所能到達的狀態(tài)作為DFA的初態(tài)S'；從S'出發(fā)，把遇到輸入符號a所轉(zhuǎn)移到的后繼狀態(tài)集作為DFA的新狀態(tài)；如此重復(fù)，直到不再有新的狀態(tài)出現(xiàn)為止。52

NFA確定化算法:

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

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

Sj是K的狀態(tài)。并且約定，狀態(tài)S1,S2,,...

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

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

轉(zhuǎn)換函數(shù)是這樣定義的：d([S1S2,...

Sj],a)=[R1R2...

Rt]

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

=

{S1,S2,,...

Sj}a4.

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

Se]，其中[Si

Sk...

Se]S且{Si

,Sk,,...

Se}Kt}54

NFA的確定化例子47356210aaaabbbb55若要將上圖的NFA轉(zhuǎn)換為DFA，步驟如下：（1）構(gòu)造一張表，它共有｜Σ｜+1列；（2）第一行第一列為-closure({0})；（3）求Ia、Ib并檢查，未在第一列出現(xiàn)過者，填入下行首列；（4）重復(fù)步驟（3）；（5）將狀態(tài)子集重新命名。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確定有限自動機的化簡說一個有限自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有限自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有限自動機。所謂有限自動機的多余狀態(tài)，是指這樣的狀態(tài)：從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。59

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

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

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

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

63

DFA的最小化算法

DFAM=（K,∑,f,k0,,kt）,最小狀態(tài)DFAM’

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

2.對∏根據(jù)最小化原則，構(gòu)造新劃分∏new

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

4.

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

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

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

設(shè)正規(guī)文法G＝（VN，VT，P，S），構(gòu)造一個與G等價的有限自動機NFA

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

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

試構(gòu)造與G等價的有限自動機M。解：

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

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

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

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

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

對終態(tài)Z，增加一產(chǎn)生式：

Z

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

其中轉(zhuǎn)換函數(shù)如圖所示，

試構(gòu)造與之等價的正規(guī)文法G。解：構(gòu)造正規(guī)文法G=(VN,VT,P,S)VN={A,B,C,D}VT={a,b}S=A產(chǎn)生式集合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òu)造的文法G:G[A]:AaB|bCBaD|bBCaC|bDD75課堂練習(xí)構(gòu)造同NFAM等價的正規(guī)文法G。解：bAaBbCDabbaG[A]：A→aB|bDB→bCC→aA|bD|εD→aB|bD|ε764.5正規(guī)式和有限自動機的等價性

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