1、1,2.4 從正規(guī)式到詞法分析器,構(gòu)造詞法分析器的一般方法和步驟： 用正規(guī)式對(duì)模式進(jìn)行描述； 為每個(gè)正規(guī)式構(gòu)造一個(gè)NFA，它識(shí)別正規(guī)式所表示的正規(guī)集； 將構(gòu)造出的NFA轉(zhuǎn)換成等價(jià)的DFA，這一過程也被稱為確定化； 優(yōu)化DFA，使其狀態(tài)數(shù)最少，這一過程也被稱為最小化； 從優(yōu)化后的DFA構(gòu)造詞法分析器。,問題： 我們是從DFA構(gòu)造詞法分析器，為何不直接從正規(guī)式構(gòu)造DFA，而要先構(gòu)造NFA，然后轉(zhuǎn)換為DFA？,原因： 機(jī)器構(gòu)造需要規(guī)范的算法； 正規(guī)式NFA：有規(guī)范的一對(duì)一的構(gòu)造算法 DFA分析器：有便于記號(hào)的識(shí)別的算法,2,2.4.1 從正規(guī)式到NFA,算法2.2 Thompson 算法 輸入 字母

2、表上的正規(guī)式r 輸出 接受L(r)的NFA N 方法 首先分解r，然后根據(jù)下述步驟構(gòu)造NFA：, 對(duì)，構(gòu)造NFA如右。其中，s0為初態(tài)，f為終態(tài)，此NFA接受；, 對(duì)上的每一個(gè)字符a，構(gòu)造NFA如右, 若N(p)和N(q)是正規(guī)式p和q的NFA，則 （a） 對(duì)正規(guī)式p|q，構(gòu)造NFA如右。其中，s0為初態(tài)，f為終態(tài)，此NFA接受L(p)L(q)；,（b） 對(duì)正規(guī)式pq，構(gòu)造NFA如右。其中，s0為初態(tài)，f為終態(tài)，此NFA接受L(p)L(q)；,（c） 對(duì)正規(guī)式p*，構(gòu)造NFA如右。其中，s0為初態(tài)，f為終態(tài)，此NFA接受L(p*)；, 對(duì)于正規(guī)式(p)，使用p本身的NFA，不再構(gòu)造新的NFA。

