第3章詞法分析

1第3章詞法分析

人們理解一篇文章（或一個程序）起碼是在單詞的級別上來思考的。同樣，編譯程序也是在單詞的級別上來分析和翻譯源程序的。

詞法分析的必要性描述單詞的結構比其它語法結構簡單，僅用3型文法就夠了；將單詞識別從語法分析識別分離出來，可采用更有效的工具實現；有些語言的單詞識別與前后文相關，不宜將其與語法分析合并；使編譯程序各部分獨立出來，有利于設計、調試和維護執(zhí)行詞法分析的程序稱為詞法分析器（掃描器）的輸出是語法分析程序的輸入本章討論詞法分析程序的手工構造方法和自動構造方法。2教學內容§3.1詞法分析程序§3.2單詞的描述工具§3.3有窮自動機§3.4正規(guī)文法和有窮自動機間的等價§3.5正規(guī)文法和有窮自動機間的轉換§3.6詞法分析程序的設計3學習目標:掌握：詞法分析程序的構造，正規(guī)式和正規(guī)文法到有窮自動機的轉換，NFA到DFA的轉換、DFA的化簡理解：正規(guī)文法、正規(guī)式、DFA的概念、NFA的概念了解：詞法分析程序的自動構造工具4§3.1詞法分析程序詞法分析器的功能是輸入源程序，輸出單詞符號。通常把詞法分析程序設計為語法分析程序的子程序。每當語法分析程序需要一個單詞符號時，就向詞法分析程序發(fā)出“取下一個單詞符號”的調用命令。詞法分析程序就從輸入字符串中，識別出一個具有獨立意義的單詞符號，并傳送給語法程序。字符串表示的

源程序詞法分析器語法分析器字符單詞符號取下一個

單詞符號1.詞法分析器的功能和輸出形式5單詞符號是一個程序語言的基本語法符號。稱作token(記號)

具有獨立意義的最小語法單位。語言的單詞符號詞法分析程序是以字符串形式的源程序作為輸入，以單詞符號或單詞符號表示的源程序作為輸出。將字符組合成記號與在一個英語句子中將字母構成單詞并確定單詞的含義很相像，此時的任務很像拼寫。6關鍵字：是由程序語言定義的具有固定意義的標識符，也稱保留字或基本字。如Pascal中的begin、end、if、integer等，C中的if、else、do、while，C++中的class、int、switch、break等都是保留字，它們一般不用作一般標識符。標識符：用來表示各種名字，如變量名、常量名、數組名、函數名、子程序名等。常數：程序中出現的各種類型的常量。常量的類型一般有整型、實型、布爾型、字符型等。如125、0.718、TRUE、“Hello”等。運算符：表達式中連接運算對象的符號。如+、-、*、/、<等。界符：程序中的定界符。如逗號、分號、括號、/*、*/等。程序語言的單詞符號一般可分為下列五種：7詞法分析程序輸出單詞的形式詞法分析器所輸出的單詞符號常常表示成如下的二元式： （單詞種別，單詞符號的屬性值）單詞種別（它是語法分析需要的信息）

通常用整數編碼。

一個語言的單詞符號如何分種，分成幾種，怎樣編碼，是一個技術性的問題。它主要取決于處理上方便。

標識符一般統(tǒng)歸為一種。

常數則按類型分種。

關鍵字可將其全體視為一種，也可以一字一種。采用一字一種的分法實際處理起來較為方便。運算符可采用一符一種的分法，但也可以把具有一定共性的運算符視為一種。

至于界符一般用一符一種的分法。8單詞自身的值（單詞符號的屬性值，它是編譯其它階段需要的信息）

屬性值是指單詞符號的特性或特征，可以是標識符在符號表的入口地址、數值的二進制值等。如果是一符一種的分法，詞法分析器只給出其種別編碼，不給出其屬性值。如果一個種別含有多個單詞符號，那么對于它的每個單詞符號，除了給出種別編碼之外，還應給出導出符號的屬性值，以便把同一種類的單詞區(qū)別開來。

標識符屬性值是自身的符號串；也可是在符號表的入口地址。

常數自身值是常數的二進制數值。9【例】試給出程序段if(a>1)b=100;輸出的單詞符號串。假定基本字、運算符和界符都是一符一種，標識符自身的值是字符串，常數是二進制值。(2,)基本字if(29,)左括號((10,‘a’)標識符a(23,)大于號>(11,‘1’的二進制)常數1(30，)右括號)(10,‘b’)標識符b(17,)賦值號=(11,‘100’的二進制)常數100(26,)分號;10經詞法分析器處理后，它將被轉換為如下的單詞符號序列：

(while,-)

(( ,-)

(id,指向i的符號表表項的指針)

(>=,-)

(id,指向j的符號表表項的指針)

(),-)

(id,指向i的符號表表項的指針)

(--,-)

(；,-)【例】考慮下述C++代碼段：

while(i>=j)i--; 另一種表示假定基本字、運算符和界符都是一符一種，標識符自身的值是符號表的入口地址，常數是二進制值。112.詞法分析器作為一個獨立子程序

