第3章詞法分析

1第3章詞法分析

人們理解一篇文章（或一個程序）起碼是在單詞的級別上來思考的。同樣，編譯程序也是在單詞的級別上來分析和翻譯源程序的。

詞法分析的必要性描述單詞的結(jié)構(gòu)比其它語法結(jié)構(gòu)簡單，僅用3型文法就夠了；將單詞識別從語法分析識別分離出來，可采用更有效的工具實(shí)現(xiàn)；有些語言的單詞識別與前后文相關(guān)，不宜將其與語法分析合并；使編譯程序各部分獨(dú)立出來，有利于設(shè)計(jì)、調(diào)試和維護(hù)執(zhí)行詞法分析的程序稱為詞法分析器（掃描器）的輸出是語法分析程序的輸入本章討論詞法分析程序的手工構(gòu)造方法和自動構(gòu)造方法。2教學(xué)內(nèi)容§3.1詞法分析程序§3.2單詞的描述工具§3.3有窮自動機(jī)§3.4正規(guī)文法和有窮自動機(jī)間的等價(jià)§3.5正規(guī)文法和有窮自動機(jī)間的轉(zhuǎn)換§3.6詞法分析程序的設(shè)計(jì)3學(xué)習(xí)目標(biāo):掌握：詞法分析程序的構(gòu)造，正規(guī)式和正規(guī)文法到有窮自動機(jī)的轉(zhuǎn)換，NFA到DFA的轉(zhuǎn)換、DFA的化簡理解：正規(guī)文法、正規(guī)式、DFA的概念、NFA的概念了解：詞法分析程序的自動構(gòu)造工具4§3.1詞法分析程序詞法分析器的功能是輸入源程序，輸出單詞符號。通常把詞法分析程序設(shè)計(jì)為語法分析程序的子程序。每當(dāng)語法分析程序需要一個單詞符號時(shí)，就向詞法分析程序發(fā)出“取下一個單詞符號”的調(diào)用命令。詞法分析程序就從輸入字符串中，識別出一個具有獨(dú)立意義的單詞符號，并傳送給語法程序。字符串表示的

源程序詞法分析器語法分析器字符單詞符號取下一個

單詞符號1.詞法分析器的功能和輸出形式5單詞符號是一個程序語言的基本語法符號。稱作token(記號)

具有獨(dú)立意義的最小語法單位。語言的單詞符號詞法分析程序是以字符串形式的源程序作為輸入，以單詞符號或單詞符號表示的源程序作為輸出。將字符組合成記號與在一個英語句子中將字母構(gòu)成單詞并確定單詞的含義很相像，此時(shí)的任務(wù)很像拼寫。6關(guān)鍵字：是由程序語言定義的具有固定意義的標(biāo)識符，也稱保留字或基本字。如Pascal中的begin、end、if、integer等，C中的if、else、do、while，C++中的class、int、switch、break等都是保留字，它們一般不用作一般標(biāo)識符。標(biāo)識符：用來表示各種名字，如變量名、常量名、數(shù)組名、函數(shù)名、子程序名等。常數(shù)：程序中出現(xiàn)的各種類型的常量。常量的類型一般有整型、實(shí)型、布爾型、字符型等。如125、0.718、TRUE、“Hello”等。運(yùn)算符：表達(dá)式中連接運(yùn)算對象的符號。如+、-、*、/、<等。界符：程序中的定界符。如逗號、分號、括號、/*、*/等。程序語言的單詞符號一般可分為下列五種：7詞法分析程序輸出單詞的形式詞法分析器所輸出的單詞符號常常表示成如下的二元式： （單詞種別，單詞符號的屬性值）單詞種別（它是語法分析需要的信息）

通常用整數(shù)編碼。

一個語言的單詞符號如何分種，分成幾種，怎樣編碼，是一個技術(shù)性的問題。它主要取決于處理上方便。

標(biāo)識符一般統(tǒng)歸為一種。

常數(shù)則按類型分種。

關(guān)鍵字可將其全體視為一種，也可以一字一種。采用一字一種的分法實(shí)際處理起來較為方便。運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算符視為一種。

至于界符一般用一符一種的分法。8單詞自身的值（單詞符號的屬性值，它是編譯其它階段需要的信息）

屬性值是指單詞符號的特性或特征，可以是標(biāo)識符在符號表的入口地址、數(shù)值的二進(jìn)制值等。如果是一符一種的分法，詞法分析器只給出其種別編碼，不給出其屬性值。如果一個種別含有多個單詞符號，那么對于它的每個單詞符號，除了給出種別編碼之外，還應(yīng)給出導(dǎo)出符號的屬性值，以便把同一種類的單詞區(qū)別開來。

標(biāo)識符屬性值是自身的符號串；也可是在符號表的入口地址。

常數(shù)自身值是常數(shù)的二進(jìn)制數(shù)值。9【例】試給出程序段if(a>1)b=100;輸出的單詞符號串。假定基本字、運(yùn)算符和界符都是一符一種，標(biāo)識符自身的值是字符串，常數(shù)是二進(jìn)制值。(2,)基本字if(29,)左括號((10,‘a(chǎn)’)標(biāo)識符a(23,)大于號>(11,‘1’的二進(jìn)制)常數(shù)1(30，)右括號)(10,‘b’)標(biāo)識符b(17,)賦值號=(11,‘100’的二進(jìn)制)常數(shù)100(26,)分號;10經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：

(while,-)

(( ,-)

(id,指向i的符號表表項(xiàng)的指針)

(>=,-)

(id,指向j的符號表表項(xiàng)的指針)

(),-)

(id,指向i的符號表表項(xiàng)的指針)

(--,-)

(；,-)【例】考慮下述C++代碼段：

while(i>=j)i--; 另一種表示假定基本字、運(yùn)算符和界符都是一符一種，標(biāo)識符自身的值是符號表的入口地址，常數(shù)是二進(jìn)制值。112.詞法分析器作為一個獨(dú)立子程序

