第二章詞法分析非確定有限自動(dòng)機(jī)

第二章詞法分析非確定有限自動(dòng)機(jī)第一頁(yè)，共二十九頁(yè)，編輯于2023年，星期四第2章outline一、詞法分析概述1，詞法分析程序的功能2，詞法分析相關(guān)的一些問(wèn)題二、正則表達(dá)式三、有限自動(dòng)機(jī)1，確定有限自動(dòng)機(jī)DFA2，非確定有限自動(dòng)機(jī)NFA，NFA到DFA的轉(zhuǎn)換3，DFA的化簡(jiǎn)4，正則表達(dá)式到NFA的轉(zhuǎn)換四、詞法分析程序構(gòu)造√√√第二頁(yè)，共二十九頁(yè)，編輯于2023年，星期四2、非確定有限自動(dòng)機(jī)確定有限自動(dòng)機(jī)是五元組(SS,,,S0,TS)確定性體現(xiàn)：初始狀態(tài)唯一、轉(zhuǎn)換函數(shù)是單值函數(shù)非確定有限自動(dòng)機(jī)：也是五元組(SS,,,S0,TS)其中

SS={S0,S1,…Sn}是狀態(tài)集是字母表

S0

SS是初始狀態(tài)集,不能為空

是轉(zhuǎn)換函數(shù)，但不要求是單值的:SS()2SS

TSSS是終止?fàn)顟B(tài)集，可為空。第三頁(yè)，共二十九頁(yè)，編輯于2023年，星期四非確定有限自動(dòng)機(jī)的例子={a,b}SS:{S0,S1,S2,S3}初始狀態(tài)集:{S0,S1}終止?fàn)顟B(tài)集:{S3}:{(S0,a){S1,S3},(S0,){S2},(S1,b){S1},(S1,){S2},(S2,){S3},(S3,b){S3}}NFA也可以用狀態(tài)轉(zhuǎn)換圖或狀態(tài)轉(zhuǎn)換矩陣表示第四頁(yè)，共二十九頁(yè)，編輯于2023年，星期四非確定有限自動(dòng)機(jī)的例子S0aS2S3abbS1abS+{S1,S3}{S2}S1+{S1}{S2}S2{S3}S3-{S3}狀態(tài)集合第五頁(yè)，共二十九頁(yè)，編輯于2023年，星期四NFA接受的字符串NFA接受的字符串如果M是一個(gè)NFA,a1a2…an

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

S0S1,S1S2,……,Sn-1Sn其中S0是開(kāi)始狀態(tài)之一，Sn是接受狀態(tài)之一，則串a(chǎn)1a2…an

被NFAM接受.NFA定義的串的集合(NFA接受的語(yǔ)言)NFAM接受的所有串的集合，稱為M定義的語(yǔ)言，記為L(zhǎng)(M)a1a2an第六頁(yè)，共二十九頁(yè)，編輯于2023年，星期四NFA與DFA的比較DFANFA初始狀態(tài)一個(gè)初始狀態(tài)初始狀態(tài)集合邊不允許允許

(S,a)

S’or⊥{S1,…,Sn}or⊥實(shí)現(xiàn)容易有不確定性對(duì)于確定的輸入串，DFA只有一條路徑接受它NFA則可能需要在多條路徑中進(jìn)行選擇！第七頁(yè)，共二十九頁(yè)，編輯于2023年，星期四NFA到DFA的轉(zhuǎn)換例如輸入串：100NFANFA需要在多條路徑中選擇，因此的效率低！但NFA描述問(wèn)題方便。NFA和DFA都識(shí)別正則語(yǔ)言。NFA可轉(zhuǎn)換成DFA。SPQ010101第八頁(yè)，共二十九頁(yè)，編輯于2023年，星期四NFA到DFA的轉(zhuǎn)換對(duì)任意NFA，都存在一個(gè)DFA與之等價(jià)。轉(zhuǎn)換的思想：消除不確定性合并初始狀態(tài)集成一個(gè)狀態(tài)消除邊消除多重定義的邊。123aa12,3a454，5第九頁(yè)，共二十九頁(yè)，編輯于2023年，星期四-closure(空閉包)對(duì)于給定的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ù)第二步,直到再?zèng)]有狀態(tài)可加入-closure(SS).第十頁(yè)，共二十九頁(yè)，編輯于2023年，星期四-closure的例子S0aS1S2S3abc

-closure({S0,S1})

=①{S0,S1}②{S0,S1,S2}③{S0,S1,S2}④{S0,S1,S2,S3}第十一頁(yè)，共二十九頁(yè)，編輯于2023年，星期四轉(zhuǎn)向狀態(tài)對(duì)于NFAA中的給定狀態(tài)集合SS

和符號(hào)a,NextStates(SS,a)={s|對(duì)于狀態(tài)集SS中的一個(gè)狀態(tài)s1,如果A中存在一條從s1到s的a轉(zhuǎn)換邊}SSS2S3S1SS’aa({S1,S2,S3},a)={S,S’}第十二頁(yè)，共二十九頁(yè)，編輯于2023年，星期四轉(zhuǎn)向狀態(tài)的例子S0aS1S2S3abc

NextStates({S0,S1},a)

={S1,S3}

NextStates({S0,S1},b)

={S1}第十三頁(yè)，共二十九頁(yè)，編輯于2023年，星期四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,對(duì)于任意a,

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

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

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

