第03章有限自動(dòng)機(jī)和詞法分析主要內(nèi)容：詞法分析過(guò)程涉及的幾個(gè)問(wèn)題詞法分析器的生成技術(shù)有限自動(dòng)機(jī)正則表達(dá)式3.1詞法分析有關(guān)詞法分析器的幾個(gè)問(wèn)題和處理方法：

1)詞法分析器的功能、分類

2)單詞的分類、Token表示

3)字符串、保留字的處理

4)空格符、制表符和換行符

5)復(fù)合型符號(hào)

6)括號(hào)類匹配預(yù)檢

7)詞法錯(cuò)誤校正

8) 詞法分析獨(dú)立化的意義3.1.1詞法分析器的功能詞法分析器功能：讀源程序的字符序列，逐個(gè)拼出單詞,并構(gòu)造相應(yīng)的內(nèi)部表示TOKEN。同時(shí)檢查源程序中的詞法錯(cuò)誤。引入Token的原因：編譯程序總是用某種程序語(yǔ)言書(shū)寫的程序，語(yǔ)言的操作對(duì)象只能是該語(yǔ)言規(guī)定的各種數(shù)據(jù)。而編譯程序的操作對(duì)象是程序中的各種語(yǔ)法單位，因此，必須把它們表示成某種數(shù)據(jù)結(jié)構(gòu)形式。

詞法分析器的兩種形式:CharList

獨(dú)立詞法分析器語(yǔ)法分析TokenList

