chap詞法分析實用

會計學(xué)1chap詞法分析實用詞法：描述語言的單詞符號的文法。

語言的單詞符號種類很多，因此需要用不同的詞法來描述他們。

例如描述某一語言標(biāo)識符的文法也稱為詞法。3.1詞法分析程序的任務(wù)功能及實現(xiàn)方案思考：詞法是哪類文法？正規(guī)文法第1頁/共92頁

定義：編譯程序中完成詞法分析任務(wù)的程序段，又稱詞法分析器

詞法分析器任務(wù)：對源程序進(jìn)行從左到右的順序掃描，按照詞法規(guī)則從中識別出一個個具有獨立意義的單詞符號并把源程序轉(zhuǎn)換為等價的內(nèi)部表示形式（屬性字流）。第2頁/共92頁詞法分析程序的功能過濾掉源程序中的注釋和空白；進(jìn)行預(yù)編譯工作(對宏進(jìn)行展開等工作)；符號表操作和錯誤處理等。識別出單詞（內(nèi)部表示）；記錄讀入字符的行號，以便發(fā)現(xiàn)錯誤后能報告出錯位置；第3頁/共92頁While(i!=j)doif(i＞j)i＝i-j;//求i,j的差值詞法分析器‘while’，‘(’，‘i’，‘!=’，‘j’，‘)’，‘do’，‘if’，‘(’，‘i’，‘＞’，‘j’,‘)’，'i','=’,'i',’-’,'j',‘;'第4頁/共92頁實現(xiàn)方案（編譯程序中實現(xiàn)方式）：基本上有兩種1.詞法分析單獨作為一遍2.詞法分析程序作為單獨的子程序S.P.(字符串)詞法分析S.P.(符號串)語法分析第一遍第二遍單詞串優(yōu)點:結(jié)構(gòu)清晰、各遍功能單一缺點：生成中間文件，效率低S.P.(字符串)詞法分析程序語法分析程序取單詞單詞第5頁/共92頁S.P.(字符串)詞法分析程序輸入緩沖區(qū)的處理？第6頁/共92頁輸入緩沖區(qū)的處理？顯然，無論緩沖區(qū)設(shè)定為多大，都不能保證單詞不會被它的邊界打斷，若有標(biāo)識符TEST123，可能在緩沖區(qū)中成為：………….TES在這種情況下，即使讀到緩沖區(qū)的最后一個字符，但仍不能找到該單詞的右邊界，這時，若從外存上再讀一部分源程序進(jìn)入緩沖區(qū)，則會將沒有處理過的字符(TES)沖掉。兩個半?yún)^(qū)互補使用為此，我們可將緩沖區(qū)分成相等的兩個區(qū)域：第7頁/共92頁掃描緩沖區(qū)一分為二，互補使用。搜索指針從單詞起點開始搜索，如果遇到半?yún)^(qū)域的邊界，但尚未到達(dá)單詞的終點時，則可將后續(xù)的輸入字符裝入該緩沖區(qū)的另一半。單詞起點

搜索指針第8頁/共92頁IfFatendoffirsthalf{reloadsecondhalf;F++;}ElseifFatendofsecondhalf{ reloadfirsthalf;moveFtobeginningoffirsthalf}ElseF++;輸入緩沖區(qū)兩個半?yún)^(qū)互補功能的實現(xiàn)算法第9頁/共92頁3.2單詞的種類及詞法分析程序的輸出形式單詞是語言中具有獨立意義的最小語法單位.單詞的種類

1.保留字：while、class、for、do2.標(biāo)識符：a、m_a3.常數(shù)：無符號數(shù)、布爾常數(shù)、字符串常數(shù)等

4.運算符：+、-、*

