編譯原理第七講

1、Compiler Construction Principles關(guān)于關(guān)于有窮自動(dòng)機(jī)我們將討論如下題目我們將討論如下題目確定的有窮自動(dòng)機(jī)DFA不確定的有窮自動(dòng)機(jī)NFANFA的確定化DFA的最小化Compiler Construction Principles1.確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)DFADFA定義：一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（K，f，S，Z）其中1.K是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2.是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為輸入符號(hào)表；Compiler Construction PrinciplesDFA定義定義3.f是轉(zhuǎn)換函數(shù)，是

2、在KK上的單值映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)；4.SK是唯一的一個(gè)初態(tài)；5.Z K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。Compiler Construction Principles一個(gè)一個(gè)DFA 的例子：的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定義為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QCompiler Construction Principles

3、DFA 的狀態(tài)圖表示的狀態(tài)圖表示bSUVQaaaba，bCompiler Construction PrinciplesDFA 的矩陣表示abSUVUQVVUQQQQ字符字符狀態(tài)狀態(tài)0001Compiler Construction Principles練習(xí) 設(shè)（ ， ， ， ，）其中（，），（，）3（，），（，）（，），（，）（，），（，）l構(gòu)造狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換矩陣Compiler Construction Principles a b 0 1 2 1 3 2 2 1 3 3 3 3 轉(zhuǎn)移矩陣0132aaaabbbb3狀態(tài)轉(zhuǎn)換圖0 0 0 1Compiler Construction P

4、rinciples例 構(gòu)造DFA作為一個(gè)奇偶校驗(yàn)器，識(shí)別0，1組成的含有奇數(shù)個(gè)1的符號(hào)串Compiler Construction PrinciplesDFA M 接受的語言* *上的符號(hào)串上的符號(hào)串t t被被DFADFA M M接受接受M=（K，f，S，Z）若t *，f(S，t)=P，其中S為 M的開始狀態(tài)，P Z，Z為終態(tài)集。則稱t為DFA M所接受接受（識(shí)別識(shí)別）.Compiler Construction Principles對(duì)于中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串等于t，則稱t可為DFA M所識(shí)別(讀出或接受)。DFA

5、M所能接受的符號(hào)串的全體即NFA M所識(shí)別的語言記為 L(M)bSUVQabbabaa,Compiler Construction Principles例例：證明證明t=baab被下圖的被下圖的DFA所接受所接受。f（S，baab）=f（f（S，b），），aab） = f（V，aab）= f（f（V，a），），ab） =f（U，ab）=f（f（U，a），），b） =f（Q，b）=QQ屬于終態(tài)。屬于終態(tài)。得證。得證。bSUVQabba, baaCompiler Construction PrinciplesDFA M所能接受的符號(hào)串的全體記為L(zhǎng)(M).對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M，如果L(M)=

6、L(M)，則稱M與M是等價(jià)的. 結(jié)論： 上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的確定有窮自動(dòng)機(jī)M，使得V=L(M)。Compiler Construction PrinciplesDFA的行為很容易用程序來模擬.DFA M=（K，f，S，Z）的行為的模擬程序K:=S；c:=getchar;while ceof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes) else return (no)Compiler Construction PrinciplesDFA的確定性表現(xiàn)在1）轉(zhuǎn)換函數(shù)f:KK是一個(gè)單值函數(shù)，也就是說，對(duì)任

7、何狀態(tài)kK，和輸入符號(hào)a，f(k,a)唯一地確定了下一個(gè)狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個(gè)輸入字符，那末任何一個(gè)狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個(gè)不同的輸入字符標(biāo)記。2）初始狀態(tài)是唯一的Compiler Construction Principles不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)NFA定義NFA M=K，f，S，Z，其中K為狀態(tài)的有窮非空集， 為有窮輸入字母表，f為K * 到K的子集（2 K）的一種映射，SK是初始狀態(tài)集，Z K為終止?fàn)顟B(tài)集.Compiler Construction Principles例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，

8、0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，ZCompiler Construction Principles狀態(tài)圖表示SPZ00,1111Compiler Construction Principles矩陣表示矩陣表示矩陣表示01SPS,Z0PZ0ZPP1簡(jiǎn)化為01SPS,Z0P.Z0ZPP1Compiler Construction Principlesf為為K * 到到K的子集（的子集（2 K）的一種映射）的一種映射具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī) 123abcCompiler Construction Principles有如下定理有如下定理: 對(duì)任何一個(gè)具有

