第3章詞法分析與有窮自動(dòng)機(jī)

詞法分析程序功能

單詞符號(hào)及輸出單詞的形式

語(yǔ)言單詞符號(hào)的兩種定義方式

正規(guī)式與有窮自動(dòng)機(jī)

正規(guī)文法與有窮自動(dòng)機(jī)

詞法分析程序的編寫(xiě)方法1intfib(intn){if(n<=1)returnn;returnfib(n-1)+fib(n-2);}chara[100]="Enteraninteger:";intmain(){print_string(a);intmax=read_int();intn=1;do{print_int(fib(n++));print_string("\n");}while(n<=max);return0;}關(guān)鍵字

if，while,do標(biāo)識(shí)符

各種名字，如變量名、常量名、數(shù)組名、函數(shù)名等。常數(shù)整型常數(shù)125、實(shí)型常數(shù)0.718、布爾型常數(shù)TRUE等。運(yùn)算符＋、－、*、/、＜等。分界符，、；、（、）、：等。3.1詞法分析程序的功能語(yǔ)言的單詞符號(hào)是指語(yǔ)言中具有獨(dú)立意義的最小語(yǔ)法單位。23.1詞法分析程序的功能33.1詞法分析程序的功能4

字符串表示的源程序詞法分析器字符單詞符號(hào)取下一個(gè)單詞符號(hào)語(yǔ)法分析器輸入:if(a＞1)b=100；3.1詞法分析程序的功能53.2單詞符號(hào)及輸出單詞的形式詞法分析程序輸出單詞的形式詞法分析程序所輸出的單詞符號(hào)通常表示成如下的二元式：

（單詞種別，單詞自身的值）63.2單詞符號(hào)及輸出單詞的形式例子:if(a＞1)b=100；標(biāo)識(shí)符的種別編碼整數(shù)10；常數(shù)的種別編碼整數(shù)11；基本字if種別編碼2；賦值號(hào)的種別編碼17；大于號(hào)的種別編碼23；分號(hào)的種別編碼26；左括號(hào)的種別編碼29；右括號(hào)的種別編碼30；73.2單詞符號(hào)及輸出單詞的形式if(a＞1)b=100；（2,）基本字if（29,）左括號(hào)(（10,‘a(chǎn)’）標(biāo)識(shí)符a（23,）大于號(hào)＞（11,1）常數(shù)1（30，）右括號(hào))（10，‘b’）標(biāo)識(shí)符b（17，）賦值號(hào)=（11，100）常數(shù)100（26,）分號(hào)；8問(wèn)題：下面的內(nèi)容表達(dá)什么？\A(?:[a-z0-9!#$%&'*+/=?^_‘{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_‘{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])\z93.3單詞符號(hào)的兩種定義方式正規(guī)式例子：l(l|d)*對(duì)應(yīng)的正規(guī)文法：I→l|Il|Id或：I→l|lTT→l|d|lT|dT/quickstart.html

10設(shè)有字母表Σ={a1,a2,…,an}，在字母表Σ上的正規(guī)式和它所表示的正規(guī)集可用如下規(guī)則來(lái)定義：1.Φ是Σ上的正規(guī)式，它所表示的正規(guī)集是Φ，即空集{}。2.ε是Σ上的正規(guī)式，它所表示的正規(guī)集僅含一空符號(hào)串，即{ε}。3.ai是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集是由單個(gè)符號(hào)ai所組成，即{ai}。3.3.1正規(guī)式和正規(guī)集114.如果e1和e2

是∑上的正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(e1)和L(e2)，則：(1)e1|e2是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1|e2)=L(e1)∪L(e2)(2)e1e2也是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1e2)=L(e1)L(e2)(3)(e1)*也是∑上的一個(gè)正規(guī)式，它所表示的正規(guī)集為L(zhǎng)((e1)*)=(L(e1))*3.3.1正規(guī)式和正規(guī)集123.3.1正規(guī)式和正規(guī)集例1設(shè)有字母表Σ={a,b}，根據(jù)正規(guī)式與正規(guī)集的定義有：1.a和b是正規(guī)式，正規(guī)集為L(zhǎng)(a)={a},L(b)=2.a|b是正規(guī)式，正規(guī)集為L(zhǎng)(a|b)=L(a)∪L(b)={a,b}3.ab是正規(guī)式，正規(guī)集為L(zhǎng)(ab)=L(a)L(b)={a}={ab}133.3.1正規(guī)式和正規(guī)集4.(a|b)*是正規(guī)式，相應(yīng)正規(guī)集為L(zhǎng)((a|b)*)=(L(a|b))*

={a,b}*={ε,a,b,aa,ab,ba,bb,…}問(wèn)題：{a,b}*的子集{anbn|n≥1}是正規(guī)集嗎？143.3.1正規(guī)式和正規(guī)集5.ba*是正規(guī)式，正規(guī)集為L(zhǎng)(ba*)=L(b)L(a*)={b,ba,baa,baaa,…}6.(a|b)*(aa|bb)(a|b)*是正規(guī)式，正規(guī)集為L(zhǎng)((a|b)*(aa|bb)(a|b)*)=L((a|b)*)L(aa|bb)L((a|b)*)＝{a,b}*{aa,bb}{a,b}*153.3.1正規(guī)式和正規(guī)集例2設(shè)Σ={a,b,c},則aa*bb*cc*是∑上的一個(gè)正規(guī)式,它所表示的正規(guī)集：L={abc,aabc,abbc,abcc,aaabc,…}

