1、Part3Part3詞法分析詞法分析授課：胡靜授課：胡靜內容提要內容提要詞法分析器的作用詞法分析器的作用詞法分析程序的設計與實現詞法分析程序的設計與實現狀態圖狀態圖詞法分析程序的自動生成詞法分析程序的自動生成有窮自動機有窮自動機正則表達式與有限自動機正則表達式與有限自動機問題的提出問題的提出如果只向前看一個字符，不能夠確定我們將要讀入的是哪種如果只向前看一個字符，不能夠確定我們將要讀入的是哪種類型的類型的token如果如果token的開頭是的開頭是“i”，那么它一定是標識符么？，那么它一定是標識符么？如果如果token的開頭是的開頭是“2”，那么它一定是一個整型的常數么？，那么它一定是一個整型

2、的常數么？如果我們通過上面的類似如果我們通過上面的類似“插入插入”式的方法來寫識別式的方法來寫識別token的程的程序，這樣的程序不容易寫正確，而且也不容易維護序，這樣的程序不容易寫正確，而且也不容易維護因此需要一個更加有原理性的方法：詞法分析器的生成器，因此需要一個更加有原理性的方法：詞法分析器的生成器，可以自動產生有效的詞法分析器。（例如可以自動產生有效的詞法分析器。（例如lex，flex，Jlex）一般說來，沒有限制的向前看是必要的一般說來，沒有限制的向前看是必要的一些問題一些問題如何明確的描述如何明確的描述tokens2.e0 20.e-01 2.0000“” “x” “” “”如何將

3、文本分割成如何將文本分割成tokensif (x = 0) a = x1;if (x = 0) a = x1;如何描述如何描述tokenstokens我們可以使用我們可以使用正則表達式正則表達式來描述程序設計語言中的來描述程序設計語言中的tokens。正則表達式的定義如下：。正則表達式的定義如下：正則集合（語言）正則集合（語言）正則表達式的例子正則表達式的例子令令 =a，b， 正則表達式正則表達式正則集合集正則集合集aaa ba,babab(a b)(a b)aa,ab,ba,bba ,a,a, 任意個任意個a的串的串(a b) ,a,b,aa,ab 所有由所有由a 和和b組成的串組成的串(a

4、 b) (aa bb)(a b) 上所有含有兩個相繼的上所有含有兩個相繼的a或兩個或兩個相繼的相繼的b組成的串組成的串正則表達式的例子正則表達式的例子 =a，b，r=a(a b) 定義的正則集合定義的正則集合: a,aa,ab,abb, =d， ，e，+，-,則則 上的正則表達式上的正則表達式 d ( dd )(e(+ - )dd )表示的是無符號數的集表示的是無符號數的集合。其中合。其中d為為09的數字。的數字。若兩個正則表達式所表示的正則集合相同，則認為二若兩個正則表達式所表示的正則集合相同，則認為二者等價。兩個等價的正則表達式者等價。兩個等價的正則表達式U和和V記為記為U=V。例如：例如

5、： U= (a b)， V = b a又如：又如： U= b(ab) , V =(ba) b再如：再如： U= (a b) , V =(a b ) 正則表達式的性質正則表達式的性質設設U、V和和W都是正則表達式，則如下關系普遍成立：都是正則表達式，則如下關系普遍成立：U|V = V|U（交換律）（交換律）U|(V|W) = (U|V)|W （結合律）（結合律）U(VW) = (UV)W（結合律）、（結合律）、U(V|W) = UV | UW （分配律）（分配律）(V|W)U = VU |WU；U = U =Ur r=rr =r rr “或或”的抽取律的抽取律正則文法和正則表達式正則文法和正則表

6、達式對對 上的正則表達式上的正則表達式U ,存在一個正則文法存在一個正則文法G=(VN,VT,P,S):L(G)=L(r)初始，初始， VT= , S VN ，生成生成正則正則產生式產生式SU (R.1) 對形如對形如 Ar1r2的的正則正則產生式：產生式：Ar1B Br2 B VN(R.2)對形如對形如Ar r1的的正則正則產生式：產生式：ArB Ar1BrB Br1 B VN (R.3)對形如對形如Ar1 r2的的正則正則產生式產生式:Ar1 A r2 不斷應用不斷應用R做變換，直到每個產生式右端只含一個做變換，直到每個產生式右端只含一個VN正則文法和正則表達式正則文法和正則表達式對對G=

