《編譯原理》第3章-詞法分析與有窮自動(dòng)機(jī)

S.PO.P語義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理第3章詞法分析本章介紹編譯第一個(gè)階段詞法分析的設(shè)計(jì)原理和設(shè)計(jì)方法，要求明確此階段的任務(wù)。理解通常的單詞分類和構(gòu)詞規(guī)那么。會(huì)使用單詞的描述和識(shí)別機(jī)制。要求掌握正規(guī)文法、狀態(tài)圖、DFA、NFA、正規(guī)式和正規(guī)集的根本概念和它們之間的關(guān)系。掌握詞法分析程序的手工實(shí)現(xiàn)方法。掌握詞法分析程序的自動(dòng)構(gòu)造原理。教學(xué)目標(biāo)3.1詞法分析的任務(wù)3.2詞法分析程序的輸出形式3.3詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)3.4正規(guī)式與有窮自動(dòng)機(jī)3.5詞法分析程序的自動(dòng)生成工具LEX3.6PL/0編譯程序的詞法分析教學(xué)內(nèi)容〔1〕分析和識(shí)別單詞及屬性，包括識(shí)別語言的關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符等；〔2〕跳過各種分隔符，如空格，回車，制表符等；〔3〕刪除注釋；〔4〕進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤；〔5〕建立符號(hào)表。3.1詞法分析的任務(wù)main()/*ADD*/{intx=10,y=20,sum;sum=x+y;}main、(、)、{、int、x、=、10、,、y、=、20、,、sum、;、sum、=、x、+、y、;、}詞法分析實(shí)現(xiàn)方案：根本上有兩種1.詞法分析單獨(dú)作為一遍2.詞法分析程序作為單獨(dú)的子程序S.P.(字符串)詞法分析S.P.(符號(hào)串)語法分析第一遍第二遍單詞串優(yōu)點(diǎn):結(jié)構(gòu)清晰、各遍功能單一缺點(diǎn)：效率低S.P.(字符串)詞法分析程序語法分析程序取單詞單詞單詞的種類〔1〕關(guān)鍵字：if、for、while〔2〕標(biāo)識(shí)符：〔3〕常數(shù)：〔4〕運(yùn)算符：+、-、*〔5〕分界符：,、;、(、)3.2詞法分析程序的輸出形式詞法分析程序的輸出形式-----二元式單詞類別單詞的屬性值單詞類別可以用整數(shù)編碼表示:一類一種或一字一種單詞類別關(guān)鍵字標(biāo)識(shí)符常數(shù)運(yùn)算符分界符編碼123453.3詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)詞法規(guī)則狀態(tài)圖詞法分析程序結(jié)點(diǎn)代表狀態(tài)，用圓圈表示，為非終結(jié)符有向弧表示狀態(tài)轉(zhuǎn)移弧上的標(biāo)記表示在射出弧的結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的輸入字符，為終結(jié)符