附屬詞法分析器語(yǔ)法分析callTokenCharList3.1.2單詞的內(nèi)部表示Token定義：Token表示最小的語(yǔ)義單位--單詞的信息。即：?jiǎn)卧~內(nèi)部表示的數(shù)據(jù)結(jié)構(gòu)形式。單詞不是程序設(shè)計(jì)語(yǔ)言中的語(yǔ)法概念，是編譯程序中引進(jìn)的一個(gè)概念。是最小的語(yǔ)義單位，不能分割。Token中需要記錄有關(guān)單詞的信息：?jiǎn)卧~的類別碼(Token.class)：標(biāo)識(shí)單詞的種類---詞法信息單詞的特征屬性（Token.seman，標(biāo)識(shí)符名，符號(hào)表地址等）：---語(yǔ)義信息Token設(shè)計(jì)示例程序表示ASC∏Token.classToken.semanIf9666019666Then478656E602478656E6Begin26567696E60326567696E6End56E6460456E646+B205B2(820682單詞的分類:標(biāo)識(shí)符：字母打頭的字母/數(shù)字串整常數(shù)：數(shù)字打頭的數(shù)字串實(shí)常數(shù)：整數(shù).整數(shù)保留字：begin，end，var，read，write，integer，real符號(hào)：+，*，(，)，:，:=，;控制：(換行符）字符串：

標(biāo)識(shí)符的語(yǔ)義信息的表示方法有兩種：

a字符數(shù)組法：字符串空間中的地址被表示為對(duì)偶地址（head,leng），如下圖所示：

b指針數(shù)組法：字符串空間中的地址用指針表示，如下圖所示：(4,3)(2,2)

x1z12名表“x1”“z12”heighteofageeofx1eofyeof0123保留字的處理：兩種識(shí)別保留字的方法：

1.建立保留字表：順序、散列、散列＋順序2.拼寫的同時(shí)進(jìn)行判斷：自動(dòng)機(jī)

例：假設(shè)保留字只有begin和end的情況見(jiàn)下圖：beginndeNot(e)Not(g)Not(i)Not(n)Not(b,e)Not(n)Not(d)該方法的優(yōu)點(diǎn)：速度快；缺點(diǎn)：自動(dòng)機(jī)太大。

運(yùn)算符的處理：

1.不區(qū)分，統(tǒng)一成一類

2.區(qū)分，每個(gè)運(yùn)算符為一類

空格符和制表符以及換行符的處理

1.無(wú)用的空格符和制表符要?jiǎng)h掉；2.字符串內(nèi)的空格不能刪；

實(shí)現(xiàn)方法：進(jìn)入字符串時(shí)令標(biāo)志變量StringFlag為true,退出時(shí)為false。3.換行符不能刪，用于錯(cuò)誤定位。括號(hào)類配對(duì)預(yù)檢括號(hào)類：

如：begin…end,if…then,[],{},()，record…end處理方法：

對(duì)每類括號(hào)設(shè)置一個(gè)計(jì)數(shù)器（初值=0）每當(dāng)遇到開(kāi)括號(hào)，則計(jì)數(shù)器加1每當(dāng)遇到閉括號(hào)時(shí)，計(jì)數(shù)器減1詞法分析結(jié)束時(shí)，如果計(jì)數(shù)器0，則表明括號(hào)不匹配，報(bào)錯(cuò)。向前看多個(gè)字符的處理對(duì)于復(fù)合型特殊符，如“:=”的處理方法：讀到“:”時(shí)不能判斷是否為冒號(hào)，必須讀下一字符。下圖是對(duì)枚舉類型如10..100和實(shí)數(shù)如3.14的處理：D.D..DD注：對(duì)于pascal和Ada等語(yǔ)言至多向前看兩個(gè)字符即名。例：錯(cuò)誤單詞12.3e+q的處理方法：每當(dāng)一個(gè)字符被掃描時(shí)，緩存并判斷已掃部分的類型或無(wú)效（Invalid），當(dāng)不能進(jìn)一步掃描時(shí)，進(jìn)行倒退工作，返回最后Invalid前面的類型，如右表中返回RealConstant。BufferedTokenTokenFlag1IntegerConstant12IntegerConstant12.Invalid12.3RealConstant12.3eInvalid12.3e+Invalid詞法錯(cuò)誤校正詞法錯(cuò)誤種類：語(yǔ)言不允許的符號(hào)：#括號(hào)類配對(duì)錯(cuò)誤：?jiǎn)卧~的后繼符錯(cuò)（偶爾）：詞法錯(cuò)誤校正：

a刪除已被讀過(guò)的字符，并重新掃描未被讀過(guò)的字符

b刪除已讀過(guò)的第一個(gè)字符，重新掃描它的后繼部分的字符。校正后的標(biāo)示詞法分析獨(dú)立化的意義1）使語(yǔ)法分析器和語(yǔ)義分析器的算法更加清晰和簡(jiǎn)練；

2）便于利用自動(dòng)機(jī)、正則表達(dá)式等理論技術(shù)加以自動(dòng)化；3）更加有利于構(gòu)造出高效的詞法分析器；

4）有利于編譯器的移植。3.2有限自動(dòng)機(jī)描述程序設(shè)計(jì)語(yǔ)言中的單詞的識(shí)別過(guò)程。主要內(nèi)容：確定有限自動(dòng)機(jī)DFA的定義確定有限自動(dòng)機(jī)DFA的實(shí)現(xiàn)非確定有限自動(dòng)機(jī)NFANFA到DFA的轉(zhuǎn)換DFA的化簡(jiǎn)一個(gè)確定的有窮自動(dòng)機(jī)（DFA）M是一個(gè)五元組：M=（SS，Σ，，S0，Z）其中1.SS是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2.Σ是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱Σ為輸入符號(hào)字母表；3.是轉(zhuǎn)換函數(shù)，是在SS×Σ→SS上的映射，即:如（ki，a）=kj，（ki∈SS，kj∈SS）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)；4.S0∈SS,是唯一的一個(gè)初態(tài)；5.ZSS,是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。3.2.1確定的有窮自動(dòng)機(jī)（DFA）定義:DFA的兩種表示方式

狀態(tài)轉(zhuǎn)換圖：

結(jié)點(diǎn)表示狀態(tài)，轉(zhuǎn)換邊表示轉(zhuǎn)換函數(shù)，邊的箭頭方向指向轉(zhuǎn)換函數(shù)中定義的轉(zhuǎn)換方向。標(biāo)識(shí)出初始狀態(tài)和終止?fàn)顟B(tài)。