9、轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFA N，一定存在一個(gè)不具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFA ，使得L(M)=L(N)。與上例等價(jià)的一個(gè)NFA.2acbb31acacbbCompiler Construction Principles NFA M 所識(shí)別的語言所識(shí)別的語言 對(duì)于中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為的弧)等于t，則稱t可為NFA M所識(shí)別(讀出或接受)。NFA M所能接受的符號(hào)串的全體即NFA M所識(shí)別的語言記為 L(M)Compiler Construction Principles注意：若M的某些結(jié)既是

10、初態(tài)結(jié)又是終態(tài)結(jié)， 或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均為，那么空字可為M所接受。Compiler Construction Principles DFA是NFA的特例.對(duì)每個(gè)NFA N一定存在一個(gè)DFA ，使得 L(M)=L(N)。對(duì)每個(gè)NFA N存在著與之等價(jià)的DFA M。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法子集法.與某一與某一NFA等價(jià)的等價(jià)的DFA不唯一不唯一.Compiler Construction Principles從NFA的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)，NFA到相應(yīng)的

11、DFA的構(gòu)造的基本思路是： DFADFA的每一個(gè)狀態(tài)對(duì)應(yīng)的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài). DFA使用它的狀態(tài)去記錄在NFA讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài).Compiler Construction Principles定義對(duì)狀態(tài)集合定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：的幾個(gè)有關(guān)運(yùn)算：1. 狀態(tài)集合狀態(tài)集合I I的的-閉包閉包，表示為-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達(dá)的狀態(tài)的集合。 狀態(tài)集合I的任何狀態(tài)S都屬于-closure(I)。2. 狀態(tài)集合狀態(tài)集合I I的的a a弧轉(zhuǎn)換弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可

12、從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。Compiler Construction Principles狀態(tài)集合狀態(tài)集合I的有關(guān)運(yùn)算的例子的有關(guān)運(yùn)算的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaaCompiler Construction Principles NFA確定化算法確定化算法: 假設(shè)NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造一個(gè)DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：1. M的狀態(tài)

13、集S由K K的一些子集的一些子集組成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的狀態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即對(duì)于子集S1, S2= S2, S1,來說，S的狀態(tài)就是S1 S2；Compiler Construction Principles2 M和N的輸入字母表是相同的，即是；3 轉(zhuǎn)換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)為M的開始狀態(tài)；5 St=Si Sk. Se，其中Si

14、 Sk. SeS且Si , Sk,. SeKtCompiler Construction PrinciplesNFA的確定化的確定化 例子4f35621iaaaabbbbIaIbi,1,21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fSABACBBADCCEDFDEFDFCE4f35621iaaaab

15、bbbCompiler Construction Principles 等價(jià)的等價(jià)的DFAaCDBAEFSbaaaaabbbbbabFCompiler Construction Principles確定有窮自動(dòng)機(jī)的化簡(jiǎn)確定有窮自動(dòng)機(jī)的化簡(jiǎn) 說一個(gè)有窮自動(dòng)機(jī)是化簡(jiǎn)了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個(gè)是互相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。 所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。 Compiler Construction Prin

16、ciples DFA的最小化就是尋求最小狀態(tài)的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒有多余狀態(tài)(死狀態(tài))沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）兩個(gè)狀態(tài)s和t可區(qū)別：不滿足兼容性同是終態(tài)或同是非終態(tài)傳播性從s出發(fā)讀入某個(gè)aa和從 t出發(fā)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。Compiler Construction Principles C和和D同是終態(tài)同是終態(tài),讀入讀入a到達(dá)到達(dá)C和和F, C和和F同是終態(tài)同是終態(tài), C和和F讀入讀入a都到達(dá)都到達(dá)C,讀入讀入b都到達(dá)都到達(dá)E. C和和D等價(jià)等價(jià)aCDBAEFSbaaaaabbbbbabFCompiler Construction Princip

