compiler4_詞法分析

1、第二章第二章 詞法分析詞法分析 本章內(nèi)容本章內(nèi)容 詞法分析器：把構(gòu)成源程序的字符流翻譯成詞法分析器：把構(gòu)成源程序的字符流翻譯成記號流，記號流，還完成和用戶接口的一些任務(wù)還完成和用戶接口的一些任務(wù) 圍繞詞法分析器的自動生成展開圍繞詞法分析器的自動生成展開 介紹正規(guī)式、狀態(tài)轉(zhuǎn)換圖和有限自動機概念介紹正規(guī)式、狀態(tài)轉(zhuǎn)換圖和有限自動機概念詞法分析器詞法分析器語法分析器語法分析器符號表符號表記號記號取下一個記號取下一個記號源程序源程序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 指數(shù)：指數(shù)：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 正規(guī)式正規(guī)式正規(guī)式正規(guī)式用來表示簡單的語言，用來表示簡單的語言，叫做叫做正規(guī)集正規(guī)集 正規(guī)式正規(guī)式定義的語言定義的語言備注備注 a a a (r) | (s)L(r)L(s) r和和s是正規(guī)式是正規(guī)式(r)(s)L(r)L(s) r和和s是正規(guī)式是正規(guī)式(r)*(L(r)* r是正規(guī)式是正規(guī)式(r)L(r) r是正規(guī)式是正規(guī)式(a) (b)*)| (c)可以寫成可以寫成ab*| c 2.2 詞法記號的描述與識別詞法記號的描述與識別 正規(guī)式的例子正規(guī)式的例子 = = a, b a | ba, b (a | b) (a | b )aa, ab, ba, bb aa |

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

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

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

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

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

9、,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)* 2.3 有有 限限 自自 動動 機機 12開始開始a0abb識別語言識別語言(a|b)*ab 的的NFA輸輸 入入 符符 號號ab00, 101 22 狀狀 態(tài)態(tài) NFA的轉(zhuǎn)換表的轉(zhuǎn)換表2.3 有有 限限 自自 動動 機機 例例 識別識別aa* *| |bb* *的的NFA12開始開始a0abb34 2.3 有有 限限 自自 動動 機機2.3.2 確定的有限自動機（簡稱確定的有限自動

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

11、受）一定的字符串狀態(tài)轉(zhuǎn)換圖可用于識別（或接受）一定的字符串a(chǎn)aa|b031bbab2a1a2anv（）合并）合并v符號合并符號合并轉(zhuǎn)換函數(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)合并到S1狀態(tài)。例1：NFA轉(zhuǎn)換成DFA (符號合并)例2：設(shè)計一個DFA，其輸入字母表是0,1，它能接受以0開始，以1結(jié)尾的所有序列。aa3cb012a01,2cb30,10ZCSAB1解：解：根據(jù)題意，得出相應(yīng)的正規(guī)式：0(0|1)*1 得狀態(tài)轉(zhuǎn)換圖(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,10ZCSAB

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

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

15、Char); If StateFinalStates then Accept else ErrorT(State,CurrentChar)：轉(zhuǎn)換函數(shù)(2)(2) NFA NFA到到DFADFA的轉(zhuǎn)換的轉(zhuǎn)換()()合并合并ss:NFA的一個狀態(tài)集;Close(ss):表示()合并后的狀態(tài)集;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的轉(zhuǎn)換的轉(zhuǎn)換符號合并符號合并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 選擇一個新元素