第二章詞法分析

1、第二章第二章 詞法分析詞法分析本章內(nèi)容本章內(nèi)容 詞法分析器：把構(gòu)成源程序的字符流翻譯成詞法分析器：把構(gòu)成源程序的字符流翻譯成記號(hào)流，記號(hào)流，還完成和用戶接口的一些任務(wù)還完成和用戶接口的一些任務(wù) 圍繞詞法分析器的自動(dòng)生成展開圍繞詞法分析器的自動(dòng)生成展開 介紹正規(guī)式、狀態(tài)轉(zhuǎn)換圖和有限自動(dòng)機(jī)概念介紹正規(guī)式、狀態(tài)轉(zhuǎn)換圖和有限自動(dòng)機(jī)概念詞法分析器詞法分析器語法分析器語法分析器符號(hào)表符號(hào)表記號(hào)記號(hào)(token)取下一個(gè)記號(hào)取下一個(gè)記號(hào)源程序源程序2.1 詞法記號(hào)及屬性詞法記號(hào)及屬性 2.1.1 詞法記號(hào)、模式、詞法單元詞法記號(hào)、模式、詞法單元 記號(hào)名記號(hào)名詞法單元例舉詞法單元例舉模式的非形式描述模式的非形

2、式描述 if if 字符字符i, f for for字符字符f, o, r relation , = , = , 或或 0） 2.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 語言的運(yùn)算語言的運(yùn)算并：并：L M = s | s L 或或 s M 連接連接：LM = st | s L 且且 t M 冪：冪：L0是是 ，Li是是Li-1L 閉包：閉包：L = L0 L1 L2 正閉包：正閉包： L+ = L1 L2 例例L: A, B, , Z, a, b, , z , D: 0, 1, , 9 L D, LD, L6, L*, L(L D )*, D+ 2.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述

3、與識(shí)別 2.2.2 正規(guī)式正規(guī)式正規(guī)式正規(guī)式用來表示簡單的語言，用來表示簡單的語言，叫做叫做正規(guī)集正規(guī)集正規(guī)式正規(guī)式定義的語言定義的語言備注備注 a a a (r) | (s)L(r)L(s) r和和s是正規(guī)式是正規(guī)式(r)(s)L(r)L(s) r和和s是正規(guī)式是正規(guī)式(r)*(L(r)* r是正規(guī)式是正規(guī)式(r)L(r) r是正規(guī)式是正規(guī)式(a) (b)*)| (c)可以寫成可以寫成ab*| c 2.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 正規(guī)式的例子正規(guī)式的例子 = = a, b a | ba, b (a | b) (a | b )aa, ab, ba, bb aa | ab |

4、ba | bbaa, ab, ba, bb a*由字母由字母a構(gòu)成的所有串集構(gòu)成的所有串集 (a | b)*由由a和和b構(gòu)成的所有串集構(gòu)成的所有串集 復(fù)雜的例子復(fù)雜的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：010011010000100000101110012.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 2.2.3 正規(guī)定義正規(guī)定義 對(duì)正規(guī)式命名，使表示簡潔對(duì)正規(guī)式命名，使表示簡潔 d1 r1 d2 r2 . . . dn rn各個(gè)各個(gè)di的名字都不同的名字都不同每個(gè)每個(gè)ri都是都是 d1, d2, , di-1 上的正

5、規(guī)式上的正規(guī)式2.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 正規(guī)定義的例子正規(guī)定義的例子 C語言的標(biāo)識(shí)符是字母、數(shù)字和下劃線組成的串語言的標(biāo)識(shí)符是字母、數(shù)字和下劃線組成的串 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_( (letter_ | |digit) )* 2.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 正規(guī)定義的例子正規(guī)定義的例子 無符號(hào)數(shù)集合，例無符號(hào)數(shù)集合，例1946, ,11.28, ,63E8, ,1.99E 6digit 0 | 1 | | 9digits digit digit*

