第三章詞法分析

第三章詞法分析22023/3/213.1詞法分析概述一、詞法分析程序的任務(wù)二、詞法分析程序的功能三、詞法分析程序的安排四、詞法分析程序的實現(xiàn)方式五、詞法分析程序的輸出形式32023/3/21中南大學(xué)軟件學(xué)院陳志剛詞法分析程序詞法分析是編譯過程中的一個階段，在語法分析前進行，也可以和語法分析結(jié)合在一起作為一遍。輸入：源程序字符串輸出：等價的屬性字序列（內(nèi)部表示形式）3.1詞法分析概述42023/3/21中南大學(xué)軟件學(xué)院陳志剛一、詞法分析程序的任務(wù)從左至右逐個字符地掃描源程序，產(chǎn)生一個個單詞符號。把作為字符的源程序改造為單詞符號串組成的中間程序，執(zhí)行詞法分析任務(wù)的程序稱為詞法分析器或稱掃描器。3.1詞法分析概述52023/3/21中南大學(xué)軟件學(xué)院陳志剛二、詞法分析程序的功能詞法分析程序主要執(zhí)行以下功能：讀入源程序字符串，識別開具有獨立含義的最小語法單位——單詞（符號）；把單詞變換成長度統(tǒng)一的且為定長的屬性字；其他功能：濾掉空格，跳過注釋、換行符某些預(yù)加工處理3.1詞法分析概述62023/3/21中南大學(xué)軟件學(xué)院陳志剛?cè)?、詞法分析程序的安排常常把詞法分析程序作為獨立的一遍或作為被語法分析程序所調(diào)用的子程序。1、作為獨立的一遍：語法分析前進行詞法分析，把單詞符號串形成中間文件存貯。3.1詞法分析概述72023/3/21中南大學(xué)軟件學(xué)院陳志剛?cè)?、詞法分析程序的安排2、作為被語法分析器詞用的子程序：

3.1詞法分析概述82023/3/21中南大學(xué)軟件學(xué)院陳志剛相對獨立方式：把詞法分析程序作為語法分析程序的一個獨立子程序。語法分析程序需要新符號時調(diào)用這個子程序。完全獨立方式：詞法分析程序作為單獨一趟來實現(xiàn)。詞法分析程序讀入整個源程序，它的輸出作為語法分析程序的輸入。四、詞法分析程序的實現(xiàn)方式3.1詞法分析概述92023/3/21中南大學(xué)軟件學(xué)院陳志剛相對獨立方式當(dāng)采用遞歸下降分析等技術(shù)實現(xiàn)一趟編譯程序時常采用這種方式。源程序詞法分析程序語法分析程序Tokengettoken….四、詞法分析程序的實現(xiàn)方式3.1詞法分析概述102023/3/21中南大學(xué)軟件學(xué)院陳志剛完全獨立方式采用詞法分析工作完全獨立的原因：簡化設(shè)計，降低語法分析的復(fù)雜性提高編譯效率增加編譯系統(tǒng)的可移植性源程序詞法分析程序語法分析程序?qū)傩宰中蛄小?四、詞法分析程序的實現(xiàn)方式3.1詞法分析概述112023/3/21中南大學(xué)軟件學(xué)院陳志剛單詞--是程序語言的基本語法符號。如：基本字、標(biāo)識符、常數(shù)、運算符、界符等。詞法分析器中單詞的輸出形式：（單詞類別、單詞內(nèi)部碼值）五、詞法分析程序的輸出形式3.1詞法分析概述122023/3/21中南大學(xué)軟件學(xué)院陳志剛詞法分析程序輸出的單詞符號通常用二元式表示：（單詞種別，單詞自身的值）單詞種別：表示單詞種類，常用整數(shù)編碼，它是語法分析需要的單詞自身的值：是編譯中其他階段所需要的信息如果一個種別只含一個單詞符號，那么該單詞符號的種別編碼就完全代表它自身的值。如果一個種別含有多個單詞符號，那么還應(yīng)給出該單詞符號的自身值：標(biāo)識符自身值是標(biāo)識符自身的字符串；常數(shù)自身值是常數(shù)的二進制數(shù)值。五、詞法分析程序的輸出形式3.1詞法分析概述132023/3/21中南大學(xué)軟件學(xué)院陳志剛語言的單詞符號單詞符號是程序語言的基本語法單位，一般分為下面5種：關(guān)鍵字（基本字）：（個數(shù)確定，可全體編為一類，也可一字一類)標(biāo)識符：（個數(shù)不確定，作為一類）常數(shù)：各種類型的常數(shù)。(個數(shù)不確定，按類型分類)運算符：如+、-、*、/、<等。(個數(shù)確定，一符一類)界符：如，、；、（、）、:等。(個數(shù)確定,一符一類)注意：一種語言的單詞如何分類、怎樣編碼，主要取決于技術(shù)上的方便。五、詞法分析程序的輸出形式3.1詞法分析概述142023/3/21中南大學(xué)軟件學(xué)院陳志剛例：若分類表為：試分析輸入串：IFa1>0 THENb1:=c1*d1ELSEb1:=5