把詞法分析器安排為一個獨立的階段的好處是，它可使整個編譯程序的結構更簡單、清晰和條理化。詞法分析比語法分析要簡單得多，可用更有效得特殊方法和工具進行處理。把詞法分析器安排為獨立的一遍，讓它把整個源程序翻譯成一連串的單詞符號（二元式）存放于文件中，待語法分析程序進入工作時再對從文件輸入的這些單詞符號進行分析。把詞法分析器安排為一個子程序，每當語法分析分析器需要一個單詞符號時就調用這個子程序。每一次調用，詞法分析器就從輸入串中識別出一個單詞符號。在后面的討論中，我們假定詞法分析器是按這種方式進行工作的。12相對獨立方式當采用遞歸下降分析等技術實現一趟編譯程序時常采用這種方式。源程序詞法分析程序語法分析程序Tokengettoken….13完全獨立方式采用詞法分析工作完全獨立的原因：簡化設計，降低語法分析的復雜性提高編譯效率增加編譯系統(tǒng)的可移植性源程序詞法分析程序語法分析程序屬性字序列….143.源程序的輸入在內存開辟緩沖區(qū)，將程序文本放進該緩沖區(qū)預處理：刪除無用字符等詞法分析程序對緩沖區(qū)掃描時，設置兩個指示器，一個指向當前正在識別的單詞的開始位置，稱為起始指針；另一個用于向前搜索，以尋找單詞的終點，稱為掃描指針。起始指針搜索指針15識別標識符的若干約定和策略一般來說，單詞的長度是有限制的在允許長度下，應按最長匹配原則進行識別有時需要超前掃描來進行單詞識別。例如，FORTRAN語言中的算術條件句IF(e)=L1,L2,L3和語句函數定義句IF(x)=f(x)中的IF的識別；以及<和<=、<>等。在進行超前掃描時，還應注意“回退”字符，即將多吃掉的字符退還回輸入緩沖區(qū)。使用堆棧實現多字符回退的算法。16單詞符號的構成規(guī)則

——標識符012字母(a-z)字母或數字(a-z0-9)其它*此時，超前搜索了一個字符17§3.2單詞的描述工具作用:描述單詞的構成規(guī)則,基于這類描述工具建立詞法分析技術,進而實現詞法分析程序的自動構造.工具有:正規(guī)文法 正規(guī)式(RegularExpression)181.正規(guī)文法

多數程序設計語言單詞的語法都能用正規(guī)文法(3型文法)描述正規(guī)文法回顧 文法的任一產生式α→β的形式都為A→aB或A→a，其中A，B∈VN

，a∈VT。 正規(guī)文法描述的是VT*上的正規(guī)集19例如:

用l表示a~z中的任一英文字母，d表示0~9中任一數字描述標識符的正規(guī)文法為

<標識符>→l｜l<字母數字> <字母數字>→l｜d｜l<字母數字>｜d<字母數字>描述無符號整數的正規(guī)文法

<無符號整數>→d｜d<無符號整數>20為什么要引進正則表達式？對于字母表∑，我們感興趣的是它的一些特殊字集－正規(guī)集。正規(guī)集是字母表Σ上的符合一定規(guī)則的符號串構成的集合正則表達式是一種適合描述符號的表示法，可由它定義正規(guī)集。212.正規(guī)式(regularexpression)定義（正規(guī)式和它所表示的正規(guī)集）：設字母標為1和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和；2任何a，a是上的一個正規(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僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。22(e1),e1e2,e1e2,e1L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))。

其中的“”讀為“或”（也有使用“+”代替“”的）；“”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復連接）。在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為“”、“”、“”。連接符“”一般可省略不寫?！啊?、“”和“”都是左結合的。23例令={a，b}，上的正規(guī)式和相應的正規(guī)集的例子有：正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意個a的串}(ab) {,a,b,aa,ab……所有由a 和b組成的串}(ab)(aabb)(ab) {上所有含有兩個相繼 的a或兩個相繼的b組成 的串}24例={l，d}，r=l(ld)定義的正規(guī)集:{l,ll,ld,ldd,……}（標識符）例={d，.，e，+，-},則上的正規(guī)式d(.dd)(e(+-)dd)表示的是無符號數的集合。其中d為0~9的數字。舉例25例:2={A,B,0,1},則(A|B){A|B|0|1}5是2上的正則表達式(A|B){A|B|0|1}5的值，即

L((A|B){A|B|0|1}5)，是這樣一個正則集，每個字符串都是以字母A或B打頭，后跟以至多5個字母（A或B）或數字（0或1）(0|1)(0|1)*∑上的“數”的全體26正規(guī)式的運算律設r,s,t為正規(guī)式，正規(guī)式服從的代數規(guī)律有：1。rs=sr “或”服從交換律2。r(st)=(rs)t “或”的可結合律3。(rs)t=r(st) “連接”的可結合律4。r(st)=rsrt (st)r=srtr 分配律5。r=r,r=r 是“連接”的恒等元素6。rr=r r=rrr…

“或”的抽取律

27程序中的單詞都能用正規(guī)式來定義令l為a~z的字母，d為0~9的數字e1=l(l|d)* e1表示標識符集合e2=dd* e2表示無符號整數注(比較)： <標識符>→l｜l<字母數字><字母數字>→l｜d｜l<字母數字>｜d<字母數字>

正規(guī)式比正規(guī)文法更容易讓人理解單詞是按怎樣的規(guī)律構成的，且可以從某個正規(guī)式自動地構造識別程序。28兩個正規(guī)式等價若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價,寫作e1=e2。例如：e1=(ab)，e2=ba又如：b(ab)=(ba)b

(ab)=(ab)293.正規(guī)文法和正規(guī)式間的轉換等價性：對任意一個正規(guī)文法，存在一個定義同一語言的正規(guī)式對任意一個正規(guī)式，存在一個定義同一語言的正規(guī)文法30將∑上的一個正規(guī)式r轉換成文法G=(VN,VT,S,P)VT=∑,首先形成產生式S→r,S為G的開始符不斷利用下面的規(guī)則做變換,直到每個產生式最多含有一個終結符為止原產生式變換后產生式規(guī)則1A→xyA→xBB→y規(guī)則2A→x*yA→xAA→y規(guī)則3A→x|yA→xA→y其中B為一新非終結符31例:將R=a(a|d)*轉換成相應的正則文法令轉換成文法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 最終有產生式：S→aA，A→ε，A→aA，

A→dA32將正規(guī)文法轉換成正規(guī)式將每條產生式改寫為正規(guī)式用代入法解正規(guī)式方程組最后只剩下一個開始符號定義的正規(guī)式,其中不含非終結符正規(guī)文法到正規(guī)式的轉換規(guī)則:文法產生式正規(guī)式規(guī)則1A→xBB→yA=xy規(guī)則2A→xA|yA=x*y規(guī)則3A→xA→yA=x|y33例：將文法G[S]轉換成正規(guī)式

