編譯原理及實現(xiàn)技術(shù)課件：第二章 詞法分析

1、第二章 詞法分析詞法分析概述正則表達式自動機理論 詞法分析器的設(shè)計與實現(xiàn)1 詞法分析器概述詞法分析器的功能詞法分析器的地位2 1.1 詞法分析器的功能功能 讀源程序的符號序列，逐個拼出單詞，并構(gòu)造相應(yīng)的內(nèi)部表示，同時檢查源程序中的詞法錯誤。單詞 所謂單詞是指語言中具有獨立含義的最小的語義單位。Token 單詞的內(nèi)部表示?！俺绦蛘Z言的操作對象（只能）是該語言規(guī)定的各種數(shù)據(jù)?！本幾g程序是用某種程序語言書寫的程序，其操作對象是一般程序中的各種語法單位。 31.1.1 單詞的分類單詞標識符X1，classT常量10，LENGTH特殊符號保留字while，int運算符+，界限符，；格式符EOF，41.1

2、.2 Token的結(jié)構(gòu)Token是單詞在詞法分析器中的內(nèi)部結(jié)構(gòu)構(gòu)成：特殊處理常數(shù)標識符特殊符號5TypeValueif (position 10) rate = 3.14 * initial;, , ？Line-num1.2 詞法分析器的接口6CharList 獨 立詞法分析器語法分析TokenList 附 屬詞法分析器語法分析callTokenChar List2 正則表達式符號串基本概念正則表達式理論正則表達式在詞法分析中的應(yīng)用72.1 基本概念字母表： ，元素的非空有窮集合。 符號串：由字母表中的符號組成的任何有窮序列?；蛘呷缦露x：空符號串（用表示）是上的符號串 若x是上的符號串,a是

3、的元素,則xa是上的符號串 y是上的符號串,當且僅當它可以由1和2導(dǎo)出8思考符號串的長度如何定義？符號的個數(shù)和有何區(qū)別？符號串有無如何判斷兩個符號串相等？對應(yīng)位置的符號相等（符號串的長度相同）9符號串的連接：設(shè)x和y均是字母表上的符號串，它們的連接是把y的所有符號順序接在x的符號之后所得到的符號串。 符號串的方冪：設(shè)x是字母表上的符號串，把x自身連接n次得到的符號串z，稱作符號串x的n 次冪，記作 z=xn。前綴和后綴：設(shè)x是字母表上的符號串，x=yz，則y是x的前綴，z是x的后綴，特別是當z時，y是x的真前綴；y時，z是x的真后綴。子符號串：非空符號串 x ，刪去它的前綴和后綴后所得到的符號

4、串稱為 x 的子符號串，簡稱子串。如果刪去的前綴和后綴不同時為,則稱該子串為真子串。10思考符號x的零次冪x0=？為什么？空串，“零次連接得到的串”首先是符號串。符號串a(chǎn)bc的前綴、真前綴、后綴、真后綴、子串、真子串分別是什么？,a,ab,abc，,a,ab，,c,bc,abc，,c,bc，,a,b,c,ab,bc,abc,a,b,c,ab,bc11符號串集合：若集合A中的所有元素都是某字母表上的符號串，則稱A為該字母表上的符號串集合。符號串集合的乘積：設(shè)A、B 是兩個符號串集合，AB表示A與B的乘積，則定義AB=xy|(xA)(yB) 符號串集合的方冪：設(shè)A是符號串集合，則稱Ai 是符號串集

5、合 A的方冪，其中i 是非負整數(shù)。A0=, A1=A, A2=AA, , An=AA A符號串集合的正閉包：A+=A1A2A3 符號串集合的星閉包：A*= A0A1A2A3 12思考符號串集合X的零次冪X0=?為什么？由符號串集合的冪定義可知，對于k為任意正整數(shù)X0 應(yīng)該滿足X0 Xk= Xk X0 =Xk，所以設(shè)X為給定的非空符號串集合，下面等式成立嗎？X+=XX*X=X= X= X=X 13思考設(shè)X=a，b，Y=c，d計算XY，YX，X4，Xn，X+。XY=ac,ad,bc,bdYX=ca,cb,da,dbX4=a4,a3b,a2ba,aba2,ba3,a2b2,abab,baab,bab