經(jīng)詞法分析后的輸出。五、詞法分析程序的輸出形式3.1詞法分析概述152023/3/21中南大學(xué)軟件學(xué)院陳志剛解：輸出的單詞串為：五、詞法分析程序的輸出形式3.1詞法分析概述162023/3/21中南大學(xué)軟件學(xué)院陳志剛一、狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。用結(jié)點代表狀態(tài)，狀態(tài)之間用箭弧連接，箭弧上的標(biāo)記（字符）代表在射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。一個狀態(tài)轉(zhuǎn)換圖只包含有限個狀態(tài)，有一個初態(tài)，終態(tài)用雙圈表示。一個狀態(tài)轉(zhuǎn)換圖可識別一定的字符串。

SIE字母數(shù)字字母或數(shù)字狀態(tài)都是非終結(jié)符號S：開始狀態(tài)E：終止?fàn)顟B(tài)，用雙圈表示I：標(biāo)識符狀態(tài)3.2詞法分析程序的設(shè)計例1：172023/3/21中南大學(xué)軟件學(xué)院陳志剛一、狀態(tài)轉(zhuǎn)換圖例2：例3：182023/3/21中南大學(xué)軟件學(xué)院陳志剛方法：每個結(jié)點對應(yīng)一段程序，前面狀態(tài)結(jié)的程序調(diào)用其后繼結(jié)點的程序。例1：二、狀態(tài)轉(zhuǎn)換圖的實現(xiàn)PROCEDUREProc0;Getchar;casecharof‘A’…‘Z’:proc1;‘0’…‘9’:proc2;otherwiseerror;endofcase;192023/3/21中南大學(xué)軟件學(xué)院陳志剛為了描述方便，引入一些標(biāo)準(zhǔn)過程（函數(shù)）與變量:1.全程字符變量Char：存放最新讀入的源程序字符；2.字符串TOKEN：存放構(gòu)成單詞符號的字符串；3.過程GETChar：讀入一個源程序字符，放入Char中，搜索指針前移；4.過程GETNBC：反復(fù)調(diào)用GETChar，直接讀入的Char<>’’為止；5.過程CONCAT：把Char中字符連到TOKEN末尾去；6.函數(shù)Letter/digit：判別Char中是否為字母/數(shù)字；7.過程Return(c,val);8.過程Retract：搜索器指針回拔一個字符。

二、狀態(tài)轉(zhuǎn)換圖的實現(xiàn)202023/3/21中南大學(xué)軟件學(xué)院陳志剛例2：PROCEDUREPro0;BEGINGetchar;IFcharIN[‘A’..‘Z’]thenpro1elseerror;END;Procedurepro1;begingetchar;whilecharIN[‘A’..‘Z’,‘o’..‘g’]DObeginconcat;getchar;End;pro2;End;procedurepro2;beginretract;return(101,TOKEN);end;212023/3/21中南大學(xué)軟件學(xué)院陳志剛?cè)?、為正則文法構(gòu)造狀態(tài)轉(zhuǎn)換圖什么是正則文法？（U::=T或U::=WT）步驟如下：以S為開始狀態(tài)作結(jié)點；把文法中的每一個非終結(jié)符號作為狀態(tài)結(jié)點；對于形如Q::=T的每個規(guī)則，引一條開始狀態(tài)S到狀態(tài)Q的弧，弧上標(biāo)記為T；對于形如Q::=RT的規(guī)則引一條從狀態(tài)R到Q的弧，弧上標(biāo)記為T，其中R為非終結(jié)符號，T為終結(jié)符號。以識別符號為終止?fàn)顟B(tài)。222023/3/21中南大學(xué)軟件學(xué)院陳志剛構(gòu)造狀態(tài)轉(zhuǎn)換圖舉例例如：對于正則文法G[Z]：

Z::=Za|Aa|BbA::=Ba|aB::=Ab|bSABabSABaZZaSABabZbaabaaaba(1)(2)(3)232023/3/21中南大學(xué)軟件學(xué)院陳志剛四、應(yīng)用狀態(tài)轉(zhuǎn)換圖識別句子如果x是相應(yīng)文法的句子便必須能從開始狀態(tài)出發(fā)，順著弧的方向行進到終止?fàn)顟B(tài)。其步驟如下:(1)從開始狀態(tài)開始，以它作為當(dāng)前狀態(tài)，并從x的最左字符開始重復(fù)步驟2，直到到達x的右端為止；

(2)掃描x的下一字符，在當(dāng)前狀態(tài)射出的各個弧中找出標(biāo)記有該字符的弧，并沿此弧前進，以達到的狀態(tài)作為下一當(dāng)前狀態(tài)。步驟2存在的兩種可能：可能找不到一條弧的標(biāo)記與當(dāng)前字符相同；總能找到一個弧，其標(biāo)記與當(dāng)前字符相同。242023/3/21中南大學(xué)軟件學(xué)院陳志剛應(yīng)用狀態(tài)轉(zhuǎn)換圖識別句子舉例例如：對于正則文法G[Z]：