={}16例3設(shè)程序語(yǔ)言字母表是鍵盤(pán)字符集合，則程序語(yǔ)言部分單詞符號(hào)可用如下正規(guī)式定義：關(guān)鍵字if|else|while|do標(biāo)識(shí)符l(l|d)*整常數(shù)dd*關(guān)系運(yùn)算符<

<=>

>=<>

3.3.1正規(guī)式和正規(guī)集173.3.1正規(guī)式和正規(guī)集標(biāo)識(shí)符正規(guī)式：ID=l(l|d)*

l代表a~z中任一字母

d代表0~9中任一數(shù)字標(biāo)識(shí)符正規(guī)文法：I→l|Il|Id183.3.1正規(guī)式和正規(guī)集例如(a|b)*(a*b*)*;b(ab)*(ba)*b如果正規(guī)式R1和R2描述的正規(guī)集相同,則我們稱正規(guī)式R1與R2等價(jià)。記為R1＝R2。193.3.1正規(guī)式和正規(guī)集正規(guī)式具有如下性質(zhì)：A、B、C均為正規(guī)式，則1．A|B=B|A ()2．A|(B|C)=(A|B)|C ()3．A(BC)=(AB)C ()4．A(B|C)=AB|AC ()5．(A|B)C=AC|BC ()6．Aε|εA=A7．A*=AA*|ε=A|A*=(A|ε)*8．(A*)*=A*203.3.2正規(guī)文法與正規(guī)式1.正規(guī)文法到正規(guī)式的轉(zhuǎn)換(1)將正規(guī)文法中的每個(gè)非終結(jié)符表示成關(guān)于它的一個(gè)正規(guī)式方程，獲得一個(gè)聯(lián)立方程組。(2)依照求解規(guī)則：若x=αx|β(或x=αx+β)則解為x=α*β若x=xα|β(或x=xα+β)則解為x=βα*213.3.2正規(guī)文法與正規(guī)式例1設(shè)有正規(guī)文法G，試給出該文法生成語(yǔ)言的正規(guī)式。Z0AA0A|0BB1A|ε分析首先給出相應(yīng)的正規(guī)式方程組(方程組中用“＋”代替正規(guī)式中的“|”)如下：Z=0A(1)A=0A+0B(2)B=1A+ε(3)22將(3)代入(2)中的B得A=0A+01A+0(4)對(duì)(4)利用分配律得A=(0+01)A+0(5)對(duì)(5)使用求解規(guī)則得A=(0+01)*0(6)將(6)代入(1)式中的A，得Z=0(0+01)*0即正規(guī)文法G[Z]所生成語(yǔ)言的正規(guī)式是R=0(0|01)*0Z=0A(1)A=0A+0B(2)B=1A+ε(3)3.3.2正規(guī)文法與正規(guī)式233.3.2正規(guī)文法與正規(guī)式例2設(shè)有正規(guī)文法G，試給出該文法生成語(yǔ)言的正規(guī)式。A

aB|bBB

aC|a|bC

aB分析首先給出相應(yīng)的正規(guī)式方程組(方程組中用“＋”代替正規(guī)式中的“|”)如下：A=aB+bB(1)B=aC+a+b(2)C=aB (3)24A=aB+bB(1)B=aC+a+b(2)C=aB (3)將(3)代入(2)中的C得B=aaB+a+b(4)對(duì)(4)使用求解規(guī)則得B=(aa)*(a+b)(5)(5)代入(1)中的B得A=(a+b)(aa)*(a+b)即正規(guī)文法G[A]所生成語(yǔ)言的正規(guī)式是R=(a|b)(aa)*(a|b)3.3.2正規(guī)文法與正規(guī)式253.3.2正規(guī)文法與正規(guī)式例3設(shè)有正規(guī)文法G：Z

U0|V1U

Z1|1V

Z0|0

相應(yīng)的正規(guī)式方程組為Z=U0+V1(1)U=Z1+1(2)V=Z0+0(3)263.3.2正規(guī)文法與正規(guī)式Z=U0+V1(1)U=Z1+1(2)V=Z0+0(3)(2)和(3)代入(1)得Z=Z10+10+Z01+01(4)對(duì)(4)使用求解規(guī)則得Z=(10+01)(10+01)*

即正規(guī)文法G[Z]所生成語(yǔ)言的正規(guī)式是？R=(10|01)(10|01)*

273.3.2正規(guī)文法與正規(guī)式例4已知描述“標(biāo)識(shí)符”單詞符號(hào)的正規(guī)文法為<標(biāo)識(shí)符>

l<標(biāo)識(shí)符>l<標(biāo)識(shí)符>d寫(xiě)出描述語(yǔ)言的正規(guī)式。根據(jù)前述求解規(guī)則,可知該文法所描述語(yǔ)言的正規(guī)式是

l(l|d)*282.正規(guī)式到正規(guī)文法的轉(zhuǎn)換(1)令VT=Σ。(2)對(duì)任何正規(guī)式R，選擇非終結(jié)符Z，生成規(guī)則Z

R，令S＝Z。(3)若a、b是正規(guī)式，對(duì)如A