狀態(tài)轉(zhuǎn)換表：可用二維數(shù)組描述。標(biāo)識(shí)出初始狀態(tài)和終止?fàn)顟B(tài)。Trans（SI，a）＝SJDFA例1：DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QDFA的狀態(tài)圖表示:f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bbDFA的矩陣表示:f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QabSUVUQVVUQQQQ字符狀態(tài)0100DFA例2：整常數(shù)集：如16,135,258實(shí)常數(shù)集：如16.135,258.5S0dS1d0d.2d3dd1DFA例3：第二位為2的整數(shù)集(包括一位)：如x2ad標(biāo)識(shí)符集：如x,ab3_7d2dL-L,DL,D∑*上的符號(hào)串t被M接受定義1：對(duì)于∑*中的任何字符串t，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的標(biāo)記符連接成的字符串等于t，則稱t可為DFAM所接受，若M的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則空字可為M所接受（識(shí)別）。定義2：若t∑*，f(S，t)=P，其中S為DFA

M的開(kāi)始狀態(tài)，PZ，Z為終態(tài)集。

則稱t為DFAM所接受（識(shí)別）?！?上的符號(hào)串t（我們將輸入符號(hào)串t表示成t1tx的形式，其中t1∈∑，tx∈∑*）在M上在DFAM上運(yùn)行的定義為：

f（Q,t1tx）=f（f（Q,t1）,tx）

其中Q∈K擴(kuò)充轉(zhuǎn)換函數(shù)f，是K×Σ*→K上的映射，且：

f（Q，）=Q例：證明t=baab被如下的DFA所接受。DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba,bb證明：

f（S，baab）

=f（f（S，b），aab）

=f（V，aab）

=f（f（V，a），ab）

=f（U，ab）

=f（f（U，a），b）

=f（Q，b）

=QQ屬于終態(tài)。得證。3.2.2確定有窮自動(dòng)機(jī)的實(shí)現(xiàn)DFA的確定性的特點(diǎn)：初始狀態(tài)唯一。轉(zhuǎn)換函數(shù)f:SSSS是一個(gè)單值函數(shù)，也就是說(shuō)，對(duì)任何狀態(tài)SSS,和輸入符號(hào)a,f(S,a)唯一地確定了下一個(gè)狀態(tài)。即轉(zhuǎn)換函數(shù)至多確定一個(gè)狀態(tài)。沒(méi)有空邊。即沒(méi)有輸入為（）用DFA構(gòu)造詞法分析器的方法1狀態(tài)轉(zhuǎn)換表的形式：（數(shù)組T存放轉(zhuǎn)換函數(shù)）

1.State(當(dāng)前狀態(tài)):=初始狀態(tài) 2.讀一個(gè)字符CurrentChar 3.如果CurrentCharEof并且

T(State,CurrentChar)error

則State:=新的狀態(tài)T(State,Current)，

轉(zhuǎn)到第2步工作。4.如果CurrentChar=Eof并且State=終止?fàn)顟B(tài)，則接受當(dāng)前字符串，程序結(jié)束。否則報(bào)錯(cuò)

特點(diǎn)：程序短小，但占用存儲(chǔ)空間多代碼如下：intScanner(charinput[]){S:=S0;in=0;ch=input[in++];While(TT(S,ch)undef&&chEof){S=TT(S,ch);ch=input[in++];};If(ch=EOF&&SFinalStates)return(1)elsereturn(0)}用DFA構(gòu)造詞法分析器的方法2狀態(tài)轉(zhuǎn)換圖的形式：

每個(gè)狀態(tài):對(duì)應(yīng)一個(gè)帶標(biāo)號(hào)的case語(yǔ)句；

轉(zhuǎn)向邊:轉(zhuǎn)向?qū)?yīng)狀態(tài)。特點(diǎn)：程序長(zhǎng)，但占用存儲(chǔ)空間少。

Switch(satate){case

Si:Switch(ch){Casea：satate:=Sj;break;Caseb：satate:=Sk;break;other:Error;}}ajbki3.2.3非確定有限自動(dòng)機(jī)NFA定義：一個(gè)非確定有限自動(dòng)機(jī)(NFA)A是一個(gè)五元組A=(,SS,S0,f,TS).其中:

是字母表;SS:

是狀態(tài)集;

S0:

是初始狀態(tài)集;f:

是轉(zhuǎn)換函數(shù)，但不要求是單值的;

f:SS(∪{})SSTS:

是終止?fàn)顟B(tài)集.NFA的特點(diǎn)：一個(gè)狀態(tài)的不同輸出邊可標(biāo)有相同的符號(hào)。允許有多個(gè)開(kāi)始狀態(tài)。允許輸出邊上標(biāo)有空串符號(hào)。<<=:=:aa*3.2.4NFA到DFA的轉(zhuǎn)換定理：對(duì)于每一個(gè)非確定自動(dòng)機(jī)A,存在一個(gè)確定自動(dòng)機(jī)A’,使得L(A)=L(A’).相關(guān)算法：

1）-閉包：close_（SS）

2）nextstate函數(shù)：nextstate（SS,a)

一、close_（SS）計(jì)算方法：1.首先令close_:=SS;2.若在close_中存在狀態(tài)S，

1）它末被處理過(guò)；

2）它存在指向close_之外狀態(tài)S1的邊；則令：close_:=close_

{S1};3.重復(fù)2，直到close_不再變化為止。-閉包的例子：

iakdjcmbdci,j,k,mba則：close_(i)={i,j,k,m}二、nextstate的定義a0a2b1c則：nextstate(0,a)={1,2}定義：nextstate(SS,a)={s1|S(a)S1,SSS}如下圖所示：三、NFA到DFA的轉(zhuǎn)換過(guò)程:1.初始化：AllStateSet={SS0},UnHandledStateSet={SS0}；2.判斷結(jié)束：若UnHandledStateSet空，則結(jié)束，否則轉(zhuǎn)下；3.從UnHandledStateSet選擇一個(gè)狀態(tài)SS；4.對(duì)于每個(gè)符號(hào)a，做下面工作：

1）求SS1=Close(nextstate(SS,a)；

2）若SS1空，則TT[SS,a]=空；

3）否則，檢查AllStateSet中有無(wú)SS1，

①若無(wú)，則把SS1追加到UnHandledStateSet和AllStateSet中，并令TT[SS,a]=SS1；②否則，令TT[SS,a]=SS1。5.從UnHandledStateSet中刪除狀態(tài)SS，并轉(zhuǎn)向步驟2。NFA到DFA的轉(zhuǎn)換例子：a03a2a1bacbabc[0][1,2][1,2][3*][1,3*][2][3*][2][1,3*][2][1,3*][2][2][3*]31,201,32acaaaba|cb*3.2.5DFA的極小化

狀態(tài)等價(jià):對(duì)DFA中的兩個(gè)狀態(tài)S1和S2，如果將它們看作是初始狀態(tài)，所接受的符號(hào)串相同，則定義S1和S2是等價(jià)的。

方法:

1)狀態(tài)合并法;

2)狀態(tài)分離法.

狀態(tài)合并法（狀態(tài)吸收方法）

尋找等價(jià)狀態(tài)S1和S2，如果S2為初始狀態(tài)，則S1和S2對(duì)調(diào)，S2的出現(xiàn)修改為S1，刪除狀態(tài)S2。

狀態(tài)分離法

1）初始化為兩個(gè)不等價(jià)狀態(tài)集組：非終止?fàn)顟B(tài)組和終止?fàn)顟B(tài)組；2）對(duì)每組中的某個(gè)狀態(tài)分離出與之不等價(jià)的狀態(tài)組，直至所有狀態(tài)組內(nèi)部狀態(tài)都等價(jià)為止。狀態(tài)合并法的例子：134a|dc2b134ac2b67c5bd化簡(jiǎn)為：實(shí)現(xiàn)方法：134ac2b67c5bd第一步：畫(huà)FA的狀態(tài)轉(zhuǎn)換表；abcd10252334*4*5667*7*第二步：4吸收7；abcd10252334*4*5664*#####第三步：3吸收6；abcd10252334*4*53##########第四步：2吸收5；abcd10222334*4*###############第五步：畫(huà)出FA。abcd10222334*4*134a|dc2b3.3正則表達(dá)式主要內(nèi)容：基本概念正則表達(dá)式定義及一些性質(zhì)擴(kuò)充的正則表達(dá)式及程序設(shè)計(jì)語(yǔ)言中單詞的定義正則表達(dá)式的局限性。正則定義

3.3.1正則符號(hào)串集的相關(guān)基本概念

字母表：非空有限集，其元素稱為符號(hào)或字母.

符號(hào)串：符號(hào)的有限序列，也稱為字?；虮硎究沾?空串集{}不同于空集。