Z::=Za|Aa|BbA::=Ba|aB::=Ab|babSABabZbaaabSABabZbaa(1)識別字符串a(chǎn)babaaaFba,b(2)識別字符串bababbb252023/3/21中南大學(xué)軟件學(xué)院陳志剛狀態(tài)轉(zhuǎn)換圖識別句子的實質(zhì)是一個規(guī)約過程，運用自底向上的識別算法：如：

SA與AZ表示：a直接規(guī)約為A，Aa直接規(guī)約為Z。從開始狀態(tài)S出發(fā)逐步到達終止?fàn)顟B(tài)Z的過程，也是從終結(jié)符號串出發(fā)，規(guī)約到非終結(jié)符號的過程。262023/3/21中南大學(xué)軟件學(xué)院陳志剛對句子ababaaa的分析步驟當(dāng)前狀態(tài)輸入的其余部分

SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZababaaaABABAZZ(a)分析過程(b)語法樹272023/3/21中南大學(xué)軟件學(xué)院陳志剛五、用狀態(tài)轉(zhuǎn)換圖為正則語言構(gòu)造正則文法從上面狀態(tài)轉(zhuǎn)換圖，可得到相應(yīng)的正則文法：

G[Z]:Z::=CbC::=Bb|bB::=AbA::=Ba|aSABCZabbbba例如：正則語言{(ab)nb2|n≥0}

基于其句子的一般形式，為其構(gòu)造狀態(tài)轉(zhuǎn)換圖：282023/3/21中南大學(xué)軟件學(xué)院陳志剛六、轉(zhuǎn)換系統(tǒng)定義：轉(zhuǎn)換系統(tǒng)是具有下列三個特征的狀態(tài)轉(zhuǎn)換圖，即

1)開始狀態(tài)S和終止?fàn)顟B(tài)Z唯一;2)無弧進入S，也無弧自Z射出；

3)可能存在標(biāo)記為空串（ε）的弧。轉(zhuǎn)換系統(tǒng)與狀態(tài)轉(zhuǎn)換圖的區(qū)別：ε弧SS1S2ZεεAZ2Z1εε292023/3/21中南大學(xué)軟件學(xué)院陳志剛一、基本概念二、確定有窮狀態(tài)自動機（DFA）三、非確定有窮狀態(tài)自動機（NFA）四、NFA和DFA的轉(zhuǎn)換五、正規(guī)式和有限自動機的等價性六、DFA的化簡3.3正規(guī)式與有限自動機302023/3/21中南大學(xué)軟件學(xué)院陳志剛一、基本概念1.字母表Σ：元素的非空有限集合。如Σ={‘A’,‘B’,‘O’}2.字符：字母表Σ的一個元素稱為一個字符（符號）3.Σ上的字：

Σ上字符的有窮序列；例：Σ={a,b,c}4.空字ε：不含任何字符的字5.字的長度：|α|6.Σ上字的全體：Σ*7.字的連接：字α與字β的連接記為αβ3.3正規(guī)式與有限自動機312023/3/21中南大學(xué)軟件學(xué)院陳志剛一、基本概念8.字的方冪：字α的n次連接稱為α的n次方冪,記為,特別地=ε9.字的集合A與B的乘積：記作,其中10.Σ*子集的方冪：

Ao={ε},A1=A,…,11.Σ*子集的正則閉包：12.Σ*子集的閉包：3.3正規(guī)式與有限自動機322023/3/21中南大學(xué)軟件學(xué)院陳志剛正規(guī)式與正規(guī)集正規(guī)集是字母表Σ上的一個特殊字集，通常我們借助正規(guī)式來描述它。關(guān)于正規(guī)式與正規(guī)集的定義是遞歸的。1.ε和φ都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和φ2.任何a∈Σ,a是Σ上的正規(guī)式，它所表示的正規(guī)式為{α}3.假定u和v是正規(guī)式，它們所代表的正規(guī)集分別是L(u)和L(v)，則u|v,uv,u*都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(u)∪L(v),L(u)L(v),L(u)*僅由有限次使用上述三步而定義的表達式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集332023/3/21中南大學(xué)軟件學(xué)院陳志剛正規(guī)式與正規(guī)集優(yōu)先級遞增：

|(或)，·（直接），*,（正規(guī)式） ∪,∩,*’,（正規(guī)集）例1.Σ={0,1}，則正規(guī)式有0,1,ε,1*,|0|,…，正規(guī)集有{0},{1},{ε},φ,{1}*,…若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價才是Σ上的正規(guī)集342023/3/21中南大學(xué)軟件學(xué)院陳志剛正規(guī)式的性質(zhì)：1．交換律：U|V=V|U

證：L(u|v)=L(u)∪L(v)=L(v)∪L(u)=L(v|u)

