編譯原理第三章 詞法分析及詞法分析程序

1、編譯原理前后文無關(guān)文法和語言設(shè)計掃描器應(yīng)注意的問題詞法分析（3型）語法分析（2型）單詞的(Class, Value)二元組表示標(biāo)識符的長度限制和按“盡可能長”的識別策略超前搜索與回退, =, , 狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一右線性文法,令|VN|=K，1) 則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個狀態(tài).2) VN中的每個符號分別表示K個狀態(tài)2.1) G的開始符S為初態(tài)狀態(tài)3) 終止?fàn)顟B(tài),用F(VN)標(biāo)記F是新加(狀態(tài)）節(jié)點右線性文法=狀態(tài)轉(zhuǎn)換圖aA - aBABA - aAFaA -消除，重用上述規(guī)則AFotherA若A為起始符（GA）A產(chǎn)生式的消除SAXFabcotherYeSAXF

2、abcYeS - aA A - b|bX X - c|eYS - aAA - bX X - c|eY狀態(tài)圖=右線性文法文法G00-a1S-aA1-d1A-dA1-bA-b0-cS-c0-c2S-cB，2有出弧2-dB-d0132abcdd左線性文法=狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一左線性文法,令|VN|=K，1) 則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個狀態(tài).2) VN中的每個符號分別表示K個狀態(tài)2.1) G的開始符S為終止?fàn)顟B(tài)3) 起始狀態(tài),用R(VN)標(biāo)記R是新加(狀態(tài)）節(jié)點左線性文法=狀態(tài)轉(zhuǎn)換圖aA - BaBAA -的消除消除，重用上述規(guī)則RAother若A為起始符（GA）AA -

3、 aRAa不存在這種轉(zhuǎn)換狀態(tài)圖=左線性文法文法G31 - aAa1 - 1dAAd3 -1bSAb2 - cBc3 - 2dSBd0132abcdd狀態(tài)矩陣狀態(tài)矩陣Bij=BSi, aj=Sk當(dāng)前狀態(tài)，掃視字符，語義動作，后續(xù)狀態(tài)程序3-2識別無符號數(shù)的狀態(tài)矩陣語義 動作中的返回值ICON、FCON分別為整型數(shù)、浮點型數(shù)的值；一般說來，無符號數(shù)具有形式dmdm-1d0.d-1d-nEdd 即dmdm-1d0d-1d-n*10(dd-n);程序3-3關(guān)于狀態(tài)無符號數(shù)識別矩陣DFA的形式定義DFA: Deterministic Finite Automata 一個DFA M定義為M=(K, , f

4、, S0, Z)，其中1) K=狀態(tài)i2) =字母表，即輸入字符i3) f : K - K，f為函數(shù)，表示某狀態(tài)接受某個字母所到達(dá)的狀態(tài)，如：f(p,a) =q, p,qK, a 4) S0 K， S0為初態(tài)5) Z K，且Z ，Z為終態(tài)集合DFA例子0132abcdd左側(cè)的狀態(tài)圖，在數(shù)學(xué)上稱作DFA，其形式化定義為M=(K, , f, S0, Z)K=0 , 1 , 2 , 3 =a , b , c , d 源狀態(tài)輸入目的狀態(tài)0a10C21d11b32d3f: S0=0Z=2 , 3 函數(shù)f的推廣定義f f : K * - K，表示某狀態(tài)接受一個字母串（而不是一個字母）所到達(dá)的狀態(tài)，f的定義

5、依賴于f的定義， f遞歸定義如下：1） f(p, ) = p, if p K，即任意一狀態(tài)p接受（串長為0）的輸入，狀態(tài)不變2） f(p, aw) = f( f(p,a), w), if p K, a , w * 函數(shù)f的推廣定義f : 例子 對于x = adb, x *，那么從狀態(tài)0可以遷移到的狀態(tài)p可以這樣求出：P = f(0, adb) = f(f(0,a), db) = f(1, db) = f(f(1,d), b) = f(1, b) = f(f(1,b), ) = f(3, ) = 30132abcdd因為從初態(tài)0接受輸入字母串a(chǎn)db后，遷移到f(0,adb)= 3 Z，所以adb