把詞法分析器安排為一個獨(dú)立的階段的好處是，它可使整個編譯程序的結(jié)構(gòu)更簡單、清晰和條理化。詞法分析比語法分析要簡單得多，可用更有效得特殊方法和工具進(jìn)行處理。把詞法分析器安排為獨(dú)立的一遍，讓它把整個源程序翻譯成一連串的單詞符號（二元式）存放于文件中，待語法分析程序進(jìn)入工作時(shí)再對從文件輸入的這些單詞符號進(jìn)行分析。把詞法分析器安排為一個子程序，每當(dāng)語法分析分析器需要一個單詞符號時(shí)就調(diào)用這個子程序。每一次調(diào)用，詞法分析器就從輸入串中識別出一個單詞符號。在后面的討論中，我們假定詞法分析器是按這種方式進(jìn)行工作的。12相對獨(dú)立方式當(dāng)采用遞歸下降分析等技術(shù)實(shí)現(xiàn)一趟編譯程序時(shí)常采用這種方式。源程序詞法分析程序語法分析程序Tokengettoken….13完全獨(dú)立方式采用詞法分析工作完全獨(dú)立的原因：簡化設(shè)計(jì)，降低語法分析的復(fù)雜性提高編譯效率增加編譯系統(tǒng)的可移植性源程序詞法分析程序語法分析程序?qū)傩宰中蛄小?143.源程序的輸入在內(nèi)存開辟緩沖區(qū)，將程序文本放進(jìn)該緩沖區(qū)預(yù)處理：刪除無用字符等詞法分析程序?qū)彌_區(qū)掃描時(shí)，設(shè)置兩個指示器，一個指向當(dāng)前正在識別的單詞的開始位置，稱為起始指針；另一個用于向前搜索，以尋找單詞的終點(diǎn)，稱為掃描指針。起始指針?biāo)阉髦羔?5識別標(biāo)識符的若干約定和策略一般來說，單詞的長度是有限制的在允許長度下，應(yīng)按最長匹配原則進(jìn)行識別有時(shí)需要超前掃描來進(jìn)行單詞識別。例如，F(xiàn)ORTRAN語言中的算術(shù)條件句IF(e)=L1,L2,L3和語句函數(shù)定義句IF(x)=f(x)中的IF的識別；以及<和<=、<>等。在進(jìn)行超前掃描時(shí)，還應(yīng)注意“回退”字符，即將多吃掉的字符退還回輸入緩沖區(qū)。使用堆棧實(shí)現(xiàn)多字符回退的算法。16單詞符號的構(gòu)成規(guī)則

——標(biāo)識符012字母(a-z)字母或數(shù)字(a-z0-9)其它*此時(shí)，超前搜索了一個字符17§3.2單詞的描述工具作用:描述單詞的構(gòu)成規(guī)則,基于這類描述工具建立詞法分析技術(shù),進(jìn)而實(shí)現(xiàn)詞法分析程序的自動構(gòu)造.工具有:正規(guī)文法 正規(guī)式(RegularExpression)181.正規(guī)文法

多數(shù)程序設(shè)計(jì)語言單詞的語法都能用正規(guī)文法(3型文法)描述正規(guī)文法回顧 文法的任一產(chǎn)生式α→β的形式都為A→aB或A→a，其中A，B∈VN

，a∈VT。 正規(guī)文法描述的是VT*上的正規(guī)集19例如:

用l表示a~z中的任一英文字母，d表示0~9中任一數(shù)字描述標(biāo)識符的正規(guī)文法為

<標(biāo)識符>→l｜l<字母數(shù)字> <字母數(shù)字>→l｜d｜l<字母數(shù)字>｜d<字母數(shù)字>描述無符號整數(shù)的正規(guī)文法

<無符號整數(shù)>→d｜d<無符號整數(shù)>20為什么要引進(jìn)正則表達(dá)式？對于字母表∑，我們感興趣的是它的一些特殊字集－正規(guī)集。正規(guī)集是字母表Σ上的符合一定規(guī)則的符號串構(gòu)成的集合正則表達(dá)式是一種適合描述符號的表示法，可由它定義正規(guī)集。212.正規(guī)式(regularexpression)定義（正規(guī)式和它所表示的正規(guī)集）：設(shè)字母標(biāo)為1和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和；2任何a，a是上的一個正規(guī)式，它所表示的正規(guī)集為{a}；3假定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僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。22(e1),e1e2,e1e2,e1L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))。

其中的“”讀為“或”（也有使用“+”代替“”的）；“”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復(fù)連接）。在不致混淆時(shí)，括號可省去，但規(guī)定算符的優(yōu)先順序?yàn)椤啊?、“”、“”。連接符“”一般可省略不寫?！啊?、“”和“”都是左結(jié)合的。23例令={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的串}(ab) {,a,b,aa,ab……所有由a 和b組成的串}(ab)(aabb)(ab) {上所有含有兩個相繼 的a或兩個相繼的b組成 的串}24例={l，d}，r=l(ld)定義的正規(guī)集:{l,ll,ld,ldd,……}（標(biāo)識符）例={d，.，e，+，-},則上的正規(guī)式d(.dd)(e(+-)dd)表示的是無符號數(shù)的集合。其中d為0~9的數(shù)字。舉例25例:2={A,B,0,1},則(A|B){A|B|0|1}5是2上的正則表達(dá)式(A|B){A|B|0|1}5的值，即

L((A|B){A|B|0|1}5)，是這樣一個正則集，每個字符串都是以字母A或B打頭，后跟以至多5個字母（A或B）或數(shù)字（0或1）(0|1)(0|1)*∑上的“數(shù)”的全體26正規(guī)式的運(yùn)算律設(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…

“或”的抽取律

27程序中的單詞都能用正規(guī)式來定義令l為a~z的字母，d為0~9的數(shù)字e1=l(l|d)* e1表示標(biāo)識符集合e2=dd* e2表示無符號整數(shù)注(比較)： <標(biāo)識符>→l｜l<字母數(shù)字><字母數(shù)字>→l｜d｜l<字母數(shù)字>｜d<字母數(shù)字>

正規(guī)式比正規(guī)文法更容易讓人理解單詞是按怎樣的規(guī)律構(gòu)成的，且可以從某個正規(guī)式自動地構(gòu)造識別程序。28兩個正規(guī)式等價(jià)若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價(jià),寫作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)=(ba)b

(ab)=(ab)293.正規(guī)文法和正規(guī)式間的轉(zhuǎn)換等價(jià)性：對任意一個正規(guī)文法，存在一個定義同一語言的正規(guī)式對任意一個正規(guī)式，存在一個定義同一語言的正規(guī)文法30將∑上的一個正規(guī)式r轉(zhuǎn)換成文法G=(VN,VT,S,P)VT=∑,首先形成產(chǎn)生式S→r,S為G的開始符不斷利用下面的規(guī)則做變換,直到每個產(chǎn)生式最多含有一個終結(jié)符為止原產(chǎn)生式變換后產(chǎn)生式規(guī)則1A→xyA→xBB→y規(guī)則2A→x*yA→xAA→y規(guī)則3A→x|yA→xA→y其中B為一新非終結(jié)符31例:將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正則文法令轉(zhuǎn)換成文法G=(VN,VT,P,S)其中VT={a,d}，文法開始符為S首先形成S→a(a|d)*,然后變換S→aA A→(a|d)*A→(a|d)AA→εA→aAA→dA 最終有產(chǎn)生式：S→aA，A→ε，A→aA，

A→dA32將正規(guī)文法轉(zhuǎn)換成正規(guī)式將每條產(chǎn)生式改寫為正規(guī)式用代入法解正規(guī)式方程組最后只剩下一個開始符號定義的正規(guī)式,其中不含非終結(jié)符正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則:文法產(chǎn)生式正規(guī)式規(guī)則1A→xBB→yA=xy規(guī)則2A→xA|yA=x*y規(guī)則3A→xA→yA=x|y33例：將文法G[S]轉(zhuǎn)換成正規(guī)式

G：S→aA|aA→dA|d先由產(chǎn)生式得: S=aA|a A=d*d將A代入S中得: S=ad*d|a利用正規(guī)式變換得 S=a(d*d|ε)=ad*