因此，u|v=v|u 2．結(jié)合律：(u|v)|w=u|(v|w),(uv)w=u(vw)3．分配律：u(v|w)=uv|uw,(u|v)w=u(vw)4． εu=uε=u

證：L(εu)=L(ε)L(u)=L(u)0L(u)=L(u)

352023/3/21中南大學(xué)軟件學(xué)院陳志剛二、確定型有窮狀態(tài)自動機一個確定的有窮自動機（DFA）D是一個五元組：D=（K，Σ，M，S，F(xiàn)）其中

K：有窮非空的狀態(tài)集合；Σ：有窮非空的輸入符號字母表；

M：轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映像，即，如M(ki,a)=kj,(ki∈K,kj∈K)就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；

S∈K是唯一的一個初態(tài)；

FK是非空的終態(tài)集合。362023/3/21中南大學(xué)軟件學(xué)院陳志剛例1．DFAM=({0,1,2},{a,b},f,0,{2})，其中δ(s,a)=S,δ(s,b)=2,s=0,1,2注：一個DFA可表示為一個狀態(tài)轉(zhuǎn)換矩陣，行表示狀態(tài)，列表示輸入字符，矩陣元素M[s,a]的值為δ(s,a)。例2．二、確定型有窮狀態(tài)自動機372023/3/21中南大學(xué)軟件學(xué)院陳志剛一個DFAM也可用一張狀態(tài)轉(zhuǎn)換圖表示，DFA的每個狀態(tài)對于狀態(tài)轉(zhuǎn)換圖的一個接點，圖中箭弧上的標(biāo)記為輸入字符，若δ(s,a)=S’，則從狀態(tài)s畫一條箭弧到S’，弧上標(biāo)記為a。對Σ*中的任何字α，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上標(biāo)記連接成的字等于α，則稱α可為DFAM所識別，或稱DFAM可讀出（或接受、識別）字α。DFAM識別的字的全體記為L(M)。二、確定型有窮狀態(tài)自動機382023/3/21中南大學(xué)軟件學(xué)院陳志剛?cè)绻粋€DFAM的輸入字母表為∑，則我們也稱M是∑上的一個DFA?？梢宰C明：∑上的一個子集是正規(guī)的，當(dāng)且僅當(dāng)存在∑上的DFAM，使得V=L（M）。DFA的確定性表現(xiàn)在映射δ：S×Σ→S是一個單值函數(shù)。也就是說，對任何狀態(tài)s∈S和輸入符號a∈Σ，δ(s,a)唯一地確定了下一狀態(tài)。特別地，若DFAM的初態(tài)同時又是終態(tài)，改DFAM可識別空字ε。顯然，若DFAM中字母表Σ含n個字母，則任何一個狀態(tài)頂多只有n條發(fā)出弧。

二、確定型有窮狀態(tài)自動機392023/3/21中南大學(xué)軟件學(xué)院陳志剛從狀態(tài)轉(zhuǎn)換圖構(gòu)造有窮狀態(tài)自動機例如：從下面狀態(tài)圖構(gòu)造DFADFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）其中M定義為：

M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z abSABabZbaa402023/3/21中南大學(xué)軟件學(xué)院陳志剛運行DFA與識別一個字符串?dāng)U充的映像M定義：

M(R,ε)=RM(R,Tt)=M(M(R,T),t)，其中t∈Σ*，

T∈Σ以上兩個式子的含義是什么？定義：對于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，則稱符號串t可被DFAD所接受。運行一個DFA的過程：識別一個符號串是否被接受412023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例如前例：DFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）

M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z