7、(VN,VT,P,S),存在一個存在一個 =VT上的正則表達式上的正則表達式r : L(r)=L(G)AxB, By A=xy AxA y A=x yAx y A=x y正則文法和正則表達式舉例正則文法和正則表達式舉例例例1：r=a(a d) VT=a,d Sa(a d) R.1SaA A(a d) R.2A(a d)BAB(a d)B BR.3 Gs:SaA A VT=a,d AaBVN=S,A,B AdB BaB BdBBP正則表達式和正則文法舉例正則表達式和正則文法舉例Gs:SaA AaA AdA Sa Aa Ad SaA a AaA a dA d A(a d)A (a d) A(a d

8、) (a d)S=a(a d) (a d) a =a(a d) (a d) =a(a d)+)R=a(a d) 有窮自動機有窮自動機有窮自動機（也稱有限自動機）作為一種識別裝置，有窮自動機（也稱有限自動機）作為一種識別裝置，它能準確地識別正則集合，即識別正則文法所定義的它能準確地識別正則集合，即識別正則文法所定義的語言與正則表達式所表示的集合，引入有窮自動機這語言與正則表達式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構造尋找特殊的個理論，正是為詞法分析程序的自動構造尋找特殊的方法和工具。方法和工具。有窮自動機分為兩類：確定的有窮自動機（有窮自動機分為兩類：確定的有窮自動機（

9、DFA）和）和不確定的有窮自動機（不確定的有窮自動機（NFA）。）。其中其中“不確定不確定”的含義是：對于某個輸入符號，在同的含義是：對于某個輸入符號，在同一狀態上存在不止一種轉換。一狀態上存在不止一種轉換。確定的和不確定的有窮自動機都能而且僅能識別正則確定的和不確定的有窮自動機都能而且僅能識別正則集合，即它們能夠識別正則表達式所表示的語言。集合，即它們能夠識別正則表達式所表示的語言。確定的有窮自動機確定的有窮自動機一個確定的有窮自動機一個確定的有窮自動機(DFA)M是一個五元式：是一個五元式：M=(S, , , s0, F)其中其中S是一個有限集，它的每個元素稱為一個狀態。是一個有限集，它的

10、每個元素稱為一個狀態。是一個有窮字母表，它的每個元素稱為一個輸入字是一個有窮字母表，它的每個元素稱為一個輸入字符符是一個從是一個從S至至S的的單值映射單值映射。(s,a)=s意味著：當意味著：當現行狀態為現行狀態為s、輸入字符為、輸入字符為a時，將轉換到下一個狀態時，將轉換到下一個狀態s。我們稱我們稱s為為s的一個后繼狀態。的一個后繼狀態。s0S，是唯一的初態。，是唯一的初態。F S，是一個終態集（可空），是一個終態集（可空） 確定的有窮自動機確定的有窮自動機DFA M=（S，U，V，Q，a，b，S，Q）其中）其中f定義為：定義為：（S，a）=U（V，a）=U（S，b）=V（V，b）=Q（U，

11、a）=Q（Q，a）=Q（U，b）=V（Q，b）=QabSUVUQVVUQQQQ字符字符狀態狀態bSUVQaaaba，bb確定的有窮自動機確定的有窮自動機DFA接受的字符串接受的字符串對于對于*中的任何字符串中的任何字符串t，若存在一條從初態結到某一終態結的，若存在一條從初態結到某一終態結的道路，且這條路上所有弧的標記符連接成的字符串等于道路，且這條路上所有弧的標記符連接成的字符串等于t，則稱，則稱t可為可為DFA M所接收，所接收，若若M的初態結同時又是終態結，則的初態結同時又是終態結，則空字空字可為可為M所識別。所識別。*上的符號串上的符號串t被被M接受接受若若t *， (S，t)=P，其中

