編譯原理—第3章 詞法分析及詞法分析程序

1、編譯原理第3章 詞法分析及詞法分析程序計(jì)算機(jī)與軟件學(xué)院 陸克中13.1 設(shè)計(jì)掃描器時(shí)應(yīng)考慮的幾個(gè)問(wèn)題2詞法分析3型語(yǔ)法分析2型單詞的(Class, Value)二元組表示標(biāo)識(shí)符的長(zhǎng)度限制和按“盡可能長(zhǎng)的識(shí)別策略超前搜索與回退：, =, , =程序3-1輸入緩沖注釋與空白的刪除3.2.1 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖3正規(guī)文法標(biāo)識(shí)符字母數(shù)字字母無(wú)符號(hào)數(shù)見(jiàn)課本49頁(yè)3.2.1 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖4狀態(tài)轉(zhuǎn)換圖有向圖結(jié)點(diǎn)表示狀態(tài)一個(gè)初態(tài)，箭頭指示假設(shè)干個(gè)終態(tài)，雙圓圈指示邊表示轉(zhuǎn)移邊上的字符表示轉(zhuǎn)移時(shí)應(yīng)滿足的條件字符串的識(shí)別0132abcdd3.2.1 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖5右線性文法=狀態(tài)轉(zhuǎn)換圖

2、設(shè)G=(VN,VT,P,S)是一右線性文法,令|VN|=K，1) 那么所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個(gè)狀態(tài)。2) VN中的每個(gè)符號(hào)分別表示K個(gè)狀態(tài)，G的開(kāi)始符S為初態(tài)狀態(tài)。3) 終止?fàn)顟B(tài)用F(VN)標(biāo)記。F是新加(狀態(tài))節(jié)點(diǎn)aAaBABAaAFaA消除，重用上述規(guī)則若A為起始符（GA）A3.2.1 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖6右線性文法=狀態(tài)轉(zhuǎn)換圖例 SaA AbX Xc|eY圖3-3 文法G的狀態(tài)轉(zhuǎn)換圖SAXFabcYe3.2.1 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖7狀態(tài)轉(zhuǎn)換圖=右線性文法利用狀態(tài)轉(zhuǎn)換圖識(shí)別符號(hào)串對(duì)應(yīng)推導(dǎo)過(guò)程例 addb的識(shí)別SaAadAaddAaddb文法GS0a1SaA1d1AdA1

3、bAb0cSc0c2ScB，2有出弧2dBd0132abcdd3.2.1 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖8左線性文法=狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一左線性文法,令|VN|=K，1) 那么所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個(gè)狀態(tài)。2) VN中的每個(gè)符號(hào)分別表示K個(gè)狀態(tài)，G的開(kāi)始符S為終止?fàn)顟B(tài)。3) 起始狀態(tài)，用R(VN)標(biāo)記。R是新加(狀態(tài))節(jié)點(diǎn)aA BaBAA 消除，重用上述規(guī)則若A為起始符（GA）AA aRAa3.2.1 由正規(guī)文法構(gòu)造狀態(tài)轉(zhuǎn)換圖9狀態(tài)轉(zhuǎn)換圖=左線性文法利用狀態(tài)轉(zhuǎn)換圖識(shí)別符號(hào)串對(duì)應(yīng)歸約過(guò)程例 addb的識(shí)別addbAddbAdbAbS文法GS1aAa11dAAd31bSAb

4、2cBc32dSBd0132abcdd3.2.2 狀態(tài)轉(zhuǎn)化圖的一種實(shí)現(xiàn)狀態(tài)矩陣法10狀態(tài)矩陣狀態(tài)矩陣Bij=BSi, aj=Sk 。當(dāng)前狀態(tài)，掃視字符，語(yǔ)義動(dòng)作，后續(xù)狀態(tài)。程序3-2。3.2.2 狀態(tài)轉(zhuǎn)化圖的一種實(shí)現(xiàn)狀態(tài)矩陣法11識(shí)別無(wú)符號(hào)數(shù)的狀態(tài)矩陣3.2.2 狀態(tài)轉(zhuǎn)化圖的一種實(shí)現(xiàn)狀態(tài)矩陣法12識(shí)別無(wú)符號(hào)數(shù)的狀態(tài)矩陣語(yǔ)義動(dòng)作中的返回值ICON、FCON分別為整型數(shù)、浮點(diǎn)型數(shù)的值。一般說(shuō)來(lái)，無(wú)符號(hào)數(shù)具有形式：dmdm-1d0.d-1d-nEdd 即dmdm-1d0d-1d-n10dd-n程序3-3。3.3.1 確定的有限自動(dòng)機(jī)13DFA: Deterministic Finite Automa