G：S→aA|aA→dA|d先由產生式得: 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

§3.3有窮自動機（FiniteAutomata）1.狀態(tài)轉換圖2.確定有窮狀態(tài)自動機（DFA）3.非確定有窮狀態(tài)自動機（NFA）4.把NFA變?yōu)镈FA5.DFA的化簡351.正規(guī)文法和狀態(tài)轉換圖正規(guī)文法定義了3型語言，常見的單詞可由正規(guī)文法定義。狀態(tài)轉換圖可用于識別3型語言；它是設計和實現掃描器的一種有效工具，是有限自動機的直觀圖示36由正規(guī)文法構造狀態(tài)轉換圖程序設計語言的單詞都能用正規(guī)文法描述；例如，標識符可定義為

<標識符><標識符>字母<標識符><標識符>數字

<標識符>字母若把字母、數字視為終結符，則上述產生式為（左線性）正規(guī)文法若我們用d表示0-9間的數字，則C語言的<無符號數>的文法也是（右線性）正規(guī)文法（見P48）一般說來，凡能用正規(guī)文法描述的語言，均可由某種有限狀態(tài)算法——狀態(tài)轉換圖進行分析。狀態(tài)轉換圖由有限個結點所組成的有向圖。每個結點代表在識別分析過程中掃描器所處的狀態(tài)，其中含有一個初始狀態(tài)和若干個終態(tài)。在圖中，狀態(tài)用圓圈表示，終態(tài)用雙層圓圈表示。狀態(tài)之間可用有向邊連接，其上標記一字符a，表示從有向邊的射出狀態(tài)出發(fā)，識別一字符a后，將進入箭頭所指狀態(tài)（結點）371)由右線性文法構造狀態(tài)轉換圖設G=(VN,VT,P,S)是一右線性文法,并設|VN|=K,則所要構造的狀態(tài)轉換圖共有K+1個狀態(tài)(結點).用VN中的每個符號分別標記其中的K個結點,且令G的開始符S為初態(tài)結點;余下的一個結點作為終態(tài)結點,用F(VN)標記.我們用如下規(guī)則來連接這K+1個結點:(1)對于G中產生式AaB,從結點A引一有向邊到結點B,并用a標記這一有向邊;(2)對于G中產生式Aa,從結點A引一有向邊到終態(tài)結點F,并用a標記這一有向邊;(3)對于G中產生式A(若有的話),則將結點A設為終態(tài).例如,P48中定義的無符號數的文法對應的~為(化簡后):0452136dddddd.E+|-Edd38利用狀態(tài)轉換圖識別符號串的方法對于已給的字符串w=a1a2…an,aiVT,利用~對w

識別的步驟如下:(1)從初始狀態(tài)S出發(fā),自左至右逐個掃描w的各個字符(當前為a1),此時在結點S所射出的諸矢線中,尋找標記為a1的矢線(若不存在,則表明w有語法錯誤),讀入a1并沿矢線所指方向前進,過渡到下一狀態(tài)(設為A1).(2)設當前處在Ai狀態(tài),所掃描的字符為ai+1,在結點Ai所射出的諸矢線中,尋找標記為ai+1的矢線(若不存在,則表明w有語法錯誤),讀入ai+1,并進入狀態(tài)Ai+1;(3)重復(2),直到w中所有字符被讀完且恰好進入終態(tài)F時,宣告整個識別結束,w可被接受.顯然,若我們從初態(tài)出發(fā),分別沿一切可能的路徑到達終態(tài)結點,并將中徑中矢線上所標記的字符依次連接起來,便得到狀態(tài)轉換圖所能識別的全部符號串,這些符號串組成的集合構成了該~識別的語言39狀態(tài)轉換圖與文法推導用狀態(tài)轉換圖識別符號串w的過程，就是為w建立一個推導S*w的過程。在第一步（在初始狀態(tài)S下，掃描到a1而過渡到下一狀態(tài)A1），由狀態(tài)轉換圖的構造規(guī)則可知，G中必有產生式Sa1A1;對于識別過程的后續(xù)步驟，由狀態(tài)Ai識別ai+1后過渡到Ai+1恰好對應了使用產生式Aiai+1Ai+1,…,最后在狀態(tài)An-1識別an后到達終態(tài)F，對應了使用產生式 Aan 進行推導：

Sa1A1a1a2A2……a1a2…an-1An-1a1a2…an40右線性文法與狀態(tài)轉換圖設G是一右線性文法,M是相應的狀態(tài)轉換圖,則從前面的討論可以看出如下事實：(1)在利用M對符號串w進行識別時,M中每次狀態(tài)的轉換都模擬了一步直接推導,即識別方法(或稱分析方法)是“”的;(2)因右線性文法只有形如AaB、Aa的產生式，所以推導的每一步所得句型只含一個非終結符，所以推導的規(guī)范的，每步所得的句型也必為規(guī)范句型；(3)對于M所識別的任一符號串x,必存在G中的一個推導S*x(即有xL(G);反之,對于L(G)中任一句子y,必存在一條從初態(tài)S到終態(tài)F的路徑,此路徑上各矢線的標記依次拼接起來所組成的符號串恰為y412)由左線性文法構造狀態(tài)轉換圖設G=(VN,VT,P,S)是一左線性文法,構造相應的狀態(tài)轉換圖的方法是:首先用G的VN符標記M的結點,其中,開始符S對應的結點為終態(tài)結點.另外,再引入一個新結點R(VN)作為初態(tài).矢線的連接規(guī)則為:(1)對于G中形如Aa

的產生式,引矢線:RA,且標記為a;(2)對于G中形如ABa

的產生式,引矢線BA,且標記為a.42由左線性文法構造狀態(tài)轉換圖的例子已給文法G=({S,U},{0,1},{SS1|U1,UU0|0},S)RUSU00UU00SU11SS11用左線性文法構造出的狀態(tài)轉換圖來識別文法的句子,其過程與前面右線性文法構造的狀態(tài)轉換圖用法一樣,這里不再贅述.不過,就識別的方法而言,它卻屬于“”分析.我們以句子00011為例,給出其識別的的步驟.見右表.步驟當前狀態(tài) 余留的符號串1 R 000112 U 00113 U 0114 U 115 S 16 S (識別結束)43識別符號串與歸約由構造狀態(tài)轉換圖的方法可知,從初態(tài)R到下一狀態(tài)A的轉換,對應了形如Ba

