compiler4_詞法分析

1、第二章第二章 詞法分析詞法分析 本章內(nèi)容本章內(nèi)容 詞法分析器：把構成源程序的字符流翻譯成詞法分析器：把構成源程序的字符流翻譯成記號流，記號流，還完成和用戶接口的一些任務還完成和用戶接口的一些任務 圍繞詞法分析器的自動生成展開圍繞詞法分析器的自動生成展開 介紹正規(guī)式、狀態(tài)轉換圖和有限自動機概念介紹正規(guī)式、狀態(tài)轉換圖和有限自動機概念詞法分析器詞法分析器語法分析器語法分析器符號表符號表記號記號取下一個記號取下一個記號源程序源程序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構成的所有串集構成的所有串集 (a | b)*由由a和和b構成的所有串集構成的所有串集 復雜的例子復雜的例子( 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語言的標識符集合語言的標識符集合letter A | B | | Z | a | b | | zdigit 0 | 1 | | 9id letter( (letter| |digit) )* =a,b=a,b，上的正規(guī)式和相應的正規(guī)集如下上的正規(guī)式和相應的正規(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 程序設計語言中的正規(guī)表達式程序設計語言中的正規(guī)表達式例1：數(shù)字集D=0,1,9和字母集L=A|Z|a|z例2：整常數(shù)的集合IntC可表示為：例3：實常數(shù)的集合RealC可表示為：“”讀作“定義定義為為”例5：由/開始并以Eol（行結束符）結束的注釋，可用正規(guī)表達式定義為如下：例4：由字母、數(shù)字和下劃線組成，由字母為首，以字母或數(shù)字結束，且下劃線不相連的標識符之集IDE可表示為如下：v 結點代表狀態(tài)，用圓圈表示。v 狀態(tài)之間用箭弧連結，箭弧上的標記(字符)代表在射出結點(即箭弧始結

7、點)狀態(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ī)定：例3：識別整數(shù)的轉換圖（如右上圖）例2：識別標識符的轉換圖（如左下圖）字母字母01字母或數(shù)字字母或數(shù)字數(shù)字數(shù)字01數(shù)字數(shù)字表示：在狀態(tài)1下，若輸入字符為x，則讀進x，并轉換到狀態(tài)2； 若輸入字符為y，則讀進y，并轉換到狀態(tài)3。132xy例1：2.3 有有 限限 自自 動動 機機 2.3.1 不確定

8、的有限自動機（簡稱不確定的有限自動機（簡稱NFA）一個數(shù)學模型，它包括一個數(shù)學模型，它包括: : 狀態(tài)集合狀態(tài)集合S； 輸入符號集合輸入符號集合 ； 轉換函數(shù)轉換函數(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的轉換表的轉換表2.3 有有 限限 自自 動動 機機 例例 識別識別aa* *| |bb* *的的NFA12開始開始a0abb34 2.3 有有 限限 自自 動動 機機2.3.2 確定的有限自動機（簡稱確定的有限自動

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

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

14、BCBCZDFA M=( S,ABC,BCZ , 0,1 , ,S, BCZ )其中其中如上(不可省略)00SBCZABC011005311240,110,10,101bbab72386145bba 注：狀態(tài)從18標注*附：部分程序偽碼附：部分程序偽碼 (1)(1)用轉換表構造用轉換表構造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)：轉換函數(shù)(2)(2) NFA NFA到到DFADFA的轉換的轉換()()合并合并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的轉換的轉換符號合并符號合并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 選擇一個新元素