ab的規(guī)則，轉(zhuǎn)換成AaB和Bb；(4)對(duì)已轉(zhuǎn)換的文法中,對(duì)如Aa*b的規(guī)則，轉(zhuǎn)換成AaA|b。(5)反復(fù)用(3)和(4)，直到每條規(guī)則最多含有一個(gè)終結(jié)符為止。3.3.2正規(guī)文法與正規(guī)式293.3.2正規(guī)文法與正規(guī)式例1將R=(a|b)(aa)*(a|b)轉(zhuǎn)換成相應(yīng)的正規(guī)文法令A(yù)是文法開(kāi)始符號(hào)，根據(jù)規(guī)則(2)變換為A

(a|b)(aa)*(a|b)根據(jù)規(guī)則(3)變換為A

(a|b)BB

(aa)*(a|b)303.3.2正規(guī)文法與正規(guī)式對(duì)B根據(jù)規(guī)則(4)變換為根據(jù)規(guī)則(3)變換為即前面例2中的文法。A

aB|bBB

aaB|a|bA

aB|bBB

aC|a|bC

aBAa*bAaA|b轉(zhuǎn)換成B

(aa)*(a|b)313.3.2正規(guī)文法與正規(guī)式例2將描述標(biāo)識(shí)符的正規(guī)式R=l(l|d)*

轉(zhuǎn)換成相應(yīng)的正規(guī)文法。令I(lǐng)為文法的開(kāi)始符號(hào)，根據(jù)規(guī)則(2)有根據(jù)規(guī)則(3)變換為根據(jù)規(guī)則(4)變換為

I

l(l|d)*

I

lT

T

(l|d)*

I

lT

T

(l|d)T|ε323.3.2正規(guī)文法與正規(guī)式進(jìn)一步變換為

I

lT

T

lT|dT|ε去掉ε規(guī)則

Il|lT

Tl|d|lT|dT即前面描述標(biāo)識(shí)符的右線性文法。333.4正規(guī)式與有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)是具有離散輸入與輸出系統(tǒng)的一種抽象數(shù)學(xué)模型有窮自動(dòng)機(jī)有“確定的”和“非確定的”兩類；確定的有窮自動(dòng)機(jī)和非確定的有窮自動(dòng)機(jī)都能準(zhǔn)確地識(shí)別正規(guī)集。343.4.1確定有窮自動(dòng)機(jī)確定有窮自動(dòng)機(jī)（DFA）M=(Q,Σ,f,S,Z)Q是一個(gè)有窮狀態(tài)集合，每一個(gè)元素稱為一個(gè)狀態(tài)。Σ是一個(gè)有窮輸入字母表，每個(gè)元素稱為一個(gè)輸入字符。f是一個(gè)從Q

Σ到Q的單值映射：S

Q，是唯一的一個(gè)初態(tài)。Z

Q，是一個(gè)終態(tài)集。35M=(Q,Σ,f,S,Z)f是一個(gè)從Q

Σ到Q的單值映射：f(qi,a)=qj(qi,qj

Q,aΣ)表示當(dāng)前狀態(tài)為qi，輸入字符為a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)換到下一個(gè)狀態(tài)qj,qj稱為qi的一個(gè)后繼狀態(tài)。3.4.1確定有窮自動(dòng)機(jī)S1S2S3S4abc36例設(shè)DFAM=({q0,q1,q2},{a,b},f,q0,{q2})其中f(q0,a)=q1f(q0,b)=q2f(q1,a)=q1f(q1,b)=q1f(q2,a)=q2f(q2,b)=q1狀態(tài)轉(zhuǎn)換矩陣狀態(tài)字符aq0

bq1

q2

q1

q1

q1

q2

q1

q2

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

f(q0,a)=q1f(q0,b)=q2f(q1,a)=q1f(q1,b)=q1f(q2,a)=q2f(q2,b)=q13.4.1確定有窮自動(dòng)機(jī)一個(gè)DFA也可以表示成一張狀態(tài)轉(zhuǎn)換圖。例DFAM=({q0,q1,q2},{a,b},f,q0,{q2})的狀態(tài)轉(zhuǎn)換圖如下圖所示。q0q1bbbaaaq2383.4.1確定有窮自動(dòng)機(jī)對(duì)Σ*中的任何符號(hào)串β，若存在一條從初態(tài)結(jié)到終態(tài)結(jié)的道路,在這條路上所有弧的標(biāo)記連結(jié)成的符號(hào)串等于β,則稱β為DFAM所識(shí)別(或接受)。M所識(shí)別的符號(hào)串的全體記為L(zhǎng)(M)，稱為DFAM所識(shí)別的語(yǔ)言。例中的DFAM所識(shí)別的語(yǔ)言為L(zhǎng)(M)=ba*。q0q1bbbaaaq2393.4.2非確定有窮自動(dòng)機(jī)非確定有窮自動(dòng)機(jī)（NFA）一個(gè)非確定有窮自動(dòng)機(jī)M是一個(gè)五元組M=(Q,Σ,f,S,Z)其中：Q,∑,Z意義同DFA，f和S不同于DFA。S1S2S3S4aaca40狀態(tài)轉(zhuǎn)換函數(shù)f不是單值函數(shù),它是一個(gè)多值函數(shù)： f(qi,a)={某些狀態(tài)的集合}

圖中：f(S1,a)={S1,

S2,S3}

非確定的有窮自動(dòng)機(jī)還允許 f(qi,ε)={某些狀態(tài)的集合}。(2)S

Q，是非空初態(tài)集。

3.4.2非確定有窮自動(dòng)機(jī)S1S2S3S4aaca41