5、ta，一個(gè)DFA M定義為M=(K, , f, S0, Z)，其中1) K=狀態(tài)i2) =字母表，即輸入字符i3) f: K-K，f為函數(shù)，表示某狀態(tài)接受某個(gè)字母所到達(dá)的狀態(tài)，如：f(p,a)=q, p,qK, a4) S0K，S0為初態(tài)5) ZK，且Z，Z為終態(tài)集合3.3.1 確定的有限自動(dòng)機(jī)14DFA例子右側(cè)的狀態(tài)圖，在數(shù)學(xué)上稱作DFA，其形式化定義為M=(K, , f, S0, Z)K=0, 1, 2, 3=a, b, c, d S0=0Z=2, 3f= 0132abcdd源狀態(tài)輸入目的狀態(tài)0a10c21d11b32d33.3.1 確定的有限自動(dòng)機(jī)15函數(shù)f的推廣定義ff: K*-K，表

6、示某狀態(tài)接受一個(gè)字母串(而不是一個(gè)字母)所到達(dá)的狀態(tài)。f的定義依賴于f的定義， f遞歸定義如下：1) f(p, )=p, if pK，即任意一狀態(tài)p接受(串長(zhǎng)為0)的輸入，狀態(tài)不變。2) f(p, aw)= f( f(p,a), w), if pK, a, w* 3.3.1 確定的有限自動(dòng)機(jī)16函數(shù)f的推廣定義f例 對(duì)于x=adb, x*，那么從狀態(tài)0可以遷移到的狀態(tài)p可以這樣求出：P=f(0, adb) =f(f(0, a), db)=f(1, db)=f(f(1, d), b)=f(1, b)=f(f(1, b), ) =f(3, )=30132abcdd因?yàn)閺某鯌B(tài)0接受輸入字母串a(chǎn)db后

7、，遷移到f(0, adb)=3Z，所以adb為DFA所識(shí)別3.3.1 確定的有限自動(dòng)機(jī)17DFA所識(shí)別的語(yǔ)言令M 為一DFA，我們定義L(M)=x | f(S0, x)Z, x*，L(M)稱為DFA M所識(shí)別的語(yǔ)言。定理：對(duì)于任給的正規(guī)文法G，都存在一個(gè)DFA M，使L(M)=L(G)，反之亦然。3.3.1 確定的有限自動(dòng)機(jī)18DFA關(guān)鍵特征狀態(tài)遷移映射f是入射函數(shù)f(x)f(y) 蘊(yùn)含xy。對(duì)任意狀態(tài)結(jié)點(diǎn)p，其出弧上的字母各不相同且不為。從狀態(tài)圖角度，如出現(xiàn)下述情況的狀態(tài)結(jié)點(diǎn)，那么不是DFA(而是NFA)。PQNaaQ NPQP QWhy?3.3.2 非確定的有限自動(dòng)機(jī)19NFA的形式定義一

8、個(gè)NFA M定義為M=(K, , f, S0, Z)。除f外其余成員與DFA相同，f定義為f: K-(K)，其中(K)為集合K的冪集合，即有|(K)|=2|K|。f 表示某狀態(tài)接受某個(gè)字母所到達(dá)的狀態(tài)集合，如f(p, a)=q, m，p, q, mK, a。3.3.2 非確定的有限自動(dòng)機(jī)20映射f的推廣定義ff: (K)*- (K)，表示某狀態(tài)集合接受一個(gè)字母串而不是一個(gè)字母所到達(dá)的狀態(tài)集合。f遞歸定義如下(依賴于f)：f(p, )=pf(p, a)=f(p1, p2, , aw)=f(f(p1, a)f(p2, a) , w)其中，p, p1, p2K, a, w*p1,p2,. if f(

9、p, a)=p1, p2, if f(p, a)= 屬于什么？3.3.2 非確定的有限自動(dòng)機(jī)21NFA所識(shí)別的語(yǔ)言令N 為一NFA，我們定義L(N)=x | f(S0, x)Z, x*。L(N)稱為NFA N所識(shí)別的語(yǔ)言。有定理：L(N)=L(M)=L(G)，其中N為一NFA，M為一DFA，G為一正規(guī)文法 。3.3.2 非確定的有限自動(dòng)機(jī)22NFA例子 寫(xiě)狀態(tài)遷移表fSABCabaaa,bba源狀態(tài)輸入目的狀態(tài)集合SaA,CAaA,CAbA,BBaABbCCx為什么是NFA？對(duì)每狀態(tài)結(jié)點(diǎn)，按出弧上的字母寫(xiě)出狀態(tài)遷移表，C行可以不填。f : K - (K)3.3.2 非確定的有限自動(dòng)機(jī)23NFA

