編譯原理電子教案第三章詞法分析（lexicalanalysis）謝強計算機科學與技術學ieqiang@.con2本章的主要內容詞法分析器的設計要求狀態轉換圖正規表達式有限自動機正規式、正規文法、有限自動機的等價性確定有限自動機的化簡詞法分析器的自動產生（了解）3本章要求知識點：詞法分析程序的功能及構造方法，正規表達式與正規集，正規表達式與正規文法，狀態轉換圖與基本符號的識別，有限自動機。深刻理解：正規表達式，有限自動機，正規文法以及三者之間的等價性；確定的有限自動機和非確定的有限自動機之間的等價性。熟練掌握：（1）對于某一正規集，寫出其正規表達式，構造其非確定的有限自動機、確定的有限自動機，并將其最小化；（2）對于某一正規集，寫出正規表達式，構造自動機，然后構造正規文法。4本章教學線索1詞法分析程序的設計1.1詞法分析程序的功能1.2詞法分析程序作為一個獨立子程序2詞法分析器的設計3狀態轉換圖4正規表達式與有限自動機5確定有限自動機的化簡6詞法分析程序的自動構造工具LEX簡介51.1詞法分析程序的功能

詞法分析的任務：從左到右逐個字符地對源程序進行掃描，產生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號串的中間程序。詞法分析器源程序單詞符號6單詞符號關鍵字、標識符、常數、（運）算符、界符；詞法分析器輸出單詞符號的表示

（單詞種別，單詞符號的屬性值）單詞種別通常用整數編碼。詞類編碼提供給語法分析程序使用；單詞自身的屬性值提供給語義分析程序使用。具體的分類設計以方便語法分析程序使用為原則。單詞分種策略標識符一般統規為一種；常數則宜按類型（整、實、布爾等）分種；關鍵字可以將全體視為一種，也可以一字一種；運算符可采用一字一種，一個將具有共性的運算符視為一種。界符一般采用一字一種。71.2詞法分析程序作為一個獨立子程序（1）語法分析程序的子程序；（2）組織成一遍掃描。（為什么？）復雜問題分解，模塊化設計，使得整個編譯程序的結構更簡潔、清晰。由于詞法分析程序相對于語法分析程序來說要簡單得多，如果把詞法分析和語法分析合在一起將會導致語法分析程序變得非常復雜，并且使編譯程序的執行效率變得很低。8詞法分析語法分析語義分析和中間代碼生成源程序中間代碼符號表管理錯誤的診查處理9whilei＜＞jdoifi＞jthen

