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

2、形式描述模式的非形式描述 if if 字符字符i, f for for字符字符f, o, r relation , = , = , 或或 0） 2.2 詞法記號的描述與識別詞法記號的描述與識別 語言的運算語言的運算 并：并：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 詞法記號的

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

4、, ba, bb aa | ab | ba | bbaa, ab, ba, bb a*由字母由字母a構成的所有串集構成的所有串集 (a | b)*由由a和和b構成的所有串集構成的所有串集 復雜的例子復雜的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：01001101000010000010111001 2.2 詞法記號的描述與識別詞法記號的描述與識別 2.2.3 正規定義正規定義 對正規式命名，使表示簡潔對正規式命名，使表示簡潔 d1 r1 d2 r2 . . . dn rn 各個各個di的名字都不同的名字都不同 每個每個ri

5、都是都是 d1, d2, , di-1 上的正規式上的正規式 2.2 詞法記號的描述與識別詞法記號的描述與識別 正規定義的例子正規定義的例子 c語言的標識符是字母、數字和下劃線組成的串語言的標識符是字母、數字和下劃線組成的串 letter_ a | b | | z | a | b | | z | _ digit 0 | 1 | | 9 id letter_( (letter_ | |digit) )* 2.2 詞法記號的描述與識別詞法記號的描述與識別 正規定義的例子正規定義的例子 無符號數集合，例無符號數集合，例1946, ,11.28, ,63e8, ,1.99e 6 digit 0 | 1

6、 | | 9 digits digit digit* optional_fraction . .digits| | optional_exponent ( e ( + | | ) digits ) | numberdigits optional_fraction optional_exponent 簡化表示簡化表示 number digit+ (.digit+)? (e(+| )? digit+)? 2.2 詞法記號的描述與識別詞法記號的描述與識別 正規定義的例子（進行下一步討論的例子）正規定義的例子（進行下一步討論的例子） while while do do relop | = | = |

7、| | = letter a | b | | z | a | b | | z id letter (letter | digit )* number digit+ (.digit+)? (e (+ | )? digit+)? delim blank | tab | newline ws delim+ 2.2 詞法記號的描述與識別詞法記號的描述與識別 2.2.4 轉換圖轉換圖 關系算符的轉換圖關系算符的轉換圖 0 5 1 6 2 4 8 3 7 return(relop, le) return(relop, ne) return(relop, lt) return(relop, ge) retu

8、rn(relop, gt) return(relop, eq) 開始開始 = = * * other other 2.2 詞法記號的描述與識別詞法記號的描述與識別 標識符和保留字的轉換圖標識符和保留字的轉換圖 91011 開始開始 letterother * letter或或digit return(installid( ) 2.2 詞法記號的描述與識別詞法記號的描述與識別 無符號數的轉換圖無符號數的轉換圖 number digit+ (.digit+)? (e (+ | )? digit+)? 開始開始 19 12 131415161718 digit digit digit digit d

9、igit digit other .e+/ e digit other other return( installnum( ) ) * 2.2 詞法記號的描述與識別詞法記號的描述與識別 空白空白的轉換圖的轉換圖 delim blank | tab | newline ws delim+ 2122 開始開始delimother * delim 20 2.3 有有 限限 自自 動動 機機 2.3.1 不確定的有限自動機（簡稱不確定的有限自動機（簡稱nfa） 一個數學模型，它包括：一個數學模型，它包括： 1、狀態集合、狀態集合s 2、輸入符號集合、輸入符號集合 3、轉換函數、轉換函數move : s

10、 ( ) p(s) 4、狀態、狀態s0是唯一的開始狀態是唯一的開始狀態 5、f s是接受狀態集合是接受狀態集合 識別語言識別語言 (a|b)*ab 的的nfa 12 開始開始a 0 a b b 輸輸 入入 符符 號號 ab 00, 10 12 2 狀狀 態態 nfa的轉換表的轉換表 2.3 有有 限限 自自 動動 機機 識別語言識別語言 (a|b)*ab 的的nfa 12 開始開始a 0 a b b 2.3 有有 限限 自自 動動 機機 例例 識別識別aa* *| |bb* *的的nfa 12 開始開始 a 0 a b b 34 2.3.2 確定的有限自動機（簡稱確定的有限自動機（簡稱dfa)