6、a,b2a2,ab3,bab2,b2ab,b3a,b4Xn=an,an-1b,an-2ba,an-3ba2,bn-1a,bnX+=a,b,a2,ab,ba,b2,a3,a2b,aba,baa,ab2, bab,b3,a4,142.2 正則表達式理論描述程序設(shè)計語言中單詞的一種簡單而且數(shù)學(xué)化的工具。表示符號串的構(gòu)成模式。正則表達式r定義了一個符號串集合S, S內(nèi)的每個符號串都與r所定義的模式相匹配，S稱為由r生成的語言L(r)152.2.1 非形式化定義基本正則表達式，a正則表達式的運算選擇x|y連接xy重復(fù)x*16思考三種運算是否可以和算數(shù)運算類比？| vs. +; vs. ; * vs. n

7、交換律 A|B=B|AABBA結(jié)合律 (A|B)|C= A|(B|C)A(BC)=(AB)C分配律 A(B|C)=AB|AC(A|B)C=AC|BC同一律 A=A=A冪等律 A*=A*三種運算的優(yōu)先級關(guān)系如何？|*172.2.2 正則表達式形式化定義正則表達式中出現(xiàn)的所有符號構(gòu)成的集合為該正則表達式的字母表，用S表示。 則S上的正則表達式遞歸定義如下：和是正則表達式；對于任意符號a，則a是正則表達式；若r和s是正則表達式，則r|s，rs，r*都是正則表達式；僅由有限次應(yīng)用上述規(guī)則所構(gòu)成的正則表達式稱為S上的正則表達式。182.2.3 正則表達式的解釋給定為給定的字母表，則每個上的正則表達式將定

8、義上的一個符號串集，稱為它表示的正則集。用R表示上的正則表達式，用L(R)表示R所表示的符號串集合，即函數(shù)L表示正則表達式到符號串集的映射。是正則表達式即R ，則有L()=。是正則表達式即R ，則有L()=。19a是正則表達式即aR，則L(a)=a。A和B是正則表達式，即AR，BR ，則有A | BR，L(A | B)= L(A)L(B)ABR，L( AB )= L(A)L(B)A*R，L( A*)= L(A)* ( A )R，L( (A) )= L(A)20當（和）不在中時實例1= a,b 21正則表達式eab*2. a(a|b)* L(e)上所有以a為首后跟任意多個（包括0個）b的符號串集

9、上所有以a為首的符號串集實例2設(shè)字母表=0，1，求二進制數(shù)字集合且為2的倍數(shù)。所有上定義的串的正則表達式為（1|0）*則二進制數(shù)表示為1（1|0）*|0其中能被二整除的表示為1（1|0）*0|022實例3設(shè)字母表=x，y，z，出現(xiàn)的第一個x之前沒有y的符號串；包含偶數(shù)個x的所有符號串。z*x(x|z)*y（x|y|z）*|（x|z）*(y|z)*x(y|z)*x)*(y|z)*23思考設(shè)字母表=a，b，求含有奇數(shù)個a的串的正則表達式和有相同個數(shù)a和b的串對應(yīng)的正則表達式。(b*ab*a)*ab*無法描述“有相同個數(shù)a和b”如何用正則表達式描述單詞？242.3 正則表達式在詞法分析中的應(yīng)用 設(shè)I

10、為字母集合a，b，z，其正則表達式為a|b|z設(shè)D為數(shù)字集合0，1，9 ，其正則表達式為0|1|9則標識符的正則表達式為I(I|D)*常數(shù)的正則表達式為(+|-|)D+(.D+|)特殊符號的正則表達式為25有瑕疵2.3.1 擴充的正則表達式 一次或多次重復(fù): A+任何符號:“”在字母表中任何符號.符號范圍: 0-9 a-z A-Z不在給定范圍內(nèi)的符號: a可選: A?262.3.2 單詞描述保留字 如 begin=begin標識符 letter=a-zA-Z digit=0-9 identifier=letter(letter|digit)*數(shù)字 整數(shù)Int1-9Digit*|0 實數(shù)realInt（.D