i:＝i-jelsej:=j-i‘while’，‘i’，‘＜＞’，‘j’，‘do’，‘if’，‘i’，‘＞’，‘j’,‘then’,'i',':=’,'i',’-’,'j','else','j',':=','j','-',‘i'詞法分析器〈while，——〉〈id，指向i的符號表入口的指針〉〈relational－op，NE〉〈id，指向j的符號表入口的指針〉〈do，——〉〈if，——〉〈id，指向i的符號表入口的指針〉〈id，指向j的符號表入口的指針〉例子：10本章教學線索1詞法分析程序的設計2詞法分析器的設計2.1輸入、輸出預處理2.2單詞符號的識別（P40—41）3狀態轉換圖4正規表達式與有限自動機5確定有限自動機的化簡6詞法分析程序的自動構造工具LEX簡介112.1輸入、輸出預處理（1）去除掉空白符、跳格符、回車符和換行符等編輯性字符；（2）去除程序中的注釋符；（3）掃描緩沖區122.2單詞符號的識別（P40—41）超前搜索問題關鍵字的識別標識符的識別常數的識別算符和界符的識別13本章教學線索1詞法分析程序的設計2詞法分析器的設計3狀態轉換圖3.1狀態轉換圖的概念3.2構造識別一種簡單語言的單詞符號的轉換圖4正規表達式與有限自動機5確定有限自動機的化簡6詞法分析程序的自動構造工具LEX簡介143.1狀態轉換圖的概念狀態轉換圖是一張有限方向圖，在狀態轉換圖中，結點代表狀態，用圓圈表示。狀態之間用箭弧連結。箭弧上的標記（字符、正規式）代表在射出結點（即箭符始結點）狀態下可能出現的輸入字符或字符類。一張狀態轉換圖只包含有限個狀態（即有限個結點），其中含有一個初態（用雙線箭頭指示）和若干個終態（用雙圈表示），而且實際上至少要有一個終態，初態表示分析的開始，終態表示分析的結束。一個狀態轉換圖可用于識別（或接受）一定的字符串。15012*字母其它字母或數字圖A—識別標識符的轉換圖012*數字其它圖B—識別整數的轉換圖數字017*其它圖C—識別Fortran實型常數的轉換圖23456數字數字數字其它+或-E或D數字E或D··數字數字數字163.2構造識別一種簡單語言的單詞符號的轉換圖限制條件：（1）所有關鍵字都是“保留字”，用戶不得使用它們作為自己定義的標識符。（2）關鍵字作為一類特殊的標識符來處理，不再專門設置對應的轉換圖，把它們預先安排在一張表格中，當轉換圖識別出一個標識符，就去查詢這張表，確定是否為一個關鍵字。（3）如果關鍵字、標識符和常數之間沒有確定的運算符或界符作間隔，則必須至少用一個空白符作間隔2**38*121311非*空白字母非字母與數字字母或數字數字數字非數字=+*...，（）其它1819本章教學線索1詞法分析程序的設計2詞法分析器的設計3狀態轉換圖4正規表達式與有限自動機4.1正規式與正規集4.2確定有限自動機（DFA）4.3非確定有限自動機NFA4.4DFAM和NFAM的等價性4.5正規文法與有限自動機的等價性4.6正規式與有限自動機的等價性5確定有限自動機的化簡6詞法分析程序的自動構造工具LEX簡介204.1正規式與正規集4.1.1正規式與正規集的定義（概念）（1）ε、Φ都是∑上的正規式，它們所表示的正規集分別為{ε}和Φ；（2）任何a∈∑，a是∑上的一個正規式，它所表示的正規集為{a}；（3）如果U、V都是∑上的正規式，它們所表示的正規集分別記為L（U）和L（V），那么，（U|V）、（U*V）和（U）*也是正規式，它們所表示的正規集分別為L（U）∪L（V）、L（U）L（V）和（L（U））*；僅由有限次使用上述步驟而得到的表達式才是∑上的正規式；僅由這些正規式所表示的字集才是∑上的正規集。21例子：令∑={a，b}，下面是∑上的正規式和相應的正規集正規式正規集ba*∑上所有以b為首后跟任意多個a的字a(a|b)*∑上所有以a為首的字（a|b）*

(aa|bb)(a|b)*∑上所有含有兩個相繼的a或兩個相繼的b的字224.1.2正規式的數學運算交換律：U|V=V|U；結合律：U|（V|W）=（U|V）|W、U（VM）=（UV）W；分配律：U（V|W）=UV|UW（V|W）|U=VU|WUε連接：εU=Uε=U23另外一種定義方法：定義正規表達式（regularexpression）是以下的一種：基本（basic）正規表達式由一個單字符a（其中a在字母表∑中），以及元字符ε或元字符Φ組成。在第1種情況下，L(a)={a}；在第2種情況下，L(ε)={ε}；在第3種情況下，L(Φ)={}。r|s格式的表達式：其中r和s均是正規式。在這種情況下，L（r|s）=L（r）∪L（s）。rs格式的表達式：其中r和s是正規式。在這種情況下，

L（rs）=L(r)L（s）。r*格式的表達式：其中r是正規表達式。在這種情況下，L（r*）=L（r）*。（r）格式的表達式：其中r是正規式。在這種情況下，L（（r））=L（r），因此，括號并不改變語言，它們只調整運算的優先權。24需要注意：｜的優先權最低，連結次之，*則最高。另外還注意到在這個定義中，5個符號|、*、*、（和）都有了元字符的含義。正規式的連接一般不滿足交換律254.2確定有限自動機（DFA）4.2.1確定有限自動機的定義

