第三章編譯原理

第三章編譯原理第1頁，課件共100頁，創(chuàng)作于2023年2月本章重點單詞的描述工具單詞的識別系統(tǒng)設(shè)計和實現(xiàn)詞法分析程序首先需要描述和刻畫程序設(shè)計語言中的原子單位——單詞，其次需要識別單詞和執(zhí)行某些相關(guān)的動作。描述程序設(shè)計語言的詞法的機制是正則表達(dá)式，識別機制是有窮狀態(tài)自動機。第2頁，課件共100頁，創(chuàng)作于2023年2月回顧什麼是詞法分析程序?qū)崿F(xiàn)詞法分析（lexicalanalysis）的程序逐個讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語言中具有獨立意義的最小單位，包括保留字、標(biāo)識符、運算符、標(biāo)點符號和常量等。詞法分析是編譯過程中的一個階段，在語法分析前進(jìn)行。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析使用。第3頁，課件共100頁，創(chuàng)作于2023年2月

詞法分析程序和語法分析程序的關(guān)系源程序詞法分析程序語法分析程序Tokengettoken….第4頁，課件共100頁，創(chuàng)作于2023年2月

詞法分析程序的主要任務(wù)：讀源程序，產(chǎn)生單詞符號詞法分析程序的其他任務(wù)：濾掉空格，跳過注釋、換行符追蹤換行標(biāo)志，復(fù)制出錯源程序，宏展開，……第5頁，課件共100頁，創(chuàng)作于2023年2月常常遇到的術(shù)語

Token 單詞,詞標(biāo)，符號lexeme 詞素，詞位pattern 模式，式樣第6頁，課件共100頁，創(chuàng)作于2023年2月

幫助理解術(shù)語Ingeneral，thereisasetofstringsintheinputforwhichthesametokenisproducedasoutput.Thissetofstringsisdescribedbyarulecalledapatternassociatedwiththetoken.Thepatternissaidtomatcheachstringintheset.Alexemeisasequenceofcharactersinthesourceprogramthatismatchedbythepatternforatoken.e.g.Constpi=3.14159；中的pi是token“identifier”的lexeme，其pattern為letterfollowedbylettersand/ordigit.第7頁，課件共100頁，創(chuàng)作于2023年2月詞法分析工作從語法分析工作獨立出來的原因：簡化設(shè)計改進(jìn)編譯效率增加編譯系統(tǒng)的可移植性第8頁，課件共100頁，創(chuàng)作于2023年2月正規(guī)表達(dá)式與正規(guī)集（正規(guī)語言）

程序設(shè)計語言中的單詞是基本語法成分.單詞符號的語法可以用有效的工具加以描述，并且基于這類描述工具，實現(xiàn)詞法分析程序的自動構(gòu)造.首先表述一些基本術(shù)語和概念.符號一個抽象實體,我們不再形式地定義它(就象幾何中的”點”一樣).例如字母是符號,數(shù)字也是符號。字母表字母表是元素的非空有窮集合，我們把字母表中的元素稱為符號，因此字母表也稱為符號集。不同的語言可以有不同的字母表，例如漢語的字母表中包括漢字、數(shù)字及標(biāo)點符號等。PASCAL語言的字母表是由字母、數(shù)字、若干專用符號及BEGIN、IF之類的保留字組成。第9頁，課件共100頁，創(chuàng)作于2023年2月符號串

由字母表中的符號組成的任何有窮序列稱為符號串，例如001110是字母表

=｛0，1｝上的符號串.

字母表A=｛a,b,c｝上的一些符號串有：a,b,c,ab,aaca。在符號串中，符號的順序是很重要的，符號串a(chǎn)b就不同于ba,abca和aabc也不同?？梢允褂米帜副硎痉柎?，如x=STR表示“x是由符號S、T和R，并按此順序組成的符號串”。符號串的長度

如果某符號串x中有m個符號，則稱其長度為m，表示為｜x｜=m，如001110的長度是6。空符號串，即不包含任何符號的符號串，用ε表示，其長度為0，即｜ε｜=0。第10頁，課件共100頁，創(chuàng)作于2023年2月

介紹有關(guān)符號串的一些運算。