17、les最小狀態(tài)最小狀態(tài)DFA對(duì)于一個(gè)DFA M =（K,f, k0,kt)，存在一個(gè)最小狀態(tài)DFA M =（K,f, k0,kt)，,使L(M)=L(M). 結(jié)論接受L的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)是唯一的。Compiler Construction Principles“分割法分割法”DFA的最小化算法的核心 把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的. 算法假定每個(gè)狀態(tài)射出的弧都是完全的,否則,引入一個(gè)新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對(duì)所有輸入，該狀態(tài)射出的弧還回到自己.Compiler

18、 Construction Principles DFA的最小化算法的最小化算法 DFA M =（K,f, k0, kt),最小狀態(tài)DFA M 1.構(gòu)造狀態(tài)的一初始劃分： 終態(tài)kt 和非終態(tài)K- kt兩組(group) 2.對(duì)施用過程過程PPPP 構(gòu)造新劃分new 3. 如new =,則令 final= 并繼續(xù)步驟4，否則:=new重復(fù)2 . 4.為final中的每一組選一代表，這些代表構(gòu)成M的狀態(tài)。若k是一代表且f(k,a)=t,令r是t組的代表，則M中有一轉(zhuǎn)換f(k,a)=rCompiler Construction Principles M 的開始狀態(tài)是含有S0的那組的代表 M 的終態(tài)是

19、含有F的那組的代表 5.去掉M中的死狀態(tài).Compiler Construction Principles過程PP : Construction of Construction of newnewFor each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to state

20、s in the same group of ;/*at worst, a state will be in a subgroup by itself*/2.replace G in n e w by the set of all subgroups formed end Compiler Construction Principles DFA的最小化的最小化例子例子0:S,A,B C,D,E,F1:S,A,B C,D,E,F 2: CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaaCompiler Construction Principles二 定義31

21、 一個(gè)確定的有限自動(dòng)機(jī) M（記 作DFA M）是一個(gè)五無組 （，0，），其中（）是一個(gè)有限狀態(tài)集合。（）是一個(gè)字母表，它的每個(gè)元素稱 為一個(gè)輸入符號(hào)。（）0，0 稱為初始狀態(tài)。（），稱為終結(jié)狀態(tài)集合。（）是一個(gè)從 到的單值映射 (，)（,，） 表示當(dāng)前狀態(tài)為q,輸入符號(hào)為a時(shí)，自動(dòng)機(jī)將轉(zhuǎn)換到下一個(gè)狀態(tài)，稱為的一個(gè)后繼。Compiler Construction Principles例33 設(shè)（， ，）其中（，），（，）3（，），（，）（，），（，）（，），（，）三 一個(gè)有三種表示：（1）象上面，用轉(zhuǎn)換函數(shù)；（2）轉(zhuǎn)移矩陣；（3）狀態(tài)轉(zhuǎn)換圖。Compiler Construction Princ