1.狀態(tài)圖：為識(shí)別單詞而專門設(shè)計(jì)的有向圖，是設(shè)計(jì)詞法分析程序的一種好途徑。SUVZ111000一張狀態(tài)圖包含有窮個(gè)狀態(tài)，只能有一個(gè)初態(tài)，至少要有一個(gè)終態(tài)〔用雙圈表示〕3.3.1正規(guī)文法及其狀態(tài)圖【例3.1】某語言的標(biāo)識(shí)符可使用以下正規(guī)文法G[S]來定義：S→lAA→ε|lA|dAl∈{a,b,…z}，d∈{1,2,…,9}試構(gòu)造此文法的狀態(tài)圖。SAll|d狀態(tài)圖可識(shí)別單詞2.由正規(guī)文法構(gòu)造狀態(tài)圖〔1〕對(duì)于右線性文法步驟1增加結(jié)點(diǎn)Z為終態(tài)；步驟2將每個(gè)非終結(jié)符號(hào)設(shè)置為一個(gè)對(duì)應(yīng)的狀態(tài)；步驟3對(duì)于A→a，引一條從A到Z的弧，弧上標(biāo)記為a；而對(duì)于A→aB，引一條從A到B的弧，弧上標(biāo)記為a。S→lAA→ε|lA|dAl|dAZεSlAZll|d〔2〕對(duì)于左線性文法步驟1增加結(jié)點(diǎn)S為初態(tài)；步驟2將每個(gè)非終結(jié)符號(hào)設(shè)置為一個(gè)對(duì)應(yīng)的狀態(tài)；步驟3對(duì)于A→a，引一條從S到A的弧，弧上標(biāo)記為a；而對(duì)于A→Ba，引一條從B到A的弧，弧上標(biāo)記為a。A→l|Al|Adl|dASlS→lAA→ε|lA|dA詞法規(guī)則狀態(tài)圖詞法分析程序3.3.2詞法分析程序的實(shí)現(xiàn)〔1〕根據(jù)詞法規(guī)那么寫出正規(guī)文法；〔2〕將正規(guī)文法轉(zhuǎn)換成狀態(tài)圖；〔3〕將狀態(tài)圖轉(zhuǎn)換成流程圖。 標(biāo)識(shí)符 關(guān)鍵字(標(biāo)識(shí)符的子集〕 常數(shù) 運(yùn)算符+*＝<<= 分界符,;【例3.2】假設(shè)某種語言的單詞符號(hào)的子集有：試構(gòu)造此語言子集的詞法分析程序。〔1〕根據(jù)詞法規(guī)那么寫出正規(guī)文法<標(biāo)識(shí)符>→字母|<標(biāo)識(shí)符>字母|<標(biāo)識(shí)符>數(shù)字〕<無符號(hào)整數(shù)>→數(shù)字|<無符號(hào)整數(shù)>數(shù)字<單界符>→+|*|<|,|;<雙界符>→<=標(biāo)識(shí)符出口S1非字母數(shù)字字母字母、數(shù)字無符號(hào)整數(shù)出口S2非數(shù)字?jǐn)?shù)字?jǐn)?shù)字單字符分界符出口S3其他字符+*=,;雙字符分界符出口S4其他字符<5=非=<標(biāo)識(shí)符>→字母|<標(biāo)識(shí)符>字母|<標(biāo)識(shí)符>數(shù)字〕<無符號(hào)整數(shù)>→數(shù)字|<無符號(hào)整數(shù)>數(shù)字<單界符>→+|*|<|,|;<雙界符>→<=〔2〕將正規(guī)文法轉(zhuǎn)換成狀態(tài)圖合并①將初始狀態(tài)合并為一個(gè)唯一的初態(tài)；②化簡調(diào)整狀態(tài)沖突并對(duì)沖突狀態(tài)重新編號(hào)；③如有必要，增加出錯(cuò)狀態(tài)。標(biāo)識(shí)符無符號(hào)整數(shù)單界符雙界符S1非字母數(shù)字字母字母、數(shù)字2非數(shù)字?jǐn)?shù)字?jǐn)?shù)字3其他字符+*，（）出口4其他字符<5=非=出錯(cuò)其他讀字符查保留字表返回S合并后的狀態(tài)圖〔3〕將狀態(tài)圖轉(zhuǎn)換成流程圖，如圖3.5寫出詞法分析程序012其他a013a110012b如：aba#如：bba#

c=nextchar();if(c==‘a(chǎn)’){

c=nextchar();

while(c==‘a(chǎn)’或者c==‘b’)

c=nextchar();接受；}else出錯(cuò)或其他情況；3.5字母表

,定義在上的正規(guī)式和正規(guī)集遞歸定義如下:1.

和都是上的正規(guī)式,它們所表示的正規(guī)集分別為:{}和;2.任何a,a是上的正規(guī)式,它所表示的正規(guī)集為:{a};3.假定U和V上的正規(guī)式,它們所表示的正規(guī)集分別記為L(e1)

和L(e2),那么e1|e2,e1?e2和e1*也都是上的正規(guī)式,它們所表示的正規(guī)集分別為L(e1)L(e2)、L(e1)?L(e2)和(L(e1))*4.任何上的正規(guī)式和正規(guī)集均由1、2和3產(chǎn)生。3.4正規(guī)表達(dá)式與有窮自動(dòng)機(jī)3.4.1正規(guī)式與正規(guī)集正規(guī)式中的運(yùn)算符：|-----或〔選擇〕?----連接 *或{}---重復(fù)〔〕----括號(hào)運(yùn)算符的優(yōu)先級(jí)：先*,后?,最后|

