編譯原理—chapter2

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

2、非形式描述 if if 字符字符i, f for for字符字符f, o, r relation , = , = , 或或 = 或或 = 或或 id sum, count, D5由字母開頭的字母數(shù)字串由字母開頭的字母數(shù)字串 number 3.1, 10, 2.8 E12任何數(shù)值常數(shù)任何數(shù)值常數(shù) literal“seg. error” 引號引號“和和”之間的任意字符之間的任意字符串，但引號本身除外串，但引號本身除外2.1 詞法記號及屬性詞法記號及屬性 歷史上詞法定義中的一些問題歷史上詞法定義中的一些問題忽略空格帶來的困難忽略空格帶來的困難DO 8 I 3. 75 DO8I 3. 75 DO 8

3、I 3, 75 關(guān)鍵字不保留關(guān)鍵字不保留IF THEN THEN THEN=ELSE；ELSE 關(guān)鍵字、保留關(guān)鍵字、保留字和字和標(biāo)準(zhǔn)標(biāo)識符的區(qū)別標(biāo)準(zhǔn)標(biāo)識符的區(qū)別保留保留字字是語言預(yù)先確定了含義的詞法單元是語言預(yù)先確定了含義的詞法單元, 如如if 標(biāo)準(zhǔn)標(biāo)識符也是預(yù)先確定了含義的標(biāo)識符，但程標(biāo)準(zhǔn)標(biāo)識符也是預(yù)先確定了含義的標(biāo)識符，但程序可以重新聲明它的含義序可以重新聲明它的含義2.1 詞法記號及屬性詞法記號及屬性2.1.2 詞法記號的屬性詞法記號的屬性 position = initial + rate 60的的序列：序列： id，指向符號表中指向符號表中position條目的指針條目的指針 ass

4、ign _ op id，指向符號表中指向符號表中initial條目的指針條目的指針 add_op id，指向符號表中指向符號表中rate條目的指針條目的指針 mul_ op number，整數(shù)值整數(shù)值60 2.1 詞法記號及屬性詞法記號及屬性2.1.3 詞法錯誤詞法錯誤詞法分析器對源程序采取非常局部的觀點詞法分析器對源程序采取非常局部的觀點難以發(fā)現(xiàn)下面的錯誤難以發(fā)現(xiàn)下面的錯誤fi (a = f (x) ) 在實數(shù)是在實數(shù)是a.b格式下，可以發(fā)現(xiàn)下面的錯誤格式下，可以發(fā)現(xiàn)下面的錯誤123.2.2 詞法記號的描述與識別詞法記號的描述與識別 2.2.1 串和語言串和語言 字母表：符號的有限集合，字母

5、表：符號的有限集合， 例：例： = 0, 1 串：符號的有窮序列，例：串：符號的有窮序列，例：0110, 語言：字母表上的一個串集語言：字母表上的一個串集 , 0, 00, 000, , , 句子和字句子和字：屬于語言的串：屬于語言的串 串的運算串的運算 連接連接xy，s = s = s 積積（指數(shù)）（指數(shù)） s0為為 ，si為為si -1s（i 0） 2.2 詞法記號的描述與識別詞法記號的描述與識別 語言的運算語言的運算和：和：L M = s | s L 或或 s M 連接連接：LM = st | s L 且且 t M 指數(shù)：指數(shù)：L0是是 ，Li是是Li -1L 閉包：閉包：L = L0

6、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 詞法記號的描述與識別詞法記號的描述與識別 2.2.2 正規(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 正規(guī)式正規(guī)式用來表示簡單的語言

7、，用來表示簡單的語言，叫做叫做正規(guī)集正規(guī)集2.2 詞法記號的描述與識別詞法記號的描述與識別 正規(guī)式的例子正規(guī)式的例子 = = a, b a | ba, b (a | b) (a | b )aa, ab, ba, bb aa | ab | 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) ) ) 句子：句子：010011010000100000101110011？2.2 詞法記號的描述與識別

8、詞法記號的描述與識別 2.2.3 正規(guī)定義正規(guī)定義 對正規(guī)式命名，使表示簡潔對正規(guī)式命名，使表示簡潔 d1 r1 d2 r2 . . . dn rn各個各個di的名字都不同的名字都不同每個每個ri都是都是 d1, d2, , di-1 上的正規(guī)式上的正規(guī)式2.2 詞法記號的描述與識別詞法記號的描述與識別 正規(guī)定義的例子正規(guī)定義的例子 C語言的標(biāo)識符是字母、數(shù)字和下劃線組成的串語言的標(biāo)識符是字母、數(shù)字和下劃線組成的串 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9id letter_( (letter_ | |digit) )* 2

