1、,Compiler,編 譯 原 理,Wednesday, March 13, 2013,詞法分析的任務(wù),Compiler,編 譯 原 理,Wednesday, March 13, 2013,標(biāo)識符,無符號整數(shù),單界符,雙界符,Compiler,編 譯 原 理,Wednesday, March 13, 2013,有窮自動機分為兩類： 確定的有窮自動機（DFA） (Deterministic Finite Automata) 不確定的有窮自動機（NFA） (Nondeterministic Finite Automata),Compiler,編 譯 原 理,Wednesday, March 13,

2、 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,M=(, Q, f,S, Z),Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,若M的初態(tài)結(jié)點同時為終態(tài)，或者存在一條從初態(tài)到某個終態(tài)結(jié)點的通路，則為M所識別。,Compiler,編 譯 原 理,Wednesday, March 13, 2013,對于符號串a(chǎn)baab,對于符號串a(chǎn)bab,C

3、ompiler,編 譯 原 理,Wednesday, March 13, 2013,f是一個多值函數(shù)，是從Q*到Q的子集的映射： f：Q2Q 其中2Q是Q的冪集，即Q中所有子集組成的集合。,Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,對于*上的任何符號串，若存在一條從某一初態(tài)到某一終態(tài)的通路，且該通路上所有弧的標(biāo)記字符依次連接成的串等于，則稱可以被NFA N所識別或接受。 若N的初態(tài)結(jié)點同時為終態(tài)，或者存在一條從初態(tài)到某個終態(tài)結(jié)點的通路，則為N所識別。,Compile

4、r,編 譯 原 理,Wednesday, March 13, 2013,上例題相應(yīng)的狀態(tài)圖為：,N所接受的語言（正規(guī)式） R=aa*b|ac*c|,Compiler,編 譯 原 理,Wednesday, March 13, 2013,(0|1)*(000|111)(0|1) *,Compiler,編 譯 原 理,Wednesday, March 13, 2013,畫出能夠識別C語言注釋/* */的DFA,Compiler,編 譯 原 理,Wednesday, March 13, 2013,狀態(tài)1：注釋開始狀態(tài)。 狀態(tài)2：進(jìn)入注釋體前的中間狀態(tài)。 狀態(tài)3：表明目前正在注釋體中的狀態(tài)。 狀態(tài)4：離

5、開注釋前的中間狀態(tài)。 狀態(tài)5：注釋結(jié)束狀態(tài)，即接受狀態(tài)。,Compiler,編 譯 原 理,Wednesday, March 13, 2013,用于某些重要軟件的設(shè)計和構(gòu)造 設(shè)計和檢查數(shù)字電路行為的軟件; 掃描如網(wǎng)頁族等大規(guī)模文本以發(fā)現(xiàn)字、詞或其它結(jié)構(gòu)的出現(xiàn)頻率的軟件; 驗證所有只有有限多個不同狀態(tài)的系統(tǒng)的軟件，這類系統(tǒng)包括通信協(xié)議和信息安全交換協(xié)議。,閱讀兩篇論文 基于協(xié)議分析狀態(tài)機的入侵檢測系統(tǒng) 有限自動機在BBS信息監(jiān)測系統(tǒng)中的運用,Compiler,編 譯 原 理,Wednesday, March 13, 2013,已證明：非確定的有窮自動機與確定的有窮自動機從功能上來說是等價的，也就

6、是說，我們能夠從：,NFA N,DFA M,構(gòu)造成一個,使得 L(M)=L(N),DFA是NFA的特例。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.,Compiler,編 譯 原 理,Wednesday, March 13, 2013,已證明：非確定的有窮自動機與確定的有窮自動機從功能上來說是等價的，也就是說，我們能夠從：,NFA M,DFA M,構(gòu)造成一個,使得 L(M)=L(M),DFA是NFA的特例。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法. 與某一NFA等價的DFA不唯一,Compiler,編 譯 原 理,Wednesday, March 13, 2013

7、,從NFA的矩陣表示中可以看出，表項通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項是一個狀態(tài)。 NFA到相應(yīng)的DFA的構(gòu)造的基本思路是： DFA的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài).,Compiler,編 譯 原 理,Wednesday, March 13, 2013,(1) 合并 如果有 ，則把S2合并到S1,轉(zhuǎn)換需解決的問題：,Compiler,編 譯 原 理,Wednesday, March 13, 2013,(2)狀態(tài)合并,Compiler,編 譯 原 理,Wednesday, March 13, 2013, 若qI，則q-closure(I)； 若qI，則從q出發(fā)經(jīng)過任意條弧而能到達(dá)的