5.界限符：逗號，分號，括號和引號種類的劃分是根據(jù)編譯的目標(biāo)和方便設(shè)定的第10頁/共92頁詞法分析程序的輸出形式-----單詞的內(nèi)部形式常用的單詞內(nèi)部形式：1、按單詞種類分類2、保留字和分界符采用一符一類3、標(biāo)識符和常數(shù)的單詞屬性值為符號表入口指針（標(biāo)識符、常數(shù)相關(guān)屬性很多）單詞類別單詞值第11頁/共92頁單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點數(shù)布爾常數(shù)字符串常數(shù)保留字分界符類別編碼1234567單詞值符號表入口指針整數(shù)值數(shù)值0或1內(nèi)部字符串保留字或內(nèi)部編碼分界符或內(nèi)部編碼1、按單詞種類分類第12頁/共92頁2、保留字和分界符采用一符一類單詞名稱標(biāo)識符無符號常數(shù)(整)無符號浮點數(shù)布爾常數(shù)字符串常數(shù)BEGINENDFORDO………:+*,(類別編碼123456789…….20212223…….單詞值符號表入口指針整數(shù)值數(shù)值0或1內(nèi)部字符串----…..-----第13頁/共92頁單詞的描述方法--正規(guī)式（正規(guī)表達(dá)式）正規(guī)式與正規(guī)集合正規(guī)式與有限自動機(jī)正規(guī)式與正規(guī)文法第14頁/共92頁例：語言L={a}{a,b}*({ε}∪({.,_}{a,b}{a,b}*))正規(guī)表達(dá)式(RegularExpression，RE，或稱為正則表達(dá)式)是一種用來描述正則語言的更緊湊的表示方法。

r=a(a|b)*(ε|(.|_)(a|b)(a|b)*)第15頁/共92頁正規(guī)表達(dá)式的遞歸定義正規(guī)表達(dá)式可以由較小的正規(guī)表達(dá)式按照特定規(guī)則遞歸地構(gòu)建。每個正則表達(dá)式r定義（表示）一個語言，記為L(r)。這個語言也是根據(jù)r的子表達(dá)式所表示的語言遞歸定義的。第16頁/共92頁字母表上的正規(guī)表達(dá)式遞歸定義如下:1.和都是上的正規(guī)表達(dá)式,它們所表示的語言分別為:{}和{};2.任何a,a是上的正規(guī)表達(dá)式,它所表示的語言為:{a};3.假定r和s是上的正規(guī)表達(dá)式,它們所表示的語言分別記為L(r)

和L(s),那么r|s,rs,

r*也都是上的正規(guī)表達(dá)式,它們所表示的語言分別為L(r)L(s)、L(r)L(s)、L(r)*r|sL(r)L(s)rsL(r)L(s)r*L(r)*一個由正規(guī)表達(dá)式表示的語言稱為正規(guī)集或正規(guī)語言。第17頁/共92頁規(guī)定“*”，“連接”，“”運算左結(jié)合，優(yōu)先級由高到低

簡化正規(guī)式(a)((b)*(c))等價于ab*c例：=A,B,…,Z,a,b,…,z,0,1,…,9

正規(guī)式1：AB...Zab...z

語言1：L(A)∪L(B)…∪L(Z)∪L(a)∪L(b)...∪L(z)=A,B,…,Z,a,b,…,z

正規(guī)式2：

01...9語言2：L(0)∪L(1)∪...∪L(9)=

0,1,…,9第18頁/共92頁例=a,b

(a)ab

L(a)∪L(b)=a,b

(b)(ab)(ab)

(L(a)∪L(b))(L(a)∪L(b))=aa,ab,ba,bb

(c)a*

(L(a))*=,a,aa,aaa,aaaa,…

(d)(ab)*

(L(a)∪L(b))*={,a,b,aa,ab,ba,bb,aaa,...

(e)aa*b符號串a(chǎn)和包括零個或多于零個a后跟一個b構(gòu)成的所有符號串第19頁/共92頁思考：C++語言的標(biāo)識符用正規(guī)式如何表示?C++語言的標(biāo)識符的語法如下：

C++語言的標(biāo)識符是由字母或下劃線開頭的字母、下劃線和數(shù)字構(gòu)成的符號串。第20頁/共92頁正規(guī)式：(AB...Zab...z_)((AB...Zab...z)_(01..9))*語言：A,B,…,Z,a,b,…,z,_(A,B,…,Z,a,b,…,z,_,0,1,…,9)*C++語言的標(biāo)識符第21頁/共92頁課堂練習(xí)1用正規(guī)式描述C語言的無符號整數(shù)。思考：無符號整數(shù)可以分為十進(jìn)制整數(shù)、八進(jìn)制整數(shù)和十六進(jìn)制整數(shù)。1.十進(jìn)制整數(shù)的正規(guī)式？2.八進(jìn)制整數(shù)的正規(guī)式？3.十六進(jìn)制整數(shù)的正規(guī)式？第22頁/共92頁參考答案1.十進(jìn)制整數(shù)的RE(1|...|9)(0|...|9)*|02.八進(jìn)制整數(shù)的RE

0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*3.十六進(jìn)制整數(shù)的RE0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*第23頁/共92頁正規(guī)表達(dá)式的代數(shù)性質(zhì)第24頁/共92頁正則定義正則定義是具有如下形式的定義序列：d1→r1d2→r2…dn→rn給一些RE命名，并在之后的RE中像使用字母表中的符號一樣使用這些名字其中：1.每個di都是一個新符號，它們都不在字母表Σ中，而且各不相同2.每個ri是字母表Σ∪{d1,d2,…,di-1}上的正則表達(dá)式第25頁/共92頁用正則定義重寫C語言標(biāo)識符digit→0|1|2|…|9letter_→A|B|…|Z|a|b|…|z|_id→letter_(letter_|digit)*第26頁/共92頁課堂練習(xí)2

（整型或浮點型）無符號數(shù)的正規(guī)表示。

例如：

33.153.15E+43.15E-43.15E43E-4第27頁/共92頁

（整型或浮點型）無符號數(shù)的正則定義

digit→0|1|2|…|9digits→digitdigit*optionalFraction→.digits|εoptionalExponent→(E(+|-|ε)digits)|εnumber→digitsoptionalFractionoptionalExponent第28頁/共92頁描述單詞符號的結(jié)構(gòu)，是進(jìn)行詞法分析程序設(shè)計的第一步,

在表示的基礎(chǔ)上如何做進(jìn)一步的工作？第29頁/共92頁正規(guī)式與有限自動機(jī)定理:設(shè)r是上一個正規(guī)表達(dá)式，則存在一個 FAm接受L(r)。反之亦然。

正規(guī)文法，正規(guī)表達(dá)式和有限自動機(jī)三者之間在表示語言的意義下是等價的。

字母表上的一個正規(guī)語言，既可以由某一個正規(guī)文法產(chǎn)生，也可以由某一個正規(guī)表達(dá)式所表示，還可以由某一個有限自動機(jī)識別。第30頁/共92頁關(guān)系圖：正規(guī)文法NFA正規(guī)表達(dá)式DFA最小化第31頁/共92頁對于上任一正規(guī)表達(dá)式r

，一定能構(gòu)造一個NFAm

，使得L(r)=L(m)。首先把轉(zhuǎn)換圖的概念拓廣，每條弧上可以用一個正規(guī)式標(biāo)記，對NFAm構(gòu)造一個廣義的轉(zhuǎn)換圖。其中只有開始狀態(tài)S和終止?fàn)顟B(tài)Z，連接S和Z的有向弧上是正規(guī)式R，然后按照下面的替換規(guī)則對正規(guī)式不斷進(jìn)行分解，不斷加入狀態(tài)結(jié)點和箭弧，直到轉(zhuǎn)換圖上的所有弧標(biāo)記都是上的元素或為止。轉(zhuǎn)換法實現(xiàn)正規(guī)式與有限自動機(jī)的轉(zhuǎn)換第32頁/共92頁acacacr1r2r1r2r1r2*r3替換規(guī)則代之以代之以代之以abcacabcr1r2r2r2r1r1r3從正規(guī)式到有限自動機(jī)第33頁/共92頁

設(shè)={x,y},上的正規(guī)式R=xy*(xy|yx)x*，構(gòu)造一個NFAM，使L(M)=L(R).xy*(xy|yx)x*SZstartxSZ1y*2xy|yx3x*xSZ13xy42yyx5xxSZ13x62yy7xyx45第34頁/共92頁對于上任一NFAm，能構(gòu)造上一個正規(guī)表達(dá)式r，使得L(r)=L(m)。首先，在m的轉(zhuǎn)換圖上加進(jìn)S,Z兩個結(jié)點。從S用弧連接到m的所有初態(tài)結(jié)點，從m的所有終結(jié)（接受）結(jié)點用弧連接到Z，從而構(gòu)成一個新的NFAm’，L(m)=L(m’)。反復(fù)使用下面的替換規(guī)則逐步消去NFAm’中的狀態(tài)結(jié)點和弧，直至剩下S,Z為止。在消去結(jié)點的過程中，逐步用正規(guī)式標(biāo)記弧。從正規(guī)式到有限自動機(jī)從有限自動機(jī)到正規(guī)式轉(zhuǎn)換法第35頁/共92頁abcacacacabcacr1r2r2r2r1r1r3r1r2r1r2r1r2*r3替換規(guī)則代之以代之以代之以從有限自動機(jī)到正規(guī)式第36頁/共92頁

NFAM如圖所示，在＝{x,y}上構(gòu)造一個正規(guī)式R，使L(M)=L(R).41start23x,yyxyyxx4123x,yyxyyxxZS第37頁/共92頁41x,yxy*yyx*xZS41x,yxy*y|yx*xZS4(x|y)*(xy*y|yx*x)ZSZ(x|y)*(xy*y|yx*x)S第38頁/共92頁例:M:03214starta,ba,ba,bbbaa解:(1)加xyx03412yεεεaa,ba,ba,babb第39頁/共92頁(2)消除M’中的所有結(jié)點a|bx024yεεεaabba|ba|bx0yaa(a|b)*bb(a|b)*a|bε解:(1)加xyx03412yεεεaa,ba,ba,babbxy(a|b)*(aa|bb)(a|b)*第40頁/共92頁關(guān)系圖：NFA正規(guī)表達(dá)式DFA最小化第41頁/共92頁構(gòu)造與正規(guī)表達(dá)式(0|1)*1(0|1)等價的DFA。第42頁/共92頁第43頁/共92頁練習(xí)：識別無符號數(shù)的DFAdigit→0|1|2|…|9digits→digitdigit*optionalFraction→.digits|εoptionalExponent→(E(+|-|ε)digits)|εnumber→digitsoptionalFractionoptionalExponent第44頁/共92頁第45頁/共92頁關(guān)系圖：正規(guī)文法NFA正規(guī)表達(dá)式DFA最小化第46頁/共92頁正規(guī)文法與有限自動機(jī)（FA）的等價性

如果對于某個正規(guī)文法G和某個有限自動機(jī)M，有L(G)=L(M)（正規(guī)文法G所產(chǎn)生的語言和某個有限自動機(jī)所識別的語言相同）,則稱G和M是等價的。第47頁/共92頁定理對每一個右線性正規(guī)文法或左線性正規(guī)文法G，都存在一個FAM，使

L(M)=L(G)定理對于每一個FAM，都存在一個右線性正規(guī)文法G和一個左線性正規(guī)文法G’，使 L(M)=L(G)=L(G’)。第48頁/共92頁有限自動機(jī)與正規(guī)文法（1）有限自動機(jī)正規(guī)文法（右線性）1.對轉(zhuǎn)換函數(shù)f(A,t)=B，可寫成一個產(chǎn)生式:A→tB算法:2.對可接受狀態(tài)Z,增加一個產(chǎn)生式:Z→ε3.有限自動機(jī)的初態(tài)對應(yīng)于文法的開始符號,

有限自動機(jī)的字母表為文法的終結(jié)符號集.ABt第49頁/共92頁例:給出如圖FA等價的正規(guī)文法GABCDstartaaabbbbG=（{A，B，C，D}，{a，b}，A，P）其中P:AaBAbDBbCCaACbDCεDaBDbDDε→→→→→→→→→第50頁/共92頁（2）正規(guī)文法（右線性）有限自動機(jī)M算法:1.字母表與G的終結(jié)符號相同.2.為G中的每個非終結(jié)符生成M的一個狀態(tài),G的開始符號S

是開始狀態(tài)S;3.增加一個新狀態(tài)Z,作為NFA的終態(tài)4.對G中的形如A→tB,其中t為終結(jié)符或ε,A和B為非終結(jié)符的產(chǎn)生式,構(gòu)造M的一個轉(zhuǎn)換函數(shù)f(A,t)=B5.對G中的形如A→t的產(chǎn)生式,構(gòu)造M的一個轉(zhuǎn)換函數(shù)

f(A,t)=Z第51頁/共92頁例:求與文法G[S]等價的NFAG[S]:S→aA|bB|εA→aB|bAB→aS|bA|εSZABstartaaabbbεε求得：第52頁/共92頁

課后思考有限自動機(jī)正規(guī)文法（左線性）？第53頁/共92頁正規(guī)文法正規(guī)式（自學(xué)）利用以下轉(zhuǎn)換規(guī)則,直至只剩下一個開始符號定義的產(chǎn)生式,并且產(chǎn)生式的右部不含非終結(jié)符.規(guī)則規(guī)則1規(guī)則2規(guī)則3文法產(chǎn)生式正則式A→xB,B→yA→xA|yA→x,A→yA=xyA=x*yA=x|y補充第54頁/共92頁例:有文法G[s]S→aA|aA→aA|dA|c于是:S=aA|aA=(aA|dA)|cA=(a|d)A|c由規(guī)則二:A=(a|d)*c

代入:S=a(a|d)*c|a第55頁/共92頁正規(guī)式正規(guī)文法算法:1)對任何正規(guī)式r,選擇一個非終結(jié)符S作為識別符號.

