《編譯原理 第3章課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理 第3章課件（14頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第三章 詞法分析 本章將討論詞法分析程序的設(shè)計(jì)原則，單詞的描述技術(shù)，識(shí)別機(jī)制及詞法分析程序的自動(dòng)構(gòu)造原理。 教學(xué)要求１.掌握：正規(guī)式，DFA的概念，NFA的概念 ２.理解：將 NFA轉(zhuǎn)換為DFA ,正規(guī)式、正規(guī)文法與有窮自動(dòng)機(jī)間的轉(zhuǎn)換 目錄3.1 詞法分析程序的設(shè)計(jì) 3.2 單詞的描述工具 3.3 有窮自動(dòng)機(jī) 3.4 正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性 3.5 正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性 3.6 詞法分析程序的自動(dòng)構(gòu)造工具 小結(jié)? 3.1.詞法分析（lexical analysis） 程序的設(shè)計(jì) 回顧： 1、詞法分析的任務(wù)：逐個(gè)讀入源程序字符并按照構(gòu)詞

2、規(guī)則切分成一系列單詞。 2、詞法分析程序：實(shí)現(xiàn)詞法分析的程序。 一.詞法與語法分析程序的接口方式 1、作為獨(dú)立的一遍 詞法分析是編譯過程中的一個(gè)階段，在語法分析前進(jìn)行，把字符流的源程序變?yōu)閱卧~序列，輸出在一個(gè)中間文件上。 2、與語法分析結(jié)合在一起作為一遍 一般、把詞法分析程序設(shè)計(jì)成一個(gè)子程序，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞，供語法分析使用。 …. Token 詞法分析程序 源程序 詞法分析程序和語法分析程序的關(guān)系 語法分析程序 get token 詞法分析程序的主要任務(wù)：讀源程序，產(chǎn)生單詞符號(hào) 詞法分析程序的其他任務(wù)：濾掉

3、空格，跳過注釋、換行符 追蹤換行標(biāo) 志，復(fù)制出錯(cuò)源程序，宏展開， …… 二、詞法分析程序的輸出 輸出是單詞符號(hào)。單詞是語言中具有獨(dú)立意義的最小單位。 單詞包括： 保留字 標(biāo)識(shí)符 常量 運(yùn)算符 界符（標(biāo)點(diǎn)符號(hào)） 詞法分析程序所輸出的單詞符號(hào)常常采用以下二元式表示：(單詞種別，單 詞自身的值)。 單詞的種別是語法分析需要的信息，而單詞自身的值則是編譯其它階段需要 的信息。 對(duì)某些單詞來說，不僅僅需要它的值，還需要其它一些信息以便編譯的進(jìn)行， 那么可以將單詞的二元式表示設(shè)計(jì)成如下形式： (標(biāo)識(shí)符

4、，指向該標(biāo)識(shí)符所在符號(hào)表中位置的指針) 單詞的種別可以用整數(shù)編碼表示，假如標(biāo)識(shí)符編碼為1，常數(shù)為2，保留字為 3，運(yùn)算符為4，界符為5 例如：程序段 if i=5 then x∶=y； 在經(jīng)詞法分析器掃描后輸出的單詞符號(hào)和它們的表示如下： 　 - 保留字if(3，'if') 　 - 標(biāo)識(shí)符i(1，指向i的符號(hào)表入口) 　 - 等號(hào)=(4，'=') 　 - 常數(shù)5(2，'5') 　 - 保留字then(3，'then') 　 - 標(biāo)識(shí)符x(1，指向x的符號(hào)表入口) 　 - 賦值號(hào)∶=(4，'∶=') 　 - 標(biāo)識(shí)符 y(1，指向y的符號(hào)表入口)

5、 　 - 分號(hào)；(5，'；') 　 三、詞法分析工作從語法分析工作獨(dú)立出來的原因： 簡(jiǎn)化設(shè)計(jì) 改進(jìn)編譯效率 增加編譯系統(tǒng)的可移植性 3.2 單詞的描述工具 程序設(shè)計(jì)語言中的單詞是基本語法成分.單詞符號(hào)的語法可以用有效的工具加以描述，并且基于這類描述工具，實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造. 描述工具：正規(guī)文法和正規(guī)式 識(shí)別工具：有窮自動(dòng)機(jī) 一．正規(guī)文法 多數(shù)程序設(shè)計(jì)語言的單詞的語法能用正規(guī)文法來描述。正規(guī)文法所描述的是VT* 上的正規(guī)集。幾類單詞的規(guī)則如下： <標(biāo)識(shí)符>→l|l<字母數(shù)字> <字母數(shù)字>→ l|d|l<字母數(shù)字>|d < 字母數(shù)

