詞法分析課件

第三章詞法分析詞法分析的基本概念正規(guī)式自動機(jī)和狀態(tài)圖詞法分析程序的設(shè)計(jì)1第三章詞法分析詞法分析的基本概念1學(xué)習(xí)目標(biāo):掌握：詞法分析程序的構(gòu)造，正規(guī)式和正規(guī)文法到有窮自動機(jī)的轉(zhuǎn)換，NFA到DFA的轉(zhuǎn)換、DFA的化簡理解：正規(guī)文法、正規(guī)式、DFA的概念、NFA的概念了解：詞法分析程序的自動構(gòu)造工具2學(xué)習(xí)目標(biāo):2詞法分析程序詞法分析是編譯過程中的一個(gè)階段，在語法分析前進(jìn)行，也可以和語法分析結(jié)合在一起作為一遍。輸入：源程序字符串輸出：單詞符號（最基本的語法單位）3詞法分析程序詞法分析是編譯過程中的一個(gè)階段，在語法分析前進(jìn)行詞法分析程序的功能詞法分析程序主要執(zhí)行以下功能：讀入源程序字符串，識別開具有獨(dú)立含義的最小語法單位——單詞（符號）；把單詞變換成長度統(tǒng)一的且為定長的屬性字；其他功能：濾掉空格，跳過注釋、換行符某些預(yù)加工處理4詞法分析程序的功能詞法分析程序主要執(zhí)行以下功能：4詞法分析程序的實(shí)現(xiàn)方式相對獨(dú)立方式：把詞法分析程序作為語法分析程序的一個(gè)獨(dú)立子程序。語法分析程序需要新符號時(shí)調(diào)用這個(gè)子程序。完全獨(dú)立方式：詞法分析程序作為單獨(dú)一趟來實(shí)現(xiàn)。詞法分析程序讀入整個(gè)源程序，它的輸出作為語法分析程序的輸入。5詞法分析程序的實(shí)現(xiàn)方式相對獨(dú)立方式：把詞法分析程序作為語法分相對獨(dú)立方式當(dāng)采用遞歸下降分析等技術(shù)實(shí)現(xiàn)一趟編譯程序時(shí)常采用這種方式。源程序詞法分析程序語法分析程序Tokengettoken….6相對獨(dú)立方式當(dāng)采用遞歸下降分析等技術(shù)實(shí)現(xiàn)一趟編譯程序時(shí)常采用完全獨(dú)立方式采用詞法分析工作完全獨(dú)立的原因：簡化設(shè)計(jì)，降低語法分析的復(fù)雜性提高編譯效率增加編譯系統(tǒng)的可移植性源程序詞法分析程序語法分析程序?qū)傩宰中蛄小?7完全獨(dú)立方式采用詞法分析工作完全獨(dú)立的原因：源程序詞法分析程源程序的輸入在內(nèi)存開辟緩沖區(qū)，將程序文本放進(jìn)該緩沖區(qū)預(yù)處理：刪除無用字符等詞法分析程序?qū)彌_區(qū)掃描時(shí)，設(shè)置兩個(gè)指示器，一個(gè)指向當(dāng)前正在識別的單詞的開始位置，稱為起始指針；另一個(gè)用于向前搜索，以尋找單詞的終點(diǎn)，稱為掃描指針。起始指針?biāo)阉髦羔?源程序的輸入在內(nèi)存開辟緩沖區(qū)，將程序文本放進(jìn)該緩沖區(qū)起始指針掃描緩沖區(qū)的大小應(yīng)當(dāng)保證單詞符號不被緩沖區(qū)的邊界打斷使用循環(huán)鏈表實(shí)現(xiàn)規(guī)定單詞符號的大小不超過整個(gè)鏈表的容量9掃描緩沖區(qū)的大小9超前搜索詞法分析程序在讀取單詞時(shí)，為了判斷是否已讀入整個(gè)單詞的全部字符，常采取向前多讀取字符并通過讀取的字符來判別，即所謂超前搜索技術(shù)。10超前搜索詞法分析程序在讀取單詞時(shí)，為了判斷是否已讀入整個(gè)單詞單詞符號的構(gòu)成規(guī)則

——標(biāo)識符012字母(a-z)字母或數(shù)字(a-z0-9)其它*此時(shí)，超前搜索了一個(gè)字符11單詞符號的構(gòu)成規(guī)則

——標(biāo)識符012字母(a-z)字母或數(shù)字詞法分析程序輸出單詞的形式詞法分析程序輸出的單詞符號通常用二元式表示：（單詞類別，單詞自身的值）單詞類別：表示單詞種類，常用整數(shù)編碼，它是語法分析需要的單詞自身的值：是編譯中其他階段所需要的信息如果一個(gè)種別只含一個(gè)單詞符號，那么該單詞符號的類別編碼就完全代表它自身的值。把單詞符號存儲在符號表中。不同種類的單詞符號可能具有不同類型的屬性。可以用不同種類的符號表實(shí)現(xiàn)。如果一個(gè)種別含有多個(gè)單詞符號，那么還應(yīng)給出該單詞符號的自身值：標(biāo)識符自身值是標(biāo)識符自身的字符串；常數(shù)自身值是常數(shù)的二進(jìn)制數(shù)值。12詞法分析程序輸出單詞的形式詞法分析程序輸出的單詞符號通常用二語言的單詞符號單詞符號是程序語言的基本語法單位，一般分為下面5種：關(guān)鍵字（基本字）：（個(gè)數(shù)確定，可全體編為一類，也可一字一類)標(biāo)識符：（個(gè)數(shù)不確定，作為一類）常數(shù)：各種類型的常數(shù)。(個(gè)數(shù)不確定，按類型分類)運(yùn)算符：如+、-、*、/、<等。(個(gè)數(shù)確定，一符一類)界符：如，、；、（、）、:等。(個(gè)數(shù)確定,一符一類)注意：一種語言的單詞如何分類、怎樣編碼，主要取決于技術(shù)上的方便。13語言的單詞符號單詞符號是程序語言的基本語法單位，一般分為下面舉例例如：程序段if(a>1)b=10;假定基本字、運(yùn)算符、界符都是一符一種。