22、iplesab012132213333轉(zhuǎn)移矩陣0132aaaabbbb3狀態(tài)轉(zhuǎn)換圖易存儲(chǔ)Compiler Construction Principles四 DFA M 接受的語言 如果對(duì)所有*，以下述方式遞歸地?cái)U(kuò)張的定義 （，），(，）(，w），）， 對(duì)任何 ,，則有（）*，若存在， 使（，） 對(duì)于例3.3的DFA M和w=baa， (0，ba）=(2,a）= (1,）=3Compiler Construction Principles 從狀態(tài)轉(zhuǎn)換圖看，從初態(tài)出發(fā)，沿任一條路徑到達(dá)接受狀態(tài)，這條路徑上的弧上的標(biāo)記符號(hào)連接起來構(gòu)成的符號(hào)串被接受。0123aaaabbbbCompiler Cons

23、truction Principles 五. DFA M 判定 ?(）的算法： 輸入：$ q:=q0; a:=nextchar; WHILE a$ DO BEGIN q:=move(q,a); a:=nextchar; END; IF q IN F THEN return (”yes) ELSE return (”no);Compiler Construction Principles3.2.2 手工構(gòu)造識(shí)別單詞的DFA m 根椐DFA識(shí)別單詞的定義，在研究給定程序語言單詞結(jié)構(gòu)的基礎(chǔ)上，能直接構(gòu)造出識(shí)別它的DFA m。例如：對(duì)于Pascal, 標(biāo)識(shí)符：字母開始的字母數(shù)字串。 整數(shù)：非空數(shù)字串。

24、 無符號(hào)實(shí)數(shù)（用表示數(shù)字）： （a) dd.d dE(+- ) dd (b) ddE(+- ) dd (c) dd.d dCompiler Construction Principles1342字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字Pascal 標(biāo)識(shí)符Pascal整數(shù)和實(shí)數(shù)0134652700dddddddEE+7*Compiler Construction Principles3.2.3 編寫詞法分析程序 根據(jù)畫出的狀態(tài)轉(zhuǎn)換圖（識(shí)別單詞的）構(gòu)造詞法分析程序，每個(gè)狀態(tài)對(duì)應(yīng)一段程序，完成到達(dá)此狀態(tài)的工作；詞法分析程序的控制程序模擬狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換。 在識(shí)別標(biāo)識(shí)符的過程中，要拼寫出來，并和保留字區(qū)別開來；在識(shí)別

25、常數(shù)的過程中，要把它轉(zhuǎn)換成機(jī)器表示以作為屬性值。Compiler Construction Principles 使用下面的全局變量和過程：1. Character 2. Token3. Getchar 4. getbc5. Concatenation6. letter,digit7. Reserve 8. Retract9. buildlist10. returnCompiler Construction Principles作業(yè)： 3.2 3.3解釋下面每個(gè)有限自動(dòng)機(jī)識(shí)別的語言是什磨？(a)12345678900000001111111(b)12345aaaaaCompiler Const

26、ruction Principles( c )0120001113.4 給出接受下列在字母表0，1上的語言的DFA: ( a ) 所有以00結(jié)束的串的集合； （b) 所有具有三個(gè)0的串的集合。0Compiler Construction Principles3. 3 有限自動(dòng)機(jī) FA m 3. 3. 1 非確定的 有限自動(dòng)機(jī)NFA m 一. NFA m 二. FA 的等價(jià)定理 三. 例3.3，用DFA模擬NFA的動(dòng)作 四. 從一個(gè)NFA構(gòu)造DFA的算法3. 3. 2 確定的 有限自動(dòng)機(jī)的化簡(jiǎn) 一.何謂確定的 有限自動(dòng)機(jī)的化簡(jiǎn) 二.等價(jià)狀態(tài)的定義 三.確定的 有限自動(dòng)機(jī)的化簡(jiǎn)方法Compiler

27、 Construction Principles一. 非確定的有限自動(dòng)機(jī)NFA m定義32 非確定有限自動(dòng)機(jī)是一個(gè)五元組 （，q，）其中，q，的意義和的定義一樣，而是一個(gè)從到的子集的映射，即： 類似FA，NFA m可用狀態(tài)轉(zhuǎn)換圖表示，可定義NFA m接受的語言。Compiler Construction Principles二. FA的等價(jià)性定理3 . 1 對(duì)任何一個(gè)NFA m，都存在一個(gè) DFA m，使L(m)=L(m)證明思想：用m的一個(gè)狀態(tài)對(duì)應(yīng)m的一個(gè)狀 態(tài)集合，用這種方法，能從一個(gè)NFA m 構(gòu)造一個(gè)DFA m，稱作子集構(gòu)造法。例3 . 2 NFAm=(0,1 , q0,q1,q0,

28、),其中 (q0,0)= q0,q1, (q0,1)= q1 (q1,0)= (q1,0)= q0,q1Compiler Construction Principlesq0q0q100111q0q0q0q1q0,q10110,1L(m)=L(m)=0,1+100,1*Compiler Construction Principles014236578910aabbb012470,1,2，4,7a3a8612473,8,6,1,2,4,7b5b961247a5,9,6,1,2,4,7bb56124b105,10,6,1,2,4,77b例3.3從具體例子的討論,提煉出從NFA構(gòu)造DFA的算法。Com

29、piler Construction Principles四. 從NFA構(gòu)造DFA的算法 1.closure(S) 的定義和算法 從S中任一狀態(tài)出發(fā)，僅沿弧到達(dá)的狀態(tài)集合，T=S ( edge(t, ), 其中，edge(t, a)是NFA中從狀態(tài)t出發(fā)，僅沿a弧到達(dá)的狀態(tài)集合。如下計(jì)算T： T:=S; REPEAT T:=T ; T:=T ( edge(t, ) (tT) UNTIL T=TtTCompiler Construction Principles2. DFA的轉(zhuǎn)移函數(shù) DFAedge(d, a)= closure( edge(t, a)其中， d是NFA的狀態(tài)集， a 。 從NF

30、A構(gòu)造DFA，是對(duì)于NFA的所有輸入,，用DFA模擬NFA的動(dòng)作，令t1是NFA的初態(tài)，DFA的初態(tài)d1= closure(t1) ，若， dj= DFAedge(di, a),那磨，從di到dj存在一條用a標(biāo)識(shí)的弧。算法3,2 從一個(gè)NFA構(gòu)造一個(gè)DFAtdCompiler Construction PrinciplesStates1 :=-closure(t1); p:=1; j:=1;WHILE j=p DO for each a e:=DFAedge(statesj,a); IF e=statesi for some i=p THENtransj,a=i ELSE p: =p+1; s

31、tatesp:=e; transj,a:=p; ; ; j:=j+1; Compiler Construction Principles01436578910abbb2astatesab3,8,6,1,2,4,70,1,2,4,725,6,1,2,4,7325,9,6,1,2,4,742325,10,6,1,2,4,7523Compiler Construction Principles3.3.2 確定的有限自動(dòng)機(jī)的化簡(jiǎn)一. 何謂確定的有限自動(dòng)機(jī)的化簡(jiǎn) 所謂一個(gè)DFA m=(, Q, q0, F, )的化簡(jiǎn)是指尋找一個(gè)狀態(tài)數(shù)比較少的DFA m,使L(m)=L(m)。而且可以證明， 存在一個(gè)最

32、少狀態(tài)的DFA m, 使L(m)=L(m)。二.等價(jià)狀態(tài)的定義 設(shè)p,q Q ，若對(duì)任何w * , (p,w) F 當(dāng)且僅當(dāng) (q,w) F ，則稱p和q是等價(jià)狀態(tài)。否則，稱p和q是可區(qū)別的。Compiler Construction Principlesq1q2q3q4q1q2q3q6q4q5q7baaaaaaaaaaabbb,bbbbbbbCompiler Construction Principles1.等價(jià)狀態(tài)定義了狀態(tài)集合上的等價(jià)關(guān)系。因此，狀態(tài)集合能被劃分成等價(jià)類；2 .兩個(gè)狀態(tài)p和q等價(jià)應(yīng)滿足如下條件：（a）一致性條件， p和q必須同時(shí)或?yàn)榻邮?狀態(tài)或?yàn)榉墙邮軤顟B(tài)；（b）蔓延性條

33、件，對(duì)于a ， （p,a)=r, （q,a)=s, r和s必須等價(jià); 相反, r和s不等價(jià), p和q不等價(jià)。 判定兩個(gè)狀態(tài)p和q不等價(jià)，只要o找到一個(gè)w*， 使（p,w)F 且（q,w) F，或者相反。 W稱為判別序列。Compiler Construction Principles三. 方法： 構(gòu)造一張表，對(duì)每一個(gè)狀態(tài)對(duì)（qi,qj）（ij）有一表項(xiàng)，每當(dāng)發(fā)現(xiàn)一對(duì)狀態(tài)不等價(jià)時(shí)，就放一個(gè)x到相應(yīng)表項(xiàng)中。1 . 根據(jù)一致性條件，在每一個(gè)對(duì)應(yīng)于終結(jié)狀態(tài)和非終結(jié)狀態(tài)的表項(xiàng)中放上一個(gè)x。2 .根據(jù)蔓延性性條件，對(duì)每一個(gè)狀態(tài)對(duì)（p,q），若a，（p,a）=r， （q,a）=s，r和s不等價(jià)，則（p,q）

34、不等價(jià)。重復(fù)2，直到?jīng)]有新的不等價(jià)狀態(tài)對(duì)出現(xiàn)。Compiler Construction Principlesq8q7q6q5q1q2q311110111000000 xxxxxxq2q3q5q6q7q8q1 q2 q3 q5 q6 q7xxxxxxxxxxxxxCompiler Construction Principles3.4 正規(guī)表達(dá)式 用正規(guī)表達(dá)式描述單詞，把它轉(zhuǎn)換成識(shí)別裝置-有限自動(dòng)機(jī)。3.4 .1正規(guī)表達(dá)式與單詞 一.正規(guī)表達(dá)式的定義 二.正規(guī)表達(dá)式的代數(shù)性質(zhì) 三.正規(guī)定義式 四.例示，用正規(guī)定義式描述單詞3.4 .2 正規(guī)表達(dá)式與有限自動(dòng)機(jī)的等價(jià)性 L( r )=L(m)Com

