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

1、編譯原理前后文無關(guān)文法和語言,設(shè)計(jì)掃描器應(yīng)注意的問題,詞法分析（3型） 語法分析（2型） 單詞的(Class, Value)二元組表示 標(biāo)識(shí)符的長(zhǎng)度限制和按“盡可能長(zhǎng)”的識(shí)別策略 超前搜索與回退 , =, , = 程序3-1 輸入緩沖 注釋與空白的刪除,狀態(tài)轉(zhuǎn)換圖,有向圖 結(jié)點(diǎn)表示狀態(tài) 一個(gè)初態(tài)，箭頭指示 若干個(gè)終態(tài)，雙圓圈指示 邊表示轉(zhuǎn)移 邊上的字符表示轉(zhuǎn)移時(shí)應(yīng)滿足的條件 字符串的識(shí)別,0,1,3,2,a,b,c,d,d,右線性文法=狀態(tài)轉(zhuǎn)換圖,設(shè)G=(VN,VT,P,S)是一右線性文法,令|VN|=K， 1) 則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個(gè)狀態(tài). 2) VN中的每個(gè)符號(hào)分別表示K個(gè)狀態(tài)

2、 2.1) G的開始符S為初態(tài)狀態(tài) 3) 終止?fàn)顟B(tài),用F(VN)標(biāo)記,右線性文法=狀態(tài)轉(zhuǎn)換圖,產(chǎn)生式的消除,S,A,X,F,a,b,c,other,Y,e,S,A,X,F,a,b,c,Y,e,S - aA A - b|bX X - c|eY,S - aA A - bX X - c|eY,狀態(tài)圖=右線性文法,左線性文法=狀態(tài)轉(zhuǎn)換圖,設(shè)G=(VN,VT,P,S)是一左線性文法,令|VN|=K， 1) 則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個(gè)狀態(tài). 2) VN中的每個(gè)符號(hào)分別表示K個(gè)狀態(tài) 2.1) G的開始符S為終止?fàn)顟B(tài) 3) 起始狀態(tài),用R(VN)標(biāo)記,左線性文法=狀態(tài)轉(zhuǎn)換圖,不存在這種轉(zhuǎn)換,狀態(tài)圖=左

3、線性文法,0,1,3,2,a,b,c,d,d,狀態(tài)矩陣,狀態(tài)矩陣Bij=BSi, aj=Sk 當(dāng)前狀態(tài)，掃視字符，語義動(dòng)作，后續(xù)狀態(tài) 程序3-2,識(shí)別無符號(hào)數(shù)的狀態(tài)矩陣,語義 動(dòng)作中的返回值ICON、FCON分別為整型數(shù)、浮點(diǎn)型數(shù)的值； 一般說來，無符號(hào)數(shù)具有形式 dmdm-1d0.d-1d-nEdd 即dmdm-1d0d-1d-n*10(dd-n); 程序3-3,關(guān)于狀態(tài)無符號(hào)數(shù)識(shí)別矩陣,DFA的形式定義,DFA: Deterministic Finite Automata 一個(gè)DFA M定義為M=(K, , f, S0, Z)，其中 1) K=狀態(tài)i 2) =字母表，即輸入字符i 3) f

4、 : K - K，f為函數(shù)，表示某狀態(tài)接受某個(gè)字母所到達(dá)的狀態(tài)，如：f(p,a) =q, p,qK, a 4) S0 K， S0為初態(tài) 5) Z K，且Z ，Z為終態(tài)集合,DFA例子,左側(cè)的狀態(tài)圖，在數(shù)學(xué)上稱作DFA，其形式化定義為,M=(K, , f, S0, Z),K=0 , 1 , 2 , 3 =a , b , c , d ,f:,S0=0 Z=2 , 3,函數(shù)f的推廣定義f,f : K * - K，表示某狀態(tài)接受一個(gè)字母串（而不是一個(gè)字母）所到達(dá)的狀態(tài)， f的定義依賴于f的定義， f遞歸定義如下： 1） f(p, ) = p, if p K，即任意一狀態(tài)p接受（串長(zhǎng)為0）的輸入，狀態(tài)不

