第3章詞法(1)

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

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

3、的終結(jié)符。q 模式模式(pattern)(pattern)：源語言中特定記號的構(gòu)成規(guī)則，可以用正則表達(dá)式示。(例如：變量名的命名規(guī)則）q 詞素（詞素（lexeme)lexeme)：是源程序中的一個(gè)字符序列，它和某個(gè)詞法單元的模式匹配，并被詞法分析器識別為該詞法單元的一個(gè)實(shí)例。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 由字母或下劃線開頭的字母數(shù)字串num 3.1, 10, 2.8E12任何數(shù)值常數(shù)literal“hello”雙引號之間的任意字符串，但雙引號本身除外10詞法單元的例子詞法單元的例子q 下列結(jié)構(gòu)作為詞法單元toke

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

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

7、給定字母表上的任意一個(gè)字符串集合,0,00,000, , a,b,aa,ab,ba,bb, , q 句子：屬于語言的字符串。 本書中句子、字符串基本表達(dá)同一個(gè)意思。15字符串例子及術(shù)語字符串例子及術(shù)語q 串banana前綴前綴Prefix:從從s的尾部刪除的尾部刪除0個(gè)或多個(gè)符號后得到的串，個(gè)或多個(gè)符號后得到的串，例如：例如： , 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)：某個(gè)給定字母表上一個(gè)任意可數(shù)的字符串集合。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串的運(yùn)算串的運(yùn)算q 連接xy 例如：x=ab y=cd, xy=abcds = s = s q 乘積（指數(shù)）定義s0為，si為si-1s（i 0）s1=s, s2=ss, s3=sss, 例如，s=ab, s1=ab, s2=abab, s3=ababab 193.2.2 語言上的運(yùn)算語言上的運(yùn)算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個(gè)或多個(gè)連接個(gè)或多個(gè)連接, L LL LLL L= L*=1iiLL的一個(gè)或多個(gè)連接的一個(gè)或多個(gè)連接, L LL LLL Kleene ，星號，德語稱 Kleensche Hlle 20語言的運(yùn)算語言的運(yùn)算例如：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 指數(shù)：指數(shù)：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語言運(yùn)算的例子語言運(yùn)算的例子L = A, B, , Z, a, b, , z ，D = 0, 1, , 9 L D ：是字符和數(shù)字的集合;LD ：一個(gè)字符的后面接一個(gè)數(shù)字的集合;L4 ：四個(gè)字符的集合 L* = 以及 L 上的所有

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

13、| (s) 是一個(gè)正則表達(dá)式，表示語言 L(r) L(s) (b) (r)(s) 是一個(gè)正則表達(dá)式，表示語言L(r) L(s) (c) (r)* 是一個(gè)正則表達(dá)式，表示語言 (L(r)* (d) (r) 是一個(gè)正則表達(dá)式，表示語言 L(r) 所有的運(yùn)算符都是左結(jié)合的。.precedence定義字母表定義字母表 上的正則表達(dá)式的規(guī)則上的正則表達(dá)式的規(guī)則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 都是左結(jié)合的

14、。優(yōu)先級從高到低：*，連接，|25正則表達(dá)式的例子正則表達(dá)式的例子( =a,b)q 正則表達(dá)式正則集合（regular set )a | ba, b(a | b) (a | b )aa, ab, ba, bbaa | ab | ba | bbaa, ab, ba, bba*由0個(gè)或多個(gè)a構(gòu)成的所有字符串集合(a | b)*由a和b構(gòu)成的所有字符串集合a | a*bq 復(fù)雜的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 偶數(shù)個(gè)和偶數(shù)個(gè)組成的偶數(shù)個(gè)和偶數(shù)個(gè)組成的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*| 是可交換的| 是可結(jié)合的“連接”是可結(jié)合的“連接”是可分配的* 和 之間的關(guān)系是“連接”的單位元* 的冪等性正則表達(dá)式的代數(shù)性質(zhì)正則表達(dá)式的代數(shù)性質(zhì)27(rs)* r*s*(r|s)* r*|s*正則表達(dá)式的代數(shù)性質(zhì)正則表達(dá)式的代數(shù)性質(zhì)283.2.4

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

17、定義的例子正則定義的例子2q 無符號數(shù)集合(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 正則表達(dá)式的擴(kuò)展正則表達(dá)式的擴(kuò)展1. “+” : 一個(gè)或多個(gè)，表示一個(gè)正則表達(dá)式及其語言的正閉包， r+表示語言(L(r)+

18、r* = r+ | r+ = r r*2. “?” : 零個(gè)或一個(gè)出現(xiàn)，也就是說，r?等價(jià)于r| 3. “”: 一個(gè)正則表達(dá)式a1|a2|an（其中ai是字母表中的各個(gè)符號）可以縮寫成a1a2an。例如：ade=a|d|e范圍 :如果a1|a2|an是連續(xù)字符集、數(shù)字集等， 例如：A-Z = A | B | C | | Z32使用簡略的表達(dá)方式使用簡略的表達(dá)方式Using Shorthands q C語言的標(biāo)識符集合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使用簡略的表達(dá)方式使用簡略的表達(dá)方式digit 0 | 1 | | 9digits digit digit*optionalFraction .d