說明:d*d|ε =(ε|d|dd|…)d|ε =d|dd|…|ε=d* 所求正規(guī)式為ad*34

§3.3有窮自動機(jī)（FiniteAutomata）1.狀態(tài)轉(zhuǎn)換圖2.確定有窮狀態(tài)自動機(jī)（DFA）3.非確定有窮狀態(tài)自動機(jī)（NFA）4.把NFA變?yōu)镈FA5.DFA的化簡351.正規(guī)文法和狀態(tài)轉(zhuǎn)換圖正規(guī)文法定義了3型語言，常見的單詞可由正規(guī)文法定義。狀態(tài)轉(zhuǎn)換圖可用于識別3型語言；它是設(shè)計(jì)和實(shí)現(xiàn)掃描器的一種有效工具，是有限自動機(jī)的直觀圖示36由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖程序設(shè)計(jì)語言的單詞都能用正規(guī)文法描述；例如，標(biāo)識符可定義為

<標(biāo)識符><標(biāo)識符>字母<標(biāo)識符><標(biāo)識符>數(shù)字

<標(biāo)識符>字母若把字母、數(shù)字視為終結(jié)符，則上述產(chǎn)生式為（左線性）正規(guī)文法若我們用d表示0-9間的數(shù)字，則C語言的<無符號數(shù)>的文法也是（右線性）正規(guī)文法（見P48）一般說來，凡能用正規(guī)文法描述的語言，均可由某種有限狀態(tài)算法——狀態(tài)轉(zhuǎn)換圖進(jìn)行分析。狀態(tài)轉(zhuǎn)換圖由有限個結(jié)點(diǎn)所組成的有向圖。每個結(jié)點(diǎn)代表在識別分析過程中掃描器所處的狀態(tài)，其中含有一個初始狀態(tài)和若干個終態(tài)。在圖中，狀態(tài)用圓圈表示，終態(tài)用雙層圓圈表示。狀態(tài)之間可用有向邊連接，其上標(biāo)記一字符a，表示從有向邊的射出狀態(tài)出發(fā)，識別一字符a后，將進(jìn)入箭頭所指狀態(tài)（結(jié)點(diǎn)）371)由右線性文法構(gòu)造狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一右線性文法,并設(shè)|VN|=K,則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個狀態(tài)(結(jié)點(diǎn)).用VN中的每個符號分別標(biāo)記其中的K個結(jié)點(diǎn),且令G的開始符S為初態(tài)結(jié)點(diǎn);余下的一個結(jié)點(diǎn)作為終態(tài)結(jié)點(diǎn),用F(VN)標(biāo)記.我們用如下規(guī)則來連接這K+1個結(jié)點(diǎn):(1)對于G中產(chǎn)生式AaB,從結(jié)點(diǎn)A引一有向邊到結(jié)點(diǎn)B,并用a標(biāo)記這一有向邊;(2)對于G中產(chǎn)生式Aa,從結(jié)點(diǎn)A引一有向邊到終態(tài)結(jié)點(diǎn)F,并用a標(biāo)記這一有向邊;(3)對于G中產(chǎn)生式A(若有的話),則將結(jié)點(diǎn)A設(shè)為終態(tài).例如,P48中定義的無符號數(shù)的文法對應(yīng)的~為(化簡后):0452136dddddd.E+|-Edd38利用狀態(tài)轉(zhuǎn)換圖識別符號串的方法對于已給的字符串w=a1a2…an,aiVT,利用~對w

識別的步驟如下:(1)從初始狀態(tài)S出發(fā),自左至右逐個掃描w的各個字符(當(dāng)前為a1),此時(shí)在結(jié)點(diǎn)S所射出的諸矢線中,尋找標(biāo)記為a1的矢線(若不存在,則表明w有語法錯誤),讀入a1并沿矢線所指方向前進(jìn),過渡到下一狀態(tài)(設(shè)為A1).(2)設(shè)當(dāng)前處在Ai狀態(tài),所掃描的字符為ai+1,在結(jié)點(diǎn)Ai所射出的諸矢線中,尋找標(biāo)記為ai+1的矢線(若不存在,則表明w有語法錯誤),讀入ai+1,并進(jìn)入狀態(tài)Ai+1;(3)重復(fù)(2),直到w中所有字符被讀完且恰好進(jìn)入終態(tài)F時(shí),宣告整個識別結(jié)束,w可被接受.顯然,若我們從初態(tài)出發(fā),分別沿一切可能的路徑到達(dá)終態(tài)結(jié)點(diǎn),并將中徑中矢線上所標(biāo)記的字符依次連接起來,便得到狀態(tài)轉(zhuǎn)換圖所能識別的全部符號串,這些符號串組成的集合構(gòu)成了該~識別的語言39狀態(tài)轉(zhuǎn)換圖與文法推導(dǎo)用狀態(tài)轉(zhuǎn)換圖識別符號串w的過程，就是為w建立一個推導(dǎo)S*w的過程。在第一步（在初始狀態(tài)S下，掃描到a1而過渡到下一狀態(tài)A1），由狀態(tài)轉(zhuǎn)換圖的構(gòu)造規(guī)則可知，G中必有產(chǎn)生式Sa1A1;對于識別過程的后續(xù)步驟，由狀態(tài)Ai識別ai+1后過渡到Ai+1恰好對應(yīng)了使用產(chǎn)生式Aiai+1Ai+1,…,最后在狀態(tài)An-1識別an后到達(dá)終態(tài)F，對應(yīng)了使用產(chǎn)生式 Aan 進(jìn)行推導(dǎo)：

Sa1A1a1a2A2……a1a2…an-1An-1a1a2…an40右線性文法與狀態(tài)轉(zhuǎn)換圖設(shè)G是一右線性文法,M是相應(yīng)的狀態(tài)轉(zhuǎn)換圖,則從前面的討論可以看出如下事實(shí)：(1)在利用M對符號串w進(jìn)行識別時(shí),M中每次狀態(tài)的轉(zhuǎn)換都模擬了一步直接推導(dǎo),即識別方法(或稱分析方法)是“”的;(2)因右線性文法只有形如AaB、Aa的產(chǎn)生式，所以推導(dǎo)的每一步所得句型只含一個非終結(jié)符，所以推導(dǎo)的規(guī)范的，每步所得的句型也必為規(guī)范句型；(3)對于M所識別的任一符號串x,必存在G中的一個推導(dǎo)S*x(即有xL(G);反之,對于L(G)中任一句子y,必存在一條從初態(tài)S到終態(tài)F的路徑,此路徑上各矢線的標(biāo)記依次拼接起來所組成的符號串恰為y412)由左線性文法構(gòu)造狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一左線性文法,構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖的方法是:首先用G的VN符標(biāo)記M的結(jié)點(diǎn),其中,開始符S對應(yīng)的結(jié)點(diǎn)為終態(tài)結(jié)點(diǎn).另外,再引入一個新結(jié)點(diǎn)R(VN)作為初態(tài).矢線的連接規(guī)則為:(1)對于G中形如Aa

