編譯原理第2章-詞法分析課件3

-1-第2章詞法分析2.1詞法分析程序的功能2.2正則表達(dá)式2.3有限自動機(jī)2.4詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)√√-2-2.3有限自動機(jī)

有限自動機(jī)

確定有限自動機(jī)DFA的定義

非確定有限自動機(jī)NFA的定義NFA到DFA的轉(zhuǎn)換DFA的化簡-3-2.3有限自動機(jī)有限狀態(tài)自動機(jī)(FiniteStateAutomata,FSA)或有限狀態(tài)機(jī)(FiniteStateMachine,FSM):工作過程：在初始狀態(tài)下，讀頭指向輸入帶的最左單元，準(zhǔn)備讀入第一個(gè)字符，每讀入一個(gè)字符，從當(dāng)前狀態(tài)進(jìn)入下一狀態(tài)；當(dāng)讀頭讀入所有字符后，若狀態(tài)進(jìn)入終態(tài)，則輸入帶上的輸入串被接受，否則，輸入串有錯(cuò)。abcde…有限狀態(tài)控制器讀頭輸入帶

初態(tài)，

中間態(tài)，終態(tài)-4-2.3有限自動機(jī)有限自動機(jī)可以分為：確定性有限自動機(jī)(DeterministicFiniteAutomata,DFA)非確定性有限自動機(jī)兩種(NondeterministicFiniteAutomata,NFA)確定有限自動機(jī)DFA為一個(gè)五元組(S,,f,s0,Z)，其中：S={s0，s1，s2，…}是一個(gè)有限狀態(tài)集合，它的每個(gè)元素稱為一個(gè)狀態(tài)；是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符；f是在SS{}上的轉(zhuǎn)換函數(shù)，是單值全映射；s0

S是唯一的一個(gè)初始狀態(tài)；ZS，是一個(gè)終止?fàn)顟B(tài)集，可為空。-5-2.3有限自動機(jī)例：DFAM=({0,1,2,3,4},{a,b},f,{0},{3})其中f為：

f(0,a)=1f(0,b)=4f(1,a)=4f(1,b)=2f(2,a)=3f(2,b)=4f(3,a)=3f(3,b)=3f(4,a)=4f(4,b)=4-6-2.3有限自動機(jī)有限自動機(jī)的兩種表示形式：轉(zhuǎn)換表轉(zhuǎn)換圖ab0141422343*334440213abababba4ab-7-2.3有限自動機(jī)去除陷阱狀態(tài)：轉(zhuǎn)換表轉(zhuǎn)換圖ab0112233*330213aabba-8-2.3有限自動機(jī)DFA的例子：轉(zhuǎn)換表轉(zhuǎn)換圖abcdS0S1S2S*S1S1S2S2S*S*S*:{a,b,c,d},S:{S0,S1,S2,S*}開始狀態(tài):S0，終止?fàn)顟B(tài)集:{S*}f:{(S0,a)S1,(S0,c)S2,(S0,d)S*,(S1,b)S1,(S1,d)S2,(S2,a)S*,(S*,c)S*}S0S2S1S*acdacdb-9-2.3有限自動機(jī)DFA接受的字符串：如果M是一個(gè)DFA,a1

a2…

an

是一個(gè)字符串，如果存在一個(gè)狀態(tài)序列(S0,S1,…,Sn),滿足

S0S1,S1S2,……,Sn-1Sn其中S0

是開始狀態(tài)，Sn

是接受狀態(tài)之一，則串a(chǎn)1

a2…

an

