1、1第三章詞法分析第三章詞法分析2本章內容q 詞法分析器：將源程序的字符流翻譯成記號流，以及用戶接口等任務q 構造詞法分析器手工自動生成q 重點正則表達式有限狀態自動機自動生成工具：Lex/Flex3 詞法分析器詞法分析器語法分析器語法分析器符號表符號表記號記號取下一個記號取下一個記號源程序源程序3.1 詞法分析器的作用詞法分析器的作用 if(count5) sum+=count; if ( count 5 ) sum += count ; 4自動生成詞法分析器自動生成詞法分析器 詞法分析器詞法分析器字符流字符流詞法單元流詞法單元流詞法分析的規則詞法分析的規則詞法分析器的詞法分析器的產生器產生器

2、(eg.Lex或或Flex)5詞法分析器的主要任務詞法分析器的主要任務q 讀入輸入字符，產生token序列，交給語法分析使用；q 相關輔助任務過濾注釋、空格等；為了報錯，記錄每個token在源文件中的位置63.1.1 詞法分析與句法分析分開的原詞法分析與句法分析分開的原因因q 簡化編譯器的設計，讓句法分析器簡單化。q 提高編譯效率：使用適合詞法分析的專門技術。q 增強編譯器的可移植性：輸入設備相關的特殊性可以被限制在詞法分析器中。73.1.2 詞法單元、模式、詞素詞法單元、模式、詞素 q 詞法單元詞法單元(token)(token)：一個詞法單元名和一個可選的屬性值組成。用表示。它是源語言文法

3、的終結符。q 模式模式(pattern)(pattern)：源語言中特定記號的構成規則，可以用正則表達式示。(例如：變量名的命名規則）q 詞素（詞素（lexeme)lexeme)：是源程序中的一個字符序列，它和某個詞法單元的模式匹配，并被詞法分析器識別為該詞法單元的一個實例。if ( count 5 ) sum += count ; Lexeme lksim 8例子例子q C語言語句：printf(“total=%d”, score);#define ID_TOKEN 300#define IF_TOKEN 400#define FOR_TOKEN 500struct Token int To

4、kenName; union int IntValue; double DblValue; IdItem * ptr; Attribute;9詞法單元的例子詞法單元的例子 詞法單元名詞法單元名 詞素例舉詞素例舉模式的非形式描述模式的非形式描述 constconst constforfor forrelation , = , = , 或 = 或 = 或 idsum, count, D5 由字母或下劃線開頭的字母數字串num 3.1, 10, 2.8E12任何數值常數literal“hello”雙引號之間的任意字符串，但雙引號本身除外10詞法單元的例子詞法單元的例子q 下列結構作為詞法單元toke

5、n：關鍵字、操作符、標識符、常量、字符串、標點符號每個關鍵字對應一個詞法單元（token）表示多個運算符的詞法單元tokens一個表示所有標識符的詞法單元一個或多個表示常量的詞法單元，比如數字和字符串每一個標點符號有一個詞法單元，比如左右括號、逗號和分號。113.1.3 詞法單元的屬性詞法單元的屬性q 用二元組表示；屬性一般用符號表的指針來表示q 例如，position = initial + rate * 60id，指向符號表中position這個條目的指針assign _ op， id，指向符號表中initial這個條目的指針add_op，+id，指向符號表中rate這個條目的指針mul_

6、 op, *num，整數，值60#define ID 600123.1.4 詞法錯誤詞法錯誤q 詞法分析器對源程序采取非常局部的觀點q 難以發現下面的錯誤fi (a = f (x) ) q 在實數是a.b格式下，可以發現下面的錯誤123.q 此時，使用“恐慌模式”的錯誤恢復q 錯誤修補133.2 詞素的描述詞素的描述q 正則表達式是模式的重要表示方法。143.2.1 串和語言串和語言q 字母表：有限符號的集合. 例： = 0,1，a,b,a,b,z,A,B,Zq 字符串：符號的有窮序列，例：0110,q 字符串s的長度：出現在s中符號的個數，記作|s|q 空串：長度為的符號串，用表示q 語言：

7、給定字母表上的任意一個字符串集合,0,00,000, , a,b,aa,ab,ba,bb, , q 句子：屬于語言的字符串。 本書中句子、字符串基本表達同一個意思。15字符串例子及術語字符串例子及術語q 串banana前綴前綴Prefix:從從s的尾部刪除的尾部刪除0個或多個符號后得到的串，個或多個符號后得到的串，例如：例如： , b, ba, ban, bana, banan, banana后綴后綴Suffix: , a, na, ana, nana, anana, banana子串子串(Substring): , b, a, n, ba, an, na, , ban, ana, nan,

8、bana, anan,nana, banan, anana, banana子序列子序列(Subsequence):bnan,nn真前綴真前綴Properprefix：b,ba,ban,bana,banan, 真后綴真后綴Propersuffix：a,na,ana,nana,anana16語言語言(Language)q 語言(Language)：某個給定字母表上一個任意可數的字符串集合。q Special Languages: and 可枚舉17語言的例子語言的例子字符集字符集語言語言0,11,10,100,1000,1000000,1,00,11,000,111,a,b,cabc,aabbcc