并構(gòu)造產(chǎn)生式S→r2)若x,y是正規(guī)式,

A→xy重寫為A→xBB→yA→x*yA→xAA→y其中B為新的非終結(jié)符,B∈VN

例:將a(a|d)*轉(zhuǎn)換成等價的正規(guī)文法解:1)S→a(a|d)*

2)S→aAA→(a|d)*S→aAA→(a|d)AA→εS→aAA→aA|dAA→ε第56頁/共92頁正規(guī)文法NFA正規(guī)表達(dá)式DFA最小化FA和正規(guī)表達(dá)式、正規(guī)文法相互等價，能夠相互轉(zhuǎn)換.第57頁/共92頁確定字母表

寫出正規(guī)表達(dá)式

NFADFA

最小化第58頁/共92頁3.3詞法分析程序的設(shè)計與實現(xiàn)詞法規(guī)則正規(guī)表達(dá)式狀態(tài)轉(zhuǎn)換圖（最小DFA）1.構(gòu)造識別單詞的狀態(tài)轉(zhuǎn)換圖(1)對程序語言的單詞按種類分別構(gòu)造對應(yīng)的狀態(tài)轉(zhuǎn)換圖.(2)對各類轉(zhuǎn)換圖合并，構(gòu)成一個能識別語言所有單詞的狀態(tài)轉(zhuǎn)換圖.2.編程實現(xiàn)狀態(tài)轉(zhuǎn)換圖第59頁/共92頁3.3.1詞法及其狀態(tài)轉(zhuǎn)換圖例1假定語言X的字母表∑={A-Z,a-z,0-9,;,=}單詞符號定義如下：