則：M(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(A,baa)=M(B,aa)=M(A,a)=Z422023/3/21中南大學(xué)軟件學(xué)院陳志剛正則集正則集：L(D)，是一個DFA接受的字符串集合正則語言與正則集：L(G)=L(D)最小狀態(tài)自動機：狀態(tài)個數(shù)最少，唯一如何減少自動機的狀態(tài)數(shù)而不改變自動機所接受的語言呢？432023/3/21中南大學(xué)軟件學(xué)院陳志剛?cè)绾卧谟嬎銠C內(nèi)表示映像？映像M：含義？映像在計算機內(nèi)的表示法：矩陣表示法表結(jié)構(gòu)表示法442023/3/21中南大學(xué)軟件學(xué)院陳志剛DFA的矩陣表示法字符狀態(tài)abSABabZbaa矩陣行代表狀態(tài)，列代表輸入字符，矩陣元素是映像得到的新狀態(tài)。452023/3/21中南大學(xué)軟件學(xué)院陳志剛表結(jié)構(gòu)表示法狀態(tài)名射出的弧數(shù)標(biāo)記1指向的下一狀態(tài)1…標(biāo)記K指向的下一狀態(tài)k對每一個狀態(tài)結(jié)點而言若某結(jié)點有K個射出的弧，則相應(yīng)表長為2k+2462023/3/21中南大學(xué)軟件學(xué)院陳志剛引入M(R,T)是K×Σ到K的單值函數(shù)，即唯一確定下一狀態(tài)如果在當(dāng)前狀態(tài)下，同一個輸入字符確定的下一狀態(tài)不止一個呢？如V::=UTW::=UTUWVTTabSABabZbaaaa例如：文法G3.2:Z::=Za|Aa|BbA::=Ba|Za|aB::=Ab|Ba|b三、非確定有窮狀態(tài)自動機472023/3/21中南大學(xué)軟件學(xué)院陳志剛一個非確定的有窮自動機（NFA）D是一個五元組：N=（K，Σ，M，S，F(xiàn)）其中K：有窮非空的狀態(tài)集合；Σ：有窮非空的輸入字母表；M：轉(zhuǎn)換函數(shù)，是在K×Σ到K的子集所組成集合的映像，M(R,T)={Q1,Q2,….Qn}SK是非空的初態(tài)集合；FK是非空的終態(tài)集合.三、非確定有窮狀態(tài)自動機482023/3/21中南大學(xué)軟件學(xué)院陳志剛DFA與NFA的區(qū)別DFANFA開始狀態(tài)唯一一個或多個映像單個狀態(tài)狀態(tài)集合492023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例前述文法G3.2對應(yīng)的自動機NFAN=({S,A,B,Z},{a,b},M,{S},{Z})其中M：M(S,a)={A}M(S,b)={B}M(A,a)={Z}M(A,b)={B}M(B,a)={A,B}M(B,b)={Z}M(Z,a)={A,Z}abSABabZbaaaa502023/3/21中南大學(xué)軟件學(xué)院陳志剛擴充映像定義：

M(R,ε)={R}R為任意的狀態(tài)

M(R,Tt)=M(Q1,t)∪M(Q2,t)∪…∪M(Qn,t)

其中t∈Σ*，T∈Σ，M(R,T)={Q1,Q2,….Qn}M(R,Tt)=M({Q1,Q2,…,Qn},t)=∪M(Qi,t)512023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例(字符串被NFA所接受)對于輸入字符串babbabb，運行G3.2的NFA步驟當(dāng)前狀態(tài)輸入的其余部分可能的后繼選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ522023/3/21中南大學(xué)軟件學(xué)院陳志剛運行NFA運行NFA：識別一個字符串是否被NFA所接受，是否能達到終態(tài)集合中的某個狀態(tài)實質(zhì)：用自底向上方法識別句子狀態(tài)轉(zhuǎn)換的下一狀態(tài)不唯一，如何解決？532023/3/21中南大學(xué)軟件學(xué)院陳志剛單狀態(tài)M(R,T)={Q1,Q2,…,Qn}變?yōu)镸(R,T)=[Q1,Q2,…,Qn]（單狀態(tài)）表示當(dāng)前狀態(tài)為R輸入字符T時，下一狀態(tài)可能是這些狀態(tài)中的某一狀態(tài)。542023/3/21中南大學(xué)軟件學(xué)院陳志剛怎樣把NFA變?yōu)镈FA?定理3.6NFAN=(K,Σ,M,S,F)對應(yīng)DFAN’=(K’,Σ,M’,S’,F’)其中K’是有窮非空狀態(tài)集合，由k的一切子集組成；用[Q1,Q2,…,Qm]表示K’的元素，Qi∈KM’([R1,R2,…,Ri],T)=[Q1,Q2,….Qj]S’=[S1,S2,…,Sn]F’={[Sj,Sk,…,Sl]|[Sj,Sk,…,Sl]∈K’,[Sj,Sk,…,Sl]∩F≠φ}則L(N)=L(N’)四、NFA與DFA的轉(zhuǎn)換552023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例例:為NFAN=({S,A,B,Z},{a,b},M,{S},{Z})構(gòu)造DFA.

設(shè)它對應(yīng)的DFAN’=(K’,{a,b},M’,[S],F’)abSABabZbaaaaK’={[S]}M([S],a)=[A]M([S],b)=[B]K’={[S],[A],[B]}M([A],a)=[Z]M([A],b)=[B]M([B],a)=[AB]M([B],b)=[Z]K’={S],[A],[B],[Z],[AB]}M([Z],a)=[AZ]M([Z],b)=φM([AB],a)=[ABZ]M([AB],b)=[BZ]K’={S],[A],[B],[Z],[AB],[AZ],[BZ],[ABZ]}M([AZ],a)=[AZ]M([AZ],b)=[B]M([BZ],a)=[ABZ]M([BZ],b)=[Z]M([ABZ],a)=[ABZ]M([ABZ],b)=[BZ]562023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例（續(xù)1）

輸入狀態(tài)ab[S][A][B][A][Z][B][B][AB][Z][Z][AZ][AB][ABZ][BZ][AZ][AZ][B][BZ][ABZ][Z][ABZ][ABZ][BZ]abSABabZbaaaa根據(jù)左邊狀態(tài)轉(zhuǎn)換矩陣，可以得到DFAN’的狀態(tài)集合（表的左列狀態(tài)），即K’={[S],[A],[b],[Z],[AB],[AZ],[BZ],[ABZ]}572023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例（續(xù)2）SBABABZAZBZAZbbbbbbbaaaaaaaa開始狀態(tài):[S]終止?fàn)顟B(tài):[Z],[AZ],[BZ],[ABZ]