3、 ,3,2.4.1 從正規(guī)式到NFA（續(xù)1）,正規(guī)式 NFA, a P|Q PQ P*,定義2.2 令是一個(gè)有限字母表，則上的正規(guī)式及其表示的集合遞歸定義如下: 1. 是正規(guī)式，它表示集合L()= 2. 若a是上的字符，則a是正規(guī)式，它表示集合L(a)=a 3. 若正規(guī)式r和s分別表示集合L(r)和L(s)，則 （a） r|s是正規(guī)式，表示集合L(r)L(s)， （b） rs是正規(guī)式，表示集合L(r)L(s)， （c） r*是正規(guī)式，表示集合(L(r)*， （d）(r)是正規(guī)式，表示的集合仍然是L(r)。（加括弧改變優(yōu)先級(jí)、結(jié)合性） 可用正規(guī)式描述的語(yǔ)言稱為正規(guī)語(yǔ)言或正規(guī)集。 ,4,2.4.1

4、 從正規(guī)式到NFA（續(xù)2）,例2.11 用Thompson算法構(gòu)造正規(guī)式r=(a|b)*abb的NFA N(r), 分解正規(guī)式 自下而上構(gòu)造NFA,強(qiáng)調(diào)： 算法的構(gòu)造與正規(guī)式一一對(duì)應(yīng) 構(gòu)造一個(gè)新的NFA最多增加兩個(gè)狀態(tài),5,2.4.2 從NFA到DFA, NFA識(shí)別記號(hào)的“并行”方法,例2.12 從甲地到乙地，可以乘小轎車也可以騎自行車，具體路線如上。其中c表示乘車，b表示騎自行車?，F(xiàn)在要求從甲地到乙地，只許乘車而不許騎自行車，該如何走？ （即識(shí)別是否有從甲到乙標(biāo)記為cc的路徑）,試探（串行方式）： 甲 c 2 無(wú)路可走，退回 甲 c 1 c 3 無(wú)路可走，退回 甲 c 1 c 乙 到達(dá)乙地，

5、成功,并行(假設(shè)有足夠的小汽車，每次都是到達(dá)小汽車可能到達(dá)的全體) 甲 c 1, 2 c 3, 乙 到達(dá)乙地，成功,由于并行的方法在每試探一步時(shí)，考慮了所有的下一狀態(tài)轉(zhuǎn)移，因此所走的每一步都是確定的。 用NFA識(shí)別記號(hào)，并不采用串行的方法（算法不易構(gòu)造，復(fù)雜度高且回溯），而是采用并行的方法，核心思想是將不確定的下一狀態(tài)確定化。,6,NFA上識(shí)別記號(hào)的確定化方法 2.4.2 從NFA到DFA（續(xù)1）,確定化的兩個(gè)步驟（回顧DFA定義） 計(jì)算下一狀態(tài)轉(zhuǎn)移時(shí)： 消除 狀態(tài)轉(zhuǎn)移：-閉包(T) 消除多于一個(gè)的下一狀態(tài)轉(zhuǎn)移：smove(S, a) smove(S, a)：從狀態(tài)集S出發(fā)，標(biāo)記為a的下一狀態(tài)

6、全體。 與move(s, a)的唯一區(qū)別：用狀態(tài)集取代狀態(tài) -閉包(T)：從狀態(tài)T出發(fā)，不經(jīng)任何字符達(dá)到的狀態(tài)全體。,定義2.6 狀態(tài)集T的-閉包(T)是一個(gè)狀態(tài)集，且滿足： （1） T中所有狀態(tài)屬于-閉包(T)； （2） 任何smove(-閉包(T)，)屬于-閉包(T)； （3） 再無(wú)其他狀態(tài)屬于-閉包(T)。 ,根據(jù)定義，上圖中-閉包(s2)應(yīng)該包括： 1. s2自身s2（1） 2. s4s2, s4（2） 3. s5s2, s4, s5（2）算法,7,算法2.3 模擬NFA 2.4.2 從NFA到DFA（續(xù)2）,輸入 NFA N，x（eof）， s0， F 輸出 若N接受x，回答“yes

7、”，否則“no” 方法 用下邊的過程對(duì)x進(jìn)行識(shí)別。S是一個(gè)狀態(tài)的集合,S := -閉包(s0); - 所有可能初態(tài)的集合 a := nextchar; while a eof loop S:=-閉包(smove(S，a)； - 所有下一狀態(tài)的集合 a := nextchar; end loop; if SF then return “yes”; else return “no”; end if;,與算法2.1的三點(diǎn)區(qū)別：模擬DFA模擬NFA 1. 開始 初態(tài)(s)初態(tài)集(S) 2. 下一狀態(tài)轉(zhuǎn)移 下一狀態(tài)下一狀態(tài)集 3. 結(jié)束 s is in F SF,算法2.5,8,2.4.2 NFA到DF

8、A（續(xù)3）,例2.13 在NFA上識(shí)別輸入序列abb和abab,識(shí)別abb: 1 計(jì)算初態(tài)集： -閉包(0) = 0,1,2,4,7， A 2 從A出發(fā)經(jīng)a到達(dá)： -閉包(smove(A, a) = 3,8,6,7,1,2,4， B 3 從B出發(fā)經(jīng)b到達(dá)： -閉包(smove(B, b) = 5,9,6,7,1,2,4， C 4 從C出發(fā)經(jīng)b到達(dá)： -閉包(smove(C, b) = 5,10,6,7,1,2,4， D 5 結(jié)束且D10=10，接受。識(shí)別的路徑為：A a B b C b D,識(shí)別abab: 初態(tài)集：-閉包(s0)=0,1,2,4,7 A 從A出發(fā)經(jīng)a到達(dá)：-閉包(smove(A

9、, a) = 3,8,6,7,1,2,4 B 從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b) = 5,9,6,7,1,2,4 C 從C出發(fā)經(jīng)a到達(dá)：-閉包(smove(C, a) = 3,8,6,7,1,2,4 B 從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b) = 5,9,6,7,1,2,4 C 識(shí)別路徑為：A a B b C a B b C。由于C10=，所以不接受,9, “子集法”構(gòu)造DFA 2.4.2 NFA到DFA（續(xù)4）,“并行”模擬NFA的弱點(diǎn)：每次動(dòng)態(tài)計(jì)算下一狀態(tài)轉(zhuǎn)移的集合，效率低。 改進(jìn)方法：將NFA上的全部路徑均確定化并且記錄下來，得到與NFA等價(jià)的DFA。,回顧從甲地

10、到乙地的路徑，它的數(shù)學(xué)模型實(shí)質(zhì)上是一個(gè)NFA （右上） 。 可以找到一個(gè)等價(jià)的DFA（右下），它們識(shí)別的路徑均是： ccccbcbb,例2.14 用DFA識(shí)別cc和cbc： 甲 c 1,2 c 3,乙， 接受 甲 c 1,2 b 3 c ?，不接受,優(yōu)點(diǎn)： 1. 消除了不確定性（將NFA的下一狀態(tài)集合并為一個(gè)狀態(tài)） 2. 無(wú)需動(dòng)態(tài)計(jì)算狀態(tài)集合（針對(duì)模擬NFA的算法）,10,算法2.5 從NFA構(gòu)造DFA（子集法） 2.4.2 NFA到DFA（續(xù)5）,輸入 NFA N 輸出 等價(jià)的DFA D。初態(tài)含有NFA初態(tài)，終態(tài)集是含有NFA終態(tài)的狀態(tài)集合 方法 用下述過程構(gòu)造DFA ：,-閉包(s0)是D

11、states僅有的狀態(tài)，且尚未標(biāo)記; while Dstates有尚未標(biāo)記的狀態(tài)T loop 標(biāo)記T; for 每一個(gè)輸入字符a loop U := -閉包(smove(T，a); if U不在Dstates中 then U作為尚未標(biāo)記的狀態(tài)加入Dstates; end if; DtranT，a := U;- 記錄狀態(tài)轉(zhuǎn)移 end loop; end loop; ,與算法2.3比較：記錄了所有狀態(tài)與狀態(tài)轉(zhuǎn)移,兩個(gè)數(shù)據(jù)結(jié)構(gòu)： Dstates(狀態(tài))，Dtran(狀態(tài)轉(zhuǎn)移),11,2.4.2 NFA到DFA（續(xù)6）,例2.15 用算法2.5構(gòu)造(a|b)*abb的DFA,-閉包(0)=0,1,2,

12、4,7* A -閉包(smove(A, a)=3,8,6,7,1,2,4* B -閉包(smove(A, b)=5,6,7,1,2,4* C -閉包(smove(B, a)=3,8,6,7,1,2,4 B -閉包(smove(B, b)=5,9,6,7,1,2,4* D -閉包(smove(C, a)=3,8,6,7,1,2,4 B -閉包(smove(C, b)=5,6,7,1,2,4 C -閉包(smove(D, a)=3,8,6,7,1,2,4 B -閉包(smove(D, b)=5,10,6,7,1,2,4* E -閉包(smove(E, a)=3,8,6,7,1,2,4 B -閉包(

13、smove(E, b)=5,6,7,1,2,4 C,問題：用哪個(gè)DFA識(shí)別輸入序列？,識(shí)別abb和abab： A a B b D b E 接受 A a B b D a B b D 不接受,12,2.4.3 最小化DFA,定義2.7 對(duì)于任何兩個(gè)狀態(tài)t和s，若從一狀態(tài)出發(fā)接受輸入字符串，而從另一狀態(tài)出發(fā)不接受，或者從t出發(fā)和從s出發(fā)到達(dá)不同的接受狀態(tài)，則稱對(duì)狀態(tài)t和s是可區(qū)分的。 ,反方向思考定義2.7： 設(shè)想任何輸入序列對(duì)s和t均是不可區(qū)分的，則說明從s出發(fā)和從t出發(fā)，分析任何輸入序列均得到相同結(jié)果。 因此，s和t可以合并成一個(gè)狀態(tài)。,引入一個(gè)“可區(qū)分”的概念：,正規(guī)式NFADFA,13,算法

14、2.6 最小化DFA的狀態(tài)數(shù) 2.4.3 最小化DFA（續(xù)1）,輸入 DFA D=S，move，s0，F(xiàn)。 輸出 等價(jià)的D=S，move，s0，F(xiàn)，（D狀態(tài)數(shù)最少） 方法 執(zhí)行如下步驟：,1. 初始劃分=S-F，F(xiàn)1，F(xiàn)2，.，F(xiàn)i是F的子集，接受不同記號(hào)；,2. 應(yīng)用下述過程構(gòu)造新的劃分new： for 的每一個(gè)組G loop 劃分G，G的兩個(gè)狀態(tài)s和t在同一組中的充要條件是: a.(move(s,a)Gimove(t,a)Gi)；- Gi是中某個(gè)組 用新劃分的組替代G，形成新的劃分new； end loop；,3. 若new=，令final=，轉(zhuǎn)4；否則令=new并重復(fù)步驟2；,4. 在f

15、inal每個(gè)組Gi中選一個(gè)代表si，使得D中從Gi所有狀態(tài)出發(fā)的狀態(tài)轉(zhuǎn)移在D中均從si出發(fā)，D中所有轉(zhuǎn)向Gi中的狀態(tài)轉(zhuǎn)移在D中均轉(zhuǎn)向si；含有D中s0的狀態(tài)組G0的代表s0稱為D的初態(tài)，D中所有含F(xiàn)中狀態(tài)的Gj的代表sj構(gòu)成D的終態(tài)集F；,5. 刪除死狀態(tài)，即不是終態(tài)且對(duì)所有輸入字符均轉(zhuǎn)向其自身，或從初態(tài)不可到達(dá)的狀態(tài)。 ,14,最小化DFA算法的主要步驟： 2.4.3 最小化DFA（續(xù)2）, 初始劃分：終態(tài)與非終態(tài)； 利用可區(qū)分的概念，反復(fù)分裂劃分中的組Gi，直到不可再分裂； 由最終劃分構(gòu)造D，關(guān)鍵是選代表和修改狀態(tài)轉(zhuǎn)移； 消除可能的死狀態(tài)和不可達(dá)狀態(tài)。,例2.17 用算法2.6化簡(jiǎn)DFA,

16、m(A,a)=B, m(A,b)=C m(B,a)=B, m(B,b)=D m(C,a)=B, m(C,b)=C m(D,a)=B, m(D,b)=E m(E,a)=B, m(E,b)=C,1初始化劃分1=ABCD，E 2根據(jù)算法中步驟2，反復(fù)分裂劃分中的組： m(D, b)=E 2=ABC，D，E m(B, b)=D 3=AC，B，D，E 3？ 于是：final=AC，B，D，E,4根據(jù)final構(gòu)造D： 選代表，用A代表AC組； 修改狀態(tài)轉(zhuǎn)移：,m(A,a)=B, m(A,b)=A m(B,a)=B, m(B,b)=D m(D,a)=B, m(D,b)=E m(E,a)=B, m(E,b)

17、=A,用0、1、2、3代替A、B、D、E，得：,15,2.4.4 由DFA構(gòu)造詞法分析器, 表驅(qū)動(dòng)型的詞法分析器,其中，需要： 1. 有適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)存放DFA； 2.修改算法2.1，以適應(yīng)實(shí)際輸入： 識(shí)別整個(gè)文件，而不是一個(gè) 記號(hào)； 滿足最長(zhǎng)匹配原則。,對(duì)于輸入序列： result := a + b 正確的識(shí)別： id := id + id 錯(cuò)誤的識(shí)別： 1. 僅識(shí)別一個(gè)： id （result） 2. 不滿足最長(zhǎng)匹配：id id .（r或re或res . ）,16, 直接編碼的詞法分析器,在表驅(qū)動(dòng)的詞法分析器中，DFA是被動(dòng)的，需要一個(gè)驅(qū)動(dòng)器來模擬DFA的行為，以實(shí)現(xiàn)對(duì)輸入序列的分析。 直

18、接編碼的詞法分析器，將DFA和DFA識(shí)別輸入序列的過程合并在一起，直接用程序代碼模擬DFA識(shí)別輸入序列的過程。 問題： 如何用程序模擬DFA識(shí)別輸入序列的過程？即如何用程序模擬DFA的狀態(tài)和它的狀態(tài)轉(zhuǎn)移？,1. 狀態(tài)和狀態(tài)轉(zhuǎn)移與語(yǔ)句的對(duì)應(yīng)關(guān)系 初態(tài)程序的開始； 終態(tài)程序的結(jié)束（return語(yǔ)句，不同終態(tài)return不同記號(hào)）； 狀態(tài)轉(zhuǎn)移分情況或者條件語(yǔ)句（case/if）； 環(huán)循環(huán)語(yǔ)句（loop）； return滿足最長(zhǎng)匹配原則。,17, 直接編碼的詞法分析器（續(xù)1）,2. 識(shí)別(a|b)*abb的程序框架,main() char buf=abba#, *ptr=buf; while (*pt

19、r!=# ) l0: while (*ptr=b) ptr+;/ state 0 l1: while (*ptr=a) ptr+;/ state 1 switch (*ptr) case a: goto l1; case b: ptr+; switch (*ptr)/ state 2 case a: goto l1; case b: ptr+; switch (*ptr)/ state3 case a: goto l1; case b: goto l0; case #: coutyesendl; return; default: break; default: break; default: break; break; / 遇到非法字符 cout no endl; ,18, 兩類分析器的比較,2.4.5 詞法分析器生成器簡(jiǎn)介（上機(jī)課中再介紹）, 構(gòu)造詞法分析器的全過程均有算法： 正規(guī)式NFADFA最小化DFA詞法分析器（分析表） LEX的基本結(jié)構(gòu) 根據(jù)正規(guī)式構(gòu)造的分析表驅(qū)動(dòng)器框架（不變的） 利用LEX構(gòu)造詞法分析器的關(guān)鍵 用LEX提供的正規(guī)式集合設(shè)計(jì)記號(hào)的模式； 用LEX提供的語(yǔ)義支持識(shí)別記號(hào)或指出輸入中的錯(cuò)誤