1、標(biāo)識符：字母打頭的字母數(shù)字串

2、無符號整數(shù)：無符號數(shù)字串

3、分界符：；

4、運算符：=第60頁/共92頁標(biāo)識符出口S1非字母數(shù)字字母字母、數(shù)字無符號整數(shù)出口S1非數(shù)字?jǐn)?shù)字?jǐn)?shù)字分界符出口S；運算符出口S=第61頁/共92頁標(biāo)識符無符號整數(shù)分界符S1非字母數(shù)字*字母字母、數(shù)字2非數(shù)字*數(shù)字?jǐn)?shù)字；出口出錯其他讀字符返回S運算符=第62頁/共92頁=80;0134256eniL字母字母字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字==；；0124563Line=80;1,‘Line’3,‘=’2,‘80’4,‘;’數(shù)字?jǐn)?shù)字字母字母11==0003;;1輸入輸出第63頁/共92頁3.3.2狀態(tài)轉(zhuǎn)換圖的實現(xiàn)——構(gòu)造詞法分析程序標(biāo)識符無符號整數(shù)分界符運算符<1，標(biāo)識符名字><2，整數(shù)值><3，“;”><4，“=”>例1假定語言X的字母表∑={A-Z,a-z,0-9,;,=}單詞符號定義如下：