它所輸出的單詞符號是：(2,)基本字if(29,)左括號((10,’a’)標(biāo)識符a(23,)大于號>(11,’1’的二進(jìn)制)常數(shù)1

(30,)

右括號)(10,’b’)標(biāo)識符b(17,)賦值號=(11,’10’的二進(jìn)制)常數(shù)10(26,)分號；14舉例例如：程序段它所輸出的單詞符號是：14正規(guī)式和有限自動機(jī)1515正規(guī)表達(dá)式和有限自動機(jī)

——學(xué)習(xí)目的和內(nèi)容用正則表達(dá)式描述詞法規(guī)則構(gòu)造正則表達(dá)式等價(jià)的NFA構(gòu)造NFA等價(jià)的DFA化簡DFA根據(jù)DFA編寫程序，實(shí)現(xiàn)詞法分析器提示：本部分內(nèi)容占學(xué)習(xí)內(nèi)容的25%，考核內(nèi)容的1/2與本部分相關(guān)16正規(guī)表達(dá)式和有限自動機(jī)

——學(xué)習(xí)目的和內(nèi)容用正則表達(dá)式描述詞單詞的描述工具作用:描述單詞的構(gòu)成規(guī)則,基于這類描述工具建立詞法分析技術(shù),進(jìn)而實(shí)現(xiàn)詞法分析程序的自動構(gòu)造.工具有:正規(guī)文法 正規(guī)式(RegularExpression)17單詞的描述工具作用:描述單詞的構(gòu)成規(guī)則,基于這類描述工具建正規(guī)文法

多數(shù)程序設(shè)計(jì)語言單詞的語法都能用正規(guī)文法(3型文法)描述正規(guī)文法回顧 文法的任一產(chǎn)生式α→β的形式都為A→aB或A→a，其中A，B∈VN，a∈VT。 正規(guī)文法描述的是VT*上的正規(guī)集18正規(guī)文法 多數(shù)程序設(shè)計(jì)語言單詞的語法都能用正規(guī)文法(3型文法例如: 用l表示a~z中的任一英文字母，d表示0~9中任一數(shù)字描述標(biāo)識符的正規(guī)文法為 <標(biāo)識符>→l｜l<字母數(shù)字> <字母數(shù)字>→l｜d｜l<字母數(shù)字>｜d<字母數(shù)字>描述無符號整數(shù)的正規(guī)文法 <無符號整數(shù)>→d｜d<無符號整數(shù)>19例如:19為什么要引進(jìn)正則表達(dá)式？對于字母表∑，我們感興趣的是它的一些特殊字集－正規(guī)集。正規(guī)集是字母表Σ上的符合一定規(guī)則的符號串構(gòu)成的集合正則表達(dá)式是一種適合描述符號的表示法，可由它定義正規(guī)集。20為什么要引進(jìn)正則表達(dá)式？對于字母表∑，我們感興趣的是它的一些正規(guī)式(regularexpression)定義（正規(guī)式和它所表示的正規(guī)集）：設(shè)字母標(biāo)為

1和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和；2任何a，a是上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；3假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1),e1e2,e1e2,e1

也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))

。（遞歸）4僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。21正規(guī)式(regularexpression)定義（正規(guī)式和(e1),e1e2,e1e2,e1

L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))

。

其中的“”讀為“或”（也有使用“+”代替“”的）；“

”讀為“連接”；“

”讀為“閉包”（即，任意有限次的自重復(fù)連接）。在不致混淆時(shí)，括號可省去，但規(guī)定算符的優(yōu)先順序?yàn)椤?/p>

”、“

”、“”。連接符“

”一般可省略不寫?！?/p>

”、“

”和“”都是左結(jié)合的。22(e1),e1e2,e1e2,e1正則集正則集定義:正則表達(dá)式e的值是字母表上的正則集，記作|e|||=||={}|a|={a}|(e)|=|e||e1e2|=|e1||e2|={xy|x|e1|且y|e2|}

|e1|e2|=|e1||e2|={x|x|e1|或x|e2|}

|{e}|=|e|*(e的閉包)例：(0|1){0|1}的值為：一切只包含0與1的任意序列組成的正則集（二進(jìn)制數(shù)集合）23正則集正則集定義:正則表達(dá)式e的值是字母表上的正則集，記作舉例例:

2={A,B,0,1},則(A|B){A|B|0|1}5是2上的正則表達(dá)式(A|B){A|B|0|1}5的值，即|(A|B){A|B|0|1}5|，是這樣一個(gè)正則集，每個(gè)字符串都是以字母A或B打頭，后跟以至多5個(gè)字母（A或B）或數(shù)字（0或1）(0|1)(0|1)*∑上的“數(shù)”的全體24舉例例:2={A,B,0,1},則24例令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a

{,a,a,……任意個(gè)a的串}(ab)

{,a,b,aa,ab……所有由a 和b組成的串}(ab)

(aabb)(ab)

{

上所有含有兩個(gè)相繼 的a或兩個(gè)相繼的b組成 的串}25例令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子有例={l，d}，r=l(ld)

定義的正規(guī)集:{l,ll,ld,ldd,……}（標(biāo)識符）例={d，.，e，+，-},則上的正規(guī)式d

(.dd

)(e(+-)dd

)表示的是無符號數(shù)的集合。其中d為0~9的數(shù)字。26例={l，d}，r=l(ld)定義的正規(guī)集:兩個(gè)正規(guī)式等價(jià)若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價(jià),寫作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)

=(ba)

b

(ab)

=(a

b

)

27兩個(gè)正規(guī)式等價(jià)若兩個(gè)正規(guī)式e1和e2所表示的正規(guī)集相同,則說正規(guī)式的運(yùn)算律設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：1。rs=sr “或”服從交換律2。r(st)=(rs)t “或”的可結(jié)合律3。(rs)t=r(st) “連接”的可結(jié)合律4。r(st)=rsrt (st)r=srtr 分配律5。r=r,r=r 是“連接”的恒等元素6。rr=r r