符號(hào)串長(zhǎng)度：符號(hào)串中字符的個(gè)數(shù)||,||=0,|ab|=2

符號(hào)串連接：和都是符號(hào)串，則為符號(hào)串的連接特別有：==

符號(hào)串集的乘積：A和B是符號(hào)串的集合，則稱

AB={|A，B}特別有：A=A=A，其中表示空集。符號(hào)串的方冪：設(shè)A是符號(hào)串的集合，則稱Ai為符號(hào)串集A的方冪，其中i是非負(fù)整數(shù)。

A0={}

A1=A,A2=AA

AK=AA......A(k個(gè))

符號(hào)串集合的星閉包：

A*=A0A1A2A3......3.3.2正則表達(dá)式的定義若用RE表示上的正則表達(dá)式，用L(RE)表示RE所包含的字符串集合

，則：■

是正則表達(dá)式，即：RE

，其中L()={}?！?/p>

是正則表達(dá)式，即：RE

，其中L()={}?！鯽是正則表達(dá)式，即：aRE

，其中L(a)={a}。■

A和B是正則表達(dá)式，即ARE，BRE，則有：

(A)

RE

，L((A)) =L(A)

A|B

RE

，L(A|B) =L(A)L(B)

A·B

RE

，L(A·B) =L(A)L(B)

A*

RE

，L(A*) =L(A)*

例1：={a,b}.正則表達(dá)式eab*2.a(a|b)*

L(e)上所有以a為首后跟任意多個(gè)（包括0個(gè)）b的字符串集上所有以a為首的字符串集若D={0,1,2,，9}.則：RealC=D+.D+擴(kuò)充的正則表達(dá)式：

A的正閉包：A+=A1A2A3......，即一次或多次重復(fù)任何符號(hào):“…”在字母表中任何符號(hào).符號(hào)范圍:[0--9]{0,1,2,3,4,5,6,7,8,9}

[a--zA--Z]

[a—z]|[A--Z]

[abc]

(a|b|c)不在給定范圍內(nèi)的符號(hào):~(a|b|c)或[^

a]可選:

（＋|-）?

//可選+或-或不選正則表達(dá)式的性質(zhì)：

A|B=B|A 選擇的可交換性

A|(B|C)=(A|B)C 選擇的可結(jié)合性

A(BC)=(AB)C 連接的可結(jié)合性

A(B|C)=AB|AC 連接的可分配性(A|B)C=AC|BC連接的可分配性

A**=A*

冪的等價(jià)性例2：整常數(shù)集：IntC=D+實(shí)常數(shù)集：RealC=D+.D+標(biāo)識(shí)符集：IDE=L(L|D|_)*3.3.3正則表達(dá)式的局限性：1）正則表達(dá)式不能用于描述配對(duì)或嵌套的結(jié)構(gòu)；例：A={anban|n>0}2）正則表達(dá)式不能用于描述重復(fù)串。例：{wcw|w是a和b的串}無(wú)法用正則表達(dá)式表示（保證兩邊w是相同的）。原因是：正則表達(dá)式中沒(méi)有變量。3.3.4正則定義正則定義：Mr//本質(zhì)是為正則表達(dá)式命名功能：為較長(zhǎng)的正則表達(dá)式提供一個(gè)簡(jiǎn)化了的名字

如：E=((a+bc)+(a+bc)(a+bc))(ab+c)+(ab+c)

其中a+bc出現(xiàn)了三次，ab+c出現(xiàn)了二次，如用正則定義可表示如下：

E1

a+bcE2

ab+cE

(E1+E1E1)E2+E2例3：標(biāo)識(shí)符：

letter[a-zA-Z] digit[0-9] identifierletter(letter|digit)*數(shù)字：

整數(shù)Int[1-9]Digit*|0實(shí)數(shù)realInt.Int特殊符號(hào)：運(yùn)算符ch+|-|…3.3.5正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)定理：對(duì)任一確定有限自動(dòng)機(jī)A，存在一正則表達(dá)式e,使得L(A)=L(e),反之亦然。關(guān)系圖：DFA正則表達(dá)式NFA正則表達(dá)式到FA的轉(zhuǎn)換規(guī)則：13ab12a|b13b*123ab12ab123bR=(a|b)*abbxiy(a|b)*abbxjyεabbiεa|bxjyεabbiεab例：為R=(a|b)*abb構(gòu)造NFA，使得L(N)=L(R)。xjyεbεiabklab123ab12ab12313ab12a|b13ab*