被DFAM接受.DFA接受的語言：DFAM接受的所有串的集合，稱為M定義語言，記為L(M)a1a2an-10-2.3有限自動機(jī)例1：該自動機(jī)接受的語言是L={aba,abaa,abab,abaab,abaaab,abaabb,……}等價(jià)于正則表達(dá)式aba(a|b)*定義的語言0213aabba-11-2.3有限自動機(jī)例2：該自動機(jī)接受的語言等價(jià)于正則表達(dá)式(ab*da|ca|d)c*定義的語言S0aS1S2S3cddabc-12-2.3有限自動機(jī)例3:若DFAM只有一個(gè)狀態(tài)，既是開始狀態(tài)又是終止?fàn)顟B(tài)，則DFAM定義的串集是L()={}例4:若若DFAM只有一個(gè)狀態(tài)，并且是開始狀態(tài)或DFAM有若干個(gè)狀態(tài)，但開始狀態(tài)到終止?fàn)顟B(tài)之間沒有通路，則DFAM定義的串集是空集SS0或S0SS’S’’-13-2.3有限自動機(jī)例5:={a,b},構(gòu)造自動機(jī)識別由所有奇數(shù)個(gè)a和奇數(shù)個(gè)b組成的字符串。S奇a,奇bS奇a,偶bS偶a,奇bS偶a,偶bbbbaabaa不需要記住所看到的整個(gè)字符串，只需記住至當(dāng)前狀態(tài)所看到的a和b的個(gè)數(shù)是奇數(shù)還是偶數(shù)-14-2.3有限自動機(jī)例6:設(shè)計(jì)有限自動機(jī)M，識別{0,1}上的語言

L={x000y|x,y{0|1}*}分析：該語言的特點(diǎn)是每個(gè)串都包含連續(xù)3個(gè)0的子串。自動機(jī)的任務(wù)就是識別/檢查000的子串。q0q1q2q300011101-15-2.3有限自動機(jī)例7:設(shè)計(jì)有限自動機(jī)M，識別{0,1,2}上的語言，每個(gè)字符串代表的數(shù)字能整除3。分析:(1)一個(gè)十進(jìn)制數(shù)除以3，余數(shù)只能是0,1,2；(2)被3整除的十進(jìn)制數(shù)的特點(diǎn)：十進(jìn)制數(shù)的所有位數(shù)字的和能整除3。q0q1q2110210022-16-2.3有限自動機(jī)例8:使用DFA定義程序設(shè)計(jì)語言的無符號實(shí)數(shù)無符號實(shí)數(shù)構(gòu)成特點(diǎn):由數(shù)字0~9和小數(shù)點(diǎn)構(gòu)成0.12,34.15接受00.12,00.,.,33.拒絕S0S30,1,…,90,1,2,…,9S10S2.

1,2,…,9S4.0,1,…,9-17-2.3有限自動機(jī)例9:使用DFA定義程序設(shè)計(jì)語言的標(biāo)識符標(biāo)識符構(gòu)成特點(diǎn):由字母a~z,A~Z和數(shù)字0~9構(gòu)成x,Xy,x123,xYz接受23x,12_x，_x拒絕q0q1letterletterdigit-18-2.3有限自動機(jī)例10:使用DFA定義程序設(shè)計(jì)語言的保留字定義識別下列符號串的自動機(jī)：{int,if,else,while,for}inseelilhewroftf-19-DFA的實(shí)現(xiàn)-基于轉(zhuǎn)換圖思想：將自動機(jī)的狀態(tài)轉(zhuǎn)換固化到程序中(1)用標(biāo)號語句表示每個(gè)狀態(tài)；(2)用switch語句模擬狀態(tài)遇到不同符號發(fā)生的轉(zhuǎn)換判斷；(3)用goto語句模擬邊所代表的狀態(tài)轉(zhuǎn)換ibjkaLi:switchCurrentCharofcasea：gotoLjcaseb:gotoLkdefault:returnfalse;-20-DFA的實(shí)現(xiàn)-基于轉(zhuǎn)換圖對于每個(gè)終止?fàn)顟B(tài)，增加一個(gè)分支，如果當(dāng)前字符是字符串的結(jié)束符#，則接受;bjkaLi:switchCurrentCharofcasea：gotoLjcaseb:gotoLk