的產(chǎn)生式,引矢線:RA,且標(biāo)記為a;(2)對于G中形如ABa

的產(chǎn)生式,引矢線BA,且標(biāo)記為a.42由左線性文法構(gòu)造狀態(tài)轉(zhuǎn)換圖的例子已給文法G=({S,U},{0,1},{SS1|U1,UU0|0},S)RUSU00UU00SU11SS11用左線性文法構(gòu)造出的狀態(tài)轉(zhuǎn)換圖來識別文法的句子,其過程與前面右線性文法構(gòu)造的狀態(tài)轉(zhuǎn)換圖用法一樣,這里不再贅述.不過,就識別的方法而言,它卻屬于“”分析.我們以句子00011為例,給出其識別的的步驟.見右表.步驟當(dāng)前狀態(tài) 余留的符號串1 R 000112 U 00113 U 0114 U 115 S 16 S (識別結(jié)束)43識別符號串與歸約由構(gòu)造狀態(tài)轉(zhuǎn)換圖的方法可知,從初態(tài)R到下一狀態(tài)A的轉(zhuǎn)換,對應(yīng)了形如Ba

的產(chǎn)生式,即將終結(jié)符a歸約成非終結(jié)符B;類似地,從狀態(tài)B轉(zhuǎn)換到狀態(tài)A,對應(yīng)了形如ABa的產(chǎn)生式,即將Ba歸約為A;如此下去,直到從某狀態(tài)A轉(zhuǎn)換到狀態(tài)S(終態(tài)),對應(yīng)了形如SAa的產(chǎn)生式,即將Aa歸約為開始符S.此時(shí)歸約成功,也恰好進(jìn)入了終態(tài),即狀態(tài)轉(zhuǎn)換圖識別了(或接受)該符號串.前面識別00011的例子對應(yīng)的歸約過程見右圖00011UUUSS44對句子ababaaa的分析步驟當(dāng)前狀態(tài)輸入的其余部分

SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZababaaaABABAZZ(a)分析過程(b)語法樹45詞法規(guī)則的描述狀態(tài)轉(zhuǎn)換圖難于書寫，非線性結(jié)構(gòu)更好的方式的要求線性方式表達(dá)與狀態(tài)轉(zhuǎn)換圖等價(jià)正規(guī)表達(dá)式[a-z][a-z|0-9]*462.有窮自動機(jī)(也稱有限自動機(jī))是一種識別裝置作用:能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合意義:為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。分類:

確定的有窮自動機(jī)

(DeterministicFiniteAutomata)

不確定的有窮自動機(jī)

(NondeterministicFiniteAutomata)47確定的有限自動機(jī)DFA1）抽象地看,狀態(tài)轉(zhuǎn)換圖由五個部分組成:(1)有限個狀態(tài)之集,記作K;(2)有限個輸入符號組成的字母表,記作;(3)從K到K的轉(zhuǎn)換函數(shù)

f:KK.f(p,a)=q表示若當(dāng)前狀態(tài)為p,且輸入符號為a,則進(jìn)入下一個狀態(tài)為q;(4)S0K,初始(開始)狀態(tài);(5)若干個終態(tài)之集:Z(K)由上述五個要素組成的五元式M=(K,,f,S0,Z)稱為一個確定的有限自動機(jī)

(DFA:DeterministicFiniteAutomata)由此可見,一DFA實(shí)際上是狀態(tài)轉(zhuǎn)換圖的形式描述(數(shù)學(xué)定義),狀態(tài)轉(zhuǎn)換圖是DFA的幾何(圖形)表示.“確定”即狀態(tài)轉(zhuǎn)換函數(shù)是單值函數(shù)！48DFA的接受集2）為定義DFA所接受(或識別)的符號串集合,我們先將其轉(zhuǎn)換函數(shù)f的定義域拓廣到K*:(1)f^(s,)=s,sK;(2)f^(s,aw)=f^(f(s,a),w),sK,a,w*;由上面的定義可知,對于x*,f^(s,x)=t

的含義是,當(dāng)M從狀態(tài)s出發(fā),依次掃描完x的各個符號后將進(jìn)入狀態(tài)t.即只要f有定義,f^與f的效果是一致的.我們稱DFAM接受(或識別)某符號串x*,用狀態(tài)轉(zhuǎn)換圖來說,就是從初態(tài)S0出發(fā),經(jīng)一恰好標(biāo)有x的路徑后可達(dá)到某終態(tài)SZ

;用f^描述就是: SZ,f(S0,x)=S

M的接受集我們把一DFAM所接受的符號串的全體稱為M的接受集,記為L(M),即L(M)={x|f(S0,x)Z,x*}49確定的有限自動機(jī)我們之所以把前面定義的有限自動機(jī)稱為確定的FA，是因?yàn)樵跔顟B(tài)轉(zhuǎn)換的每一步，根據(jù)FA當(dāng)前的狀態(tài)及掃描的輸入字符，便能唯一地確定FA的下一狀態(tài)。在轉(zhuǎn)換圖上看，若||=n，則任何結(jié)點(diǎn)所引出的矢線至多有n條，且矢線上的標(biāo)記均不同。例如，P51圖3-4所對應(yīng)的DFA為M=({R,U,S},{0,1},f,R,{S})

其中，f的定義如下：f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S由DFA與狀態(tài)轉(zhuǎn)換圖的關(guān)系可知，構(gòu)造狀態(tài)轉(zhuǎn)換圖的算法，同樣適用于構(gòu)造DFA。實(shí)際上，我們可以證明，正規(guī)文法G，DFAM，使 L(M)=L(G)，反之亦然。50從狀態(tài)轉(zhuǎn)換圖構(gòu)造有窮狀態(tài)自動機(jī)例如：從下面狀態(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 abSABabZbaa51運(yùn)行DFA與識別一個字符串定義：對于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，則稱符號串t可被DFAD所接受。運(yùn)行一個DFA的過程：識別一個符號串是否被接受52舉例如前例：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)=Z53正則集正則集：L(D)，是一個DFA接受的字符串集合正則語言與正則集：L(G)=L(D)最小狀態(tài)自動機(jī)：狀態(tài)個數(shù)最少，唯一54DFA的矩陣表示法字符狀態(tài)abSABabZbaa矩陣行代表狀態(tài)，列代表輸入字符，矩陣元素是映像得到的新狀態(tài)。553.非確定的有限自動機(jī)若在一左線性文法中含有多個右部相同的產(chǎn)生式，如 AUaBUaCUaXUa,或在一右線性文法中同時(shí)含有形如 UaAUaBUaCUaX的產(chǎn)生式，在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，就會出現(xiàn)這樣的結(jié)點(diǎn)U，它具有多條標(biāo)記為同一輸入符號a的矢線，如右圖所示圖3-8NFA的狀態(tài)轉(zhuǎn)換圖由上圖可知，在U狀態(tài)下，輸入符號為a時(shí)，F(xiàn)A的下一狀態(tài)不唯一，而是在狀態(tài)集{A,B,C,…,X}中任選其一。具有這種性質(zhì)的FA稱為非確定的FA（NFA:Nondeterministic