6、字> <無符號(hào)整數(shù)>→d|d <無符號(hào)整數(shù)> <運(yùn)算符> →+|-|*|/|<<等號(hào)>|><等號(hào)>|…… <等號(hào)> →= <界符> →，|；|（|）|…… 二．正規(guī)式（regular expression） 描述單詞符號(hào)最方便的工具。 正規(guī)式也稱正則表達(dá)式,是說明單詞的模式(pattern)的一種重要的表示法（記號(hào)），是定義正規(guī)集的數(shù)學(xué)工具。 下面是正規(guī)式和它所表示的正規(guī)集的遞歸定義。 定義（正規(guī)式和它所表示的正規(guī)集）： 設(shè)字母表為S，輔助字母表S`={F，e，?，，*，(，)}。 1 e和F都是S上的正規(guī)式，2 它們所表示的正規(guī)集分別為{e}和F

7、 ； 2 任何a? S，a是S上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}； 3 假定e1和e2都是S上的正規(guī)式，它們所 表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)， 那么，(e1), e1? e2, e1?e2, e1*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(zhǎng)(e1), L(e1)*L(e2), L(e1)L(e2)和(L(e1))*。 4 僅由有限次使用上述三步驟而定義的表達(dá)式才是S上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是S上的正規(guī)集 正規(guī)式中的符號(hào)說明 “?”讀為“或” ； “· ”讀為“連接”； “*”讀為“閉包”（即，任意有限次的自重復(fù)連接

8、）。 在不致混淆時(shí)，括號(hào)可省去，但規(guī)定算符的優(yōu)先順序?yàn)椤?”、“· ”、“?” 。 連接符“· ”一般可省略不寫。 “*”、“· ”和“?” 都是左結(jié)合的。 例子：令S={a，b}， S上的正規(guī)式和相應(yīng)的正規(guī)集的例子有： 正規(guī)式 正規(guī)集 a {a} a?b {a,b} ab {ab} (a?b)(a?b) {aa,ab,ba,bb} a * {e ,a,aa,…任意個(gè)a串} 正規(guī)式: (a?b)* 正規(guī)集: {e ,a,b,aa,ab ……所有由a和b組成的串} 正規(guī)式:(a?b)* (a

9、a?bb)(a?b)* 正規(guī)集:{S*上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串} 討論下面兩個(gè)例子 例3.1 令S={l，d}，則S上的正規(guī)式 r=l(l ?d) *定義的正規(guī)集為: {l,ll,ld,ldd,……} 其中：l代表字母,d代表數(shù)字； 1 正規(guī)式即是字母(字母|數(shù)字) * ； 2 它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”； 3 就是多數(shù)程序設(shè)計(jì)語言允許的的標(biāo)識(shí)符的詞法規(guī)則 例3.2S={d，，e，+，-},則S上的正規(guī)式 ：d*(*dd *? e )(e(+?- e?)dd* e?) 其中d為0

10、~9的數(shù)字。 表示的是無符號(hào)數(shù)的集合。其中d為0~9的數(shù)字。 2，22.34,3.2e2,23.8e-3等都是其正規(guī)集中的元素。 程序設(shè)計(jì)語言的單詞都能用正規(guī)式來定義 若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價(jià),寫作e1=e2。 – 例如： e1= (a?b)，– e2 = b?a – 又如： e1= b(ab)* , e2 =(ba)*b – 再如： e1= (a?b)* , e2 =(a*?b*)* 設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有： r?s=s?r “或”服從交換律 r?(s?t)=(r?s)?t

11、 “或”的可結(jié)合律 (rs)t=r(st) “連接”的可結(jié)合律 r(s?t)=rs?rt (s?t)r=sr?tr 分配律 er=r, re=r e是“連接”的恒等元素 r?r=r r*=?er?rr?… “或”的抽取律 正規(guī)文法和正規(guī)式 一個(gè)正規(guī)語言可以由正規(guī)文法定義，也可以由正規(guī)式定義。 1、將Σ上的正規(guī)式r轉(zhuǎn)換成正規(guī)文法G =（VN,VT,P,S）。 VT = Σ 對(duì)任何正規(guī)式r，選擇一個(gè)非終結(jié)符S生成產(chǎn)生式S->r,將S為G的識(shí)別符號(hào)。 若x和y都是正規(guī)式， 對(duì)A->xy,重寫成：

12、A->xB, B->y; 對(duì)形如A->x|y,重寫成： A->x,A->y; 對(duì)形如A->x* y,重寫成： A->xB, A->y, B-> xB, B->y; 不斷使用如上規(guī)則，直到每個(gè)產(chǎn)生式最多含有一個(gè)終結(jié)符為止。 例如：將R=a(a|d) *轉(zhuǎn)換成正規(guī)文法 S-> a(a|d) * 將S是文法的識(shí)別符號(hào)。 根據(jù)規(guī)則1形成S->aA,A-> (a|d) * 根據(jù)規(guī)則3，對(duì)第二條重寫成A->(a|d)B, A->ε,B->(a|d)B,B->ε 最后得出正規(guī)文法為S->

13、aA,A->aB, A->dB, A->ε, B->aB, B->dB, B->ε 2、正規(guī)文法轉(zhuǎn)換成正規(guī)式 使用如下規(guī)則，最后只剩下一個(gè)開始符號(hào)定義的產(chǎn)生式，并且右部不含非終結(jié)符。 規(guī)則1 ：A-> xB,B->y => A -> xy 規(guī)則2： A->xA|y => A -> x * y 規(guī)則3： A->x, A->y => A -> x|y 例如：文法G[S]為：S->aA, S->a, A-> aA, A->dA, A->a, A->d S-> aA|a A=> (aA| dA)|(a|d) =>A=(a|d)A|(a|d) =

14、>A=(a|d) * (a|d)=(a|d) + A帶入S得： S-> a (a|d) + |a S-> a ((a|d) +|ε） S-> a (a|d) * 對(duì)應(yīng)正規(guī)式為：a (a|d) * 3.3 有窮自動(dòng)機(jī) 有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。 有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)(Deterministic Finite Automata)和不確定的有窮自動(dòng)機(jī)(Nonde

15、terministic Finite Automata) 。 關(guān)于有窮自動(dòng)機(jī)我們將討論如下題目:確定的有窮自動(dòng)機(jī)DFA NFA的確定化 不確定的有窮自動(dòng)機(jī)NFA DFA的最小化 3.3.1確定的有窮自動(dòng)機(jī)DFA DFA定義： 一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，Σ，f，S，Z）其中 1.K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)； 2.Σ是一個(gè)有窮字母表,它的每個(gè)元素稱為一個(gè)輸入符號(hào),也稱Σ為輸入符號(hào)表； 3.f是轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映射，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)

16、，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)； 4.S∈K是唯一的一個(gè)初態(tài)； 5 .Z K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。 一個(gè)DFA 的例子： DFA M=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定義為： f（S，a）=U f（V，a）=U f（S，b）=V f（V，b）=Q f（U，a）=Q f（Q，a）=Q f（U，b）=V f（Q，b）=Q 一個(gè)DFA可以表示成一個(gè)狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。畫法為： 1、假定DFA M含有m個(gè)狀態(tài)，n個(gè)輸入字符，那么這個(gè)狀態(tài)圖含有m個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)最多有n個(gè)弧射出。 2

17、、整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)終態(tài)結(jié)點(diǎn)，初態(tài)結(jié)點(diǎn)冠以雙箭頭“=>”或標(biāo)以“-”，終態(tài)結(jié)點(diǎn)用雙圈表示或標(biāo)以“+”。 3、若 f(ki,a)=kj，則從狀態(tài)結(jié)點(diǎn)ki到狀態(tài)結(jié)點(diǎn)kj畫標(biāo)記為a的??； b S U V Q a a a b a，b DFA M 的狀態(tài)圖表示 一個(gè)DFA還可以用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭“=>”標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標(biāo)以1，非終態(tài)標(biāo)以0。 0 0 0

18、 1 DFA M 的矩陣表示 為了說明DFA如何作為一種識(shí)別機(jī)制,我們還要理解下面的定義 ∑*上的符號(hào)串t在DFA M上運(yùn)行 一個(gè)輸入符號(hào)串t，（將它表示成Tt1的形式，其中T∈∑，t1∈ ∑*）在DFA M=（K，Σ，f，S，Z）上運(yùn)行的定義為： f（Q， Tt1）=f（f（Q，T），t1） 其中Q∈K 擴(kuò)充轉(zhuǎn)換函數(shù)f為 K×Σ*→K上的映射，且： f（ki，e）= ki ∑*上的符號(hào)串t被DFA M接受 M=（K，Σ，f，S，Z） 若t? ∑*，f(S，t

19、)=P，其中S為 M的開始狀態(tài)，P ? Z，Z為終態(tài)集。 則稱t為DFA M所接受（識(shí)別）. 例：證明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)。得證。 DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:K×Σ→K是一個(gè)單值函數(shù)，也就是說，對(duì)任何狀態(tài)k∈K，和輸入符號(hào)a∈Σ，f(k,a)唯一地確定了下一個(gè)狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，若字母表Σ含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)

20、點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。 DFA的行為很容易用程序來模擬. DFA M=（K，Σ，f，S，Z）的行為的模擬程序 K:=S； c:=getchar; while c<>eof do {K:=f(K,c); c:=getchar; }; if K is in Z then return (‘yes’) else return (‘no’) DFA M所能接受的符號(hào)串的全體記為L(zhǎng)(M). 對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M′，如果L(M)=L(M′)，則稱M與M′是等價(jià)的.? 結(jié)論： ?

21、上一個(gè)符號(hào)串集Vì?*是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)?上的確定有窮自動(dòng)機(jī)M，使得 V=L(M)。 3.3.2 不確定的有窮自動(dòng)機(jī)NFA 定義 NFA M=íK，?，f，S，Zy，其中: K為狀態(tài)的有窮非空集; ?為有窮輸入字母表; f為K′ ?* 到K的子集（2 K）的一種映射; S ì K是初始狀態(tài)集; Z ì K為終止?fàn)顟B(tài)集; 例子 NFA M=（{S，P，Z}，{0，1}，f，{S，P}，{Z}） S P Z 0 0,1 1 1 1 狀態(tài)圖表示 其中 f（S，0）={P} f（Z，0）={P} f（P，1）={Z} f（Z，1）

22、={P} f（S，1）={S，Z} 簡(jiǎn)化為 矩陣表示、 0 1 S {P} {S\Z} 0 P {} {Z} 0 Z {P} {P} 1 0 1 S P S、Z 0 P . Z 0 Z P P 1 類似DFA, 對(duì)NFA M=íK，?，f，S，Zy也有如下定義 ∑*上的符號(hào)串t在NFA M上運(yùn)行 一個(gè)輸入符號(hào)串t，（我們將它表示成Tt1的形式，其中T∈∑，t1∈ ∑*）在NFA M上運(yùn)行

23、的定義為： f（Q， Tt1）=f（f（Q，T），t1） 其中Q∈K. ∑*上的符號(hào)串t被NFA M接受 若t? ∑*，f(S0，t)=P，其中S0 ∈S，P ? Z，則稱t為NFA M所接受（識(shí)別） ∑*上的符號(hào)串t被NFA M接受也可以這樣理解 對(duì)于Σ﹡中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為ε的弧)等于t，則稱t可為NFA M所識(shí)別(讀出或接受)。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均為ε，那么空串可為M所接受。 000 111 101

24、0001 110000001 00 01100 NFA M所能接受的符號(hào)串的全體記為 L(M). 結(jié)論： ?上一個(gè)符號(hào)串集Vì?*是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)?上的不確定的有窮自動(dòng)機(jī)M，使得V=L(M)。 (0|1)*(000|111)(0|1)* 3.3.3 NFA->DFA的轉(zhuǎn)換 DFA是NFA的特例 對(duì)每個(gè)NFA 　N一定存在一個(gè)DFA?。?，使得 L(M)=L(N)。對(duì)每個(gè)NFA N存在著與之等價(jià)的DFA M。 有一種算法，將NFA轉(zhuǎn)換成接

25、受同樣語言的DFA.這種算法稱為子集法. 與某一NFA等價(jià)的DFA不唯一. 從NFA的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造的基本思路是： DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài). DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài). 定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算： 1狀態(tài)集合I的ε-閉包，表示為ε-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達(dá)的狀態(tài)的集合。 其中: 狀態(tài)集合I的任何狀態(tài)S都屬于 ε-closure(I)。

26、2. 狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。 1 2 5 3 4 6 8 7 a a e e e e e a 狀態(tài)集合I的有關(guān)運(yùn)算的例子 I={1}, e-closure(I)={1,2}; I={5}, e-closure(I)={5,6,2}; move({1,2},a)={5,3,4}: e-closure({5,3,4})={2,3,4,5,6,7,8}; NFA確定化算法: 假設(shè)NFA N=(K, ?,f,K0

27、,Kt)按如下辦法構(gòu)造一個(gè)DFA M=(S, ?,d,S0,St)，使得L(M)=L(N)： 1. M的狀態(tài)集S由K的一些子集組成。用[S1 S2... Sj]表示S的元素，其中S1, S2,,... Sj是K的狀態(tài)。并且約定，狀態(tài)S1, S2,,... Sj是按某種規(guī)則排列的，即對(duì)于子集{S1, S2}={ S2, S1,}來說，S的狀態(tài)就是[S1 S2]； 2 M和N的輸入字母表是相同的，即是?； 3轉(zhuǎn)換函數(shù)是這樣定義的: d([S1 S2,... Sj],a)= [R1R2... Rt]其中: {R1,R2,... , Rt} = e-closure(move({S1, S

28、2,,... Sj},a)) 4 S0=e-closure(K0)為M的開始狀態(tài)； 5 St={[Si Sk... Se]，其中[Si Sk... Se]?S且{Si , Sk,,... Se}?Kt1F} 構(gòu)造NFA N的狀態(tài)K的子集的算法： 假定所構(gòu)造的子集族為C，即C= (T1, T2,,... TI),其中T1, T2,,... TI為狀態(tài)K的子集。 1 開始，令e-closure(K0)為C中唯一成員，并且它是未被標(biāo)記的。 2 while （C中存在尚未被標(biāo)記的子集T）do { 標(biāo)記T； f

29、or 每個(gè)輸入字母a do{ U:= e-closure(move(T,a))； 4 f 3 5 6 2 1 i e e e e a a a a b b b b if U不在C中 then 將U作為未標(biāo)記的子集加在C中 } NFA的確定化 例子 Ia Ib {I,1,2} S {1,2,3 } A {1,2,4} B {1,2,3} A

30、 {1,2,3,5,6,f} C {1,2,4} B {1,2,4} B {1,2,3} A {1,2,4,5,6,f} D {1,2,3,5,6,f} C {1,2,3,5,6,f} C {1,2,4,6,f} E {1,2,4,5,6,f} D {1,2,3,6,f} F {1,2,4,5,6,f} D {1,2,4,6,f}

31、 E {1,2,3,6,f} F {1,2,4,5,6,f} D {1,2,3,6,f} F {1,2,3,5,6,f} C {1,2,4,6,f} E 等價(jià)的DFA a C D B A E F S b a a a a a b b b b b a b 3.3.4確定有窮自動(dòng)機(jī)的化簡(jiǎn) 說一個(gè)有窮自動(dòng)機(jī)是化簡(jiǎn)了的，即是

32、說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是互相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。 DFA的最小化就是尋求最小狀態(tài)DFA 最小狀態(tài)DFA的含義: 1.沒有多余狀態(tài)(死狀態(tài)) 2.沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。 兩個(gè)狀態(tài)s和t等價(jià)：滿足 一致性條件(兼容性)——同是終態(tài)或同是非終態(tài) S和C等價(jià)嗎？ C和D等價(jià)嗎？ 蔓延性條件（傳播性）——從s出發(fā)讀入某個(gè)a(a)??和從

33、t出發(fā)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。 上圖中 S和C不等價(jià)，因?yàn)镃是終態(tài)，而S不是終態(tài)； C和D同是終態(tài),讀入a到達(dá)C和F, C和F同是終態(tài), C和F讀入a都到達(dá)C,讀入b都到達(dá)E.C和F等價(jià)；同樣D和E也等價(jià)；可以推出C和D等價(jià)； “分割法” DFA的最小化算法的核心 把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的. 從前面例子可知C、D、E、F等價(jià)！ DFA的最小化—例子 1.將M的狀態(tài)分成非終態(tài)和終態(tài)集 見上圖 D B A S a a a

34、b b b b {S,A,B} {C,D,E,F} 2 .尋找子集中不等價(jià)狀態(tài) {S,A,B} {C,D,E,F} {A} {S，B} b {S} {B} 3. P={{S},{A},{B},{D}} 3.4 正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性 對(duì)有窮自動(dòng)機(jī)和正規(guī)表達(dá)式進(jìn)行了上述討

35、論之后,我們介紹有窮自動(dòng)機(jī)和正規(guī)表達(dá)式的等價(jià)性,即： 1.對(duì)于∑上的一個(gè)NFA M，可以構(gòu)造一個(gè)∑上的正規(guī)式R,使得L(R)=L(M)。 2.對(duì)于∑上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)∑上的NFA M，使的L(M)=L(R)。 一.對(duì)于∑上的一個(gè)NFA M，可以構(gòu)造一個(gè)∑上的正規(guī)式R,使得L(R)=L(M)。我們把狀態(tài)轉(zhuǎn)換圖的概念拓廣，令每一條弧可用一個(gè)正規(guī)式作標(biāo)記。 第一步，在M的狀態(tài)轉(zhuǎn)換圖上加進(jìn)兩個(gè)結(jié)點(diǎn)，一個(gè)為X結(jié)點(diǎn),一個(gè)為Y結(jié)點(diǎn)，從X結(jié)點(diǎn)用e弧連接到M的所有初態(tài)結(jié)點(diǎn)，從M的所有終態(tài)結(jié)點(diǎn)用弧連接到Y(jié)結(jié)點(diǎn)，形成一個(gè)與M等價(jià)的M`, M`只有一個(gè)初態(tài)和一個(gè)終態(tài). 第二步，逐

36、步消去M`中的所有結(jié)點(diǎn)，直至只剩下X 和Y結(jié)點(diǎn) 1 3 R1R2 其消結(jié)規(guī)則如下: 1 2 3 R1 R2 ①對(duì)于 代之為 1 2 R1|R2 R1 1 2 R2 ②對(duì)于 代之為 1 3 R1R2* R3 1 2 3 R1 R2 R3 ③對(duì)于 代之為 最后X和Y結(jié)點(diǎn)間的弧上的標(biāo)記則為所求的正規(guī)式

