編譯原理第四章

1、1詞法分析程序的設(shè)計原則 單詞的描述技術(shù)單詞的識別機(jī)制詞法分析程序的自動構(gòu)造原理第4章 詞法分析及其自動構(gòu)造2回顧回顧 什麼是詞法分析程序4實(shí)現(xiàn)詞法分析（lexical analysis）的程序 逐個讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。 是語言中具有獨(dú)立意義的最小單位，包括保留字、標(biāo)識符、運(yùn)算符、標(biāo)點(diǎn)符號和常量等。 詞法分析是編譯過程中的一個階段，在語法分析前進(jìn)行 。可以和語法分析結(jié)合在一起作為一遍。3 詞法分析程序和語法分析程序的關(guān)系源程序詞法分析程序語法分析程序Tokenget token.源程序詞法分析程序語法分析程序4 詞法分析程序的主要任務(wù)主要任務(wù)： 讀源程序，產(chǎn)生單詞符號

2、詞法分析程序的其他任務(wù)其他任務(wù)： 濾掉空格，跳過注釋、換行符 追蹤換行標(biāo)志，復(fù)制出錯源程序， 宏展開，5詞法分析程序的輸出 4詞法分析程序所輸出的單詞符號常常采用以下二元式表示：4 (單詞種別，單詞自身的值)。 4(標(biāo)識符，指向該標(biāo)識符所在符號表中位置的指針)語法分析需要的信息 編譯其它階段需要的信息 6 詞法分析工作從語法分析工作獨(dú)立出來的原因： 簡化設(shè)計 改進(jìn)編譯效率 增加編譯系統(tǒng)的可移植性 7單詞的描述工具-正規(guī)表達(dá)式正規(guī)表達(dá)式 回顧正規(guī)文法正規(guī)文法描述的是VT上的正規(guī)集，即是正規(guī)語言4 標(biāo)識符l|l字母數(shù)字字母數(shù)字l|d|l字母數(shù)字|d字母數(shù)字無符號整數(shù)d|d無符號整數(shù)運(yùn)算符+|-|*

3、|/|=|等號|等號等號=界符，|；|(|)| 8正規(guī)式 正規(guī)式也稱正則表達(dá)式,是定義正規(guī)集的數(shù)學(xué)工具。 正規(guī)表達(dá)式（regular expression）是說明單詞的模式(pattern)的一種重要的表示法（記號），我們用以描述單詞符號。94設(shè)字母表為，輔助字母表=，|，*，(，) 。 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和 ； 任何a，a是上的一個正規(guī)式，它所表示的正規(guī)集為a； 假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1), e1|e2, e1e2, e1*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(

4、e1)L(e2)和(L(e1)*。 僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。 10令=a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集的例子 a ab ab (ab)(ab) a (ab) (ab)(aabb)(ab) a a,b ab aa,ab,ba,bb ,a,aa, 任意個a的串 ,a,b,aa,ab,bb 所有由 a和b組成的串 上所有含有兩個相繼的a或兩個相繼的b組成的串11討論例1 令=l，d，則上的正規(guī)式 r=l(l d) 定義的正規(guī)集為: l,ll,ld,ldd,其中l(wèi)代表字母,d代表數(shù)字,正規(guī)式 即是 字母(字母|數(shù)字) ,它表示的

5、正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”, 多數(shù)程序設(shè)計語言允許的的標(biāo)識符的詞法規(guī)則.例2=d，e，+，-,則上的正規(guī)式 d(dd )(e(+- )dd )表示的是無符號數(shù)的集合。其中d為09的數(shù)字。 程序設(shè)計語言的單詞都能用正規(guī)式程序設(shè)計語言的單詞都能用正規(guī)式 來定義來定義. .12正規(guī)文法與正規(guī)式4r-G變換 對任何正規(guī)式r，選擇一個非終結(jié)符S生成產(chǎn)生式Sr叫做正規(guī)產(chǎn)生式，并將S定為G的識別符號。若x和y都是正規(guī)式，對形如Axy的正規(guī)產(chǎn)生式，重寫成：AxB，By兩個正規(guī)產(chǎn)生式，其中B是新選擇的非終結(jié)符對已形成的形如Ax*y的正規(guī)產(chǎn)生式，重寫為：AxBAyBxBBy B為一新非終結(jié)

6、符。對形如Ax|y的正規(guī)產(chǎn)生式，重寫為：Ax，Ay不斷利用上述規(guī)則做變換，直到每個產(chǎn)生式都符合三型文法的要求。 134將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正規(guī)文法：4令S是文法的開始符號Sa(a|d)*，4 SaA A(a|d)*， 重寫第二條 4SaAA(a|d)B，AB(a|d)B和B進(jìn)而變換為SaABaBAaBBdBAdBBA即為所求。144文法GSSaASaAaAAdA4 AaAd4S=aA|aA=(aA|dA)|(a|d)再將A的正規(guī)式變換A=(a|d)A|(a|d)， 4 A=(a|d)*(a|d)，4 A 右端代入S的正規(guī)式：S=a(a|d)*(a|d)|a再利用正規(guī)式的代數(shù)變換可依

7、次得到S=a(a|d)*(a|d)|)S=a(a|d)*即a(a|d)*為所求。 15有窮自動機(jī)有窮自動機(jī)將討論如下內(nèi)容：確定的有窮自動機(jī)DFA不確定的有窮自動機(jī)NFANFA的確定化DFA的最小化16有窮自動機(jī)有窮自動機(jī) 有窮自動機(jī)(也稱有限自動機(jī))作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)式所表示的集合.應(yīng)用有窮自動機(jī)這個理論，為詞法分析程序的自動構(gòu)造尋找有效的方法和工具。 有窮自動機(jī)分為兩類：確定的有窮自動機(jī)(Deterministic Finite Automata)和不確定的有 窮自動機(jī)(Nondeterministic Finite Automata) 。17確定的有窮自動機(jī)