符號串的頭,尾，固有頭和固有尾：如果z=xy是一符號串，那么x是z的頭，y是z的尾，如果x是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。舉個例子:設(shè)z=abc,那么z的頭是ε,a,ab,abc,除abc外，其它都是固有頭；z的尾是ε,c,bc,abc,z的固有尾是ε,c,bc。當(dāng)對符號串z=xy的頭感興趣而對其余部分不感興趣時，采用省略寫法：z=x…；如果只是為了強調(diào)x在符號串z中的某處出現(xiàn)，則可表示為：z=…x…；符號t是符號串z的第一個符號，則表示為z=t…。第11頁，課件共100頁，創(chuàng)作于2023年2月符號串的連接：設(shè)x和y是符號串，它們的連接xy是把y的符號寫在x的符號之后得到的符號串.由于ε

的含義，顯然有ε

x=xε=x。例如x=ST，y=abu，則它們的連接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5符號串的方冪：符號串自身連接n次得到的符號串a(chǎn)n定義為aa…aan個aa1=a,a2=aa且a0=ε例；若x=AB則:x0=ε

x1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n>0)第12頁，課件共100頁，創(chuàng)作于2023年2月

符號串集合：若集合A中所有元素都是某字母表

上的符號串，則稱A為字母表

上的符號串集合。兩個符號串集合A和B的乘積定義為AB=xy|xA且yB若集合A=ab,cde集合B=0,1則AB=ab1,ab0,cde0,cde1

使用*表示上的一切符號串（包括ε）組成的集合。Σ*稱為Σ的閉包。

上的除ε外的所有符號串組成的集合記為

+。

Σ+稱為Σ的正閉包。第13頁，課件共100頁，創(chuàng)作于2023年2月