的產生式,即將終結符a歸約成非終結符B;類似地,從狀態(tài)B轉換到狀態(tài)A,對應了形如ABa的產生式,即將Ba歸約為A;如此下去,直到從某狀態(tài)A轉換到狀態(tài)S(終態(tài)),對應了形如SAa的產生式,即將Aa歸約為開始符S.此時歸約成功,也恰好進入了終態(tài),即狀態(tài)轉換圖識別了(或接受)該符號串.前面識別00011的例子對應的歸約過程見右圖00011UUUSS44對句子ababaaa的分析步驟當前狀態(tài)輸入的其余部分

SababaaaAbabaaaBabaaaAbaaaBaaaAaaZaZababaaaABABAZZ(a)分析過程(b)語法樹45詞法規(guī)則的描述狀態(tài)轉換圖難于書寫，非線性結構更好的方式的要求線性方式表達與狀態(tài)轉換圖等價正規(guī)表達式[a-z][a-z|0-9]*462.有窮自動機(也稱有限自動機)是一種識別裝置作用:能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合意義:為詞法分析程序的自動構造尋找特殊的方法和工具。分類:

確定的有窮自動機

(DeterministicFiniteAutomata)

不確定的有窮自動機

(NondeterministicFiniteAutomata)47確定的有限自動機DFA1）抽象地看,狀態(tài)轉換圖由五個部分組成:(1)有限個狀態(tài)之集,記作K;(2)有限個輸入符號組成的字母表,記作;(3)從K到K的轉換函數

f:KK.f(p,a)=q表示若當前狀態(tài)為p,且輸入符號為a,則進入下一個狀態(tài)為q;(4)S0K,初始(開始)狀態(tài);(5)若干個終態(tài)之集:Z(K)由上述五個要素組成的五元式M=(K,,f,S0,Z)稱為一個確定的有限自動機

(DFA:DeterministicFiniteAutomata)由此可見,一DFA實際上是狀態(tài)轉換圖的形式描述(數學定義),狀態(tài)轉換圖是DFA的幾何(圖形)表示.“確定”即狀態(tài)轉換函數是單值函數！48DFA的接受集2）為定義DFA所接受(或識別)的符號串集合,我們先將其轉換函數f的定義域拓廣到K*:(1)f^(s,)=s,sK;(2)f^(s,aw)=f^(f(s,a),w),sK,a,w*;由上面的定義可知,對于x*,f^(s,x)=t

的含義是,當M從狀態(tài)s出發(fā),依次掃描完x的各個符號后將進入狀態(tài)t.即只要f有定義,f^與f的效果是一致的.我們稱DFAM接受(或識別)某符號串x*,用狀態(tài)轉換圖來說,就是從初態(tài)S0出發(fā),經一恰好標有x的路徑后可達到某終態(tài)SZ

;用f^描述就是: SZ,f(S0,x)=S

M的接受集我們把一DFAM所接受的符號串的全體稱為M的接受集,記為L(M),即L(M)={x|f(S0,x)Z,x*}49確定的有限自動機我們之所以把前面定義的有限自動機稱為確定的FA，是因為在狀態(tài)轉換的每一步，根據FA當前的狀態(tài)及掃描的輸入字符，便能唯一地確定FA的下一狀態(tài)。在轉換圖上看，若||=n，則任何結點所引出的矢線至多有n條，且矢線上的標記均不同。例如，P51圖3-4所對應的DFA為M=({R,U,S},{0,1},f,R,{S})

其中，f的定義如下：f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S由DFA與狀態(tài)轉換圖的關系可知，構造狀態(tài)轉換圖的算法，同樣適用于構造DFA。實際上，我們可以證明，正規(guī)文法G，DFAM，使 L(M)=L(G)，反之亦然。50從狀態(tài)轉換圖構造有窮狀態(tài)自動機例如：從下面狀態(tài)圖構造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 abSABabZbaa51運行DFA與識別一個字符串定義：對于某DFAD=（K,Σ,M,S,F），如果M(S，t)=P,P∈F，則稱符號串t可被DFAD所接受。運行一個DFA的過程：識別一個符號串是否被接受52舉例如前例：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)=Z53正則集正則集：L(D)，是一個DFA接受的字符串集合正則語言與正則集：L(G)=L(D)最小狀態(tài)自動機：狀態(tài)個數最少，唯一54DFA的矩陣表示法字符狀態(tài)abSABabZbaa矩陣行代表狀態(tài)，列代表輸入字符，矩陣元素是映像得到的新狀態(tài)。553.非確定的有限自動機若在一左線性文法中含有多個右部相同的產生式，如 AUaBUaCUaXUa,或在一右線性文法中同時含有形如 UaAUaBUaCUaX的產生式，在相應的狀態(tài)轉換圖中，就會出現這樣的結點U，它具有多條標記為同一輸入符號a的矢線，如右圖所示圖3-8NFA的狀態(tài)轉換圖由上圖可知，在U狀態(tài)下，輸入符號為a時，FA的下一狀態(tài)不唯一，而是在狀態(tài)集{A,B,C,…,X}中任選其一。具有這種性質的FA稱為非確定的FA（NFA:Nondeterministic

FA）UABCXaaaa...56非確定有限自動機的定義在形式上，NFAM同樣可用五元式定義：M=(K,,f,S0,Z)，其中，K,,S0,Z的含義同DFA,轉換函數f的定義為

f:K(K),即將(Si,aj)映射到K的一個子集{Sk1,…,Skm}

類似地，我們可把f的定義域拓廣到K*

：(1)f^(S,)={S};(2)f^(S,aw)=f^(f(S,a),w)a,w*.再設f(S,a)=

