第二章詞法分析確定有限自動機(jī)第一頁，共三十七頁，2022年，8月28日第2章outline一、詞法分析概述1，詞法分析程序的功能2，詞法分析相關(guān)的一些問題二、正則表達(dá)式三、有限自動機(jī)1，確定有限自動機(jī)DFA2，非確定有限自動機(jī)NFA，NFA到DFA的轉(zhuǎn)換3，DFA的化簡4，正則表達(dá)式到NFA的轉(zhuǎn)換四、詞法分析程序構(gòu)造√√第二頁，共三十七頁，2022年，8月28日三、有限自動機(jī)正則表達(dá)式-specification有限自動機(jī)–Implementation什么是有限自動機(jī)？ 有限自動機(jī)是描述有限狀態(tài)系統(tǒng)的數(shù)學(xué)模型。有限狀態(tài)系統(tǒng)：狀態(tài)：是將事物區(qū)分開的一種標(biāo)識.具有離散狀態(tài)的系統(tǒng)：如數(shù)字電路(0,1);電燈開關(guān)(on,off);十字路口的紅綠燈；其狀態(tài)數(shù)是有限的。具有連續(xù)狀態(tài)的系統(tǒng)：水庫的水位、室內(nèi)的溫度等可以連續(xù)發(fā)生變化；可以有無窮個狀態(tài).有限狀態(tài)系統(tǒng)是離散狀態(tài)系統(tǒng)。在很多領(lǐng)域，如網(wǎng)絡(luò)協(xié)議分析、形式驗(yàn)證、代碼安全、排版系統(tǒng)等有重要應(yīng)用。第三頁，共三十七頁，2022年，8月28日有限自動機(jī)的例子-經(jīng)典的過河問題一個人帶著一頭狼，一頭羊，以及一棵白菜處于河的左岸。人和他的伴隨品都希望渡到河的右岸。有一條小船，每擺渡一次，只能攜帶人和其余三者之一。如果單獨(dú)留下狼和羊，狼會吃羊；如果單獨(dú)留下羊和白菜，羊會吃菜。怎樣才能渡河，而羊和白菜不會被吃掉呢？第四頁，共三十七頁，2022年，8月28日過河問題模型化第五頁，共三十七頁，2022年，8月28日有限自動機(jī)的模型有限自動機(jī)FA可以理解成狀態(tài)控制器FA有有限個狀態(tài)，其中有初始狀態(tài)，終止?fàn)顟B(tài)起始：處于初始狀態(tài)，讀頭位于輸入帶開頭中間：從左到右依次讀取字符，發(fā)生狀態(tài)遷移結(jié)束：讀頭到達(dá)輸入帶末尾，狀態(tài)到達(dá)終態(tài)10110…狀態(tài)控制器讀頭輸入帶輸出第六頁，共三十七頁，2022年，8月28日有限自動機(jī)的五要素有限狀態(tài)集SS有限輸入符號集轉(zhuǎn)移函數(shù)(s,a)=t一個開始狀態(tài)s0一個終止?fàn)顟B(tài)集TS輸入：字符串輸出：若輸入字符串結(jié)束，且到達(dá)終止?fàn)顟B(tài)，則接受，否則拒絕。例如：“101”

輸出拒絕，“1010”輸出接受。第七頁，共三十七頁，2022年，8月28日1、確定有限自動機(jī)DFA確定有限自動機(jī)DFA是一個五元組M=(SS,,,S0,TS)，SS：有限的狀態(tài)集合{S0，S1，S2，…}：有限的輸入字符表：狀態(tài)轉(zhuǎn)換函數(shù)，SSSS{}是單值全映射函數(shù)；S0：初始狀態(tài)，S0

SSTS：終止?fàn)顟B(tài)集，TSSS

第八頁，共三十七頁，2022年，8月28日例1：DFAM=({0,1,2,3,4},{a,b},,{0},{3})其中為：

(0,a)=1(0,b)=4

(1,a)=4(1,b)=2

(2,a)=3(2,b)=4

(3,a)=3(3,b)=3