設(shè)有NFAM=({1,2,3},{a,b},f,{1,3},{2})其中f(1,a)={3}f(1,b)={1,2}f(2,a)=Φf(2,b)={3}f(3,a)=Φf(3,b)={2}NFAM′

對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如下表所示。3.4.2非確定有窮自動(dòng)機(jī)狀態(tài)字符a1b{2}{3}Φ{3}{1,2}23Φ42設(shè)有NFAM=({1,2,3},{a,b},f,{1,3},{2})其中f(1,a)={3}f(1,b)={1,2}f(2,a)=Φf(2,b)={3}f(3,a)=Φf(3,b)={2}例中NFAM′

對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如下圖所示。3.4.2非確定有窮自動(dòng)機(jī)

b1abb23b43

例中NFAM'所識(shí)別的語(yǔ)言為L(zhǎng)(M')=b*(b|ab)(bb)*3.4.2非確定有窮自動(dòng)機(jī)b1abb23b44

由NFA的定義可知，同一個(gè)符號(hào)串β可由多條路來(lái)識(shí)別。例中NFAM',對(duì)符號(hào)串β=bbb可由3條路來(lái)識(shí)別。第一條路：狀態(tài)1

狀態(tài)2狀態(tài)3狀態(tài)2；

第二條路：狀態(tài)1狀態(tài)1狀態(tài)1

狀態(tài)2；第三條路：狀態(tài)3狀態(tài)2狀態(tài)3狀態(tài)2；3.4.2非確定有窮自動(dòng)機(jī)b1abb23b453.4.2非確定有窮自動(dòng)機(jī)提問(wèn)：DFA是NFA的特例？NFA是否比DFA描述能力更強(qiáng)呢？對(duì)于每個(gè)NFAM是否存在DFAM’,使L(M)=L(M’)？463.4.2非確定有窮自動(dòng)機(jī)對(duì)于每個(gè)NFAM存在DFAM’,使L(M)=L(M’)。利用有窮自動(dòng)機(jī)構(gòu)造詞法分析程序的方法是:從語(yǔ)言單詞的描述中構(gòu)造出非確定的有窮自動(dòng)機(jī)，再將非確定的有窮自動(dòng)機(jī)轉(zhuǎn)化為確定的有窮自動(dòng)機(jī)，并將其化簡(jiǎn)為狀態(tài)最少化的DFA,然后對(duì)DFA的每一個(gè)狀態(tài)構(gòu)造一小段程序?qū)⑵滢D(zhuǎn)化為識(shí)別語(yǔ)言單詞的詞法分析程序。47輸入：字母表Σ上的正規(guī)式R輸出：識(shí)別(接受)語(yǔ)言L(R)的NFAN方法：1.引進(jìn)初始結(jié)點(diǎn)X和終止結(jié)點(diǎn)Y2.分析R的語(yǔ)法結(jié)構(gòu)，用如下規(guī)則對(duì)R中的每個(gè)基本符號(hào)構(gòu)造NFA。3.4.3由正規(guī)式R構(gòu)造NFAXYR48(1)R=Φ,構(gòu)造NFA如圖所示。(2)R=ε,構(gòu)造NFA如圖所示。(3)R=a(aΣ),構(gòu)造NFA如圖所示。3.4.3由正規(guī)式R構(gòu)造NFA49對(duì)于代換為對(duì)于代換為對(duì)于代換為3.4.3由正規(guī)式R構(gòu)造NFA(4)若R是復(fù)合正規(guī)式，則按下圖的轉(zhuǎn)換規(guī)則對(duì)R進(jìn)行分裂和加進(jìn)新結(jié)點(diǎn),直至每個(gè)邊上留下一個(gè)符號(hào)或ε為止。503.4.3由正規(guī)式R構(gòu)造NFA3.整個(gè)分裂過(guò)程中,所有新結(jié)點(diǎn)均采用不同的名字，保留X，Y為全圖唯一初態(tài)結(jié)和終態(tài)結(jié)。51例1試構(gòu)造識(shí)別語(yǔ)言R=(a|b)*abb的NFAN,使L(N)=L(R)。

首先將R表示成如下拓廣轉(zhuǎn)換圖(a|b)*abbXY從左到右分裂RX12Y(a|b)*3bbaX12Yε3bba0εba3.4.3由正規(guī)式R構(gòu)造NFA52例2試構(gòu)造識(shí)別標(biāo)識(shí)符的NFA，描述正規(guī)式R=l(l|d)*

首先將R表示成如下拓廣轉(zhuǎn)換圖從左到右分裂R3.4.3由正規(guī)式R構(gòu)造NFA53例3試構(gòu)造正規(guī)式R=0(l*)*|01的NFA。

首先將R表示成如下拓廣轉(zhuǎn)換圖從左到右分裂R∵(l*)*=1*∴R=01*|01=0(1*|1)

=01*3.4.3由正規(guī)式R構(gòu)造NFA54對(duì)于一個(gè)NFA，由于狀態(tài)轉(zhuǎn)換函數(shù)f是一個(gè)多值函數(shù)f(q,a)={q1,

q2,q3…,qn}該集合是NFA狀態(tài)集合中的一個(gè)子集，為了將NFA轉(zhuǎn)換為DFA，把狀態(tài)集合{q1,

q2,q3…,qn}看作一個(gè)狀態(tài)A。3.4.4NFA確定化為DFA的方法55輸入：一個(gè)NFAN

