編譯原理第三章：詞法分析

第三章詞法分析3.1對于詞法分析器的要求3.2詞法分析器的設計3.3正規(guī)表達式與有限自動機3.4詞法分析器的自動產(chǎn)生

復習題3.1對于詞法分析器的要求

一、詞法分析器的功能和輸出形式1.詞法分析器的功能輸入源程序，輸出單詞符號2.單詞符號單詞符號：一個程序語言的基本語法符號3.單詞符號輸出形式二元式（單詞種別，單詞符號屬性值）二元式（單詞種別，單詞符號屬性值）i.單詞種別

標識符

一種

常數(shù)

一種，整數(shù)、實數(shù)、布爾用整數(shù)編碼

關(guān)鍵字

全體視為一種或一字一種

算符

一符一種

界符

一符一種

ii.單詞符號屬性值

如果一個種別只含一個單詞符號，那么，對于這個單詞符號，種別編碼就完全代表它自身了。若一個種別含有多個單詞符號，那么，對于它的每個單詞符號，除了給出種別編碼之外，還應給出有關(guān)單詞符號的屬性信息。

單詞符號屬性是指單詞符號的特性或特征，屬性值則是反應特性或特征的值。二、詞法分析器作為一個獨立子程序在實現(xiàn)編譯程序時，常將詞法分析程序從語法分析中獨立出來，這樣做有什么好處？可使編譯程序結(jié)構(gòu)更簡潔，清晰和條理化可用更有效的特殊方法和工具進行處理/改進編譯程序的效率有利于集中力量考慮其他枝節(jié)問題/增強編譯程序的可移植性3.2詞法分析器的設計一、輸入、預處理任務：（1）建立輸入緩沖區(qū)，輸入源程序到緩沖區(qū)（2）預處理剔除一些無用的空白符、跳格符、回車符、換行符等編輯性字符（3）將預處理結(jié)果送掃描緩沖區(qū)預處理可作為一個子程序完成上述三個任務，并被詞法分析器調(diào)用，每調(diào)用一次，它就處理出一串確定長度（如120個字符）的輸入字符，并送進掃描緩沖區(qū)。二、掃描器——詞法分析的主要部分掃描器的構(gòu)造原理設置兩個指示器（起點指示器、搜索指示器），一個可以互補使用的一分為二的掃描緩沖區(qū)，一個指向當前正在識別的單詞的開始位置（指向新單詞的首字符），另一個用于向前搜索以尋找單詞的終點，掃描緩沖區(qū)總長度為2×120個字符，掃描器單詞長度的要求是單詞長度≤1/2掃描緩沖區(qū)長度。2．掃描器的工作原理調(diào)用預處理子程序，把120個輸入字符裝進掃描緩沖區(qū)的某半?yún)^(qū)，搜索指針從起點指針開始向前尋找單詞的終點，若在該半?yún)^(qū)內(nèi)查找到單詞的終點，便輸出二元式，再把起點指針移到此處的后一個字符，繼續(xù)搜索下一個單詞，如果在搜索到該半?yún)^(qū)的邊緣，尚未到達單詞終點，那么就調(diào)用預處理子程序，把后續(xù)的120個字符裝進另半?yún)^(qū)，繼續(xù)搜索。三、狀態(tài)轉(zhuǎn)換圖-設計詞法分析器的好工具（好途徑）1．轉(zhuǎn)換圖是一張有限方向圖

結(jié)點

代表狀態(tài)，用圓圈表示。

箭弧

狀態(tài)之間的連接，箭弧上的標記（字符）代表

在射出結(jié)點狀態(tài)下可能出現(xiàn)的輸入字符或字符類。

初態(tài)

識別出某一類字符串的開始，初態(tài)只有一個。

終態(tài)

識別出某一單詞，至少有一個。用雙圈表示。一個狀態(tài)轉(zhuǎn)換圖可用于識別（或接受）一定的字符串如：（1）識別標識符

（2）識別整數(shù)（3）2.狀態(tài)轉(zhuǎn)換圖的實現(xiàn)——如何由圖寫出程序·最簡單辦法是讓每個狀態(tài)結(jié)點對應一小段程序·作為實現(xiàn)轉(zhuǎn)換圖的基本成份，要引進一組全局變量和過程（1）ch