case#:returntrue;default:returnfalse;i-21-DFA的實(shí)現(xiàn)-基于轉(zhuǎn)換圖例：S0aS1S2S3cddabcLS0:Read(CurrentChar);

switch(CurrentChar){casea:gotoLS1;casec:gotoLS2:cased:gotoLS3;default:returnfalse;}LS1:Read(CurrentChar);

switch(CurrentChar){caseb:gotoLS1;cased:gotoLS2:default:returnfalse;}-22-DFA的實(shí)現(xiàn)-基于轉(zhuǎn)換圖例：S0aS1S2S3cddabcLS2:Read(CurrentChar);

switch(CurrentChar){casea:gotoLS3;default:returnfalse;}LS3:Read(CurrentChar);

switch(CurrentChar){ casec:gotoLS3:

case#:returntrue;default:returnfalse;}-23-DFA的實(shí)現(xiàn)-基于轉(zhuǎn)換表思想：將自動機(jī)表示成二維表格，作為識別程序的輸入，該識別程序的計(jì)算邏輯是自動機(jī)工作過程的模擬。識別程序：1.State=InitState;

2.Read(CurrentChar);

3.whileT(State,CurrentChar)<>error&&CurrentChar<>‘#’dobeginState=T(State,CurrentChar);Read(CurrentChar);end;4.ifCurrentChar=‘#’&&StateFinalStates，

returntrue;otherwise,returnfalse.DFA的實(shí)現(xiàn)-基于轉(zhuǎn)換表-24-abcdS0+S1⊥S2S3S1⊥S1⊥S2S2S3⊥⊥⊥S3-⊥⊥S3⊥1)cab接受or拒絕？2）abdacc接受or拒絕？拒絕接受-25-DFA的實(shí)現(xiàn)—兩種實(shí)現(xiàn)方式比較轉(zhuǎn)換表方式：是通用的算法，不同的語言，只需改變輸入的轉(zhuǎn)換表，識別程序不需改變；轉(zhuǎn)換圖方式：不需要存儲轉(zhuǎn)換表(通常轉(zhuǎn)換表是很大的)，但當(dāng)語言改變即自動機(jī)的結(jié)構(gòu)改變時(shí)，整個(gè)識別程序都需要改變。-26-2.3有限自動機(jī)小結(jié):DFA是一個(gè)抽象的數(shù)學(xué)模型，用于描述有限狀態(tài)的系統(tǒng)DFA既可以定義符號串，也可以識別符號串DFA確定性的體現(xiàn)作業(yè)：構(gòu)造一個(gè)DFA：使它能夠識別出所有能被3整除的二進(jìn)制數(shù)。注意：讀數(shù)順序是從高位到低位-27-2.3有限自動機(jī)非確定有限自動機(jī)NFA是一個(gè)五元組(S,,f,S0,Z)，其中：S是一個(gè)有限狀態(tài)集合；是一個(gè)有窮字母表；f是在S{}2S的轉(zhuǎn)換函數(shù)；S0

S是非空的初始狀態(tài)集合；ZS，是終止?fàn)顟B(tài)集，可為空。與DFA不同：（1）允許有空邊（2）對同一輸入符號允許轉(zhuǎn)向多個(gè)狀態(tài)（3）初始狀態(tài)不唯一-28-2.3有限自動機(jī)NFA的例子：S0aS2S3abbS1abS0+{S1,S3}{S2}S1+{S1}{S2}S2{S3}S3-{S3}-29-2.3有限自動機(jī)NFA所接受的字符串：定義與DFA相同NFA所定義的語言：定義與DFA相同S0aS2S3abbS1從S0出發(fā)

:(a||ab*)b*從S1出發(fā)