?在正規(guī)式中可以省略.正規(guī)式相等這兩個(gè)正規(guī)式表示的語言相等【例3.3】設(shè)Σ={a,b}正規(guī)式正規(guī)集ba*所有以b為首后跟任意多個(gè)a的符號(hào)串a(chǎn)(a|b)*所有以a為首的符號(hào)串(a|b)*abb所有以abb為尾的a，b符號(hào)串(a|b)*(aa|bb)(a|b)*所有含有兩個(gè)相繼的a或相繼的b的符號(hào)串(aa|ab|ba|bb)*空串和任何長度為偶數(shù)的符號(hào)串(a|b)(a|b)(a|b)*任何長度大于等于2的符號(hào)串【例3.3】使用正規(guī)式來表例如3.2中的相應(yīng)單詞符號(hào)。<標(biāo)識(shí)符>→字母|<標(biāo)識(shí)符>字母|<標(biāo)識(shí)符>數(shù)字〕<無符號(hào)整數(shù)>→數(shù)字|<無符號(hào)整數(shù)>數(shù)字<單界符>→+|*|<|,|;<雙界符>→<=標(biāo)識(shí)符：l(l|d)*無符號(hào)整數(shù)：dd*單界符：+|*|<|,|;雙界符：<=設(shè)r，s，t均是正規(guī)式，那么有以下性質(zhì)：〔1〕交換律：r|s=s|r〔2〕結(jié)合律：r|(s|t)=(r|s)|t(rs)t=r(st)〔3〕分配律：(r|s)t=rt|st〔4〕同一律：εr=rε=r1.正規(guī)文法正規(guī)式規(guī)則1規(guī)則2規(guī)則3文法產(chǎn)生式正規(guī)式A→xB,B→yA→xA|yA→x,A→yA=xyA=x*yA=x|y步驟1將每條產(chǎn)生式改寫為正規(guī)式；步驟2用代入法解正規(guī)式方程組，最后只剩下一個(gè)開始符號(hào)定義的正規(guī)式，其中不含非終結(jié)符。3.4.2正規(guī)文法與正規(guī)式【例3.5】G[S]:S→aA|aA→dA|d規(guī)則1規(guī)則2規(guī)則3文法產(chǎn)生式正規(guī)式A→xB,B→yA→xA|yA→x,A→yA=xyA=x*yA=x|yS=aA|aA=d*d代入:S=ad*d|a＝ad*2.正規(guī)式正規(guī)文法步驟1構(gòu)造S→r步驟2不斷利用表3.4的規(guī)那么做變換,直到每個(gè)產(chǎn)生式最多含有一個(gè)終結(jié)符為止規(guī)則1規(guī)則2規(guī)則3文法產(chǎn)生式正規(guī)式A→xB,B→yA→xA|yA→x,A→yA=xyA=x*yA=x|y【例3.6】求正規(guī)式(a|b)(a|b|0|1)*對(duì)應(yīng)的正規(guī)文法S→(a|b)(a|b|0|1)*S→(a|b)ＡA→aA|bA|0A|1A|εG[S]：S→aA|bAA→aA|bA|0A|1A|εA→(a|b|0|1)*下面是用正規(guī)式表示的變量聲明：

(int|float)id(,id)*

請(qǐng)改用上下文無關(guān)文法表示，也就是寫一個(gè)上下文無關(guān)文法，它和該正規(guī)式等價(jià)。(int|float)id(,id)*D→(int|float)LL→id(,id)*D→intL|floatLL→L,id|idG[D]：D→intL|floatLL→L,id|id3.4.3有窮自動(dòng)機(jī)標(biāo)識(shí)符無符號(hào)整數(shù)單界符雙界符S1非字母數(shù)字字母字母、數(shù)字2非數(shù)字?jǐn)?shù)字?jǐn)?shù)字3其他字符+*，（）出口4其他字符<5=非=出錯(cuò)其他讀字符查保留字表返回S狀態(tài)圖的形式化描述有窮自動(dòng)機(jī)是一種數(shù)學(xué)模型，具有離散的輸入與輸出，系統(tǒng)可處于有窮狀態(tài)中的任何一個(gè)它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)文法所定義的語言和正規(guī)式所表示的集合引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)〔DFA〕(DeterministicFiniteAutomata)不確定的有窮自動(dòng)機(jī)〔NFA〕(NondeterministicFiniteAutomata)2型文法（不確定的下推自動(dòng)機(jī)）1型文法（不確定的界限自動(dòng)機(jī)）0型文法（圖靈機(jī)）3型文法（有限自動(dòng)機(jī)）1.確定的有窮自動(dòng)機(jī)〔DFA〕 M=(Σ,Q,f,S,Z)Σ：有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)Q：有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)S∈K，是唯一的初態(tài)ZK是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)f是轉(zhuǎn)換函數(shù)，是Q×Σ→Q上的單值映射：f〔q1，a〕=q2狀態(tài)轉(zhuǎn)移函數(shù)f可用一矩陣來表示：輸入字符狀態(tài)ab012132213333例如:M:〔{0,1,2,3},{a,b},f，0，{3}〕f〔0，a〕=1f〔0，b〕=2f〔1，a〕=3f〔1，b〕=2f〔2，a〕=1f〔2，b〕=3f〔3，a〕=3f〔3，b〕=3所謂確定的狀態(tài)機(jī)，其確定性表現(xiàn)在狀態(tài)轉(zhuǎn)移函數(shù)是單值函數(shù)！字母表Σ含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。M=(Σ,Q,f,S,Z)

一個(gè)DFA也可以用一狀態(tài)轉(zhuǎn)換圖表示：