5、變 2） f(p, aw) = f( f(p,a), w), if p K, a , w *,函數(shù)f的推廣定義f : 例子,對(duì)于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, ) = 3,因?yàn)閺某鯌B(tài)0接受輸入字母串a(chǎn)db后，遷移到f(0,adb)= 3 Z，所以adb為DFA所識(shí)別,DFA所識(shí)別的語言,令M 為一DFA，我們： 定義L(M)=x | f(S0, x) Z, x * L(M)稱為DF

6、A M所識(shí)別的語言 有定理：L(M) = L(G)，其中M為一DFA，G為一正規(guī)文法,DFA關(guān)鍵特征,狀態(tài)遷移映射f是入射函數(shù)即 f(x) f(y) 蘊(yùn)含 x y 即對(duì)任意狀態(tài)結(jié)點(diǎn)p，其出弧上的字母各不相同且不為 從狀態(tài)圖角度，如出現(xiàn)下述情況的狀態(tài)結(jié)點(diǎn)，則不是DFA（而是NFA）,Why?,NFA的形式定義,一個(gè)NFA M定義為M=(K, , f, S0, Z)， 除f外其余成員與DFA相同，f定義為 f : K - (K)， 其中(K)為集合K的冪集合，即有 |(K)|=2|K| f 表示某狀態(tài)接受某個(gè)字母所到達(dá)的狀態(tài)集合，如：f(p,a) =q,m p,q,mK, a ,映射f的推廣定義f

7、,f : (K) * - (K)， 表示某狀態(tài)集合接受一個(gè)字母串（而不是一個(gè)字母）所到達(dá)的狀態(tài)集合， f遞歸定義如下(依賴于f)： f(p, ) = p f(p,a) =,f(p,aw) = f(f(p,a), w),其中，p,p1,p2 K, a , w *,屬于什么？,NFA所識(shí)別的語言,令N 為一NFA，我們： 定義L(N)=x | f(S0, x) Z , x * L(N)稱為NFA N所識(shí)別的語言 有定理：L(N) = L(M) = L(G)，其中N為一NFA，M為一DFA，G為一正規(guī)文法,NFA例子 寫狀態(tài)遷移表f,為什么是NFA,對(duì)每狀態(tài)結(jié)點(diǎn)，按出弧上的字母寫出狀態(tài)遷移表,C行可

8、以不填,f : K - (K),NFA例子 接受串,f : K - (K),當(dāng)前狀態(tài) 余留輸入 后續(xù)狀態(tài) 選擇狀態(tài),S ababb A,C A or C ?,注意，NFA識(shí)別輸入符號(hào)串時(shí)有一個(gè)試探過程，為了能走到終態(tài)，往往要走許多彎路（帶回溯），這影響了NFA的效率。,解決辦法？,NFA與DFA的等價(jià)性,定理3.1 對(duì)于字母表上的任一NFA N，必存在與M等價(jià)的DFA M，使L(N)=L(M),有了該定理，為提高NFA識(shí)別字符串的效率提供了tips： 將NFA轉(zhuǎn)換為DFA， 即NFA的確定化,基本idea: DFA的 f : K - K NFA的f : K - (K)，將其改造為 f : (K

9、) - (K)，并證明f是入射函數(shù) 且f接收的串與f接收的串相同,例子,帶有動(dòng)作的NFA例子,a b c ,S0 S0 S1, S2,S1 S1, S3,S2 S2 S3,S3,帶有動(dòng)作的NFA,-閉包 -closure(S0)=S0, S1, S2, S3 f(S, ) = -closure(S) f(S,wa) = -closure( f(f(S,w),a) ) f(q, )通常不等于f(q, ) f(S0, ) f(S0, ),帶有動(dòng)作的NFA的確定化,1) 令K=-closure(S0)(給出M的初態(tài)q0) 2) 對(duì)于K中任一尚未標(biāo)記的狀態(tài)qi=Si1,Si2,Sim，Sik K，作