6、optional_fraction . .digits| | optional_exponent ( E ( + | | ) digits ) | numberdigits optional_fraction optional_exponent 簡化表示簡化表示number digit+ (.digit+)? (E(+| )? digit+)?2.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 正規(guī)定義的例子（進(jìn)行下一步討論的例子）正規(guī)定義的例子（進(jìn)行下一步討論的例子）while whiledo dorelop | = | = | | | =letter A | B | | Z | a | b

7、| | z id letter (letter | digit )*number digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+2.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 2.2.4 轉(zhuǎn)換圖轉(zhuǎn)換圖 關(guān)系算符的轉(zhuǎn)換圖關(guān)系算符的轉(zhuǎn)換圖051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)開始開始=*otherother2.2

8、 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 標(biāo)識(shí)符和關(guān)鍵字的轉(zhuǎn)換圖標(biāo)識(shí)符和關(guān)鍵字的轉(zhuǎn)換圖91011開始開始letterother*letter或或digitreturn(installId( )2.2 詞法記號(hào)的描述與識(shí)別詞法記號(hào)的描述與識(shí)別 無符號(hào)數(shù)的轉(zhuǎn)換圖無符號(hào)數(shù)的轉(zhuǎn)換圖 number digit+ (.digit+)? (E (+ | )? digit+)?開始開始1912131415161718digitdigitdigitdigitdigitdigitother.E+/ Edigitotherotherreturn( installNum( ) )*2.2 詞法記號(hào)的描述與識(shí)別詞法記

9、號(hào)的描述與識(shí)別 空白空白的轉(zhuǎn)換圖的轉(zhuǎn)換圖delim blank | tab | newline ws delim+2122開始開始delimother*delim202.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 2.3.1 不確定的有限自動(dòng)機(jī)（簡稱不確定的有限自動(dòng)機(jī)（簡稱NFA）一個(gè)數(shù)學(xué)模型，它包括：一個(gè)數(shù)學(xué)模型，它包括：1、有限的狀態(tài)集合、有限的狀態(tài)集合S2、輸入符號(hào)集合、輸入符號(hào)集合 3、轉(zhuǎn)換函數(shù)、轉(zhuǎn)換函數(shù)move : S ( ) P(S)4、狀態(tài)、狀態(tài)s0是唯一的開始狀態(tài)是唯一的開始狀態(tài)5、F S是接受狀態(tài)集合是接受狀態(tài)集合識(shí)別語言識(shí)別語言(a|b)*ab 的的NFA12開始開始a0abb輸輸

10、入入 符符 號(hào)號(hào)ab00, 10122狀狀 態(tài)態(tài) NFA的轉(zhuǎn)換表的轉(zhuǎn)換表2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 識(shí)別語言識(shí)別語言(a|b)*ab 的的NFA12開始開始a0abb2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 例例 識(shí)別識(shí)別aa* *| |bb* *的的NFA12開始開始a0abb34 2.3.2 確定的有限自動(dòng)機(jī)（簡稱確定的有限自動(dòng)機(jī)（簡稱DFA) ) 一個(gè)數(shù)學(xué)模型，包括：一個(gè)數(shù)學(xué)模型，包括：1、有限的狀態(tài)集合、有限的狀態(tài)集合S2、輸入字母集合、輸入字母集合 3、轉(zhuǎn)換函數(shù)、轉(zhuǎn)換函數(shù)move : S S，且可以是部分函數(shù)且可以是部分函數(shù)4、唯一的開始狀態(tài)、唯一的開始狀態(tài) s05、接受狀態(tài)接

11、受狀態(tài)集合集合F S12開始開始a0abbab識(shí)別語言識(shí)別語言(a|b)*ab 的的DFA2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 例例 DFA，識(shí)別，識(shí)別0,1上能被上能被5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)已讀過已讀過尚未讀尚未讀已讀部分的值已讀部分的值某時(shí)刻某時(shí)刻10101110005讀進(jìn)讀進(jìn)01010 1110005 2 = 10讀進(jìn)讀進(jìn)110101 1100010 2 + 1= 215個(gè)狀態(tài)即可，分別代表已讀部分的值除以個(gè)狀態(tài)即可，分別代表已讀部分的值除以5的余數(shù)的余數(shù) 例例 DFA，識(shí)別，識(shí)別0,1上能被上能被5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開

