第二章詞法分析

1、第二章第二章 詞法分析詞法分析本章內容本章內容 詞法分析器：把構成源程序的字符流翻譯成詞法分析器：把構成源程序的字符流翻譯成記號流，記號流，還完成和用戶接口的一些任務還完成和用戶接口的一些任務 圍繞詞法分析器的自動生成展開圍繞詞法分析器的自動生成展開 介紹正規(guī)式、狀態(tài)轉換圖和有限自動機概念介紹正規(guī)式、狀態(tài)轉換圖和有限自動機概念詞法分析器詞法分析器語法分析器語法分析器符號表符號表記號記號(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 正規(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 詞法記號的描述與識別詞法記號的描述與識別 正規(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構成的所有串集構成的所有串集 (a | b)*由由a和和b構成的所有串集構成的所有串集 復雜的例子復雜的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：010011010000100000101110012.2 詞法記號的描述與識別詞法記號的描述與識別 2.2.3 正規(guī)定義正規(guī)定義 對正規(guī)式命名，使表示簡潔對正規(guī)式命名，使表示簡潔 d1 r1 d2 r2 . . . dn rn各個各個di的名字都不同的名字都不同每個每個ri都是都是 d1, d2, , di-1 上的正

5、規(guī)式上的正規(guī)式2.2 詞法記號的描述與識別詞法記號的描述與識別 正規(guī)定義的例子正規(guī)定義的例子 C語言的標識符是字母、數(shù)字和下劃線組成的串語言的標識符是字母、數(shù)字和下劃線組成的串 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_( (letter_ | |digit) )* 2.2 詞法記號的描述與識別詞法記號的描述與識別 正規(guī)定義的例子正規(guī)定義的例子 無符號數(shù)集合，例無符號數(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 詞法記號的描述與識別詞法記號的描述與識別 正規(guī)定義的例子（進行下一步討論的例子）正規(guī)定義的例子（進行下一步討論的例子）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 詞法記號的描述與識別詞法記號的描述與識別 2.2.4 轉換圖轉換圖 關系算符的轉換圖關系算符的轉換圖051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)開始開始=*otherother2.2

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

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

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

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

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

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

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

15、輸入符號輸入符號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 有有 限限 自自 動動 機機 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 有有 限限 自自 動動 機機 19開始開始 0ab ab6782345 輸入符號輸入符號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 有有 限限 自自 動動 機機 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 有有 限限 自自 動動 機機 19開始開始 0ab ab6782345 輸入符號輸入符號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 有有 限限 自自 動動 機機 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 有有 限限 自自 動動 機機 19開始開始 0ab ab6782345 輸入符號輸入符號abABCBBDCBCDBC狀態(tài)狀態(tài) BD開始開始aAabbabCba2.3 有

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

19、分函數(shù)改成全函數(shù)表示時引入 左圖需要引入死狀態(tài)左圖需要引入死狀態(tài)E ；右圖無須引入死狀態(tài)；右圖無須引入死狀態(tài)BD開始開始aAabbabCba2.3 有有 限限 自自 動動 機機 可區(qū)別的狀態(tài)可區(qū)別的狀態(tài) A和和B是可區(qū)別的狀態(tài)是可區(qū)別的狀態(tài) 從從A出發(fā)，讀過單字符出發(fā)，讀過單字符b構成的串，到達非接受構成的串，到達非接受狀態(tài)狀態(tài)C，而從，而從B出發(fā)，讀過串出發(fā)，讀過串b，到達接受狀態(tài)，到達接受狀態(tài)D A和和C是不可區(qū)別的狀態(tài)是不可區(qū)別的狀態(tài) 無任何串可用來像上面這樣無任何串可用來像上面這樣區(qū)別它們區(qū)別它們BD開始開始aAabbabCba2.3 有有 限限 自自 動動 機機 方法方法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 有有 限限 自自 動動 機機 從正規(guī)式建立識別器的步驟從正規(guī)式建立識別器的步驟從正規(guī)式構造從正規(guī)式構造NFA（本節(jié)介紹）本節(jié)介紹）用語法制導的算法，它用正規(guī)式語法結構來指導用語法制導的算法，它用正規(guī)式語法結構來指導構造過程構造過程把把NFA變成變成DFA （子集構造法，已介紹）子集構造法，已介紹） 將將DFA化簡化簡 （合并不可區(qū)別狀態(tài)，

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

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

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

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

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

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

27、器的步驟建立詞法分析器的步驟Lex編譯器編譯器Lex源程序源程序lex.llex.yy.cC編譯器編譯器lex.yy.ca.outa.out輸入流輸入流記號序列記號序列2.5 詞法分析器的生成器詞法分析器的生成器 Lex程序包括三個部分程序包括三個部分 聲明聲明 翻譯規(guī)則翻譯規(guī)則 輔助過程輔助過程 Lex程序的翻譯規(guī)則程序的翻譯規(guī)則 p1動作動作1 p2動作動作2 pn動作動作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/* * 沒有動作，也不返回沒有動作，也不返回 * */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 ( ) /* * 把詞法單元裝入符號表并返回指針。把詞法單元裝入符號表并返回指針。yytext指向該詞法單元的第一個字符，指向該詞法單元的第一個字符，yyleng給出的它的長度給出的它的長度* */installNum ( ) /* * 類似上面的過程，但詞法單元不是標識符而類似上面的過程，但詞法單元不是標識符而是數(shù)是數(shù) * */2.5 詞法分析器的生成器詞法分析器的生成器 詞法分析器的作用和接口，用高級語言編寫詞法分析器的作用和接口，用高級語言編寫詞法分析器等內容詞法分析器等內容 掌握下面涉及的一些概念，它們之間轉換的掌握下面涉及的一些概念，它們之間轉換的技巧、方法或算法技巧、方法或算法 非形式描述的語言非形式描述的語言 正規(guī)式正規(guī)式 正規(guī)式正規(guī)式 NF