編譯原理課件：Chapter-3 詞法分析

1、第三章 詞法分析3.1 詞法分析的功能3.2 詞法分析程序的設(shè)計與實(shí)現(xiàn)狀態(tài)圖3.3 詞法分析程序的自動生成有窮自動機(jī)3.1 詞法分析程序的功能及實(shí)現(xiàn)方案 詞法分析程序的功能詞法分析：根據(jù)詞法規(guī)則識別及組合單詞，進(jìn)行詞法檢查。對數(shù)字常數(shù)完成數(shù)字字符串到（二進(jìn)制）數(shù)值的轉(zhuǎn)換。刪去空格字符和注解。實(shí)現(xiàn)方案：基本上有兩種1. 詞法分析單獨(dú)作為一遍2. 詞法分析程序作為單獨(dú)的子程序S.P.(字符串)詞法分析S.P.(符號串)語法分析第一遍第二遍單詞串優(yōu)點(diǎn): 結(jié)構(gòu)清晰、各遍功能單一缺點(diǎn)：效率低S.P.(字符串)詞法分析程序語法分析程序取單詞單詞3.2 單詞的種類及詞法分析程序的輸出形式單詞的種類 1. 保

2、留字：begin、end、for、do2. 標(biāo)識符：3. 常數(shù)：無符號數(shù)、布爾常數(shù)、字符串常數(shù)等4. 分界符：+、-、*、/詞法分析程序的輸出形式單詞的內(nèi)部形式幾種常用的單詞內(nèi)部形式：1、按單詞種類分類2、保留字和分界符采用一符一類3、標(biāo)識符和常數(shù)的單詞值可為指示字（指針值）單詞類別 單詞值單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點(diǎn)數(shù)布爾常數(shù)字符串常數(shù)保留字分界符類別編碼1234567單詞值內(nèi)部字符串整數(shù)值數(shù)值0 或 1內(nèi)部字符串保留字或內(nèi)部編碼分界符或內(nèi)部編碼方案1、按單詞種類分類方案2、保留字和分界符采用一符一類單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點(diǎn)數(shù)布爾常數(shù)字符串常數(shù)BEGINENDFO

3、RDO:+*,(類別編碼123456789.20212223.單詞值內(nèi)部字符串整數(shù)值數(shù)值0 或 1內(nèi)部字符串-.-3.3 正則文法和狀態(tài)圖 狀態(tài)圖的畫法（根據(jù)文法畫出狀態(tài)圖）例如：正則文法 Z:= U0 | V1 U :=Z1 | 1 V :=Z0 | 0左線性文法 L(GZ) = Bn | n0 , 其中 B= 01,10左線性文法狀態(tài)圖的畫法：1. 令G的每個非終結(jié)符都是一個狀態(tài)；2. 設(shè)一個開始狀態(tài)S；3. 若Q:=T, Q Vn, TVt,則：QST4. 若Q:=RT, Q、RVn, TVt,則：QRT5. 按自動機(jī)方法，可加上開始狀態(tài)和終止?fàn)顟B(tài)標(biāo)志。例：正則文法 Z:= U0 |V1

4、 U :=Z1 |1 V :=Z0 | 0例如：正則文法 Z:= U0 | V1 U :=Z1 | 1 V :=Z0 | 0 其狀態(tài)圖為：SUVZ111000初始狀態(tài)終止?fàn)顟B(tài)識別算法（自然語言描述）利用狀態(tài)圖可按如下步驟分析和識別字符串x：1、置初始狀態(tài)為當(dāng)前狀態(tài)，從x的最左字符開始，重復(fù)步驟2，直到x右端為止。2、掃描x的下一個字符，在當(dāng)前狀態(tài)所射出的弧中找出標(biāo)記有該字符的弧，并沿此弧過渡到下一個狀態(tài)； 如果找不到標(biāo)有該字符的弧，那么x不是句子，過程到此結(jié)束； 如果掃描的是x的最右端字符，并從當(dāng)前狀態(tài)出發(fā)沿著標(biāo)有該字符的弧過渡到下一個狀態(tài)為終止?fàn)顟B(tài)Z，則x是句子。例：x=01101 和101