輸入字符狀態(tài)ab012132213333DFA的狀態(tài)圖表示：1032aabba,bba字母表Σ含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。換言之：假設(shè)存在一條初始狀態(tài)到某一終止?fàn)顟B(tài)的路徑，且這條路徑上所有弧的標(biāo)記符號(hào)連接成符號(hào)串α，那么稱α為DFAM〔接受〕識(shí)別。DFAM所接受的語言為：L(M)={α|f(S,α)=Sn,Sn∈Z}DFAM所能接受的符號(hào)串的全體記為L(M)假設(shè)M的初態(tài)結(jié)點(diǎn)同時(shí)為終態(tài)，或者存在一條從初態(tài)到某個(gè)終態(tài)結(jié)點(diǎn)的ε通路，那么ε為M所識(shí)別。δ〔0，abaab〕=δ〔1，baab〕=δ〔2，aab〕=δ〔1，ab〕=δ〔3，b〕=3(接受)DFA的狀態(tài)圖表示：1032aabba,bbaδ〔0，abab〕=δ〔1，bab〕=δ〔2，ab〕=δ〔1，b〕=2(拒絕)對(duì)于符號(hào)串a(chǎn)baab對(duì)于符號(hào)串a(chǎn)babf是一個(gè)多值函數(shù)，是從Q×Σ*到Q的子集的映射：f：Q×Σ→Q’其中Q’是Q的冪集，即Q中所有子集組成的集合。2.不確定的有窮自動(dòng)機(jī)〔NFA〕 M=(Σ,Q,f,S,Z)有窮自動(dòng)機(jī)的不確定性表現(xiàn)在在某個(gè)狀態(tài)下，對(duì)于某個(gè)輸入字符存在多個(gè)后繼狀態(tài)，即狀態(tài)的轉(zhuǎn)向是不確定的例：NFAN=({a,b,c},{1,2,3,4},f,{1},{4})

符號(hào)狀態(tài)εabc1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦ對(duì)于Σ*上的任何符號(hào)串，假設(shè)存在一條從某一初態(tài)到某一終態(tài)的通路，且該通路上所有弧的標(biāo)記字符依次連接成的串等于，那么稱可以被NFAN所識(shí)別或接受。假設(shè)N的初態(tài)結(jié)點(diǎn)同時(shí)為終態(tài)，或者存在一條從初態(tài)到某個(gè)終態(tài)結(jié)點(diǎn)的通路，那么為N所識(shí)別。NFAN所能識(shí)別的符號(hào)串的全體記為L(N)，稱為NFAN所識(shí)別的語言

上例題相應(yīng)的狀態(tài)圖為：

1234abacacεN所接受的語言〔正規(guī)式〕R=aa*b|ac*c|ε

符號(hào)狀態(tài)εabc

1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦ能接受0001111010001110000001(0|1)*(000|111)(0|1)*不能接受0001100畫出能夠識(shí)別C語言注釋/**/的DFA12453othersothers/***/6othersothersallall12453othersothers/***/狀態(tài)1：注釋開始狀態(tài)。 狀態(tài)2：進(jìn)入注釋體前的中間狀態(tài)。 狀態(tài)3：說明目前正在注釋體中的狀態(tài)。 狀態(tài)4：離開注釋前的中間狀態(tài)。 狀態(tài)5：注釋結(jié)束狀態(tài)，即接受狀態(tài)。用于某些重要軟件的設(shè)計(jì)和構(gòu)造設(shè)計(jì)和檢查數(shù)字電路行為的軟件;掃描如網(wǎng)頁族等大規(guī)模文本以發(fā)現(xiàn)字、詞或其它結(jié)構(gòu)的出現(xiàn)頻率的軟件;驗(yàn)證所有只有有限多個(gè)不同狀態(tài)的系統(tǒng)的軟件，這類系統(tǒng)包括通信協(xié)議和信息平安交換協(xié)議。有窮自動(dòng)機(jī)的其它應(yīng)用閱讀兩篇論文基于協(xié)議分析狀態(tài)機(jī)的入侵檢測系統(tǒng)有限自動(dòng)機(jī)在BBS信息監(jiān)測系統(tǒng)中的運(yùn)用

已證明：非確定的有窮自動(dòng)機(jī)與確定的有窮自動(dòng)機(jī)從功能上來說是等價(jià)的，也就是說，我們能夠從：NFANDFAM構(gòu)造成一個(gè)使得L(M)=L(N)DFA是NFA的特例。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.

已證明：非確定的有窮自動(dòng)機(jī)與確定的有窮自動(dòng)機(jī)從功能上來說是等價(jià)的，也就是說，我們能夠從：NFAM’DFAM構(gòu)造成一個(gè)使得L(M)=L(M’)DFA是NFA的特例。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法.與某一NFA等價(jià)的DFA不唯一3.NFA確實(shí)定化從NFA的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)。NFA到相應(yīng)的DFA的構(gòu)造的根本思路是：DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài).