1、標(biāo)識符：字母打頭的字母數(shù)字串

2、無符號整數(shù)：無符號數(shù)字串

3、分界符：；

4、運算符：=第64頁/共92頁標(biāo)識符S1非字母數(shù)字字母字母、數(shù)字無符號整數(shù)S1非數(shù)字?jǐn)?shù)字?jǐn)?shù)字分界符出口S；運算符S=出口出口出口第65頁/共92頁標(biāo)識符出口S1非字母數(shù)字字母字母、數(shù)字If(ISLETTER){WHILE(ISLETTERORISDIGIT)DO{

當(dāng)前字符放入一臨時字符數(shù)組；

GETNEXTCHAR

；//從緩沖區(qū)取下一字符

};

UNGETCH；//回退一字符

OUTPUT(1，標(biāo)識符名字)；}；=80;eniLLine=80;==;;第66頁/共92頁無符號整數(shù)出口S1非數(shù)字?jǐn)?shù)字?jǐn)?shù)字If(ISDIGIT){WHILEISDIGITDO{

當(dāng)前字符放入一臨時字符數(shù)組；

GETNEXTCHAR

；//從緩沖區(qū)取下一字符

};

UNGETCH；//回退一字符

OUTPUT(2,整數(shù))；};=80;eniLLine=80;==;;第67頁/共92頁分界符出口S；If(CH==‘;’)OUTPUT(3,“;”)；If(CH==‘=’)OUTPUT(4,“=”)；運算符S=出口第68頁/共92頁標(biāo)識符無符號整數(shù)分界符S1字母字母、數(shù)字2數(shù)字?jǐn)?shù)字；出口出錯其他讀字符返回S運算符=第69頁/共92頁例1程序語言的詞法分析程序GETNEXTCHAR()