5、1 問題：1、上述分析過程是屬于自底向上分析？還是自頂向下分析？2、怎樣確定句柄？3.4 詞法分析程序的設(shè)計與實(shí)現(xiàn)詞法規(guī)則 狀態(tài)圖 詞法分析程序3.4.1 文法及其狀態(tài)圖語言的單詞符號 標(biāo)識符 保留字（標(biāo)識符的子集） 無符號整數(shù) 單分界符 +、*、：、，（、） 雙分界符 := 兩點(diǎn)說明：1、注釋符號 /* 和 */ 以及 /。詞法分析程序不輸出注釋！2、各單詞之間用空白符號（空格、制表、回車）分開。標(biāo)識符S標(biāo)字母字母、數(shù)字無符號整數(shù)S無數(shù)字?jǐn)?shù)字單字符分界符S單界+ * ，（ ）雙字符分界符S冒號：雙界=文法：1. := 字母 | 字母 | 數(shù)字 2. :=數(shù)字 | 數(shù)字 3. := : | +

6、 | * | , | ( | ) 4. := = 5. := :出口非字母數(shù)字出口非數(shù)字出口其它字符出口其它字符非 =正則文法！標(biāo)識符無符號整數(shù)單字符分界符雙字符分界符S標(biāo)非字母數(shù)字字母字母、數(shù)字?jǐn)?shù)非數(shù)字?jǐn)?shù)字?jǐn)?shù)字單界其它字符+ * ，（ ）出口冒號其它字符：雙界=非 =出錯其它讀字符查保留字表返回S3.4.2 狀態(tài)圖的實(shí)現(xiàn)構(gòu)造詞法分析程序1. 單詞及內(nèi)部表示2. 詞法分析程序需要引用的公共（全局）變量和過程3. 詞法分析程序算法1.單詞及內(nèi)部表示：保留字和分界符采用一符一類單詞名稱BEGINENDFORDOIFTHENELSE標(biāo)識符常數(shù)(整):+*,():=類別編碼12345678910111

7、213141516記憶符BEGINSYENDSYFORSYDOSYIFSYTHENSYELSESYIDSYINTSYCOLONSYPLUSSYSTARSYCOMSYLPARSYRPARSYASSIGNSY單詞值-內(nèi)部字符串整數(shù)值-2.詞法分析程序需要引用的公共（全局）變量和過程名 稱類 型功 能CHAR字符變量存放當(dāng)前讀入的字符TOKEN字符數(shù)組存放單詞字符串GETCHAR讀字符過程讀字符到CHAR，移動指針GETNBC過程反復(fù)調(diào)用GETCHAR，直至CHAR進(jìn)入一個非空白字符CAT過程CHAR與TOKEN連接ISLETTER 和 ISDIGIT布爾函數(shù)判斷CHAR是字母還是數(shù)字UNGETCH

8、過程讀字符指針后退一個字符RESERVE布爾函數(shù)判斷TOKEN中的字符串是保留字，還是標(biāo)識符ATOI函數(shù)字符串到數(shù)字的轉(zhuǎn)換ERROR過程出錯處理3、詞法分析程序算法START: TOKEN := ; /*置TOKEN為空串*/ GETCHAR; GETNBC; CASE CHAR OF A.Z: BEGIN WHILE ISLETTER OR ISDIGET DO BEGIN CAT; GETCHAR; END UNGETCH; C:= RESERVE; IF C=0 THEN RETURN(IDSY, TOKEN) ELSE RETURN (C,-); /*C為保留字編碼*/END 0.9:

9、 BEGIN WHILE ISDIGIT DO BEGIN CAT; GETCHAR; END UNGETCH; RETURN (INTSY,ATOI); END+ : RETURN(PLUSSY,-) ;S標(biāo)非字母數(shù)字字母字母、數(shù)字?jǐn)?shù)非數(shù)字?jǐn)?shù)字?jǐn)?shù)字單界其它字符+ * ，（ ）出口冒號其它字符：雙界=非=出錯其它* : RETURN(STARSY,-) ;, : RETURN(COMMASY,-) ;( : RETURN(LPARSY,-) ;) : RETURN(RPARSY,-) ;: : BEGINGETCHAR;if CHAR= THEN RETURN(ASSIGNSY,-);UNGE