符號(hào)狀態(tài)εabc

1{4}{2，3}ΦΦ2Φ{2}{4}Φ3ΦΦΦ{3，4}4ΦΦΦΦ1234abacacε(1)ε合并 如果有，那么把S2合并到S1S1S2ε轉(zhuǎn)換需解決的問題：ijkmεaban（a）i,jmkaabn（b）(2)狀態(tài)合并0123aabc（a）01,23abc（b）定義1狀態(tài)集合I的

-閉包，表示為

-closure(I)①假設(shè)q∈I，那么q∈-closure(I)；②假設(shè)q∈I，那么從q出發(fā)經(jīng)過任意條弧而能到達(dá)的任何狀態(tài)q'都屬于-closure(I)。為了使得NFA確定化，我們首先給出兩個(gè)定義：ε_(tái)closure(I)εεεIIS2S2S1S1S3S3例：如下圖的狀態(tài)圖：令I(lǐng)={1}，求ε-closure〔I〕=？156432aεaaε根據(jù)定義：ε-closure〔I〕={1，3}課堂練習(xí)：令I(lǐng)={1,2}，求ε-closure〔I〕=？I是狀態(tài)集，由I中的狀態(tài)出發(fā)，經(jīng)過一條a弧可能到達(dá)的狀態(tài)的集合稱為move〔I，a〕，那么Ia=ε_(tái)closure(move(I,a))定義2Ia

