《編譯原理》課件第2章

第2章詞法分析2.1詞法分析器設(shè)計(jì)方法2.2一個(gè)簡(jiǎn)單的詞法分析器實(shí)例2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造2.5詞法分析器的自動(dòng)生成習(xí)題二任務(wù)：

從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符號(hào)，把字符串形式的源程序改造成為單詞符號(hào)串形式的中間程序。詞法分析器/掃描器：執(zhí)行詞法分析的程序詞法分析可以采用如下兩種處理結(jié)構(gòu)：

(1)把詞法分析程序作為主程序。將詞法分析工作作為獨(dú)立的一遍來(lái)完成，即把詞法分析與語(yǔ)法分析明顯分開(kāi)，由詞法分析程序?qū)⒆址问降脑闯绦蚋脑斐蓡卧~符號(hào)串形式的中間程序，以這個(gè)中間程序作為語(yǔ)法分析程序的輸入。在這種處理結(jié)構(gòu)中，詞法分析和語(yǔ)法分析是分別實(shí)現(xiàn)的，如圖2–1(a)所示。

(2)把詞法分析程序作為語(yǔ)法分析程序調(diào)用的子程序。在進(jìn)行語(yǔ)法分析時(shí)，每當(dāng)語(yǔ)法分析程序需要一個(gè)單詞時(shí)便調(diào)用詞法分析程序，詞法分析程序每一次調(diào)用便從字符串源程序中識(shí)別出一個(gè)單詞交給語(yǔ)法分析程序。在這種處理結(jié)構(gòu)中，詞法分析和語(yǔ)法分析實(shí)際上是交替進(jìn)行的，如圖2–1(b)所示。由于把詞法分析器安排成一個(gè)子程序比較自然，因此，詞法分析程序通常采用第二種處理結(jié)構(gòu)。圖2–1詞法分析的兩種處理結(jié)構(gòu)(a)詞法分析程序作為主程序；

(b)詞法分析程序作為子程序

2.1

詞法分析器設(shè)計(jì)方法1.單詞符號(hào)的分類(lèi)與輸出形式單詞符號(hào)1.保留字：2.標(biāo)識(shí)符：3.常數(shù)：4.運(yùn)算符：5.界符：

是編譯程序識(shí)別各類(lèi)語(yǔ)法成分的依據(jù)，也可以稱(chēng)為基本字。這些字保留了語(yǔ)言所規(guī)定的含義，如C語(yǔ)言中的if、else、while和do等單詞符號(hào)：是程序語(yǔ)言的基本語(yǔ)法單位

用來(lái)標(biāo)記常量、數(shù)組、類(lèi)型、變量、過(guò)程或函數(shù)名等

包括各種類(lèi)型的常數(shù)，如整型常數(shù)386、實(shí)型常數(shù)0.618、布爾型常數(shù)TRUE等。如“+”、“?”、“*”、“/”、“>”、“<”等。在語(yǔ)言中是作為語(yǔ)法上的分界符號(hào)使用的一個(gè)程序語(yǔ)言的保留字、運(yùn)算符和界符的個(gè)數(shù)是確定的標(biāo)識(shí)符或常數(shù)的使用則不限定個(gè)數(shù)2.1

詞法分析器設(shè)計(jì)方法詞法分析程序輸出單詞的形式

輸出是與源程序等價(jià)的單詞符號(hào)序列，并且所輸出的單詞符號(hào)通常表示成如下的二元式：（單詞種別，單詞自身的值）（1）單詞種別：

表示單詞的種類(lèi)，它是語(yǔ)法分析所需要的信息。一個(gè)語(yǔ)言的單詞符號(hào)如何劃分種類(lèi)、分為幾類(lèi)、如何編碼都屬于技術(shù)性問(wèn)題，取決于處理上的方便。種別劃分可以全體視為一種，也可以一字一種

一般統(tǒng)歸為一種可統(tǒng)歸為一種，也可按整型、實(shí)型、布爾型等分為幾種

采用一符一種采用一符一種保留字：標(biāo)識(shí)符：常數(shù)：運(yùn)算符：界符：2.1

詞法分析器設(shè)計(jì)方法（2）單詞自身的值