根據(jù)上面狀態(tài)轉(zhuǎn)換矩陣，同時可以得到N’的映像函數(shù)，根據(jù)該映像可以畫出它的狀態(tài)轉(zhuǎn)換圖（如下）。終態(tài)集合中的元素為：由新映像得到的狀態(tài)、且這些狀態(tài)包含原NFAN的終態(tài)集合中的狀態(tài)。582023/3/21中南大學(xué)軟件學(xué)院陳志剛1．Σ上NFAM所能識別的字的全體是Σ上的一個正規(guī)集證明：設(shè)轉(zhuǎn)換圖中每條弧上可用一個正規(guī)式作標(biāo)記，讓NFAM的轉(zhuǎn)換圖中加進兩節(jié)點X和Y，形成新的NFAM’，從X畫ε弧指向原NFAM的所有初態(tài)，從原NFAM的所有終態(tài)畫ε弧指向Y，顯然L(M)=L(M’)

然后，對NFAM’消結(jié)，直至只剩下X、Y兩個結(jié)點為止，符上標(biāo)記為一正規(guī)式。所以，NFAM’識別的為一正規(guī)式；NFAM識別的是一正規(guī)集。

五、正規(guī)式和有限自動機的等價性592023/3/21中南大學(xué)軟件學(xué)院陳志剛消結(jié)規(guī)則為五、正規(guī)式和有限自動機的等價性602023/3/21中南大學(xué)軟件學(xué)院陳志剛例1.消結(jié)點⑤五、正規(guī)式和有限自動機的等價性例2.消結(jié)點①612023/3/21中南大學(xué)軟件學(xué)院陳志剛2．對于Σ上的每個正規(guī)集V，存在一個Σ上的DFAM，使得V=L(M)。證明：第一步，用替代辦法構(gòu)造一個NFAM’，使V=L(M’)，因為正規(guī)集V可用正規(guī)式u來描述，而u由一系列單個字符連接而成，故可用下述方法分解之：五、正規(guī)式和有限自動機的等價性SZe1e2SZe1e2SZe1|e2SZ{e}SZSZe1e2e622023/3/21中南大學(xué)軟件學(xué)院陳志剛具體方法：構(gòu)造如下轉(zhuǎn)換圖：逐步分解，便可得到一個NFAM’，有L(u)=V=L(M’)。例1．第二步，把NFAM’確定化為DFAM，得證。五、正規(guī)式和有限自動機的等價性632023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例例：正則表達式(A|B){A|B|0|1}的轉(zhuǎn)換系統(tǒng)的構(gòu)造過程如下：SZ(A|B){A|B|0|1}SZ(A|B){A|B|0|1}SZABA|B|0|1SZAB10AB642023/3/21中南大學(xué)軟件學(xué)院陳志剛概念1.假設(shè)I是NFAM’的狀態(tài)集的一個子集，我們定義ε-CLOSURE(I)為（I的ε-閉包）。（1）若S∈I，則S∈ε-CLOSURE(I)（2）若S∈I，則從s出發(fā)經(jīng)過任意條ε弧而達到的狀態(tài)s’，有s’∈ε-CLOSURE(I)例1.五、正規(guī)式和有限自動機的等價性若I={1,3}，則ε-CLOSURE(I)={1,3,2,8}652023/3/21中南大學(xué)軟件學(xué)院陳志剛概念2.假定I是M’的狀態(tài)子集，a是Σ中的字符，定義Ia=ε-CLOSURE(J),其中J是I中任意狀態(tài)出發(fā)（跳過前面任意多條ε弧），經(jīng)過一條a弧而能達到的狀態(tài)結(jié)的全體。例2．同例1DFA，Ia={5,6,2}利用概念1和概念2，便可把NFA確定化。五、正規(guī)式和有限自動機的等價性662023/3/21中南大學(xué)軟件學(xué)院陳志剛五、正規(guī)式和有限自動機的等價性令，構(gòu)造一張如下的表，此表第0列為狀態(tài)子集I，第1至m列分別為狀態(tài)子集，設(shè)第一行第0列為ε-CLOSURE(X),，其中X為NFAM’的初態(tài)，求出第一個的，如果某個Iai(i=1,…,m)未曾在第0列中列出，則把Iai補入狀態(tài)子集集合I中，即列于第0列新的一行。重復(fù)上述各步，直至所有行的Iai(i=1,…,m)均在第0列I中出現(xiàn)過為止。這種循環(huán)必將在有限步內(nèi)中止。（因為S是有限狀態(tài)集，所以S中狀態(tài)的組合數(shù)也是有限的）