6、為DFA所識別 DFA所識別的語言令M 為一DFA，我們：定義L(M)=x | f(S0, x) Z, x *L(M)稱為DFA M所識別的語言有定理：L(M) = L(G)，其中M為一DFA，G為一正規(guī)文法DFA關(guān)鍵特征狀態(tài)遷移映射f是入射函數(shù)即f(x) f(y) 蘊含 x y即對任意狀態(tài)結(jié)點p，其出弧上的字母各不相同且不為從狀態(tài)圖角度，如出現(xiàn)下述情況的狀態(tài)結(jié)點，則不是DFA（而是NFA）PQNaaQ NPQP QWhy?NFA的形式定義一個NFA M定義為M=(K, , f, S0, Z)，除f外其余成員與DFA相同，f定義為 f : K - (K)，其中(K)為集合K的冪集合，即有 |(

7、K)|=2|K|f 表示某狀態(tài)接受某個字母所到達(dá)的狀態(tài)集合，如：f(p,a) =q,m p,q,mK, a 映射f的推廣定義ff : (K) * - (K)，表示某狀態(tài)集合接受一個字母串（而不是一個字母）所到達(dá)的狀態(tài)集合，f遞歸定義如下(依賴于f)：f(p, ) = pf(p,a) =p1, p2,. if f(p,a)=p1,p2, if f(p,a) = f(p,aw) = f(f(p,a), w)其中，p,p1,p2 K, a , w *屬于什么？NFA所識別的語言令N 為一NFA，我們：定義L(N)=x | f(S0, x) Z , x *L(N)稱為NFA N所識別的語言有定理：L(

8、N) = L(M) = L(G)，其中N為一NFA，M為一DFA，G為一正規(guī)文法NFA例子 寫狀態(tài)遷移表fSABCabaaa,bba為什么是NFA源狀態(tài)輸入目的狀態(tài)集合-SaA,CAaA,CAbA,BBaABbCCx 對每狀態(tài)結(jié)點，按出弧上的字母寫出狀態(tài)遷移表C行可以不填f : K - (K)NFA例子 接受串源狀態(tài)輸入目的狀態(tài)集合-SaA,CAaA,CAbA,BBaABbCCx f : K - (K)當(dāng)前狀態(tài) 余留輸入 后續(xù)狀態(tài) 選擇狀態(tài) S ababb A,C A or C ?注意，NFA識別輸入符號串時有一個試探過程，為了能走到終態(tài)，往往要走許多彎路（帶回溯），這影響了NFA的效率。解決

9、辦法？NFA與DFA的等價性定理3.1 對于字母表上的任一NFA N，必存在與M等價的DFA M，使L(N)=L(M) 有了該定理，為提高NFA識別字符串的效率提供了tips：將NFA轉(zhuǎn)換為DFA，即NFA的確定化基本idea:DFA的 f : K - KNFA的f : K - (K)，將其改造為 f : (K) - (K)，并證明f是入射函數(shù) 且f接收的串與f接收的串相同例子S0S1abba,bq0q2a,babq1b帶有動作的NFA例子 a b c S0 S0 S1, S2 S1 S1, S3 S2 S2 S3 S3 bS0S1S3aS2cb帶有動作的NFA-閉包-closure(S0)=

10、S0, S1, S2, S3f(S, ) = -closure(S)f(S,wa) = -closure( f(f(S,w),a) )f(q, )通常不等于f(q, )f(S0, ) f(S0, )帶有動作的NFA的確定化1) 令K=-closure(S0)(給出M的初態(tài)q0)2) 對于K中任一尚未標(biāo)記的狀態(tài)qi=Si1,Si2,Sim，Sik K，作2.1)標(biāo)記qi2.2)對于每個a ，置T=f(Si1,Si2,Sim,a)qj= -closure(T)2.3) 若qj不在K中，則將qj作為一個未加標(biāo)記的狀態(tài)添加到K中，且把狀態(tài)轉(zhuǎn)移添加到M。3)重復(fù)進(jìn)行步驟2)，直到K中不再含有未標(biāo)記的狀態(tài)

11、為止，對于由此構(gòu)造的K ，我們把那些至少含有一個Z中的元素的qi作為M的終態(tài)。S0S1S3aS2cbbDFA狀態(tài)數(shù)最小化可區(qū)分狀態(tài)ABa1a2ana1a2狀態(tài)A,B被某一輸入串w=a1a2.an所區(qū)分，指1）從其中一個狀態(tài)出發(fā)讀入w，到達(dá)終態(tài)，2）而從另一個狀態(tài)出發(fā)進(jìn)入非終態(tài)可區(qū)分狀態(tài)的遞歸定義在一個DFA中，狀態(tài)A與狀態(tài)B可區(qū)分：1）A是終止?fàn)顟B(tài)，B是非終止?fàn)顟B(tài)或 B是終止?fàn)顟B(tài)，A是非終止?fàn)顟B(tài)2）對于字母a，有f(A,a)=C, f(B,a)=D2.1) C與D可區(qū)分2.2) C=NULL 且 D NULL且D可達(dá)終態(tài)或 C NULL且C可達(dá)終態(tài) 且 D=NULLDFA狀態(tài)數(shù)最小化-例子S0