12、始410010101012.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 10102 = 10101112 = 710 例例 DFA, ,接受接受 0和和1的個(gè)數(shù)都是偶數(shù)的字符串的個(gè)數(shù)都是偶數(shù)的字符串0000 3 211奇奇0奇奇1奇奇0偶偶1 1011開始開始偶偶0偶偶1偶偶0奇奇12.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 2.3.3 NFA到到DFA的變換的變換 子集構(gòu)造法子集構(gòu)造法1、DFA的一個(gè)狀態(tài)是的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合的一個(gè)狀態(tài)集合2、讀了輸入、讀了輸入a1 a2 an后后， NFA能到達(dá)的所有狀態(tài)：能到達(dá)的所有狀態(tài)：s1, s2, , sk，則則 DFA到達(dá)狀態(tài)到達(dá)狀態(tài)s1, s2,

13、, sk 12a開始開始 0abb00, 1aba0, 2b2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 未畫完未畫完19開始開始 0ab ab6782345 例例 (a|b)*ab，NFA如下，把它變換為如下，把它變換為DFA2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)ab狀態(tài)狀態(tài) 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abA狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abAB狀態(tài)狀態(tài) A =

14、0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abABB狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abABCB狀態(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 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345

15、輸入符號(hào)輸入符號(hào)abABCBC狀態(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 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abABCBBC狀態(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 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abABCBBDC狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3,

16、4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abABCBBDCD狀態(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 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abABCBBDCBCD狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3

17、, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abABCBBDCBCDBC狀態(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 2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 輸入符號(hào)輸入符號(hào)abABCBBDCBCDBC狀態(tài)狀態(tài) BD開始開始aAabbabCba2.3 有

18、有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 BD開始開始aAabbabCba12開始開始a0abbab識(shí)別語言識(shí)別語言(a|b)*ab 的的自動(dòng)機(jī)自動(dòng)機(jī)2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 19開始開始 0ab ab6782345 BD開始開始aAabbabCba12開始開始a0abbab識(shí)別語言識(shí)別語言(a|b)*ab 的的自動(dòng)機(jī)自動(dòng)機(jī)子集構(gòu)造法不一子集構(gòu)造法不一定得到最簡定得到最簡DFA2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) BD開始開始aAabbaa, bCbaEb2.3.4 DFA的化簡的化簡 死狀態(tài)死狀態(tài) 在轉(zhuǎn)換函數(shù)由部分函數(shù)改成全函數(shù)表示時(shí)引入在轉(zhuǎn)換函數(shù)由部

19、分函數(shù)改成全函數(shù)表示時(shí)引入 左圖需要引入死狀態(tài)左圖需要引入死狀態(tài)E ；右圖無須引入死狀態(tài)；右圖無須引入死狀態(tài)BD開始開始aAabbabCba2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 可區(qū)別的狀態(tài)可區(qū)別的狀態(tài) A和和B是可區(qū)別的狀態(tài)是可區(qū)別的狀態(tài) 從從A出發(fā)，讀過單字符出發(fā)，讀過單字符b構(gòu)成的串，到達(dá)非接受構(gòu)成的串，到達(dá)非接受狀態(tài)狀態(tài)C，而從，而從B出發(fā)，讀過串出發(fā)，讀過串b，到達(dá)接受狀態(tài)，到達(dá)接受狀態(tài)D A和和C是不可區(qū)別的狀態(tài)是不可區(qū)別的狀態(tài) 無任何串可用來像上面這樣無任何串可用來像上面這樣區(qū)別它們區(qū)別它們BD開始開始aAabbabCba2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 方法方法1. A,

20、B, C, Dmove(A, B, C, a) = Bmove(A, B, C, b) = C, D2. A, C, B, Dmove(A, C, a) = Bmove(A, C, b) = CBD開始開始aAabbabCba12開始開始a0abbab2.3 有有 限限 自自 動(dòng)動(dòng) 機(jī)機(jī) 從正規(guī)式建立識(shí)別器的步驟從正規(guī)式建立識(shí)別器的步驟從正規(guī)式構(gòu)造從正規(guī)式構(gòu)造NFA（本節(jié)介紹）本節(jié)介紹）用語法制導(dǎo)的算法，它用正規(guī)式語法結(jié)構(gòu)來指導(dǎo)用語法制導(dǎo)的算法，它用正規(guī)式語法結(jié)構(gòu)來指導(dǎo)構(gòu)造過程構(gòu)造過程把把NFA變成變成DFA （子集構(gòu)造法，已介紹）子集構(gòu)造法，已介紹） 將將DFA化簡化簡 （合并不可區(qū)別狀態(tài)，

21、也已介紹）（合并不可區(qū)別狀態(tài)，也已介紹）2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 首先構(gòu)造識(shí)別首先構(gòu)造識(shí)別 和字母表中一個(gè)符號(hào)的和字母表中一個(gè)符號(hào)的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒有向外的轉(zhuǎn)換重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒有向外的轉(zhuǎn)換i開始開始 識(shí)別正規(guī)式識(shí)別正規(guī)式 的的NFAafif開始開始識(shí)別正規(guī)式識(shí)別正規(guī)式a的的NFA2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 構(gòu)造識(shí)別主算符為選擇的正規(guī)式的構(gòu)造識(shí)別主算符為選擇的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒有向外的轉(zhuǎn)換重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒有向外的轉(zhuǎn)換 fi開始開始識(shí)別正規(guī)式識(shí)別正規(guī)式s | t 的的NFAN (

22、s)N (t) 2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 構(gòu)造識(shí)別主算符為連接的正規(guī)式的構(gòu)造識(shí)別主算符為連接的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒有向外的轉(zhuǎn)換重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒有向外的轉(zhuǎn)換識(shí)別正規(guī)式識(shí)別正規(guī)式 st 的的NFAiN (s)f開始開始N (t)2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 構(gòu)造識(shí)別主算符為閉包的正規(guī)式的構(gòu)造識(shí)別主算符為閉包的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒有向外的轉(zhuǎn)換重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒有向外的轉(zhuǎn)換N (s)f開始開始識(shí)別正規(guī)式識(shí)別正規(guī)式 s* 的的NFAi 2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 對(duì)

23、于加括號(hào)的正規(guī)式對(duì)于加括號(hào)的正規(guī)式(s)，使用使用N(s)本身作為本身作為它的它的NFA2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 本方法產(chǎn)生的本方法產(chǎn)生的NFA有有下列性質(zhì)下列性質(zhì) N(r)的狀態(tài)數(shù)最多是的狀態(tài)數(shù)最多是r中符號(hào)和算符總數(shù)的兩倍中符號(hào)和算符總數(shù)的兩倍 N(r)只有一個(gè)接受狀態(tài)，接受狀態(tài)沒有向外的轉(zhuǎn)只有一個(gè)接受狀態(tài)，接受狀態(tài)沒有向外的轉(zhuǎn)換換2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī)19開始開始 0ab ab6782345 本方法產(chǎn)生的本方法產(chǎn)生的NFA有有下列性質(zhì)下列性質(zhì) N(r)的每個(gè)狀態(tài)有一個(gè)用的每個(gè)狀態(tài)有一個(gè)用 的符號(hào)標(biāo)記的指向其它的符號(hào)標(biāo)記的指向其它結(jié)點(diǎn)的轉(zhuǎn)換

24、，或者最多兩個(gè)指向其它結(jié)點(diǎn)的結(jié)點(diǎn)的轉(zhuǎn)換，或者最多兩個(gè)指向其它結(jié)點(diǎn)的 轉(zhuǎn)轉(zhuǎn)換換2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī)19開始開始 0ab ab6782345 2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 19開始開始 0 ab678ab2345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 19開始開始 0ab ab6782345

25、 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī)19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.

26、4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解 (a|b)*ab的兩個(gè)的兩個(gè)NFA的比較的比較 12開始開始a 0abb手工構(gòu)造手工構(gòu)造:算法構(gòu)造算法構(gòu)造:2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī)19開始開始 0ab ab6782345 小結(jié)：從正規(guī)式建立識(shí)別器的步驟小結(jié)：從正規(guī)式建立識(shí)別器的步驟從正規(guī)式構(gòu)造從正規(guī)式構(gòu)造NFA把把NFA變成變成DFA 將將DFA化簡化簡 存在其它辦法存在其它辦法2.4 從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式到有限自動(dòng)機(jī) 用用Lex建立詞法分析