；SWITCH(CHCODE);{CASE1:{WHILE(ISLETTERORISDIGIT)DO{

SAVE();//當(dāng)前字符放入一臨時字符數(shù)組；

GETNEXTCHAR()

；//從緩沖區(qū)取下一字符

};

UNGETCH；//回退一字符

OUTPUT(1，標(biāo)識符名字)；

}；BREAK;CASE2:{WHILEISDIGITDO{

SAVE();//當(dāng)前字符放入一臨時字符數(shù)組；

GETNEXTCHAR

；//從緩沖區(qū)取下一字符

};

UNGETCH；//回退一字符

OUTPUT(2,整數(shù))；

};BREAK;第70頁/共92頁CASE3:OUTPUT(3,“;”)；BREAK;CASE4:OUTPUT(4,“=”)；BREAK;DEFAULT:Error();};標(biāo)識符無符號整數(shù)分界符S1字母字母、數(shù)字2數(shù)字?jǐn)?shù)字；出口出錯其他讀字符返回S運算符=第71頁/共92頁采用面向?qū)ο蟮姆椒ㄔO(shè)計詞法分析器標(biāo)識符無符號整數(shù)分界符S1字母字母、數(shù)字2數(shù)字?jǐn)?shù)字；出口出錯其他讀字符返回S運算符=第72頁/共92頁詞法規(guī)則正規(guī)表達(dá)式狀態(tài)轉(zhuǎn)換圖（最小DFA）合并狀態(tài)轉(zhuǎn)換圖編程實現(xiàn)狀態(tài)轉(zhuǎn)換圖合并狀態(tài)轉(zhuǎn)換圖文法、正規(guī)表達(dá)式、有限自動機(jī)有限自動機(jī)(最小化？)第73頁/共92頁識別各進(jìn)制無符號整數(shù)的DFADEC→(1|...|9)(0|...|9)*|0OCT→0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*HEX→0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*詞法規(guī)則正規(guī)表達(dá)式1.第74頁/共92頁第75頁/共92頁第76頁/共92頁詞法分析階段的錯誤處理詞法分析階段可檢測錯誤的類型單詞拼寫錯誤非法字符詞法錯誤檢測如果當(dāng)前狀態(tài)與當(dāng)前輸入符號在轉(zhuǎn)換表對應(yīng)項中的信息為空，而當(dāng)前狀態(tài)又不是終止?fàn)顟B(tài)，則調(diào)用錯誤處理程序第77頁/共92頁錯誤處理查找已掃描字符串中最后一個對應(yīng)于某終態(tài)的字符如果找到了，將該字符與其前面的字符識別成一個單詞。然后將輸入指針退回到該字符，掃描器重新回到初始狀態(tài)，繼續(xù)識別下一個單詞如果沒找到，則確定出錯，采用錯誤恢復(fù)策略第78頁/共92頁錯誤恢復(fù)策略最簡單的錯誤恢復(fù)策略：