對(duì)于單詞符號(hào)來(lái)說(shuō)，如果一個(gè)種別只含有一個(gè)單詞符號(hào)，其種別編碼就完全代表了它自身的值。如果一個(gè)種別含有多個(gè)單詞符號(hào)，那么對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別編碼之外還應(yīng)給出單詞符號(hào)自身的值。

標(biāo)識(shí)符自身的值就是標(biāo)識(shí)符自身的字符串，而常數(shù)自身的值是常數(shù)本身的二進(jìn)制數(shù)值是編譯中其它階段所需要的信息

注意：2.1

詞法分析器設(shè)計(jì)方法2.狀態(tài)轉(zhuǎn)換圖

在詞法分析中，可以用狀態(tài)轉(zhuǎn)換圖來(lái)識(shí)別單詞。狀態(tài)轉(zhuǎn)換圖是有限的有向圖，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示；結(jié)點(diǎn)之間可由有向邊連接，有向邊上可標(biāo)記字符。

在狀態(tài)i下，若輸入字符為x，則讀入x并轉(zhuǎn)換到狀態(tài)j；若輸入字符為y，則讀入y并轉(zhuǎn)換到狀態(tài)k。2.1

詞法分析器設(shè)計(jì)方法

狀態(tài)（即結(jié)點(diǎn)）數(shù)是有限的，其中必有一初始狀態(tài)以及若干終止?fàn)顟B(tài)，終止?fàn)顟B(tài)（終態(tài)）的結(jié)點(diǎn)用雙圈表示以區(qū)別于其它狀態(tài)。標(biāo)識(shí)符無(wú)符號(hào)整數(shù)無(wú)符號(hào)數(shù)2.1

詞法分析器設(shè)計(jì)方法

某些終止?fàn)顟B(tài)是在讀入了一個(gè)其它不屬于該單詞的符號(hào)后才得到相應(yīng)的單詞編碼的，這表明在識(shí)別單詞的過(guò)程中多讀入了一個(gè)符號(hào)，所以識(shí)別出單詞后應(yīng)將最后多讀入的這個(gè)符號(hào)予以回退；我們對(duì)此類(lèi)情況的處理是在終態(tài)上以“*”作為標(biāo)識(shí)。2.1

詞法分析器設(shè)計(jì)方法

對(duì)于不含回路的分支狀態(tài)來(lái)說(shuō)，可以讓它對(duì)應(yīng)一個(gè)switch(?)

語(yǔ)句或一組if-else語(yǔ)句。s=getchar(?);switch(s){?case'a':case'b':…case'z':…;//實(shí)現(xiàn)狀態(tài)j功能的語(yǔ)句case'0':case'1':…case'9':…;//實(shí)現(xiàn)狀態(tài)k功能的語(yǔ)句}2.1

詞法分析器設(shè)計(jì)方法對(duì)于含回路的狀態(tài)來(lái)說(shuō)，可以讓它對(duì)應(yīng)一個(gè)while語(yǔ)句。

getchar(?);while(?letter(?)||digit(?))getchar(?);…; //實(shí)現(xiàn)狀態(tài)j功能的語(yǔ)句2.2一個(gè)簡(jiǎn)單的詞法分析器實(shí)例

大多數(shù)程序語(yǔ)言的單詞符號(hào)都可以用狀態(tài)轉(zhuǎn)換圖予以識(shí)別。作為一個(gè)綜合例子，我們來(lái)構(gòu)造一個(gè)C語(yǔ)言子集的簡(jiǎn)單詞法分析器。狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)

C語(yǔ)言子集的單詞符號(hào)表示C語(yǔ)言子集對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖

2.2.1C語(yǔ)言子集的單詞符號(hào)表示2.2一個(gè)簡(jiǎn)單的詞法分析器實(shí)例單詞符號(hào)種別編碼助記符內(nèi)碼值while1while—if2if—else3else—switch4switch—case5case—標(biāo)識(shí)符6idid在符號(hào)表中的位置常數(shù)7numnum在常數(shù)表中的位置+8+—?9?—*10*—<=11relopLE<11relopLT==11relopEQ=12=—；13；—2.2.2C語(yǔ)言子集對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖在設(shè)計(jì)的狀態(tài)轉(zhuǎn)換圖中，首先對(duì)輸入串做預(yù)處理，即剔除多余的空白符(在實(shí)際的詞法分析中，預(yù)處理還包括剔除注釋和制表?yè)Q行符等編輯性字符的工作)，使詞法分析工作既簡(jiǎn)單又清晰。其次，將保留字作為一類(lèi)特殊的標(biāo)識(shí)符來(lái)處理，也即對(duì)保留字不專(zhuān)設(shè)對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖，當(dāng)轉(zhuǎn)換圖識(shí)別出一個(gè)標(biāo)識(shí)符時(shí)就去查對(duì)表2.1的前五項(xiàng)，確定它是否為一個(gè)保留字。當(dāng)然，也可以專(zhuān)設(shè)一個(gè)保留字表來(lái)進(jìn)行處理。2.2.3狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換圖非常容易用程序?qū)崿F(xiàn)，最簡(jiǎn)單的辦法是讓每個(gè)狀態(tài)對(duì)應(yīng)一小段程序。對(duì)于圖2–5所示的狀態(tài)轉(zhuǎn)換圖，我們首先引進(jìn)一組變量和過(guò)程如下：

(1)character：字符變量，存放最新讀入的源程序字符。

(2)token：字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串。

(3)getbe()：若character中的字符為空白，則調(diào)用getchar()，直至character為非空白字符為止。

(4)concatenation()：將token中的字符串與character中的字符連接并作為token中新的字符串。

(5)letter()和digit()：判斷character中的字符是否為字母和數(shù)字的布爾函數(shù)，是則返回true，否則返回false。

(6)reserve()：按token數(shù)組中的字符串查表2.1中的前五項(xiàng)(即判別其是否為保留字)，若是保留字則返回它的編碼，否則返回0值。

(7)retract()：掃描指針回退一個(gè)字符，同時(shí)將character置為空白。

(8)buildlist()：將標(biāo)識(shí)符登錄到符號(hào)表中或?qū)⒊?shù)登錄到常數(shù)表中。

(9)error()：出現(xiàn)非法字符，顯示出錯(cuò)信息。相對(duì)于圖2–5的詞法分析器構(gòu)造如下：

token=''; /*對(duì)token數(shù)組初始化*/

s=getchar();

getbe(); /*濾除空格*/

switch(s)

{

case'a':

case'b':

…

case'z':

while(letter()‖digit())

{

concatenation();

/*將當(dāng)前讀入的字符送入token數(shù)組*/

getchar();

}

retract(); /*掃描指針回退一個(gè)字符*/

c=reserve();

if(c==0)

{

buildlist(); /*將標(biāo)識(shí)符登錄到符號(hào)表中*/

return(id，指向id的符號(hào)表入口指針);

}

else

return(保留字碼，null);

break;

case'0':

case'1':

…

case'9':

while(digit())

{

concatenation();

getchar();

}

retract();

buildlist(); /*將常數(shù)登錄到常數(shù)表中*/

return(num，num的常數(shù)表入口指針);

break;

case'+':

return('+'，null);

break;

case'?':

return('?'，null);

break;

case'*':

return('*'，null);

break;

case'<':

getchar();

if(character=='=')

return(relop,LE);

else

{

retract();

return(relop，LT);

}

break;

case'=':

getchar();

if(character=='=')

return(relop,EQ);

else

{

retract();

return('=',null);

}

break;

case';':

return(';',null);

break;

default:

error();

}2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介

為了便于詞法分析器的自動(dòng)生成，須將狀態(tài)轉(zhuǎn)換圖的概念加以形式化。正規(guī)表達(dá)式就是一種形式化的表示法，它可以表示單詞符號(hào)的結(jié)構(gòu)，從而精確地定義單詞符號(hào)集。正規(guī)表達(dá)式簡(jiǎn)稱(chēng)為正規(guī)式，它表示的集合即為正規(guī)集。1.正規(guī)表達(dá)式與正規(guī)集例：字母用letter表示，數(shù)字用digit表示