11、 ) 一個數學模型，包括：一個數學模型，包括： 1、狀態集合、狀態集合s 2、輸入字母集合、輸入字母集合 3、轉換函數、轉換函數move : s s，且可以是部分函數且可以是部分函數 4、唯一的開始狀態、唯一的開始狀態 s0 5、接受狀態接受狀態集合集合f s 12 開始開始 a 0 a b b a b 識別語言識別語言 (a|b)*ab 的的dfa 2.3 有有 限限 自自 動動 機機 2.3 有有 限限 自自 動動 機機 例例 dfa，識別，識別0,1上能被上能被5整除的二進制數整除的二進制數 已讀過已讀過尚未讀尚未讀已讀部分的值已讀部分的值 某時刻某時刻10101110005 讀進讀進0

12、1010 1110005 2 = 10 讀進讀進110101 1100010 2 + 1= 21 5個狀態即可，分別代表已讀部分的值除以個狀態即可，分別代表已讀部分的值除以5的余數的余數 例例 dfa，識別，識別0,1上能被上能被5整除的二進制數整除的二進制數 0123 開始開始 4 1 0 0 1 0 1 0 10 1 2.3 有有 限限 自自 動動 機機 10102 = 1010 1112 = 710 例例 dfa, ,接受接受 0和和1的個數都是偶數的字符串的個數都是偶數的字符串 0000 3 2 1 1 奇奇0奇奇1 奇奇0偶偶1 1 0 1 1 開始開始 偶偶0偶偶1 偶偶0奇奇1

13、2.3 有有 限限 自自 動動 機機 2.3.3 nfa到到dfa的變換的變換 子集構造法子集構造法 1、dfa的一個狀態是的一個狀態是nfa的一個狀態集合的一個狀態集合 2、讀了輸入、讀了輸入a1 a2 an后后， nfa能到達的所有狀態：能到達的所有狀態：s1, s2, , sk，則則 dfa到達狀態到達狀態s1, s2, , sk 12 a 開始開始 0 a b b00, 1 a b a 0, 2 b 2.3 有有 限限 自自 動動 機機 未畫完未畫完 19 開始開始 0 a b ab 678 23 45 例例 (a|b)*ab，nfa如下，把它變換為如下，把它變換為dfa 2.3 有有

14、 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab 狀態狀態 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab a 狀態狀態 a = 0, 1, 2, 4, 7 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab ab 狀態狀態 a = 0, 1, 2, 4, 7 b = 1, 2, 3, 4, 6, 7, 8 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入

15、符號 ab ab b 狀態狀態 a = 0, 1, 2, 4, 7 b = 1, 2, 3, 4, 6, 7, 8 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab abc b 狀態狀態 a = 0, 1, 2, 4, 7 b = 1, 2, 3, 4, 6, 7, 8 c = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab abc b c 狀態狀態 a = 0, 1, 2, 4, 7 b = 1, 2, 3, 4, 6, 7,

16、 8 c = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab abc bb c 狀態狀態 a = 0, 1, 2, 4, 7 b = 1, 2, 3, 4, 6, 7, 8 c = 1, 2, 4, 5, 6, 7 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab abc bbd c 狀態狀態 a = 0, 1, 2, 4, 7 b = 1, 2, 3, 4, 6, 7, 8 c = 1, 2, 4, 5, 6, 7 d = 1

17、, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab abc bbd c d 狀態狀態 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 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab abc bbd cbc d 狀態狀態 a = 0, 1, 2, 4, 7 b = 1, 2, 3, 4, 6, 7, 8

18、c = 1, 2, 4, 5, 6, 7 d = 1, 2, 4, 5, 6, 7, 9 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab abc bbd cbc dbc 狀態狀態 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 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 輸入符號輸入符號 ab abc bbd cbc dbc 狀態狀態 bd 開始開始a a

