第3章詞法分析

1第3章詞法分析

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

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

源程序詞法分析器語法分析器字符單詞符號(hào)取下一個(gè)

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

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

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

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

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

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

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

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

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

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

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

(while,-)

(( ,-)

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

(>=,-)

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

(),-)

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

(--,-)

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

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

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

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

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

<無符號(hào)整數(shù)>→d｜d<無符號(hào)整數(shù)>20為什么要引進(jìn)正則表達(dá)式？對(duì)于字母表∑，我們感興趣的是它的一些特殊字集－正規(guī)集。正規(guī)集是字母表Σ上的符合一定規(guī)則的符號(hào)串構(gòu)成的集合正則表達(dá)式是一種適合描述符號(hào)的表示法，可由它定義正規(guī)集。212.正規(guī)式(regularexpression)定義（正規(guī)式和它所表示的正規(guī)集）：設(shè)字母標(biāo)為1和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和；2任何a，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；3假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(zhǎng)(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í)，括號(hào)可省去，但規(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,……任意個(gè)a的串}(ab) {,a,b,aa,ab……所有由a 和b組成的串}(ab)(aabb)(ab) {上所有含有兩個(gè)相繼 的a或兩個(gè)相繼的b組成 的串}24例={l，d}，r=l(ld)定義的正規(guī)集:{l,ll,ld,ldd,……}（標(biāo)識(shí)符）例={d，.，e，+，-},則上的正規(guī)式d(.dd)(e(+-)dd)表示的是無符號(hào)數(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)，是這樣一個(gè)正則集，每個(gè)字符串都是以字母A或B打頭，后跟以至多5個(gè)字母（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)識(shí)符集合e2=dd* e2表示無符號(hào)整數(shù)注(比較)： <標(biāo)識(shí)符>→l｜l<字母數(shù)字><字母數(shù)字>→l｜d｜l<字母數(shù)字>｜d<字母數(shù)字>

正規(guī)式比正規(guī)文法更容易讓人理解單詞是按怎樣的規(guī)律構(gòu)成的，且可以從某個(gè)正規(guī)式自動(dòng)地構(gòu)造識(shí)別程序。28兩個(gè)正規(guī)式等價(jià)若兩個(gè)正規(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à)性：對(duì)任意一個(gè)正規(guī)文法，存在一個(gè)定義同一語言的正規(guī)式對(duì)任意一個(gè)正規(guī)式，存在一個(gè)定義同一語言的正規(guī)文法30將∑上的一個(gè)正規(guī)式r轉(zhuǎn)換成文法G=(VN,VT,S,P)VT=∑,首先形成產(chǎn)生式S→r,S為G的開始符不斷利用下面的規(guī)則做變換,直到每個(gè)產(chǎn)生式最多含有一個(gè)終結(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ī)式方程組最后只剩下一個(gè)開始符號(hào)定義的正規(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有窮自動(dòng)機(jī)（FiniteAutomata）1.狀態(tài)轉(zhuǎn)換圖2.確定有窮狀態(tài)自動(dòng)機(jī)（DFA）3.非確定有窮狀態(tài)自動(dòng)機(jī)（NFA）4.把NFA變?yōu)镈FA5.DFA的化簡(jiǎn)351.正規(guī)文法和狀態(tài)轉(zhuǎn)換圖正規(guī)文法定義了3型語言，常見的單詞可由正規(guī)文法定義。狀態(tài)轉(zhuǎn)換圖可用于識(shí)別3型語言；它是設(shè)計(jì)和實(shí)現(xiàn)掃描器的一種有效工具，是有限自動(dòng)機(jī)的直觀圖示36由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖程序設(shè)計(jì)語言的單詞都能用正規(guī)文法描述；例如，標(biāo)識(shí)符可定義為

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

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

