編譯原理 Lecture02.Lexical Analysis (I)

1、Principles of Compiler ConstructionLecture 2 Lexical Analysis (I)回顧：編譯器的結(jié)構(gòu)Lexical Analyzer vs. Syntax Analyzer (Parser)詞法分析的任務(wù)源程序在經(jīng)詞法分析之前是字符的序列例如：if (month = March)nday = 31; 是字符序列：tif (month = March)nttnday = 31;詞法分析的任務(wù)詞法分析器將其轉(zhuǎn)化為token的序列token是指帶有附加信息的字符串例如單純的字符串我們稱為lexeme在自然語言中：名詞，動詞，形容詞程序語言中：標(biāo)識符，關(guān)

2、鍵字，常量，運算符，分界符類別屬性是包括在token中的基本信息語法分析器每次從詞法分析器獲得一個token，對不同類別token的處理截然不同關(guān)鍵問題如何識別出一個token？如何識別出一個lexeme？如何知道lexeme的類別屬性？類別定義關(guān)鍵字或保留字：預(yù)先指定的單詞，如if, for, else等標(biāo)識符：字母開頭的字母或數(shù)字序列非保留字數(shù)字：正整數(shù)：首字符非0的數(shù)字序列負數(shù)：-和正整數(shù)的連接類別定義自然語言定義方式的缺陷：繁瑣不精確難以被計算機處理怎么辦？借助形式化的語言！3.3.1 Strings and Languages字母表：An alphabet is any finite

3、 set of symbols.語言：字母表上的語言，是由中字符組成的字符串的集合例如：=0, 1則001, 100100，1, 11, 111, 1111, 都是定義在字母表的語言語言（Language）字母表：字符的集合語言：字母表上的語言，是由中字符組成的字符串的集合例如：=0, 1則001, 100100，1, 11, 111, 1111, 都是定義在字母表的語言程序設(shè)計語言 程序：程序設(shè)計：程序設(shè)計語言：語句：語言：作用：告訴計算機“做什么”和“怎么做” 編寫程序的過程編寫程序使用的語言定義在一個字符集合上的按一定的語法規(guī)則連接的有意義的字符串由語句組成的全體交換信息的工具自然語言與

4、形式語言自然語言：人與人交換信息的工具。不精確，有二義性 漢語、英語 手提包形式語言：數(shù)學(xué)語言，精確語言，無二義性。計算機語言為人與計算機交換信息的工具 計算機語言文法、自動機、表達式語言的運算語言是一種集合，所以集合的運算也適用于語言語言運算的例子L=A,B,Z,a,b,z, D=0,1,9正則語言（Regular Language）正則語言的優(yōu)點：容易理解能高效實現(xiàn)具有堅實的理論基礎(chǔ)3.3.3 Regular Expressions正則表達式及其描述的語言遞歸定義：Basis: is a regular expr; L() = . a is a regular expr; L(a) = a

5、. Induction: if r and s are regular exprs, r | s is a regular expr; L(r | s) = L(r) L(s). r s is a regular expr; L(r s) = L(r) L(s). r* is a regular expr; L(r*) = (L(r)*. (r) is a regular expr; L(r) = L(r).一些規(guī)定為了去除不必要的符號，我們規(guī)定：一元運算符*具有最高的優(yōu)先級連接運算符具有次高優(yōu)先級|運算符的優(yōu)先級最低上述運算符都是左結(jié)合的（left associative）例子令字母表為a,

6、 b正則語言A language that can be defined by a regular expression is called a regular set.If two regular expressions r and s denote the same regular set, we say they are equivalent and write r = s.例如：(a|b)=(b|a)一些正則語言的等價規(guī)則例子：C語言的標(biāo)識符：(a | b | . | z | A | B | . | Z|_) ( (a | b | . | z | A | B | . | Z|_) |

7、(0 | 1 | . | 9) )*還是太繁瑣了，有沒更簡潔的表示？例子：C語言的標(biāo)識符：(a | b | . | z | A | B | . | Z|_) ( (a | b | . | z | A | B | . | Z|_) | (0 | 1 | . | 9) )*還是太繁瑣了，有沒更簡潔的表示？正則定義（ Regular Definition ）d1r1d2r2dnrnwhere: 1. Each di is a new symbol, not in C and not the same as any other of the ds, and 2. Each ri is a regula

8、r expression over the alphabet C U d1, d 2 , . . , di-1). 例子例1：C語言的標(biāo)識符例子例2：無符號浮點數(shù)digit 0 | 1 | |9 digits digit digit* optionalFraction . digits | optionalExponent ( E ( + | - | ) digits ) | number digits optionalFraction optionalExponent 正則表達式的擴展r+=rr*r?=r|abc=a|b|c, a-z=a|b|z例子C語言標(biāo)識符：無符號浮點數(shù)：練習(xí)下列正則表

9、達式描述什么語言？a(a|b)*a(a|b)*a(a|b)(a|b)a*ba*ba*ba*(|a)b*)*練習(xí)用正則表達式描述下列語言：所有由按詞典遞增序排列的小寫字母組成的字符串例如：add, low都符合要求，而zzg則不符合a*b*c*d*e*f*g*h*i*.不以ab開頭的所有只含有字母a和b的字符串.正則表達式的其它應(yīng)用文本搜索和模糊匹配合法性檢查文本的自動更正和編輯信息提取Chomsky hierarchy A Big QUESTION如何讓計算機識別用正則表達式描述的語言？非確定有限自動機（NFA）The language defined (or accepted) by an NFA is the set of strings labeling some path from the start to an accepting state.例子：NFA識別語言識別語言 L(a|b)*abb).例子：帶的NFA識別語言L(aa*|bb*).確定有限自動機（DF