:(|b*)b*合并兩個(gè)串集:(a|)b*對于確定的輸入串，DFA只有一條路徑接受它，而NFA需要在多條路徑中進(jìn)行選擇-30-2.3有限自動機(jī)識別串集:(a|)b*的DFA如下：S0aS2S3abS1S0S1abbb識別符號串a(chǎn)bb？NFA的效率低！但描述問題方便。-31-2.3有限自動機(jī)NFA到DFA的轉(zhuǎn)換：對任意NFA，都存在一個(gè)DFA與之等價(jià)。轉(zhuǎn)換的思想：消除不確定性合并初始狀態(tài)集成一個(gè)狀態(tài)消除邊消除多重定義的邊。454,5123aa12,3a-32--closure(空閉包)對于給定的NFAA,和它的一個(gè)狀態(tài)集合SS,SS的空閉包計(jì)算如下：第一步：令-closure(SS)=SS;第二步：如果在狀態(tài)集SS中存在狀態(tài)s,

s到狀態(tài)s’存在一條邊，并且s’-closure(SS),

則將s’加入SS的空閉包-closure(SS);重復(fù)第二步,直到再沒有狀態(tài)可加入-closure(SS).-33-NextStates(SS,a)對于NFAA中的給定狀態(tài)集合SS

和符號a,

NextStates(SS,a)={s|對于狀態(tài)集SS中的一個(gè)狀態(tài)s1,如果A中存在一條從s1到s的a轉(zhuǎn)換邊}SSS2S3S1SS’aaSS’-34-NFA到DFA的轉(zhuǎn)換算法給定一個(gè)NFAA={,SS,SS0,,TS}生成等價(jià)的DFAA’={,SS’,S0,’,TS’}步驟(1)令S0=-closure(SS0),將S0

加入SS’;(2)從SS’中選擇一個(gè)狀態(tài)s,對于任意a,

若有s’=-closure(NextStates(s,a)),

令’(s,a)s’。若s’SS’,將s’加入SS’;

(3)重復(fù)第二步，直到SS’

中的所有狀態(tài)都被處理過;(4)對于SS’中的一個(gè)狀態(tài)s,如s={S1,..,Sn},如果有狀態(tài)SiTS,則s是A’的一個(gè)接受狀態(tài),將s加入TS’;-35-NFA到DFA的轉(zhuǎn)換算法例1：S0aS2S3abS1b={a,b}_closure({s0,s1})={s0,s1,s2,s3}-36-NFA到DFA的轉(zhuǎn)換算法例2：ab{q0}+{q1,q3}{q1,q3}{q1,q3}{q2,q4,q6,q5}{q2,q4,q6,q5}-{q4,q6,q5}{q6,q5,q4}{q4,q6,q5}-{q6,q5,q4}{q6,q5,q4}-37-DFA的化簡NFA轉(zhuǎn)換成的DFA，有時(shí)候會有一些等價(jià)狀態(tài)等價(jià)狀態(tài)會使分析效率降低，因此應(yīng)合并。合并了所有等價(jià)狀態(tài)后的DFA稱為最簡自動機(jī)。對于DFA中的任意兩個(gè)狀態(tài)s1和s2，如果分別將s1和s2當(dāng)作開始狀態(tài)，它們接受的字符串集合相同，則稱s1和s2是等價(jià)的，否則稱s1和s2是可區(qū)分的。-38-DFA化簡：狀態(tài)分離法分離法的基本思想：將一個(gè)DFA的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集中的狀態(tài)都是可區(qū)分的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的；然后，在每一個(gè)子集中選一個(gè)代表，合并掉其他的等價(jià)狀態(tài)，由此得到一個(gè)最小的DFA.分離步驟：(1)將DFA的所有狀態(tài)分成兩組：{終止?fàn)顟B(tài)},{非終止?fàn)顟B(tài)};(2)任取一組狀態(tài)，考察組內(nèi)狀態(tài)是否等價(jià)，不等價(jià)則進(jìn)行拆分；(3)重復(fù)(2)，直至所有組組內(nèi)的狀態(tài)都是等價(jià)的；(4)狀態(tài)重新命名，確認(rèn)初態(tài)，終態(tài)，狀態(tài)轉(zhuǎn)換。-39-狀態(tài)分離法---步驟(2)給定