10、例子 接受串源狀態(tài)輸入目的狀態(tài)集合SaA,CAaA,CAbA,BBaABbCCxf : K - (K)當(dāng)前狀態(tài) 余留輸入 后續(xù)狀態(tài) 選擇狀態(tài) S ababb A,C A or C ?注意，NFA識(shí)別輸入符號(hào)串時(shí)有一個(gè)試探過(guò)程，為了能走到終態(tài)，往往要走許多彎路帶回溯，這影響了NFA的效率。解決方法？3.3.2 非確定的有限自動(dòng)機(jī)24課堂練習(xí)對(duì)于以下圖所示NFA，求f(S, ababb)。SABCabaaa,bba3.3.2 非確定的有限自動(dòng)機(jī)25課堂練習(xí)對(duì)于以下圖所示NFA，求f(S, ababb)。SABCabaaa,bbaSaA,CA,BbA,CaA,BbA,B,CbSaA,CA,BbA,B

11、,Cabbaab3.3.3 NFA與DFA的等價(jià)性26定理3.1 對(duì)于字母表上的任一NFA N，必存在與M等價(jià)的DFA M，使L(N)=L(M) 。有了該定理，為提高NFA識(shí)別字符串的效率提供了tips：將NFA轉(zhuǎn)換為DFA，即NFA確實(shí)定化。根本idea:DFA的f: K-KNFA的f: K-(K)，將其改造為f: (K)-(K)，并證明f是入射函數(shù)，且f接收的串與f接收的串相同。3.3.3 NFA與DFA的等價(jià)性27例子S0S1abba,bS0S0,S1a,babS1b狀態(tài)abS0S0,S1S1S0,S1S0,S1S0,S1S1S0,S1DFA狀態(tài)矩陣3.3.4 帶有動(dòng)作的FA28例子 a

12、 b c S0 S0 S1, S2 S1 S1, S3 S2 S2 S3 S3 bS0S1S3aS2cb3.3.4 帶有動(dòng)作的FA29-閉包-closure(q): 從狀態(tài)q出發(fā)，僅經(jīng)過(guò)假設(shè)干條標(biāo)記為的矢線所能到達(dá)的狀態(tài)所組成的集合約定q也在此集合之中。-closure(S0)=S0, S1, S2, S3-closure(S1)=?-closure(S2)=?-closure(S3)=?3.3.4 帶有動(dòng)作的FA30f的定義f(S, )=-closure(S)f(S, wa)=-closure(f(f(S, w), a)f(q, )通常不等于f(q, )f(S0, )f(S0, )f(S0,

13、 )=?f(S0, a)=?f(S0, ac)=?帶有動(dòng)作的NFA所識(shí)別的語(yǔ)言L(M)=w | f(S0, w)Z圖3-11 識(shí)別某語(yǔ)言單詞的NFA M3.3.5 帶有動(dòng)作的NFA確實(shí)定化子集法311) 令K=-closure(S0)(給出M的初態(tài)q0)2) 對(duì)于K中任一尚未標(biāo)記的狀態(tài)qi=Si1,Si2,Sim，作2.1)標(biāo)記qi2.2)對(duì)于每個(gè)a，置T=f(Si1,Si2,Sim,a)，qj=-closure(T)2.3) 假設(shè)qj不在K中，那么將qj作為一個(gè)未加標(biāo)記的狀態(tài)添加到K中，且把狀態(tài)轉(zhuǎn)移添加到M3)重復(fù)進(jìn)行步驟2)，直到K中不再含有未標(biāo)記的狀態(tài)為止，對(duì)于由此構(gòu)造的K，我們把那些至

