第三章 詞法分析與有窮自動(dòng)機(jī)

1、第三章 詞法分析與有窮自動(dòng)機(jī) 詞法分析器的功能與輸出 單詞符號(hào)的兩種定義方式 正規(guī)表達(dá)式與有窮自動(dòng)機(jī) 正規(guī)文法與有窮自動(dòng)機(jī) 詞法分析器的設(shè)計(jì) 詞法分析程序自動(dòng)構(gòu)造工具LEX簡介b詞法分析：對(duì)字符串表示的源程序進(jìn)行從左到右的掃描和詞法分析：對(duì)字符串表示的源程序進(jìn)行從左到右的掃描和分解，根據(jù)語言的詞法規(guī)則識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的分解，根據(jù)語言的詞法規(guī)則識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的單詞符號(hào)。單詞符號(hào)。3.1 詞法分析器的功能b 通常將詞法分析程序設(shè)計(jì)為語法分析程序的子程序源程序詞法分析器語法分析器單詞符號(hào)取下一個(gè)單詞符號(hào) (1)詞法分析作為一個(gè)獨(dú)立的階段； (2)與語法分析組織成一遍，作為語法分析的

2、子程序詞法分析語法分析語義分析和中間代碼生成源程序中間代碼 符 號(hào) 表 管 理 錯(cuò) 誤 的 診 查 處 理一、 語言的單詞符號(hào) （token） 具有獨(dú)立意義的最小語法單位。3.2 單詞符號(hào)及輸出單詞的形式關(guān)鍵字標(biāo)識(shí)符常量運(yùn)算符界符：基本字 保留字：表示各種名字：常數(shù)：+ - * / ： , ; : ( )3.2.2 單詞的輸出形式： （單詞種別，單詞自身的值） 3.2 單詞符號(hào)及輸出單詞的形式1、單詞種別 單詞種別編碼：整數(shù)碼 一符一種、一類一種2、單詞自身的值 標(biāo)識(shí)符自身值的表示 常數(shù)自身值的表示詞法分析器的輸出： （單詞種別，單詞符號(hào)的屬性值）單詞種別提供給語法分析程序使用；單詞自身的屬性