19、 a b b a b c b a 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 bd 開始開始a a a b b a b c b a 12 開始開始a 0 a b b a b 識別語言識別語言 (a|b)*ab 的的自動機自動機 2.3 有有 限限 自自 動動 機機 19 開始開始 0 a b ab 678 23 45 bd 開始開始a a a b b a b c b a 12 開始開始a 0 a b b a b 識別語言識別語言 (a|b)*ab 的的自動機自動機 子集構造法不一子集構造法不一 定得到最簡定得到最簡dfa 2.3 有有 限限 自自

20、 動動 機機 bd 開始開始a a a b b a a, b c b a e b 2.3.4 dfa的化簡的化簡 死狀態死狀態 在轉換函數由部分函數改成全函數表示時引入在轉換函數由部分函數改成全函數表示時引入 左圖需要引入死狀態左圖需要引入死狀態e ；右圖無須引入死狀態；右圖無須引入死狀態 bd 開始開始a a a b b a b c b a 2.3 有有 限限 自自 動動 機機 可區別的狀態可區別的狀態 a和和b是可區別的狀態是可區別的狀態 從從a出發，讀過串出發，讀過串b，到達非接受狀態，到達非接受狀態c，而，而 從從b出發，讀過串出發，讀過串b，到達接受狀態，到達接受狀態d a和和c是不

21、可區別的狀態是不可區別的狀態 無任何串可用來像上面這樣無任何串可用來像上面這樣 區別它們區別它們 bd 開始開始a a a b b a b c b a 2.3 有有 限限 自自 動動 機機 方法方法 1. a, b, c, d move(a, b, c, a) = b move(a, b, c, b) = c, d 2. a, c, b, d move(a, c, a) = b move(a, c, b) = c bd 開始開始a a a b b a b c b a 1 2 開始開始a 0 a b b a b 2.3 有有 限限 自自 動動 機機 從正規式建立識別器的步驟從正規式建立識別器的步

22、驟 從正規式構造從正規式構造nfa（本節介紹）本節介紹） 用語法制導的算法，它用正規式語法結構來指導用語法制導的算法，它用正規式語法結構來指導 構造過程構造過程 把把nfa變成變成dfa （子集構造法，已介紹）子集構造法，已介紹） 將將dfa化簡化簡 （合并不可區別狀態，也已介紹）（合并不可區別狀態，也已介紹） 2.4 從正規式到有限自動機從正規式到有限自動機 首先構造識別首先構造識別 和字母表中一個符號的和字母表中一個符號的nfa 重要特點：僅一個接受狀態，它沒有向外的轉換重要特點：僅一個接受狀態，它沒有向外的轉換 i 開始開始 識別正規式識別正規式 的的nfa a fif 開始開始 識別正

23、規式識別正規式a的的nfa 2.4 從正規式到有限自動機從正規式到有限自動機 構造識別主算符為選擇的正規式的構造識別主算符為選擇的正規式的nfa 重要特點：僅一個接受狀態，它沒有向外的轉換重要特點：僅一個接受狀態，它沒有向外的轉換 f i 開始開始 識別正規式識別正規式s | t 的的nfa n (s) n (t) 2.4 從正規式到有限自動機從正規式到有限自動機 構造識別主算符為連接的正規式的構造識別主算符為連接的正規式的nfa 重要特點：僅一個接受狀態，它沒有向外的轉換重要特點：僅一個接受狀態，它沒有向外的轉換 i n (s) f 開始開始 識別正規式識別正規式 st 的的nfa n (t

24、) 2.4 從正規式到有限自動機從正規式到有限自動機 構造識別主算符為閉包的正規式的構造識別主算符為閉包的正規式的nfa 重要特點：僅一個接受狀態，它沒有向外的轉換重要特點：僅一個接受狀態，它沒有向外的轉換 n (s) f 開始開始 識別正規式識別正規式 s* 的的nfa i 2.4 從正規式到有限自動機從正規式到有限自動機 對于加括號的正規式對于加括號的正規式(s)，使用使用n(s)本身作為本身作為 它的它的nfa 2.4 從正規式到有限自動機從正規式到有限自動機 本方法產生的本方法產生的nfa有有下列性質下列性質 n(r)的狀態數最多是的狀態數最多是r中符號和算符總數的兩倍中符號和算符總數