cabcDFA到正則表達(dá)式的轉(zhuǎn)換規(guī)則：例：03124a,baaa,ba,bbb求正規(guī)式R03124a,baaa,ba,bbbxyεεε024a|baaa|ba|bbbxyεεε024a|baaa|ba|bbbxyεεε0a|baa(a|b)*bb(a|b)*xyε0a|baa(a|b)*bb(a|b)*xyε0a|bxyεaa(a|b)*|bb(a|b)*xy(a|b)*(aa|bb)(a|b)*R=(a|b)*(aa|bb)(a|b)*習(xí)題作業(yè)

S={a,b,c}，試給出S一個(gè)不包含連續(xù)兩個(gè)b的所有符號(hào)串集合的正則定義。

S={a,b,c}，敘述正則式((b|c)*a(b|c)*a)*(b|c)*

描述的符號(hào)串。S＝{0,1}，敘述正則式(00|11)

((01|10)(00|11)

(01|10)

)

(00|11)

描述的符號(hào)串。給出能被5整除的二進(jìn)制數(shù)表示形式的正則定義。*3.4詞法分析器的構(gòu)造詞法分析器（Scanner）輸入流詞法描述（正則表達(dá)式）NFADFATokenListerror詞法分析器的構(gòu)造方法用DFA人工構(gòu)造：1.確定詞法分析器的接口，即確定詞法分析器是作為語(yǔ)法分析的一個(gè)子程序還是作為獨(dú)立一遍。2.確定單詞分類和Token結(jié)構(gòu)。3.根據(jù)2步，構(gòu)造每一類單詞的描述：正則表達(dá)式NFADFA。4.根據(jù)3步設(shè)計(jì)算法實(shí)現(xiàn)DFA。利用工具自動(dòng)生成：ScanGen、Lex3.4.1用DFA人工構(gòu)造詞法分析器單詞的TOKEN輸出表如下：

identifier($id,Name)

number($int,Numb)

+($plus,‘‘);($semi,‘‘):=($assi,‘‘):($colon,‘‘)<=($le,‘‘)<($lt,‘‘)單詞的一個(gè)DFA15L023L|DD4869710D+;:<==otherother狀態(tài)(0)的代碼：Ls0:string:=‘‘;ReadChar(CurrentChar);caseCurrentCharof‘A’..’Z’|‘a(chǎn)’..’z’:gotoLs1;‘0’..’9’:gotoLs2;’+’:gotoLs3;’;’:gotoLs4;’:’:gotoLs5;’<’:gotoLs8;end;狀態(tài)(1)的代碼：Ls1:beginstring:=Append(string,CurrentChar);ReadChar(CurrentChar);caseCurrentCharof‘A’..’Z’|‘a(chǎn)’..’z’|‘0’..’9’:gotoLs1;other:beginBACK;return($id,string)endendend;狀態(tài)(2)的代碼：Ls2:beginstring:=Append(string,CurrentChar);ReadChar(CurrentChar);caseCurrentCharof‘0’..’9’:gotoLs2;other:beginBACK;return($int,string)endendend;狀態(tài)(3)(4)(5)(6)的代碼：Ls3:return($plus,’’);Ls4:return($semi,’’);Ls5:beginReadChar(CurrentChar);caseCurrentCharof‘=’:gotoLs6;other:gotoLs7;endend;Ls6:return($assi,’’);狀態(tài)(7)(8)(9)(10)的代碼：Ls7:beginBACK;return($plus,’’)endLs8:beginReadChar(CurrentChar);caseCurrentCharof‘=’:gotoLs9;other:gotoLs10;endend;Ls9:return($le,’’);Ls10:beginBACK;return($lt,’’)end3.4.2詞法分析器的生成器Lex功能：依據(jù)語(yǔ)言的正則表達(dá)式，自動(dòng)生成該語(yǔ)言的詞法分析程序。執(zhí)行過(guò)程：正則表達(dá)式文件Lex.lLex詞法分析器lexyy.cC編譯器a.out輸入流Token序列Lex的常規(guī)表達(dá)式（1）字符