字符變量，存放最新讀進的源程序字符（2）strToken

字符數(shù)組，存放構(gòu)成單詞符號的字符串（3）GetChar

將下一個輸入字符讀到ch中，搜索指示器前移一字符位置（4）GetBC

檢查ch中的字符是否為空白，若是，則調(diào)用Getchar直至ch中進入一個非空白字符（5）Concat

將ch中字符連接到strToken之后

（6）IsLetter和IsDigit

分別判斷ch中字符是否為字母和數(shù)字（7）Reserve對StrToken中字符串查找保留字表，若它是一個保留字返回它的編碼，否則返回0

（8）Retract將搜索指示器回調(diào)一個字符位置,將ch置為空白字符（9）InsertId

將strToken中標識符插入符號表，返回符號表指針（10）InsertConst

將strToken中常數(shù)插入常數(shù)表，返回常數(shù)表指針（11）DTB把strToken中數(shù)字串譯成標準二進制碼，并作為函數(shù)值返回（十進制轉(zhuǎn)換為二進制）（12）Ainput

輸入源程序（鍵盤直接輸入或以文件形式輸入）·由狀態(tài)轉(zhuǎn)換圖編寫掃描器的一般方法3.3正規(guī)表達式與有限自動機

一、正規(guī)式與正規(guī)集

二、確定有限自動機（DFA）

三、非確定有限自動機（NFA）

四、確定有限自動機的化簡3.3正規(guī)表達式與有限自動機一、正規(guī)式與正規(guī)集1．正規(guī)式與正規(guī)集的遞歸定義（1）ε和?都是∑上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和?（2）任何a∈∑，a是∑上的一個正規(guī)式，它所表示的正規(guī)集為{a}（3）假定U和V都是∑上的正規(guī)式，它們所表示的正規(guī)集分別記為L(U)和L(V)，那么（U|V），（U·V）和（U）*也都是正規(guī)式.它們所表示的正規(guī)集分別為L(U)∪L(V),L(U)·L(V)和(L(U))*

僅由有限次使用上述步驟而得到的表達式才是∑上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是∑上的正規(guī)集2．優(yōu)先順序*

·

|例3．1令∑={a,b},下面是∑上的正規(guī)式和相應的正規(guī)集正規(guī)式正規(guī)集

ba*∑上所有以b為首后跟任意多個a的字

a(a|b)*∑上所有以a為首的字

(a|b)*(aa|bb)(a|b)*∑上含有兩個相繼的a或二個相繼的b的字例3．2令∑={A,B,0,1},則正規(guī)式正規(guī)集(A|B)(A|B|0|1)*∑上的”標識符”的全體(0|1)(0|1)*∑上”數(shù)”的全體3.正規(guī)式的相等（等價）若兩個正規(guī)式所表示的正規(guī)集相同，則這兩個正規(guī)式等價

U=VL（U）=L（V）如：b(a|b)*=(ba)*b(a|b)*=(a*b*)*4.運算規(guī)律

(1)U|V=V|U交換律

(2)U|(V|W)=(U|V)|W結(jié)合律

(3)U(VW)=(UV)W結(jié)合律

(4)U(V|W)=UV|UW分配律

(V|W)U=VU|WU(5)εU=Uε=U二、確定有限自動機（DFA）1.定義一個確定的有限自動機（DFA）M是一個五元式M=（S,∑,δ,s0,F）

其中：

S是一個有限集，它的每個元素稱為一個狀態(tài)

∑是一個有窮字母表，它的每個元素稱為一個輸入字符(3)δ是一個S×∑至S的單值部分映射，δ(s,a)=s’表示:當現(xiàn)行狀態(tài)為s，輸入字符為a時，將轉(zhuǎn)換到下一狀態(tài)s’，稱s’為s的一個后繼狀態(tài)(4)s0∈S,是唯一的初態(tài)(5)FS，是一個終態(tài)集（可空）2.表示形式（1）狀態(tài)轉(zhuǎn)換矩陣一個DFA可用一個矩陣表示，行表示狀態(tài)，列表示輸入字符，矩陣元素表示δ(s,a)的值。這個矩陣為狀態(tài)轉(zhuǎn)換矩陣例有（DFA）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)=3則狀態(tài)轉(zhuǎn)換矩陣

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