輸出：一個(gè)接受（識(shí)別）相同語(yǔ)言的DFAM

狀態(tài)集合I的ε-閉包（ε-closure(I)）。設(shè)I是NFAN的一個(gè)狀態(tài)子集，ε-closure(I)定義如下：(1)如果s∈I，那么s∈ε-closure(I)(2)如果s∈I，從s出發(fā)經(jīng)過(guò)任意條ε弧到達(dá)s'，那么s’∈ε-closure(I)

3.4.4NFA確定化為DFA的方法56通過(guò)下圖理解狀態(tài)集合I的ε-閉包。ε-closure({0})={0,1,2,3}εεε0123456789εεεεbb3.4.4NFA確定化為DFA的方法57若令A(yù)={0,1,2,3},則J=f(A,b)=f(0,b)∪f(wàn)(1,b)∪f(wàn)(2,b)∪f(wàn)(3,b)={4,7}令B=ε–closure({4,7})={4,5,6,7,8,9}定義B是DFA在狀態(tài)A下遇到輸入符號(hào)b后轉(zhuǎn)移到的狀態(tài)。0123456789εεεεεεεbb3.4.4NFA確定化為DFA的方法583.4.4NFA確定化為DFA的方法2.從NFAN構(gòu)造DFAM的算法輸入:

NFAN=(Q,∑,f,x,{y})輸出:

DFAM=(Q',∑,f',初態(tài),終態(tài)集)開(kāi)始：令Q'={}59

3.4.4NFA確定化為DFA的方法計(jì)算DFAM的初態(tài)ε–CLOSURE({x}),并置為無(wú)標(biāo)記送入Q';