3、值提供給語義分析程序使用。具體的分類設(shè)計(jì)以方便語法分析程序使用為原則。關(guān)鍵字可分成一類，也可以一個(gè)關(guān)鍵字分成一類。常數(shù)可統(tǒng)歸一類，也可按類型（整型、實(shí)型、布爾型等），每個(gè)類型的常數(shù)劃分成一類。while (i!=j) if (ij) ii-j; else j=ji;詞法分析器例while， (，i，!=，j， )， if，(，i，j,), i, = , i, - , j, ;, else, j, =, j, -, i , ;例如：程序段 if (ij) i=20; 經(jīng)詞法分析器處理后，輸出單詞符號(hào)系列：if， (， id，指向i的符號(hào)表入口的指針 ， id，指向j的符號(hào)表人口的指針）， id，

4、指向i的符號(hào)表入口的指針=， con，指向20的常量表入口的指針 ；， 2， 29， 10，指向i的符號(hào)表入口的指針 23， 10，指向j的符號(hào)表人口的指針30， 10，指向i的符號(hào)表入口的指針17， 11，指向20的常量表入口的指針 26， 單詞符號(hào)結(jié)構(gòu)的形式化描述方法：正規(guī)文法（型文法）(regular grammar)正規(guī)式（正規(guī)表達(dá)式）(regular expression)3.3 單詞符號(hào)的兩種定義方式例：標(biāo)識(shí)符的定義id let | id dig | id letlet ( let | dig )*一、定義 設(shè) =a1,a2,an是字母表 正規(guī)表達(dá)式 正規(guī)表達(dá)式表達(dá)的語言（正規(guī)集）

5、 1. ， ， 2. ai ai 3. 若有 r, s L( r ) , L(s) 則有 ( a ) r | s L( r ) L(s) ( b ) rs L( r ) L(s) ( c ) ( r )* ( L( r )* “*”，連接，“”運(yùn)算左結(jié)合，優(yōu)先級(jí)由高到低。3.3.1 正規(guī)式與正規(guī)集 正規(guī)式 正規(guī)集 a b a b a|b a,b ab ab (a|b)* ,a,b,aa,ab,ba,bb,aaa, 注意：a,b*的任一子集，不能也認(rèn)為是一個(gè)正規(guī)集。 如：anbn|n1例 3.2 =a,b,c aa*bb*cc*例 3.3例3.1 字母表=a,bR1=R2 正規(guī)式R1與R2等價(jià)

6、正規(guī)式的代數(shù)性質(zhì)： 恒等式 說明 rs=sr “”是可交換的 r(st)=(rs)t “”是可結(jié)合的 r(st)=(rs)t 連接是可結(jié)合的 r(st)=rs rt (st)r=srtr 分配律 r=r r=r 對(duì)連接，是單位元素 r*=(r)* “*”和之間的關(guān)系 r*=r* “*”是冪等的 正規(guī)集對(duì)應(yīng)的正規(guī)式練習(xí)：1、以1開頭以0結(jié)尾的二進(jìn)制串；2、倒數(shù)第三個(gè)符號(hào)是0的二進(jìn)制串；3、含有相繼的三個(gè)0的二進(jìn)制串；4、含有相繼的兩個(gè)0或相繼的兩個(gè)1的二進(jìn)制串；5、含有奇數(shù)個(gè)1的二進(jìn)制串；6、二進(jìn)制的奇數(shù)； =0,18、長度能被3整除的二進(jìn)制串；9、值能被3整除的二進(jìn)制串；7、每個(gè)1都有0直接跟

7、在后邊；3.3.2 正規(guī)文法與正規(guī)式n對(duì)任何正規(guī)文法G，存在定義同一語言的正規(guī)式r；n對(duì)任何正規(guī)式r，存在生成同一語言的正規(guī)文法G。n（等價(jià)關(guān)系，不是一一對(duì)應(yīng)）. 正規(guī)文法到正規(guī)式的轉(zhuǎn)換. 正規(guī)式到正規(guī)文法的轉(zhuǎn)換1. 正規(guī)文法到正規(guī)式的轉(zhuǎn)換將文法中的規(guī)則寫成關(guān)于每個(gè)非終結(jié)符的正規(guī)式方程，得到一個(gè)方程組；依照求解規(guī)則： 若A=A=AA | |，則解為A= A= * *； 若A=A=AA | |，則解為A= A= * *； 并使用正規(guī)式的代數(shù)性質(zhì)，求文法開始符號(hào)的解。例3.4 例3.5 例3.6 P36-37Z=0(0|01)*01. 正規(guī)文法到正規(guī)式的轉(zhuǎn)換將文法中的規(guī)則寫成關(guān)于每個(gè)非終結(jié)符的正規(guī)

8、式方程，得到一個(gè)方程組；依照求解規(guī)則： 若A=A=AA | |，則解為A= A= * *； 若A=A=AA | |，則解為A= A= * *； 并使用正規(guī)式的代數(shù)性質(zhì)，求文法開始符號(hào)的解。例3.4 例3.5 例3.6 P36-37例3.4 有正規(guī)文法G： Z 0A A 0A | 0B B 1A | 例3.6 有正規(guī)文法G： Z U0 | V1 U Z1 | 1 V Z0 | 0例3.5 有正規(guī)文法G： A aB | bB B aC | a | b C aBA=(a|b)(aa)*(a|b)Z=(10|01)(10|01)*2. 正規(guī)式到正規(guī)文法的轉(zhuǎn)換字母表 上的正規(guī)式R到等價(jià)的正規(guī)文法G：令V

9、T= ；令文法的開始符號(hào)S = R ；對(duì)形如Aab 的規(guī)則轉(zhuǎn)換為AaB 和Bb；在新的文法中，將形如Aa*b 的規(guī)則進(jìn)一步轉(zhuǎn)換為AaA | b；不斷利用和進(jìn)行轉(zhuǎn)換，直到每條規(guī)則的右部最多含有一個(gè)終結(jié)符號(hào)為止。 P37-38例3.8 R=(a|b)(aa)*(a|b)例3.9 R=e(e|d)*3.4 正規(guī)式與有窮自動(dòng)機(jī) 有窮自動(dòng)機(jī)（ finite automata）（FA）：具有離散輸入和輸出系統(tǒng)的一種抽象數(shù)學(xué)模型。能夠準(zhǔn)確地識(shí)別正規(guī)集。DFA NFA正規(guī)式R與FA M是等價(jià)的：n(1)對(duì)任何正規(guī)式R,都存在一個(gè)FA M 使得L(M)=L(R);n(2)對(duì)任何FA M,都存在一個(gè)正規(guī)式R, 使

10、得L(R)=L(M)3.4.1 確定有窮自動(dòng)機(jī)（DFA）n一個(gè) DFA M是一個(gè)五元式 M=（Q， ， ，S，F(xiàn)）其中，Q是有限狀態(tài)集，是輸入字符的字母表，n是Q到Q的單值部分映射（即狀態(tài)轉(zhuǎn)換）， (qi,a)=qj， nSQ是唯一初態(tài)， F 是終態(tài)集（可空）例3.10設(shè)DFA M=(q0,q1,q2,a,b,f,q0，q2）f(q1,a)=q1 f(q1,b)=q1 f(q2,a)=q2 f(q2,b)=q1 f(q0,a)=q1 f(q0,b)=q2一個(gè)DFA可用一個(gè)狀態(tài)轉(zhuǎn)換矩陣表示,行表示狀態(tài)，列表示輸入字符，矩陣元素表示(qi,a)的值。一個(gè)DFA也可用一個(gè)狀態(tài)轉(zhuǎn)換圖表示。 所以,一個(gè)

11、有三種表示方法：（1）轉(zhuǎn)換函數(shù)；（2）狀態(tài)轉(zhuǎn)換矩陣；（3）狀態(tài)轉(zhuǎn)換圖。例例 設(shè)（設(shè)（, ， , ， ， ，），）其中其中（，），（，），（，）（，）3（，），（，），（，）（，）（，），（，），（，）（，）（，），（，），（，）（，）ab012132213333轉(zhuǎn)換矩陣3b012aaaabbb3狀態(tài)轉(zhuǎn)換圖易存儲(chǔ) 從狀態(tài)轉(zhuǎn)換圖看，從初態(tài)出發(fā)，沿任一條路徑到達(dá)接受狀態(tài)，這條路徑上的弧上的標(biāo)記符號(hào)連接起來構(gòu)成的符號(hào)串被接受(識(shí)別)。 DFA M所能識(shí)別的字的全體即L(M)。字集V是正規(guī)的 iff V=L（M）012aaaabbb3b例：DFA，接受 0和1的個(gè)數(shù)都是偶數(shù)個(gè)的二進(jìn)制串312011110

12、000開始開始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇1解釋下列有限自動(dòng)機(jī)分別識(shí)別什么語言？123456789000000011111111345aaaaa2一個(gè) NFA M是一個(gè)五元式 M=（Q， ， ，S，F(xiàn)）它包括：n 狀態(tài)集合Qn 輸入符號(hào)集合 n 轉(zhuǎn)換函數(shù) : Q ( ) P(Q)n S 是非空開始狀態(tài)集n F Q是接受狀態(tài)集合 例3.11 P3912開始開始a0abb識(shí)別語言識(shí)別語言(a|b)*ab 的的NFA3.4.2 非確定有窮自動(dòng)機(jī)（NFA）12開始開始a0abb識(shí)別語言識(shí)別語言(a|b)*ab 的的NFA狀狀 態(tài)態(tài) NFA的轉(zhuǎn)換表的轉(zhuǎn)換表n例 識(shí)別aa* *| |bb

13、* *的NFA12開始開始a0abb34 注意： NFA M的狀態(tài)轉(zhuǎn)換圖中可有標(biāo)記為 的邊。DFA是NFA的特例。對(duì)于每一個(gè)NFA M存在一個(gè)DFA M ,使得L(M) = L(M )。也就是說，每一個(gè)NFA M都可以轉(zhuǎn)換成等價(jià)的DFA M 。NFADFA 實(shí)現(xiàn)最小化的DFA 3.4.3 由正規(guī)表達(dá)式R構(gòu)造NFA方法和步驟：X R= R= R=aR為復(fù)合正規(guī)式？XXX3.4.3 由正規(guī)表達(dá)式R構(gòu)造NFA方法和步驟：X R= R= R=aR為復(fù)合正規(guī)式？AA| AACACA例3.12 3.13 P41方法（子集法）1、改造M為M：引進(jìn)新的初態(tài)結(jié)點(diǎn)X、終態(tài)結(jié)點(diǎn)Y；對(duì)M的狀態(tài)轉(zhuǎn)換圖實(shí)施分裂（替換）2

14、、將M進(jìn)一步變換為DFA :狀態(tài)子集T的閉包_CLOSURE(T)定義狀態(tài)集Ta = _CLOSURE(J)從DFA的初態(tài)_CLOSURE(X)開始計(jì)算狀態(tài)轉(zhuǎn)換矩陣；直到不再產(chǎn)生新的狀態(tài)子集為止。、換名3.4.4 NFA確定化為DFA例3.14 3.15 P43-44定義狀態(tài)集Ta = _CLOSURE(J)： 若狀態(tài)子集T=t1,t2,tn，則(T,)= _CLOSURE(J);其中J=(t1,)(t2,) (tn,) i：若：若s T,T,則則s屬于屬于 _CLOSURE(T)；ii：若：若s T,T,則從則從s s出發(fā)經(jīng)過任意條出發(fā)經(jīng)過任意條 弧而能到達(dá)的狀態(tài)弧而能到達(dá)的狀態(tài)s都都屬于屬

15、于 _CLOSURE(T)。狀態(tài)子集T的閉包_CLOSURE(T)： NFA到DFA的變換 子集構(gòu)造法子集構(gòu)造法nDFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合n讀了輸入a1 a2 an后， NFA能到達(dá)的所有狀態(tài)：s1, s2, , sk，則 DFA到達(dá)狀態(tài)s1, s2, , sk12a開始開始0abb有 限 自 動(dòng) 機(jī)(NFA與DFA) NFA到DFA的變換 子集構(gòu)造法子集構(gòu)造法nDFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合n讀了輸入a1 a2 an后， NFA能到達(dá)的所有狀態(tài)：s1, s2, , sk，則 DFA到達(dá)狀態(tài)s1, s2, , sk12a開始開始0abb00, 1a有 限 自 動(dòng) 機(jī)(NF

16、A與DFA) NFA到DFA的變換 子集構(gòu)造法子集構(gòu)造法nDFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合n讀了輸入a1 a2 an后， NFA能到達(dá)的所有狀態(tài)：s1, s2, , sk，則 DFA到達(dá)狀態(tài)s1, s2, , sk12a開始開始0abb00, 1ab有 限 自 動(dòng) 機(jī)(NFA與DFA) NFA到DFA的變換 子集構(gòu)造法子集構(gòu)造法nDFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合n讀了輸入a1 a2 an后， NFA能到達(dá)的所有狀態(tài)：s1, s2, , sk，則 DFA到達(dá)狀態(tài)s1, s2, , sk12a開始開始0abb00, 1aba有 限 自 動(dòng) 機(jī)(NFA與DFA) NFA到DFA的變換 子

17、集構(gòu)造法子集構(gòu)造法nDFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合n讀了輸入a1 a2 an后， NFA能到達(dá)的所有狀態(tài)：s1, s2, , sk，則 DFA到達(dá)狀態(tài)s1, s2, , sk12a開始開始0abb00, 1aba0, 2b有 限 自 動(dòng) 機(jī)(NFA與DFA) NFA到DFA的變換 子集構(gòu)造法子集構(gòu)造法nDFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合n讀了輸入a1 a2 an后， NFA能到達(dá)的所有狀態(tài)：s1, s2, , sk，則 DFA到達(dá)狀態(tài)s1, s2, , sk12a開始開始0abb00, 1aba0, 2bab有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab678234

18、5 狀態(tài)狀態(tài) 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4,

19、 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345

20、狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4,

21、 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 動(dòng) 機(jī)(NFA與DFA)19開始開始 0ab ab6782345 狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 有 限 自 動(dòng) 機(jī)(NFA與DFA)有 限 自 動(dòng) 機(jī)(NFA與DFA)BD開始開始aAabbabCba19開始開始 0ab ab6782345 狀態(tài)狀態(tài) 有 限 自 動(dòng) 機(jī)(NFA與DFA)BD開始開始aAabbabCba12開

22、始開始a0abbab19開始開始 0ab ab6782345 識(shí)別語言識(shí)別語言(a|b)*ab 的的自動(dòng)機(jī)自動(dòng)機(jī) 有 限 自 動(dòng) 機(jī)(NFA與DFA)BD開始開始aAabbabCba12開始開始a0abbab19開始開始 0ab ab6782345 識(shí)別語言識(shí)別語言(a|b)*ab 的的自動(dòng)機(jī)自動(dòng)機(jī)子集構(gòu)造法不一子集構(gòu)造法不一定得到最簡定得到最簡DFA結(jié)論：NFA M通過“子集法”可以確定化為DFA M ，它們接收語言的能力是等價(jià)的，通常不區(qū)分（確定化時(shí)除外），合稱為有限自動(dòng)機(jī)(finite automata)（FA）。 3.4.5 DFA M的化簡DFA M的化簡是指:尋找一個(gè)狀態(tài)數(shù)比M少的

23、DFA M，使得L(M)=L(M)化簡了的DFA： 沒有多余狀態(tài) ； 沒有兩個(gè)狀態(tài)是等價(jià)的。3.4.5 DFA M的化簡M的狀態(tài)s和t是等價(jià)的： DFA M=（Q， ， ，S0，F(xiàn)），s,tQ 若對(duì)任何a*, (s,a)F當(dāng)且僅當(dāng)(t,a)F如果狀態(tài)s和t是不等價(jià)的，則稱s和t是可區(qū)別的。 DFA M的化簡方法：一個(gè)DFA M的狀態(tài)最少化過程：將M的狀態(tài)集分割成一些不相交的子集，任何不同的兩子集中的狀態(tài)都是可區(qū)別的，同一子集中的任何兩狀態(tài)都是等價(jià)的；最后，在每個(gè)子集中選一個(gè)狀態(tài)作代表，消去其他狀態(tài)，得到最少狀態(tài)的等價(jià)DFA M。例 3.16 3.17 P45-46步驟：將DFA M的狀態(tài)集Q分

24、劃成兩個(gè)子集：終態(tài)集和非終態(tài)集；對(duì)每個(gè)子集G，如果面對(duì)某個(gè)輸入符號(hào)得到的后繼狀態(tài)不屬于同一個(gè)子集，則將G進(jìn)一步分劃；重復(fù)直到不再產(chǎn)生新分劃；在每個(gè)子集中選一個(gè)狀態(tài)作代表，消去其他狀態(tài)，得到最少狀態(tài)的等價(jià)DFA M。3.4.6 有窮自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換1、改造M為M：引進(jìn)新的初態(tài)結(jié)點(diǎn)X、終態(tài)結(jié)點(diǎn)Y；2、對(duì)M的狀態(tài)轉(zhuǎn)換圖實(shí)施替換，逐步消除結(jié)點(diǎn)，直至只剩下結(jié)點(diǎn)X、Y替換規(guī)則：AA| AACAXP46例3.18CA1AB00110BD1A011C00(00|11)*(01|10)(1(0(11)*0)*1|0(1(00)*1)*0)*1(0(11)*0)*|(00|11)*0DBCA11110000開

25、始開始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇13.5 正規(guī)文法與有窮自動(dòng)機(jī)的等價(jià)性n對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M,如果L(G)=L(M),則稱G和M是等價(jià)的(equivalence)。n正規(guī)文法G和M的等價(jià)性是指：n(1)對(duì)每一個(gè)正規(guī)文法G,都存在一個(gè)FA M 使得L(M)=L(G);n(2)對(duì)每一個(gè)FA M,都存在一個(gè)GR和GL, 使得L(M)=L(GR)=L(GL)3.5.1 右線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換n對(duì)每一個(gè)正規(guī)文法GR,都存在一個(gè)FA M，使得L(M)=L( GR); 已知文法GR=(VT，VN，S，P), 構(gòu)造NFA M=(VN UD, VT, ,S，D)對(duì)Aa,有(

26、A,a)=D； 對(duì)AaB,有(A,a)=B；對(duì)A,有(A ,)=D例3.19文法GZ：Z 0AA 0A | 0BB 1A | 3.5.2 左線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換(略)n對(duì)每一個(gè)正規(guī)文法GL,都存在一個(gè)FA M，使得L(M)=L( GL); 已知文法GL=(VT，VN，S，P), 構(gòu)造NFA M=(VN Uq0, VT, ,q0，S)對(duì)Aa,有(q0,a)=A； 對(duì)ABa,有(B,a)=A；對(duì)A,有(q0,)=A P48例3.203.5.3-1 有窮自動(dòng)機(jī)到正規(guī)文法GR的轉(zhuǎn)換n對(duì)每一個(gè)FA M,都存在一個(gè)GR和GL, 使得L(M)=L(GR)=L(GL) 已知有窮自動(dòng)機(jī)FA M=(Q,

27、 , ,q0，Z) 構(gòu)造G=(VT，VN，S，P),令VT= ，VN= Q ，S=q0對(duì)(A,a)=B且B不是終態(tài)，有AaB ； 對(duì)(A,a)=B且B是終態(tài)，有AaB和B 或 Aa | aB ；若q0也是終態(tài)，則有規(guī)則SP49例3.21 3.223.5.3-2有窮自動(dòng)機(jī)到正規(guī)文法GL的轉(zhuǎn)換(略)n對(duì)每一個(gè)FA M,都存在一個(gè)GR和GL, 使得L(M)=L(GR)=L(GL)已知NFA M=（Q， ， ，q0，f）構(gòu)造文法GL=( ，Q- q0 ，f，P),對(duì)(A,a)=B,A是初態(tài),則有B a;否則B Aa若f也是初態(tài)，則有規(guī)則fn結(jié)論:正規(guī)文法、正規(guī)式、DFA、NFA在識(shí)別（接收）語言的能力

28、上是互相等價(jià)的。值能被4整除的二進(jìn)制串。正規(guī)式：正規(guī)式：FA：正規(guī)文法：正規(guī)文法： (0|1)*00 | 03.6 詞法分析程序的編寫n設(shè)置單詞種別和屬性，用正規(guī)式編寫詞法規(guī)則n從單詞的描述出發(fā)，逐步實(shí)現(xiàn)詞法分析程序n手工方法n利用LEX自動(dòng)生成3.6 詞法分析程序的編寫n設(shè)置單詞種別和屬性，用正規(guī)式編寫詞法規(guī)則n從單詞的描述出發(fā)，逐步實(shí)現(xiàn)詞法分析程序正規(guī)表達(dá)式正規(guī)表達(dá)式狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖識(shí)別過程的實(shí)現(xiàn)算法識(shí)別過程的實(shí)現(xiàn)算法程序?qū)崿F(xiàn)和測試程序?qū)崿F(xiàn)和測試P50-53011393實(shí)現(xiàn)：讓每個(gè)狀態(tài)對(duì)應(yīng)一小段程序詞法分析(lexical analysis)n狀態(tài)轉(zhuǎn)換圖n正規(guī)式與正規(guī)集n確定有限自動(dòng)機(jī)(DFA)n非確定有限自動(dòng)機(jī)(NFA)nNFA確定化為DFA，DFA化簡n正規(guī)式