第二章詞法分析非確定有限自動機

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

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

S0

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

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

TSSS是終止狀態(tài)集，可為空。第三頁，共二十九頁，編輯于2023年，星期四非確定有限自動機的例子={a,b}SS:{S0,S1,S2,S3}初始狀態(tài)集:{S0,S1}終止狀態(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)換矩陣表示第四頁，共二十九頁，編輯于2023年，星期四非確定有限自動機的例子S0aS2S3abbS1abS+{S1,S3}{S2}S1+{S1}{S2}S2{S3}S3-{S3}狀態(tài)集合第五頁，共二十九頁，編輯于2023年，星期四NFA接受的字符串NFA接受的字符串如果M是一個NFA,a1a2…an

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

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

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

(S,a)

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

-closure({S0,S1})

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

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

NextStates({S0,S1},a)

={S1,S3}

NextStates({S0,S1},b)

={S1}第十三頁，共二十九頁，編輯于2023年，星期四NFA到DFA的轉(zhuǎn)換算法(子集法)給定一個NFAA={,SS,SS0,,TS}生成等價的DFAA’={,SS’,S0,’,TS’}步驟(1)令S0=-closure(SS0),將S0

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

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

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

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

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

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

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

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

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

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

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

4

012aababbb3a，b

4

012aababba，b第二十六頁