37、。 B C 0,1 1 0 A 例： 0,1 X B C 1 0 e e A Y Y X e 0,1 A 10 X Y (0|1)*10 二.從Σ上的一個(gè)正規(guī)式R構(gòu)造Σ上的一個(gè)NFA M，使得L(M)=L(R)的方法。 下面介紹的方法稱為“語法制導(dǎo)”的方法,首先將正規(guī)式分解成一系列子表達(dá)式,然后使用如下規(guī)則為R構(gòu)造NFA，對(duì)R的各種規(guī)則具體描述如下： 對(duì)于正規(guī)式e ,構(gòu)造的NFA 對(duì)于正規(guī)式R=? ,構(gòu)造的NFA

38、 e S S F F X 對(duì)于正規(guī)式x,x ?∑構(gòu)造的NFA 對(duì)于正規(guī)式r, r= R1|R2構(gòu)造的NFA 對(duì)于正規(guī)式r, r=R1R2構(gòu)造的NFA 對(duì)于正規(guī)式r, r=R1*構(gòu)造的NFA R= (a|b)* 構(gòu)造為NFA N 還可采用另外的分解方式構(gòu)造NFA: 解：從左到右分解R， R= (a|

39、b)*ab 構(gòu)造為NFA N x y (a|b)* ab i 3 2 a 令r1=a,則有 a|b y x i e i ab e 5 4 b 令r2=b,則有 令r3=a|b,則有 a x i b e y e i b i a 3 2 a 5 4 b 1 6 e e e e 令r4=(a|b)*,則有

