蘇州大學(xué)ppt

1、編譯原理,第三章 詞法分析,1,詞法分析器模型 圖3.49,3.8詞法分析器生成工具的設(shè)計,2,DFA模擬器 圖3.27,NFA模擬器 圖3.27,DFA轉(zhuǎn)換表,NFA轉(zhuǎn)換表,詞法分析器工作方式,詞法分析器生成工具工作方式實例 3.26 任務(wù)包括多個正則表達(dá)式，且分別對應(yīng)不同的語義動作。a {模式P1的動作A1}abb {模式P2的動作A2}a*b+ {模式P3的動作A3},3.8詞法分析器生成工具的設(shè)計,3,

2、詞法分析器生成工具工作方式NFA/DFA轉(zhuǎn)換表的構(gòu)造把每個正則表達(dá)式轉(zhuǎn)換為一個NFA按照圖3.50方式，把所有NFA合并為一個NFA。把這個NFA轉(zhuǎn)換為一個DFA，使用這個DFA識別與所有正則表達(dá)式相匹配的詞素。,3.8詞法分析器生成工具的設(shè)計,4,詞法分析器生成工具的設(shè)計基于NFA的模式匹配 圖3.53一直運(yùn)行到達(dá)一個沒有后續(xù)狀態(tài)的輸入點后，首先回頭查找一個包含可接收狀態(tài)的集合，即利用最長匹配確定可接受狀態(tài)集合，然后根據(jù)重

3、要性（例如根據(jù)正則表達(dá)式出現(xiàn)順序）確定哪個正則表達(dá)式。最后進(jìn)行forward指針修復(fù)，同時執(zhí)行與此正則表達(dá)式相關(guān)的語義動作。,5,3.8詞法分析器生成工具的設(shè)計,3.8詞法分析器生成工具的設(shè)計,詞法分析器生成工具的設(shè)計基于DFA的模式匹配 圖3.54與NFA類似：DFA可接受狀態(tài)包含一個或多個NFA可接受狀態(tài)。,6,轉(zhuǎn)換方式：不需構(gòu)造中間的NFA動機(jī)：可能的狀態(tài)轉(zhuǎn)移只與某些狀態(tài)相關(guān)轉(zhuǎn)移函數(shù)：move(s,a)/move(S,a)

4、存在一個非ε標(biāo)號(Σ中字母) 離開該狀態(tài)s，即存在某個 字母a, 轉(zhuǎn)移函數(shù)move(s,a)非空。,3.9直接從正則式到DFA（3.9.1-3.9.5）,7,構(gòu)造原理重要狀態(tài)對應(yīng)于正則式中字母的每次出現(xiàn)位置，即抽象語法樹的非ε葉子節(jié)點。拓廣正則表達(dá)式 （r）#加入右端結(jié)束標(biāo)記#確保接受狀態(tài)是重要狀態(tài)！實例 (a|b)*abb# 圖3-56,3.9直接從正則式到DFA,8,構(gòu)造原理轉(zhuǎn)換表：聚焦重要狀態(tài)之間的轉(zhuǎn)移開始

5、狀態(tài)：可能出現(xiàn)在給定正則表達(dá)式描述的語言中任何一個串第一個符號位置的所有重要狀態(tài)。接受狀態(tài)：和結(jié)尾#相關(guān)的位置,3.9直接從正則式到DFA,9,構(gòu)造算法定義四個函數(shù)：nullable、firstpos、lastpos、followpos,3.9直接從正則式到DFA,10,構(gòu)造算法計算nullable、firstpos、lastpos：圖3.58&3.59,3.9直接從正則式到DFA,11,構(gòu)造算法計算followpos：