9、.2 詞法記號的描述與識別詞法記號的描述與識別 正規(guī)定義的例子正規(guī)定義的例子 無符號數(shù)集合，例無符號數(shù)集合，例1946, ,11.28, ,63E8, ,1.99E 6 digit 0 | 1 | | 9digits digit digit*optional_fraction . .digits| | optional_exponent ( E ( + | | ) digits ) | number digits optional_fraction optional_exponent 簡化表示簡化表示number digit+ (.digit+)? (E(+| )? digit+)? 這里這里

10、r?=r| r?=r| 2.2 詞法記號的描述與識別詞法記號的描述與識別 正規(guī)定義的例子（進(jìn)行下一步討論的例子）正規(guī)定義的例子（進(jìn)行下一步討論的例子）while whiledo dorelop | = | = | | | =letter A | B | | Z | a | b | | z id letter (letter | digit )*number digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+識別記號 詞法分析器詞法分析器語法分析器語法分析器符號表符號表記號記號(token)取下一

11、個記號取下一個記號源程序源程序描繪了語法分析器為了得到下一個記號而調(diào)用詞法分析器時，詞法分析器所做的動作。狀態(tài)轉(zhuǎn)化圖2.2 詞法記號的描述與識別詞法記號的描述與識別 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 詞法記號的描述與識別詞法記號的描述與識別 標(biāo)識符和保留字的轉(zhuǎn)換圖標(biāo)識符和保留字的轉(zhuǎn)換圖91011開始開始lett

12、erother*letter或或digitreturn(installId( )2.2 詞法記號的描述與識別詞法記號的描述與識別 無符號數(shù)的轉(zhuǎn)換圖無符號數(shù)的轉(zhuǎn)換圖開始開始1912131415161718digitdigitdigitdigitdigitdigitother.E+/ Edigitotherotherreturn( installNum( ) )*number digit+ (. .digit+)? (E (+ | )? digit+)? 2.2 詞法記號的描述與識別詞法記號的描述與識別 空白空白的轉(zhuǎn)換圖的轉(zhuǎn)換圖delim blank | tab | newline ws deli

13、m+2122開始開始delimother*delim20詞法分析器代碼示例有限自動機(jī)(語言)識別器字符串xY/N?有限自動機(jī)不確定有限自動機(jī)確定有限自動機(jī)（Nondeterministic Finite Automata）（Deterministic Finite Automata）2.3 有有 限限 自自 動動 機(jī)機(jī) 2.3.1 不確定的有限自動機(jī)（簡稱不確定的有限自動機(jī)（簡稱NFA）一個數(shù)學(xué)模型，它包括：一個數(shù)學(xué)模型，它包括：1、狀態(tài)集合、狀態(tài)集合S2、輸入符號集合、輸入符號集合 3、轉(zhuǎn)換函數(shù)、轉(zhuǎn)換函數(shù)move : S ( ) P(S), P(S)是是S的冪集的冪集4、狀態(tài)、狀態(tài)s0是唯一

14、開始狀態(tài)是唯一開始狀態(tài)5、F S是接受（終止）狀態(tài)集合是接受（終止）狀態(tài)集合識別語言識別語言(a|b)*ab 的的NFA12開始開始a0abb12開始開始a0abb識別語言識別語言(a|b)*ab 的的NFA輸輸 入入 符符 號號ab00, 10122狀狀 態(tài)態(tài) NFA的轉(zhuǎn)換表的轉(zhuǎn)換表2.3 有有 限限 自自 動動 機(jī)機(jī) 2.3 有有 限限 自自 動動 機(jī)機(jī) 例例 識別識別aa* *| |bb* *的的NFA12開始開始a0abb34 2.3.2 確定的有限自動機(jī)（簡稱確定的有限自動機(jī)（簡稱DFA) ) 一個數(shù)學(xué)模型，包括：一個數(shù)學(xué)模型，包括：1、狀態(tài)集合、狀態(tài)集合S2、輸入字母表、輸入字母表

15、 3、轉(zhuǎn)換函數(shù)、轉(zhuǎn)換函數(shù)move : S S4、唯一的初態(tài)、唯一的初態(tài) s S5、終態(tài)集合、終態(tài)集合F S12開始開始a0abbab識別語言識別語言(a|b)*ab 的的DFA2.3 有有 限限 自自 動動 機(jī)機(jī) 1、沒有 轉(zhuǎn)換,必須有符號；2、任何狀態(tài)s和字符a， 最多只有一條標(biāo)記離開畫出畫出DFA, ,接受接受 0和和1的個數(shù)都是偶數(shù)的字符串的個數(shù)都是偶數(shù)的字符串312011110000開始開始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇12.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始42.3 有有 限限 自