35、piler Construction Principles3.4.2 正規(guī)表達(dá)式與有限自動(dòng)機(jī)的等價(jià)性 單詞結(jié)構(gòu)用正規(guī)表達(dá)式描述，用機(jī)械的方法（程序），把正規(guī)表達(dá)式變換成等價(jià)的有限自動(dòng)機(jī)。定理3.2 設(shè)r是上一個(gè)正規(guī)表達(dá)式，則存在一個(gè)FA m接受L( r )。反之亦然。證 對(duì)正規(guī)表達(dá)式r的運(yùn)算數(shù)目作歸納。設(shè)r具有零個(gè)運(yùn)算，則或r=或r= 或r=a q0q0q1q0q1ar=r= r=aCompiler Construction Principles設(shè)結(jié)論對(duì)少于i(i1)個(gè)運(yùn)算的正規(guī)表達(dá)式r成立。當(dāng)r有i個(gè)運(yùn)算時(shí)，有三種情況： 情況1 r=r1r2 情況2 r=r1r2 情況3 r=r1* 有 m

36、1=(1,Q1,q1,F!,1), m2=(2,Q2,q2,F2,2) 且L(m1)=L( r 1), L(m2)=L(r2) ，由m1和m2構(gòu)造m,使得 L(m)=L( r ).構(gòu)造方法圖示如下：q0q1f1f2q2f0m2m1r=r1r2Compiler Construction Principlesq0q1f1q2f0m2m1f2q1f1r=r1r2r=r1* 上述證明方法，是對(duì)于一個(gè)正規(guī)表達(dá)式r,構(gòu)造一個(gè)FA m,且L(m)=L( r )的算法,但假定知道r的計(jì)算順序。 正規(guī)表達(dá)式r的語法是上下文無關(guān)文法。Compiler Construction Principles例3.5構(gòu)造與下