9、,aaabbbccc,A,ZTEE,FORE,BALL,FOR,WHILE,GOTO,A,Z,a,z,0,9,所有合法的所有合法的C語言程序語言程序+,-,所有語法正確的英語句子所有語法正確的英語句子18串的運算串的運算q 連接xy 例如：x=ab y=cd, xy=abcds = s = s q 乘積（指數）定義s0為，si為si-1s（i 0）s1=s, s2=ss, s3=sss, 例如，s=ab, s1=ab, s2=abab, s3=ababab 193.2.2 語言上的運算語言上的運算OPERATIONDEFINITIONL和和M的的并并(union)L和和M的的連接連接(conc

10、atenation)L的的Kleene閉包閉包(Kleene closure)L的正閉包的正閉包( positive closure)L = L M=s|sL或或s ML = LM=st|sL且且s M L = L+=0iiLL的的0個或多個連接個或多個連接, L LL LLL L= L*=1iiLL的一個或多個連接的一個或多個連接, L LL LLL Kleene ，星號，德語稱 Kleensche Hlle 20語言的運算語言的運算例如：L=a,b, M=cc,ddq 和：和：LM =s |s L 或或s M 例如： LM = a, b, cc, dd q 連接：連接：LM=st|s L且

11、且t M 例如： LM = acc, add, bcc, bdd q 指數：指數：L0= ，Li=Li -1L 例如： L1=L, L2=LL=aa,ab,ba,bb L3=aaa, aab, aba, abb, baa, bab, bba, bbbq 閉包：閉包：L =L0L1L2q 正閉包：正閉包：L+=L1L2Kleene閉包閉包Kleene 星號,克林星號21語言運算的例子語言運算的例子L = A, B, , Z, a, b, , z ，D = 0, 1, , 9 L D ：是字符和數字的集合;LD ：一個字符的后面接一個數字的集合;L4 ：四個字符的集合 L* = 以及 L 上的所有

12、可能的串 L (L D )* ：以字符開頭的字符和數字組成的串的集合D+ ：一個或多個數字組成的串的集合。223.2.3 正則表達式正則表達式q 例如，C語言的標識符集可以定義為：letter_ (letter_ | digit )*其中 letter_ a,b,z, A,B,Z, _ q 正則式(Regular Expression)可以用來表示簡單的語簡單的語言言，叫做正則集（regular set）。23 是一個正則表達式，L()= 如果a是上的一個符號,那么a是一個正則表達式，并且L(a)= a假設 r和s都是正則表達式，分別表示語言 L(r) and L(s)，那么 (a) (r)

13、| (s) 是一個正則表達式，表示語言 L(r) L(s) (b) (r)(s) 是一個正則表達式，表示語言L(r) L(s) (c) (r)* 是一個正則表達式，表示語言 (L(r)* (d) (r) 是一個正則表達式，表示語言 L(r) 所有的運算符都是左結合的。.precedence定義字母表定義字母表 上的正則表達式的規則上的正則表達式的規則24正則式定義的語言備注aa 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 都是左結合的

14、。優先級從高到低：*，連接，|25正則表達式的例子正則表達式的例子( =a,b)q 正則表達式正則集合（regular set )a | ba, b(a | b) (a | b )aa, ab, ba, bbaa | ab | ba | bbaa, ab, ba, bba*由0個或多個a構成的所有字符串集合(a | b)*由a和b構成的所有字符串集合a | a*bq 復雜的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 偶數個和偶數個組成的偶數個和偶數個組成的01字符串字符串letter_ (letter_ | digit )*letter_

15、 a,b,.z,A,B,Z,0,1,9, _ 26AXIOMDESCRIPTIONr | s = s | rr | (s | t) = (r | s) | t(r s) t = r (s t) r = rr = rr* = ( r | )*r ( s | t ) = r s | r t( s | t ) r = s r | t rr* = r*| 是可交換的| 是可結合的“連接”是可結合的“連接”是可分配的* 和 之間的關系是“連接”的單位元* 的冪等性正則表達式的代數性質正則表達式的代數性質27(rs)* r*s*(r|s)* r*|s*正則表達式的代數性質正則表達式的代數性質283.2.4

16、 正則定義正則定義為了讓正則表達式的表示簡潔，可以對正則式命名。 d1 r1 d2 r2 . . . dn rn各個di的名字都不同, di每個ri都是d1, d2, , di-1 上的正則式 29正則定義的例子正則定義的例子1q C語言的標識符集合letter_ A | B | | Z | a | b | | z | _digit 0 | 1 | | 9id letter_ ( letter_ | digit)* 如果代入，則有標識符標識符的正則表達式為( A | | Z | a | | z | _ ) ( A | | Z | a | | z | _ | 0 | 1 | | 9 )*30正則

17、定義的例子正則定義的例子2q 無符號數集合(integer or floating point)，例如1946, 11.28, 63.6E8, 1.99E6 digit 0 | 1 | | 9digits digit digit*optionalFraction .digits | optionalExponent (E ( + | | ) digits ) | number digits optionalFraction optionalExponen313.2.5 正則表達式的擴展正則表達式的擴展1. “+” : 一個或多個，表示一個正則表達式及其語言的正閉包， r+表示語言(L(r)+

18、r* = r+ | r+ = r r*2. “?” : 零個或一個出現，也就是說，r?等價于r| 3. “”: 一個正則表達式a1|a2|an（其中ai是字母表中的各個符號）可以縮寫成a1a2an。例如：ade=a|d|e范圍 :如果a1|a2|an是連續字符集、數字集等， 例如：A-Z = A | B | C | | Z32使用簡略的表達方式使用簡略的表達方式Using Shorthands q C語言的標識符集合letter_ A | B | | Z | a | b | | z | _digit 0 | 1 | | 9id letter_ ( letter_ | digit)* q 簡化為：letter_ A-Za-z_digit 0-9id letter_ ( letter_ | digit)* 33使用簡略的表達方式使用簡略的表達方式digit 0 | 1 | | 9digits digit digit*optionalFraction .d