16、自 動動 機(jī)機(jī) 10101110001010 11100010101 110001010111000被能被能5整除整除？ 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始402.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始4102.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始41002.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開

17、始開始410012.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始4100102.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始41001012.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始410010102.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始4100101012.3 有有 限限

18、自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始41001010102.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始410010101012.3 有有 限限 自自 動動 機(jī)機(jī) 例：識別例：識別 =0,1上能被能上能被能5整除的二進(jìn)制數(shù)整除的二進(jìn)制數(shù)0123開始開始410010101012.3 有有 限限 自自 動動 機(jī)機(jī) 10102 = 1010 余余01112 = 710 余余21010111000余？余？2.3 有有 限限 自自 動動 機(jī)機(jī)輸輸 入入 符符

19、 號號ab00, 101222.3.3 NFA到到DFA的變換的變換2.3.3 NFA到到DFA的變換的變換 子集構(gòu)造法子集構(gòu)造法1、DFA的一個狀態(tài)是的一個狀態(tài)是NFA的一個狀態(tài)集合的一個狀態(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, , sk2.3 有有 限限 自自 動動 機(jī)機(jī) (a|b)*ab 的的NFA12a開始開始0abb2.3.3 NFA到到DFA的變換的變換 子集構(gòu)造法子集構(gòu)造法1、DFA的一個狀態(tài)是的一個狀態(tài)是NFA的一個狀態(tài)集合的一個狀態(tài)集合2、讀了輸入、讀了

20、輸入a1 a2 an后后， NFA能到達(dá)的所有狀態(tài)：能到達(dá)的所有狀態(tài)：s1, s2, , sk，則則 DFA到達(dá)狀態(tài)到達(dá)狀態(tài)s1, s2, , sk12a開始開始0abb00, 1a2.3 有有 限限 自自 動動 機(jī)機(jī) 2.3.3 NFA到到DFA的變換的變換 子集構(gòu)造法子集構(gòu)造法1、DFA的一個狀態(tài)是的一個狀態(tài)是NFA的一個狀態(tài)集合的一個狀態(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, , sk12a開始開始0abb00, 1ab2.3 有有 限限 自自 動動 機(jī)機(jī) 2.3.3

21、 NFA到到DFA的變換的變換 子集構(gòu)造法子集構(gòu)造法1、DFA的一個狀態(tài)是的一個狀態(tài)是NFA的一個狀態(tài)集合的一個狀態(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, , sk12a開始開始0abb00, 1aba2.3 有有 限限 自自 動動 機(jī)機(jī) 2.3.3 NFA到到DFA的變換的變換 子集構(gòu)造法子集構(gòu)造法1、DFA的一個狀態(tài)是的一個狀態(tài)是NFA的一個狀態(tài)集合的一個狀態(tài)集合2、讀了輸入、讀了輸入a1 a2 an后后， NFA能到達(dá)的所有狀態(tài)：能到達(dá)的所有狀態(tài)：s1, s2, ,

22、sk，則則 DFA到達(dá)狀態(tài)到達(dá)狀態(tài)s1, s2, , sk12a開始開始0abb00, 1aba0, 2b2.3 有有 限限 自自 動動 機(jī)機(jī) NFA狀態(tài)上的運算 -closure(s): 從從NFA開始狀態(tài)開始狀態(tài)s出發(fā)，經(jīng)出發(fā)，經(jīng) 轉(zhuǎn)化能達(dá)到的轉(zhuǎn)化能達(dá)到的NFA狀態(tài)集合狀態(tài)集合 -closure(T)： 從從NFA狀態(tài)集合狀態(tài)集合T中某個狀態(tài)中某個狀態(tài)s出發(fā)，經(jīng)出發(fā)，經(jīng) 轉(zhuǎn)化能達(dá)到的轉(zhuǎn)化能達(dá)到的NFA 狀態(tài)集合狀態(tài)集合 move(T,a)： 從從NFA狀態(tài)集合狀態(tài)集合T中某個狀態(tài)中某個狀態(tài)s出發(fā)，經(jīng)標(biāo)記出發(fā)，經(jīng)標(biāo)記a的的轉(zhuǎn)化能達(dá)到轉(zhuǎn)化能達(dá)到 的的NFA狀態(tài)集合狀態(tài)集合2.3 有有 限限 自

23、自 動動 機(jī)機(jī)19開始開始 0ab ab6782345 輸入符號輸入符號ab狀態(tài)狀態(tài) 1. N 屬于屬于 T= -closure(s0)狀態(tài)狀態(tài)2. N 移動到移動到 move(T,a)中任一個狀態(tài)中任一個狀態(tài)3. N 可到達(dá)可到達(dá) T= -closure(move(T,a) 中任一個狀態(tài)中任一個狀態(tài)2.3 有有 限限 自自 動動 機(jī)機(jī)19開始開始 0ab ab6782345 輸入符號輸入符號abA狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 2.3 有有 限限 自自 動動 機(jī)機(jī)19開始開始 0ab ab6782345 輸入符號輸入符號abAB狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B

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

25、 A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 動動 機(jī)機(jī)19開始開始 0ab ab6782345 輸入符號輸入符號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 有有 限限 自自 動動 機(jī)機(jī)19開始開始 0ab ab6782345 輸入符號輸入符號abABCBBDC狀態(tài)狀態(tài) A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2,

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

27、4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 動動 機(jī)機(jī)19開始開始 0ab ab6782345 輸入符號輸入符號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 有有 限限 自自 動動 機(jī)機(jī)BD開始開始aAabbabCba19開開始始 0ab ab6782345 輸入符號輸入符號abABCBBDCBCDBC狀態(tài)狀態(tài) 2.3 有有 限限 自自 動動 機(jī)機(jī)BD開始開始aAabba

28、bCba12開始開始a0abbab19開始開始 0ab ab6782345 識別語言識別語言(a|b)*ab 的的自動機(jī)自動機(jī)2.3 有有 限限 自自 動動 機(jī)機(jī)BD開始開始aAabbabCba12開始開始a0abbab19開始開始 0ab ab6782345 識別語言識別語言(a|b)*ab 的的自動機(jī)自動機(jī)子集構(gòu)造法不一子集構(gòu)造法不一定得到最簡定得到最簡DFA2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 從正規(guī)式建立識別器從正規(guī)式建立識別器從正規(guī)式構(gòu)造從正規(guī)式構(gòu)造NFA用語法制導(dǎo)的算法，它用正規(guī)式語法結(jié)構(gòu)來指用語法制導(dǎo)的算法，它用正規(guī)式語法結(jié)構(gòu)來指導(dǎo)構(gòu)造過程導(dǎo)構(gòu)造過程把把NFA變成變成

29、DFA （子集構(gòu)造法）子集構(gòu)造法） 將將DFA化簡化簡 （合并不可區(qū)別狀態(tài)）（合并不可區(qū)別狀態(tài)）2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 首先構(gòu)造識別首先構(gòu)造識別 和字母表中一個符號的和字母表中一個符號的NFAi開始開始 識別正規(guī)式識別正規(guī)式 的的NFAafif開始開始識別正規(guī)式識別正規(guī)式a的的NFA2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 構(gòu)造識別主算符為選擇的正規(guī)式的構(gòu)造識別主算符為選擇的正規(guī)式的NFA fi開始開始識別正規(guī)式識別正規(guī)式s | t的的NFAN (s)N (t) 2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 構(gòu)造識別主算符為連接的正規(guī)式的構(gòu)造識別主算符為連

30、接的正規(guī)式的NFA iN (s)f開始開始識別正規(guī)式識別正規(guī)式st 的的NFAN (t)2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 構(gòu)造識別主算符為閉包的正規(guī)式的構(gòu)造識別主算符為閉包的正規(guī)式的NFA N (s)f開始開始識別正規(guī)式識別正規(guī)式s* 的的NFAi 2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 對于加括號的正規(guī)式對于加括號的正規(guī)式(s)，使用使用N(s)本身作為本身作為它的它的NFA。2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 本方法產(chǎn)生的本方法產(chǎn)生的NFA有有下列性質(zhì)下列性質(zhì): : N(r)的狀態(tài)數(shù)最多是的狀態(tài)數(shù)最多是r中符號和算符總數(shù)的兩倍中符號和算符總數(shù)的兩倍

31、N(r)只有一個開始狀態(tài)和一個接受狀態(tài)，接受狀只有一個開始狀態(tài)和一個接受狀態(tài)，接受狀態(tài)沒有向外的轉(zhuǎn)換態(tài)沒有向外的轉(zhuǎn)換 N(r)的每個狀態(tài)有一個用的每個狀態(tài)有一個用 的符號標(biāo)記的指向其的符號標(biāo)記的指向其它結(jié)點的轉(zhuǎn)換，或者最多兩個指向其它結(jié)點的它結(jié)點的轉(zhuǎn)換，或者最多兩個指向其它結(jié)點的 轉(zhuǎn)換轉(zhuǎn)換2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 19開始開始 0 ab678ab2345 r9r7r8r4r3r5r6*)(r2r1a|

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

33、9開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 19開始開始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解的分解2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) (a|b)*ab的兩個的兩個NFA的比較的比較12開始開始a0abb19開始開始 0ab ab6782345 手工構(gòu)造手工構(gòu)造:算法構(gòu)造算法構(gòu)造:2.4 從正規(guī)式到有限自動機(jī)從正規(guī)式到有限自動機(jī) 小結(jié)：從正規(guī)式建立識別器的步驟小結(jié)：從正規(guī)式建立識別器的步驟從

34、正規(guī)式構(gòu)造從正規(guī)式構(gòu)造NFA把把NFA變成變成DFA 將將DFA化簡化簡 存在其它辦法存在其它辦法2.5 詞法分析器的生成器詞法分析器的生成器 Lex(lexical analyzer generator) 用用Lex建立詞法分析器的步驟建立詞法分析器的步驟Lex編譯器編譯器Lex源程序源程序lex.llex.yy.cC編譯器編譯器lex.yy.ca.outa.out輸入流輸入流記號序列記號序列2.5 詞法分析器的生成器詞法分析器的生成器 Lex程序包括三個部分程序包括三個部分 聲明聲明 翻譯規(guī)則翻譯規(guī)則 輔助過程輔助過程 Lex程序的翻譯規(guī)則程序的翻譯規(guī)則 p1動作動作1 p2動作動作2 p

35、n動作動作n2.5 詞法分析器的生成器詞法分析器的生成器 例例-聲明部分聲明部分%/* * 常量常量LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP的定義的定義* */%/* * 正規(guī)定義正規(guī)定義 * */delim t n wsdelim+letterA Za zdigit0 9idletter(letter|digit)* *numberdigit+( .digit+)?(E+ ?digit+)?2.5 詞法分析器的生成器詞法分析器的生成器 例例-翻譯規(guī)則部分翻譯規(guī)則部分ws/* * 沒有動作，也不返回沒有動作，也不返回 * */wh

36、ilereturn (WHILE);doreturn (DO);idyylval = install_id ( ); return (ID);numberyylval = install_num( ); return (NUMBER);“ ”yylval = LT; return (RELOP); “ = ” yylval = LE; return (RELOP);“ = ”yylval = EQ; return (RELOP);“ ”yylval = NE; return (RELOP);“ ”yylval = GT; return (RELOP);“ = ”yylval = GE; ret

37、urn (RELOP);2.5 詞法分析器的生成器詞法分析器的生成器 例例-輔助過程部分輔助過程部分install_ id ( ) /* * 把詞法單元裝入符號表并返回指針。把詞法單元裝入符號表并返回指針。yytext指向該詞法單元的第一個字符，指向該詞法單元的第一個字符，yyleng給出的它的長度給出的它的長度* */install_num ( ) /* * 類似上面的過程，但詞法單元不是標(biāo)識符而是類似上面的過程，但詞法單元不是標(biāo)識符而是數(shù)數(shù) * */本本 章章 要要 點點 詞法分析器的作用和接口，用高級語言編寫詞詞法分析器的作用和接口，用高級語言編寫詞法分析器等內(nèi)容，它們與詞法分析器的實現(xiàn)有法分析器等內(nèi)容，它們與詞法分析器的實現(xiàn)有關(guān)關(guān) 掌握下面涉及的一些概念，它們之間轉(zhuǎn)換的技掌握下面涉及的一些概念，它們之間轉(zhuǎn)換的技巧、方法或算法巧、方法或算法 非形式描述的語言非形式描述的語言 正規(guī)式正規(guī)式 正規(guī)式正規(guī)式 NFA 非形式描述的語言非形式描述的語言 NFA NFA DFA DFA 最簡最簡DFA 非形式描述的語言非形式描述的語言 DFA（或最簡或最簡DFA）例例 題題 1 敘述下面的正規(guī)式描述的語言，并畫出接受敘述下面的正規(guī)式描述的語言，并畫出接受該語言的最簡該語言的最簡DFA的狀態(tài)