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

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

輸出拒絕，“1010”輸出接受。第七頁(yè)，共三十七頁(yè)，2022年，8月28日1、確定有限自動(dòng)機(jī)DFA確定有限自動(dòng)機(jī)DFA是一個(gè)五元組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

第八頁(yè)，共三十七頁(yè)，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第九頁(yè)，共三十七頁(yè)，2022年，8月28日DFA的兩種表示形式轉(zhuǎn)換表(transitiontable)易于實(shí)現(xiàn)轉(zhuǎn)換圖(transitiongraph)直觀，易于理解第十頁(yè)，共三十七頁(yè)，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第十一頁(yè)，共三十七頁(yè)，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第十二頁(yè)，共三十七頁(yè)，2022年，8月28日轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換邊

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

aS1S2第十三頁(yè)，共三十七頁(yè)，2022年，8月28日轉(zhuǎn)換圖ab0+141422343-334440213abababba4ab第十四頁(yè)，共三十七頁(yè)，2022年，8月28日轉(zhuǎn)換圖ab0+112233-330213aabbaab0+112233-33第十五頁(yè)，共三十七頁(yè)，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第十六頁(yè)，共三十七頁(yè)，2022年，8月28日DFA的確定性形式定義初始狀態(tài)唯一：S0轉(zhuǎn)換函數(shù)是單值函數(shù)，即對(duì)任一狀態(tài)和輸入符號(hào)，唯一地確定了下一個(gè)狀態(tài)轉(zhuǎn)換表初始狀態(tài)唯一：第一行表元素唯一轉(zhuǎn)換圖初始狀態(tài)唯一:每個(gè)狀態(tài)最多發(fā)出n條邊，n是字母表中字母的個(gè)數(shù)，且發(fā)出的任意兩條邊上標(biāo)的字母都不同第十七頁(yè)，共三十七頁(yè)，2022年，8月28日DFA的一些概念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定義的串的集合(DFA接受的語(yǔ)言)DFAM接受的所有串的集合，稱為M定義的語(yǔ)言，記為L(zhǎng)(M)a1a2an第十八頁(yè)，共三十七頁(yè)，2022年，8月28日DFA接受的語(yǔ)言例1中自動(dòng)機(jī)接受的語(yǔ)言是L(aba(a|b)*)例2中自動(dòng)機(jī)接受的語(yǔ)言是L((ab*da|ca|d)c*)0213aabbaS0aS1S2S3cddabc第十九頁(yè)，共三十七頁(yè)，2022年，8月28日DFA接受的語(yǔ)言若DFAM只有一個(gè)狀態(tài)，既是開始狀態(tài)又是終止?fàn)顟B(tài)，則DFAM定義的串集是L()={}若若DFAM只有一個(gè)狀態(tài)，并且是開始狀態(tài)或DFAM有若干個(gè)狀態(tài)，但開始狀態(tài)到終止?fàn)顟B(tài)之間沒有通路，則DFAM定義的串集是空集SS0或S0SS’S’’第二十頁(yè)，共三十七頁(yè)，2022年，8月28日設(shè)計(jì)有限自動(dòng)機(jī)自動(dòng)機(jī)的設(shè)計(jì)是一個(gè)創(chuàng)造過(guò)程，沒有固定的算法和過(guò)程例1：={a,b},構(gòu)造自動(dòng)機(jī)識(shí)別由所有奇數(shù)個(gè)a和奇數(shù)個(gè)b組成的字符串。S奇a,奇bS奇a,偶bS偶a,奇bS偶a,偶bbbbaabaa關(guān)鍵：不需要記住所看到的整個(gè)字符串，只需記住至此所看到的a和b的個(gè)數(shù)是奇數(shù)還是偶數(shù)第二十一頁(yè)，共三十七頁(yè)，2022年，8月28日設(shè)計(jì)有限自動(dòng)機(jī)例2：設(shè)計(jì)有限自動(dòng)機(jī)M，識(shí)別{0,1}上的語(yǔ)言

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

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

的子串。q0q1q2q300011101第二十二頁(yè)，共三十七頁(yè)，2022年，8月28日設(shè)計(jì)有限自動(dòng)機(jī)例3：設(shè)計(jì)有限自動(dòng)機(jī)M，識(shí)別{0,1,2}上的語(yǔ)言，每個(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第二十三頁(yè)，共三十七頁(yè)，2022年，8月28日DFA與程序設(shè)計(jì)語(yǔ)言的單詞結(jié)構(gòu)例4：使用DFA定義程序設(shè)計(jì)語(yǔ)言的無(wú)符號(hào)實(shí)數(shù)

0.12,34.15接受

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

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

否則輸出false數(shù)據(jù)結(jié)構(gòu)：轉(zhuǎn)換表(二維數(shù)組T)兩個(gè)變量State:記錄當(dāng)前狀態(tài);CurrentChar:記錄串中當(dāng)前正在被讀的字符;第二十八頁(yè)，共三十七頁(yè)，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.第二十九頁(yè)，共三十七頁(yè)，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拒絕？拒絕接受第三十頁(yè)，共三十七頁(yè)，2022年，8月28日基于轉(zhuǎn)換圖的DFA實(shí)現(xiàn)每個(gè)狀態(tài)對(duì)應(yīng)一個(gè)帶標(biāo)號(hào)的case語(yǔ)句每條邊對(duì)應(yīng)一個(gè)goto

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

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

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

switch(CurrentChar){casea:gotoLS1;

casec:gotoLS2:

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

switch(CurrentChar){caseb:gotoLS1;