一個DFA可表示成一張（確定的）狀態(tài)轉(zhuǎn)換圖，假定DFAM含m個狀態(tài)和n個輸入字符，則這個圖含有m個狀態(tài)結(jié)點，每個結(jié)點頂多有n條箭弧射出和別的結(jié)點相連接，每條箭弧用∑中的一個不同輸入字符作標記。整張圖含有唯一的一個初態(tài)結(jié)點和若干個（可以是0個）終態(tài)結(jié)點。例:3.可識別

對于∑*中的任何字α，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路上所有弧的標識符連接成的字等于α，則稱α可為DFAM所識別（讀出或接受）。若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字ε可為M所識別（接受）。DFAM所能識別的字的全體記為L（M）。4.定理如果一個DFAM的輸入字母表為∑，則稱M是∑上的一個DFA，可以證明：∑上的一個字集V∑*是正規(guī)的，當且僅當存在∑上的DFAM，使得V=L（M）。三、非確定有限自動機（NFA）1．定義

一個非確定有限自動機（NFA）M是一個五元式M=（S，∑，δ，S0，F(xiàn)）其中：（1）S是一個有限集，它的每個元素稱為一個狀態(tài)（2）∑是一個有窮字母表，它的每個元素稱為一個輸入字符（3）δ是一個從S×∑*到S的子集的映照（多值映射）,可表示為S×∑*→2s,其中2s即S的所有子集的全體（4）S0S，是一個非空初態(tài)集（5）FS，是一個終態(tài)集（可空）2．表示形式狀態(tài)轉(zhuǎn)換圖一個含有m個狀態(tài)和n個輸入字符的NFA可表示成如下狀態(tài)轉(zhuǎn)換圖。該圖含有m個狀態(tài)結(jié)點，每個結(jié)點可射出若干條箭弧與別的結(jié)點相連接，每條弧用∑*中的一個字（不一定要不同的字且可以是空字）作標記（輸入字），整張圖至少含有一個初態(tài)結(jié)點以及若干個（可以是0個）終態(tài)結(jié)點，某些結(jié)點既可以是初態(tài)結(jié)點也可以是終態(tài)結(jié)點。3．可識別對于∑*中的任何一個字α，若存在一條從某一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標記字依序連接成的字等于α，則稱α可為NFAM所識別（讀出或接受）。若M的某些結(jié)點既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的ε的通路，那么空字可為M接受。

NFA所能識別的字也是所有含有相繼兩個a或相繼兩個b的字4.確定化定理（非確定有限自動機NFA確定化為有限自動機）對于每個NFAM存在一個DFAM″，使得L（M）=L（M″）證明：（1）假定NFAM=（S，∑，δ，S0，F(xiàn)），對M進行改造引進新的初態(tài)結(jié)點X和終態(tài)結(jié)點Y。X，YS

從X到S0中任意狀態(tài)結(jié)點連一條ε箭弧，從F任意狀態(tài)結(jié)點連一條ε箭弧到Y(jié)②（2）將M′進一步變換為DFA。確定化過程假定I是M′的狀態(tài)集的子集，定義I的ε閉包ε_CLOSURE(I)為：若q∈I，則q∈ε_CLOSURE（I）若q∈I，那么從q出發(fā)經(jīng)任意條ε弧而能到達的任何狀態(tài)q′都屬于ε_CLOSURE（I）；②假定I是M′的狀態(tài)集的子集，a∈∑，定義

Ia=ε_CLOSURE（J），其中，J是那些可以從I中的某一狀態(tài)結(jié)點出發(fā)經(jīng)過一條a弧而到達的狀態(tài)結(jié)點的全體