FA）UABCXaaaa...56非確定有限自動機(jī)的定義在形式上，NFAM同樣可用五元式定義：M=(K,,f,S0,Z)，其中，K,,S0,Z的含義同DFA,轉(zhuǎn)換函數(shù)f的定義為

f:K(K),即將(Si,aj)映射到K的一個子集{Sk1,…,Skm}

類似地，我們可把f的定義域拓廣到K*

：(1)f^(S,)={S};(2)f^(S,aw)=f^(f(S,a),w)a,w*.再設(shè)f(S,a)=

{Sk1,…,Skm},且定義這樣，我們已把f的定義域擴(kuò)大到(K)*。根據(jù)類似的理由，我們將對f和f^不加區(qū)分57NFA的接受集對于x*,若集合f(S0,x)中含有Z中的元素（終態(tài)），則說明，至少存在一條從初態(tài)S0到某一終態(tài)的路徑，此路徑上的符號之連接恰為x，此時(shí)，我們稱x為M所接受所有為M所接受的符號串之集稱為NFAM的接受集（或識別集），記作L(M).即L(M)={x|f(S0,x)Z,x}例3.1

給定M=({S,A,B,C},{a,b},f,S,{C}),其狀態(tài)轉(zhuǎn)換圖見右。由圖可知M是一NFA。M識別符號串a(chǎn)babb的路徑為S(a)A(b)B(a)A(b)B(b)C(接受)。(參見書中P60的表)SABCaa,babbaa注意，NFA識別輸入符號串時(shí)有一個試探過程，為了能走到終態(tài)，往往要走許多彎路（帶回溯），這影響了FA的效率。能否提高其工作效率就是我們下一小節(jié)討論的課題。事實(shí)上，對任一NFAM，總可構(gòu)造一個DFAM’，使L(M’)=L(M)成立。這就是NFA與DFA的等價(jià)性。58DFA與NFA的區(qū)別DFANFA開始狀態(tài)唯一一個或多個映像單個狀態(tài)狀態(tài)集合59舉例前述文法G3.2對應(yīng)的自動機(jī)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}abSABabZbaaaa60舉例(字符串被NFA所接受)對于輸入字符串babbabb，運(yùn)行NFA步驟當(dāng)前狀態(tài)輸入的其余部分可能的后繼選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZabABabZbaaaaS61運(yùn)行NFA運(yùn)行NFA：識別一個字符串是否被NFA所接受，是否能達(dá)到終態(tài)集合中的某個狀態(tài)實(shí)質(zhì)：用自底向上方法識別句子狀態(tài)轉(zhuǎn)換的下一狀態(tài)不唯一，如何解決？62DFA和NFA的關(guān)系對于Σ*上的字符串β，如果存在一條從初態(tài)到終態(tài)的通路，且這條通路上的輸入字符恰好連接成β，稱為β可以此DFA、NFA識別DFA、NFA都可以識別一個字符集Σ上的字符串可以用DFA、NFA定義Σ上的字符串的集合DFA都是NFA、NFA可化為等價(jià)的DFA63構(gòu)造與正規(guī)式等價(jià)的NFA方法XYααα|β12αβ12643αεε1αβ32αβ1221α*1265構(gòu)造與正規(guī)式等價(jià)的NFA示例a(a|b)*XYa(a|b)*XYa1(a|b)*66XYa1(a|b)2XYa1a2bεεεε674.NFA的確定化方法初態(tài)的唯一化終態(tài)的唯一化從初態(tài)集開始，求對于每個輸入符號的后繼狀態(tài)集合Si——新的狀態(tài)對每個Si，求對于每個輸入符號的后繼狀態(tài)集合Si+1直到不產(chǎn)生新的后繼狀態(tài)集合含有終態(tài)的狀態(tài)集合為終態(tài)68舉例例:為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]

69舉例（續(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]}70舉例（續(xù)2）SBABABZAZBZAZbbbbbbbaaaaaaaa開始狀態(tài):[S]終止?fàn)顟B(tài):[Z],[AZ],[BZ],[ABZ]

根據(jù)上面狀態(tài)轉(zhuǎn)換矩陣，同時(shí)可以得到N’的映像函數(shù)，根據(jù)該映像可以畫出它的狀態(tài)轉(zhuǎn)換圖（如下）。終態(tài)集合中的元素為：由新映像得到的狀態(tài)、且這些狀態(tài)包含原NFAN的終態(tài)集合中的狀態(tài)。71NFA的確定化示例狀態(tài)轉(zhuǎn)換矩陣 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {}XYa1a2bεεa(a|b)*72 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {}

a

b{X} {1,2,Y}{} {1,2,Y}{2,Y}{2,Y}{2,Y} {2,Y}{2,Y}NFA狀態(tài)轉(zhuǎn)換矩陣1)(2)(3) a

b1) (2) (2) (3) (3)(3) (3) (3)等價(jià)的DFA狀態(tài)轉(zhuǎn)換矩陣73 a b1) (2) (2) (3) (3)(3) (3) (3)13aabab274NFA確定化的例子M=({S0,S1},{a,b},f,S0,{s1})S0S1abba|b_f_|_a____b___S0|{S0,S1}{S1}S1|{S0,S1}M’=(K’,{a,b},f’,[S0],{[S1],[S0,S1]})f’|ab.|newstate[]|[][]|[S0]|[S0S1][S1]|1[S1]|[][S0S1]|2[S0S1]|[S0S1][S0S1]|3123abb|ab75具有動作的FA若在一FA中,允許對也作狀態(tài)轉(zhuǎn)移,則這樣的FA稱為具有動作的FA(NFA).此時(shí),有的矢線上標(biāo)記為標(biāo)記為的矢線對識別符號串無影響,但卻改變了當(dāng)前的狀態(tài).例如,右圖中的FA中,從狀態(tài)0到狀態(tài)3存在路徑:0(a)0(a)0()2(c)2(c)2()3,即M識別了aacc=aacc.~的定義

M=(K,,f,S0,Z),其中,f的定義為f:K({})(K).在~中,可以視為一個輸入符號,在矩陣表示中,也有相應(yīng)的列.0123abbcf也可以拓廣到f’:K*(K).f’(S,x)是由這樣的狀態(tài)Q組成,存在從S到Q的路徑,該路徑上的連線標(biāo)記組成的符號串恰好為x,其中,允許有有限個標(biāo)記為76狀態(tài)S的-閉包：-CLOSURE(S)為定義拓廣的f’,我們首先引入每個狀態(tài)S的-閉包的定義： -CLOSURE(S),它是從S出發(fā)經(jīng)過若干標(biāo)記為的矢線所能達(dá)到的全部狀態(tài)之集，其歸納定義如下：(1)S-CLOSURE(s);(2)設(shè)Sj-CLOSURE(S),且SjSk,則Sk-CLOSURE(S);(3)有限地使用規(guī)則（2）所得的集合為-CLOSURE(S).例，在上頁的NFA中，-CLOSURE(0)={0,1,2,3} -CLOSURE(1)={1} -CLOSURE(2)={2,3} -CLOSURE(3)={3}.進(jìn)一步，-CLOSURE還可定義在-CLOSURE:(K)(K)，設(shè)QK(Q(K))，則77轉(zhuǎn)換函數(shù)f的拓廣利用-CLOSURE(S)，可定義f’如下：78f與f’的區(qū)別由f’的定義可知，f’(S,a)