{Sk1,…,Skm},且定義這樣，我們已把f的定義域擴大到(K)*。根據類似的理由，我們將對f和f^不加區(qū)分57NFA的接受集對于x*,若集合f(S0,x)中含有Z中的元素（終態(tài)），則說明，至少存在一條從初態(tài)S0到某一終態(tài)的路徑，此路徑上的符號之連接恰為x，此時，我們稱x為M所接受所有為M所接受的符號串之集稱為NFAM的接受集（或識別集），記作L(M).即L(M)={x|f(S0,x)Z,x}例3.1

給定M=({S,A,B,C},{a,b},f,S,{C}),其狀態(tài)轉換圖見右。由圖可知M是一NFA。M識別符號串ababb的路徑為S(a)A(b)B(a)A(b)B(b)C(接受)。(參見書中P60的表)SABCaa,babbaa注意，NFA識別輸入符號串時有一個試探過程，為了能走到終態(tài)，往往要走許多彎路（帶回溯），這影響了FA的效率。能否提高其工作效率就是我們下一小節(jié)討論的課題。事實上，對任一NFAM，總可構造一個DFAM’，使L(M’)=L(M)成立。這就是NFA與DFA的等價性。58DFA與NFA的區(qū)別DFANFA開始狀態(tài)唯一一個或多個映像單個狀態(tài)狀態(tài)集合59舉例前述文法G3.2對應的自動機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}abSABabZbaaaa60舉例(字符串被NFA所接受)對于輸入字符串babbabb，運行NFA步驟當前狀態(tài)輸入的其余部分可能的后繼選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZabABabZbaaaaS61運行NFA運行NFA：識別一個字符串是否被NFA所接受，是否能達到終態(tài)集合中的某個狀態(tài)實質：用自底向上方法識別句子狀態(tài)轉換的下一狀態(tài)不唯一，如何解決？62DFA和NFA的關系對于Σ*上的字符串β，如果存在一條從初態(tài)到終態(tài)的通路，且這條通路上的輸入字符恰好連接成β，稱為β可以此DFA、NFA識別DFA、NFA都可以識別一個字符集Σ上的字符串可以用DFA、NFA定義Σ上的字符串的集合DFA都是NFA、NFA可化為等價的DFA63構造與正規(guī)式等價的NFA方法XYααα|β12αβ12643αεε1αβ32αβ1221α*1265構造與正規(guī)式等價的NFA示例a(a|b)*XYa(a|b)*XYa1(a|b)*66XYa1(a|b)2XYa1a2bεεεε674.NFA的確定化方法初態(tài)的唯一化終態(tài)的唯一化從初態(tài)集開始，求對于每個輸入符號的后繼狀態(tài)集合Si——新的狀態(tài)對每個Si，求對于每個輸入符號的后繼狀態(tài)集合Si+1直到不產生新的后繼狀態(tài)集合含有終態(tài)的狀態(tài)集合為終態(tài)68舉例例:為NFAN=({S,A,B,Z},{a,b},M,{S},{Z})構造DFA.

設它對應的DFAN’=(K’,{a,b},M’,[S],F’)abSABabZbaaaaK’={[S]}M([S],a)=[A]M([S],b)=[B]K’={[S],[A],[B]}M([A],a)=[Z]M([A],b)=[B]M([B],a)=[AB]M([B],b)=[Z]K’={S],[A],[B],[Z],[AB]}M([Z],a)=[AZ]M([Z],b)=φM([AB],a)=[ABZ]M([AB],b)=[BZ]K’={S],[A],[B],[Z],[AB],[AZ],[BZ],[ABZ]}M([AZ],a)=[AZ]M([AZ],b)=[B]M([BZ],a)=[ABZ]M([BZ],b)=[Z]M([ABZ],a)=[ABZ]M([ABZ],b)=[BZ]

69舉例（續(xù)1）

輸入狀態(tài)ab[S][A][B][A][Z][B][B][AB][Z][Z][AZ][AB][ABZ][BZ][AZ][AZ][B][BZ][ABZ][Z][ABZ][ABZ][BZ]abSABabZbaaaa根據左邊狀態(tài)轉換矩陣，可以得到DFAN’的狀態(tài)集合（表的左列狀態(tài)），即K’={[S],[A],[b],[Z],[AB],[AZ],[BZ],[ABZ]}70舉例（續(xù)2）SBABABZAZBZAZbbbbbbbaaaaaaaa開始狀態(tài):[S]終止狀態(tài):[Z],[AZ],[BZ],[ABZ]

根據上面狀態(tài)轉換矩陣，同時可以得到N’的映像函數，根據該映像可以畫出它的狀態(tài)轉換圖（如下）。終態(tài)集合中的元素為：由新映像得到的狀態(tài)、且這些狀態(tài)包含原NFAN的終態(tài)集合中的狀態(tài)。71NFA的確定化示例狀態(tài)轉換矩陣 a bX{1,2,Y} {}1{2,Y} {2,Y}2{2,Y} {2,Y}Y{} {}XYa1a2bεεa(a|b)*72 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)轉換矩陣1)(2)(3) a

b1) (2) (2) (3) (3)(3) (3) (3)等價的DFA狀態(tài)轉換矩陣73 a b1) (2) (2) (3) (3)(3) (3) (3)13aabab274NFA確定化的例子M=({S0,S1},{a,b},f,S0,{s1})S0S1abba|b_f_|_a____b___S0|{S0,S1}{S1}S1|{S0,S1}M’=(K’,{a,b},f’,[S0],{[S1],[S0,S1]})f’|ab.|newstate[]|[][]|[S0]|[S0S1][S1]|1[S1]|[][S0S1]|2[S0S1]|[S0S1][S0S1]|3123abb|ab75具有動作的FA若在一FA中,允許對也作狀態(tài)轉移,則這樣的FA稱為具有動作的FA(NFA).此時,有的矢線上標記為標記為的矢線對識別符號串無影響,但卻改變了當前的狀態(tài).例如,右圖中的FA中,從狀態(tài)0到狀態(tài)3存在路徑:0(a)0(a)0()2(c)2(c)2()3,即M識別了aacc=aacc.~的定義