while(Q'中存在一個(gè)無(wú)標(biāo)記的狀態(tài)T={s1,s2,s3,…,sn})

{標(biāo)記T;for(每個(gè)輸入符號(hào)a)/*求解f'(T,a)=U*/{J=f({s1,s2,s3,…,sn},a)=f(s1,a)∪f(wàn)(s2,a)∪…∪f(wàn)(sn,a);U=ε–CLOSURE(J);if(U不在Q'中&&U不為空)置U為無(wú)標(biāo)記并送入Q’;if(U不為空)置M[T,a]=U;if(U中至少有一個(gè)是N的終態(tài))U為M的終態(tài);

}}60例1將下圖所示的NFAN確定化。

其等價(jià)DFA的開(kāi)始狀態(tài)為:A=ε–CLOSURE({X})={X,0,1}A作為未標(biāo)記的狀態(tài),添加到Q'中。

b{X,0,1}{0,1,Y}{0,1,3}{0,1}{0,1,2}a{0,1,2}{0,1,2}{0,1}{0,1,2}{0,1}{0,1,Y}{0,1}EDCBAQ′{0,1,3}{0,1,2}{0,1,2}3.4.4NFA確定化為DFA的方法61ABCDEaaaaabbbbbb{X,0,1}{0,1,Y}{0,1,3}{0,1}{0,1,2}a{0,1,2}{0,1,2}{0,1}{0,1,2}{0,1}{0,1,Y}{0,1}EDCBAQ′{0,1,3}{0,1,2}{0,1,2}3.4.4NFA確定化為DFA的方法62

首先確定其初態(tài)

,命名為0狀態(tài)

Q′dl{X}{1,2,Y}Φ{1,2,Y}{2,Y}{2,Y}{2,Y}{2,Y}{2,Y}021ε–CLOSURE({X})={X}3.4.4NFA確定化為DFA的方法例2將NFAN確定化。63例3將NFAN確定化。首先確定其初態(tài)

,命名為0狀態(tài)

0=ε–CLOSURE({X})={X}Q′10{X}{1,2,Y}Φ{1,2,Y}{2,Y}{2,Y}{2,Y}021ΦΦ3.4.4NFA確定化為DFA的方法643.4.5DFA的化簡(jiǎn)1.DFA的化簡(jiǎn)DFAM的化簡(jiǎn)：尋找一個(gè)狀態(tài)數(shù)比M少的DFAM'

，使得L(M)=L(M')?；?jiǎn)了的DFA滿足兩個(gè)條件:(1)沒(méi)有多余狀態(tài)；(2)它的狀態(tài)集中沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)的。653.4.5DFA的化簡(jiǎn)2.多余狀態(tài)有窮自動(dòng)機(jī)的多余狀態(tài)：從該自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的狀態(tài)。663.4.5DFA的化簡(jiǎn)3.等價(jià)狀態(tài)設(shè)DFAM＝(Q,Σ,f,S0,F),s,t∈

Q，若對(duì)任何

*,f(s,

)∈F

當(dāng)且僅當(dāng)f(t,

)∈F，則稱狀態(tài)s和t是等價(jià)的。如果s和t不等價(jià),則稱s和t是可區(qū)別的。例如：終態(tài)與非終態(tài)是可區(qū)別的。因?yàn)榻K態(tài)有一條到達(dá)自身的ε道路，而非終態(tài)沒(méi)有到達(dá)終態(tài)的ε道路。673.4.5DFA的化簡(jiǎn)4.兩個(gè)狀態(tài)等價(jià)的條件:一致性條件:狀態(tài)s和t必須同為終態(tài)或非終態(tài)。蔓延性條件:對(duì)所有輸入符a,

s和t必須轉(zhuǎn)到等價(jià)的狀態(tài)。5.化簡(jiǎn)方法

輸入：一個(gè)DFAM。輸出：接受與M相同語(yǔ)言的DFAM'，且其狀態(tài)數(shù)最少。683.4.5DFA的化簡(jiǎn)化簡(jiǎn)方法:將M的狀態(tài)集Q分劃成一些不相交的子集，使得每個(gè)子集中任何兩個(gè)狀態(tài)是等價(jià)的，而任何兩個(gè)屬于不同子集的狀態(tài)都是可區(qū)別的。然后在每個(gè)子集中任取一個(gè)狀態(tài)作“代表”,而刪去子集中其余狀態(tài),并把射向其余狀態(tài)的箭弧都改作射向作“代表”的狀態(tài)中。693.4.5DFA的化簡(jiǎn)下面給出化簡(jiǎn)算法的具體執(zhí)行步驟:1.將DFAM的狀態(tài)集Q分成兩個(gè)子集：終態(tài)集F和非終態(tài)集Q-F，形成初始分劃∏。2.對(duì)∏使用如下方法建立新分劃∏NEW：對(duì)∏的每個(gè)狀態(tài)子集G:

(1)把G分劃成新的子集，使得G的兩個(gè)狀態(tài)s和t屬于同一子集，當(dāng)且僅當(dāng)對(duì)任何輸入符號(hào)a，狀態(tài)s和t轉(zhuǎn)換到的狀態(tài)都屬于∏的同一子集。703.4.5DFA的化簡(jiǎn)用G分劃出的所有新子集替換G,形成新的分劃∏NEW；如果∏NEW＝∏，則執(zhí)行第4步；否則令∏＝∏NEW，重復(fù)第2步。分劃結(jié)束后，對(duì)分劃中的每個(gè)狀態(tài)子集，選出一個(gè)狀態(tài)作代表，而刪去其它一切等價(jià)的狀態(tài)，并把射向其它狀態(tài)的箭弧改為射向這個(gè)作為代表的狀態(tài)。71ABCDEaaaaabbbbbEDBAaaaabbbb例1.將DFA最小化初始分劃∏=({A,B,C,D}{E}){A,B,C,D}a={B}{A,B,C,D}b={C,D,E}∏=({A,B,C}{D}{E}){A,B,C}a={B}{A,B,C}b={C,D}∏=({A,C}{B}{D}{E})

{A,C}a={B}{A,C}b={C}

∏=({A,C}{B}{D}{E})

3.4.5DFA的化簡(jiǎn)7202llldd1d01ll3.4.5DFA的化簡(jiǎn)例2.將右面的DFAM最小化分析由圖可知，給定的DFA無(wú)多余狀態(tài)。初始分劃∏=({1,2}{0}){1,2}l={2}{1,2}d={2}∏=({1,2}{0})

733.4.6有窮自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換1.在M的轉(zhuǎn)換圖上添加兩個(gè)結(jié)點(diǎn)：結(jié)點(diǎn)X、Y。從X用ε連線連結(jié)到M的所有初態(tài)結(jié)點(diǎn)；從M的所有終態(tài)結(jié)點(diǎn)用ε連線連結(jié)到Y(jié)結(jié)。構(gòu)成新的非確定有窮自動(dòng)機(jī)M’，只有一個(gè)初態(tài)X和一個(gè)終態(tài)Y。顯然，L(M)=L(M’)。即這兩個(gè)NFA是等價(jià)的。743.4.6有窮自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換2.逐步消去M’中的其它結(jié)點(diǎn)，直至只剩下X，Y結(jié)點(diǎn)。在消除結(jié)點(diǎn)過(guò)程中，逐步用正規(guī)式來(lái)標(biāo)記相應(yīng)的箭弧。反復(fù)使用以下替換規(guī)則:

753.4.6有窮自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換對(duì)于代換為ABr1r2ACBr1r2對(duì)于ABr1|r2代換為代換為ABr1r2*r3ABr1r2對(duì)于ACBr1r3r2763.4.6有窮自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換例1.設(shè)窮自動(dòng)機(jī)的狀態(tài)圖如圖所示。求識(shí)別語(yǔ)言的正規(guī)式。R=(10|01)(10|01)*

773.5正規(guī)文法與有窮自動(dòng)機(jī)右線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換方法

設(shè)給定了一個(gè)右線性正規(guī)文法G=(VN,VT,P,S)則相應(yīng)的有窮自窮自動(dòng)機(jī)M=(Q,Σ,f,q0,Z)1.令Q=VN∪{D}(DVN)Z={D}Σ=VTq0=S2.對(duì)G中每一形如A→aB(A,B∈VN,a∈VT∪{ε})的產(chǎn)生式,令f(A,a)=B∈/a=ε,A→B令f(A,ε)=B

A→aBA→a783.5.1右線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換方法3.對(duì)G中每一形如A→a(A∈VN,a∈VT)的產(chǎn)生式,令f(A,a)=D4.對(duì)G中每一形如A→ε(A∈VN)的產(chǎn)生式,令A(yù)為接受狀態(tài)或令f(A,ε)=D79BAZ0010(a)AZ0010(b)DBε例1構(gòu)造下述文法G[Z]的有窮自動(dòng)機(jī)。Z→0AA→0A|0BB→1A|ε其狀態(tài)圖如圖(a)或(b)所示。顯然,自動(dòng)機(jī)M是非確定的。它識(shí)別的語(yǔ)言就是文法G[Z]所描述的語(yǔ)言即L(G[Z])=L(M)=0(0|01)*0。3.5.1右線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換方法803.5.2左線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換方法設(shè)給定了一個(gè)左線性正規(guī)文法G=(VN,VT,P,S)則相應(yīng)的有窮自窮自動(dòng)機(jī)M=(Q,Σ,f,q0,Z)1.令Q=VN∪{q0}(q0

VN)Z={S}Σ=VT

2.對(duì)G中每一形如A→Ba(A,B∈VN,a∈VT∪{ε}的產(chǎn)生式,令f(B,a)=A∈/a=ε,A→B令f(B,ε)=AA→BaA→a813.5.2左線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換方法3.對(duì)G中每一形如A→a

(A∈VN,a∈VT∪{ε})的產(chǎn)生式,令f(q0,a)=A82ABS01013.5.2左線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換方法例1.構(gòu)造下述文法G[A]的自動(dòng)機(jī)。A→A1|B1B→B0|0其狀態(tài)圖如下圖所示。顯然,該自動(dòng)機(jī)是確定的。它識(shí)別的語(yǔ)言就是文法G[A]所描述的語(yǔ)言。即L(G[A])=L(M)=00*11*

83

3.5.3有窮自動(dòng)機(jī)到正規(guī)文法的轉(zhuǎn)換843.5.3有窮自動(dòng)機(jī)到正規(guī)文法的轉(zhuǎn)換例1設(shè)有窮自動(dòng)機(jī)M=({S,A},{a,b,0,1},f,S,{A})f(S,a)=Af(S,b)=Af(A,a)=Af(A,b)=Af(A,0)=Af(A,1)=AM的狀態(tài)轉(zhuǎn)換圖如圖所示。根據(jù)上述轉(zhuǎn)換規(guī)則,與M等價(jià)的正規(guī)文法G為:G=({S,A},{a,b,0,1},P,S)其中P為：S→aA|bAA→aA|bA|0A|1A|ε或S→aA|bA|a|bA→aA|bA|0A|1A|a|b|0|1自動(dòng)機(jī)M所識(shí)別的語(yǔ)言L(M)=L(G)=(a|b)(0|1|a|b)*。

85例2設(shè)DFAM=({A,B,C,D},{0,1},δ,A,{B})δ(A,0)=Bδ(A,1)=Dδ(B,0)=Dδ(B,1)=Cδ(C,0)=Bδ(C,1)=Dδ(D,0)=Dδ(D,1)=D構(gòu)造一個(gè)右線性文法G,使得L(G)=L(M)。該自動(dòng)機(jī)相應(yīng)的狀態(tài)轉(zhuǎn)換圖如下圖所示。BCA001D0110,13.5.3有窮自動(dòng)機(jī)到正規(guī)文法的轉(zhuǎn)換863.5.3有窮自動(dòng)機(jī)到正規(guī)文法的轉(zhuǎn)換從狀態(tài)轉(zhuǎn)換圖可以看出,狀態(tài)D是多余的,可去掉,得到與M等價(jià)的DFAM’的狀態(tài)轉(zhuǎn)換圖，如圖所示。BCA001BCA001D0110,1873.5.3有窮自動(dòng)機(jī)到正規(guī)文法的轉(zhuǎn)換根據(jù)轉(zhuǎn)換規(guī)則所求右線性文法為G=({A,B,C},{0,1},P,A)其中P為或該自動(dòng)機(jī)所識(shí)別的語(yǔ)言為0(10)*。A→0B|0B→1CC→0B|0A→0BB→1C|ε

C→0BBCA001883.6詞法分析程序的編寫(xiě)方法構(gòu)造詞法分析程序的方法:第一種方法手工方式：根據(jù)識(shí)別語(yǔ)言單詞的狀態(tài)轉(zhuǎn)換圖，使用某種高級(jí)語(yǔ)言，例如C語(yǔ)言，直接編寫(xiě)詞法分析程序。第二種方法是自動(dòng)生成：利用工具Flex，自動(dòng)生成詞法分析程序。以某種簡(jiǎn)單語(yǔ)言為例，對(duì)第一種方法作簡(jiǎn)要的介紹。89例如，列出了某個(gè)簡(jiǎn)單語(yǔ)言的所有單詞符號(hào)，以及它們的種別編碼和單詞值。3.6詞法分析程序的編寫(xiě)方法單詞符號(hào)種別編碼單詞值1234567101113141516171819212223內(nèi)部字符串二進(jìn)制數(shù)值表示beginendifthenelsewhiledo標(biāo)識(shí)符整常數(shù)+-*/<=<><::=;90右圖是識(shí)別前表單詞的狀態(tài)轉(zhuǎn)換圖。狀態(tài)0為初態(tài),帶雙圈均為終態(tài);狀態(tài)17是識(shí)別不出單詞符號(hào)的出錯(cuò)情況；l代表任一字母，d代表任一數(shù)字；根據(jù)轉(zhuǎn)換圖，用C語(yǔ)言編寫(xiě)出識(shí)別所有單詞的詞法分析程序。3.6詞法分析程序的編寫(xiě)方法913.6詞法分析程序的編寫(xiě)方法規(guī)定所有關(guān)鍵字,用戶不得使用它們作為自己定義的標(biāo)識(shí)符。關(guān)鍵字作為特殊的標(biāo)識(shí)符來(lái)處理，需預(yù)先安排在一個(gè)表格中（關(guān)鍵字表）。當(dāng)識(shí)別出一個(gè)標(biāo)識(shí)符時(shí)，再去查關(guān)鍵字表，確定是否是一個(gè)關(guān)鍵字。其次規(guī)定，若關(guān)鍵字、標(biāo)識(shí)符和常數(shù)之間沒(méi)有確定的運(yùn)算符或界符作間隔，則必須至少用一個(gè)空白符作間隔。923.6詞法分析程序的編寫(xiě)方法根據(jù)狀態(tài)轉(zhuǎn)換圖構(gòu)造出詞法分析程序：讓每個(gè)狀態(tài)對(duì)應(yīng)一小段程序。全局變量、函數(shù)如下：1.ch字符變量，存放當(dāng)前讀進(jìn)的源程序字符。2.token字符數(shù)組,存放構(gòu)成單詞符號(hào)的字符串。3.getch()函數(shù)，從輸入緩沖區(qū)中讀進(jìn)源程序的下一個(gè)字符放在ch中，并把讀字符指針指向下一個(gè)字符。4.getbc()函數(shù)，檢查ch中的字符是否為空白字符，若是空白字符，則反復(fù)調(diào)用getbc()，直至ch中進(jìn)入一個(gè)非空白字符為止。935.concat()函數(shù)：把當(dāng)前ch中的字符與token中的字符串聯(lián)接。例如，token中原值為“ab”,ch為“c”,調(diào)用concat()，token值變?yōu)椤癮bc”。

6.letter(ch)和degit(ch)函數(shù)：判定ch中的字符是否為字母或數(shù)字，給出true或false。7.reserve()函數(shù)：對(duì)token中的字符串查關(guān)鍵字表，若是關(guān)鍵字,則回送編碼，否則，回送標(biāo)識(shí)符的種別碼10。3.6詞法分析程序的編寫(xiě)方法948.retract()函數(shù)：讀字符指針回退一個(gè)字符。9.return()函數(shù)：收集并攜帶必要的信息返回調(diào)用程序，即返回語(yǔ)法分析程序。10.dtb()：將token中的數(shù)字串轉(zhuǎn)換成二進(jìn)制數(shù)值表示,并以此作為函數(shù)值返回。根據(jù)該語(yǔ)言的狀態(tài)轉(zhuǎn)換圖，用C語(yǔ)言編寫(xiě)出詞法分析程序：3.6詞法分析程序的編寫(xiě)方法953.6詞法分析程序的編寫(xiě)方法Scaner(){token=NULL;getch();getbc();//狀態(tài)轉(zhuǎn)換圖用C語(yǔ)言編寫(xiě)出詞法分析程序如下:if(letter(ch)){while(letter(ch)||digit(ch)){concat();getch();}retract();c=reserve();if(c!=10)return(c,token);elsereturn(10,token);}96elseif(digit(ch)){while(digit(ch)){concat();getch();}retract();return(11,dtb());}3.6詞法分析程序的編寫(xiě)方法973.6詞法分析程序的編寫(xiě)方法elseswitch(ch){case’+’:return(13,―);break;case’-’:return(14,―);break;case’*’:return(15,―);break;case’/’:return(16,―);break;case’<’:getch();if(ch==`=′)return(17,―);elseif(ch==`>′)return(18,―);retract();return(19,―);break;case’:’:getch();if(ch==’=’)return(22,―);retract();return(21,―);break;case’;’:return(23,―);break;default:error();break;}}98由此可知,只要構(gòu)造出識(shí)別語(yǔ)言單詞符號(hào)的有窮自動(dòng)機(jī),就很容易構(gòu)造出識(shí)別語(yǔ)言單詞符號(hào)的詞法分析程序。3.6詞法分析程序的編寫(xiě)方法99本章小結(jié)本章重點(diǎn)介紹了詞法分析程序的設(shè)計(jì)思想和構(gòu)造方法。主要內(nèi)容有： 1．詞法分析程序的功能是從左到右掃描源程序字符串，根據(jù)語(yǔ)言的詞法規(guī)則識(shí)別出各類單詞符號(hào)。 輸出單詞符號(hào)的形式是二元組:（單詞種別，單詞自身值）100本章小結(jié)2．程序語(yǔ)言單詞符號(hào)的兩種定義方式例如定義“標(biāo)識(shí)符”單詞的正規(guī)式是l(l|d)*

正規(guī)文法是＜標(biāo)識(shí)符＞→l|＜標(biāo)識(shí)符＞l|＜標(biāo)識(shí)符＞d正規(guī)文法正規(guī)式101本章小結(jié)3．有窮自動(dòng)機(jī)有確定的和非確定兩大類：DFAM=(Q,Σ,f,S,Z)其中是f單值映射函數(shù)，S是唯一初態(tài)NFAN=(Q,Σ,f,S,Z)其中f是多值映射函數(shù)，S為非空初態(tài)集。有窮自動(dòng)機(jī)通常表示為狀態(tài)轉(zhuǎn)換圖，它是有窮自動(dòng)機(jī)的非形式化描述。

102本章小結(jié)從單詞兩種定義方式中構(gòu)造詞法分析程序的過(guò)程是：正規(guī)式正規(guī)文法NFA分裂法轉(zhuǎn)換規(guī)則子集法D