③假定∑={a1,………ak}，構(gòu)造一張表，此表每一行含有K+1列，置該表首行首列為ε_CLOSURE（X），一般而言，如果某一行的第一列的狀態(tài)子集已經(jīng)確定，例如記為I，那么，置該行的i+1列為Iai（i=1……k）。然后，檢查該行上的所有狀態(tài)子集，看它們是否已經(jīng)在表的第一列中出現(xiàn)，將未曾出現(xiàn)者重填入到后面空行的第一列，重復上述過程，直到出現(xiàn)在i+1列（i=1……k）上的所有狀態(tài)子集均已在第一列上出現(xiàn)，因為M′的狀態(tài)子集的個數(shù)是有限的，所以上述過程必定在有限步內(nèi)終止。我們將構(gòu)造出來的表視為狀態(tài)轉(zhuǎn)換表，將其中每個狀態(tài)子集視為新的狀態(tài)，顯然該表刻劃了一個DFAM″。初態(tài)是該表首行首列的那個狀態(tài)，終態(tài)是那些含有原終態(tài)的終態(tài)子集，根據(jù)上述構(gòu)造方法，得L（M″）=L（M′）=L（M）。上述把NFA確定化為DFA的方法稱為子集法5.舉例例3.4正規(guī)式（a|b）*(aa|bb)(a|b)*對應的NFA(1)構(gòu)造NFA(2)構(gòu)造狀態(tài)轉(zhuǎn)換矩陣

重新命名對應狀態(tài)轉(zhuǎn)換圖如下圖所示。其中0為初態(tài)，3,4,5和6為終態(tài)四、確定有限自動機的化簡一個確定有限自動機M的化簡是指：尋找一個狀態(tài)數(shù)比M少的DFAM′，使得L（M）=L（M′）1．狀態(tài)等價和可區(qū)別（1）狀態(tài)等價假設s和t是M的兩個不同狀態(tài)，若從狀態(tài)s出發(fā)能讀出某個字ω而停于終態(tài)，那么，同樣從t出發(fā)也能讀出同樣的字ω而停于終態(tài)，反之，若從t出發(fā)能讀出某個字ω而停于終態(tài)，則從s出發(fā)也能讀出同樣的字ω而停于終態(tài)，則稱s和t是等價的。（2）可區(qū)別若DFAM的兩個狀態(tài)s和t不等價，則稱s和t是可區(qū)別的。2.化簡（最少化）一個DFAM的狀態(tài)最少化過程旨在將M的狀態(tài)集分割成一些不相交的子集，使得任何不同的兩子集中的狀態(tài)都是可區(qū)別的，而同一個子集中的任何兩個狀態(tài)都是等價的，在每個子集中選出一個代表同時消去其它等價狀態(tài)分劃步驟：（1）初始分劃把S的終態(tài)與非終態(tài)分開

П={Z，S-Z}△{I(1),I(2)}（2）進一步分劃若某個時候Π已含m個子集，記Πm={I(1),I(2),…,I(m)}。并且屬于不同子集的狀態(tài)是區(qū)別的，檢查Πm中每個I(i)能否進一步分劃。對于某I(i)，令I(lǐng)(i)={q1,q2,…,qk}，若存在一個輸入字符a使得Ia(i)不全包含在現(xiàn)行Πm的某一子集I(j)中，將I(i)一分為二。若s1和s2經(jīng)a弧分別達到狀態(tài)t1和t2，而t1和t2屬于現(xiàn)行Πm的兩個不同子集。將I(i)分成兩半，使得一半含有s1：

I(i1)={s|s∈I(i1)且s經(jīng)a弧到達t1所在子集中的某狀態(tài)},

另一半含有s2：I(i2)=I(i)-I(i1)I(i1)中狀態(tài)與I(i2)中的狀態(tài)是可分別的，形成新的分劃。重復上述分劃過程，直至分劃中所含子集數(shù)不再增長為止。即每個子集中狀態(tài)是互相等價的，而不同子集中的狀態(tài)則是可互相區(qū)別的。（3）選代表對于最后分劃∏中的每一個子集，選取子集中的一個狀態(tài)代表其它狀態(tài)，I={q1,q2,…，qk}，挑選q1,凡導入到q2，…，qk的弧都改成導入到q1中，然后將q2，…，qk從原來的狀態(tài)集s中刪除。（4）經(jīng)如此化簡之后得到的DFAMˊ和原來的M是等價的，即L(M)=L(Mˊ)。解：1°初始分劃終態(tài)組{3，4，5，6}

非終態(tài)組{0，1，2}2°進一步分劃考察{3，4，5，6}{3，4，5，6}a={3，6}{3，4，5，6}{3，4，5，6}b={4，5}{3，4，5，6}

則{3，4，5，6}不能分劃5°選代表令狀態(tài)3代表{3，4，5