Letter(letter∣digit)*letter或digit兩者選一零次或多次引用由“?*?”標(biāo)記的表達(dá)式letter?(letter∣digit)*表示以字母開(kāi)頭的字母數(shù)字串，也即標(biāo)識(shí)符集。就是表示標(biāo)識(shí)符的正規(guī)式，而標(biāo)識(shí)符集就是這個(gè)正規(guī)式所表示的正規(guī)集。2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介對(duì)于給定的字母表Σ，正規(guī)式和正規(guī)集的遞歸定義如下：

（1）ε和Ф都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和Ф。（2）對(duì)任一個(gè)a∈Σ，a是Σ上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}?；A(chǔ)規(guī)則:（3）如果R和S是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(R)?和L(S)，則：①R∣S是Σ上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(R)∪L(S)；②R?S是Σ上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(R)?L(S)；③(R)*是Σ上的正規(guī)式，它所表示的正規(guī)集為(L(R))*；④R也是Σ上的正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(R)。歸納規(guī)則:2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介（4）僅由有限次使用規(guī)則（1）～（3）得到的表示式是Σ上的正規(guī)式，它所表示的集合是Σ上的正規(guī)集。界限規(guī)則（終止規(guī)則）

Σ上的一個(gè)字是指由Σ中的字符所構(gòu)成的一個(gè)有窮序列；不包含任何字符的序列稱(chēng)為空字，用ε表示。我們用Σ*表示Σ上所有字的全體，則空字ε也在其中。用Ф表示不含任何元素的空集{}。這里需要注意ε、{?}和{ε}的區(qū)別：{ε}是由空字組成的集合，而{?}則表示不含任何字的集合。例如，若Σ={a,?b}，則Σ*={ε,

a,

b,

aa,

ab,

ba,

bb,

aaa,

…}2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介“∣”表示或“?”表示連接（通常可省略）“?*?”表示閉包，使用括號(hào)可以改變運(yùn)算的次序

如果規(guī)定“?*?”優(yōu)先于“?”，“?”優(yōu)先于“∣”，則在不出現(xiàn)混淆的情況下括號(hào)也可以省去。2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介Σ*的正規(guī)式R和S的連接可以形式化地定義為RS={αβ∣α∈R?&β∈S}

即集合RS中的字是由R和S中的字連接而成的，且R自身的n次連接記為Rn=RR…R

我們規(guī)定R0={ε}，并令R*=R0∪R1∪R2∪R3∪…，則稱(chēng)R*是R的閉包；此外，令R+=RR*，并稱(chēng)R+是R的正則閉包。閉包R*中的每個(gè)字都是由R中的字經(jīng)過(guò)有限次連接而生成的。n個(gè)2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介

對(duì)于Σ上的正規(guī)式R和S，如果它所表示的正規(guī)集L(R)?=L(S)，則稱(chēng)R和S等價(jià)并記為R=S。正規(guī)式具有下列性質(zhì)：交換律：R∣S=S∣R結(jié)合律：R∣(S∣T)=(R∣S)∣TR(ST)=(RS)T分配律：R(S∣T)=RS∣RT (R∣S)T=RT∣ST同一律：εR=Rε=R2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介2.有限自動(dòng)機(jī)

有限自動(dòng)機(jī)（FA）是更一般化的狀態(tài)轉(zhuǎn)換圖，它分為確定有限自動(dòng)機(jī)DFA和非確定有限自動(dòng)機(jī)NFA兩種。確定有限自動(dòng)機(jī)（DFA）

一個(gè)確定的有限自動(dòng)機(jī)Md（記為DFAMd）是一個(gè)五元組（1）S是一個(gè)有限狀態(tài)集，它的每一個(gè)元素稱(chēng)為一個(gè)狀態(tài)；（2）Σ是一個(gè)有窮輸入字母表，它的每一個(gè)元素稱(chēng)為一個(gè)輸入字符；（3）f是一個(gè)從S×Σ到S的單值映射，即f(si,?a)?=sj且有si、sj∈S和a∈Σ；（4）s0∈S，是惟一的一個(gè)初態(tài)；（5）Z

S，是一個(gè)終態(tài)集。Md=?(S,?Σ,?f,?s0,?Z)2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介f(si,

a)