40、 3 2 a 5 4a e 2 e e 0 1 e e b 1 6 0 e e e e e 7 e e e 將R=(a|ab)* b b*構(gòu)造為NFA N 3.5 正規(guī)文法和有窮自動(dòng)機(jī)間的轉(zhuǎn)換 1、從正規(guī)文法構(gòu)造NFA M 字母表與G的終結(jié)符集相同。 為G的每個(gè)非終結(jié)符生成M的一個(gè)狀態(tài)，G的開始符號(hào)S是初態(tài)。 增加一個(gè)新狀態(tài)Z，作為NFA的終態(tài)。 對(duì)G中的形如A->tB的產(chǎn)生式, 其中t為終結(jié)符或e，A和B為非終結(jié)符，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t

41、)=B; 對(duì)G中的形如A->t的產(chǎn)生式,構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=Z; A S a a a e b b b B Z e 例如：求文法G[S]等價(jià)的NFA M G[S]： S->aA S->bB S-> e A-> aB A-> bA B-> aS B-> bA B-> e 2、NFA M 轉(zhuǎn)換成正規(guī)文法的規(guī)則 有窮自動(dòng)機(jī)的初態(tài)對(duì)應(yīng)文法的開始符號(hào)。 有窮自動(dòng)機(jī)的字母表為文法的終結(jié)符集。 對(duì)轉(zhuǎn)換函數(shù)f(A,t)=B，可寫一個(gè)產(chǎn)生式A->tB。 對(duì)可接受狀態(tài)Z，增加一個(gè)