識(shí)別的步驟如下:(1)從初始狀態(tài)S出發(fā),自左至右逐個(gè)掃描w的各個(gè)字符(當(dāng)前為a1),此時(shí)在結(jié)點(diǎn)S所射出的諸矢線中,尋找標(biāo)記為a1的矢線(若不存在,則表明w有語法錯(cuò)誤),讀入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有語法錯(cuò)誤),讀入ai+1,并進(jìn)入狀態(tài)Ai+1;(3)重復(fù)(2),直到w中所有字符被讀完且恰好進(jìn)入終態(tài)F時(shí),宣告整個(gè)識(shí)別結(jié)束,w可被接受.顯然,若我們從初態(tài)出發(fā),分別沿一切可能的路徑到達(dá)終態(tài)結(jié)點(diǎn),并將中徑中矢線上所標(biāo)記的字符依次連接起來,便得到狀態(tài)轉(zhuǎn)換圖所能識(shí)別的全部符號(hào)串,這些符號(hào)串組成的集合構(gòu)成了該~識(shí)別的語言39狀態(tài)轉(zhuǎn)換圖與文法推導(dǎo)用狀態(tài)轉(zhuǎn)換圖識(shí)別符號(hào)串w的過程，就是為w建立一個(gè)推導(dǎo)S*w的過程。在第一步（在初始狀態(tài)S下，掃描到a1而過渡到下一狀態(tài)A1），由狀態(tài)轉(zhuǎn)換圖的構(gòu)造規(guī)則可知，G中必有產(chǎn)生式Sa1A1;對(duì)于識(shí)別過程的后續(xù)步驟，由狀態(tài)Ai識(shí)別ai+1后過渡到Ai+1恰好對(duì)應(yīng)了使用產(chǎn)生式Aiai+1Ai+1,…,最后在狀態(tài)An-1識(shí)別an后到達(dá)終態(tài)F，對(duì)應(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對(duì)符號(hào)串w進(jìn)行識(shí)別時(shí),M中每次狀態(tài)的轉(zhuǎn)換都模擬了一步直接推導(dǎo),即識(shí)別方法(或稱分析方法)是“”的;(2)因右線性文法只有形如AaB、Aa的產(chǎn)生式，所以推導(dǎo)的每一步所得句型只含一個(gè)非終結(jié)符，所以推導(dǎo)的規(guī)范的，每步所得的句型也必為規(guī)范句型；(3)對(duì)于M所識(shí)別的任一符號(hào)串x,必存在G中的一個(gè)推導(dǎo)S*x(即有xL(G);反之,對(duì)于L(G)中任一句子y,必存在一條從初態(tài)S到終態(tài)F的路徑,此路徑上各矢線的標(biāo)記依次拼接起來所組成的符號(hà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對(duì)應(yīng)的結(jié)點(diǎn)為終態(tài)結(jié)點(diǎn).另外,再引入一個(gè)新結(jié)點(diǎn)R(VN)作為初態(tài).矢線的連接規(guī)則為:(1)對(duì)于G中形如Aa

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

的產(chǎn)生式,即將終結(jié)符a歸約成非終結(jié)符B;類似地,從狀態(tài)B轉(zhuǎn)換到狀態(tài)A,對(duì)應(yīng)了形如ABa的產(chǎn)生式,即將Ba歸約為A;如此下去,直到從某狀態(tài)A轉(zhuǎn)換到狀態(tài)S(終態(tài)),對(duì)應(yīng)了形如SAa的產(chǎn)生式,即將Aa歸約為開始符S.此時(shí)歸約成功,也恰好進(jìn)入了終態(tài),即狀態(tài)轉(zhuǎn)換圖識(shí)別了(或接受)該符號(hào)串.前面識(shí)別00011的例子對(duì)應(yīng)的歸約過程見右圖00011UUUSS44對(duì)句子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.有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))是一種識(shí)別裝置作用:能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合意義:為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。分類:

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

(DeterministicFiniteAutomata)

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

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

f:KK.f(p,a)=q表示若當(dāng)前狀態(tài)為p,且輸入符號(hào)為a,則進(jìn)入下一個(gè)狀態(tài)為q;(4)S0K,初始(開始)狀態(tài);(5)若干個(gè)終態(tài)之集:Z(K)由上述五個(gè)要素組成的五元式M=(K,,f,S0,Z)稱為一個(gè)確定的有限自動(dòng)機(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所接受(或識(shí)別)的符號(hào)串集合,我們先將其轉(zhuǎn)換函數(shù)f的定義域拓廣到K*:(1)f^(s,)=s,sK;(2)f^(s,aw)=f^(f(s,a),w),sK,a,w*;由上面的定義可知,對(duì)于x*,f^(s,x)=t

的含義是,當(dāng)M從狀態(tài)s出發(fā),依次掃描完x的各個(gè)符號(hào)后將進(jìn)入狀態(tài)t.即只要f有定義,f^與f的效果是一致的.我們稱DFAM接受(或識(shí)別)某符號(hào)串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所接受的符號(hào)串的全體稱為M的接受集,記為L(zhǎng)(M),即L(M)={x|f(S0,x)Z,x*}49確定的有限自動(dòng)機(jī)我們之所以把前面定義的有限自動(dòng)機(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所對(duì)應(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)自動(dòng)機(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與識(shí)別一個(gè)字符串定義：對(duì)于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，則稱符號(hào)串t可被DFAD所接受。運(yùn)行一個(gè)DFA的過程：識(shí)別一個(gè)符號(hào)串是否被接受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)，是一個(gè)DFA接受的字符串集合正則語言與正則集：L(G)=L(D)最小狀態(tài)自動(dòng)機(jī)：狀態(tài)個(gè)數(shù)最少，唯一54DFA的矩陣表示法字符狀態(tài)abSABabZbaa矩陣行代表狀態(tài)，列代表輸入字符，矩陣元素是映像得到的新狀態(tài)。553.非確定的有限自動(dòng)機(jī)若在一左線性文法中含有多個(gè)右部相同的產(chǎn)生式，如 AUaBUaCUaXUa,或在一右線性文法中同時(shí)含有形如 UaAUaBUaCUaX的產(chǎn)生式，在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，就會(huì)出現(xiàn)這樣的結(jié)點(diǎn)U，它具有多條標(biāo)記為同一輸入符號(hào)a的矢線，如右圖所示圖3-8NFA的狀態(tài)轉(zhuǎn)換圖由上圖可知，在U狀態(tài)下，輸入符號(hào)為a時(shí)，F(xiàn)A的下一狀態(tài)不唯一，而是在狀態(tài)集{A,B,C,…,X}中任選其一。具有這種性質(zhì)的FA稱為非確定的FA（NFA:Nondeterministic

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

f:K(K),即將(Si,aj)映射到K的一個(gè)子集{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ù)類似的理由，我們將對(duì)f和f^不加區(qū)分57NFA的接受集對(duì)于x*,若集合f(S0,x)中含有Z中的元素（終態(tài)），則說明，至少存在一條從初態(tài)S0到某一終態(tài)的路徑，此路徑上的符號(hào)之連接恰為x，此時(shí)，我們稱x為M所接受所有為M所接受的符號(hào)串之集稱為NFAM的接受集（或識(shí)別集），記作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識(shí)別符號(hào)串a(chǎn)babb的路徑為S(a)A(b)B(a)A(b)B(b)C(接受)。(參見書中P60的表)SABCaa,babbaa注意，NFA識(shí)別輸入符號(hào)串時(shí)有一個(gè)試探過程，為了能走到終態(tài)，往往要走許多彎路（帶回溯），這影響了FA的效率。能否提高其工作效率就是我們下一小節(jié)討論的課題。事實(shí)上，對(duì)任一NFAM，總可構(gòu)造一個(gè)DFAM’，使L(M’)=L(M)成立。這就是NFA與DFA的等價(jià)性。58DFA與NFA的區(qū)別DFANFA開始狀態(tài)唯一一個(gè)或多個(gè)映像單個(gè)狀態(tài)狀態(tài)集合59舉例前述文法G3.2對(duì)應(yīng)的自動(dò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所接受)對(duì)于輸入字符串babbabb，運(yùn)行NFA步驟當(dāng)前狀態(tài)輸入的其余部分可能的后繼選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZabABabZbaaaaS61運(yùn)行NFA運(yùn)行NFA：識(shí)別一個(gè)字符串是否被NFA所接受，是否能達(dá)到終態(tài)集合中的某個(gè)狀態(tài)實(shí)質(zhì)：用自底向上方法識(shí)別句子狀態(tài)轉(zhuǎn)換的下一狀態(tài)不唯一，如何解決？62DFA和NFA的關(guān)系對(duì)于Σ*上的字符串β，如果存在一條從初態(tài)到終態(tài)的通路，且這條通路上的輸入字符恰好連接成β，稱為β可以此DFA、NFA識(shí)別DFA、NFA都可以識(shí)別一個(gè)字符集Σ上的字符串可以用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)集開始，求對(duì)于每個(gè)輸入符號(hào)的后繼狀態(tài)集合Si——新的狀態(tài)對(duì)每個(gè)Si，求對(duì)于每個(gè)輸入符號(hào)的后繼狀態(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è)它對(duì)應(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具有動(dòng)作的FA若在一FA中,允許對(duì)也作狀態(tài)轉(zhuǎn)移,則這樣的FA稱為具有動(dòng)作的FA(NFA).此時(shí),有的矢線上標(biāo)記為標(biāo)記為的矢線對(duì)識(shí)別符號(hào)串無影響,但卻改變了當(dāng)前的狀態(tài).例如,右圖中的FA中,從狀態(tài)0到狀態(tài)3存在路徑:0(a)0(a)0()2(c)2(c)2()3,即M識(shí)別了aacc=aacc.~的定義

M=(K,,f,S0,Z),其中,f的定義為f:K({})(K).在~中,可以視為一個(gè)輸入符號(hào),在矩陣表示中,也有相應(yīng)的列.0123abbcf也可以拓廣到f’:K*(K).f’(S,x)是由這樣的狀態(tài)Q組成,存在從S到Q的路徑,該路徑上的連線標(biāo)記組成的符號(hào)串恰好為x,其中,允許有有限個(gè)標(biāo)記為76狀態(tài)S的-閉包：-CLOSURE(S)為定義拓廣的f’,我們首先引入每個(gè)狀態(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，就可把識(shí)別各種不同單詞的FA用矢線（并連）連接起來，組成一個(gè)單一的NFA，經(jīng)確定化后可得識(shí)別所有單詞的DFA，由此可設(shè)計(jì)編譯程序的詞法分析器。例如，某語言的單詞有：1.BEGIN 2.END 3.IF 4.THEN 5.ELSE6.標(biāo)識(shí)符 7.無符號(hào)整數(shù) 8.< 9.<= 10.= 11.<> 12.> 13.>=我們可容易地分別構(gòu)造出識(shí)別各類單詞的FA,然后將其合并為一個(gè)大FA,如書中P65圖3-11所示(由于較難描繪,這里略去,請(qǐng)自行參閱教材)80ε閉包狀態(tài)集I的ε_(tái)CLOSURE(I)如果q屬于Iq屬于ε_(tái)CLOSURE(I)從q出發(fā)經(jīng)任意條ε弧到達(dá)的任何狀態(tài)q’都屬于ε_(tái)CLOSURE(I)81具有動(dòng)作的NFA的確定化設(shè)已給具有動(dòng)作的NFAM=(K,,f,S0,Z),構(gòu)造相應(yīng)的DFAM’=(K’,,f’,q0,Z’)的方法是，先令q0=[-CLOSURE(S0)],然后對(duì)每個(gè)a，令[-CLOSURE(f’(q0,a))]為新狀態(tài)，如此反復(fù)，直到無新狀態(tài)產(chǎn)生：1.令K’={[-CLOSURE(S0)]};f’=;2.對(duì)K’中尚未被標(biāo)記的狀態(tài)qi=[Si1,Si2,…,Sim]: (1)標(biāo)記qi; (2)對(duì)于每個(gè)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確定化具有動(dòng)作的NFA的例子例3.4考慮前面引入的具有動(dòng)作的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

對(duì)于書中圖3-13所示的NFA利用上述算法所得的DFA如P67圖3-13所示.其中,圓圈中的數(shù)字是原NFA的狀態(tài)編號(hào),在圖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的化簡(jiǎn)狀態(tài)的等價(jià)性能夠識(shí)別相同的字符串劃分為終態(tài)和非終態(tài)兩個(gè)子集如果某個(gè)子集中的狀態(tài)是可區(qū)分的，則進(jìn)一步劃分這個(gè)子集直到在每個(gè)子集內(nèi)，各個(gè)狀態(tài)都是不可區(qū)分的。同一子集內(nèi)的狀態(tài)合并。85DFA狀態(tài)數(shù)的最小化對(duì)于一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劃分為兩個(gè)子集Z和K-Z,顯然分屬于這兩個(gè)集合的狀態(tài)是可(被)區(qū)分的.記={Z,K-Z}.2.設(shè)當(dāng)前的劃分中已含有m個(gè)子集:={I1,I2,…,Im},其中,屬于不同子集的狀態(tài)是可區(qū)分的,而屬于同一子集中的狀態(tài)則待區(qū)分.現(xiàn)對(duì)每個(gè)子集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被子某個(gè)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.對(duì)于最終的，從每個(gè)劃分塊中任選一狀態(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化簡(jiǎn)的例子設(shè)有一個(gè)DFAM=(K，，f，S，Z)，其狀態(tài)圖如下圖所示。對(duì)其進(jìn)行化簡(jiǎn)。21ba03abbaab89DFA的化簡(jiǎn)示例 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)簡(jiǎn)化為{1,2}9013aabab21a2ab化簡(jiǎn)前的DFA化簡(jiǎn)后的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ū)分的兩個(gè)集合用e表示出錯(cuò)狀態(tài)非終止?fàn)顟B(tài)集{0,1,2}——不認(rèn)識(shí)ε終止?fàn)顟B(tài)集{3,4,5,6}——認(rèn)識(shí)ε{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的特例。對(duì)于每個(gè)NFA

M，存在一個(gè)DFA

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

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

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

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

§3.4NFA與DFA的等價(jià)性101§3.5正規(guī)文法與有窮自動(dòng)機(jī)之間的轉(zhuǎn)換設(shè)右線性文法G=(VN，VT，P，S)，下面介紹將其轉(zhuǎn)換成有窮自動(dòng)機(jī)M=(K，，f，S0，Z)，使得L(G)=L(M)的方法。令K=VNZ，Z是M中新增的終態(tài)；=VT，S0=S；f由下列方法確定：對(duì)于G的每條形如AaB的規(guī)則，在M中設(shè)轉(zhuǎn)換函數(shù)f(A,a)=B；對(duì)于G的每條形如Aa的規(guī)則，在M中設(shè)轉(zhuǎn)換函數(shù)f(A,a)=Z。102例對(duì)于正規(guī)文法G[S]：SaB|bBBbS|a|b，可以轉(zhuǎn)換成自動(dòng)機(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。這是一個(gè)NFA。對(duì)應(yīng)的狀態(tài)圖如下：SaBZbbab103有窮自動(dòng)機(jī)轉(zhuǎn)換成右線性文法若有限自動(dòng)機(jī)是NFA則將其確定化，設(shè)確定的有窮自動(dòng)機(jī)M=(K，，f，S0，Z)，則轉(zhuǎn)換得到右線性文法G=(VN，VT，P，S)，其中：VN=K，VT=，S=S0，P中的規(guī)則用如下方法確定：對(duì)M中任一形如f(A,a)=B的轉(zhuǎn)換函數(shù)，有規(guī)則AaBP；對(duì)M中的終態(tài)Z，則加一條規(guī)則ZP。104左線性文法轉(zhuǎn)換成自動(dòng)機(jī)的方法設(shè)左線性文法G=(VN，VT，P，S)，有窮自動(dòng)機(jī)M=(K，，f，S0，Z)，則M中的K=VNS0，S0

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

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

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

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

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

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

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

%%

識(shí)別規(guī)則

%%

用戶子程序125

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

AuxiliaryDefinitions /*輔助定義*/letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣zdigit→0∣1∣2∣3∣…∣9%%RecognitionRules /*識(shí)別規(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)