=sj表示當(dāng)前狀態(tài)為si且輸入字符為a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)換到下一個(gè)狀態(tài)sj，也即sj稱(chēng)為si的一個(gè)后繼狀態(tài)。狀態(tài)轉(zhuǎn)換函數(shù)f是單值函數(shù)，f(si,

a)

惟一確定了下一個(gè)要轉(zhuǎn)換的狀態(tài)，即由每個(gè)狀態(tài)發(fā)出的有向邊（輸出邊）上所標(biāo)記的輸入字符各不相同。

例如，對(duì)右圖給出的狀態(tài)s1有：

f(s1,?a)?=s2

f(s1,?b)?=s3

f(s1,?c)?=s4因此，f是單值映射函數(shù)。

注意：2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介一個(gè)非確定有限自動(dòng)機(jī)Mn（記為NFAMn）是一個(gè)五元組非確定有限自動(dòng)機(jī)（NFA）Mn=

(S,?Σ,

f,

Q,

Z)（1）S、Σ、Z的意義與DFA相同；（2）f是一個(gè)從S×Σ*到S的子集映射；（3）Q

S，是一個(gè)非空初態(tài)集。2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介NFA可以有若干個(gè)初始狀態(tài)，而DFA僅有一個(gè)

初始狀態(tài)；NFA和DFA的區(qū)別NFA的狀態(tài)轉(zhuǎn)換函數(shù)f是一個(gè)多值函數(shù)??2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介對(duì)下圖所給出的狀態(tài)s1有：例f(s1,?a)?={s1,?s2,?s3}

即f是一個(gè)從S×Σ*到S的子集映射；Σ*表示輸出邊上所標(biāo)記的不僅是字符，也可以是字。此外，NFA還允許f(s1,ε)={某些狀態(tài)的集合}，即在NFA的狀態(tài)轉(zhuǎn)換圖中輸出邊上的標(biāo)記還可是ε（空字）。2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介3.狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣

DFA和NFA都可以用狀態(tài)轉(zhuǎn)換圖表示。假定DFA（或NFA）有m個(gè)狀態(tài)、n個(gè)輸入字符（或字），則這個(gè)狀態(tài)轉(zhuǎn)換圖含有m個(gè)狀態(tài)，每個(gè)狀態(tài)最多有n條輸出邊與其它狀態(tài)相連接，每一條輸出邊用Σ（或Σ*）中的一個(gè)不同的輸入字符（或一個(gè)輸入字）作標(biāo)記，整個(gè)圖含有惟一一個(gè)初態(tài)（或多個(gè)初態(tài)）和若干個(gè)終態(tài)。

DFA和NFA也可以用狀態(tài)轉(zhuǎn)換矩陣表示。狀態(tài)轉(zhuǎn)換矩陣的行表示狀態(tài)，列表示輸入符號(hào)，矩陣元素表示f(si,

a)?的值。2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介假定DFAMd=?({s0,?s1,?s2},?{a,?b},?f,?s0,?{s2})，且有：

f(s0,?a)?=s1f(s0,?b)?=s2 f(s1,?a)?=s1f(s1,?b)?=s2 f(s2,?a)?=s2f(s2,?b)?=s1試給出DFAMd的狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣。

字符狀態(tài)abs0s1s2s1s1s2s2s2s1例狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換矩陣2.3正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介

對(duì)于任何兩個(gè)FAM和FAM'，如果L(M)