6、圖3.60&3.61,3.9直接從正則式到DFA,12,構(gòu)造算法算法3.36 圖3.62 vs 圖3.32子集構(gòu)造法初始狀態(tài)：firstpos(n0) vs ε-closure(s0)后續(xù)狀態(tài)：S中和a對應(yīng)的所有位置p的followpos(p) vs ε-closure(move(T,a))S中有些p與a對應(yīng)，有些不對應(yīng)。,3.9直接從正則式到DFA,13,構(gòu)造算法實例 例3.37,3.9直接從正則式到DFA,14,得

7、到的DFA狀態(tài)比通過NFA得到的DFA狀態(tài)少！,DFA最簡化原理最簡DFA唯一性：每一個正則式可以由一個狀態(tài)數(shù)最少的DFA識別，且這個DFA唯一?？尚行裕篋FA存在不可區(qū)別狀態(tài)，可以合并?；啑l件：確保DFA是全函數(shù)DFA可能是部分函數(shù)：存在狀態(tài)s符號a，move(s,a)不存在！解決方式：DFA化簡前引入死狀態(tài)（化簡后可以去掉死狀態(tài)）,3.10 DFA最簡化（3.9.6-3.9.7）,15,死狀態(tài)在轉(zhuǎn)換函數(shù)由部分函數(shù)改成全

8、函數(shù)表示時引入。死狀態(tài)對所有輸入符號都轉(zhuǎn)換到本身。左圖需要引入死狀態(tài)E ；右圖無須引入死狀態(tài)。,3.10 DFA最簡化,16,可區(qū)別狀態(tài)狀態(tài)s和t可區(qū)別：存在一個串x，分別從狀態(tài)s和t出發(fā)，沿著標(biāo)號為x的路徑到達(dá)的兩個狀態(tài)中只有一個是接受狀態(tài)。A和B是可區(qū)別的狀態(tài)：從A出發(fā)，通過串b，到達(dá)非接受狀態(tài)C，而從B出發(fā)，通過過串b，到達(dá)接受狀態(tài)D。A和C是不可區(qū)別的狀態(tài)（等價的狀態(tài)）：無任何串可像上面這樣區(qū)別它們。,3.10 DFA

9、最簡化,17,最簡化DFA算法：算法3.39 圖3.64構(gòu)造狀態(tài)集合的初始劃分π：兩個子集——接受狀態(tài)子集F和非接受狀態(tài)子集S – F可以存在多個接受狀態(tài)子集：每個對應(yīng)不同詞法單元的識別。應(yīng)用下面的過程構(gòu)造πnew對于π 中的每個子集G把G劃分為若干子集，G的兩個狀態(tài) s 和 t 在同一子集中，當(dāng)且僅當(dāng)對任意輸入符號 a ，s 和 t 的 a 轉(zhuǎn)換都到 π 的同一子集中。在πnew 中，用G的劃分代替G如果πnew = π

10、，則πfinal = π；否則令π = πnew ，轉(zhuǎn)上步在πfinal的每個狀態(tài)子集中選一個狀態(tài)代表它（同一個狀態(tài)子集中的各個狀態(tài)等價，不可區(qū)別），即為最簡DFA的狀態(tài)。最簡DFA的開始狀態(tài)：包含了原始DFA開始狀態(tài)的組的代表最簡DFA的接受狀態(tài)：包含了原始DFA接受狀態(tài)的組的代表轉(zhuǎn)換表：對于πfinal 中狀態(tài)子集G和H的代表s和r，如果存在move(s,a)=t且t屬H，那么move(s,a)=r。,3.10 DFA最簡化

11、,18,最簡化DFA算法：實例S-F={A, B, C}, F={D} {A, C}, {B}, {D}move(A,a)=Bmove(B,a)=Bmove(C,a)=Bmove(A,b)=Cmove(B,b)=D move(C,a)=C,3.10 DFA最簡化,19,敘述下面的正則式描述的語言，并畫出接受該語言的最簡DFA的狀態(tài)轉(zhuǎn)換圖(1|01)* 0*描述的語言：所有不含子串001的0和1的串