編譯原理 詞法分析

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

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

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

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

5、,b， 上所有含有兩個(gè)相繼的上所有含有兩個(gè)相繼的a或兩或兩個(gè)相繼的個(gè)相繼的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符號(hào)合并符號(hào)合并轉(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)

6、合并到S1狀態(tài)。32例1：NFA轉(zhuǎn)換成DFA (符號(hào)合并)例2：設(shè)計(jì)一個(gè)DFA，其輸入字母表是0,1，它能接受以0開始，以1結(jié)尾的所有序列。aa3cb012a01,2cb30,10ZCSAB1解：解：根據(jù)題意，得出相應(yīng)的正則式：0(0|1)*1 得狀態(tài)轉(zhuǎn)換圖(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)轉(zhuǎn)換圖(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)劃分成兩個(gè)子集G1,G2;v分別從兩個(gè)子集G1,G2中尋找等價(jià)狀態(tài)