10、2.1)標(biāo)記qi 2.2)對(duì)于每個(gè)a ，置 T=f(Si1,Si2,Sim,a) qj= -closure(T) 2.3) 若qj不在K中，則將qj作為一個(gè)未加標(biāo)記的狀態(tài)添加到K中，且把狀態(tài)轉(zhuǎn)移添加到M。 3)重復(fù)進(jìn)行步驟2)，直到K中不再含有未標(biāo)記的狀態(tài)為止，對(duì)于由此構(gòu)造的K ，我們把那些至少含有一個(gè)Z中的元素的qi作為M的終態(tài)。,DFA狀態(tài)數(shù)最小化,可區(qū)分狀態(tài),a1,a2,an,a1,a2,狀態(tài)A,B被某一輸入串w=a1a2.an所區(qū)分，指 1）從其中一個(gè)狀態(tài)出發(fā)讀入w，到達(dá)終態(tài)， 2）而從另一個(gè)狀態(tài)出發(fā)進(jìn)入非終態(tài),可區(qū)分狀態(tài)的遞歸定義,在一個(gè)DFA中，狀態(tài)A與狀態(tài)B可區(qū)分：,1）A是終止

11、狀態(tài)，B是非終止?fàn)顟B(tài) 或 B是終止?fàn)顟B(tài)，A是非終止?fàn)顟B(tài),2）對(duì)于字母a，有f(A,a)=C, f(B,a)=D 2.1) C與D可區(qū)分,2.2) C=NULL 且 D NULL且D可達(dá)終態(tài) 或 C NULL且C可達(dá)終態(tài) 且 D=NULL,DFA狀態(tài)數(shù)最小化-例子,S0,S1,S3,S2,b,a,b,b,a,a,a,b,a,b,復(fù)習(xí),一個(gè)DFA M=(K, , f, S0, Z)，函數(shù)f : K - K表示某狀態(tài)Ki接受某字母a后，到達(dá)狀態(tài)Kj的轉(zhuǎn)換。 一個(gè)NFA M=(K, , f, S0, Z)，函數(shù)f : K - (K)表示某狀態(tài)Ki接受某字母a后，到達(dá)狀態(tài)集合K1, , Kj的轉(zhuǎn)換。 一

12、個(gè)帶動(dòng)作的NFA M=(K, , f, S0, Z)，函數(shù) f : K - (K)表示某狀態(tài)Ki接受某字母a或空串后，到達(dá)狀態(tài)集合K1, , Kj的轉(zhuǎn)換。,試描述下述文法所產(chǎn)生的語言的特點(diǎn),GS=(VN=S, , , VT=AZ, az, 09, P, S), 其中P= S S， S S， S ， A， z， 0， 9 ,上述正規(guī)文法產(chǎn)生的語言的特點(diǎn)是 由字母開頭，后接0個(gè)或多個(gè)字母和(或)數(shù)字的符號(hào)串 即標(biāo)識(shí)符的定義 如果使用型如 字母(字母|數(shù)字)* 的式子來表示上述符號(hào)串構(gòu)成的集合，那么這樣的式子就稱為正規(guī)表達(dá)式(正則式，Regular Expression)，相應(yīng)的符號(hào)串集合則稱為該表