M=(K,,f,S0,Z),其中,f的定義為f:K({})(K).在~中,可以視為一個輸入符號,在矩陣表示中,也有相應的列.0123abbcf也可以拓廣到f’:K*(K).f’(S,x)是由這樣的狀態(tài)Q組成,存在從S到Q的路徑,該路徑上的連線標記組成的符號串恰好為x,其中,允許有有限個標記為76狀態(tài)S的-閉包：-CLOSURE(S)為定義拓廣的f’,我們首先引入每個狀態(tài)S的-閉包的定義： -CLOSURE(S),它是從S出發(fā)經過若干標記為的矢線所能達到的全部狀態(tài)之集，其歸納定義如下：(1)S-CLOSURE(s);(2)設Sj-CLOSURE(S),且SjSk,則Sk-CLOSURE(S);(3)有限地使用規(guī)則（2）所得的集合為-CLOSURE(S).例，在上頁的NFA中，-CLOSURE(0)={0,1,2,3} -CLOSURE(1)={1} -CLOSURE(2)={2,3} -CLOSURE(3)={3}.進一步，-CLOSURE還可定義在-CLOSURE:(K)(K)，設QK(Q(K))，則77轉換函數f的拓廣利用-CLOSURE(S)，可定義f’如下：78f與f’的區(qū)別由f’的定義可知，f’(S,a)

與f(S,a)

不同，f’(S,a)是從S出發(fā)經過路徑a據達的狀態(tài)集（可走若干步）；而f(S,a)是從S出發(fā)經過矢線a所達狀態(tài)之集（只走一步）其實，

f(S,a)-CLOSURE(f(S,a))f’(S,a)

只走一步a矢線

|多步，第一步必須走a矢線

|路徑a：第一步可以是矢線例如，在前面的NFA中，f’(0,)=-CLOSURE(0)={0,1,2,3}f(0,)={1,2}f’(0,a)={0,1,2,3} f(0,a)={0}-NFA的接受集：L(M)={w|f’(S0,w)Z}79-NFA的用途：構造更復雜的FA有了-NFA，就可把識別各種不同單詞的FA用矢線（并連）連接起來，組成一個單一的NFA，經確定化后可得識別所有單詞的DFA，由此可設計編譯程序的詞法分析器。例如，某語言的單詞有：1.BEGIN 2.END 3.IF 4.THEN 5.ELSE6.標識符 7.無符號整數 8.< 9.<= 10.= 11.<> 12.> 13.>=我們可容易地分別構造出識別各類單詞的FA,然后將其合并為一個大FA,如書中P65圖3-11所示(由于較難描繪,這里略去,請自行參閱教材)80ε閉包狀態(tài)集I的ε_CLOSURE(I)如果q屬于Iq屬于ε_CLOSURE(I)從q出發(fā)經任意條ε弧到達的任何狀態(tài)q’都屬于ε_CLOSURE(I)81具有動作的NFA的確定化設已給具有動作的NFAM=(K,,f,S0,Z),構造相應的DFAM’=(K’,,f’,q0,Z’)的方法是，先令q0=[-CLOSURE(S0)],然后對每個a，令[-CLOSURE(f’(q0,a))]為新狀態(tài)，如此反復，直到無新狀態(tài)產生：1.令K’={[-CLOSURE(S0)]};f’=;2.對K’中尚未被標記的狀態(tài)qi=[Si1,Si2,…,Sim]: (1)標記qi; (2)對于每個a,令Ta=f({Si1,Si2,…,Sim},a);qj=[-CLOSURE(Ta)]; (3)若qjK’,則令K’=K’{qj}; (4)令f’=f’{f’(qj,a)=qj};3.重復2.,直到K’中無未標記的狀態(tài);4.令Z’={qj|qjZ}(這里把qj

視為集合)82確定化具有動作的NFA的例子例3.4考慮前面引入的具有動作的NFA的例子(P63圖3-10)1.q0=[0,1,2,3]==>K’;2.q0未標記,故(1)標記q0;(2)令f”(q0,a)=[-CLOSURE(f’(q0,a))]=q0; f”(q0,b)=[-CLOSURE(f’(q0,b))]=[1,3]=q1;q1==>K’; f”(q0,c)=[2,3]=q2;q2==>K’;3.此時,K’={q0,q1,a2},q1,q2arenotmarked.so,(1)markq1;(2)letf”(q1,a)=[-CLOSURE(f’(q1,a))]=; f”(q1,b)=…=q1; f”(q1,c)=…=;4.q2isnotmarked,so(1)markq2;(2)f”(q2,a)=f”(q2,b)=; f”(q2,c)=q2;K’isnotincreasedandallstatesaremarked.Z’={q0,q1,q2}q1q0q2abbcc83手工計算確定化的方法在人工進行NFA確定化時,可按下述的構造矩陣的方法實現:_____________|abc_q0:[0123]|[0123][13][23]q1:[13]|[][13][]q2:[23]|[][][23]需要說明的是,本算法也適合于不含產生式的NFA的確定化.例3.5