25、的兩倍 n(r)只有一個接受狀態，接受狀態沒有向外的轉只有一個接受狀態，接受狀態沒有向外的轉 換換 2.4 從正規式到有限自動機從正規式到有限自動機 1 9 開始開始 0 a b ab 678 23 45 本方法產生的本方法產生的nfa有有下列性質下列性質 n(r)的每個狀態有一個用的每個狀態有一個用 的符號標記的指向其它的符號標記的指向其它 結點的轉換，或者最多兩個指向其它結點的結點的轉換，或者最多兩個指向其它結點的 轉轉 換換 2.4 從正規式到有限自動機從正規式到有限自動機 1 9 開始開始 0 a b ab 678 23 45 2.4 從正規式到有限自動機從正規式到有限自動機 1 9

26、開始開始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 從正規式到有限自動機從正規式到有限自動機 1 9 開始開始 0 ab 678 a b 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 從正規式到有限自動機從正規式到有限自動機 1 9 開始開始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.

27、4 從正規式到有限自動機從正規式到有限自動機 1 9 開始開始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 從正規式到有限自動機從正規式到有限自動機 1 9 開始開始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 2.4 從正規式到有限自動機從正規式到有限自動機 1 9 開始開始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1

28、a | b a b (a|b)*ab的分解的分解 2.4 從正規式到有限自動機從正規式到有限自動機 1 9 開始開始 0 a b ab 678 23 45 r9 r7 r8 r4 r3 r5 r6 * )( r2r1 a | b a b (a|b)*ab的分解的分解 (a|b)*ab的兩個的兩個nfa的比較的比較 1 2 開始開始a 0 a b b 1 9 開始開始 0 a b ab 678 23 45 手工構造手工構造: 算法構造算法構造: 2.4 從正規式到有限自動機從正規式到有限自動機 小結：從正規式建立識別器的步驟小結：從正規式建立識別器的步驟 從正規式構造從正規式構造nfa 把把nf

29、a變成變成dfa 將將dfa化簡化簡 存在其它辦法存在其它辦法 2.4 從正規式到有限自動機從正規式到有限自動機 用用lex建立詞法分析器的步驟建立詞法分析器的步驟 lex 編譯器編譯器 lex源程序源程序lex.l lex.yy.c c 編譯器編譯器 lex.yy.ca.out a.out 輸入流輸入流 記號序列記號序列 2.5 詞法分析器的生成器詞法分析器的生成器 lex程序包括三個部分程序包括三個部分 聲明聲明 翻譯規則翻譯規則 輔助過程輔助過程 lex程序的翻譯規則程序的翻譯規則 p1動作動作1 p2動作動作2 pn動作動作n 2.5 詞法分析器的生成器詞法分析器的生成器 例例聲明部分

30、聲明部分 % /* * 常量常量lt, le, eq, ne, gt, ge, while, do, id, number, relop的定義的定義* */ % /* * 正規定義正規定義 * */ delim t n wsdelim+ lettera za z digit0 9 idletter(letter|digit)* * numberdigit+( .digit+)?(e+ ?digit+)? 2.5 詞法分析器的生成器詞法分析器的生成器 例例翻譯規則部分翻譯規則部分 ws/* * 沒有動作，也不返回沒有動作，也不返回 * */ whilereturn (while); doretu

31、rn (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; return (relop); 2.5

32、詞法分析器的生成器詞法分析器的生成器 例例輔助過程部分輔助過程部分 install_ id ( ) /* * 把詞法單元裝入符號表并返回指針。把詞法單元裝入符號表并返回指針。 yytext指向該詞法單元的第一個字符，指向該詞法單元的第一個字符， yyleng給出的它的長度給出的它的長度* */ install_num ( ) /* * 類似上面的過程，但詞法單元不是標識符而類似上面的過程，但詞法單元不是標識符而 是數是數 * */ 2.5 詞法分析器的生成器詞法分析器的生成器 詞法分析器的作用和接口，用高級語言編寫詞法分析器的作用和接口，用高級語言編寫 詞法分析器等內容詞法分析器等內容 掌握下面涉及的一些概念，它們之間轉換的掌握下面涉及的一些概念，它們之間轉換的 技巧、方法或算法技巧、方法或算法 非形式描述的語言非形式描述的語言 正規式正規