8、DFADFA定義：一個確定的有窮自動機(jī)（DFA）M是一個五元組：M=（K，f，S，Z）其中1.K是一個有窮集，它的每個元素稱為一個狀態(tài)；2.是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號表；18DFA定義3.f是轉(zhuǎn)換函數(shù)，是在KK上的映射，即，如 f（ki，a）=kj，（kiK， kj K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)kj ，我們把kj稱作ki的一個后繼狀態(tài)；4.SK是唯一的一個初態(tài)；5.Z K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。19一個DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定義為：f（S，a）=Uf（

9、V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q20 DFA 的狀態(tài)圖表示4f(ki,a)=kj表示為從ki到kj的標(biāo)記為a的弧線bSUVQaaaba，bb21DFA 的矩陣表示的矩陣表示abSUVUQVVUQQQQ字符字符狀態(tài)狀態(tài)0001224DFA的表現(xiàn)在轉(zhuǎn)換函數(shù)f:KK是一個單值函數(shù)，也就是說，對任何狀態(tài)kK，和輸入符號a，f(k,a)唯一地確定了下一個狀態(tài)。4從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個輸入字符，那末任何一個狀態(tài)結(jié)點(diǎn)最多有n條弧射出，而且每條弧以一個不同的輸入字符標(biāo)記。 4對于對于*中的任何符號串中的任何符號串t，如果存

10、在一條，如果存在一條從初態(tài)結(jié)點(diǎn)到某一個終態(tài)結(jié)點(diǎn)的道路，從初態(tài)結(jié)點(diǎn)到某一個終態(tài)結(jié)點(diǎn)的道路，而且這條路上的所有弧的標(biāo)記符連接成而且這條路上的所有弧的標(biāo)記符連接成的符號串等于的符號串等于t，稱，稱t可以為可以為DFA M所接所接受。受。4若若M的初態(tài)結(jié)點(diǎn)同時也是終態(tài)結(jié)點(diǎn)，則的初態(tài)結(jié)點(diǎn)同時也是終態(tài)結(jié)點(diǎn)，則空字可被空字可被M所識別（接受）所識別（接受）23244*上的符號串上的符號串t被被M接受接受- 若t*，f(S，t)=P，其中S為 M的開始狀態(tài)，PZ，Z為終態(tài)集。- 則稱t為DFA M所接受（識別）4*上的符號串上的符號串t在在M上上運(yùn)行運(yùn)行一個輸入符號串t，表示成t1t2的形式-其中t1，t2