27、器的步驟建立詞法分析器的步驟Lex編譯器編譯器Lex源程序源程序lex.llex.yy.cC編譯器編譯器lex.yy.ca.outa.out輸入流輸入流記號(hào)序列記號(hào)序列2.5 詞法分析器的生成器詞法分析器的生成器 Lex程序包括三個(gè)部分程序包括三個(gè)部分 聲明聲明 翻譯規(guī)則翻譯規(guī)則 輔助過程輔助過程 Lex程序的翻譯規(guī)則程序的翻譯規(guī)則 p1動(dòng)作動(dòng)作1 p2動(dòng)作動(dòng)作2 pn動(dòng)作動(dòng)作n2.5 詞法分析器的生成器詞法分析器的生成器 例例聲明部分聲明部分%/* * 常量常量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定義的定義* */%/*

28、* 正規(guī)定義正規(guī)定義 * */delim t n wsdelim+letterA Za zdigit0 9idletter(letter|digit)* *numberdigit+( .digit+)?(E+ ?digit+)?2.5 詞法分析器的生成器詞法分析器的生成器 例例翻譯規(guī)則部分翻譯規(guī)則部分ws/* * 沒有動(dòng)作，也不返回沒有動(dòng)作，也不返回 * */whilereturn (WHILE);doreturn (DO);idyylval = install_id ( ); return (ID);numberyylval = install_num( );return (NUMBER);