“恐慌模式(panicmode)”恢復(fù)從剩余的輸入中不斷刪除字符，直到詞法分析器能夠在剩余輸入的開頭發(fā)現(xiàn)一個正確的字符為止第79頁/共92頁3.4

詞法分析程序的自動生成器—LEX（LEXICALAnalyzerGenerator）LEX是1972年在貝爾實驗室的UNIX上首先實現(xiàn)FLEX是1984年GNU工程推出，是LEX的擴(kuò)充，并兼容LEX原理：LEX源程序S.P.字符串LEX可執(zhí)行L詞法分析程序LS.P.單詞字符串詞法分析程序LC編譯器可執(zhí)行L第80頁/共92頁3.4.1LEX源程序一個LEX源程序主要由三個部分組成:1.輔助定義式(說明部分)2.識別規(guī)則。3.用戶子程序各部分之間用%%隔開，同時%%在最左邊.第81頁/共92頁一、輔助定義式是如下形式的LEX語句：D1R1

D2R2∶∶DnRn

其中：R1,R2，……，Rn

為正則表達(dá)式。

D1,D2，……，Dn為正則表達(dá)式名字，稱簡名字

第82頁/共92頁例：C++標(biāo)識符

letterA|B|¨¨¨|Z|_

digit0|1|¨¨¨|9

idenletter(letter|digit)*第83頁/共92頁二、識別規(guī)則：是一串如下形式的LEX語句：

P1{A1}P2{A2}∶∶Pm{Am}Pi：定義在Σ∪{D1,D2,¨¨Dn}上的正規(guī)表達(dá)式，也稱詞形。{Ai}：Ai為語句序列，它指出，在識別出詞形為Pi的單詞以后，詞法分析器所應(yīng)作的動作。其基本動作是返回單詞的類別編碼和其屬性。第84頁/共92頁三、用戶子程序定義模式動作需要的函數(shù)或包括主函數(shù)在這三部分中一和三為可選項，但是二是必須的

除輔助定義之外定義的部分必須用符號%{和%}括起來，其內(nèi)容為：所對應(yīng)語言的庫文件外部變量外部函數(shù)和函數(shù)原型第85頁/共92頁下面是識別某語言單詞符號的LEX源程序：例：LEX源程