一個確定有限自動機（DFA）M是一個五元式：M=（S，∑，δ，s0，F），其中：S是一個有限集，它的每個元素稱為一個狀態；∑是一個有窮字母表，它的每個元素稱為一個輸入字符；δ是一個從Sx∑至S的單值部分映射。δ（s，a）=s′，意味著：當現行狀態為s、輸入為字符a時，將狀態轉換到下一個狀態s′。我們稱s′為s的一個后繼狀態。s0∈S，是唯一的初態。FS，是一個終態集（可空）。264.2.2DFA的矩陣表示及狀態轉換圖表示行表示狀態列表示輸入字符矩陣元素表示δ（s，a）的值。這個矩陣稱為狀態轉換矩陣。例子：M=（{0，1，2，3}，{a，b}，δ，0，{3}）其中δ為：δ(0，a)=1δ(0，b)=2δ(1，a)=3δ(1，b)=2δ(2，a)=1δ(2，b)=3δ(3，a)=3δ(3，b)=327對應的狀態轉換矩陣：狀態ab012132213333一個DFA也可以表示成一張（確定的）狀態轉換圖：δ(0，a)=1δ(0，b)=2δ(1，a)=3δ(1，b)=2δ(2，a)=1δ(2，b)=3δ(3，a)=3δ(3，b)=31023ababa，bab28確定有限自動機（DFA）的三種表示形式1）狀態轉換函數2）狀態轉換矩陣3）狀態轉換圖開始狀態一般狀態終態狀態轉換圖節點的三種形式294.2.3有限自動機DFAM接受的語言從狀態轉換函數來看：如果對所有α∈Σ*，以下述方式遞歸擴張δ的定義：δ（s，ε）＝s，δ(s，αa）＝δ（δ（s，α），a）（ａ∈Σ，s∈S），則有Ｌ（Ｍ）＝｛α｜α∈Σ*，若存在s∈Ｆ，使δ（s0，α）＝s｝對上例的DFAM和w=baa，δ（0，baa）=δ（2，aa）=δ(1，a）=3（注意：其中0代表0態，1表示1態，2表示2態，3表示3態）30從狀態轉換圖來看：對于Σ*上的任何字α，如果存在一條從初態結點到某一終態結點的通路，且這條通路上所有弧的標記符連接成的字等于α，則稱α可為DFAM所識別（讀出或接受），如果M的初態結點同時又是終態結點，則空字ε可為DFAM所識別。DFAM所能識別的字的全體記為L(M)。課后例子：給出接受下列在字母表{0，1}上的語言的DFA：所有以00結束的串的集合；（1|0）*00所有具有三個0的串的集合。1*01*01*01*314.2.4DFA的程序模擬DFAM=（K，Σ，f，S，Z）的行為的模擬程序K=S；c=getchar;whilec<>eofdo{K=f(K,c);c=getchar;};ifKisinZthenreturn(‘yes’)Elsereturn(‘no’)324.3非確定有限自動機NFA一個非確定有限自動機NFAM是一個五元式：M=(S，Σ，δ，S0，F)其中：S是一個有限集，它的每個元素稱為一個狀態；∑是一個有窮字母表，它的每個元素稱為一個輸入字符；δ是一個從Sx∑*至S的子集的映射，即δ：Sx∑*→2s（S集合的冪集/S的所有子集的集合）S0S，是一個非空初態集。FS,是一個終態集（可空）。33對于∑*中的任何一個字α，若存在一條從某一初態結點到某一終態結點的通路，且這條通路上所有弧的標記字依序連接成的字（忽略那些標記為ε的弧）等于α，則稱α可為NFAM所識別（讀出或接受）。若M的某些結點既是初態結點又是終態結點，或者存在一條從初態結點到某一終態結點的ε通路，那么，空字ε可為M所接受。例子：識別所有含有相繼兩個a或相繼兩個b的字NFA。5X12346Yaaaabbbbεεεε344.4DFAM和NFAM的等價性定理：對于每個NFAM存在一個DFAM′，使得L(M)=L(M′)證明思想：用M′的一個狀態對應M的一個狀態集合，用這種方法，能從一個NFAM構造一個DFAM′使得L（M′）=L（M），這種方法稱作子集構造法。354.4.1狀態集的ε閉包定義設I是有限自動機的狀態集的子集，I的ε閉包ε_CLOSURE(I)為：(1)如果狀態q∈I，則q∈ε_CLOSURE（I）（既I中的狀態全部屬于ε_CLOSURE(I)）(2)如果狀態q∈I，那么從狀態q出發經過任意ε弧而能到達的任何狀態q′都屬于ε_CLOSURE(I)。（注意：可以連續經過多條ε弧）364.4.2有限自動機的轉移函數假定I是非確定有限自動機的狀態集的子集，則定義：

Ia=ε_CLOSURE(J)

其中：a∈Σ，J是從I中的某一狀態結點出發經過一條a弧而達到的狀態結點的全體。

374.4.3從NFAM構造DFAM的步驟（方法）（1）設NFAM=<S，Σ，δ，S0，F>，對M的狀態圖進行改造：引進新的初態結點X和終態結點Y，且X，Y?S，從X到S0中任意狀態結點連一條ε箭弧，從F中任意狀態結點連一條ε箭弧到Y；對M中的狀態圖進行下圖所示的替換，其中k是新引進的狀態。重復這種分裂過程直到狀態圖中的每條箭弧上的標記或為ε，或為Σ中的單個字母。將最終得到的NFA記為M′，顯然L（M′）=L（M）ijikjABABijA|BijA*ijAB

ikjεεA38（2）將非確定有限自動機M′轉換成確定有限自動機M"

方法：假設Σ={a1，a2，a3，…，ak}，構造狀態轉化表，表的構成：a)每一行包含k+1列，首行首列為ε_CLOSURE(X)；b)如果每行的第一列假定為I，則該行的i+1列為Iai(i=1，2，…，k)。然后檢查該行的所有狀態子集，將未曾在第一列出現的填入到后面空行的第一列。c)重復上述b)，直到出現在表的第i+1列上的所有狀態子集均在第一列中出現。d)將構造出來的表視為狀態轉換表，將其中的每個狀態子集視為新的狀態，顯然該表唯一的刻畫了一個DFAM"，該有限自動機的初態為該表的首行首列，終態為那些包含原終態的狀態子集。顯然L(M")=L(M')=L(M)39例子：p50正規式（a|b）*（aa|bb）（a|b）*對應的NFA如例3.3中圖。其中X為初態，Y為終態。狀態轉換矩陣如下表：

IJIaJIb{X,5,1}{5,3}{5,3,1}{5,4}{5,4,1}{5,3,1}{5,3,2}{5,3,1,2,6,Y}{5,4}{5,4,1}{5,4,1}{5,3,1}{5,4,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1,6,Y}X5126Y34εεεεababaabb40轉換成狀態轉換矩陣：（將第一列從上向下編號）

sab0121322153344655656340123564abababababbaba41312ababaBSAbabCaa，baaIaIb{S}{A,C}Φ{A,C}{A,C}{A,B}{A,B}{A,C}{A,B}42a，bSAaa，bbb132babIaIb{S}{S,A}{A}{S,A}{S,A}{S,A}{A}Φ{S,A}43124εbaεεb3cASBccabbIaIbIc{1，2，3，4}{1，2，3，4}{2，4}{3，4}{2，4}Φ{2，4}Φ{3，4}ΦΦ{3，4}444.5正規文法與有限自動機的等價性正規文法與有限自動機的等價性結論：對每個右線性正規文法GR或左線性正規文法GL，都存在一個有限自動機（FA）M，使得：L（M）=L（G）對每一個FAM，都存在一個右線性正規文法GR和左線性正規文法GL，使得：L（M）=L（GR）=L（GL）右線性正規文法：A→αB或A→α,α∈VT*，A，B∈VN左線性正規文法：A→Bα或A→α,α∈VT*，A，B∈VN45證明1：右線性正規文法GR同有限自動機的等價性（1）設右線性正規文法GR=<VT，VN，S，P>。將VN中的每一非終結符號視為狀態符號，并增加一個新的終結狀態符號f，f?VN。構造有限自動機M=<VN∪{f}，VT

，δ，S，{f}>，其中狀態轉換函數δ定義如下：如果對某個A∈VN且a∈VT∪{ε}，P中有產生式A→a，則令δ（A，a）=f。對任意A∈VN且a∈VT∪{ε}，設P中左端為A，右端第一符號為a的所有產生式為：A→aA1|aA2|…|aAk（不包含：A→a）則令：δ（A，a）={A1，A2，…，AK}顯然，上述的自動機M為一非確定有限自動機（NFA）（為什么是非確定）。46（2）設左線性正規文法GL=<VT，VN，S，P>，將VN中的每一符號視為狀態符號，并且增加一個初態符號q0，q0VN。 令M=<VN∪{q0}，VT，δ，q0，{S}>，其中狀態轉換函數可以由以下規則定義：若對某個A∈VN及a∈VT∪{ε}，P中有產生式A→a，則令δ（q0，a）=A對任意的A∈VN及a∈VT∪{ε}，若P中所有右端第一符號為A，第二符號為a的產生式為：A1→Aa，A2→Aa，A3→Aa，…，Ak→Aa。則令δ（A，a）={A1，A2,…,Ak}q0AaAA1A2Ak…aaa47證明2：有限自動機同正規文法的等價性設DFAM=<S，Σ，δ，s0，F>，構造右線性正規文法：（1）若s0?F，令GR=<Σ，S，s0，P>，其中P的產生式集合如下定義：對任何a∈Σ及A，B∈S，若有δ（A，a）=B則：當B?F時，令A→aB；當B∈F時，令A→a|aB；對于w∈Σ*，不妨設w=a1a2…ak，其中ai∈Σ(i=1,…,k)。若s0w，則存在一個最左推導:s0?a1A1?

a1a2A2?…?a1…aiAi?…?a1a2…ak，因而，在M中有一條從s0出發依次經過A1，…，Ak-1，達到終態的通路，該通路上所有箭弧依次標記為a1，a2，…，ak。反之亦然。所以：w∈L(GR)當且僅當w∈L(M)。48（2）當s0∈F，因為δ(s0，ε)=s0，所以ε∈L(M)。但ε不屬于上面構造的GR產生的文法L(GR)。但是：L(GR)=L(M)-{ε}。所以在上面的GR中添加新的非終結符號s0′(s0′?S)和產生式s0′→s0|ε,并用s0′代替s0作開始符號。這樣修正后的文法GR′仍然是右線性正規文法，并且L(GR′)=L(M)。注意：構造左線性正規文法，將終態視為開始符號，P的定義如下：對任何a

及A1，A2VN,有(A1，a)=A2,則

(a)A1是初態，A2a|A1a(b)A1不是初態,A2A1a

如果有多個終態，需要引入新終態，將原來的終態連接到新終態，箭符上的標記符為ε，將新的終態作為左線性正規文法的開始符號，其產生式為f′→f1|f2|…

49綜合例子：P52~53

DFAM=<{A,B,C,D},{0,1},δ,A,B>ADBC0,1000111504.6正規式與有限自動機的等價性包含兩方面的含義：（1）對于任何有限自動機M，都存在一個正規式r，使得L(r)=L(M)；（2）對于任何正規式r，都存在一個有限自動機M，使得L(M)=L(r)

正規文法、正規式、確定有限自動機和非確定有限自動機在接受語言的能力上是一致的。51證明1：對于Σ上的NFAM，構造Σ上的正規式r，使得L(r)=L(M)；對M的狀態轉換圖進行改造：在M中加入兩個結點X、Y。從X用ε弧連接到M的所有初態結點；從M的所有終態結點用ε連接到Y，從而形成一個新的NFA，記為M′，它只有一個初態X和一個終態Y。顯然，L(M)=L(M′)。按下列方式消除M′中的所有結點，直至只剩X和Y。

123V1V2ij12V1V2ijV1|V2V1V2123V1V3V2ijV1V2*V352證明2：有Σ上的正規式r，構造一個NFAM（M只有一個終態，并且沒有從終態出發的箭弧）方法：對r中運算符數目進行歸納證明：(運算符：|，*,*)(1)若r具有0個運算符，則r=ε，r=Φ，r=a，a∈Σ，下圖的三個有限自動機顯然符合要求。q0q0qfq0qfa對應ε的狀態轉換圖(q0既是初態又是終態)對應Φ的狀態轉換圖（初態到終態沒有通路）對應a的狀態轉換圖Thopmson

方法53（2）設結論對少于i(i≥1)個運算的正規表達式r成立。當r有i個運算時，有三種情況：a)r=r1|r2，r2中的運算符個數少于k。由歸納假設，對ri存在Mi=<Si，Σi，δi，qi，fi>，使得L(Mi)=L(ri)，并且Mi沒有從終態出發的箭弧（i=1,2）。設S1∩S2=Φ，在S1∪S2中加入新狀態q0，f0。設M=<S1∪S2∪{q0，f0}，Σ1∪Σ2，δ，q0，f0>，其中δ定義為：(a)δ（q0，ε）={q1，q2}；(b)δ（q，a）=δ1（q，a），當q∈S1–{f1}，a∈Σ1∪{ε}；