與f(S,a)

不同，f’(S,a)是從S出發(fā)經(jīng)過路徑a據(jù)達(dá)的狀態(tài)集（可走若干步）；而f(S,a)是從S出發(fā)經(jīng)過矢線a所達(dá)狀態(tài)之集（只走一步）其實(shí)，

f(S,a)-CLOSURE(f(S,a))f’(S,a)

只走一步a矢線

|多步，第一步必須走a矢線

|路徑a：第一步可以是矢線例如，在前面的NFA中，f’(0,)=-CLOSURE(0)={0,1,2,3}f(0,)={1,2}f’(0,a)={0,1,2,3} f(0,a)={0}-NFA的接受集：L(M)={w|f’(S0,w)Z}79-NFA的用途：構(gòu)造更復(fù)雜的FA有了-NFA，就可把識別各種不同單詞的FA用矢線（并連）連接起來，組成一個單一的NFA，經(jīng)確定化后可得識別所有單詞的DFA，由此可設(shè)計(jì)編譯程序的詞法分析器。例如，某語言的單詞有：1.BEGIN 2.END 3.IF 4.THEN 5.ELSE6.標(biāo)識符 7.無符號整數(shù) 8.< 9.<= 10.= 11.<> 12.> 13.>=我們可容易地分別構(gòu)造出識別各類單詞的FA,然后將其合并為一個大FA,如書中P65圖3-11所示(由于較難描繪,這里略去,請自行參閱教材)80ε閉包狀態(tài)集I的ε_CLOSURE(I)如果q屬于Iq屬于ε_CLOSURE(I)從q出發(fā)經(jīng)任意條ε弧到達(dá)的任何狀態(tài)q’都屬于ε_CLOSURE(I)81具有動作的NFA的確定化設(shè)已給具有動作的NFAM=(K,,f,S0,Z),構(gòu)造相應(yīng)的DFAM’=(K’,,f’,q0,Z’)的方法是，先令q0=[-CLOSURE(S0)],然后對每個a，令[-CLOSURE(f’(q0,a))]為新狀態(tài)，如此反復(fù)，直到無新狀態(tài)產(chǎn)生：1.令K’={[-CLOSURE(S0)]};f’=;2.對K’中尚未被標(biāo)記的狀態(tài)qi=[Si1,Si2,…,Sim]: (1)標(biāo)記qi; (2)對于每個a,令Ta=f({Si1,Si2,…,Sim},a);qj=[-CLOSURE(Ta)]; (3)若qjK’,則令K’=K’{qj}; (4)令f’=f’{f’(qj,a)=qj};3.重復(fù)2.,直到K’中無未標(biāo)記的狀態(tài);4.令Z’={qj|qjZ}(這里把qj

視為集合)82確定化具有動作的NFA的例子例3.4考慮前面引入的具有動作的NFA的例子(P63圖3-10)1.q0=[0,1,2,3]==>K’;2.q0未標(biāo)記,故(1)標(biāo)記q0;(2)令f”(q0,a)=[-CLOSURE(f’(q0,a))]=q0; f”(q0,b)=[-CLOSURE(f’(q0,b))]=[1,3]=q1;q1==>K’; f”(q0,c)=[2,3]=q2;q2==>K’;3.此時(shí),K’={q0,q1,a2},q1,q2arenotmarked.so,(1)markq1;(2)letf”(q1,a)=[-CLOSURE(f’(q1,a))]=; f”(q1,b)=…=q1; f”(q1,c)=…=;4.q2isnotmarked,so(1)markq2;(2)f”(q2,a)=f”(q2,b)=; f”(q2,c)=q2;K’isnotincreasedandallstatesaremarked.Z’={q0,q1,q2}q1q0q2abbcc83手工計(jì)算確定化的方法在人工進(jìn)行NFA確定化時(shí),可按下述的構(gòu)造矩陣的方法實(shí)現(xiàn):_____________|abc_q0:[0123]|[0123][13][23]q1:[13]|[][13][]q2:[23]|[][][23]需要說明的是,本算法也適合于不含產(chǎn)生式的NFA的確定化.例3.5

對于書中圖3-13所示的NFA利用上述算法所得的DFA如P67圖3-13所示.其中,圓圈中的數(shù)字是原NFA的狀態(tài)編號,在圖3-13中,q0={0,1,7,11,14,19,24,26,28,30,33,35,40}.標(biāo)有“#”的狀態(tài)為特殊狀態(tài),在該狀態(tài)下,若遇非弧線上出現(xiàn)的字符,則轉(zhuǎn)到狀態(tài)25.845.DFA的化簡狀態(tài)的等價(jià)性能夠識別相同的字符串劃分為終態(tài)和非終態(tài)兩個子集如果某個子集中的狀態(tài)是可區(qū)分的，則進(jìn)一步劃分這個子集直到在每個子集內(nèi)，各個狀態(tài)都是不可區(qū)分的。同一子集內(nèi)的狀態(tài)合并。85DFA狀態(tài)數(shù)的最小化對于一DFA來說,其狀態(tài)數(shù)可能并不是最小的.原因是DFA中有些狀態(tài)是“等價(jià)”的.為得到效率高的DFA,需將這些“等價(jià)”狀態(tài)合并,這就是DFA的最小化.DFAM的最小化:構(gòu)造等價(jià)的DFAM’其狀態(tài)數(shù)達(dá)到最小.可區(qū)分狀態(tài):設(shè)s,tK,s,t由某w*所區(qū)分iff (f(s,w)Zf(t,w)Z)(f(s,w)Zf(t,w)Z)若w*,f(s,w)Zf(t,w)Z,則稱s與t等價(jià)(不可區(qū)分)在一DFA中,等價(jià)狀態(tài)可合并.86DFA最小化算法基本思想:將M的狀態(tài)集K逐步地進(jìn)行劃分加細(xì),以期將K劃分為滿足等價(jià)關(guān)系的等價(jià)類,使得在同一類中的狀態(tài)不可區(qū)分;在不同類中的狀態(tài)可區(qū)分.算法如下:1.先將狀態(tài)集K劃分為兩個子集Z和K-Z,顯然分屬于這兩個集合的狀態(tài)是可(被)區(qū)分的.記={Z,K-Z}.2.設(shè)當(dāng)前的劃分中已含有m個子集:={I1,I2,…,Im},其中,屬于不同子集的狀態(tài)是可區(qū)分的,而屬于同一子集中的狀態(tài)則待區(qū)分.現(xiàn)對每個子集Ii={Si1,Si2,…,Sin}中的各狀態(tài)Sir(SirK,1rn)進(jìn)行考查,看其是否可區(qū)分.若存在a,使得Su=f(Sip,a)Ij,Sv=f(Siq,a)Ik