含義

A-Z,0-9,a-z構(gòu)成了部分模式的字符和數(shù)字。.匹配任意字符，除了

\n。-用來(lái)指定范圍。例如：A-Z指從

A到

Z之間的所有字符。[]一個(gè)字符集合。匹配括號(hào)內(nèi)的

任意

字符。如果第一個(gè)字符是

^那么它表示否定模式。例如：[abC]匹配

a,b和

C中的任何一個(gè)。

*匹配

0個(gè)或者多個(gè)上述的模式。

+匹配

1個(gè)或者多個(gè)上述模式。

?匹配

0個(gè)或1個(gè)上述模式。

$作為模式的最后一個(gè)字符匹配一行的結(jié)尾。Lex的常規(guī)表達(dá)式（2）字符

含義

{}指出一個(gè)模式可能出現(xiàn)的次數(shù)。

例如：A{1,3}表示

A可能出現(xiàn)1次或3次。\用來(lái)轉(zhuǎn)義元字符。同樣用來(lái)覆蓋字符在此表中定義的特殊意義，只取字符的本意。^否定。|表達(dá)式間的邏輯或。"<一些符號(hào)>"

字符的字面含義。元字符具有。/向前匹配。如果在匹配的模版中的“/”后跟有后續(xù)表達(dá)式，只匹配模版中“/”前面的部分。如：如果輸入

A01，那么在模版

A0/1中的

A0是匹配的。()將一系列常規(guī)表達(dá)式分組。常規(guī)表達(dá)式舉例常規(guī)表達(dá)式

含義

joke[rs]匹配

jokes或

joker。A{1,2}shis+匹配

AAshis,Ashis,Ashiss,Ashisss。(A[b-e])+匹配在

A出現(xiàn)位置后跟隨的從

b到

e的所有字符中的

1個(gè)或多個(gè)。標(biāo)記聲明舉例標(biāo)記

相關(guān)表達(dá)式

含義

數(shù)字(number)([0-9])+1個(gè)或多個(gè)數(shù)字字符(chars)[A-Za-z]任意字符空格(blank)""一個(gè)空格字(word)(chars)+1個(gè)或多個(gè)

chars

變量(variable)(字符)+(數(shù)字)*(字符)*(數(shù)字)*Lex輸入文件的格式輸入文件格式：{declarations}

%%{rules}

%%{auxiliaryprocedures}%{聲明變量,常量%}正則定義p{action}Lex編程

Lex編程可以分為三步：以Lex可以理解的格式指定模式相關(guān)的動(dòng)作。在這一文件上運(yùn)行Lex，生成掃描器的C代碼。編譯和鏈接C代碼，生成可執(zhí)行的掃描器。Lex的輸入格式

一個(gè)Lex程序分為三個(gè)段：第一段：是C和Lex的全局聲明第二段：包括模式（C代碼）第三段：是補(bǔ)充的C函數(shù)。這些段以%%來(lái)分界。（1）C和Lex的全局聲明這一段中我們可以增加C變量聲明。

%{intwordCount=0;/*保存統(tǒng)計(jì)出來(lái)的字?jǐn)?shù)

*/

%}

chars[A-Za-z]numbers([0-9])+delim[""\n\t]whitespace{delim}+

words{chars}+

%%兩個(gè)百分號(hào)標(biāo)記指出了Lex程序中這一段的結(jié)束和三段中第二段的開(kāi)始。

（2）Lex的模式匹配規(guī)則{words}{wordCount++;/*increasethewordcountbyone*/}{whitespace}{/*donothing*/}{numbers}{/*onemaywanttoaddsomeprocessinghere*/}%%

（3）C代碼

Lex編程的第三段，也就是最后一段覆蓋了C的函數(shù)聲明（有時(shí)是主函數(shù)）。Lex有一套可供使用的函數(shù)和變量。其中之一就是yywrap。一般來(lái)說(shuō)，yywrap()的定義如下例。

voidmain(){yylex();/*starttheanalysis*/printf("Noofwords:%d\n",wordCount);}intyywrap(){return1;}例：識(shí)別PL/0單詞的LEX程序%{#include<stdio.h>#include“code.h”#include“symbol.h”#include“y.tab.h”externintlevel;int