11、*,在DFA M上運(yùn)行的定義為：- f（Q， t1t2 ）=f（f（Q， t1 ）， t2 ） 其中QK - 擴(kuò)充轉(zhuǎn)換函數(shù)f，是K*K上的映射， 且： f（ki，）= ki25* *上的符號串上的符號串t t被被DFADFA M M接受接受例例：證明證明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, baa26DFA M所能接受的符號串的全體記為L(M).結(jié)論： 上一個符

12、號串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個上的確定有窮自動機(jī)M，使得V=L(M)。27DFA的行為很容易用程序來模擬.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)28DFA = digit,not digit29不確定的有窮自動機(jī)NFA定義NFA M=K，f，S，Z，其中K為狀態(tài)的有窮非空集， 為有窮輸入字母表，f為K * 到K的子集（2 K）的一種映射，S K是初始狀態(tài)集，Z K為終止?fàn)顟B(tài)集

13、.30例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（S，1）=S，Z f（P，1）=Zf（Z，0）=Pf（Z，1）=P31狀態(tài)圖表示SPZ00,111132矩陣表示矩陣表示01SPS,Z0PZ0ZPP1簡化為01SPS,Z0P.Z0ZPP133具有轉(zhuǎn)移的不確定的有窮自動機(jī)f為K * 到K的子集（2 K）的一種映射 123abc34有如下定理: 對任何一個具有轉(zhuǎn)移的不確定的有窮自動機(jī)NFA N，一定存在一個不具有轉(zhuǎn)移的不確定的有窮自動機(jī)NFA ，使得L(M)=L(N)。與上例等價的一個NFA.cb2acbb31acab35類似DFA, 對NFA M=K，f，S

14、，Z也有如下定義*上的符號串t在NFA M上運(yùn)行.一個輸入符號串t，（我們將它表示成Tt1的形式，其中T，t1 *）在NFA M上運(yùn)行運(yùn)行的定義為：f（Q， Tt1）=f（f（Q，T），t1） 其中QK.*上的符號串t被NFA M接受若t *，f(S0，t)=P，其中S0 S，P Z，則稱t為NFA M所接受接受（識別識別）36 *上的符號串t被NFA M接受也可以用狀態(tài)轉(zhuǎn)換圖來理解 對于中的任何一個串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為的弧)等于t，則稱t可為NFA M所識別(讀出或接受)。 若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)

15、，或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均為，那么空字可為M所接受。37NFA M所能接受的符號串的全體記為 L(M)結(jié)論： 上一個符號串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個上的不確定的有窮自動機(jī)M，使得V=L(M)。3800011110100011100000010001100特點(diǎn)？特點(diǎn)？39(0|1)*(000|111)(0|1)*40確定有限自動機(jī)和不確定有限自動機(jī)確定有限自動機(jī)和不確定有限自動機(jī)關(guān)系關(guān)系 DFA是NFA的特例。 對每個NFA N一定存在一個DFA ，使得 L(M)=L(N)。 找一種算法，將找一種算法，將NFA轉(zhuǎn)換成接受同轉(zhuǎn)換成接受同樣語言的樣語言的DF

16、A. 子集法子集法. 與某一與某一NFA等價的等價的DFA不唯一不唯一.等等價價41先定義對狀態(tài)集合I的有關(guān)運(yùn)算：1. 狀態(tài)集合狀態(tài)集合I I的的-閉包閉包，表示為-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S而能到達(dá)的狀態(tài)的集合。 狀態(tài)集合I的任何狀態(tài)-closure(I)。2. 狀態(tài)集合狀態(tài)集合I I的的a a弧轉(zhuǎn)換弧轉(zhuǎn)換，表示為move(I,a) 定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)而到達(dá)的狀態(tài)的全體。42狀態(tài)集合I的有關(guān)運(yùn)算的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4-

17、closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa43 NFA確定化算法: NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造一個DFA M=(S, ,d,S0,St)，使得L(M)=L(N)：1. M的狀態(tài)集S由K K的一些子集的一些子集組成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的狀態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即對于子集S1, S2= S2, S1,來說，S的狀態(tài)就是S1 S2；442 M和N的輸入字母表是相同的，即是；3 轉(zhuǎn)換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其