10、TCH;RETURN(COLONSY,-) ; ENDEND OF CASEERROR;GOTO START;S標(biāo)非字母數(shù)字字母字母、數(shù)字?jǐn)?shù)非數(shù)字?jǐn)?shù)字?jǐn)?shù)字單界其它字符+ * ，（ ）出口冒號其它字符：雙界=非=出錯其它3.5 正則表達(dá)式與有窮自動機(jī)3.5.1 正則表達(dá)式和正則集合的遞歸定義有字母表, 定義在 上的正則表達(dá)式和正則集合遞歸定義如下:1. 和 都是 上的正則表達(dá)式，它們所表示的正則集合分別為: 和 ;2. 任何 a , a 是 上的正則表達(dá)式，它所表示的正則集合為: a ; 3. 假定 U 和 V 都是 上的正則表達(dá)式， 它們所表示的正則集合分別記為 L( U )和L( V )，那

11、么U | V，U V和 U* 也都是 上的正則表達(dá)式，它們所表示的正則集合分別為L( U )L( V )、L( U ) L( V )和 L( U )* ;4. 任何 上的正則表達(dá)式和正則集合均由1、2和3產(chǎn)生。正則表達(dá)式中的運(yùn)算符： | 或（選擇） 連接 * 或 重復(fù) （） 括號與集合的閉包運(yùn)算有區(qū)別這里a*表示由任意個a組成的串，而a,b* = ，a，b，aa，ab，ba，bb，.運(yùn)算符的優(yōu)先級： 先*, 后 , 最后 | 在正則表達(dá)式中可以省略。正則表達(dá)式相等 這兩個正則表達(dá)式表示的語言相等。 例：設(shè) = a,b ,下面是定義在上的正則表達(dá)式和正則集合正則表達(dá)式ba*a(a|b)*(a|b

12、)*(aa|bb)(a|b)* 正則集上所有以b為首，后跟任意多個a的字。上所有以a為首的字。上所有含有兩個相繼的a或兩個相繼的b的字。正則表達(dá)式的性質(zhì)： 設(shè)e1, e2和e3均是某字母表上的正則表達(dá)式, 則有: 單位正則表達(dá)式: e = e = e 交換律: e1|e2 = e2|e1結(jié)合律: e1|(e2|e3) = (e1|e2)|e3 e1(e2e3) = (e1e2)e3分配律: e1(e2|e3) = e1e2|e1e3 (e1|e2)e3 = e1e3|e2e3 此外: r* = (r|)* r* =r* (r|s)* = (r*s*)*例： 3型文法 S:= aS|aBB:=

13、bCC:= aC|a正則表達(dá)式aS|aba*aba*aa*a正則表達(dá)式與3型文法等價例如：正則表達(dá)式： ba* a(a|b)* 3型文法： Z := Za|b Z:=Za|Zb|a a*aba*a3.5.2 確定有窮自動機(jī)（DFA） 前面介紹狀態(tài)圖的形式化一個確定的有窮自動機(jī)（DFA）M是一個五元式:M = ( S , ，,s0, Z ) 其中:1. S 有窮狀態(tài)集2. 輸入字母表3. 映射函數(shù)(也稱狀態(tài)轉(zhuǎn)換函數(shù)) SS (s, a) = s s, s S, a4. s0 初始狀態(tài) s0 S5. Z終止?fàn)顟B(tài)集 Z Ss叫做s的后繼狀態(tài)狀態(tài)轉(zhuǎn)移函數(shù)可用一矩陣來表示： 輸入 字符 狀態(tài) a b 0

14、 1 2 1 3 2 2 1 3 3 3 3例如: M: ( 0, 1, 2, 3 , a, b , ，0，3 ) ( 0，a ) = 1 ( 0，b ) =2 ( 1，a ) = 3 ( 1，b ) =2 ( 2，a ) = 1 ( 2，b ) =3 ( 3，a ) = 3 ( 3，b ) =3所謂確定的狀態(tài)機(jī)，其確定性表現(xiàn)在狀態(tài)轉(zhuǎn)移函數(shù)是單值函數(shù)！一個DFA也可以用一狀態(tài)轉(zhuǎn)換圖表示： 輸入 字符 狀態(tài) a b 0 1 2 1 3 2 2 1 3 3 3 3DFA的狀態(tài)圖表示：1032startaabba,bba換言之：若存在一條從初始狀態(tài)到某一終止?fàn)顟B(tài)的路徑，且這條路徑上所有弧的標(biāo)記符連接