672023/3/21中南大學(xué)軟件學(xué)院陳志剛顯然，這張表可以看成一個狀態(tài)轉(zhuǎn)換表，也就是說可把I中每個子集看成一個狀態(tài)，而狀態(tài)轉(zhuǎn)換表唯一地刻劃了一個DFAM，其初態(tài)為該表的第1行第0列，含有原NFAM’終態(tài)的子集為新的終態(tài)。（證畢）推論：一個子集是正規(guī)的，當(dāng)且僅當(dāng)它可由一個DFA（或NFA）所識別。五、正規(guī)式和有限自動機的等價性682023/3/21中南大學(xué)軟件學(xué)院陳志剛例：設(shè)計一個DFAM，它識別二進制偶數(shù)（不以0開頭的無符號數(shù)）解：1． 寫出正規(guī)式1（1|0）*02． 畫出NFAM’

細化為：3.確定化為DFAM五、正規(guī)式和有限自動機的等價性692023/3/21中南大學(xué)軟件學(xué)院陳志剛五、正規(guī)式和有限自動機的等價性或：702023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例正則表達式{a}|{(a|b)a}的相應(yīng)轉(zhuǎn)換系統(tǒng)與狀態(tài)轉(zhuǎn)換圖的構(gòu)造過程。AB{a}|{(a|b)a}AB{(a|b)a}{a}ABDCa(a|b)a

ABDCaa

Eab(a)(b)(c)(d)開始狀態(tài)：A終止?fàn)顟B(tài)：B712023/3/21中南大學(xué)軟件學(xué)院陳志剛前例續(xù)NFAN=({A,C,D,E},{a,b},M,{A,C,D},{A,C,D})M:M(A,a)={C,E}M(A,b)={E}M(C,a)={C}M(D,a)={E}M(D,b)={E}M(E,a)={D}ABDCaa

EabACaaa

b(e)(f)DaEab開始狀態(tài)：A,B終止?fàn)顟B(tài)：B,C,D開始狀態(tài)：A,C,D終止?fàn)顟B(tài)：A,C,D722023/3/21中南大學(xué)軟件學(xué)院陳志剛正則表達式的值與有窮自動機所接受的語言定理3.11：上的NFAA所接受的字符串集合L(A)是上的某個正則表達式e的值，即L(A)=|e|。例:NFAN相應(yīng)的狀態(tài)轉(zhuǎn)換圖為圖(a)，則N所接受的語言為合成所得到的正則表達式

{(aa|bb)|(ab|ba){aa|bb}(ab|ba)}的值。ZTab,baab,baaa,bbaa,bb(a)ZTab|baab|baaa|bbaa|bbXY

(b)732023/3/21中南大學(xué)軟件學(xué)院陳志剛前例續(xù)正則表達式與有窮狀態(tài)自動機是等價的。Zaa|bbXY

(ab|ba){aa|bb}(ab|ba)XY(d)(c){(aa|bb)|(ab|ba){aa|bb}(ab|ba)}742023/3/21中南大學(xué)軟件學(xué)院陳志剛字符串W把狀態(tài)P和狀態(tài)Q區(qū)別開：等價狀態(tài)：無法區(qū)別開的兩個狀態(tài)基本思想：把狀態(tài)集劃分成互不相交的子集，使子集中的狀態(tài)是等價的化簡DFA的算法步驟：劃分狀態(tài)集合并狀態(tài):取每組狀態(tài)中的代表狀態(tài)，刪去其他等價狀態(tài)若有死狀態(tài)或不可達狀態(tài)，則把它們刪去。死狀態(tài)：無法達到終止?fàn)顟B(tài)的非終止?fàn)顟B(tài)不可達狀態(tài)：不能從開始狀態(tài)達到它的那些狀態(tài)六、DFA的化簡752023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例劃分狀態(tài)集為{4}和{0,1,2,3}對于{0,1,2,3}和輸入字符a和b:M(0,a)={1}M(1,a)={1}M(2,a)={1}M(3,a)={1}M(0,b)={2}M(1,b)={3}M(2,b)={2}M(3,b)={4}只有狀態(tài)3在輸入為b時映像的后繼狀態(tài)不在{0,1,2,3}中，因此該狀態(tài)集劃分為{3}和{0,1,2}對于{0,1,2}:狀態(tài)1在輸入為b時的后繼狀態(tài)不在{0,1,2}中，因此劃分為{1}和{0,2}02314bbbbbaaaaa對于{0,2}:對于相同輸入字符，該子集中每一狀態(tài)映像得到的后繼狀態(tài)都相同，因此不再可劃分最后劃分為：