=rrr… “或”的抽取律

28正規(guī)式的運(yùn)算律設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：程序中的單詞都能用正規(guī)式來定義令l為a~z的字母，d為0~9的數(shù)字e1=l(l|d)* e1表示標(biāo)識符集合e2=dd* e2表示無符號整數(shù)注(比較)： <標(biāo)識符>→l｜l<字母數(shù)字><字母數(shù)字>→l｜d｜l<字母數(shù)字>｜d<字母數(shù)字> 正規(guī)式比正規(guī)文法更容易讓人理解單詞是按怎樣的規(guī)律構(gòu)成的，且可以從某個(gè)正規(guī)式自動地構(gòu)造識別程序。29程序中的單詞都能用正規(guī)式來定義29正規(guī)文法和正規(guī)式間的轉(zhuǎn)換等價(jià)性：對任意一個(gè)正規(guī)文法，存在一個(gè)定義同一語言的正規(guī)式對任意一個(gè)正規(guī)式，存在一個(gè)定義同一語言的正規(guī)文法30正規(guī)文法和正規(guī)式間的轉(zhuǎn)換等價(jià)性：30將∑上的一個(gè)正規(guī)式r轉(zhuǎn)換成文法G=(VN,VT,S,P)VT=∑,首先形成產(chǎn)生式S→r,S為G的開始符不斷利用下面的規(guī)則做變換,直到每個(gè)產(chǎn)生式最多含有一個(gè)終結(jié)符為止原產(chǎn)生式變換后產(chǎn)生式規(guī)則1A→xyA→xBB→y規(guī)則2A→x*yA→xAA→y規(guī)則3A→x|yA→xA→y其中B為一新非終結(jié)符31將∑上的一個(gè)正規(guī)式r轉(zhuǎn)換成文法G=(VN,VT,S,P)原產(chǎn)例:將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正則文法令轉(zhuǎn)換成文法G=(VN,VT,P,S)其中VT={a,d}，文法開始符為S首先形成S→a(a|d)*,然后變換S→aA A→(a|d)*A→(a|d)AA→εA→aAA→dA 最終有產(chǎn)生式：S→aA，A→ε，A→aA， A→dA32例:將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正則文法A→(a|d)將正規(guī)文法轉(zhuǎn)換成正規(guī)式將每條產(chǎn)生式改寫為正規(guī)式用代入法解正規(guī)式方程組最后只剩下一個(gè)開始符號定義的正規(guī)式,其中不含非終結(jié)符正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則:文法產(chǎn)生式正規(guī)式規(guī)則1A→xBB→yA=xy規(guī)則2A→xA|yA=x*y規(guī)則3A→xA→yA=x|y33將正規(guī)文法轉(zhuǎn)換成正規(guī)式文法產(chǎn)生式正規(guī)式規(guī)則1A→xBB→例：將文法G[S]轉(zhuǎn)換成正規(guī)式G：S→aA|aA→dA|d先由產(chǎn)生式得: S=aA|a A=d*d將A代入S中得: S=ad*d|a利用正規(guī)式變換得 S=a(d*d|ε)=ad*說明:d*d|ε =(ε|d|dd|…)d|ε =d|dd|…|ε=d* 所求正規(guī)式為ad*34例：將文法G[S]轉(zhuǎn)換成正規(guī)式34有窮自動機(jī)（FiniteAutomata）狀態(tài)轉(zhuǎn)換圖確定有窮狀態(tài)自動機(jī)（DFA）非確定有窮狀態(tài)自動機(jī)（NFA）把NFA變?yōu)镈FADFA的化簡35狀態(tài)轉(zhuǎn)換圖35狀態(tài)轉(zhuǎn)換圖（TransitionDiagram）為了識別正則文法的句子而專門設(shè)計(jì)的有向圖。如：C語言中關(guān)于標(biāo)識符定義的規(guī)則（詞法規(guī)則）如下：<標(biāo)識符>::=字母|<標(biāo)識符>字母|<標(biāo)識符>數(shù)字則識別標(biāo)識符的狀態(tài)（轉(zhuǎn)換）圖：SIE字母數(shù)字字母或數(shù)字狀態(tài)都是非終結(jié)符號S：開始狀態(tài)E：終止?fàn)顟B(tài)，用雙圈表示I：標(biāo)識符狀態(tài)36狀態(tài)轉(zhuǎn)換圖（TransitionDiagram）為了識別正狀態(tài)轉(zhuǎn)換圖——概念1有限方向圖結(jié)點(diǎn)表示狀態(tài)有一個(gè)起始狀態(tài)，初態(tài)至少有一個(gè)終止?fàn)顟B(tài)，終態(tài)。用雙圓圈表示狀態(tài)的數(shù)量有限狀態(tài)之間用有方向的邊——箭頭相連箭頭上有標(biāo)記37狀態(tài)轉(zhuǎn)換圖——概念1有限方向圖37狀態(tài)轉(zhuǎn)換圖——概念2當(dāng)前狀態(tài)箭頭的起始結(jié)點(diǎn)目的狀態(tài)箭頭的終點(diǎn)箭頭上的標(biāo)記當(dāng)前狀態(tài)允許輸入字符或一類字符從當(dāng)前狀態(tài)通過輸入箭頭上的標(biāo)記到達(dá)目的狀態(tài)38狀態(tài)轉(zhuǎn)換圖——概念2當(dāng)前狀態(tài)38voidstate0(buffer&aBuf,token&aToken){charaChar=aBuf.getChar();if(aChar<=‘z’)&&(aChar>=‘a(chǎn)’){aToken.val.append(aChar);state1(aBuf,aToken);}elseaToken.type=token.error;}39voidstate0(buffer&aBuf,tvoidstate1(buffer&aBuf,token&aToken){charaChar=aBuf.getChar();while((aChar<=‘z’)&&(aChar>=‘a(chǎn)’)||(aChar<=‘9’)&&(aChar>=‘0’)){aChar=aBuf.getChar();aToken.val.append(aChar);}state2(aBuf,aToken);}40voidstate1(buffer&aBuf,tvoidstate2(buffer&aBuf,token&aToken){aBuf.goBack(1);aToken.val.removeTail(1);aToken.type=token.identifier;}

41voidstate2(buffer&aBuf,to如何為正則文法構(gòu)造狀態(tài)轉(zhuǎn)換圖？什么是正則文法？（U::=a或U::=aB）步驟如下：以S為開始狀態(tài)作結(jié)點(diǎn)；把文法中的每一個(gè)非終結(jié)符號作為狀態(tài)結(jié)點(diǎn)；對于形如Q::=a的每個(gè)規(guī)則，引一條開始狀態(tài)S到狀態(tài)Q的弧，弧上標(biāo)記為a；對于形如Q::=aB的規(guī)則引一條從狀態(tài)a到Q的弧，弧上標(biāo)記為B，其中a為非終結(jié)符號，B為終結(jié)符號。以識別符號為終止?fàn)顟B(tài)。42如何為正則文法構(gòu)造狀態(tài)轉(zhuǎn)換圖？什么是正則文法？（U::=a構(gòu)造狀態(tài)轉(zhuǎn)換圖舉例例如：對于正則文法G[Z]：Z::=Za|Aa|BbA::=Ba|aB::=Ab|bSABabSABaZZaSABabZbaabaaaba(1)(2)(3)43構(gòu)造狀態(tài)轉(zhuǎn)換圖舉例例如：對于正則文法G[Z]：SABabSA如何應(yīng)用狀態(tài)轉(zhuǎn)換圖識別句子？如果x是相應(yīng)文法的句子便必須能從開始狀態(tài)出發(fā)，順著弧的方向行進(jìn)到終止?fàn)顟B(tài)。其步驟如下:(1)從開始狀態(tài)開始，以它作為當(dāng)前狀態(tài)，并從x的最左字符開始重復(fù)步驟2，直到到達(dá)x的右端為止；(2)掃描x的下一字符，在當(dāng)前狀態(tài)射出的各個(gè)弧中找出標(biāo)記有該字符的弧，并沿此弧前進(jìn)，以達(dá)到的狀態(tài)作為下一當(dāng)前狀態(tài)。步驟2存在的兩種可能：可能找不到一條弧的標(biāo)記與當(dāng)前字符相同；總能找到一個(gè)弧，其標(biāo)記與當(dāng)前字符相同。44如何應(yīng)用狀態(tài)轉(zhuǎn)換圖識別句子？如果x是相應(yīng)文法的句子便必須能從應(yīng)用狀態(tài)轉(zhuǎn)換圖識別句子舉例例如：對于正則文法G[Z]：Z::=Za|Aa|BbA::=Ba|aB::=Ab|babSABabZbaaabSABabZbaa(1)識別字符串a(chǎn)babaaaFba,b(2)識別字符串bababbb45應(yīng)用狀態(tài)轉(zhuǎn)換圖識別句子舉例例如：對于正則文法G[Z]：abS狀態(tài)轉(zhuǎn)換圖識別句子的實(shí)質(zhì)是一個(gè)規(guī)約過程，運(yùn)用自底向上的識別算法：如：SA與AZ表示：a直接規(guī)約為A，Aa直接規(guī)約為Z。從開始狀態(tài)S出發(fā)逐步到達(dá)終止?fàn)顟B(tài)Z的過程，也是從終結(jié)符號串出發(fā)，規(guī)約到非終結(jié)符號的過程。46狀態(tài)轉(zhuǎn)換圖識別句子的實(shí)質(zhì)是一個(gè)規(guī)約過程，運(yùn)用自底向上的識別算對句子ababaaa的分析步驟當(dāng)前狀態(tài)輸入的其余部分SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZababaaaABABAZZ(a)分析過程(b)語法樹47對句子ababaaa的分析步驟當(dāng)前狀態(tài)輸入的其余狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)1每個(gè)狀態(tài)對應(yīng)一個(gè)子程序當(dāng)前結(jié)點(diǎn)的輸出邊的目的結(jié)點(diǎn)不是當(dāng)前結(jié)點(diǎn)——不含有直接回路用嵌套的條件語句實(shí)現(xiàn)當(dāng)前結(jié)點(diǎn)的輸出邊的目的結(jié)點(diǎn)是當(dāng)前結(jié)點(diǎn)——含有直接回路用循環(huán)語句實(shí)現(xiàn)48狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)1每個(gè)狀態(tài)對應(yīng)一個(gè)子程序48狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)2終態(tài)結(jié)點(diǎn)用返回語句實(shí)現(xiàn)返回單詞符號的種類和屬性值帶有*的結(jié)點(diǎn)為進(jìn)行了超前搜索的結(jié)點(diǎn)。需要把掃描位置退回超前搜索字符的個(gè)數(shù)49狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)2終態(tài)結(jié)點(diǎn)用返回語句實(shí)現(xiàn)49什么是轉(zhuǎn)換系統(tǒng)？轉(zhuǎn)換系統(tǒng)對于從正則表達(dá)式轉(zhuǎn)換到狀態(tài)轉(zhuǎn)換圖起到了中間表示的作用。定義：轉(zhuǎn)換系統(tǒng)是具有下列三個(gè)特征的狀態(tài)轉(zhuǎn)換圖，即1)開始狀態(tài)S和終止?fàn)顟B(tài)Z唯一;2)無弧進(jìn)入S，也無弧自Z射出；3)可能存在標(biāo)記為空串（ε）的弧。轉(zhuǎn)換系統(tǒng)與狀態(tài)轉(zhuǎn)換圖的區(qū)別：ε弧SS1S2ZεεAZ2Z1εε50什么是轉(zhuǎn)換系統(tǒng)？轉(zhuǎn)換系統(tǒng)對于從正則表達(dá)式轉(zhuǎn)換到狀態(tài)轉(zhuǎn)換圖起到詞法規(guī)則的描述狀態(tài)轉(zhuǎn)換圖難于書寫，非線性結(jié)構(gòu)更好的方式的要求線性方式表達(dá)與狀態(tài)轉(zhuǎn)換圖等價(jià)正規(guī)表達(dá)式[a-z][a-z0-9]*51詞法規(guī)則的描述狀態(tài)轉(zhuǎn)換圖51有窮自動機(jī)(也稱有限自動機(jī))是一種識別裝置作用:能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合意義:為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。分類:

確定的有窮自動機(jī)

(DeterministicFiniteAutomata)

不確定的有窮自動機(jī)

(NondeterministicFiniteAutomata)52有窮自動機(jī)(也稱有限自動機(jī))是一種識別裝置52確定型有窮狀態(tài)自動機(jī)一個(gè)確定的有窮自動機(jī)（DFA）D是一個(gè)五元組：D=（K，Σ，f，S，Z）其中K：有窮非空的狀態(tài)集合；Σ：有窮非空的輸入符號字母表；f：轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映像，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作ki的一個(gè)后繼狀態(tài)；S∈K是唯一的一個(gè)初態(tài)；Z_K是非空的終態(tài)集合?！按_定”即狀態(tài)轉(zhuǎn)換函數(shù)是單值函數(shù)！53確定型有窮狀態(tài)自動機(jī)一個(gè)確定的有窮自動機(jī)（DFA）D是一個(gè)五從狀態(tài)轉(zhuǎn)換圖構(gòu)造有窮狀態(tài)自動機(jī)例如：從下面狀態(tài)圖構(gòu)造DFADFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）其中M定義為：M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z abSABabZbaa54從狀態(tài)轉(zhuǎn)換圖構(gòu)造有窮狀態(tài)自動機(jī)例如：從下面狀態(tài)圖構(gòu)造DFAa運(yùn)行DFA與識別一個(gè)字符串定義：對于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，則稱符號串t可被DFAD所接受。運(yùn)行一個(gè)DFA的過程：識別一個(gè)符號串是否被接受55運(yùn)行DFA與識別一個(gè)字符串定義：對于某DFAD=（K,Σ舉例如前例：DFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}）M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z 則：M(S,ababaa)=M(M(S,a),babaa)=M(A,babaa)=M(M(A,b),abaa)=M(B,abaa)=M(A,baa)=M(B,aa)=M(A,a)=Z56舉例如前例：DFAD=（{S，Z，A，B}，{a，b}正則集正則集：L(D)，是一個(gè)DFA接受的字符串集合正則語言與正則集：L(G)=L(D)最小狀態(tài)自動機(jī)：狀態(tài)個(gè)數(shù)最少，唯一57正則集正則集：L(D)，是一個(gè)DFA接受的字符串集合57如何在計(jì)算機(jī)內(nèi)表示映像？映像M：含義？映像在計(jì)算機(jī)內(nèi)的表示法：矩陣表示法表結(jié)構(gòu)表示法DFA的確定性體現(xiàn)在δ是一個(gè)從SXΣ到S的單值部分映射也即使?fàn)顟B(tài)的轉(zhuǎn)換是確定的，是單值映射58如何在計(jì)算機(jī)內(nèi)表示映像？映像M：含義？58DFA的矩陣表示法字符狀態(tài)abSABabZbaa矩陣行代表狀態(tài)，列代表輸入字符，矩陣元素是映像得到的新狀態(tài)。59DFA的矩陣表示法字符狀態(tài)abSABabZbaa矩陣行代表表結(jié)構(gòu)表示法狀態(tài)名射出的弧數(shù)標(biāo)記1指向的下一狀態(tài)1…標(biāo)記K指向的下一狀態(tài)k對每一個(gè)狀態(tài)結(jié)點(diǎn)而言若某結(jié)點(diǎn)有K個(gè)射出的弧，則相應(yīng)表長為2k+260表結(jié)構(gòu)表示法狀態(tài)名射出的弧數(shù)標(biāo)記1指向的下一狀態(tài)1…標(biāo)記K指非確定有窮狀態(tài)自動機(jī)的引入M(R,T)是K×Σ到K的單值函數(shù)，即唯一確定下一狀態(tài)如果在當(dāng)前狀態(tài)下，同一個(gè)輸入字符確定的下一狀態(tài)不止一個(gè)呢？如V::=UTW::=UTUWVTTabSABabZbaaaa例如：文法G3.2:Z::=Za|Aa|BbA::=Ba|Za|aB::=Ab|Ba|b61非確定有窮狀態(tài)自動機(jī)的引入M(R,T)是K×Σ到K的單值函數(shù)非確定有窮狀態(tài)自動機(jī)一個(gè)非確定的有窮自動機(jī)（NFA）D是一個(gè)五元組：N=（K，Σ，M，S，F(xiàn)）其中K：有窮非空的狀態(tài)集合；Σ：有窮非空的輸入字母表；M：轉(zhuǎn)換函數(shù)，是在K×Σ到K的子集所組成集合的映像，M(R,T)={Q1,Q2,….Qn}S=K是非空的初態(tài)集合；F=K是非空的終態(tài)集合.62非確定有窮狀態(tài)自動機(jī)一個(gè)非確定的有窮自動機(jī)（NFA）D是一個(gè)DFA與NFA的區(qū)別DFANFA開始狀態(tài)唯一一個(gè)或多個(gè)映像單個(gè)狀態(tài)狀態(tài)集合63DFA與NFA的區(qū)別DFANFA開始狀態(tài)唯一一個(gè)或多個(gè)映像單舉例前述文法G3.2對應(yīng)的自動機(jī)NFAN=({S,A,B,Z},{a,b},M,{S},{Z})其中M：M(S,a)={A}M(S,b)={B}M(A,a)={Z}M(A,b)={B}M(B,a)={A,B}M(B,b)={Z}M(Z,a)={A,Z}abSABabZbaaaa64舉例前述文法G3.2對應(yīng)的自動機(jī)NFAN=({S,A,B,舉例(字符串被NFA所接受)對于輸入字符串babbabb，運(yùn)行G3.2的NFA步驟當(dāng)前狀態(tài)輸入的其余部分可能的后繼選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ65舉例(字符串被NFA所接受)對于輸入字符串babbabb，運(yùn)運(yùn)行NFA運(yùn)行NFA：識別一個(gè)字符串是否被NFA所接受，是否能達(dá)到終態(tài)集合中的某個(gè)狀態(tài)實(shí)質(zhì)：用自底向上方法識別句子狀態(tài)轉(zhuǎn)換的下一狀態(tài)不唯一，如何解決？66運(yùn)行NFA運(yùn)行NFA：識別一個(gè)字符串是否被NFA所接受，是否DFA和NFA的關(guān)系對于Σ*上的字符串β，如果存在一條從初態(tài)到終態(tài)的通路，且這條通路上的輸入字符恰好連接成β，稱為β可以此DFA、NFA識別DFA、NFA都可以識別一個(gè)字符集Σ上的字符串可以用DFA、NFA定義Σ上的字符串的集合DFA都是NFA、NFA可化為等價(jià)的DFA67DFA和NFA的關(guān)系對于Σ*上的字符串β，如果存在一條從初態(tài)構(gòu)造與正規(guī)式等價(jià)的NFA方法XYααα|β12αβ1268構(gòu)造與正規(guī)式等價(jià)的NFA方法XYααα|β12αβ12683αεε1αβ32αβ1221α*12693αεε1αβ32αβ1221α*1269構(gòu)造與正規(guī)式等價(jià)的NFA示例a(a|b)*XYa(a|b)*XYa1(a|b)*70構(gòu)造與正規(guī)式等價(jià)的NFA示例a(a|b)*XYa(a|b)XYa1(a|b)2XYa1a2bεεεε71XYa1(a|b)2XYa1a2bεεεε71NFA的確定化方法初態(tài)的唯一化終態(tài)的唯一化從初態(tài)開始，求對于每個(gè)輸入符號的后繼狀態(tài)集合Si——新的狀態(tài)對每個(gè)Si，求對于每個(gè)輸入符號的后繼狀態(tài)集合Si+1直到不產(chǎn)生新的后繼狀態(tài)集合含有終態(tài)的狀態(tài)集合為終態(tài)72NFA的確定化方法初態(tài)的唯一化72NFA的確定化示例狀態(tài)轉(zhuǎn)換矩陣 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {}XYa1a2bεε73NFA的確定化示例狀態(tài)轉(zhuǎn)換矩陣 a bXYa1a2bεε73 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {} a b{X} {1,2,Y}{} {1,2,Y}{2,Y}{2,Y}{2,Y} {2,Y}{2,Y}NFA狀態(tài)轉(zhuǎn)換矩陣1)(2)(3) a b1) (2) (2) (3) (3)(3) (3) (3)等價(jià)的DFA狀態(tài)轉(zhuǎn)換矩陣74 a b a bNFA狀態(tài)轉(zhuǎn)換矩陣1) a b等價(jià)的 a b1) (2) (2) (3) (3)(3) (3) (3)13aabab275 a b13aabab275ε閉包狀態(tài)集I的ε_CLOSURE(I)如果q屬于Iq屬于ε_CLOSURE(I)從q出發(fā)經(jīng)任意條ε弧到達(dá)的任何狀態(tài)q’都屬于ε_CLOSURE(I)76ε閉包狀態(tài)集I的ε_CLOSURE(I)76DFA的化簡狀態(tài)的等價(jià)性能夠識別相同的字符串劃分為終態(tài)和非終態(tài)兩個(gè)子集如果某個(gè)子集中的狀態(tài)是可區(qū)分的，則進(jìn)一步劃分這個(gè)子集直到在每個(gè)子集內(nèi)，各個(gè)狀態(tài)都是不可區(qū)分的。同一子集內(nèi)的狀態(tài)合并。77DFA的化簡狀態(tài)的等價(jià)性77DFA的化簡示例 a b1) 2) 2) (3) (3)(3) (3) (3)劃分1：{1},{2，3}{2,3}a={3}屬于{2,3}{2,3}b={3}屬于{2,3}狀態(tài)2、3不可區(qū)分，應(yīng)簡化為{1,2}78DFA的化簡示例 a b劃分1：{1},{2，3}7813aabab21a2ab化簡前的DFA化簡后的DFA7913aabab21a2ab化簡前的DFA化簡后的DFA79練習(xí)字母表{a,b}上所有含有aa或bb的字符串組成的集合用正規(guī)式表達(dá)為(a|b)*(aa|bb)(a|b)*80練習(xí)字母表{a,b}上所有含有aa或bb的字符串組成的集合8(a|b)*(aa|bb)(a|b)*0Y(a|b)*(aa|bb)(a|b)*1Y(aa|bb)(a|b)*0(a|b)*1Y(a|b)*0(a|b)*2(aa|bb)81(a|b)*(aa|bb)(a|b)*0Y(a|b)*(aa1Y(a|b)*0a2(aa|bb)3bεε1Y(a|b)*0a2aa3bεεbb821Y(a|b)*0a2(aa|bb)3bεε1Y(a|b)*1Y(a|b)*0a2a3bεεb45ab831Y(a|b)*0a2a3bεεb45ab831Y0a2a3bεεb45ab6baεε841Y0a2a3bεεb45ab6baεε84狀態(tài)轉(zhuǎn)換矩陣

a b{X,3,1} {3,1,4} {3,1,5}{3,1,4} {3,1,4,2,6,Y} {3,1,5}{3,1,5} {3,1,4} {3,1,5,2,6,Y}{3,1,4,2,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}{3,1,5,2,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,5,6,Y} {3,1,4,6,Y} {3,1,5,2,6,Y}{3,1,4,6,Y} {3,1,4,2,6,Y} {3,1,5,6,Y}85狀態(tài)轉(zhuǎn)換矩陣 a b85狀態(tài)轉(zhuǎn)換矩陣

a b0 1 21 3 22 1 43） 3 54） 6 45） 6 46） 3 586狀態(tài)轉(zhuǎn)換矩陣 a b86DFA的最小化一定可以區(qū)分的兩個(gè)集合用e表示出錯狀態(tài)非終止?fàn)顟B(tài)集{0,1,2}——不認(rèn)識ε終止?fàn)顟B(tài)集{3,4,5,6}——認(rèn)識ε{0,1,2}中δ(0,a)=1,δ(1,a)=3,δ(2,a)=1{0,2}與{1}不同，可區(qū)分{0,2}中δ(0,b)=2,δ(2,b)=4{0}與{2}不同，可區(qū)分{3,4,5,6}a={3,6},{3,4,5,6}b={4,5}{3,4,5,6}內(nèi)不可區(qū)分87DFA的最小化一定可以區(qū)分的兩個(gè)集合87最小化的DFA a b0 1 21 3 22 1 33 3 3 88最小化的DFA a b88詞法分析程序的實(shí)現(xiàn)詞法分析程序的構(gòu)造方法詞法分析程序的編寫89詞法分析程序的實(shí)現(xiàn)89構(gòu)造詞法分析程序的方法用手工方式，即根據(jù)識別語言單詞的狀態(tài)轉(zhuǎn)換圖，使用某種高級語言，例如，C語言直接編寫詞法分析程序。利用自動生成工具LEX自動生成詞法分析程序。90構(gòu)造詞法分析程序的方法用手工方式，即根據(jù)識別語言單詞的狀態(tài)轉(zhuǎn)詞法分析程序?qū)崿F(xiàn)中

