《編譯原理》課件第2章

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

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

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

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

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

2.1

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

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

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

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

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

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

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

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

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

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

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

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

注意：2.1

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

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

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

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

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

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

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

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

對于不含回路的分支狀態(tài)來說，可以讓它對應(yīng)一個switch(?)

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

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

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

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

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

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

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

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

(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中的前五項(即判別其是否為保留字)，若是保留字則返回它的編碼，否則返回0值。

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

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

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

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

s=getchar();

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

switch(s)

{

case'a':

case'b':

…

case'z':

while(letter()‖digit())

{

concatenation();

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

getchar();

}

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

c=reserve();

if(c==0)

{

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

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

}

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ī)表達式與有限自動機簡介

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

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

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

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

a,

b,

aa,

ab,

ba,

bb,

aaa,

…}2.3正規(guī)表達式與有限自動機簡介“∣”表示或“?”表示連接（通常可省略）“?*?”表示閉包，使用括號可以改變運算的次序

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

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

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

對于Σ上的正規(guī)式R和S，如果它所表示的正規(guī)集L(R)?=L(S)，則稱R和S等價并記為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ī)表達式與有限自動機簡介2.有限自動機

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

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

S，是一個終態(tài)集。Md=?(S,?Σ,?f,?s0,?Z)2.3正規(guī)表達式與有限自動機簡介f(si,

a)

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

a)

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

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

f(s1,?a)?=s2

f(s1,?b)?=s3

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

注意：2.3正規(guī)表達式與有限自動機簡介一個非確定有限自動機Mn（記為NFAMn）是一個五元組非確定有限自動機（NFA）Mn=

(S,?Σ,

f,

Q,

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

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

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

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

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

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

a)?的值。2.3正規(guī)表達式與有限自動機簡介假定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ī)表達式與有限自動機簡介

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

=L(M')，則稱有限自動機M和M'等價。此外，對于任一給定的NFAM，一定存在一個DFAM'，使L(M)

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

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

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

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

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

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

Ia=ε_CLOSURE(J)

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

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

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

[解答]

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

{5,

3,

4}

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

{5,

6,

2,

3,

8,

4,

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

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

=L(M’)?；喠说腄FAM‘滿足下述兩個條件：（1）沒有多余狀態(tài)；（2）在其狀態(tài)集中，沒有兩個相互等價的狀態(tài)存在。

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

s2,

…,

sk}，若存在一個輸入字符a（a∈Σ）使得Ia(i)不全包含在當(dāng)前劃分的某一子集I(j)中（即跨越到兩個子集），就將I(i)一分為二（3）重復(fù)步驟（2），直到子集個數(shù)不再增加為止（即每個子集已是不可再分的了）。所謂不能劃分，是指該子集或者僅有一個狀態(tài)，或者雖有多個狀態(tài)但這些狀態(tài)均不可區(qū)分（即等價）。DFAM的化簡方法如下：2.4正規(guī)表達式到有限自動機的構(gòu)造化簡由例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}，它們分屬于兩個不同的狀態(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)集，故不進行劃分。（5）考察{3,?4,?5,?6}b：3b=6b={5}{3,?4,?5,?6}；4b=5b={4}{3,?4,?5,?6}，即都屬于終態(tài)集，故不進行劃分。（6）按順序重新命名狀態(tài)子集{0}、{1}、{2}、{3,

4,

5,

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

化簡后的DFAM''

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

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

(

a∣b

)*與

(

a*b*

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

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

例2.4正規(guī)表達式到有限自動機的構(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ī)表達式到有限自動機的構(gòu)造

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

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

a*b*

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

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

用子集法將圖2-20所示的NFA確定化得到第一個表所列的轉(zhuǎn)換表，重新命名得到第二個表所列的狀態(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由于兩個狀態(tài)轉(zhuǎn)換矩陣相同，故?(

a∣b

)*和

(

a*b*

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

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

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

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

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

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

Lex有兩種使用方式：一種是將Lex作為一個單獨的工具，用以生成所需的識別程序；另一種是將Lex和語法分析器自動生成工具（如YACC）結(jié)合起來使用，以生成一個編譯程序的掃描器和語法分析器。2.5詞法分析器的自動生成LEX源程序片段AuxiliaryDefinitions /*輔助定義*/letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣zdigit→0∣1∣2∣3∣…∣9%%RecognitionRules /*識別規(guī)則*/1while {return?(?1,?null?)}2do {return?(?2,?null?)}3if {return(?3,?null?)}4else {return?(?4,?null?)}5switch {return?(?5,?,null?)}例2.5詞法分析器的自動生成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詞法分析器的自動生成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