對于書中圖3-13所示的NFA利用上述算法所得的DFA如P67圖3-13所示.其中,圓圈中的數字是原NFA的狀態(tài)編號,在圖3-13中,q0={0,1,7,11,14,19,24,26,28,30,33,35,40}.標有“#”的狀態(tài)為特殊狀態(tài),在該狀態(tài)下,若遇非弧線上出現的字符,則轉到狀態(tài)25.845.DFA的化簡狀態(tài)的等價性能夠識別相同的字符串劃分為終態(tài)和非終態(tài)兩個子集如果某個子集中的狀態(tài)是可區(qū)分的，則進一步劃分這個子集直到在每個子集內，各個狀態(tài)都是不可區(qū)分的。同一子集內的狀態(tài)合并。85DFA狀態(tài)數的最小化對于一DFA來說,其狀態(tài)數可能并不是最小的.原因是DFA中有些狀態(tài)是“等價”的.為得到效率高的DFA,需將這些“等價”狀態(tài)合并,這就是DFA的最小化.DFAM的最小化:構造等價的DFAM’其狀態(tài)數達到最小.可區(qū)分狀態(tài):設s,tK,s,t由某w*所區(qū)分iff (f(s,w)Zf(t,w)Z)(f(s,w)Zf(t,w)Z)若w*,f(s,w)Zf(t,w)Z,則稱s與t等價(不可區(qū)分)在一DFA中,等價狀態(tài)可合并.86DFA最小化算法基本思想:將M的狀態(tài)集K逐步地進行劃分加細,以期將K劃分為滿足等價關系的等價類,使得在同一類中的狀態(tài)不可區(qū)分;在不同類中的狀態(tài)可區(qū)分.算法如下:1.先將狀態(tài)集K劃分為兩個子集Z和K-Z,顯然分屬于這兩個集合的狀態(tài)是可(被)區(qū)分的.記={Z,K-Z}.2.設當前的劃分中已含有m個子集:={I1,I2,…,Im},其中,屬于不同子集的狀態(tài)是可區(qū)分的,而屬于同一子集中的狀態(tài)則待區(qū)分.現對每個子集Ii={Si1,Si2,…,Sin}中的各狀態(tài)Sir(SirK,1rn)進行考查,看其是否可區(qū)分.若存在a,使得Su=f(Sip,a)Ij,Sv=f(Siq,a)Ik

則由假設,Su和Sv被子某個w所區(qū)分,進一步,Sip

和Siq

可被aw

區(qū)分:f(Sip,aw)=f(Su,w)屬于Z而f(Siq,aw)=f(Sv,w)不屬于Z(或反之),即Siq

與Sip

可區(qū)分.將Ii細分,使其落入不同的更小的子集中.得到新劃分new.

（細分Ii的方法見下頁）。3.若new.不等于,則令

=new.

轉2.4.對于最終的，從每個劃分塊中任選一狀態(tài)為代表，構成K‘，S0的代表為初態(tài)。若IiZ，則Ii

的代表Z’；將引入(出)非代表的矢線引向代表.87DFA最小化的例子1.={{0,1,2,3},{4}}{0,1,2,3}a={1}未區(qū)分;{0,1,2}b={2,3},{3}b={4},所以3與0,1,2可區(qū)分;={{0,1,2},{3},{4}}2.{0,1,2}a={1},未區(qū)分;{0,2}b={2},{1}b={3},1與0,2可區(qū)分;={{0,2},{1},{3},{4}};3.{0,2}a={1},{0,2}b={2}不可區(qū)分,new=.結束.0123aaababbb定理3.2

最小狀態(tài)數的DFA在同構意義下是唯一的.01324aaaaabbbbb88DFA化簡的例子設有一個DFAM=(K，，f，S，Z)，其狀態(tài)圖如下圖所示。對其進行化簡。21ba03abbaab89DFA的化簡示例 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ū)分，應簡化為{1,2}9013aabab21a2ab化簡前的DFA化簡后的DFA91練習字母表{a,b}上所有含有aa或bb的字符串組成的集合用正規(guī)式表達為(a|b)*(aa|bb)(a|b)*92(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)931Y(a|b)*0a2(aa|bb)3bεε1Y(a|b)*0a2aa3bεεbb941Y(a|b)*0a2a3bεεb45ab951YXa2a3bεεb45ab6baεε96狀態(tài)轉換矩陣

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}97

a b0 1 21 3 22 1 43） 3 54） 6 45） 6 46） 3 5

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}98DFA的最小化一定可以區(qū)分的兩個集合用e表示出錯狀態(tài)非終止狀態(tài)集{0,1,2}——不認識ε終止狀態(tài)集{3,4,5,6}——認識ε{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}內不可區(qū)分99最小化的DFA a b0 1 21 3 22 1 33 3 3 100顯然DFA是NFA的特例。對于每個NFA

M，存在一個DFA