(4,a)=4(4,b)=4第九頁，共三十七頁，2022年，8月28日DFA的兩種表示形式轉(zhuǎn)換表(transitiontable)易于實(shí)現(xiàn)轉(zhuǎn)換圖(transitiongraph)直觀，易于理解第十頁，共三十七頁，2022年，8月28日轉(zhuǎn)換表行：狀態(tài)列：字符元素：表示狀態(tài)轉(zhuǎn)換，狀態(tài)或開始狀態(tài)：默認(rèn)表的第一行表示開始狀態(tài),或者狀態(tài)加上角標(biāo)+終止?fàn)顟B(tài)：狀態(tài)加上角標(biāo)-ab0+14142………3-33第十一頁，共三十七頁，2022年，8月28日轉(zhuǎn)換表例1：DFAM=({0,1,2,3,4},{a,b},,{0},{3})其中為：

(0,a)=1(0,b)=4

(1,a)=4(1,b)=2

(2,a)=3(2,b)=4

(3,a)=3(3,b)=3

(4,a)=4(4,b)=4ab0+141422343-33444第十二頁，共三十七頁，2022年，8月28日轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換邊

f(S1,a)=S2開始狀態(tài)終止?fàn)顟B(tài)S0SS

aS1S2第十三頁，共三十七頁，2022年，8月28日轉(zhuǎn)換圖ab0+141422343-334440213abababba4ab第十四頁，共三十七頁，2022年，8月28日轉(zhuǎn)換圖ab0+112233-330213aabbaab0+112233-33第十五頁，共三十七頁，2022年，8月28日DFA的例子例2：:{a,b,c,d}SS:{S0,S1,S2,S3}開始狀態(tài):S0

終止?fàn)顟B(tài)集:{S3}f:{(S0,a)S1,(S0,c)S2,(S0,d)S3,(S1,b)S1,(S1,d)S2,(S2,a)S3,(S3,c)S3}S0aS1S2S3cddabc第十六頁，共三十七頁，2022年，8月28日DFA的確定性形式定義初始狀態(tài)唯一：S0轉(zhuǎn)換函數(shù)是單值函數(shù)，即對任一狀態(tài)和輸入符號，唯一地確定了下一個狀態(tài)轉(zhuǎn)換表初始狀態(tài)唯一：第一行表元素唯一轉(zhuǎn)換圖初始狀態(tài)唯一:每個狀態(tài)最多發(fā)出n條邊，n是字母表中字母的個數(shù)，且發(fā)出的任意兩條邊上標(biāo)的字母都不同第十七頁，共三十七頁，2022年，8月28日DFA的一些概念DFA接受的字符串如果M是一個DFA,a1

a2…

an

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

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

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

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

a2…

an

被DFAM接受.DFA定義的串的集合(DFA接受的語言)DFAM接受的所有串的集合，稱為M定義的語言，記為L(M)a1a2an第十八頁，共三十七頁，2022年，8月28日DFA接受的語言例1中自動機(jī)接受的語言是L(aba(a|b)*)例2中自動機(jī)接受的語言是L((ab*da|ca|d)c*)0213aabbaS0aS1S2S3cddabc第十九頁，共三十七頁，2022年，8月28日DFA接受的語言若DFAM只有一個狀態(tài)，既是開始狀態(tài)又是終止?fàn)顟B(tài)，則DFAM定義的串集是L()={}若若DFAM只有一個狀態(tài)，并且是開始狀態(tài)或DFAM有若干個狀態(tài)，但開始狀態(tài)到終止?fàn)顟B(tài)之間沒有通路，則DFAM定義的串集是空集SS0或S0SS’S’’第二十頁，共三十七頁，2022年，8月28日設(shè)計(jì)有限自動機(jī)自動機(jī)的設(shè)計(jì)是一個創(chuàng)造過程，沒有固定的算法和過程例1：={a,b},構(gòu)造自動機(jī)識別由所有奇數(shù)個a和奇數(shù)個b組成的字符串。S奇a,奇bS奇a,偶bS偶a,奇bS偶a,偶bbbbaabaa關(guān)鍵：不需要記住所看到的整個字符串，只需記住至此所看到的a和b的個數(shù)是奇數(shù)還是偶數(shù)第二十一頁，共三十七頁，2022年，8月28日設(shè)計(jì)有限自動機(jī)例2：設(shè)計(jì)有限自動機(jī)M，識別{0,1}上的語言

L={x000y|x,y{0|1}*}