13、達(dá)式對(duì)應(yīng)的正規(guī)集。,正規(guī)表達(dá)式及正規(guī)集的定義,正規(guī)式 正規(guī)集,1. 空集,2. ,3. a，a a,4. (r)(s) Lr Ls (r)|(s) Lr Ls (r)* Lr*,r=(r)|() Lr (r)+=(r)(r)*) Lr+,算符優(yōu)先級(jí)與正規(guī)式化簡(jiǎn),算符優(yōu)先級(jí)從高到低依次為 (), , *,+, , | 如( (r) ( (s)* ) ) | ( r )，可化簡(jiǎn)為 r s*|r 又因?yàn)檫B接符通?？墒÷圆粚?， 再化簡(jiǎn)為rs*|r,正規(guī)式與正規(guī)集的例子,=a,b,正規(guī)式與正規(guī)集的多對(duì)一關(guān)系,給定一個(gè)正規(guī)式，它唯一確定一個(gè)正規(guī)集；反之不然。 即一個(gè)正規(guī)集可由多個(gè)不同的正規(guī)式表示。 我們稱

14、兩個(gè)正規(guī)式等價(jià)，當(dāng)且僅當(dāng)它們所描述的正規(guī)集相同。 例如a|b與b|a, (a|b)*與 (b|a)*等等,正規(guī)式的基本等價(jià)公理,A1. r|s=s|rA2. r|r=r A3. r|=r A4. (r|s)|t=r|(s|t) A5. (rs)t=r(st) A6. r(s|t)=rs|rt A7. (s|t)r=sr|trA8. r = r = A9. r = r =rA10. r*=(|r)*=|rr*,由正規(guī)文法構(gòu)造正規(guī)式1/4,使用正規(guī)式描述下述右線性文法產(chǎn)生的語言 S aS | b S aS | bS | c (或S (a|b)S | c ) S abS | c 總結(jié)出規(guī)律: S S

15、 | 對(duì)應(yīng)的正規(guī)式是 *,由正規(guī)文法構(gòu)造正規(guī)式2/4,使用正規(guī)式描述下述左線性文法產(chǎn)生的語言 S Sa | b S Sa | Sb | c (或S S(a|b) | c ) S Sab | c 總結(jié)出規(guī)律: S S | 對(duì)應(yīng)的正規(guī)式是 *,由正規(guī)文法構(gòu)造正規(guī)式3/4,如果將“ | ”用 “ + ”替換，“ ” 用 “ = ” 替換，那么可以將產(chǎn)生式轉(zhuǎn)換為方程的形式，于是對(duì)上述兩個(gè)規(guī)律，我們得到論斷： 論斷3.1 方程X= X + （對(duì)應(yīng)S S | ），有解 X= * 論斷3.2 方程X= X + （對(duì)應(yīng) S S | ），有解 X= *,由正規(guī)文法構(gòu)造正規(guī)式4/4,于是，對(duì)文法GS SaS |

16、bA | b AaS 我們可以將所有產(chǎn)生式的運(yùn)算符“ | ”用 “ + ”替換，“ ” 用 “ = ” 替換，再以我們習(xí)摜的線性方程組求解方法來求解S對(duì)應(yīng)的正規(guī)式。,例子,1) SaS|bA|b, AaS 2) SaA, AbA|aB|b, BaA 3) SbS|aA, AaA|bB, BaA|bC|b, CbS|aA,練習(xí),1) SaS|bA|c, AbS 2) SaA, AaA|bB|c, BcS,由正規(guī)式構(gòu)造FAThompson法,當(dāng)n=0 r= r= r=a,根據(jù)正規(guī)式所含運(yùn)算符個(gè)數(shù)n遞歸給出。,r= r1|r2,r1,S01,r2,S02,s0,Sf,不再是初態(tài),不再是終態(tài),Sf1,Sf2,r=r1r2,r1,S01,Sf1,r2,S02,Sf2,r=r*,S01,Sf1,s,Sf,例子與練習(xí),例子： 1）a(b|aa)*b 2）( (0*|1) (1*0) )* 練習(xí)： 1） ab|c* 2） (b|aa|ac|aaa|aac)*,綜合練習(xí)1,對(duì)文法GS=(S, A, B, a, b