M`，使得L（M）=L（M`）。對于任何兩個有窮自動機M和M`，如果

L（M）=L（M`），則稱M與M`是等價的。對每個NFA

N存在著與之等價的DFA

M。與某一NFA等價的DFA不唯一。

§3.4NFA與DFA的等價性101§3.5正規(guī)文法與有窮自動機之間的轉換設右線性文法G=(VN，VT，P，S)，下面介紹將其轉換成有窮自動機M=(K，，f，S0，Z)，使得L(G)=L(M)的方法。令K=VNZ，Z是M中新增的終態(tài)；=VT，S0=S；f由下列方法確定：對于G的每條形如AaB的規(guī)則，在M中設轉換函數f(A,a)=B；對于G的每條形如Aa的規(guī)則，在M中設轉換函數f(A,a)=Z。102例對于正規(guī)文法G[S]：SaB|bBBbS|a|b，可以轉換成自動機M=(K，，f，S0，Z)，其中：K={S，B，Z}，={a，b}，S0=S，Z={Z}，f為：

f(S,a)=B，f(S,b)=B，f(B,b)=S，

f(B,a)=Z，f(B,b)=Z。這是一個NFA。對應的狀態(tài)圖如下：SaBZbbab103有窮自動機轉換成右線性文法若有限自動機是NFA則將其確定化，設確定的有窮自動機M=(K，，f，S0，Z)，則轉換得到右線性文法G=(VN，VT，P，S)，其中：VN=K，VT=，S=S0，P中的規(guī)則用如下方法確定：對M中任一形如f(A,a)=B的轉換函數，有規(guī)則AaBP；對M中的終態(tài)Z，則加一條規(guī)則ZP。104左線性文法轉換成自動機的方法設左線性文法G=(VN，VT，P，S)，有窮自動機M=(K，，f，S0，Z)，則M中的K=VNS0，S0

是M中新增的初態(tài)；=VT，Z={S}；f由下列方法確定：對于G的每條形如ABa的規(guī)則，在M中設轉換函數f(B,a)=A；對于G的每條形如Aa的規(guī)則，在M中設轉換函數f(S0,a)=A。105設左線性文法G[S]：SSa|Aa|BbABa|aBAb|b，則按照上述方法構造的有窮自動機為M=(K，，f，S0，Z)，其中：K={S0，A，B，S}，={a，b}，Z={S}，f為：

f(S,a)=S，f(A,a)=S，f(B,b)=S，f(B,a)=A，

f(S0,a)=A，f(A,b)=B，f(S0,b)=B。其對應的狀態(tài)圖如下：baS0BSAabaab106

§3.6詞法分析程序的設計主要內容：詞法分析設計考慮的問題詞法分析程序的流程107詞法分析設計考慮的問題程序的預處理刪除源程序的無用字符濾掉源程序中的注釋進行宏替換實現文件包含命令和條件編譯命令嵌入處理保留字（關鍵字）的識別與查表算法單詞的識別與超前搜索108詞法分析程序流程使用狀態(tài)圖設計詞法分析程序的步驟對程序設計語言的單詞按類構造相應的狀態(tài)圖。合并各類單詞的狀態(tài)圖，構成一個能識別程序語言所有單詞的狀態(tài)轉換圖。具體方法：將各類單詞的狀態(tài)圖的初態(tài)合并為唯一的初態(tài)；化簡沖突和狀態(tài)編號；增加出錯處理終態(tài)。對狀態(tài)圖每一個終點編寫一段相應的語義子程序。109例設一程序設計語言有下列單詞組成：

關鍵字：int，for，if，while，cout，cin，do；標識符：<標識符><標識符>字母|<標識符>數字|字母；

無符號整數：<無符號整數><無符號整數>數字|數字；

運算符或界符：=，*，>，+，++，{，}。11010字母|數字3*2其它字母數字567101113*4其它*8其它9+數字=*+>{}其它12111詞法分析程序流程圖開始濾掉空格是字母?讀標識符查保留字表查到否?保留字類碼syYY返回是字母?取數Y整數類碼sy數值NUM標識符類碼

sy標識符ID是界符?界符或運算符類碼sy出錯處理NNYNN112詞法分析程序的實現詞法分析程序的構造方法詞法分析程序的編寫113構造詞法分析程序的方法用手工方式，即根據識別語言單詞的狀態(tài)轉換圖，使用某種高級語言，例如，C語言直接編寫詞法分析程序。利用自動生成工具LEX自動生成詞法分析程序。114詞法分析程序實現中

要考慮的問題確定實現詞法分析程序的執(zhí)行方式確定屬性字的結構緩沖區(qū)預處理，超前搜索,關鍵字的處理，符號表的實現查找效率，算法的優(yōu)化實現詞法錯誤處理115屬性字詞法分析程序對說明部分不做語義處理。詞法分析程序輸出屬性字一般采用下面的形式：（符號類，符號值）屬性字是符號的機內表示，有統(tǒng)一固定的長度116關鍵字的識別與查表算法對于關鍵字，先把它們當成標識符，然后去查關鍵字表。若在表中查到，則為關鍵字，獲取相應的類別碼；否則，認為是標識符。查找算法：線性查找折半查找Hash函數117出錯處理對定義外的（如，對首字符不是字母的，不是數字的，不是運算符和分界符的）單詞進行出錯處理。118詞法分析中使用的數據字符表：（字母表）列出源程序中所有可能的字符。特定符號與機內表示表：一切特定符號與相應編碼。標識符表：登錄一切源程序中出現的一切標識符。此表的序號作為屬性字的值。常數表：登錄一切源程序中出現的常數。此表的序號作為屬性字的值。119使用狀態(tài)圖設計詞法分析程序多數語言的詞法規(guī)則可用正則文法和正則表達式來描述。正則文法或正則表達式定義的語言都可以被狀態(tài)圖識別。使用狀態(tài)圖設計詞法分析程序的步驟如下：對程序設計語言的單詞按類構造相應的狀態(tài)圖。（這里把關鍵字與標識符作為一類）合并各類單詞的狀態(tài)圖，增加一個出錯處理終態(tài)，構成一個識別該語言所有單詞的狀態(tài)轉換圖對狀態(tài)圖的每一個終點編一段相應的子程序。120201字母字母|數字其它3456數字數字其它+-78*/9101113<=>:;1617其它13=舉例121詞法分析程序的結構取字符子程序取符號子程序，一般有如下約定：進入子程序時，已經取到當前符號的一個字符。離開子程序時，已經取到其后繼字符。查造標識符表子程序查造常量表子程序查符號機內表示對照表子程序122詞法分析程序的自動生成（Lex)LEX是由美國Bell實驗室的M.Lesk和Schmidt于1975年用C語言研制的一個詞法分析程序的自動生成工具。對任何高級程序語言，用戶必須用正規(guī)表達式描述該語言的各個詞法類（這一描述稱為LEX的源程序），LEX就可以自動生成該語言的詞法分析程序。LEX及其編譯系統(tǒng)的作用如圖。123圖LEX及其編譯系統(tǒng)的作用124一個LEX源程序由用“%%”分隔的三部分組成：第一部分為正規(guī)式的輔助定義式，第二部分為識別規(guī)則，最后一部分為用戶子程序。其書寫格式為：輔助定義式

%%

識別規(guī)則

%%

用戶子程序125

其中，輔助定義式和用戶子程序是任選的，而識別規(guī)則是必需的。如果用戶子程序缺省，則第二個分隔符號“%%”可以省去；但如果無輔助定義式部分，第一個分隔符號“%%”不能省去，因為第一個分隔符號用于指示識別規(guī)則部分的開始。126下面給出一個簡單語言的單詞符號的LEX源程序例子，其輸出單詞的類別編碼用整數編碼表示。

AuxiliaryDefinitions /*輔助定義*/letter→A∣B∣C∣…∣Z∣a∣b∣c∣…∣zdigit→0∣1∣2∣3∣…∣9%%RecognitionRules /*識別規(guī)則*/1271while {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)