=L(M')，則稱(chēng)有限自動(dòng)機(jī)M和M'等價(jià)。此外，對(duì)于任一給定的NFAM，一定存在一個(gè)DFAM'，使L(M)

=L(M')。因此，DFA是NFA的特例，NFA可以有DFA與之等價(jià)，即兩者描述能力相同。DFA便于識(shí)別，易于計(jì)算機(jī)實(shí)現(xiàn)，而NFA便于定理的證明。

注意：2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造

由正規(guī)表達(dá)式與有限自動(dòng)機(jī)的等價(jià)性可知：如果R是Σ上的一個(gè)正規(guī)表達(dá)式，則必然存在一個(gè)NFAM，使得L(M)

=L(R)；反之亦然。1.由正規(guī)表達(dá)式構(gòu)造等價(jià)的非確定有限自動(dòng)機(jī)（NFA）

由正規(guī)表達(dá)式構(gòu)造等價(jià)的NFAM的方法如下：（1）將正規(guī)表達(dá)式R表示成如圖2-10所示的拓廣轉(zhuǎn)換圖。（2）對(duì)正規(guī)表達(dá)式采用如圖2-11所示的三條轉(zhuǎn)換規(guī)則來(lái)構(gòu)造NFAM。

對(duì)于給定的正規(guī)表達(dá)式R，首先將其表示成如圖2-10所示的形式，其中X為初始狀態(tài)，Y為終止?fàn)顟B(tài)；然后逐步將這個(gè)拓廣轉(zhuǎn)換圖運(yùn)用圖2-11的三條轉(zhuǎn)換規(guī)則不斷加入新結(jié)點(diǎn)進(jìn)行分解，直至每條有向邊上僅標(biāo)識(shí)有Σ的一個(gè)字母或ε為止，則NFAM構(gòu)造完成。2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造2.NFA的確定化NFA的確定化是指對(duì)給定的NFA都能相應(yīng)地構(gòu)造出一個(gè)與之等價(jià)的DFA，使它們能夠識(shí)別相同的語(yǔ)言。我們采用子集法來(lái)對(duì)NFAM確定化。首先定義FAM的一個(gè)狀態(tài)子集I的ε_(tái)閉包，即ε_(tái)CLOSURE(I)，則：（1）若si∈I，則si∈ε_(tái)CLOSURE(I)；（2）若si∈I，則對(duì)從si出發(fā)經(jīng)過(guò)ε通路所能到達(dá)的任何狀態(tài)sj，都有sj∈ε_(tái)CLOSURE(I)。其次，對(duì)FAM的一個(gè)狀態(tài)子集I，若a是Σ中的一個(gè)字符，定義

Ia=ε_(tái)CLOSURE(J)

其中，J是所有那些可以從I中的某一狀態(tài)出發(fā)經(jīng)過(guò)有向邊a而能到達(dá)的狀態(tài)集。2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造

已知一狀態(tài)轉(zhuǎn)換圖下圖所示，且假定I=ε_(tái){1}={1,

2}，試求從狀態(tài)I出發(fā)經(jīng)過(guò)一條有向邊a而能到達(dá)的狀態(tài)集J和ε_(tái)CLOSURE(J)。

[解答]

從狀態(tài)I中的狀態(tài)1或狀態(tài)2出發(fā)經(jīng)過(guò)一條a弧而能到達(dá)的狀態(tài)集J為

{5,

3,

4}

若si∈J，則由si出發(fā)經(jīng)過(guò)任意條ε有向邊而能到達(dá)的任何狀態(tài)sj∈ε_(tái)CLOSURE(J)，因此ε_(tái)CLOSURE(J)?為

{5,

6,

2,

3,

8,

4,

7}例2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造用子集法對(duì)NFA確定化的方法如下：（1）構(gòu)造一張轉(zhuǎn)換表，其第一列為狀態(tài)子集I，對(duì)不同的a（a∈Σ）在表中單設(shè)一列Ia。（2）表的第一行第一列其狀態(tài)子集I為ε_(tái)CLOSURE(s0)；其中，s0為初始狀態(tài)。（3）根據(jù)第一列中的I為每一個(gè)a求其Ia并記入對(duì)應(yīng)的Ia列中，如果此Ia不同于第一列已存在的所有狀態(tài)子集I，則將其順序列入空行中的第一列。（4）重復(fù)步驟（3）直至對(duì)每個(gè)I及a均已求得Ia，并且無(wú)新的狀態(tài)子集Ia加入第一列時(shí)為止；此過(guò)程可在有限步后終止。（5）重新命名第一列的每一狀態(tài)子集，則轉(zhuǎn)換表便成為新的狀態(tài)轉(zhuǎn)換矩陣，其狀態(tài)轉(zhuǎn)換函數(shù)f是S×Σ到S的單值映射，即為與NFAM等價(jià)的DFAM'。2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造3.確定有限自動(dòng)機(jī)（DFA）的化簡(jiǎn)

對(duì)NFA確定化后所得到的DFA可能含有多余的狀態(tài)，因此還應(yīng)對(duì)其進(jìn)行化簡(jiǎn)。所謂DFAM的化簡(jiǎn)，是指尋找一個(gè)狀態(tài)數(shù)比M少的DFAM‘，使得L(M)

=L(M’)?；?jiǎn)了的DFAM‘滿(mǎn)足下述兩個(gè)條件：（1）沒(méi)有多余狀態(tài)；（2）在其狀態(tài)集中，沒(méi)有兩個(gè)相互等價(jià)的狀態(tài)存在。