{4}{3}{1}{0,2}六、DFA的化簡762023/3/21中南大學(xué)軟件學(xué)院陳志剛舉例（續(xù)1）對于劃分結(jié)果{4},{3},{1},{0,2}，把{0,2}合并為一個狀態(tài)，其狀態(tài)轉(zhuǎn)換圖如圖：0213aaaabbb02314bbbbbaaaaab六、DFA的化簡772023/3/21中南大學(xué)軟件學(xué)院陳志剛構(gòu)造詞法分析程序的方法用手工方式，即根據(jù)識別語言單詞的狀態(tài)轉(zhuǎn)換圖，使用某種高級語言，例如，C語言直接編寫詞法分析程序。利用自動生成工具LEX自動生成詞法分析程序。3.4詞法分析程序的實現(xiàn)782023/3/21中南大學(xué)軟件學(xué)院陳志剛詞法分析程序?qū)崿F(xiàn)中要考慮的問題確定實現(xiàn)詞法分析程序的執(zhí)行方式確定屬性字的結(jié)構(gòu)緩沖區(qū)預(yù)處理，超前搜索,關(guān)鍵字的處理，符號表的實現(xiàn)查找效率，算法的優(yōu)化實現(xiàn)詞法錯誤處理3.4詞法分析程序的實現(xiàn)792023/3/21中南大學(xué)軟件學(xué)院陳志剛屬性字詞法分析程序?qū)φf明部分不做語義處理。詞法分析程序輸出屬性字一般采用下面的形式：（符號類，符號值）屬性字是符號的機內(nèi)表示，有統(tǒng)一固定的長度3.4詞法分析程序的實現(xiàn)802023/3/21中南大學(xué)軟件學(xué)院陳志剛源程序的輸入在內(nèi)存開辟緩沖區(qū)，將程序文本放進該緩沖區(qū)預(yù)處理：刪除無用字符等詞法分析程序?qū)彌_區(qū)掃描時，設(shè)置兩個指示器，一個指向當(dāng)前正在識別的單詞的開始位置，稱為起始指針；另一個用于向前搜索，以尋找單詞的終點，稱為掃描指針。起始指針?biāo)阉髦羔?.4詞法分析程序的實現(xiàn)812023/3/21中南大學(xué)軟件學(xué)院陳志剛超前搜索詞法分析程序在讀取單詞時，為了判斷是否已讀入整個單詞的全部字符，常采取向前多讀取字符并通過讀取的字符來判別，即所謂超前搜索技術(shù)。3.4詞法分析程序的實現(xiàn)822023/3/21中南大學(xué)軟件學(xué)院陳志剛關(guān)鍵字的識別與查表算法對于關(guān)鍵字，先把它們當(dāng)成標(biāo)識符，然后去查關(guān)鍵字表。若在表中查到，則為關(guān)鍵字，獲取相應(yīng)的類別碼；否則，認為是標(biāo)識符。查找算法：線性查找折半查找Hash函數(shù)3.4詞法分析程序的實現(xiàn)832023/3/21中南大學(xué)軟件學(xué)院陳志剛出錯處理對定義外的（如，對首字符不是字母的，不是數(shù)字的，不是運算符和分界符的）單詞進行出錯處理。3.4詞法分析程序的實現(xiàn)842023/3/21中南大學(xué)軟件學(xué)院陳志剛使用狀態(tài)圖設(shè)計詞法分析程序多數(shù)語言的詞法規(guī)則可用正則文法和正則表達式來描述。正則文法或正則表達式定義的語言都可以被狀態(tài)圖識別。使用狀態(tài)圖設(shè)計詞法分析程序的步驟如下：對程序設(shè)計語言的單詞按類構(gòu)造相應(yīng)的狀態(tài)圖。（這里把關(guān)鍵字與標(biāo)識符作為一類）合并各類單詞的狀態(tài)圖，增加一個出錯處理終態(tài)，構(gòu)成一個識別該語言所有單詞的狀態(tài)轉(zhuǎn)換圖對狀態(tài)圖的每一個終點編一段相應(yīng)的子程序。3.4詞法分析程序的實現(xiàn)852023/3/21中南大學(xué)軟件學(xué)院陳志剛201字母字母|數(shù)字其它3456數(shù)字?jǐn)?shù)字其它+-78*/9101113<=>:;1617其它13=舉例862023/3/21中南大學(xué)軟件學(xué)院陳志剛本節(jié)討論：用正規(guī)式描述單詞符號，并研究如何從正規(guī)產(chǎn)生識別這些單詞符號的詞法分析程序。3.5詞法分析器的自動生成872023/3/21中南大學(xué)軟件學(xué)院陳志剛一、LEX語言一個LEX語言程序經(jīng)過編譯后得到的結(jié)果程序，其作用相當(dāng)于一個DFA，可用來識別和產(chǎn)生單詞也就是說其功能即為一個詞法分析器。882023/3/21中南大學(xué)軟件學(xué)院陳志剛一個LEX源程序包括兩部分：輔助定義式和識別規(guī)則1、輔助定義式

D1→R1

Dn→Rn

其中Ri為正規(guī)式，只允許出現(xiàn)∑上字符D1,…,Di-1；Di為這個正規(guī)式Ri的簡名例1．Letter→A|B|…|ZDigit→0|1|…|9Id→Letter(Letter|Digit)*...892023/3/21中南大學(xué)軟件學(xué)院陳志剛2.識別規(guī)則

P1{A1}...Pm{Am}其中，Pi稱為詞形，為正規(guī)式(∑∪{D1,…,Dm})