子集例：令I(lǐng)={1}Ia=ε-closure(move〔I，a〕)=ε-closure(f〔1，a〕〕=ε-closure({2，4}〕={2，4，6}根據(jù)定義1，2，可以將上述的M’確定化〔即可構(gòu)造出狀態(tài)轉(zhuǎn)換矩陣〕156432aεaaε課堂練習(xí)：令I(lǐng)={1,2,3}求Ia=？課堂練習(xí)：令I(lǐng)={1}，設(shè)S'=ε-closure〔I〕，求S'＝？S'a=？將從狀態(tài)S出發(fā)經(jīng)過任意條

弧所能到達(dá)的狀態(tài)作為DFA的初態(tài)S'從S'出發(fā)，把遇到輸入符號(hào)a所轉(zhuǎn)移到的后繼狀態(tài)集作為DFA的新狀態(tài)如此重復(fù)，直到不再有新的狀態(tài)出現(xiàn)為止

NFA轉(zhuǎn)換為DFA的思想1234abacacε

IIaIbIc

{1,4}{2,3}φφ

{2,3}{2}{4}{3,4}

{2}{2}{4}φ

{4}φφφ

{3,4}φφ{(diào)3,4}

〔1〕構(gòu)造一張表，它共有｜Σ｜+1列〔2〕第一行第一列為-closure({S})〔3〕求Ia〔4〕重復(fù)步驟〔3〕〔5〕將狀態(tài)子集重新命名1234abacacε將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號(hào)DFAM狀態(tài)轉(zhuǎn)換矩陣：

符號(hào)狀態(tài)abc02341221________3344DFAM的狀態(tài)圖：

注意：包含原初始狀態(tài)1的狀態(tài)子集為DFAM的初態(tài)包含原終止?fàn)顟B(tài)4的狀態(tài)子集為DFAM的終態(tài)。01423{1,4}{2,3}{4}{2}acabbc{3,4}1234abacacε課堂練習(xí)4f35621i

aaaabbbbstart

等價(jià)的DFAaCDBAEFSbaaaaabbbbbabFstart4.DFA的最小化如果不同的DFA能識(shí)別相同的語言，那么稱它們是等價(jià)的DFA。在等價(jià)的DFA中，如果某一個(gè)DFA的狀態(tài)數(shù)是最少的，那么這個(gè)DFA是最簡的。對(duì)于任一個(gè)DFA，存在一個(gè)唯一的狀態(tài)最少的等價(jià)的DFA最簡的DFA

它沒有多余狀態(tài)和等價(jià)狀態(tài)定義1多余狀態(tài)：從開始狀態(tài)出發(fā),任何輸入串也不能到達(dá)的狀態(tài)01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s101s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s6例:畫狀態(tài)圖可以看出s4,s6,s8為不可達(dá)狀態(tài)應(yīng)該消除定義2等價(jià)狀態(tài)狀態(tài)s和t的等價(jià)條件是:①狀態(tài)S和T必須同時(shí)為終態(tài)或非終態(tài)②對(duì)于所有輸入符號(hào)，S和T必須轉(zhuǎn)換到等價(jià)的狀態(tài)里把DFA的狀態(tài)劃分成一些不相交的子集任何不同的兩個(gè)子集的狀態(tài)都是可區(qū)分的同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的5724361srartaaaaaaabbbbbbbDFA最小化算法的根本思想(沒有多余狀態(tài))：解:(一)區(qū)分終態(tài)與非終態(tài)12345663731546737414212ab區(qū)號(hào)123123456637315467374142ab區(qū)號(hào)〔1〕將所有狀態(tài)分成兩個(gè)子集：終態(tài)集和非終態(tài)集〔2〕把等價(jià)的狀態(tài)構(gòu)成一個(gè)子集，假設(shè)不等價(jià)繼續(xù)劃分〔3〕結(jié)束后，重新標(biāo)號(hào)或從每個(gè)子集中選一個(gè)狀態(tài)做代表123456637315467374142ab12431243123456637315467374142ab5區(qū)號(hào)區(qū)號(hào)將區(qū)號(hào)代替狀態(tài)號(hào)得:12345ab5214355231155243aaaaabbbbb化簡后的有窮自動(dòng)機(jī)具有較少的狀態(tài)，實(shí)現(xiàn)起來更加簡潔。3.4.4正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性〔1〕對(duì)于字母表Σ上的NFAM，可以構(gòu)造一個(gè)Σ上的正規(guī)式R，使得L(R)=L(M)；〔2〕對(duì)于字母表Σ上的每個(gè)正規(guī)式R，可以構(gòu)造一個(gè)Σ上的NFAM，使得L(M)=L(R)。1.NFAM

正規(guī)式R(1)在M上加兩個(gè)結(jié)點(diǎn)S,Z，從S結(jié)點(diǎn)用ε弧到M的所有初態(tài)，從M的所有終態(tài)用ε到Z結(jié)成與M等價(jià)的M’，M’只有一個(gè)初態(tài)S和一個(gè)終態(tài)Z.例:M:03214starta,ba,ba,bbbaa解:(1)加SZS03412Zεεεaa,ba,ba,babb(2)逐步消去M’中的所有結(jié)點(diǎn),直至剩下S和Z結(jié)點(diǎn),在消結(jié)過程中,逐步用正規(guī)式來標(biāo)記弧,規(guī)則如下:

1.對(duì)于代之為

2.對(duì)于代之為

3.對(duì)于代之為R1R212331R1R21221R2R1R2R1|R1R312331R1R2﹡R3R2(2)消除M中的所有結(jié)點(diǎn)a|bx024yεεεaabba|ba|bx0yaa(a|b)*bb(a|b)*a|bε解:(1)加xyx03412yεεεaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*2.正規(guī)式RNFAM〔1〕對(duì)NFAM構(gòu)造一個(gè)廣義的狀態(tài)圖，其中只有一個(gè)初態(tài)S和終態(tài)Z，連接S和Z的有向弧標(biāo)記為正規(guī)式。〔2〕對(duì)正規(guī)式依次進(jìn)行分解，分解的過程是一個(gè)不斷參加結(jié)點(diǎn)和弧的過程，直到轉(zhuǎn)換圖上的所有弧標(biāo)記上都是字母表Σ上的元素或?yàn)橹?。假設(shè)s,t為Σ上的正規(guī)式(a)對(duì)于正規(guī)式R=stxystxystt(b)對(duì)于正規(guī)式R=s|txys|txyst(c)對(duì)于正規(guī)式R=rs*txyrs*txyrtts

AZS(a|b)*abb

例:為R=(a|b)abb構(gòu)造NFA,使得L(N)=L(R)*

SZbabABba

ZbbSa|bAa3.4.5正規(guī)文法與有窮自動(dòng)機(jī)的等價(jià)性〔1〕對(duì)于NFAM，存在一個(gè)右線性文法〔左線性文法〕G，使得L(G)=L(M)；〔2〕對(duì)于右線性文法〔左線性文法〕G，可以構(gòu)造一個(gè)NFAM，使得L(M)=L(G)。1.NFA