8、任何狀態(tài)q都屬于-closure(I)。,為了使得NFA確定化，我們首先給出兩個定義：,Compiler,編 譯 原 理,Wednesday, March 13, 2013,例： 如圖所示的狀態(tài)圖： 令I(lǐng)=1， 求-closure（I）=？,根據(jù)定義： -closure（I）=1，3,課堂練習(xí)： 令I(lǐng)=1,2， 求-closure（I）=？,Compiler,編 譯 原 理,Wednesday, March 13, 2013,I是狀態(tài)集，由I中的狀態(tài)出發(fā)，經(jīng)過一條a弧可能到達(dá)的狀態(tài)的集合稱為move（I，a），則 Ia= _closure ( move( I , a ) ),Compiler,

9、編 譯 原 理,Wednesday, March 13, 2013,例：令 I=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)換矩陣）,課堂練習(xí)： 令I(lǐng)=1,2,3 求Ia =？,Compiler,編 譯 原 理,Wednesday, March 13, 2013,課堂練習(xí)： 令I(lǐng)=1，設(shè)S= -closure（I），求 S？ Sa =？,將從狀態(tài)S出發(fā)經(jīng)過任意條弧所能到達(dá)的狀態(tài)作為DFA的初態(tài)S 從S出發(fā)，把遇到輸入符號a所轉(zhuǎn)移到的后繼狀態(tài)集作為DFA的新狀

10、態(tài) 如此重復(fù)，直到不再有新的狀態(tài)出現(xiàn)為止,Compiler,編 譯 原 理,Wednesday, March 13, 2013,I Ia Ib Ic,1,4 2,3 ,2,3 2 4 3,4,2 2 4 ,4 ,3,4 3,4,（1）構(gòu)造一張表，它共有+1列 （2）第一行第一列為-closure(S) （3）求Ia （4）重復(fù)步驟（3） （5）將狀態(tài)子集重新命名,Compiler,編 譯 原 理,Wednesday, March 13, 2013,將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號 DFA M狀態(tài)轉(zhuǎn)換矩陣：,Compiler,編 譯 原 理,Wednesday, March 13, 2013,Com

11、piler,編 譯 原 理,Wednesday, March 13, 2013,課堂練習(xí),Compiler,編 譯 原 理,Wednesday, March 13, 2013,等價的DFA,a,a,b,start,Compiler,編 譯 原 理,Wednesday, March 13, 2013,最簡的DFA 它沒有多余狀態(tài)和等價狀態(tài),Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,C

12、ompiler,編 譯 原 理,Wednesday, March 13, 2013,解:,(一)區(qū)分終態(tài)與非終態(tài),1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,a,b,區(qū)號,Compiler,編 譯 原 理,Wednesday, March 13, 2013,區(qū)號,區(qū)號,Compiler,編 譯 原 理,Wednesday, March 13, 2013,40,正規(guī)表達(dá)式的引入：,對自動生成詞法分析程序而言，正規(guī)表達(dá) 式也是非常有用的工具。,所謂正規(guī)表達(dá)式就是用特定的運算符及運算對象按某種規(guī)則構(gòu)造的表達(dá)式。例如：c-語言的詞法。,正規(guī)表達(dá)式用來描述單詞結(jié)構(gòu)

13、(定義單詞)。,41,正規(guī)表達(dá)式(也稱正則表達(dá)式)就是用特定的運算符及運算對象按某種規(guī)則構(gòu)造的表達(dá)式。 每個正規(guī)表達(dá)式代表一個字符串的集合，我們把其稱為正規(guī)集。 語言(Language)是字符串組成的集合，我們也可以把正規(guī)表達(dá)式表示的正規(guī)集稱為該正規(guī)表達(dá)式表示的語言。,42,正規(guī)表達(dá)式和它所表示的正規(guī)集(字符串的集合)的遞歸定義如下： 設(shè)有字母表為，輔助字母表=, | , . , * , ( , ) ,43,(1)和是上的正規(guī)式，它們所表示的正規(guī)集分別為和; (2) 若a，則a是上的正規(guī)式，它所表示的正規(guī)集為a;,若r和s都是上的正規(guī)式，且它們所表示的正規(guī)集分別為L(r)和L(s)，那么：,4