14、少含有一個(gè)Z中的元素的qi作為M的終態(tài)。3.3.5 帶有動(dòng)作的NFA確實(shí)定化子集法32例S0S1S3aS2cbb狀態(tài)abcS0,S1,S2,S3S0,S1,S2,S3S1,S3S2,S3S1,S3S1,S3S2,S3S2,S3aS0,S1,S2,S3cS2,S3cS1,S3bb3.3.5 帶有動(dòng)作的NFA確實(shí)定化子集法33課堂練習(xí)S0S1S3aS2cb3.3.5 帶有動(dòng)作的NFA確實(shí)定化子集法34課堂練習(xí)S0S1S3aS2cb狀態(tài)abcS0,S2,S3S1S2,S3S1S3S2,S3S2,S3S3DFA狀態(tài)矩陣S0,S2,S3cS2,S3cS1baS33.3.6 DFA狀態(tài)數(shù)的最小化35可區(qū)分

15、狀態(tài)狀態(tài)A,B被某一輸入串w=a1a2.an所區(qū)分，指1從其中一個(gè)狀態(tài)出發(fā)讀入w，到達(dá)終態(tài)2而從另一個(gè)狀態(tài)出發(fā)進(jìn)入非終態(tài)ABa1a2ana1a23.3.6 DFA狀態(tài)數(shù)的最小化36可區(qū)分狀態(tài)的遞歸定義在一個(gè)DFA中，狀態(tài)A與狀態(tài)B可區(qū)分：1A是終止?fàn)顟B(tài)，B是非終止?fàn)顟B(tài)或 B是終止?fàn)顟B(tài)，A是非終止?fàn)顟B(tài)2對(duì)于字母a，有f(A, a)=C, f(B, a)=D2.1) C與D可區(qū)分2.2) C=NULL且DNULL且D可達(dá)終態(tài) 或 C NULL且C可達(dá)終態(tài)且D=NULL 3.3.6 DFA狀態(tài)數(shù)的最小化37例S0S1S3S2babbaaabS4ab3.3.6 DFA狀態(tài)數(shù)的最小化38例(1)劃分為終

16、態(tài)和非終態(tài):S0,S1,S2,S3=q0,S4=q1 S0,S1,S2與S3可區(qū)分。(2)劃分為:S0,S1,S2=q0,S3=q1,S4=q2 S0,S2與S1可區(qū)分。S0S1S3S2babbaaabS4ababS0q0q0S1q0q0S2q0q0S3q0q1abS0q0q0S1q0q1S2q0q03.3.6 DFA狀態(tài)數(shù)的最小化39例(3)劃分為:S0,S2=q0,S1=q1,S3=q2,S4=q3 S0與S2不再可區(qū)分。(4)合并狀態(tài)S0和S2，可得S0S1S3S2babbaaabS4ababS0q1q0S2q1q0q0q1q2abaabq3abb3.3 有限自動(dòng)機(jī)40小結(jié)一個(gè)DFA M

17、=(K, , f, S0, Z)，函數(shù)f: K-K表示某狀態(tài)Ki接受某字母a后，到達(dá)狀態(tài)Kj的轉(zhuǎn)換。一個(gè)NFA M=(K, , f, S0, Z)，函數(shù)f: K-(K)表示某狀態(tài)Ki接受某字母a后，到達(dá)狀態(tài)集合K1, , Kj的轉(zhuǎn)換。 一個(gè)帶動(dòng)作的NFA M=(K, , f, S0, Z)，函數(shù)f: K-(K)表示某狀態(tài)Ki接受某字母a或空串后，到達(dá)狀態(tài)集合K1, , Kj的轉(zhuǎn)換。3.4 正規(guī)表達(dá)式與正規(guī)集41試描述下述文法所產(chǎn)生的語(yǔ)言的特點(diǎn)GS=(VN=S, , , VT=AZ, az, 09, P, S)，其中P=SS, SS, S, A, , z, 0, , 9上述正規(guī)文法產(chǎn)生的語(yǔ)言的特