正規(guī)文法〔1〕NFA的字母表為文法的終結(jié)符號(hào)集；〔2〕NFA的狀態(tài)集為文法的非終結(jié)符號(hào)集；〔3〕NFA的初態(tài)對(duì)應(yīng)于文法的開始符號(hào)；〔4〕NFA的轉(zhuǎn)換函數(shù)f(A,t)=B，寫成一個(gè)產(chǎn)生式A→tB；〔5〕對(duì)NFA的終態(tài)Z，增加一個(gè)產(chǎn)生式Z→。ABt例:給出如圖NFA等價(jià)的正規(guī)文法GABCDaaabbbbG=（{A，B，C，D}，{a，b}，P，A）其中P:AaBAbDBbCCaACbDCεDaBDbDDε→→→→→→→→→〔1〕文法的終結(jié)符號(hào)集為NFA的字母表；〔2〕文法的非終結(jié)符號(hào)集為NFA的狀態(tài)集；〔3〕文法的開始符號(hào)作為NFA的初態(tài)；〔4〕對(duì)文法中形如A→tB的產(chǎn)生式，其中t為終結(jié)符或，A和B為非終結(jié)符，構(gòu)造NFA的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=B；〔5〕對(duì)文法中形如A→t的產(chǎn)生式，構(gòu)造NFA的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=Z。2.正規(guī)文法NFA例:求與文法G[S]等價(jià)的NFAG[S]:S→aA|bB|εA→aB|bAB→aS|bA|εSZABaaabbbεε求得：正規(guī)文法NFA正規(guī)式654312DFA最小化轉(zhuǎn)換方法87判斷題1．對(duì)任意一個(gè)右線性文法G，都存在一個(gè)NFAM，滿足L(G)=L(M).2．對(duì)任意一個(gè)右線性文法G，都存在一個(gè)DFAM，滿足L(G)=L(M).3．對(duì)任何正規(guī)表達(dá)式e，都存在一個(gè)NFAM，滿足L(M)=L(e).4．對(duì)任何正規(guī)表達(dá)式e，都存在一個(gè)DFAM，滿足L(M)=L(e).LEX源程序LEX編譯器C程序3.5詞法分析程序的自動(dòng)生成工具—LEXC程序C編譯器詞法分析程序輸入流詞法分析程序單詞序列3.5.1LEX的源程序一個(gè)LEX源程序主要由三個(gè)局部組成說明局部－－可選%%－－必須有識(shí)別規(guī)那么－－必須有〔LEX的核心〕%%－－可選輔助過程－－可選1、說明局部:變量、常量說明和正規(guī)式定義正規(guī)式定義格式如下：D1R1

D2R2∶∶DnRn

其中：

R1,R2，……，Rn

為正規(guī)式

D1,D2，……，Dn為正規(guī)式名字

例：標(biāo)識(shí)符：

digit[0-9]letter[A-Za-z]id({letter}|[_])({letter}|{digit}|[_])*帶符號(hào)整數(shù)：

integerdigit(digit)*sign+|-|εsignintegersigninteger說明局部可用一個(gè)名字代表一個(gè)正規(guī)式，增加程序的可讀性2、識(shí)別規(guī)那么：是一串如下形式的LEX語句：R1{A1}R2{A2}∶∶Rm{Am}Ri：正規(guī)式{Ai}：Ai為語句序列，在識(shí)別出單詞Ri以后，詞法分析器所應(yīng)作的動(dòng)作。其根本動(dòng)作是返回單詞的類別編碼和單詞值。3、輔助過程:用戶定義的子程序下面是識(shí)別C語言局部單詞符號(hào)的LEX源程序：/*說明局部*/digit[0-9]letter[A-Za-z]id({letter}|[_])({letter}|{digit}|[_])*%%/*識(shí)別規(guī)那么，每條規(guī)那么中的動(dòng)作都用大括號(hào)括起來*/“main”|”int”|”if”{Upper(yytext,yyleng);printf("%s,KEY\n",yytext);}{id}{printf("%s,ID\n",yytext);}“+”|”-”|”*”{printf("%s,SYMBOL\n",yytext);}%%/*輔助過程*/Upper(char*s,intl){inti;for(i=0;i<l;i++)

s[i]=toupper(s[i]);

return1;}voidmain(void){yylex();}格式含義示例x匹配單個(gè)字符x

.匹配換行符之外的任意字符

\轉(zhuǎn)義字符，定義同ANSIC如\n，\t，\r[]字符集合,匹配括號(hào)內(nèi)的任意字符[abc]匹配a,b,和c中的任何一個(gè)-指定范圍[a-z]匹配a和z之間的任何一個(gè)^否定[^ab]匹配除了a和b之外的任意字符在LEX源文件識(shí)別規(guī)那么的最后應(yīng)加一條規(guī)那么：.{…};3.5.2LEX的正規(guī)式R*匹配0個(gè)或多個(gè)R(R是正規(guī)式)(ab)

*匹配{ε,ab,abab,ababab,…}中任何一個(gè)R＋匹配1個(gè)或多個(gè)R(ab)＋匹配{ab,abab,ababab,…}中的任何一個(gè)R?匹配0個(gè)或1個(gè)R(ab)?匹配ε或abR{m,n}匹配m到n之間次的R(m,n是整數(shù))a{2,4}匹配{aa,aaa,aaaa}中的任何一個(gè)R{m,}匹配m次以上的Ra{2,}匹配{aa,aaa,aaaa…}中的任何一個(gè)R{m}匹配m次Ra{2}匹配aa(R)匹配R，且R中運(yùn)算符優(yōu)先(ab)匹配abR|S匹配R或Sab|ba匹配ab或baRS匹配R和S的連接abba匹配abbaR/S匹配R，但R之后一定是S，稱S為R的尾部條件ab/ba匹配ab，但ab之后一定是ba^R匹配R，但R一定出現(xiàn)在行首