則由假設(shè),Su和Sv被子某個w所區(qū)分,進(jìn)一步,Sip

和Siq

可被aw

區(qū)分:f(Sip,aw)=f(Su,w)屬于Z而f(Siq,aw)=f(Sv,w)不屬于Z(或反之),即Siq

與Sip

可區(qū)分.將Ii細(xì)分,使其落入不同的更小的子集中.得到新劃分new.

（細(xì)分Ii的方法見下頁）。3.若new.不等于,則令

=new.

轉(zhuǎn)2.4.對于最終的，從每個劃分塊中任選一狀態(tài)為代表，構(gòu)成K‘，S0的代表為初態(tài)。若IiZ，則Ii

的代表Z’；將引入(出)非代表的矢線引向代表.87DFA最小化的例子1.={{0,1,2,3},{4}}{0,1,2,3}a={1}未區(qū)分;{0,1,2}b={2,3},{3}b={4},所以3與0,1,2可區(qū)分;={{0,1,2},{3},{4}}2.{0,1,2}a={1},未區(qū)分;{0,2}b={2},{1}b={3},1與0,2可區(qū)分;={{0,2},{1},{3},{4}};3.{0,2}a={1},{0,2}b={2}不可區(qū)分,new=.結(jié)束.0123aaababbb定理3.2

最小狀態(tài)數(shù)的DFA在同構(gòu)意義下是唯一的.01324aaaaabbbbb88DFA化簡的例子設(shè)有一個DFAM=(K，，f，S，Z)，其狀態(tài)圖如下圖所示。對其進(jìn)行化簡。21ba03abbaab89DFA的化簡示例 a b1) (2) (2) (3) (3)(3) (3) (3)劃分1：{1},{2，3}{2,3}a={3}屬于{2,3}{2,3}b={3}屬于{2,3}狀態(tài)2、3不可區(qū)分，應(yīng)簡化為{1,2}9013aabab21a2ab化簡前的DFA化簡后的DFA91練習(xí)字母表{a,b}上所有含有aa或bb的字符串組成的集合用正規(guī)式表達(dá)為(a|b)*(aa|bb)(a|b)*92(a|b)*(aa|bb)(a|b)*0Y(a|b)*(aa|bb)(a|b)*1Y(aa|bb)(a|b)*0(a|b)*1Y(a|b)*0(a|b)*2(aa|bb)931Y(a|b)*0a2(aa|bb)3bεε1Y(a|b)*0a2aa3bεεbb941Y(a|b)*0a2a3bεεb45ab951YXa2a3bεεb45ab6baεε96狀態(tài)轉(zhuǎn)換矩陣

a b{X,3,1} {3,1,4} {3,1,5}{3,1,4} {3,1,4,2,6,Y} {3,1,5}{3,1,5} {3,1,4} {3,1,5,2,6,Y}{3,1,4,2,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}{3,1,5,2,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,5,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,4,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}97

a b0 1 21 3 22 1 43） 3 54） 6 45） 6 46） 3 5

a b{X,3,1} {3,1,4} {3,1,5}{3,1,4} {3,1,4,2,6,Y} {3,1,5}{3,1,5} {3,1,4} {3,1,5,2,6,Y}{3,1,4,2,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}{3,1,5,2,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,5,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,4,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}98DFA的最小化一定可以區(qū)分的兩個集合用e表示出錯狀態(tài)非終止?fàn)顟B(tài)集{0,1,2}——不認(rèn)識ε終止?fàn)顟B(tài)集{3,4,5,6}——認(rèn)識ε{0,1,2}中δ(0,a)=1,δ(1,a)=3,δ(2,a)=1{0,2}與{1}不同，可區(qū)分{0,2}中δ(0,b)=2,δ(2,b)=4{0}與{2}不同，可區(qū)分{3,4,5,6}a={3,6},{3,4,5,6}b={4,5}{3,4,5,6}內(nèi)不可區(qū)分99最小化的DFA a b0 1 21 3 22 1 33 3 3 100顯然DFA是NFA的特例。對于每個NFA

M，存在一個DFA