18、點(diǎn)是由字母開(kāi)頭，后接0個(gè)或多個(gè)字母和(或)數(shù)字的符號(hào)串。即標(biāo)識(shí)符的定義。3.4.1 正規(guī)表達(dá)式及正規(guī)集的定義42如果使用型如字母(字母|數(shù)字)*的式子來(lái)表示上述符號(hào)串構(gòu)成的集合，那么這樣的式子就稱為正規(guī)表達(dá)式，相應(yīng)的符號(hào)串集合那么稱為該表達(dá)式對(duì)應(yīng)的正規(guī)集。正規(guī)式正規(guī)集空集a, aa(r)(s)LrLs(r)|(s)LrLs(r)*Lr*(r)+=(r)(r)*)Lr+3.4.1 正規(guī)表達(dá)式及正規(guī)集的定義43算符優(yōu)先級(jí)與正規(guī)式化簡(jiǎn)算符優(yōu)先級(jí)從高到低依次為 (), *, +, , |。 如(r)(s)*)|(r)，可化簡(jiǎn)為rs*|r，又因?yàn)檫B接符通?？墒÷圆粚?xiě)，再化簡(jiǎn)為rs*|r。3.4.1 正規(guī)

19、表達(dá)式及正規(guī)集的定義44正規(guī)式與正規(guī)集的例子=a, b3.4.1 正規(guī)表達(dá)式及正規(guī)集的定義45正規(guī)式與正規(guī)集的多對(duì)一關(guān)系給定一個(gè)正規(guī)式，它唯一確定一個(gè)正規(guī)集；反之不然。即一個(gè)正規(guī)集可由多個(gè)不同的正規(guī)式表示。我們稱兩個(gè)正規(guī)式等價(jià)，當(dāng)且僅當(dāng)它們所描述的正規(guī)集相同。例如a|b與b|a, (a|b)*與 (b|a)*等等。3.4.1 正規(guī)表達(dá)式及正規(guī)集的定義46正規(guī)式的根本等價(jià)公理A1. r|s=s|rA2. r|r=rA3. r|=rA4. (r|s)|t=r|(s|t)A5. (rs)t=r(st)A6. r(s|t)=rs|rtA7. (s|t)r=sr|trA8. r=r= A9. r=r=r

20、A10. r*=(|r)*=|rr*3.4.1 正規(guī)表達(dá)式及正規(guī)集的定義47例 寫(xiě)出一個(gè)正規(guī)式，它能匹配C語(yǔ)言的標(biāo)識(shí)符。(a|b|z|A|B|Z|_)(0|1|9|a|b|z|A|B|Z|_)*3.4.1 正規(guī)表達(dá)式及正規(guī)集的定義48課程練習(xí)寫(xiě)出一個(gè)正規(guī)式，它能匹配C語(yǔ)言的整數(shù)。例如：0X89aB、+0123、-45等等3.4.1 正規(guī)表達(dá)式及正規(guī)集的定義49課程練習(xí)寫(xiě)出一個(gè)正規(guī)式，它能匹配C語(yǔ)言的整數(shù)。例如：0X89aB、+0123、-45等等 (+|-|)(0(x|X)(0|1|9|a|b|f|A|B|F)+)|(0(0|1|7)*)|(1|9)(0|1|9)*)3.4.2 由正規(guī)文法構(gòu)造

21、相應(yīng)的正規(guī)式50右線性文法使用正規(guī)式描述下述右線性文法產(chǎn)生的語(yǔ)言S aS | bS aS | bS | c (或S (a|b)S | c )S abS | c 總結(jié)出規(guī)律:S S | 對(duì)應(yīng)的正規(guī)式是 *3.4.2 由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式51左線性文法使用正規(guī)式描述下述左線性文法產(chǎn)生的語(yǔ)言S Sa | bS Sa | Sb | c (或S S(a|b) | c )S Sab | c 總結(jié)出規(guī)律:S S | 對(duì)應(yīng)的正規(guī)式是 *3.4.2 由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式52如果將“|用 “+替換，“ 用 “=替換，那么可以將產(chǎn)生式轉(zhuǎn)換為方程的形式，于是對(duì)上述兩個(gè)規(guī)律，我們得到論斷：論斷3.1 方程X

22、=X+對(duì)應(yīng)SS|，有解X=*論斷3.2 方程X=X+對(duì)應(yīng)SS|，有解X=*3.4.2 由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式53文法GS:SaS | bA | bAaS我們可以將所有產(chǎn)生式的運(yùn)算符“ | 用 “ + 替換，“ 用 “ = 替換，再以我們習(xí)摜的線性方程組求解方法來(lái)求解S對(duì)應(yīng)的正規(guī)式。3.4.2 由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式54例SaS|bA|b AaSSaS|baS|b S=(a+ba)S+b S=(a+ba)*b(a|ba)*bSaA AbA|aB|b BaAAbA|aaA|b A=(b+aa)A+b A=(b+aa)*b S=a(b+aa)*b a(b|aa)*bSbS|aA AaA|bB