(c)δ（q，a）=δ2（q，a），當q∈S2–{f2}，a∈Σ2∪{ε}；

(d)δ（f1，ε）=δ（f2，ε）={f0}M的狀態轉換圖中不難看出，M中有一條從q0到f0的通路w，當且僅當在M1中有一條從q1到f1的通路w或者在M2中有一條從q2到f2的通路w，即：L(M)=L(M1)∪L(M2)=L(r1)∪L(r2)=L(r)q0M1q1f1M2q2f2f0εεεε54b)r=r1r2。Mi同a)設M=<S1∪S2，∑1∪∑2，δ，q1，{f2}>δ:(a)δ（q，a）=δ1（q，a），當q∈S1–{f1}，a∈Σ1∪{ε}；(b)δ（q，a）=δ2（q，a），當q∈S2–{f2}，a∈Σ2∪{ε}；(c)δ（f1，ε）={q2}c)r=r1*。設M1同a)設M=<S1∪{q0，f0}，∑1，δ，q0，{f0}>，其中q0,f0?S1，δ:(a)δ（q0，ε）=δ（f1，ε）={q1，f0}；(b)δ（q，a）=δ1（q，a），當q∈S1–{f1}，a∈Σ1∪{ε}

M1q1f1q0f0εεεε

M2

M1q1f1q2f2ε55Thompson方法所構造的NFA的狀態數和轉換較多。可以采用下面方法減少之：

R=R1|R2R1R2

R=R1R2R1R2

R=R1*R1

RRR156本章教學線索1詞法分析程序的設計2詞法分析器的設計3狀態轉換圖4正規表達式與有限自動機5確定有限自動機的化簡6詞法分析程序的自動構造工具LEX簡介575確定有限自動機的化簡1)確定的有限自動機的化簡一個DFAM=(，S，，s0，F)的化簡是指尋找一個狀態數比較少的DFAM′，使L(M)=L(M′)。而且可以證明，存在一個最少狀態的DFAM′，使L(M)=L(M′)。2)等價狀態的定義設s，tS，若對任何w

*，(s，w)F當且僅當(t，w)F，則稱s和t是等價狀態。否則，稱s和t是可區別的。（即假定s和t是M的兩個不同狀態，如果從狀態s出發能夠讀出某個字而停于終態，同樣從t出發也能讀出某個字而停于終態，稱s和t是等價的，如果