R$匹配R，但R一定出現(xiàn)在行尾，等價(jià)于R/\n

{name}匹配名字為name的正規(guī)式

運(yùn)算符說明優(yōu)先級(jí)()分組括號(hào)1（最高）[]字符類括號(hào)2*+?閉包運(yùn)算符3cc連接運(yùn)算符4|或運(yùn)算符5^?指定行首和行末6LEX正規(guī)式運(yùn)算符優(yōu)先級(jí)正規(guī)式含義[a-zA-Z0-9_]表示所有字母、數(shù)字及下劃線組成的字符集合[^\t\n]表示除空格、tab和換行外的所有字符組成的集合(\”[^”\n]*)表示以雙引號(hào)開頭，后跟除雙引號(hào)和換行外的若干字符組成的字符串，如“Iamastudent[A-Za-z][A-Za-z0-9]*表示以字母開頭，后跟若干字母和數(shù)字的字符串([Ee][-+][0-9]+)表示科學(xué)計(jì)數(shù)法的指數(shù)部分LEX正規(guī)式實(shí)例3.5.3LEX的實(shí)現(xiàn)LEX的功能是根據(jù)LEX源程序構(gòu)造一個(gè)詞法分析程序，該詞法分析器實(shí)質(zhì)上是一個(gè)有窮自動(dòng)機(jī)。LEX生成的詞法分析程序有兩局部組成:詞法分析程序由正規(guī)式構(gòu)造DFA識(shí)別單詞的控制程序LEX的處理過程：·掃描每條識(shí)別規(guī)那么Pi構(gòu)造一相應(yīng)的非確定有窮自動(dòng)機(jī)Mi¨將各條規(guī)那么的有窮自動(dòng)機(jī)Mi合并成一個(gè)新的NFAM即生成該DFA的狀態(tài)轉(zhuǎn)換矩陣和識(shí)別單詞的控制程序0P1εεεM1P2M2P3M3·¨確定化并最小化，NFADFALEX處理二義性規(guī)那么的原那么：1.最長匹配原則在識(shí)別單詞過程中，有一字符串xxxxx

根據(jù)最長匹配原則，應(yīng)識(shí)別為這是一個(gè)符合Pk規(guī)則單詞，而不是Pj和Pi規(guī)則的單詞。PjPiPk2.優(yōu)先匹配原那么如有一字符串，有兩條規(guī)那么可以同時(shí)匹配時(shí)，那么用規(guī)那么序列中位于前面的規(guī)那么相匹配，所以排列在前面的規(guī)那么優(yōu)先權(quán)最高如,main如,mains在寫LEX源程序時(shí)應(yīng)注意規(guī)那么的排列順序。另要注意，優(yōu)先匹配原那么是在符合最長匹配的前提下執(zhí)行的。例：LEX源程序，

a{}abb{}abb{}一.讀LEX源程序，分別生成NFA，用狀態(tài)圖表示為：二.合并成一個(gè)NFA：031745268startbbbbaaεεεa12345678startstartstartaaabbbb三.確定化給出狀態(tài)轉(zhuǎn)換的矩陣

狀態(tài)ab

到達(dá)終態(tài)所識(shí)別的單詞

初態(tài)終態(tài)

終態(tài)

終態(tài)

終態(tài){0,1,3,7}

{2,4,7}

{8}{7}

{5,8}

{6,8}{2,4,7}{7}{7}{8}{5,8}{8}{8}{8}{6,8}φφφaabbabb

abb在此DFA中初態(tài)為{0,1,3,7}

終態(tài)為{2,4,7},{8},{5,8},{6,8}031745268startbbbbaaεεεa優(yōu)先匹配原那么

狀態(tài)ab

到達(dá)終態(tài)所識(shí)別的單詞

初態(tài)終態(tài)

終態(tài)

終態(tài)

終態(tài){0,1,3,7}{2,4,7}{8}{7}{5,8}{6,8}{2,4,7}{7}{7}{8}{5,8}{8}{8}{8}{6,8}φφφaabbabbabb詞法分析程序的分析過程令輸入字符串為aba…讀入字符進(jìn)入狀態(tài)開始aba{0,1,3,7}{2,4,7}{5,8}無后繼狀態(tài)(退掉輸入字符a)(1)吃進(jìn)字符ab(2)按反序檢查狀態(tài)子集檢查前一次狀態(tài)是否含有原NFA的