15、成符號串,則稱為DFA M(接受)識別。DFA M所接受的符號串： 令= a1 a2an，*， 若(s0, a1), a2) , an-1）, an ) = sn, 且sn Z， 則可以寫成(s0, ) = sn, 我們稱可為M所接受。DFA M所接受的語言為：L(M)=|( s0, )= sn, snZ3.5.3 非確定的有窮自動機(jī)(NFA) 若是一個多值函數(shù)，且輸入可允許為，則有窮自動機(jī)是不確定的。即在某個狀態(tài)下，對于某個輸入字符存在多個后繼狀態(tài)。NFA的形式定義為：一個非確定的有窮自動機(jī)NFA M是一個五元式: NFA M = ( S, , , S0, Z )其中 S 有窮狀態(tài)集 輸入符

16、號加上，即自動機(jī)的每個結(jié)點(diǎn)所射出 的弧可以是中的一個字符或是。 S0 初態(tài)集 Z 終態(tài)集 轉(zhuǎn)換函數(shù) S 2S (2S ：S的冪集S的子集構(gòu)成的集合）NFA M所接受的語言為: L(M) = |( S0,) = S SZ 例： NFA M= (1, 2, 3, 4, , a, b, c , 1, 4) 符號 狀態(tài) a b c 1 4 2，3 2 2 4 3 3，4 4 上例題相應(yīng)的狀態(tài)圖為： 1234startabacacM 所接受的語言（用正則表達(dá)式） R=aa b|ac c| 符號 狀態(tài) a b c 1 4 2，3 2 2 4 3 3，4 4 總結(jié)：1. 正則表達(dá)式與有窮自動機(jī)，給出兩者定義

17、。用3型文法所定義的語言都可以用正則表達(dá)式描述。用正則表達(dá)式描述單詞是為了指導(dǎo)生成詞法分析程序。有一個正則表達(dá)式則對應(yīng)一個正則集合。若V是正則集合，iff V = L ( M )。即一個正則表達(dá)式對應(yīng)一個DFA M。2. NFA定義。非單值函數(shù)，且有弧 ，表現(xiàn)為非確定性。 如： (S,a)=s1,s2 (S,a)=s1 ,s3 saas1s2ss1s2s3aa3.5.4 NFA的確定化 已證明：非確定的有窮自動機(jī)與確定的有窮自動機(jī)從功能上來說是等價的。也就是說，我們能夠從：NFA MDFA M構(gòu)造成一個使得 L(M) = L(M)為了使得NFA確定化，我們首先給出兩個定義：定義1、集合 I 的

18、 -閉包：令 I 是一個狀態(tài)集的子集，定義-closure（I）為：1）若sI，則s-closure（I）；2）若sI，則從 s 出發(fā)經(jīng)過任意條弧能夠到達(dá)的任何 狀態(tài)都屬于-closure（I）。 狀態(tài)集-closure（I）稱為 I 的-閉包。我們可以通過一例子來說明狀態(tài)子集的-閉包的構(gòu)造方法。例：如圖所示的狀態(tài)圖：令I(lǐng)=1，求-closure（I）=？156432aaa根據(jù)定義：-closure（I）=1，3 我們同樣可以通過一例子來說明上述定義，仍采用前面給定狀態(tài)圖為例。 J 是從狀態(tài)子集 I 中的每個狀態(tài)出發(fā)，經(jīng)過標(biāo)記為 a 的弧而達(dá)到的狀態(tài)集合。 Ia是狀態(tài)子集，其元素為 J 中的狀

19、態(tài)，加上從 J 中每一個狀態(tài)出發(fā)通過弧到達(dá)的狀態(tài)。定義2: 令 I 是NFA M的狀態(tài)集的一個子集，a 定義: Ia =- closure(J) 其中J = (s, a)SI例：令 I=1 Ia=-closure(J) =-closure(（1，a） =-closure(2，4）=2，4，6 根據(jù)定義1、2，可以將上述的M確定化（即可構(gòu)造出狀態(tài)的轉(zhuǎn)換矩陣）。156432aaa I Ia Ib Ic 1,4 2,3 2,3 2 4 3,4 2 2 4 4 3,4 3,4 1234startabacac A B B C D E C C D D E E 1,4 2,3 2,3 2 4 3,4 2 2

20、 4 4 3,4 3,4 I Ia Ib Ic 1234startabacac將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號DFA M狀態(tài)轉(zhuǎn)換矩陣： 符號狀態(tài)abc0 2 341221_3344DFA M的狀態(tài)圖： 注意：包含原初始狀態(tài) 1 的狀態(tài)子集為DFA M的初態(tài)； 包含原終止?fàn)顟B(tài) 4 的狀態(tài)子集為DFA M的終態(tài)。01423start1,42,342acabbc3,4由于正則集合與正則表達(dá)式相對應(yīng)，所以該定理表明了正則表達(dá)式與DFA的等價性。V是正則集合，R是與其相對應(yīng)的正則表達(dá)式 DFA M V=L(R) L(M)=L(R) 所以，正則表達(dá)式R NFA M DFA M L(R) = L(M) = L(

21、M)證明：根據(jù)定義.3.5.5 正則表達(dá)式與DFA的等價性定理：在上的一個字集V（V*）是正則集合，當(dāng)且僅當(dāng) 存在一個DFA M，使得V = L( M )。3.6 詞法分析程序的自動生成器LEX（LEXICAL）LEX的功能：LEX源程序S.P.字符串LEXL詞法分析程序LS.P.單詞字符串下面我們介紹LEX源程序：3.6.1 LEX源程序一個LEX源程序主要由三個部分組成：1. 規(guī)則定義式2. 識別規(guī)則3. 用戶子程序各部分之間用%隔開。規(guī)則定義式是如下形式的LEX語句：D1 R1 D2 R2 Dn Rn 其中： R1, R2，Rn 為正則表達(dá)式。 D1, D2，Dn 為正則表達(dá)式名字，稱簡

22、名。 例如某種語言標(biāo)識符： letterA|B|Z digit 0|1| |9 iden letter(letter|digit)*帶符號整數(shù)： integerdigit (digit)* sign +| - | signinteger sign integer識別規(guī)則：是一串如下形式的LEX語句： P1 A1 P2 A2 Pm Am Pi ：定義在D1,D2,Dn上的正則表達(dá)式，也稱詞形。Ai：Ai為語句序列。它指出在識別出詞形為Pi的單詞以后，詞法分析器所應(yīng)作的動作。 其基本動作是返回單詞的類別編碼和單詞值。下面是識別某語言單詞符號的LEX源程序：例：LEX 源程序 AUXILIARY D

23、EFINITIONS /*輔助定義*/ letter A|B|Z digit 0|1|9 % RECOGNITION RULES /*識別規(guī)則*/1.BEGIN 2.END 3.FOR RETURN(1,) RETURN(2,) RETURN(3,) RETURN是LEX過程，該過程將單詞傳給語法分析程序 RETURN（C，LEXVAL） 其中C為單詞類別編碼 LEXVAL： 標(biāo)識符：TOKEN（字符數(shù)組） 整常數(shù)：DTB（數(shù)值轉(zhuǎn)換函數(shù)，將TOKEN 中的數(shù)字串轉(zhuǎn)換二進(jìn)制） 其他單詞：無定義。6.THEN 7.ELSE 8.letter(letter |digit)* 9.digit(digi

24、t)* RETURN(6,) RETURN(7,) RETURN(8,TOKEN) RETURN(9,DTB 4.DO 5.IF RETURN(4,) RETURN(5,) 10. : 11. + 12. “*” RETURN(10,) RETURN(11,) RETURN(12,) 13. , 16. := 17. = RETURN(13,) RETURN(14,) RETURN(15,) RETURN(16,) RETURN(17,) 14. “（” 15. “）” %/* definitions of manifest constantsLT, LE, EQ, NE, GT, GEIF,

25、 THEN, ELSE, ID, NUMBER, RELOP */%/* regular definitions */delim tnwsdelim+letterA-Za-zdigit0-9idletter(letter|digit)*numberdigit+(.digit+)?(E+-?digit+)?%ws/* no action and no return */ifreturnIF;thenreturnTHEN;elsereturnELSE;idyylval = (int) installID();return(ID);numberyylval = (int) installNum();

26、return(NUMBER);“”yylval = LT; return(RELOP);“=”yylval = LE; return(RELOP);“=”yylval = EQ; return(RELOP);“”yylval = NE; return(RELOP);“”yylval = GT; return(RELOP);“=”yylval = GE; return(RELOP);%int installID() /* function to install the lexeme, whose first character is pointed to by yytext, and whose

27、 length is yyleng, into the symbol table and return a pointer thereto */int installNum() /* similar to installID, but puts numerical constants into a separate table */規(guī)則定義式識別規(guī)則用戶子程序3.6.2 LEX的實(shí)現(xiàn) LEX的功能是根據(jù)LEX源程序構(gòu)造一個詞法分析程序，該詞法分析器實(shí)質(zhì)上是一個有窮自動機(jī)。LEX生成的詞法分析程序由兩部分組成：詞法分析程序狀態(tài)轉(zhuǎn)換矩陣(DFA)控制執(zhí)行程序LEX的功能是根據(jù)LEX源程序生成狀態(tài)轉(zhuǎn)

28、換矩陣和控制程序LEX的處理過程： 掃描每條識別規(guī)則Pi構(gòu)造一相應(yīng)的非確定有窮自動機(jī)Mi將各條規(guī)則的有窮自動機(jī)Mi合并成一個新的NFA M確定化 NFADFA生成該DFA的狀態(tài)轉(zhuǎn)換矩陣和控制執(zhí)行程序0P1startM1P2M2P3M3LEX二義性問題的兩條原則：1. 最長匹配原則 在識別單詞過程中，有一字符串 x x x x x 根據(jù)最長匹配原則，應(yīng)識別為這是 一個符合Pk規(guī)則單詞，而不是Pj和Pi規(guī)則的單詞。PjPiPk2. 最優(yōu)匹配原則 如有一字符串，有兩條規(guī)則可以同時匹配時，那么用規(guī)則序列中位于前面的規(guī)則相匹配，所以排列在前面的規(guī)則優(yōu)先權(quán)最高。如:begin, :=例：字符串beginP

29、8P1根據(jù)原則，應(yīng)該識別為關(guān)鍵字begin，所以在寫LEX源程序時應(yīng)注意規(guī)則的排列順序。另要注意的是，優(yōu)先匹配原則是在符合最長匹配的前提下執(zhí)行的。我們可以通過一個例子來說明這些問題。例： LEX源程序， a abb a bb 一.讀LEX源程序，分別生成NFA，用狀態(tài)圖表示為：二.合并成一個NFA：031745268startbbbbaaastart12ab3456startabb78startab 狀態(tài) a b 到達(dá)終態(tài)所識別的單詞0,1,3,7 2,4,7 8 7 5,8 6,8 2,4,7 7 7 8 5,8 8 8 8 6,8 三.確定化 給出狀態(tài)轉(zhuǎn)換的矩陣初態(tài)a*bb*aa*bb*a

30、bb或a*bb*在此DFA M中 初態(tài)為0,1,3,7 終態(tài)為2,4,7,8,5,8,6,8終態(tài)終態(tài)終態(tài)終態(tài)031745268startbbbbaaa6,8集合存在二義性！解決方法：多個終態(tài)規(guī)則式誰在先就算誰！詞法分析程序的分析過程令輸入字符串為aba讀入字符讀入字符開始 a b a0,1,3,72,4,75,8無后繼狀態(tài)(退掉輸入字符a)(1) 吃進(jìn)字符ab(2) 按反序檢查狀態(tài)子集檢查前一次狀態(tài)是否含有原NFA的終止?fàn)顟B(tài)即檢查5,8。含有終態(tài)8，因此斷定所識別的單詞ab是屬于 a*bb*中的一個。若在狀態(tài)子集中無NFA的終態(tài)，則要從識別的單詞再退掉一個字符(b)，然后再檢查上一個狀態(tài)子集。

31、若一旦吃進(jìn)的字符都退完，則識別失敗，調(diào)用出錯程序，一般是跳過一個字符然后重新分析。(應(yīng)打印出錯信息)三點(diǎn)說明：1)以上是LEX的構(gòu)造原理，雖然是原理性，但據(jù)此就不 難將LEX構(gòu)造出來。2)所構(gòu)造出來的LEX是一個通用的工具，用它可以生成 各種語言的語法分析程序，只需要根據(jù)不同的語言書 寫不同的LEX源文件就可以了。3)LEX不但能自動生成詞法分析器，而且也可以產(chǎn)生多 種模式識別器及文本編輯程序等。第三章作業(yè)：P56：1、2、4P76：1、2、4、5補(bǔ)充習(xí)題1.有正則表達(dá)式1(0|1)*101 構(gòu)造DFA2.試將下列自動機(jī)確定化：10startaaa,b補(bǔ)充正則文法NFA正則表達(dá)式123456D