例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}第14頁，課件共100頁，創(chuàng)作于2023年2月正規(guī)式正規(guī)式也稱正則表達(dá)式,正規(guī)表達(dá)式（regularexpression）是說明單詞的模式(pattern)的一種重要的表示法（記號），是定義正規(guī)集的數(shù)學(xué)工具。我們用以描述單詞符號。下面是正規(guī)式和它所表示的正規(guī)集的遞歸定義。第15頁，課件共100頁，創(chuàng)作于2023年2月定義（正規(guī)式和它所表示的正規(guī)集）：設(shè)字母表為，輔助字母表`={，，，，，，}。1。和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和{}；第16頁，課件共100頁，創(chuàng)作于2023年2月2。任何a

，a是上的一個正規(guī)式，它所表示的正規(guī)集為{a}；3。假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1

也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1),L(e1)L(e2),L(e1)L(e2)和(L(e1))

。4。僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集。第17頁，課件共100頁，創(chuàng)作于2023年2月

正規(guī)式中的符號

其中的“”讀為“或”（也有使用“+”代替“”的）；“

”讀為“連接”；“

”讀為“閉包”（即，任意有限次的自重復(fù)連接）。在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為“

”、“

”、“”。連接符“

”一般可省略不寫?！?/p>

”、“

”和“”都是左結(jié)合的。第18頁，課件共100頁，創(chuàng)作于2023年2月例子令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a

{,a,a,……任意個a的 串}第19頁，課件共100頁，創(chuàng)作于2023年2月

正規(guī)式 正規(guī)集(ab)

{,a,b,aa,ab……所有由a 和b組成的串}(ab)

(aabb)(ab)

{

上所有含有兩個相繼 的a或兩個相繼的b組成 的串}第20頁，課件共100頁，創(chuàng)作于2023年2月

討論下面兩個例子例3.1令

={l，d}，則上的正規(guī)式r=l(ld)

定義的正規(guī)集為:{l,ll,ld,ldd,……},其中l(wèi)代表字母,d代表數(shù)字,正規(guī)式即是字母(字母|數(shù)字)

,它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”,就是Pascal和多數(shù)程序設(shè)計語言允許的的標(biāo)識符的詞法規(guī)則.例3.2={d，，e，+，-},則上的正規(guī)式d

(dd

)(e(+-)dd

)表示的是無符號數(shù)的集合。其中d為0~9的數(shù)字。

程序設(shè)計語言的單詞都能用正規(guī)式來定義.第21頁，課件共100頁，創(chuàng)作于2023年2月若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價,寫作e1=e2。例如：e1=(ab)，e2=ba又如：e1=b(ab)

,e2=(ba)

b

e1=(ab),e2

=(a

b

)

第22頁，課件共100頁，創(chuàng)作于2023年2月設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：1。rs=sr “或”服從交換律2。r(st)=(rs)t “或”的可結(jié)合律3。(rs)t=r(st) “連接”的可結(jié)合律4。r(st)=rsrt (st)r=srtr 分配律第23頁，課件共100頁，創(chuàng)作于2023年2月5。r=r,r=r 是“連接”的恒等元素 零一律6。rr=r r

=rrr… “或”的抽取律

第24頁，課件共100頁，創(chuàng)作于2023年2月有窮自動機有窮自動機(也稱有限自動機)作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。有窮自動機分為兩類：確定的有窮自動機(DeterministicFiniteAutomata)和不確定的有窮自動機(NondeterministicFiniteAutomata)。第25頁，課件共100頁，創(chuàng)作于2023年2月關(guān)于有窮自動機我們將討論如下題目確定的有窮自動機DFA不確定的有窮自動機NFANFA的確定化DFA的最小化第26頁，課件共100頁，創(chuàng)作于2023年2月確定的有窮自動機DFADFA定義：一個確定的有窮自動機（DFA）M是一個五元組：M=（K，Σ，f，S，Z）其中1.K是一個有窮集，它的每個元素稱為一個狀態(tài)；2.Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱Σ為輸入符號表；第27頁，課件共100頁，創(chuàng)作于2023年2月DFA定義3.f是轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4.S∈K是唯一的一個初態(tài)；5.Z

K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。第28頁，課件共100頁，創(chuàng)作于2023年2月一個DFA的例子：DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q第29頁，課件共100頁，創(chuàng)作于2023年2月一個DFA可以表示成一個狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。假定DFAM含有m個狀態(tài)，n個輸入字符，那么這個狀態(tài)圖含有m個結(jié)點，每個結(jié)點最多有n個弧射出，整個圖含有唯一一個初態(tài)結(jié)點和若干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“=>”或標(biāo)以“-”，終態(tài)結(jié)點用雙圈表示或標(biāo)以“+”，若f(ki,a)=kj，則從狀態(tài)結(jié)點ki到狀態(tài)結(jié)點kj畫標(biāo)記為a的??；

第30頁，課件共100頁，創(chuàng)作于2023年2月

DFA的狀態(tài)圖表示bSUVQaaaba，b第31頁，課件共100頁，創(chuàng)作于2023年2月一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭“=>”標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標(biāo)以1，非終態(tài)標(biāo)以0。第32頁，課件共100頁，創(chuàng)作于2023年2月DFA的矩陣表示字符狀態(tài)0001第33頁，課件共100頁，創(chuàng)作于2023年2月

為了說明DFA如何作為一種識別機制,我們還要理解下面的定義

∑*上的符號串t在DFAM上運行一個輸入符號串t，（將它表示成Tt1的形式，其中T∈∑，t1∈∑*）在DFAM=（K，Σ，f，S，Z）上運行的定義為：f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K擴充轉(zhuǎn)換函數(shù)f為K×Σ*→K上的映射，且：f（ki，

）=ki第34頁，課件共100頁，創(chuàng)作于2023年2月∑*上的符號串t被DFAM接受M=（K，Σ，f，S，Z）若t

∑*，f(S，t)=P，其中S為M的開始狀態(tài)，PZ，Z為終態(tài)集。則稱t為DFAM所接受（識別）.第35頁，課件共100頁，創(chuàng)作于2023年2月例：證明t=baab被下圖的DFA所接受。f（S，baab）=f（f（S，b），aab）

=f（V，aab）=f（f（V，a），ab）

=f（U，ab）=f（f（U，a），b）

=f（Q，b）=QQ屬于終態(tài)。得證。bSUVQabba,baa第36頁，課件共100頁，創(chuàng)作于2023年2月

DFAM所能接受的符號串的全體記為L(M).對于任何兩個有窮自動機M和M′，如果L(M)=L(M′)，則稱M與M′是等價的.

結(jié)論：

上一個符號串集V

是正規(guī)的，當(dāng)且僅當(dāng)存在一個上的確定有窮自動機M，使得V=L(M)。第37頁，課件共100頁，創(chuàng)作于2023年2月DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:K×Σ→K是一個單值函數(shù)，也就是說，對任何狀態(tài)k∈K，和輸入符號a∈Σ，f(k,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，若字母表Σ含有n個輸入字符，那末任何一個狀態(tài)結(jié)點最多有n條弧射出，而且每條弧以一個不同的輸入字符標(biāo)記。第38頁，課件共100頁，創(chuàng)作于2023年2月DFA的行為很容易用程序來模擬.DFAM=（K，Σ，f，S，Z）的行為的模擬程序K:=S；c:=getchar;whilec<>eofdo{K:=f(K,c);c:=getchar;};ifKisinZthenreturn(‘yes’)elsereturn(‘no’)第39頁，課件共100頁，創(chuàng)作于2023年2月reviewRegularexpressionsonthealphabet?aredefinedbythefollowingrecursiverules:1)Everysymbolof?isaregularexpression2)ε

andfisaregularexpression3)ifr1andr2areregularexpressions,soare(r1)r1r2r1|r2r1*4)Nothingelseisaregularexpression.

?={0,1,2,3,4,5,6,7,8,9}(1|2|3|4|5|6|7|8|9|0)*isaregularexpression(1|2|3|4|...8|9|0)(1|2|3...|8|9|0)*isaregularexpression(1|2|3...|8|9|0)+第40頁，課件共100頁，創(chuàng)作于2023年2月reviewDFAM=（K，Σ，f，S，Z）1)Afinitesetofstates,oneofwhichisdesignatedtheinitialstateorstartstate,andsomeofwhicharedesignatedasfinalstates.2)Analphabetofpossibleinputsymbols.3)Afinitesetoftransitionsthatspecifiesforeachstateandforeachsymboloftheinputalphabet,whichstatetogotonext.第41頁，課件共100頁，創(chuàng)作于2023年2月DFA第42頁，課件共100頁，創(chuàng)作于2023年2月DFA?={digit,notdigit}

第43頁，課件共100頁，創(chuàng)作于2023年2月

DFAM所能接受的符號串的全體記為L(M).對于任何兩個有窮自動機M和M′，如果L(M)=L(M′)，則稱M與M′是等價的.

結(jié)論：

上一個符號串集V

是正規(guī)的，當(dāng)且僅當(dāng)存在一個上的確定有窮自動機M，使得V=L(M)。第44頁，課件共100頁，創(chuàng)作于2023年2月FA等價第45頁，課件共100頁，創(chuàng)作于2023年2月不確定的有窮自動機NFA定義NFAM=K，，f，S，Z，其中K為狀態(tài)的有窮非空集，為有窮輸入字母表，f為K*到K的子集（2K）的一種映射，SK是初始狀態(tài)集，ZK為終止?fàn)顟B(tài)集.第46頁，課件共100頁，創(chuàng)作于2023年2月例子NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）其中f（S，0）={P}f（Z，0）={P}f（P，1）={Z}f（Z，1）={P}f（S，1）={S，Z}第47頁，課件共100頁，創(chuàng)作于2023年2月

狀態(tài)圖表示SPZ00,1111第48頁，課件共100頁，創(chuàng)作于2023年2月矩陣表示矩陣表示簡化為第49頁，課件共100頁，創(chuàng)作于2023年2月f為K*到K的子集（2K）的一種映射具有

轉(zhuǎn)移的不確定的有窮自動機

12

3abc第50頁，課件共100頁，創(chuàng)作于2023年2月有如下定理:

對任何一個具有

轉(zhuǎn)移的不確定的有窮自動機NFA

N，一定存在一個不具有

轉(zhuǎn)移的不確定的有窮自動機NFAＭ，使得L(M)=L(N)。與上例等價的一個NFA.2acbb31acacbb第51頁，課件共100頁，創(chuàng)作于2023年2月類似DFA,對NFAM=K，，f，S，Z也有如下定義∑*上的符號串t在NFAM上運行..一個輸入符號串t，（我們將它表示成Tt1的形式，其中T∈∑，t1∈∑*）在NFAM上運行的定義為：f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K.∑*上的符號串t被NFAM接受若t

∑*，f(S0，t)=P，其中S0∈S，PZ，則稱t為NFAM所接受（識別）第52頁，課件共100頁，創(chuàng)作于2023年2月

∑*上的符號串t被NFAM接受也可以這樣理解

對于Σ﹡中的任何一個串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為ε的弧)等于t，則稱t可為NFAM所識別(讀出或接受)。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均為ε，那么空字可為M所接受。第53頁，課件共100頁，創(chuàng)作于2023年2月00011110100011100000010001100第54頁，課件共100頁，創(chuàng)作于2023年2月

NFAM所能接受的符號串的全體記為L(M)結(jié)論：

上一個符號串集V

是正規(guī)的，當(dāng)且僅當(dāng)存在一個上的不確定的有窮自動機M，使得V=L(M)。第55頁，課件共100頁，創(chuàng)作于2023年2月(0|1)*(000|111)(0|1)第56頁，課件共100頁，創(chuàng)作于2023年2月DFA是NFA的特例.對每個NFA

N一定存在一個DFAＭ，使得L(M)=L(N)。對每個NFAN存在著與之等價的DFAM。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法.與某一NFA等價的DFA不唯一.第57頁，課件共100頁，創(chuàng)作于2023年2月從NFA的矩陣表示中可以看出，表項通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項是一個狀態(tài)，NFA到相應(yīng)的DFA的構(gòu)造的基本思路是：DFA的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài).DFA使用它的狀態(tài)去記錄在NFA讀入一個輸入符號后可能達(dá)到的所有狀態(tài).第58頁，課件共100頁，創(chuàng)作于2023年2月NFA確定化算法:

假設(shè)NFAN=(K,,f,K0,Kt)按如下辦法構(gòu)造一個DFAM=(S,,d,S0,St)，使得L(M)=L(N)：1.M的狀態(tài)集S由K的一些子集組成。用[S1S2...

Sj]表示S的元素，其中S1,S2,,...

Sj是K的狀態(tài)。并且約定，狀態(tài)S1,S2,,...

Sj是按某種規(guī)則排列的，即對于子集{S1,S2}={S2,S1,}來說，S的狀態(tài)就是[S1S2]；第59頁，課件共100頁，創(chuàng)作于2023年2月2M和N的輸入字母表是相同的，即是；3轉(zhuǎn)換函數(shù)是這樣定義的： d([S1S2,...

Sj],a)=[R1R2...

Rt] 其中{R1,R2,...,Rt}=-closure(move({S1,S2,,...

Sj},a))4S0=-closure(K0)為M的開始狀態(tài)；5St={[SiSk...

Se]，其中[Si

Sk...

Se]S且{Si,Sk,,...

Se}Kt

}第60頁，課件共100頁，創(chuàng)作于2023年2月

定義對狀態(tài)集合I的幾個有關(guān)運算：

1.狀態(tài)集合I的ε-閉包，表示為ε-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達(dá)的狀態(tài)的集合。狀態(tài)集合I的任何狀態(tài)S都屬于ε-closure(I)。2.狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。第61頁，課件共100頁，創(chuàng)作于2023年2月狀態(tài)集合I的有關(guān)運算的例子I={1},-closure(I)={1,2}；I={5},-closure(I)={5,6,2}；move({1,2},a)={5,3,4}-closure({5,3,4})={2,3,4,5,6,7,8}；12534687aa

a第62頁，課件共100頁，創(chuàng)作于2023年2月構(gòu)造NFAN的狀態(tài)K的子集的算法：假定所構(gòu)造的子集族為C，即C=(T1,T2,,...

TI),其中T1,T2,,...

TI為狀態(tài)K的子集。1開始，令-closure(K0)為C中唯一成員，并且它是未被標(biāo)記的。第63頁，課件共100頁，創(chuàng)作于2023年2月2while（C中存在尚未被標(biāo)記的子集T）do { 標(biāo)記T； for每個輸入字母ado { U:=-closure(move(T,a))； ifU不在C中then 將U作為未標(biāo)記的子集加在C中 } }第64頁，課件共100頁，創(chuàng)作于2023年2月NFA的確定化例子4f35621i

aaaabbbb第65頁，課件共100頁，創(chuàng)作于2023年2月4f35621i

aaaabbbb第66頁，課件共100頁，創(chuàng)作于2023年2月

等價的DFAaCDBAEFSbaaaaabbbbbabF第67頁，課件共100頁，創(chuàng)作于2023年2月確定有窮自動機的化簡

說一個有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有窮自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有窮自動機。所謂有窮自動機的多余狀態(tài)，是指這樣的狀態(tài)：從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達(dá)終態(tài)。

第68頁，課件共100頁，創(chuàng)作于2023年2月DFA的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別）兩個狀態(tài)s和t可區(qū)別：不滿足兼容性——同是終態(tài)或同是非終態(tài)傳播性——從s出發(fā)讀入某個aa和從 t出發(fā)讀入某個a到達(dá)的狀態(tài)等價。第69頁，課件共100頁，創(chuàng)作于2023年2月

C和D同是終態(tài),讀入a到達(dá)C和F,C和F同是終態(tài),C和F讀入a都到達(dá)C,讀入b都到達(dá)E.C和D等價aCDBAEFSbaaaaabbbbbabF第70頁，課件共100頁，創(chuàng)作于2023年2月最小狀態(tài)DFA對于一個DFAM=（K,∑,f,k0,,kt)，存在一個最小狀態(tài)DFAM’=（K’,∑,f’,k0’,,kt’)，,使L(M’)=L(M).結(jié)論接受L的最小狀態(tài)有窮自動機不計同構(gòu)是唯一的。第71頁，課件共100頁，創(chuàng)作于2023年2月“分割法”DFA的最小化算法的核心把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的.

算法假定每個狀態(tài)射出的弧都是完全的,否則,引入一個新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己.第72頁，課件共100頁，創(chuàng)作于2023年2月

DFA的最小化算法DFAM=（K,∑,f,k0,,kt),最小狀態(tài)DFAM’

1.構(gòu)造狀態(tài)的一初始劃分：終態(tài)kt

和非終態(tài)K-kt兩組(group)2.對∏施用過程PP

構(gòu)造新劃分∏new

3.如∏new=∏,則令∏final=∏并繼續(xù)步驟4，否則∏:=∏new重復(fù)2.4.為∏final中的每一組選一代表，這些代表構(gòu)成M’的狀態(tài)。若k是一代表且f(k,a)=t,令r是t組的代表，則M’中有一轉(zhuǎn)換f’(k,a)=r第73頁，課件共100頁，創(chuàng)作于2023年2月M’的開始狀態(tài)是含有S0的那組的代表M’的終態(tài)是含有F的那組的代表5.去掉M’中的死狀態(tài).第74頁，課件共100頁，創(chuàng)作于2023年2月過程PP

:Constructionof∏newForeachgroupGof∏dobegin

1.PartitonGintosubgroupssuchthattwostatessandtofGareinthesamesubgroupsifandonlyifforallinputsymbolsa,statessandthavetransitionsonatostatesinthesamegroupof∏;/*atworst,astatewillbeinasubgroupbyitself*/2.replaceGin∏newbythesetofallsubgroupsformed

end

第75頁，課件共100頁，創(chuàng)作于2023年2月

DFA的最小化—例子∏0:{S,A,B}{C,D,E,F}∏1:{S,A,B} {C,D,E,F} ∏2:CDBAEFSbaaaaaabbbbbba}{}{AS,BbB{{S}}DBASaaabbbbaa第76頁，課件共100頁，創(chuàng)作于2023年2月3.4詞法分析程序的自動構(gòu)造對有窮自動機和正規(guī)表達(dá)式進(jìn)行了上述討論之后,我們介紹詞法分析程序的自動構(gòu)造方法,這個方法基于有窮自動機和正規(guī)表達(dá)式的等價性,即：

1.對于∑上的一個NFAM，可以構(gòu)造一個∑上的正規(guī)式R,使得L(R)=L(M)。2.對于∑上的一個正規(guī)式R，可以構(gòu)造一個∑上的NFAM，使的L(M)=L(R)。第77頁，課件共100頁，創(chuàng)作于2023年2月從Σ上的一個正規(guī)式R構(gòu)造Σ上的一個NFAM，使得L(M)=L(R)的方法。“語法制導(dǎo)”的方法，即按正規(guī)式的語法結(jié)構(gòu)指引構(gòu)造過程，構(gòu)造規(guī)則具體描述如下：第78頁，課件共100頁，創(chuàng)作于2023年2月.“對于∑上的一個正規(guī)式R,可以構(gòu)造一個∑上的NFAM，，使得L(M)=L(R).”說明一種構(gòu)造方法：(1)R=,構(gòu)造任一具有空終態(tài)集的NFAM

(2）R=

，構(gòu)造的NFAM=({k0},∑,f,k0.{k0}):f（k0,a)對于所有a∑都沒定義。(3）R=a,構(gòu)造的NFAM=({k0,,k1},∑,f,k0.{k1}):f(k0,a)=k1(4)R=R1|R2,將步驟（1）（2）（3）分別應(yīng)用到R1,R2

產(chǎn)生M1==(K1,∑,f1,k1,F1),M2=(K2,∑,f2,k2,F2),其中K1,K2不相交.構(gòu)造的NFAM=(K1K2{k},∑,f,k,F):k是新增加的狀態(tài)符號，f包含f1和f2,且f(k,a)=f1(k1,a)f2(k2,a).若k1F1且k2F2則F=F1F2，否則F=F1F2{k}第79頁，課件共100頁，創(chuàng)作于2023年2月(5)R=R1.R2

將步驟（1）（2）（3）分別應(yīng)用到R1,R2

產(chǎn)生M1==(K1,∑,f1,k1,F1),M2=(K2,∑,f2,k2,F2),其中K1,K2不相交.構(gòu)造的NFAM=(K1K2,∑,f,k1,F2):f包含f1和f2,且f(k,a)=f1(k,a),當(dāng)kF1時;

f(k,a)=f2(k,a),當(dāng)k∈K2時;f(k1,

)=k2,(6)R=R1*將步驟（1）（2）（3）分別應(yīng)用到R1,產(chǎn)生M1==(K1,∑,f1,k1,F1),

構(gòu)造的NFAM=(K1{k0,F0},∑,f,k0,F0)其中k0,F0

是新增加的兩個狀態(tài),f(k,a)=f1(k,a),當(dāng)kF1時;

f(k0,

)=f(F1,

)={k1,,F0},,第80頁，課件共100頁，創(chuàng)作于2023年2月再用狀態(tài)圖說明可用方法對于正規(guī)式x,x

∑構(gòu)造的NFA（兩種）X第81頁，課件共100頁，創(chuàng)作于2023年2月對于正規(guī)式

,構(gòu)造的NFA（三種）

FS

F第82頁，課件共100頁，創(chuàng)作于2023年2月對于正規(guī)式R=

,構(gòu)造的NFA

FS第83頁，課件共100頁，創(chuàng)作于2023年2月對于正規(guī)式r,r=R1|R2構(gòu)造的NFA第84頁，課件共100頁，創(chuàng)作于2023年2月對于正規(guī)式r,r=R1R2構(gòu)造的NFA第85頁，課件共100頁，創(chuàng)作于2023年2月對于正規(guī)式r,r=R1*構(gòu)造的NFA第86頁，課件共100頁，創(chuàng)作于2023年2月R=(a|ab)*bb*第87頁，課件共100頁，創(chuàng)作于2023年2月

正規(guī)式用于說明(描述)單詞的結(jié)構(gòu)十分簡潔方便。而把一個正規(guī)式編譯(或稱轉(zhuǎn)換)為一個NFA進(jìn)而轉(zhuǎn)換為相應(yīng)的DFA，這個NFA或DFA正是識別該正規(guī)式所表示的語言的句子的識別器。基于這種方法來構(gòu)造詞法分析程序第88頁，課件共100頁，創(chuàng)作于2023年2月詞法分析程序的設(shè)計技術(shù)可