1、1第四章第四章: :詞法分析詞法分析Lexical AnalysisLexical Analysis234第二遍第二遍單詞串單詞串取單詞取單詞優(yōu)點優(yōu)點: 結構清晰、各遍功能單一結構清晰、各遍功能單一缺點：效率低缺點：效率低562. 詞法分析程序的輸出形式詞法分析程序的輸出形式-單詞的內部形式單詞的內部形式7If (3, if)I (1,8910111213=a,b=a,b，上的正規(guī)式和相應的正規(guī)集如下上的正規(guī)式和相應的正規(guī)集如下：14例例 2 2：令令=A,B,0,1=A,B,0,1，則，則：例例 3 3：令令=d,.,e,+,-=d,.,e,+,-，寫出，寫出上的無符號數(shù)的正則上的無符號數(shù)的

2、正則式式15例例 3 3：令：令=d,.,e,+,-=d,.,e,+,-，則，則上的無符號數(shù)上的無符號數(shù)的正則式表示為：的正則式表示為：164.2.3 4.2.3 程序設計語言中的正則表達式程序設計語言中的正則表達式例1：數(shù)字集D=0,1,9和字母集L=A|Z|a|z例2：整常數(shù)的集合IntC可表示為：例3：實常數(shù)的集合RealC可表示為：“”讀作“定義定義為為”17例5：由/開始并以Eol（行結束符）結束的注釋，可用正則表達式定義為如下：例4：由字母、數(shù)字和下劃線組成，由字母為首，以字母或數(shù)字結束，且下劃線不相連的標識符之集IDE可表示為如下：18 192021v 結點代表狀態(tài)，用圓圈表示。

3、v 狀態(tài)之間用箭弧連結，箭弧上的標記(字符)代表在射出結點(即箭弧始結點)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。v 一張轉換圖只包含有限個狀態(tài)(即有限個結點)，其中一個為初態(tài)，至少一個為終態(tài)(雙圈表示)。狀態(tài)轉換圖狀態(tài)轉換圖狀態(tài)轉換圖是設計詞法分析程序的一種好途徑。狀態(tài)轉換圖是設計詞法分析程序的一種好途徑。狀態(tài)轉換圖，一張有限方向圖，規(guī)定：狀態(tài)轉換圖，一張有限方向圖，規(guī)定：22例3：識別整數(shù)的轉換圖（如右上圖）例2：識別標識符的轉換圖（如左下圖）字母字母01字母或數(shù)字字母或數(shù)字數(shù)字數(shù)字01數(shù)字數(shù)字表示：在狀態(tài)1下，若輸入字符為x，則讀進x，并轉換到狀態(tài)2； 若輸入字符為y，則讀進y，并轉換到狀態(tài)3

4、。132xy例1：2324它所對應的狀態(tài)轉移矩陣如圖：一個一個DFADFA可用一個矩陣表示，該矩陣的行表示狀態(tài)，可用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示列表示輸入字符，矩陣元素表示(s,a)(s,a)的值，這個的值，這個矩陣稱狀態(tài)轉移矩陣。矩陣稱狀態(tài)轉移矩陣。狀態(tài)狀態(tài)ab01213221333325狀態(tài)轉換圖可用于識別（或接受）一定的字符串狀態(tài)轉換圖可用于識別（或接受）一定的字符串aaa|b031bbab226a1a2an27NFA的形式定義為的形式定義為:28ABijABijkA|BijA*ijABijijkANFA替換規(guī)則替換規(guī)則NFA允許允許邊出現(xiàn)邊出現(xiàn)29=a

5、,b， 上所有含有兩個相繼的上所有含有兩個相繼的a或兩或兩個相繼的個相繼的b的字的集合的字的集合用用NFA表示如下表示如下：NFA M=( 0,1,2,3,4,5,6,7 , a,b , , 0 , 7 )其中其中如上（不可省略）(a|b)*aa|bb(a|b)*aa576bbab01234ba初態(tài)初態(tài)終態(tài)終態(tài)(a|b)* (aa|bb) (a|b)* 3031v（）合并）合并v符號合并符號合并轉換函數(shù)初態(tài)NFA M (S,S0,F)SS的子集多值映射S0 S非空初態(tài)DFA M (S,s0,F)SS單值映射s0S唯一的初態(tài)NFA允許允許邊出現(xiàn)邊出現(xiàn)（）合并：）合并：如果有S1S2,則把S2狀態(tài)

6、合并到S1狀態(tài)。32例1：NFA轉換成DFA (符號合并)例2：設計一個DFA，其輸入字母表是0,1，它能接受以0開始，以1結尾的所有序列。aa3cb012a01,2cb30,10ZCSAB1解：解：根據題意，得出相應的正則式：0(0|1)*1 得狀態(tài)轉換圖(NFA)如下：3301stateDFA stateSSSABCS,ABCS,ABCABCBCBCZ ABC,BC,BCZS,ABC,BC,BCZBCBCBCZ BC,BCZS,ABC,BC,BCZBCZBCBCZ BCZS,ABC,BC,BCZ(S,)=;(S,0)=？(S,0)=A; (A,)=B; (B,)=C; (C,)=； 0,10ZCSAB134得狀態(tài)轉換圖(DFA)如下：000SCA101B1000SBCZABC101BC1在DFA中，所有含有NFA的終態(tài)的狀態(tài)作為DFA的終態(tài)DFA M=( S,A,B,C , 0,1 , , S , C )其中其中如上（不可省略）353637初態(tài)初態(tài)3839404142v將所有DFA的終態(tài)與其它狀態(tài)劃分成兩個子集G1,G2;v分別從兩個子集G1,G2中尋找等價狀態(tài)