1、第二章第二章 詞法分析詞法分析 本章內容本章內容 詞法分析器：把構成源程序的字符流翻譯成詞法分析器：把構成源程序的字符流翻譯成記號流，記號流，還完成和用戶接口的一些任務還完成和用戶接口的一些任務 圍繞詞法分析器的自動生成展開圍繞詞法分析器的自動生成展開 介紹正規式、狀態轉換圖和有限自動機概念介紹正規式、狀態轉換圖和有限自動機概念 詞法分析器詞法分析器語法分析器語法分析器符號表符號表記號記號取下一個記號取下一個記號源程序源程序2.1 詞法記號及屬性詞法記號及屬性 2.1.1 詞法記號、模式、詞法單元詞法記號、模式、詞法單元 詞法記號詞法記號詞法單元例舉詞法單元例舉模式的非形式描述模式的非形式描述

2、 var var var for for for relation , = , = , 或或 0） 2.2 詞法記號的描述與識別詞法記號的描述與識別 語言的運算語言的運算和：和：LM = s | s L 或或 s M 連接：連接：LM = st | s L 且且 t M 指數：指數：L0是是 ，Li是是Li -1L 閉包：閉包：L L = = L L0 L L1 L L2 正閉包正閉包： L L+ = = L L1 L L2 例例L: A, B, , Z, a, b, , z , D: 0, 1, , 9 LD, LD, L6, L*, L(LD )*, D+ 2.2 詞法記號的描述與識別詞法

3、記號的描述與識別 2.2.2 正規式正規式正規式正規式用來表示簡單的語言，用來表示簡單的語言，叫做叫做正規集正規集 正規式正規式定義的語言定義的語言備注備注 a a a (r) | (s)L(r)L(s) r和和s是正規式是正規式(r)(s)L(r)L(s) r和和s是正規式是正規式(r)*(L(r)* r是正規式是正規式(r)L(r) r是正規式是正規式(a) (b)*)| (c)可以寫成可以寫成ab*| c 2.2 詞法記號的描述與識別詞法記號的描述與識別 正規式的例子正規式的例子 = = a, b a | ba, b (a | b) (a | b )aa, ab, ba, bb aa |

4、 ab | ba | bbaa, ab, ba, bb a*由字母由字母a構成的所有串集構成的所有串集 (a | b)*由由a和和b構成的所有串集構成的所有串集 復雜的例子復雜的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：010011010000100000101110012.2 詞法記號的描述與識別詞法記號的描述與識別 2.2.3 正規定義正規定義對正規式命名，使表示簡潔。對正規式命名，使表示簡潔。 d1 r1 d2 r2 . . . dn rn各個各個di的名字都不同的名字都不同每個每個ri都是都是 d1, d2, , d

5、i-1 上的正規式上的正規式2.2 詞法記號的描述與識別詞法記號的描述與識別 正規定義的例子正規定義的例子Pascal語言的標識符集合語言的標識符集合letter A | B | | Z | a | b | | zdigit 0 | 1 | | 9id letter( (letter| |digit) )* =a,b=a,b，上的正規式和相應的正規集如下上的正規式和相應的正規集如下：例例 2 2：令令=A,B,0,1=A,B,0,1，則，則：例例 3 3：令令=d,.,e,+,-=d,.,e,+,-，則，則上的無符號數的正規式上的無符號數的正規式 表示為：表示為：例例 3 3：令：令=d,.,

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

7、結點)狀態下可能出現的輸入字符或字符類。v 一張轉換圖只包含有限個狀態(即有限個結點)，其中一個為初態，至少一個為終態(雙圈表示)。狀態轉換圖狀態轉換圖狀態轉換圖是設計詞法分析程序的一種好途徑。狀態轉換圖是設計詞法分析程序的一種好途徑。狀態轉換圖，一張有限方向圖，規定：狀態轉換圖，一張有限方向圖，規定：例3：識別整數的轉換圖（如右上圖）例2：識別標識符的轉換圖（如左下圖）字母字母01字母或數字字母或數字數字數字01數字數字表示：在狀態1下，若輸入字符為x，則讀進x，并轉換到狀態2； 若輸入字符為y，則讀進y，并轉換到狀態3。132xy例1：2.3 有有 限限 自自 動動 機機 2.3.1 不確

8、定的有限自動機（簡稱不確定的有限自動機（簡稱NFA）一個數學模型，它包括一個數學模型，它包括: : 狀態集合狀態集合S； 輸入符號集合輸入符號集合 ； 轉換函數轉換函數move : S ( ) P(S)； 狀態狀態s0是開始狀態；是開始狀態； F S是接受狀態集合是接受狀態集合。NFA的形式定義為的形式定義為:ABijABijkA|BijA*ijABijijkANFA替換規則替換規則NFA允許允許邊出現邊出現=a,b， 上所有含有兩個相繼的上所有含有兩個相繼的a或兩或兩個相繼的個相繼的b的字的集合的字的集合用用NFA表示如下表示如下：(a|b)* (aa|bb) (a|b)* NFA M=(

9、0,1,2,3,4,5,6,7 , a,b , , 0 , 7 )其中其中如上（不可省略）(a|b)*aa|bb(a|b)*aa576bbab01234ba初態初態終態終態(a|b)* (aa|bb) (a|b)* 2.3 有有 限限 自自 動動 機機 12開始開始a0abb識別語言識別語言(a|b)*ab 的的NFA輸輸 入入 符符 號號ab00, 101 22 狀狀 態態 NFA的轉換表的轉換表2.3 有有 限限 自自 動動 機機 例例 識別識別aa* *| |bb* *的的NFA12開始開始a0abb34 2.3 有有 限限 自自 動動 機機2.3.2 確定的有限自動機（簡稱確定的有限自