對(duì)一給定的DFAM，若存在狀態(tài)s1、s2∈S且s1≠s2，如果從s1出發(fā)能識(shí)別字符串α而停于終態(tài)，從s2出發(fā)也同樣能夠識(shí)別這個(gè)α而停于終態(tài)；反之，若從s2出發(fā)能識(shí)別β而停于終態(tài)，則從s1出發(fā)也能識(shí)別這個(gè)β而停于終態(tài)，則稱(chēng)s1和s2是等價(jià)的，否則就是可區(qū)分的。2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造（1）首先將DFAM的狀態(tài)集S中的終態(tài)與非終態(tài)分開(kāi)，形成兩個(gè)子集，即得到基本劃分。（2）對(duì)當(dāng)前已劃分出的I(1)、I(2)、…、I(m)子集（屬于不同子集的狀態(tài)是可區(qū)分的），看每一個(gè)I是否能進(jìn)一步劃分；也即對(duì)某個(gè)I(i)={s1,

s2,

…,

sk}，若存在一個(gè)輸入字符a（a∈Σ）使得Ia(i)不全包含在當(dāng)前劃分的某一子集I(j)中（即跨越到兩個(gè)子集），就將I(i)一分為二（3）重復(fù)步驟（2），直到子集個(gè)數(shù)不再增加為止（即每個(gè)子集已是不可再分的了）。所謂不能劃分，是指該子集或者僅有一個(gè)狀態(tài)，或者雖有多個(gè)狀態(tài)但這些狀態(tài)均不可區(qū)分（即等價(jià)）。DFAM的化簡(jiǎn)方法如下：2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造化簡(jiǎn)由例2.8得到的DFA（1）首先將狀態(tài)集S={0,

1,

2,

3,

4,

5,

6}劃分為終態(tài)集{3,

4,

5,

6}和非終態(tài)集{0,

1,

2}。（2）考察{0,?1,?2}a：因0a=2a={1}，而1a={3}，分屬于非終態(tài)集和終態(tài)集，故將{0,?1,?2}劃分為{0,?2}和{1}。（3）考察{0,

2}b：0b={2}，2b={4}，它們分屬于兩個(gè)不同的狀態(tài)集，故{0,

2}劃分為{0}和{2}。（4）考察{3,?4,?5,?6}a：3a=6a={3}{3,?4,?5,?6}；4a=5a={6}{3,?4,?5,?6}，即都屬于終態(tài)集，故不進(jìn)行劃分。（5）考察{3,?4,?5,?6}b：3b=6b={5}{3,?4,?5,?6}；4b=5b={4}{3,?4,?5,?6}，即都屬于終態(tài)集，故不進(jìn)行劃分。（6）按順序重新命名狀態(tài)子集{0}、{1}、{2}、{3,

4,

5,

6}為0、1、2、3，則得到化簡(jiǎn)后的狀態(tài)轉(zhuǎn)換矩陣（見(jiàn)表2.6）和DFAM''例[解答]2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造Sab012132213333狀態(tài)轉(zhuǎn)換矩陣

化簡(jiǎn)后的DFAM''

2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造4.正規(guī)表達(dá)式到有限自動(dòng)機(jī)構(gòu)造示例

試用DFA的等價(jià)性證明正規(guī)表達(dá)式

(

a∣b

)*與

(

a*b*

)*等價(jià)。[解答]（1）正規(guī)表達(dá)式

(a∣b)*對(duì)應(yīng)的NFA如圖所示。