42、產(chǎn)生式Z-> e B A a a b a b b D b C 例如：給出與下圖NFA等價(jià)的正規(guī)文法 G[A]： A->aB A->bD B->bC C->aA C->bD C-> e D->aB D->bD D-> e 3.6 詞法分析程序的自動(dòng)構(gòu)造工具 正規(guī)式用于說明(描述)單詞的結(jié)構(gòu)十分簡(jiǎn)潔方便。而把一個(gè)正規(guī)式編譯(或稱轉(zhuǎn)換)為一個(gè)NFA進(jìn)而轉(zhuǎn)換為相應(yīng)的DFA，這個(gè)NFA或DFA正是識(shí)別該正規(guī)式所表示的語言的句子的識(shí)別器?；谶@種方法來構(gòu)造詞法分析程序，LEX是一個(gè)廣泛使用的工具。

43、 詞法分析程序的設(shè)計(jì)技術(shù)可應(yīng)用于其它領(lǐng)域，比如查詢語言以及信息檢索系統(tǒng)等，這種應(yīng)用領(lǐng)域的程序設(shè)計(jì)特點(diǎn)是，通過字符串模式的匹配來引發(fā)動(dòng)作。 詞法分析程序的自動(dòng)構(gòu)造工具也廣泛應(yīng)用于許多方面，如用以生成一個(gè)程序，可識(shí)別印刷電路板中的缺陷，又如開關(guān)線路設(shè)計(jì)和文本編輯的自動(dòng)生成等。 本章小結(jié) 詞法分析程序是編譯第一階段的工作，它讀入字符流的源程序，按照詞法規(guī)則識(shí)別單詞，交由語法分析程序接下去。 本章講述了詞法分析程序設(shè)計(jì)原則，并介紹了分別作為正規(guī)集的描述機(jī)制和識(shí)別機(jī)制的正規(guī)式和有窮動(dòng)機(jī)。 實(shí)驗(yàn)一 · 使用自己熟悉的語言（C++），結(jié)合簡(jiǎn)單語言

44、的語法編寫一個(gè)簡(jiǎn)單的詞法分析程序 · 詞法分析程序?qū)o定一個(gè)源程序(如C語言的)能夠輸出單詞序列表。 · 要求輸入和輸出都通過文件處理。 練習(xí) · 1、將a和b分別進(jìn)行確定化和最小化 2、題：構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的DFA. DFA X A B C Y 1 0,1 1 0 1 解：1) 2)確定化 ： 3)重新命名，令A(yù)B為B、AC為C、ABY為D B C D D A C B C B B A A A X 1 0 AB AC ABY ABY A AC AB AC AB AB A A A X 1 0