32、FA最小化補(bǔ)充正則文法NFA正則表達(dá)式123456DFA最小化（1）有窮自動機(jī) 正則文法1.對轉(zhuǎn)換函數(shù)f (A, t) = B，可寫成一個產(chǎn)生式:AtB算法:2.對可接受狀態(tài)Z，增加一個產(chǎn)生式：Z3.有窮自動機(jī)的初態(tài)對應(yīng)于文法的開始符號， 有窮自動機(jī)的字母表為文法的終結(jié)符號集。ABt例：給出如圖NFA等價的正則文法GABCDstartaaabbbbG=（A，B，C，D，a，b，P，A）其中P: A aB A bD B bC C aA C bD C D aB D bD D （2）正則文法 有窮自動機(jī)M算法:1. 字母表與G的終結(jié)符號相同。2. 為G中的每個非終結(jié)符生成M的一個狀態(tài)，G的開始符號S

33、是開始狀態(tài)S。3. 增加一個新狀態(tài)Z，作為NFA的終態(tài)。4. 對G中的形如AtB，其中t為終結(jié)符或,A和B為非終結(jié)符的產(chǎn)生式，構(gòu)造M的一個轉(zhuǎn)換函數(shù)f (A, t) = B。5. 對G中的形如At的產(chǎn)生式，構(gòu)造M的一個轉(zhuǎn)換函數(shù) f (A, t) = Z。例:求與文法GS等價的NFA GS: SaA | bB | AaB | bA BaS | bA |SZABstartaaabbb求得：（3）正則式 有窮自動機(jī)語法制導(dǎo)方法1.(a)對于正則式,所構(gòu)造NFA: xy (b)對于正則式,所構(gòu)造NFA: xy (c)對于正則式a, a,則 NFA: xya2.若s,t為上的正則式,相應(yīng)的NFA分別為N(

34、s)和N(t);(a)對于正則式R = s | t , NFA(R) xyN(s)N(t) 或:N(s)xN(t)y (b)對正則式R = s t , NFA(R)xyN(s)N(t)(c)對于正則式R = s*, NFA(R) xyN(s)(d)對R = ( s )，與R = S的NFA一樣。 例:為R=( a|b ) abb構(gòu)造NFA，使得L(N)=L(R)*從左到右分解R,令r1=a,第一個a,則有 23a令r2=b,則有 45b令r3= r1 |r2,則有 164532ab令r4= r3 則有: 164532ab*07令r5=a,令r6=b令r7=b令r8= r5 r6令r9= r8