12、S1S3S2babbaaabS4ab復(fù)習(xí)一個DFA M=(K, , f, S0, Z)，函數(shù)f : K - K表示某狀態(tài)Ki接受某字母a后，到達(dá)狀態(tài)Kj的轉(zhuǎn)換。一個NFA M=(K, , f, S0, Z)，函數(shù)f : K - (K)表示某狀態(tài)Ki接受某字母a后，到達(dá)狀態(tài)集合K1, , Kj的轉(zhuǎn)換。 一個帶動作的NFA M=(K, , f, S0, Z)，函數(shù) f : K - (K)表示某狀態(tài)Ki接受某字母a或空串后，到達(dá)狀態(tài)集合K1, , Kj的轉(zhuǎn)換。試描述下述文法所產(chǎn)生的語言的特點GS=(VN=S, , , VT=AZ, az, 09, P, S), 其中P= S S，S S，S ， A，

13、 z， 0， 9 上述正規(guī)文法產(chǎn)生的語言的特點是由字母開頭，后接0個或多個字母和(或)數(shù)字的符號串即標(biāo)識符的定義如果使用型如 字母(字母|數(shù)字)* 的式子來表示上述符號串構(gòu)成的集合，那么這樣的式子就稱為正規(guī)表達(dá)式(正則式，Regular Expression)，相應(yīng)的符號串集合則稱為該表達(dá)式對應(yīng)的正規(guī)集。正規(guī)表達(dá)式及正規(guī)集的定義正規(guī)式 正規(guī)集1. 空集2. 3. a，a a4. (r)(s) Lr Ls(r)|(s) Lr Ls(r)* Lr* r=(r)|() Lr (r)+=(r)(r)*) Lr+算符優(yōu)先級與正規(guī)式化簡 算符優(yōu)先級從高到低依次為 (), , *,+, , | 如( (r)

14、 ( (s)* ) ) | ( r )，可化簡為 r s*|r 又因為連接符通常可省略不寫， 再化簡為rs*|r正規(guī)式與正規(guī)集的例子=a,b正規(guī)式與正規(guī)集的多對一關(guān)系給定一個正規(guī)式，它唯一確定一個正規(guī)集；反之不然。即一個正規(guī)集可由多個不同的正規(guī)式表示。我們稱兩個正規(guī)式等價，當(dāng)且僅當(dāng)它們所描述的正規(guī)集相同。例如a|b與b|a, (a|b)*與 (b|a)*等等正規(guī)式的基本等價公理A1. r|s=s|rA2. r|r=rA3. r|=r A4. (r|s)|t=r|(s|t)A5. (rs)t=r(st) A6. r(s|t)=rs|rtA7. (s|t)r=sr|trA8. r = r = A9

15、. r = r =rA10. r*=(|r)*=|rr* 由正規(guī)文法構(gòu)造正規(guī)式1/4使用正規(guī)式描述下述右線性文法產(chǎn)生的語言S aS | bS aS | bS | c (或S (a|b)S | c )S abS | c 總結(jié)出規(guī)律: S S | 對應(yīng)的正規(guī)式是 *由正規(guī)文法構(gòu)造正規(guī)式2/4使用正規(guī)式描述下述左線性文法產(chǎn)生的語言S Sa | bS Sa | Sb | c (或S S(a|b) | c )S Sab | c 總結(jié)出規(guī)律: S S | 對應(yīng)的正規(guī)式是 *由正規(guī)文法構(gòu)造正規(guī)式3/4如果將“ | ”用 “ + ”替換，“ ” 用 “ = ” 替換，那么可以將產(chǎn)生式轉(zhuǎn)換為方程的形式，于是對上

16、述兩個規(guī)律，我們得到論斷：論斷3.1 方程X= X + （對應(yīng)S S | ），有解 X= *論斷3.2 方程X= X + （對應(yīng) S S | ），有解 X= *由正規(guī)文法構(gòu)造正規(guī)式4/4于是，對文法GS SaS | bA | b AaS 我們可以將所有產(chǎn)生式的運算符“ | ”用 “ + ”替換，“ ” 用 “ = ” 替換，再以我們習(xí)摜的線性方程組求解方法來求解S對應(yīng)的正規(guī)式。例子1) SaS|bA|b, AaS2) SaA, AbA|aB|b, BaA3) SbS|aA, AaA|bB, BaA|bC|b, CbS|aA練習(xí)1) SaS|bA|c, AbS2) SaA, AaA|bB|c, BcS由正規(guī)式構(gòu)造FAThompson法S0SfS0S0Sfa當(dāng)n=0r=r=r=a根據(jù)正規(guī)式所含運算符個數(shù)n遞歸給出。r= r1|r2r1S01r2S02s0Sf不再是初態(tài)不再是終態(tài)Sf1Sf2r=r1r2r1S01Sf1r2S02Sf2r=r*S01Sf1sSf例子與練習(xí)例子：1）a(b|aa)*b2）( (0*|1) (1*0) )*練習(xí)：1） ab|c*2） (b|aa|ac|aaa|aac)*綜合練習(xí)1對文法GS=