23、 BaA|bC|b CbS|aABaA|bS|b BS|b AaA|bS|bb AS|bb SbS|aS|abbS=(a+b)S+abb(a|b)*abb3.4.2 由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式55課堂練習(xí)構(gòu)造以下文法的正規(guī)式：(1) SaS|bA|c AbS(2) SaA AaA|bB|c BcS3.4.2 由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式56課堂練習(xí)構(gòu)造以下文法的正規(guī)式：(1) SaS|bA|c AbSSaS|bbS|c S=(a+bb)S+c(a|bb)*c(2) SaA AaA|bB|c BcSAaA|bcS|c AaA|bcaA|c A=(a+bca)A+cA=(a+bca)*c S=a(a

24、+bca)*ca(a|bca)*c3.4.3 由正規(guī)式構(gòu)造FAThompson法57根據(jù)正規(guī)式所含運(yùn)算符個(gè)數(shù)n遞歸給出n=0r=r=r=aS0SfS0S0Sfa3.4.3 由正規(guī)式構(gòu)造FAThompson法58根據(jù)正規(guī)式所含運(yùn)算符個(gè)數(shù)n遞歸給出n1r= r1|r2r1S01r2S02S0Sf不再是初態(tài)不再是終態(tài)Sf1Sf23.4.3 由正規(guī)式構(gòu)造FAThompson法59h根據(jù)正規(guī)式所含運(yùn)算符個(gè)數(shù)n遞歸給出n1r=r1r2r1S01Sf1r2S02Sf23.4.3 由正規(guī)式構(gòu)造FAThompson法60根據(jù)正規(guī)式所含運(yùn)算符個(gè)數(shù)n遞歸給出n1r=r1*r1S01Sf1S0Sf3.4.3 由正規(guī)式

25、構(gòu)造FAThompson法61例(1) a(b|aa)*b(2) (0*|1)(1*0)*abba11003.4.3 由正規(guī)式構(gòu)造FAThompson法62課堂練習(xí)構(gòu)造以下正規(guī)式的FA：(1) ab|c*(2) (b|aa|ac|aaa|aac)*3.4.3 由正規(guī)式構(gòu)造FAThompson法63課堂練習(xí)構(gòu)造以下正規(guī)式的FA：(1) ab|c*(2) (b|aa|ac|aaa|aac)*cabbccaaaa3.5 詞法分析程序的實(shí)現(xiàn)64構(gòu)造詞法分析程序的兩種途徑根據(jù)對(duì)語(yǔ)言中各類單詞的某種描述或定義，用手工的方式構(gòu)造詞法分析程序詞法分析程序的自動(dòng)生成3.5.1 詞法分析程序的編寫(xiě)65表3-4 一

26、個(gè)語(yǔ)言的單詞符號(hào)及其分類碼圖3-22 識(shí)別表3-4所列語(yǔ)言單詞的DFA及相關(guān)的主義過(guò)程程序3-4 根據(jù)圖3-22編寫(xiě)的掃描器3.5.3 詞法分析程序的自動(dòng)生成66LEX源文件結(jié)構(gòu)定義局部%識(shí)別規(guī)那么局部%輔助函數(shù)局部3.5.3 詞法分析程序的自動(dòng)生成67LEX源程序的定義局部宏digit0-9alphaa-zA-Zalnum(alpha|digit)idalphaalnum*其中，0-9=0|1|2|93.5.3 詞法分析程序的自動(dòng)生成68LEX源程序的定義局部宏%#include #include extern int flag#define Zhao 1#define Qian 2int

27、ERROR=-1char c%digit0-9alphaa-zA-Zalnum(alpha|digit)%3.5.3 詞法分析程序的自動(dòng)生成69LEX源程序的識(shí)別規(guī)那么局部R1A1R2A2RmAm3.5.3 詞法分析程序的自動(dòng)生成70LEX源程序的識(shí)別規(guī)那么局部%#define FCON 1#define ICON 2%D 0-9%D+return ICON;(D+|D*.D+|D+.D*)(eE+-?D+)?return FCON;3.5.3 詞法分析程序的自動(dòng)生成71輔助函數(shù)局部一個(gè)語(yǔ)言掃描器的LEX源程序%#include #include #include #define BEGIN 1#define END 2#define