37、列正規(guī)式 ( c) r=01*1 等價(jià)的有限自動(dòng)機(jī)。語法樹如左下圖。*011q0q10q2q31q2q3q5q41Compiler Construction Principles01q0q1q6q71q2q5q4q0q1q4q2q3q3q6q7110q8q5q9Compiler Construction Principles 對(duì)于上任一NFA m，能構(gòu)造上一個(gè)正規(guī)表達(dá)式r，使得L( r )=L(m)。 把轉(zhuǎn)換圖的概念拓廣，每條弧上可以用一個(gè)正規(guī)式標(biāo)記。首先，在m的轉(zhuǎn)換圖上加進(jìn)x,y兩個(gè)結(jié)。從x用弧連接到m的所有初態(tài)結(jié)點(diǎn)，從m的所有接受態(tài)結(jié)點(diǎn)用弧連接到y(tǒng)，從而構(gòu)成一個(gè)新的NFA m，L(m)=L

38、(m)。下面，逐步消去NFA m中的狀態(tài)結(jié)點(diǎn)，直至剩下x,y為止。在消結(jié)的過程中，逐步用正規(guī)式標(biāo)記弧。消結(jié)的過程是直觀的，只需反復(fù)使用下面的替換規(guī)則。Compiler Construction Principlesabcacacacabcacr1r2r2r2r1r1r3r1r2r1r2r1r2*r3替換規(guī)則代之以代之以代之以Compiler Construction Principles3.5 正規(guī)文法與有限自動(dòng)機(jī)(FA)的等價(jià)性 L(G)=L(m)定理3.3 對(duì)于每一個(gè)右線性正規(guī)文法或左 線性正規(guī)文法G，都存在一個(gè)FA m，使 L(m)=L(G)證 給定右線性正規(guī)文法G=(VT,VN,S,P

39、),設(shè)f VN ，令m=(VT ,Q, S, F, ), 其中，F(xiàn)= fQ= VNf, 轉(zhuǎn)移函數(shù) 定義如下： (a) Aa, (A,a)=f (b) A aA1aA2 . aAn (A,a)= A1,A2 ,. ,An Compiler Construction Principles 給定左線性正規(guī)文法G=(VT, VN, S, P), 設(shè)q0VN ，令m=(VT ,Q, q0 ,S , ), 其中，Q= VN q0 , 轉(zhuǎn)移函數(shù) 定義如下： (a) Aa, (q0,a)=A (b) A1 A,a, A2Aa , An Aa (A,a)= A1, A2 ,. , A n定理3.4 對(duì)于每一個(gè)D