要考慮的問題確定實(shí)現(xiàn)詞法分析程序的執(zhí)行方式確定屬性字的結(jié)構(gòu)緩沖區(qū)預(yù)處理，超前搜索,關(guān)鍵字的處理，符號表的實(shí)現(xiàn)查找效率，算法的優(yōu)化實(shí)現(xiàn)詞法錯誤處理91詞法分析程序?qū)崿F(xiàn)中

要考慮的問題確定實(shí)現(xiàn)詞法分析程序的執(zhí)行方屬性字詞法分析程序?qū)φf明部分不做語義處理。詞法分析程序輸出屬性字一般采用下面的形式：（符號類，符號值）屬性字是符號的機(jī)內(nèi)表示，有統(tǒng)一固定的長度92屬性字詞法分析程序?qū)φf明部分不做語義處理。92關(guān)鍵字的識別與查表算法對于關(guān)鍵字，先把它們當(dāng)成標(biāo)識符，然后去查關(guān)鍵字表。若在表中查到，則為關(guān)鍵字，獲取相應(yīng)的類別碼；否則，認(rèn)為是標(biāo)識符。查找算法：線性查找折半查找Hash函數(shù)93關(guān)鍵字的識別與查表算法對于關(guān)鍵字，先把它們當(dāng)成標(biāo)識符，然后去出錯處理對定義外的（如，對首字符不是字母的，不是數(shù)字的，不是運(yùn)算符和分界符的）單詞進(jìn)行出錯處理。94出錯處理對定義外的（如，對首字符不是字母的，不是數(shù)字的，不是詞法分析中使用的數(shù)據(jù)字符表：（字母表）列出源程序中所有可能的字符。特定符號與機(jī)內(nèi)表示表：一切特定符號與相應(yīng)編碼。標(biāo)識符表：登錄一切源程序中出現(xiàn)的一切標(biāo)識符。此表的序號作為屬性字的值。常數(shù)表：登錄一切源程序中出現(xiàn)的常數(shù)。此表的序號作為屬性字的值。95詞法分析中使用的數(shù)據(jù)字符表：（字母表）列出源程序中所有可能的使用狀態(tài)圖設(shè)計(jì)詞法分析程序多數(shù)語言的詞法規(guī)則可用正則文法和正則表達(dá)式來描述。正則文法或正則表達(dá)式定義的語言都可以被狀態(tài)圖識別。使用狀態(tài)圖設(shè)計(jì)詞法分析程序的步驟如下：對程序設(shè)計(jì)語言的單詞按類構(gòu)造相應(yīng)的狀態(tài)圖。（這里把關(guān)鍵字與標(biāo)識符作為一類）合并各類單詞的狀態(tài)圖，增加一個(gè)出錯處理終態(tài)，構(gòu)成一個(gè)識別該語言所有單詞的狀態(tài)轉(zhuǎn)換圖對狀態(tài)圖的每一個(gè)終點(diǎn)編一段相應(yīng)的子程序。96使用狀態(tài)圖設(shè)計(jì)詞法分析程序多數(shù)語言的詞法規(guī)則可用正則文法和正201字母字母|數(shù)字其它3456數(shù)字?jǐn)?shù)字其它+-78*/9101113<=>:;1617其它13=舉例97201字母字母|數(shù)字其它3456數(shù)字?jǐn)?shù)字其它+-78*/91詞法分析程序的結(jié)構(gòu)取字符子程序取符號子程序，一般有如下約定：進(jìn)入子程序時(shí)，已經(jīng)取到當(dāng)前符號的一個(gè)字符。離開子程序時(shí)，已經(jīng)取到其后繼字符。查造標(biāo)識符表子程序查造常量表子程序查符號機(jī)內(nèi)表示對照表子程序98詞法分析程序的結(jié)構(gòu)取字符子程序98詞法分析程序的自動生成（Lex)LEX是由美國Bell實(shí)驗(yàn)室的M.Lesk和Schmidt于1975年用C語言研制的一個(gè)詞法分析程序的自動生成工具。對任何高級程序語言，用戶必須用正規(guī)表達(dá)式描述該語言的各個(gè)詞法類（這一描述稱為LEX的源程序），LEX就可以自動生成該語言的詞法分析程序。LEX及其編譯系統(tǒng)的作用如圖。99詞法分析程序的自動生成（Lex)LEX是由美國Bell實(shí)驗(yàn)圖LEX及其編譯系統(tǒng)的作用100圖LEX及其編譯系統(tǒng)的作用100一個(gè)LEX源程序由用“%%”分隔的三部分組成：第一部分為正規(guī)式的輔助定義式，第二部分為識別規(guī)則，最后一部分為用戶子程序。其書寫格式為：輔助定義式%%識別規(guī)則%%用戶子程序101一個(gè)LEX源程序由用“%%”分隔的三部分組其中，輔助定義式和用戶子程序是任選的，而識別規(guī)則是必需的。如果用戶子程序缺省，則第二個(gè)分隔符號“%%”可以省去；但如果無輔助定義式部分，第一個(gè)分隔符號“%%”不能省去，因?yàn)榈谝粋€(gè)分隔符號用于指示識別規(guī)則部分的開始。102其中，輔助定義式和用戶子程序是任選的下面給出一個(gè)簡單語言的單詞符號的LEX源程序例子，其輸出單詞的類別編碼用整數(shù)編碼表示。AuxiliaryDefinitions /*輔助定義*/letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣zdigit→0∣1∣2∣3∣…∣9%%RecognitionRules /*識別規(guī)則*/103下面給出一個(gè)簡單語言的單詞符號的LEX源程1while {return(1,null)}2do {return(2,null)}3if {return(3,null)}4else {return(4,null)}5switch {return(5,null)}6{ {return(6,null)}7} {return(7,null)}8( {return(8,null)}9) {return(9,null)}10+ {return(10,null)}11? {return(11,null)}1041while {ret12* {return(12,null)}13/ {return(13,null)}14= {return(14,null)}15； {return(15,null)}16letter(letter∣digit)*{if(keyword(id)==0){return(16,null)；return(id)};elsereturn(keyword(id))}17digit(digit)* {val=int(id)； return(17,null)； return(val)}10512* {retu18（letter∣digit∣{∣}∣(∣)∣+∣?∣*∣/∣=∣；）* {return(18，null)；inslit(id)； return(pointer，lenth)}該LEX源程序中用戶子程序?yàn)榭?；其中識別規(guī)則{A18}語句中調(diào)用過程“inslit(id)”是將字符串常量id存放到字符表中，“pointer”中存放該串的起始位置，“l(fā)enth”存放該串的長度。10618（letter∣digit∣{∣}∣(∣LEX可以用兩種方式來使用：一種是將LEX作為一個(gè)單獨(dú)的工具，用以生成所需的識別程序；另一種是將LEX和語法分析器自動生成工具（如YACC）結(jié)合起來使用，以生成一個(gè)編譯程序的掃描器和語法分析器。107LEX可以用兩種方式來使用：一種是主線：兩個(gè)工具：正規(guī)文法和正規(guī)式一個(gè)識別系統(tǒng)：有窮自動機(jī)詞法分析程序的設(shè)計(jì)

本章小結(jié)108主線：本章小結(jié)108自動機(jī)、正則文法、正則表達(dá)式

的相互轉(zhuǎn)化正則文法NFA正則表達(dá)式123456DFA最小化109自動機(jī)、正則文法、正則表達(dá)式

的相互轉(zhuǎn)化正則文法NFA正則表主要內(nèi)容詞法分析的功能單詞的種類及詞法分析程序的輸出形式正則文法和狀態(tài)圖★★★正則表達(dá)式與有窮自動機(jī)★★★

詞法分析程序110主要內(nèi)容詞法分析的功能110基本要求了解詞法分析程序的功能和實(shí)質(zhì)。明確DFA與NFA的區(qū)別，掌握把NFA變?yōu)镈FA的方法；熟練掌握把正則文法變?yōu)闋顟B(tài)轉(zhuǎn)換圖以及寫出有窮狀態(tài)自動機(jī)的方法。掌握詞法分析程序的基本實(shí)現(xiàn)方法。111基本要求了解詞法分析程序的功能和實(shí)質(zhì)。111作業(yè)第1題:構(gòu)造正規(guī)式相應(yīng)的最小化的DFA：1(0|1)*101