中的所有狀態(tài)都被處理過(guò);(4)對(duì)于SS’中的一個(gè)狀態(tài)s,如s={S1,..,Sn},如果有狀態(tài)SiTS,則s是A’的一個(gè)接受狀態(tài),將s加入TS’;第十四頁(yè)，共二十九頁(yè)，編輯于2023年，星期四NFA到DFA轉(zhuǎn)換的例子例1：={a,b,c},S0=-closure({S0,S10})

={S0,S10,S2,S*}

,abc{S0,S1,S2,S3}+-{S1,S3,S2}{S1,S3,S2}{S3}{S1,S3,S2}-{S1,S3,S2}{S3}{S3}-{S3}S0aS1S2S3abc第十五頁(yè)，共二十九頁(yè)，編輯于2023年，星期四NFA到DFA轉(zhuǎn)換的例子例2：

01{S0}+{S0,S1}{S0}{S0,S1}-{S0,S1,S2}{S0}{S0,S1,S2}-{S0,S1,S2}{S0}S0S1S2SPQ010101第十六頁(yè)，共二十九頁(yè)，編輯于2023年，星期四NFA到DFA轉(zhuǎn)換的例子例3：q0q1q4q6q2q3q5aaabbba,bab{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}第十七頁(yè)，共二十九頁(yè)，編輯于2023年，星期四DFA的化簡(jiǎn)NFA轉(zhuǎn)換成的DFA，有時(shí)候會(huì)有一些等價(jià)狀態(tài)，這些等價(jià)狀態(tài)會(huì)使分析效率降低，因此應(yīng)合并。合并了所有等價(jià)狀態(tài)后的DFA稱為最簡(jiǎn)自動(dòng)機(jī)。q0aqAqcqBaa,bbabDFAM1第十八頁(yè)，共二十九頁(yè)，編輯于2023年，星期四等價(jià)DFA和最簡(jiǎn)DFA的定義等價(jià)DFAs如果兩個(gè)DFA接受的字符串的集合是相同的;在接受相同字符串集的DFA中，最小DFA指的是狀態(tài)數(shù)最少的DFAq0aqAqca,bbDFAM2a第十九頁(yè)，共二十九頁(yè)，編輯于2023年，星期四等價(jià)的DFAsS0aS1S4*bdS3*S2dS0aS1bdS*兩個(gè)DFA等價(jià)，是因?yàn)樵谶@兩個(gè)DFA中存在接受相同字符串的狀態(tài)!第二十頁(yè)，共二十九頁(yè)，編輯于2023年，星期四主要思想等價(jià)狀態(tài)對(duì)于DFA中的任意兩個(gè)狀態(tài)s1和s2，如果分別將s1和s2當(dāng)作開(kāi)始狀態(tài)，它們接受的字符串集合相同，則稱s1和s2是等價(jià)狀態(tài);DFA化簡(jiǎn)的兩種方式合并等價(jià)狀態(tài);(狀態(tài)合并法)分離不等價(jià)狀態(tài);(狀態(tài)分離法)第二十一頁(yè)，共二十九頁(yè)，編輯于2023年，星期四狀態(tài)分離法化簡(jiǎn)DFA給定一個(gè)DFAA={,SS,S0,,TS}：要生成與其等價(jià)的DFAA’={,SS’,S0’,’,TS’}分離步驟：(1)將A的所有狀態(tài)分成兩組：{非終止?fàn)顟B(tài)},{終止?fàn)顟B(tài)};(2)選擇一組狀態(tài)SSi={Si1,…,Sin},用split(SSi)替換SSi;(3)重復(fù)第(2)步，直到所有組都被處理過(guò);

(4)令SS’=組的集合;(5)S0’：包含S0

的組作為S0’;(6)TS’:包含A的終止?fàn)顟B(tài)的組，作為A’的終止?fàn)顟B(tài);(7)’:’（SSi,a）=SSj,若在A中有SiSj,且siSSi,sjSSja第二十二頁(yè)，共二十九頁(yè)，編輯于2023年，星期四分離狀態(tài)

給定一個(gè)DFAA={,SS,S0,,TS}：假定狀態(tài)集合SS分成了m組：{SS1,…,SSm},SS1……SSm=SS,SS1……SSm=;

任取一個(gè)狀態(tài)組SSi={Si1,…,Sin},考察SSi是否可繼續(xù)分離split(SSi)

：判斷SSi是否需要分裂，是則將SSi分裂成兩組G1和G2,過(guò)程如下：初始G1={Sip},1pn,即任取SSi中的一個(gè)狀態(tài)放入G1,G2={}.forj=1ton(假設(shè)SSi有n個(gè)狀態(tài))對(duì)于所有a,任意的SijSSi,若有(Sip,a)=Sk，(Sij,a)=Sq，如果Sk和Sq屬于同一個(gè)組SSt,則將Sij加入組G1;否則將Sij加入組G2;

第二十三頁(yè)，共二十九頁(yè)，編輯于2023年，星期四簡(jiǎn)單例子S0aS1S4*bdS3*S2d{S0,S1,S2},{S3*,S4*}{S0},{S1,S2},{S3*,S4*}第二十四頁(yè)，共二十九頁(yè)，編輯于2023年，星期四DFA化簡(jiǎn)的例子例1：{0，1，2，3}和{4}{0,1,3},{2}和{4}{0,3},{1},{2}和{4}01234aabbabbb0124aabbbb第二十五頁(yè)，共二十九頁(yè)，編輯于2023年，星期四DFA化簡(jiǎn)的例子例2：{0，1，2，3}，{4}{0，2}、{1，3}，{4}{0}，{2}，{1，3}，{4}a

4

012aababbb3a，b

4

012aababba，b第二十六頁(yè)