40、FA m，都存在一個(gè)右 線性正規(guī)文法G和一個(gè)左線性正規(guī)文法G， 使L(m)=L(G)=L(G)。證 設(shè)m=(, VN , S,F, ),右線性正規(guī)文法G的構(gòu)造方法如下：Compiler Construction Principles若sF, G=(,V N ,S,P), P的定義如下：對(duì)任何a 及A,B VN, 若有(A,a)=B, 則 (a) B F, A aB (b) B F A aaB若s F, S0 V N , S0 S 構(gòu)造左線性正規(guī)文法， P的定義如下：對(duì)任何a 及A1,A2 VN, 有(A1,a)=A2, 則 (a) A1是初態(tài)， A2 a (b) A1不是初態(tài), A2 A1aC

41、ompiler Construction Principles例3.6 DFA m 右線性正規(guī)文法G NFA m左線性正規(guī)文法G ADCB0,1111000A00B 1DB 0D 1CC 0 0B 1DD 0D 1DCompiler Construction PrinciplesADCB0,1111000S0C0B 0C0C B 1D 1B0 C1 D0 D1f00NFA m左線性正規(guī)文法Compiler Construction Principles3.6詞法分析程序的自動(dòng)構(gòu)造工具LEX簡(jiǎn)介一.原理 單詞的結(jié)構(gòu)用正規(guī)式描述 正規(guī)式 NFA DFA min DFA二.用LEX建立詞法分析程序的

42、過程LEX編譯器LEX源程序lex.1Lex.yy.cCompiler Construction PrinciplesC編譯器Lex.yy.ca.outa.out輸入流單詞序列三.lex源程序 lex源程序由三部分組成Compiler Construction Principles聲明%翻譯規(guī)則%輔助過程聲明包括變量，顯明常量和正規(guī)定義式。 翻譯規(guī)則的形式為： p1 動(dòng)作1 p2 動(dòng)作2 p n 動(dòng)作nCompiler Construction Principles 每個(gè)pi是正規(guī)定義式的名子，每個(gè)動(dòng)作i是正規(guī)定義式pi識(shí)別某類單詞時(shí)，詞法分析器應(yīng)執(zhí)行動(dòng)作的程序段。用C書寫。 輔助過程是動(dòng)作需

43、要的，這些過程用C書寫，可以分別編譯。 詞法分析器返回給語法分析器一個(gè)單詞, ,把單詞的屬性值存放于全程變量yylval中。Compiler Construction Principles3.5 對(duì)于下列各語言，分別寫出它們的正規(guī) 表達(dá)式： (a) 字母表a,b,c上的串，其中第一個(gè)a先于 第一個(gè)b。 (b) 具有偶數(shù)個(gè)a的字母表a,b,c上的串。 ( c ) 0，1上的串，該串看成二進(jìn)制是4的 倍 數(shù)。 (d) 0，1上不含子串011的串。 (e) 0，1 上的串，有偶數(shù)個(gè)0和奇數(shù)個(gè)1。 (f) 英文字母組成的所有符號(hào)串，且順序 包 含五個(gè)元音字母。Compiler Construction Principles3.7 構(gòu)造等價(jià)于下列正規(guī)表達(dá)式的NFA (a) ab|(a|bb)a*b (b) (a|b)*|(bb)*Compiler Construction Principles識(shí)別識(shí)別Pl0單詞的單詞的FACompiler Construction PrinciplesNFA的確定化的確定化 More exampleCompiler Construction PrinciplesCompiler Construction PrinciplesCompiler Construction PrinciplesCompile