第2題:給出下述文法所對應(yīng)的正則式：S→0A|1B,A→1S|1,B→0S|0第3題:構(gòu)造正規(guī)式相應(yīng)的最小化DFA：b*abb*(abb*)*112作業(yè)第1題:構(gòu)造正規(guī)式相應(yīng)的最小化的DFA：1(0|1一個(gè)簡單的詞法分析器示例1C語言子集的單詞符號表示一個(gè)非常重要的事實(shí)是：大多數(shù)程序語言的單詞符號都可以用狀態(tài)轉(zhuǎn)換圖予以識別。作為一個(gè)綜合例子，我們來構(gòu)造一個(gè)C語言子集的簡單詞法分析器。表1列出了這個(gè)C語言子集的所有單詞符號以及它們的種別編碼和內(nèi)碼值。由于直接使用整數(shù)編碼不利于記憶，故該例中用一些特殊符號來表示種別編碼。113一個(gè)簡單的詞法分析器示例1C語言子集的單詞符號表示11表1C語言子集的單詞符號及內(nèi)碼值單詞符號種別編碼助記符內(nèi)碼值while1while—if2if—else3else—switch4switch—case5case—標(biāo)識符6idid在符號表中的位置常數(shù)7numnum在常數(shù)表中的位置+8+—?9?—*10*—<=11relopLE<11relopLT==11relopEQ=12=—；13；—114表1C語言子集的單詞符號及內(nèi)碼值while1while2C語言子集對應(yīng)的狀態(tài)轉(zhuǎn)換圖在設(shè)計(jì)的狀態(tài)轉(zhuǎn)換圖中，首先對輸入串做預(yù)處理，即剔除多余的空白符（在實(shí)際的詞法分析中，預(yù)處理還包括剔除注釋和制表換行符等編輯性字符的工作），使詞法分析工作既簡單又清晰。其次，將保留字作為一類特殊的標(biāo)識符來處理，也即對保留字不專設(shè)對應(yīng)的狀態(tài)轉(zhuǎn)換圖，當(dāng)轉(zhuǎn)換圖識別出一個(gè)標(biāo)識符時(shí)就去查對表1的前五項(xiàng)，確定它是否為一個(gè)保留字。當(dāng)然，也可以專設(shè)一個(gè)保留字表來進(jìn)行處理。圖5就是對應(yīng)表1這個(gè)簡單詞法分析的狀態(tài)轉(zhuǎn)換圖。

1152C語言子集對應(yīng)的狀態(tài)轉(zhuǎn)換圖115圖5簡單詞法分析的狀態(tài)