M`，使得L（M）=L（M`）。對于任何兩個有窮自動機(jī)M和M`，如果

L（M）=L（M`），則稱M與M`是等價(jià)的。對每個NFA

N存在著與之等價(jià)的DFA

M。與某一NFA等價(jià)的DFA不唯一。

§3.4NFA與DFA的等價(jià)性101§3.5正規(guī)文法與有窮自動機(jī)之間的轉(zhuǎn)換設(shè)右線性文法G=(VN，VT，P，S)，下面介紹將其轉(zhuǎn)換成有窮自動機(jī)M=(K，，f，S0，Z)，使得L(G)=L(M)的方法。令K=VNZ，Z是M中新增的終態(tài)；=VT，S0=S；f由下列方法確定：對于G的每條形如AaB的規(guī)則，在M中設(shè)轉(zhuǎn)換函數(shù)f(A,a)=B；對于G的每條形如Aa的規(guī)則，在M中設(shè)轉(zhuǎn)換函數(shù)f(A,a)=Z。102例對于正規(guī)文法G[S]：SaB|bBBbS|a|b，可以轉(zhuǎn)換成自動機(jī)M=(K，，f，S0，Z)，其中：K={S，B，Z}，={a，b}，S0=S，Z={Z}，f為：

f(S,a)=B，f(S,b)=B，f(B,b)=S，

f(B,a)=Z，f(B,b)=Z。這是一個NFA。對應(yīng)的狀態(tài)圖如下：SaBZbbab103有窮自動機(jī)轉(zhuǎn)換成右線性文法若有限自動機(jī)是NFA則將其確定化，設(shè)確定的有窮自動機(jī)M=(K，，f，S0，Z)，則轉(zhuǎn)換得到右線性文法G=(VN，VT，P，S)，其中：VN=K，VT=，S=S0，P中的規(guī)則用如下方法確定：對M中任一形如f(A,a)=B的轉(zhuǎn)換函數(shù)，有規(guī)則AaBP；對M中的終態(tài)Z，則加一條規(guī)則ZP。104左線性文法轉(zhuǎn)換成自動機(jī)的方法設(shè)左線性文法G=(VN，VT，P，S)，有窮自動機(jī)M=(K，，f，S0，Z)，則M中的K=VNS0，S0

是M中新增的初態(tài)；=VT，Z={S}；f由下列方法確定：對于G的每條形如ABa的規(guī)則，在M中設(shè)轉(zhuǎn)換函數(shù)f(B,a)=A；對于G的每條形如Aa的規(guī)則，在M中設(shè)轉(zhuǎn)換函數(shù)f(S0,a)=A。105設(shè)左線性文法G[S]：SSa|Aa|BbABa|aBAb|b，則按照上述方法構(gòu)造的有窮自動機(jī)為M=(K，，f，S0，Z)，其中：K={S0，A，B，S}，={a，b}，Z={S}，f為：

f(S,a)=S，f(A,a)=S，f(B,b)=S，f(B,a)=A，

f(S0,a)=A，f(A,b)=B，f(S0,b)=B。其對應(yīng)的狀態(tài)圖如下：baS0BSAabaab106

§3.6詞法分析程序的設(shè)計(jì)主要內(nèi)容：詞法分析設(shè)計(jì)考慮的問題詞法分析程序的流程107詞法分析設(shè)計(jì)考慮的問題程序的預(yù)處理刪除源程序的無用字符濾掉源程序中的注釋進(jìn)行宏替換實(shí)現(xiàn)文件包含命令和條件編譯命令嵌入處理保留字（關(guān)鍵字）的識別與查表算法單詞的識別與超前搜索108詞法分析程序流程使用狀態(tài)圖設(shè)計(jì)詞法分析程序的步驟對程序設(shè)計(jì)語言的單詞按類構(gòu)造相應(yīng)的狀態(tài)圖。合并各類單詞的狀態(tài)圖，構(gòu)成一個能識別程序語言所有單詞的狀態(tài)轉(zhuǎn)換圖。具體方法：將各類單詞的狀態(tài)圖的初態(tài)合并為唯一的初態(tài)；化簡沖突和狀態(tài)編號；增加出錯處理終態(tài)。對狀態(tài)圖每一個終點(diǎn)編寫一段相應(yīng)的語義子程序。109例設(shè)一程序設(shè)計(jì)語言有下列單詞組成：

關(guān)鍵字：int，for，if，while，cout，cin，do；標(biāo)識符：<標(biāo)識符><標(biāo)識符>字母|<標(biāo)識符>數(shù)字|字母；

無符號整數(shù)：<無符號整數(shù)><無符號整數(shù)>數(shù)字|數(shù)字；

運(yùn)算符或界符：=，*，>，+，++，{，}。11010字母|數(shù)字3*2其它字母數(shù)字567101113*4其它*8其它9+數(shù)字=*+>{}其它12111詞法分析程序流程圖開始濾掉空格是字母?讀標(biāo)識符查保留字表查到否?保留字類碼syYY返回是字母?取數(shù)Y整數(shù)類碼sy數(shù)值NUM標(biāo)識符類碼

sy標(biāo)識符ID是界符?界符或運(yùn)算符類碼sy出錯處理NNYNN112詞法分析程序的實(shí)現(xiàn)詞法分析程序的構(gòu)造方法詞法分析程序的編寫113構(gòu)造詞法分析程序的方法用手工方式，即根據(jù)識別語言單詞的狀態(tài)轉(zhuǎn)換圖，使用某種高級語言，例如，C語言直接編寫詞法分析程序。利用自動生成工具LEX自動生成詞法分析程序。114詞法分析程序?qū)崿F(xiàn)中

要考慮的問題確定實(shí)現(xiàn)詞法分析程序的執(zhí)行方式確定屬性字的結(jié)構(gòu)緩沖區(qū)預(yù)處理，超前搜索,關(guān)鍵字的處理，符號表的實(shí)現(xiàn)查找效率，算法的優(yōu)化實(shí)現(xiàn)詞法錯誤處理115屬性字詞法分析程序?qū)φf明部分不做語義處理。詞法分析程序輸出屬性字一般采用下面的形式：（符號類，符號值）屬性字是符號的機(jī)內(nèi)表示，有統(tǒng)一固定的長度116關(guān)鍵字的識別與查表算法對于關(guān)鍵字，先把它們當(dāng)成標(biāo)識符，然后去查關(guān)鍵字表。若在表中查到，則為關(guān)鍵字，獲取相應(yīng)的類別碼；否則，認(rèn)為是標(biāo)識符。查找算法：線性查找折半查找Hash函數(shù)117出錯處理對定義外的（如，對首字符不是字母的，不是數(shù)字的，不是運(yùn)算符和分界符的）單詞進(jìn)行出錯處理。118詞法分析中使用的數(shù)據(jù)字符表：（字母表）列出源程序中所有可能的字符。特定符號與機(jī)內(nèi)表示表：一切特定符號與相應(yīng)編碼。標(biāo)識符表：登錄一切源程序中出現(xiàn)的一切標(biāo)識符。此表的序號作為屬性字的值。常數(shù)表：登錄一切源程序中出現(xiàn)的常數(shù)。此表的序號作為屬性字的值。119使用狀態(tài)圖設(shè)計(jì)詞法分析程序多數(shù)語言的詞法規(guī)則可用正則文法和正則表達(dá)式來描述。正則文法或正則表達(dá)式定義的語言都可以被狀態(tài)圖識別。使用狀態(tài)圖設(shè)計(jì)詞法分析程序的步驟如下：對程序設(shè)計(jì)語言的單詞按類構(gòu)造相應(yīng)的狀態(tài)圖。（這里把關(guān)鍵字與標(biāo)識符作為一類）合并各類單詞的狀態(tài)圖，增加一個出錯處理終態(tài)，構(gòu)成一個識別該語言所有單詞的狀態(tài)轉(zhuǎn)換圖對狀態(tài)圖的每一個終點(diǎn)編一段相應(yīng)的子程序。120201字母字母|數(shù)字其它3456數(shù)字?jǐn)?shù)字其它+-78*/9101113<=>:;1617其它13=舉例121詞法分析程序的結(jié)構(gòu)取字符子程序取符號子程序，一般有如下約定：進(jìn)入子程序時(shí)，已經(jīng)取到當(dāng)前符號的一個字符。離開子程序時(shí)，已經(jīng)取到其后繼字符。查造標(biāo)識符表子程序查造常量表子程序查符號機(jī)內(nèi)表示對照表子程序122詞法分析程序的自動生成（Lex)LEX是由美國Bell實(shí)驗(yàn)室的M.Lesk和Schmidt于1975年用C語言研制的一個詞法分析程序的自動生成工具。對任何高級程序語言，用戶必須用正規(guī)表達(dá)式描述該語言的各個詞法類（這一描述稱為LEX的源程序），LEX就可以自動生成該語言的詞法分析程序。LEX及其編譯系統(tǒng)的作用如圖。123圖LEX及其編譯系統(tǒng)的作用124一個LEX源程序由用“%%”分隔的三部分組成：第一部分為正規(guī)式的輔助定義式，第二部分為識別規(guī)則，最后一部分為用戶子程序。其書寫格式為：輔助定義式

%%

識別規(guī)則

%%

用戶子程序125

其中，輔助定義式和用戶子程序是任選的，而識別規(guī)則是必需的。如果用戶子程序缺省，則第二個分隔符號“%%”可以省去；但如果無輔助定義式部分，第一個分隔符號“%%”不能省去，因?yàn)榈谝粋€分隔符號用于指示識別規(guī)則部分的開始。126下面給出一個簡單語言的單詞符號的LEX源程序例子，其輸出單詞的類別編碼用整數(shù)編碼表示。

AuxiliaryDefinitions /*輔助定義*/letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣zdigit→0∣1∣2∣3∣…∣9%%RecognitionRules /*識別規(guī)則*/1271while {return(1,null)}2do {return(2,null)}3if {return(3,null)}4else {return(4,null)}5switch {return(5,null)}6{ {return(6,null)}7} {return(7,null)}8( {return(8,null)}9)