35、r7 則有 910b87baR=(a|b)*abb令r10= r4 r9 則最終得到NFA N: 164532ab071089abb 分解R的方法有很多種。下面我們看看另一種分解方式和所構(gòu)成的NFA。R=(a|b)*abb iyx(a|b)*abb（a） iyxabbjab（c） iyxbjabklba（d）R=(a|b)*abb iyxabbj（b）a|b（4）有窮自動機(jī) 正則式R算法: 1)在M上加兩個結(jié)點(diǎn)x, y。從x用弧連接到M的所有初態(tài)結(jié)點(diǎn)，從M的所有終態(tài)結(jié)點(diǎn)用弧連接到y(tǒng)，形成與M等價的M。M只有一個初態(tài)x和一個終態(tài)y。 2)逐步消去M中的所有結(jié)點(diǎn)，直至剩下x和y為止。在消除結(jié)點(diǎn)的過

36、程中，逐步用正則式來標(biāo)記箭弧。其消結(jié)規(guī)則如下： 1.對于 代之為 2.對于 代之為3.對于 代之為R1R212331R1R21221R2R1R2R1|31R1R2R3R1R3123R2例:M:03214starta,ba,ba,bbbaa解: (1)加x和yx03412yaa,ba,ba,babb(2)消除M中的所有結(jié)點(diǎn)a|bx024yaabba|ba|bx0yaa(a|b) *bb(a|b) *a|bx03412yaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*（5）正則文法 正則式 利用以下轉(zhuǎn)換規(guī)則，直至只剩下一個開始符號定義的產(chǎn)生式，并且產(chǎn)生式的右部不含非終結(jié)符。規(guī)則規(guī)則1規(guī)則2規(guī)則3文法產(chǎn)生式正則式AxB, ByAxA | yAx, AyA=xyA=x*yA=x|y例：有文法G s Sa A | a Aa A | d A | a | d于是：S = a A | a A= ( a A | d A ) | ( a | d ) A = ( a | d ) A | ( a | d )由規(guī)則二： A= ( a | d )* ( a | d ) 代入：S = a ( ( a | d )* ( a | d ) ) | a 于是：S = a ( ( a | d )* ( a