14、4,r|s 是正規(guī)式，表示的正規(guī)集為 L(r|s)=L(r)L(s) ； rs 是正規(guī)式，表示的正規(guī)集為 L(rs)=L(r)L(s) ； r *是正規(guī)式，表示的正規(guī)集為(L(r)*。 (r) 是正規(guī)式，表示的正規(guī)集為L(r)；,45,(4)僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的符號串集合才是上的正規(guī)集。 注：算符的優(yōu)先級為先“ * ”，再“ . ”最后“ | ” ,都是左結(jié)合的，它們滿足結(jié)合律。,舉例： C-語言的詞法,46,例1，令=a，b，上的正規(guī)式和相應(yīng)的正規(guī)集的例子：,正規(guī)式 正規(guī)集,a,a,ab,ab,(ab)(ab),a ,a,b,ab,aa

15、,ab,ba,bb, ,a,aa, 任意個a的串,(ab) ,a,b*,即,a,b,aa,ab,ba,bb,47,例2，正規(guī)式(a)| (b) * (c)它所表示的正規(guī)集為：,根據(jù)運算符的優(yōu)先級，上述正規(guī)式可以表示成 a|b*c； a|b*c所表示的正規(guī)集為：串a(chǎn)或者是由零個或多個b后跟一個c 形成的字符串的集合。 或?qū)懗蒐(a|b*c)=a bnc | 其中n是大于或等于0的整數(shù),48,每一種程序設(shè)計語言都有自己的字符集(字母表)。 語言中的各個單詞或是上的單個字符(如運算符、分隔符等)，或是上的字符串(如常數(shù)、表示符和關(guān)鍵字等)。 程序設(shè)計語言的單詞可用正規(guī)式來定義，由正規(guī)式描述的正規(guī)集即

16、為程序設(shè)計語言的單詞類。例如：C-語言的詞法,49,正規(guī)表達(dá)式是表示模式的一種重要方法，每個模式匹配一個字符串集合(即正規(guī)集)。 正規(guī)集是正規(guī)表達(dá)式所定義的語言。 正規(guī)表達(dá)式可以作為字符串集合(即正規(guī)集)的名字。,50,給定一個正規(guī)式,它唯一確定一個正規(guī)集；反之不成立。即一個正規(guī)集可由多個不同的正規(guī)式表示。,aa,a,aa, aaa,任意個a的串,a|aa,a,aa, aaa,任意個a的串,例如：,Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,(1)在M上加兩個結(jié)點S,

17、Z，從S結(jié)點用弧到M的所有初態(tài)，從M的所有終態(tài)用到Z結(jié)成與M等價的M，M只有一個初態(tài)S和一個終態(tài)Z.,Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,（1）對NFA M構(gòu)造一個廣義的狀態(tài)圖，其中只有一個初態(tài)S和終態(tài)Z，連接S和Z的有向弧標(biāo)記為正規(guī)式。 （2）對正規(guī)式依次進(jìn)行分解，分解的過程是一個不斷加入結(jié)點和弧的過程，直到轉(zhuǎn)換圖上的所有弧標(biāo)記上都是字母表上的元素或為止。,Compiler

18、,編 譯 原 理,Wednesday, March 13, 2013,若s,t為上的正規(guī)式,Compiler,編 譯 原 理,Wednesday, March 13, 2013,Compiler,編 譯 原 理,Wednesday, March 13, 2013,步驟1 將每條產(chǎn)生式改寫為正規(guī)式； 步驟2 用代入法解正規(guī)式方程組，最后只剩下一個開始符號定義的正規(guī)式，其中不含非終結(jié)符。,Compiler,編 譯 原 理,Wednesday, March 13, 2013,【例3.5】GS: SaA|a AdA|d,Compiler,編 譯 原 理,Wednesday, March 13, 2013,步驟1 構(gòu)造 Sr 步驟2 不斷利用表3.4的規(guī)則做變換,直到每個產(chǎn)生式最多含有一個終結(jié)符為止,Compiler,編 譯 原 理,Wednesday, March 13, 2013,【例3.6】求正規(guī)式(a|b)(a|b|0|1)*對應(yīng)的正規(guī)文法,S(a|b)(a|b|0|1)*,S(a|b),AaA|bA|0A|1A|,GS： SaA|bA AaA|bA|0A|1A|,A(a|b|0|1)*,Compiler,編 譯 原 理,Wednesday, March 1