29、“ ”yylval = LT; return (RELOP); “ = ” yylval = LE; return (RELOP);“ = ”yylval = EQ; return (RELOP);“ ”yylval = NE; return (RELOP);“ ”yylval = GT; return (RELOP);“ = ”yylval = GE; return (RELOP);2.5 詞法分析器的生成器詞法分析器的生成器 例例輔助過程部分輔助過程部分installId ( ) /* * 把詞法單元裝入符號(hào)表并返回指針。把詞法單元裝入符號(hào)表并返回指針。yytext指向該詞法單元的第一個(gè)字符，指向該詞法單元的第一個(gè)字符，yyleng給出的它的長度給出的它的長度* */installNum ( ) /* * 類似上面的過程，但詞法單元不是標(biāo)識(shí)符而類似上面的過程，但詞法單元不是標(biāo)識(shí)符而是數(shù)是數(shù) * */2.5 詞法分析器的生成器詞法分析器的生成器 詞法分析器的作用和接口，用高級(jí)語言編寫詞法分析器的作用和接口，用高級(jí)語言編寫詞法分析器等內(nèi)容詞法分析器等內(nèi)容 掌握下面涉及的一些概念，它們之間轉(zhuǎn)換的掌握下面涉及的一些概念，它們之間轉(zhuǎn)換的技巧、方法或算法技巧、方法或算法 非形式描述的語言非形式描述的語言 正規(guī)式正規(guī)式 正規(guī)式正規(guī)式 NF