10、動機（簡稱DFA) ) 一個數學模型，包括：一個數學模型，包括： 狀態集合狀態集合S； 輸入字母表輸入字母表 ； 轉換函數轉換函數move : S S； 唯一的初態唯一的初態 s S； 終態集合終態集合F S；12開始開始a0abbab識別語言識別語言(a|b)*ab 的的DFA它所對應的狀態轉移矩陣如圖：一個一個DFADFA可用一個矩陣表示，該矩陣的行表示狀態，可用一個矩陣表示，該矩陣的行表示狀態，列表示輸入字符，矩陣元素表示列表示輸入字符，矩陣元素表示(s,a)(s,a)的值，這個的值，這個矩陣稱狀態轉移矩陣。矩陣稱狀態轉移矩陣。狀態狀態ab012132213333狀態轉換圖可用于識別（或

11、接受）一定的字符串狀態轉換圖可用于識別（或接受）一定的字符串aaa|b031bbab2a1a2anv（）合并）合并v符號合并符號合并轉換函數初態NFA M (S,S0,F)SS的子集多值映射S0 S非空初態DFA M (S,s0,F)SS單值映射s0S唯一的初態NFA允許允許邊出現邊出現（）合并：）合并：如果有S1S2,則把S2狀態合并到S1狀態。例1：NFA轉換成DFA (符號合并)例2：設計一個DFA，其輸入字母表是0,1，它能接受以0開始，以1結尾的所有序列。aa3cb012a01,2cb30,10ZCSAB1解：解：根據題意，得出相應的正規式：0(0|1)*1 得狀態轉換圖(NFA)如

12、下：01stateDFA stateSS,ABCSABCS,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,10ZCSAB101stateDFA stateSS,ABCSABCS,ABCS,ABCABCBCBCZ ABC,BC,BCZS,ABC,BC,BCZBCBCBCZ BC,BCZS,ABC,BC,BCZBCZBCBCZ BCZS,ABC,BC,BCZ 0,10ZCSA

13、B1(ABC,0)初態初態(S,0)得狀態轉換圖(DFA)如下：000SCA101B1000SBCZABC101BC1在DFA中，所有含有NFA的終態的狀態作為DFA的終態DFA M=( S,A,B,C , 0,1 , , S , C )其中其中如上（不可省略）初態初態v將所有DFA的終態與其它狀態劃分成兩個子集G1,G2;v分別從兩個子集G1,G2中尋找等價狀態進行化簡。v將所有DFA的終態與其它狀態劃分成兩個子集例2：設計一個DFA，其輸入字母表是0,1，它能接受以0開始，以1結尾的所有序列。化簡01SABCABCBCBCZBCBCBCZBCZBCBCZ01SABCABCABCBCZBCZ

14、ABCBCZDFA M=( S,ABC,BCZ , 0,1 , ,S, BCZ )其中其中如上(不可省略)00SBCZABC011005311240,110,10,101bbab72386145bba 注：狀態從18標注*附：部分程序偽碼附：部分程序偽碼 (1)(1)用轉換表構造用轉換表構造DFADFAState:=Initstate; /初態Read(CurrentChar); /上字符(源程序字符)While T(State,CurrentChar)error & CurrentChar Eof do State:=T(State,CurrentChar); Read(Curren

15、tChar); If StateFinalStates then Accept else ErrorT(State,CurrentChar)：轉換函數(2)(2) NFA NFA到到DFADFA的轉換的轉換()()合并合并ss:NFA的一個狀態集;Close(ss):表示()合并后的狀態集;PROCEDURE Close(ss:NFA_state)BEGIN new:=1; While new:=1 do If (存在Sjss & Skss & T(Sj, )=Sk) THEN ss:=ssSk ELSE new:=0 END(3) (3) NFANFA到到DFADFA的轉換的

16、轉換符號合并符號合并PROCEDURE MakeDFA(NA:NFA_state; DA:DFA_state)BEGIN1 DA.init_state=Close(NA.initial_states); DA.states:=DA.init_state ; States:=DA.init_state;2 選擇一個新元素ssstates,對每個a做: ss1:=Close(MoveSet(ss,a,NA.T); 令DA.T(ss,a)=ss1; /確定DFA的轉換函數 若ss1DA.states則將ss1分別加入states和DA.states中 3 從States刪除ss;4 若States非空,則重復24;5 DA.final