12、，其中S為為 M的開始狀態，的開始狀態，P Z，Z為終態為終態集。則稱集。則稱t為為DFA M所接受（識別）。所接受（識別）。*上的符號串上的符號串t，（我們將它表示成，（我們將它表示成t1tx的形式，其中的形式，其中t1，tx *）在）在DFA M上上運行的定義為：的定義為： (Q, t1tx)= (Q, t1),tx) 其中其中QS確定的有窮自動機確定的有窮自動機例：證明例：證明t=baab被例中的被例中的DFA所接受。所接受。 (S,baab)= ( (S,b),aab)= (V,aab)= ( (V,a),ab)= (U,ab)= (f(U,a),b)= (Q,b)=QQ屬于終態。屬于

13、終態。DFA M=（S，U，V，Q，a，b，S，Q）其中）其中定義為：定義為：（S，a）=U（V，a）=U（S，b）=V（V，b）=Q（U，a）=Q（Q，a）=Q（U，b）=V（Q，b）=Q非確定的有窮自動機非確定的有窮自動機一個非確定的有窮自動機一個非確定的有窮自動機(NFA)M是一個五元式：是一個五元式：M=(S, , , S0, F)其中其中S是一個有限集，它的每個元素稱為一個狀態。是一個有限集，它的每個元素稱為一個狀態。是一個有窮字母表，它的每個元素稱為一個輸入字是一個有窮字母表，它的每個元素稱為一個輸入字符符是一個從是一個從S*至至S子集的單值映射。即：子集的單值映射。即：: S*

14、2SS0 S，是一個，是一個非空的初態集非空的初態集F S，是一個終態集（可空），是一個終態集（可空） 非確定的有窮自動機例子非確定的有窮自動機例子NFA N=（S,P,Z,0,1,S,P,Z）其中）其中(S,0)=P(S,1)=S，Z(P,1)=Z(Z,0)=P(Z,1)=PSPZ00,111101SPS,Z0PZ0ZPP1簡化為01SPS,Z0P.Z0ZPP1非確定的有窮自動機非確定的有窮自動機對于對于*中任何字中任何字，若存在一條從某一初態結點到某，若存在一條從某一初態結點到某一個終態結點的通路，且這條通路上所有弧的標記字一個終態結點的通路，且這條通路上所有弧的標記字依序連接成的字依序連

15、接成的字（忽略那些標記為（忽略那些標記為的弧）的弧）等于等于，則，則稱稱可為可為NFA M所識別（讀出或接受）。所識別（讀出或接受）。若若M的某些結點既是初態結點又是終態結點，或存在的某些結點既是初態結點又是終態結點，或存在一條從某一初態結點到某一終態結點的一條從某一初態結點到某一終態結點的通路，那么通路，那么空字空字可為可為M所識別。所識別。 NFANFA的確定化的確定化NFANFA的確定化的確定化顯然，顯然，DFA是是NFA的特例，但是對于每個的特例，但是對于每個NFA M都存都存在一個在一個DFA M，使，使L(M)=L(M)。 定義對狀態集合定義對狀態集合I的幾個有關運算：的幾個有關運