例2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造

用子集法將NFA確定化得到第一張表所列的轉(zhuǎn)換表，重新命名后得到第二張表所列的狀態(tài)轉(zhuǎn)換矩陣。

IIaIb{X,1,Y}{1,Y}{1,Y}{1,Y}{1,Y}{1,Y}Sab0111112.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造

由于狀態(tài)0和狀態(tài)1均為終態(tài)，故無(wú)論輸入什么字符，其下一狀態(tài)仍是終態(tài)，故最簡(jiǎn)DFA如圖所示。

2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造（2）正規(guī)表達(dá)式?(

a*b*

)*對(duì)應(yīng)的NFA如圖所示。

2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造

用子集法將圖2-20所示的NFA確定化得到第一個(gè)表所列的轉(zhuǎn)換表，重新命名得到第二個(gè)表所列的狀態(tài)轉(zhuǎn)換矩陣。

IIaIb{X,1,2,3,Y}{2,3,1,Y}{2,3,1,Y}{2,3,1,Y}{2,3,1,Y}{2,3,1,Y}Sab011111由于兩個(gè)狀態(tài)轉(zhuǎn)換矩陣相同，故?(

a∣b

)*和

(

a*b*

)*等價(jià)。2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造對(duì)正規(guī)表達(dá)式a*b*構(gòu)造DFA，則首先畫(huà)出NFA如圖所示abεXY

注意：2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造IIaIb{X,Y}{X,Y}{Y}{Y}—{Y}Sab0011—1

用子集法將上圖所示的NFA確定化得到如表一所列的轉(zhuǎn)換表，重新命名得到如表二所列的狀態(tài)轉(zhuǎn)換矩陣。（表中的空集Φ一律用“—”表示）

2.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造

雖然狀態(tài)0和狀態(tài)1都是終態(tài)，但兩者面對(duì)字符a轉(zhuǎn)換的下一狀態(tài)是不一樣的：0a=0，1a=Φ（即“—”）；也即狀態(tài)0和狀態(tài)1不等價(jià)，故不可將圖2-21的DFA合并成圖2-19的DFA。因此，正規(guī)表達(dá)式a*b*根據(jù)表2.12最終得到的DFA如圖所示。

abb012.5詞法分析器的自動(dòng)生成1.此法分析程序的自動(dòng)生成原理2.5詞法分析器的自動(dòng)生成2.LEX源程序的組成：一個(gè)Lex源程序由用“%%”分隔的三部分組成輔助定義式%%識(shí)別規(guī)則%%用戶(hù)子程序

Lex有兩種使用方式：一種是將Lex作為一個(gè)單獨(dú)的工具，用以生成所需的識(shí)別程序；另一種是將Lex和語(yǔ)法分析器自動(dòng)生成工具（如YACC）結(jié)合起來(lái)使用，以生成一個(gè)編譯程序的掃描器和語(yǔ)法分析器。2.5詞法分析器的自動(dòng)生成LEX源程序片段AuxiliaryDefinitions /*輔助定義*/letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣zdigit→0∣1∣2∣3∣…∣9%%RecognitionRules /*識(shí)別規(guī)則*/1while {return?(?1,?null?)}2do {return?(?2,?null?)}3if {return(?3,?null?)}4else {return?(?4,?null?)}5switch {return?(?5,?,null?)}例2.5詞法分析器的自動(dòng)生成6{ {return?(?6,?null?)}7} {return?(?7,?null?)}8( {return?(?8,?null?)}9) {return?(?9,?null?)}10+ {return?(?10,?null?)}11? {return?(?11,?null?)}12* {return?(?12,?null?)}13/ {return?(13,?null?)}14= {return?(?14,?null?)}15； {return?(?15,?null?)}2.5詞法分析器的自動(dòng)生成16letter(letter∣digit)* {if(keyword(id)==0)

{return?(?16,?null?)；

return?(?id?)};

elsereturn?(?keyword(id)?)}17digit(digit)*{val=int(id)；

return?(?17,?null?)；

return?(?val?)}18(?letter∣digit∣{∣}∣(∣)∣+∣?∣*∣/∣=∣；)* {retu