分析：該語言的特點(diǎn)是每個串都包含連續(xù)3個0的子串。自動機(jī)的任務(wù)就是識別/檢查000

的子串。q0q1q2q300011101第二十二頁，共三十七頁，2022年，8月28日設(shè)計(jì)有限自動機(jī)例3：設(shè)計(jì)有限自動機(jī)M，識別{0,1,2}上的語言，每個字符串代表的數(shù)字能整除3。分析:(1)一個十進(jìn)制數(shù)除以3，余數(shù)只能是0,1,2；(2)被3整除的十進(jìn)制數(shù)的特點(diǎn)：十進(jìn)制數(shù)的所有位數(shù)字的和能整除3。q0q1q2110210022第二十三頁，共三十七頁，2022年，8月28日DFA與程序設(shè)計(jì)語言的單詞結(jié)構(gòu)例4：使用DFA定義程序設(shè)計(jì)語言的無符號實(shí)數(shù)

0.12,34.15接受

00.12,00.,.,33.拒絕S0S30,1,…,90,1,2,…,9S10S2.

1,2,…,9S4.0,1,…,9第二十四頁，共三十七頁，2022年，8月28日DFA與程序設(shè)計(jì)語言的單詞結(jié)構(gòu)例5：使用DFA定義程序設(shè)計(jì)語言的標(biāo)識符x,Xy,x123,xYz接受23x,12_x，_x拒絕q0q1letterletterdigit第二十五頁，共三十七頁，2022年，8月28日DFA與程序設(shè)計(jì)語言的單詞結(jié)構(gòu)例6：使用DFA定義程序設(shè)計(jì)語言的保留字{if,else,while,for}ifseelilhewrof第二十六頁，共三十七頁，2022年，8月28日DFA的實(shí)現(xiàn)目的給定一個DFAM定義了一個串集編寫一個程序，檢查給定的串是否被DFAM所識別或接受兩種途徑基于轉(zhuǎn)換表基于轉(zhuǎn)換圖第二十七頁，共三十七頁，2022年，8月28日基于轉(zhuǎn)換表的DFA實(shí)現(xiàn)主要思想輸入:一個字符串,以’#’結(jié)尾.輸出:如果接受則輸出true

否則輸出false數(shù)據(jù)結(jié)構(gòu)：轉(zhuǎn)換表(二維數(shù)組T)兩個變量State:記錄當(dāng)前狀態(tài);CurrentChar:記錄串中當(dāng)前正在被讀的字符;第二十八頁，共三十七頁，2022年，8月28日基于轉(zhuǎn)換表的DFA實(shí)現(xiàn)算法主要思想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.第二十九頁，共三十七頁，2022年，8月28日S0(c)S2(a)S3(b)S0(a)S1(b)S1(d)S2(a)S3(c)S3(c)S3abcdS0+S1⊥S2S3S1⊥S1⊥S2S2S3⊥⊥⊥S3-⊥⊥S3⊥1)cab接受or拒絕？2）abdacc接受or拒絕？拒絕接受第三十頁，共三十七頁，2022年，8月28日基于轉(zhuǎn)換圖的DFA實(shí)現(xiàn)每個狀態(tài)對應(yīng)一個帶標(biāo)號的case語句每條邊對應(yīng)一個goto

語句對于每個終止?fàn)顟B(tài)，增加一個分支，如果當(dāng)前字符是字符串的結(jié)束符#，則接受;ibjkaLi:caseCurrentCharofa：gotoLjb:gotoLkother:Error()第三十一頁，共三十七頁，2022年，8月28日基于轉(zhuǎn)換圖的DFA實(shí)現(xiàn)每個狀態(tài)對應(yīng)一個帶標(biāo)號的case語句每條邊對應(yīng)一個goto

語句對于每個終止?fàn)顟B(tài)，增加一個分支，如果當(dāng)前字符是字符串的結(jié)束符#，則接受;bjkaiLi:caseCurrentCharofa：gotoLjb:gotoLk

#:returntrue;other:returnfalse;第三十二頁，共三十七頁，2022年，8月28日S0aS1S2S3cddabcLS0:Read(CurrentChar);

switch(CurrentChar){casea:gotoLS1;

casec:gotoLS2:

cased:gotoLS3;other:returnfalse;}LS1:Read(CurrentChar);

switch(CurrentChar){caseb:gotoLS1;