16、算：1 狀態集合狀態集合I的的 -閉包，表示為閉包，表示為 -closure(I)，定義為一，定義為一狀態集，是狀態集狀態集，是狀態集I中的任何狀態中的任何狀態s經任意條經任意條 弧而能到弧而能到達的狀態的集合。達的狀態的集合。狀態集合狀態集合I的任何狀態的任何狀態s都屬于都屬于 -closure(I)。2 狀態集合狀態集合I的的a弧轉換，表示為弧轉換，表示為move(I,a)定義為狀態定義為狀態集合集合J，其中，其中J是所有那些可從是所有那些可從I的某一狀態經過一條的某一狀態經過一條a弧而到達的狀態的全體。弧而到達的狀態的全體。定義定義Ia = -closure(move(I,a) - -閉

17、包的例子閉包的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4I=1,2, Ia= -closure(5,3,4)=2,3,4,5,6,7,8；12534687aa aNFANFA確定化的例子確定化的例子4f35621iaaaabbbbi,1,2i,1,21,2,31,2,31,2,31,2,31,2,41,2,41,2,3,5,6,f1,2,3,5,6,f1,2,41,2,41,2,31,2,3I Ib bI Ia a1,2,41,2,4SAB1,2,3,5,6,f1,2,3,5,6,fABCCA1,2,4,5,6

18、,f1,2,4,5,6,fD1,2,4,5,6,f1,2,4,5,6,fD1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,6,f1,2,3,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,5,6,fCE1,2,4,6,f1,2,4,6,fEF1,2,3,6,f1,2,3,6,fFD1,2,3,6,f1,2,3,6,fF1,2,4,5,6,f1,2,4,5,6,fD1,2,3,5,6,f1,2,3,5,6,fC1,2,4,6,f1,2,4,6,fEBNFANFA的確定化的確定化aCDBAEFSbaaaaabbbbbabFS SA AA AB BC CB BA

19、Ab ba aB BC CD DD DC CE EF FD DE EF FF FD DC CE EDFADFA的最小化的最小化DFA的最小化（的最小化（DFA的化簡）的化簡） 一個有窮自動機一個有窮自動機通過消除多余狀態和合并等價狀態而轉換成一個最小通過消除多余狀態和合并等價狀態而轉換成一個最小的與之等價的有窮自動機。的與之等價的有窮自動機。最小狀態最小狀態DFA沒有多余狀態沒有多余狀態(死狀態死狀態)沒有兩個狀態是互相等價（不可區別）沒有兩個狀態是互相等價（不可區別）兩個狀態兩個狀態s和和t可區別：不滿足可區別：不滿足兼容性（一致性）兼容性（一致性）同是終態或同是非終態同是終態或同是非終態傳

20、播性（蔓延性）傳播性（蔓延性）從狀態從狀態s出發讀入某個出發讀入某個a a和和從狀態從狀態t出發出發讀入某個讀入某個a到達的狀態等價。到達的狀態等價。DFADFA的最小化的最小化算法的核心算法的核心把把M的狀態集的狀態集K分成不相交的子集。分成不相交的子集。結論結論接受接受L的最小狀態有窮自動機不計同構是唯一的。的最小狀態有窮自動機不計同構是唯一的。DFA M =（K,f, k0, kt),最小狀態最小狀態DFA M1.構造狀態的初始劃分構造狀態的初始劃分：終態終態kt 和非終態和非終態K- kt兩組兩組2.對對施施用傳播性原則用傳播性原則 構造新劃分構造新劃分new 3. 如如new =,則

21、令則令 final= 并繼續步驟并繼續步驟4，否則否則:=new重復重復2 4.為為final中的每一組選一代表，這些代表構成中的每一組選一代表，這些代表構成M的狀態。若的狀態。若k是是一代表且一代表且f(k,a)=t,令令r是是t組的組的代表，則代表，則M中有一轉換中有一轉換f(k,a)=r M 的開始狀態是含有的開始狀態是含有K0的那組的代表的那組的代表 M的終態是含有的終態是含有Kt的那組的的那組的代表代表 5.去掉去掉M中的死狀態中的死狀態.DFADFA的最小化的最小化初始劃分：一個由終態組成，一初始劃分：一個由終態組成，一個由非終態組成個由非終態組成P0=(1,2,3,4,5,6,7

22、)P0=(1,2,3,4,5,6,7)觀察第一個子集，在讀入觀察第一個子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)觀察第二個子集，在讀入觀察第二個子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)觀察第四個子集，在讀入觀察第四個子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)正則文法與有限自動機的等價性正則文法與有限自動機的等價性對于正則文法對于正則文法G和有限自動機和有限自動機M，如果，如果L(G)=L(M)，則稱則稱G和和M是等價的。關于正則文法和有限自動機的是等價的。關于正則文法和有限自動機的等價問題，有以下結論：等價問題，有以下結論：對每一個右線性正則文法對每一個右線性正則文法G或左線性正則文法或左線性正則文法G，都存，都存在一個正則自動機在一個正則自動機(FA)M，使得，使得L(M)=L(G)。對每一個對每一個FA M，都存在一個右線性正則文法，都存在一個右線性正則文法GR和左線和左線性正則