18、中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)為M的開始狀態(tài)；5 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKt45構(gòu)造NFA N的狀態(tài)狀態(tài)K K的子集的子集的算法：假定所構(gòu)造的子集族為C，即C= (T1, T2,. TI),其中T1, T2,. TI為狀態(tài)K的子集。1 開始，令-closure(K0)為C中唯一成員，并且它是未被標(biāo)記的。462 while （C中存在尚未被標(biāo)記的子集T）do 標(biāo)記T； for 每個輸入字母a do U:= -closure(move(T,a)； i

19、f U不在C中 then 將U作為未標(biāo)記的子集加在C中 47 NFA的確定化 例子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,f4f35621iaaaabbbb49 等價的DFAaCDBAEFSbaaaaabbbbbabF50確定有窮自動機(jī)的化簡 一個

20、有窮自動機(jī)是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。 一個有窮自動機(jī)可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有窮自動機(jī)。 多余狀態(tài)，是指：從自動機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達(dá)終態(tài)。 51 DFA的最小化就是尋求最小狀態(tài)DFA最小狀態(tài)DFA的含義:沒有多余狀態(tài)(死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別）兩個狀態(tài)s和t等價等價：滿足兼容性同是終態(tài)或同是非終態(tài)傳播性從s出發(fā)讀入所有aa和從 t出發(fā)讀入所有a到達(dá)的狀態(tài)等價。分析52最小狀態(tài)DFA對于一個DFA M =（K,f, k0,kt)，存在一個最小狀

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

22、group) 2.對施用過程過程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)=r55 M 的開始狀態(tài)是含有S0的那組的代表 M 的終態(tài)是含有F的那組的代表 5.去掉M中的死狀態(tài).56過程過程PPPP : Construction of new 對對每一個狀態(tài)組每一個狀態(tài)組G進(jìn)行下述工作：進(jìn)行下述工作：將將G劃分為子組。劃分為子組。G的兩個狀態(tài)的兩個狀態(tài)s和和t分分在同一子組的充要條件是：對所有的在同

23、一子組的充要條件是：對所有的輸入符號輸入符號a，狀態(tài)，狀態(tài)s和和t的的a轉(zhuǎn)換都是轉(zhuǎn)換都是的的同一組中的狀態(tài)。同一組中的狀態(tài)。形成的所有子組成為形成的所有子組成為new的狀態(tài)組。的狀態(tài)組。 57 DFA的最小化例子0:S,A,B C,D,E,F1:S,A,B C,D,E,F 2: CDBAEFSbaaaaaabbbbbba S,BA bB SDBASaaabbbbaa58詞法分析程序的自動構(gòu)造 詞法分析程序的自動構(gòu)造方法,這個方法基于有窮自動機(jī)和正規(guī)表達(dá)式的等價性有窮自動機(jī)和正規(guī)表達(dá)式的等價性,即即： 1.對于上的一個NFA M，可以構(gòu)造一個上的正規(guī)式R,使得L(R)=L(M)。2.對于上的一個

24、正規(guī)式R，可以構(gòu)造一個上的NFA M，使的L(M)=L(R)。59RNFA從上的一個正規(guī)式R構(gòu)造上的一個NFA M，使得L(M)=L(R)的方法。“語法制導(dǎo)”的方法，即按正規(guī)式的語法結(jié)構(gòu)指引構(gòu)造過程，構(gòu)造規(guī)則具體描述如下： 60對于正規(guī)式 ,構(gòu)造的NFA 61對于正規(guī)式 ,構(gòu)造的NFA 62對于正規(guī)式a ,構(gòu)造的NFA 63對于正規(guī)式r, r= s|t構(gòu)造的NFA s和t相應(yīng)的NFA分別為N(s)和N(t), 64對于正規(guī)式r, r=st 構(gòu)造的NFA65對于正規(guī)式r, r = s*構(gòu)造的NFA對于正規(guī)式r, r = （s）構(gòu)造的NFA4同S的NFA一樣6667正規(guī)表達(dá)式正規(guī)表達(dá)式 1*0(0+1)*舉例舉例:從從正規(guī)表達(dá)式正規(guī)表達(dá)式構(gòu)造等價的構(gòu)造等價的 - NFA100+1 11* 68從從正規(guī)表