詞法分析程序的設(shè)計(jì)原則-單詞的描述技術(shù)-識(shí)別機(jī)制及詞法

詞法分析程序的設(shè)計(jì)原則，單詞的描述技術(shù)，識(shí)別機(jī)制及詞法分析程序的自動(dòng)構(gòu)造原理。第三章詞法分析及其自動(dòng)構(gòu)造

單詞的描述工具單詞的識(shí)別系統(tǒng)設(shè)計(jì)詞法分析程序,實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造回顧什麼是詞法分析程序?qū)崿F(xiàn)詞法分析（）的程序逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語(yǔ)言中具有獨(dú)立意義的最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行。也可以和語(yǔ)法分析結(jié)合在一起作為一遍，由語(yǔ)法分析程序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。詞法分析程序和語(yǔ)法分析程序的關(guān)系源程序詞法分析程序語(yǔ)法分析程序

….源程序詞法分析程序語(yǔ)法分析程序源程序詞法分析程序語(yǔ)法分析程序源程序詞法分析程序的主要任務(wù)：讀源程序，產(chǎn)生單詞符號(hào)詞法分析程序的其他任務(wù)：濾掉空格，跳過(guò)注釋、換行符追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序，宏展開(kāi)，……詞法分析工作從語(yǔ)法分析工作獨(dú)立出來(lái)的原因：簡(jiǎn)化設(shè)計(jì)改進(jìn)編譯效率增加編譯系統(tǒng)的可移植性

單詞的描述工具-正規(guī)表達(dá)式單詞的識(shí)別系統(tǒng)-有窮自動(dòng)機(jī)設(shè)計(jì)詞法分析程序,實(shí)現(xiàn)詞法分析程序的自動(dòng)構(gòu)造令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子

aab

(ab)(ab) a (ab) (ab)()(ab)正規(guī)式正規(guī)式也稱正則表達(dá)式,是定義正規(guī)集的數(shù)學(xué)工具。正規(guī)表達(dá)式（）是說(shuō)明單詞的模式()的一種重要的表示法（記號(hào)），我們用以描述單詞符號(hào)。令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子

aab

(ab)(ab) a (ab) (ab)()(ab){a}{}{}{}{,……任意個(gè)a的串}{……所有由a和b組成的串}

{上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串}

討論兩個(gè)例子例3.1令={l，d}，則上的正規(guī)式(ld)定義的正規(guī)集為:{,……},其中l(wèi)代表字母代表數(shù)字,正規(guī)式即是字母(字母|數(shù)字),它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”,就是和多數(shù)程序設(shè)計(jì)語(yǔ)言允許的的標(biāo)識(shí)符的詞法規(guī)則.例3.2={d，，e，+，-},則上的正規(guī)式d()(e(+-))表示的是無(wú)符號(hào)數(shù)的集合。其中d為0~9的數(shù)字。程序設(shè)計(jì)語(yǔ)言的單詞都能用正規(guī)式來(lái)定義.有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)(也稱有限自動(dòng)機(jī))作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)式所表示的集合.應(yīng)用有窮自動(dòng)機(jī)這個(gè)理論，為詞法分析程序的自動(dòng)構(gòu)造尋找有效的方法和工具。有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)()和不確定的有窮自動(dòng)機(jī)()。關(guān)于有窮自動(dòng)機(jī)我們將討論如下題目確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)的確定化的最小化確定的有窮自動(dòng)機(jī)定義：一個(gè)確定的有窮自動(dòng)機(jī)（）M是一個(gè)五元組：（K，Σ，f，S，Z）其中1是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2.Σ是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱Σ為輸入符號(hào)表；定義3是轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映射，即，如f（，a），（∈K，∈K）就意味著，當(dāng)前狀態(tài)為，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)，我們把稱作的一個(gè)后繼狀態(tài)；4∈K是唯一的一個(gè)初態(tài)；5K是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。一個(gè)的例子：（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定義為：f（S，a） f（V，a）f（S，b） f（V，b）f（U，a） f（Q，a）f（U，b） f（Q，b）的狀態(tài)圖表示bSUVQaaaba，bb的矩陣表示字符狀態(tài)0001∑*上的符號(hào)串t被M接受例：證明被下圖的所接受。f（S，）（f（S，b），）=f（V，）=f（f（V，a），）（U，）（f（U，a），b）（Q，b）Q屬于終態(tài)。得證。bSUVQabba,baa

M所能接受的符號(hào)串的全體記為L(zhǎng)(M).結(jié)論：上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的確定有窮自動(dòng)機(jī)M，使得(M)。的行為很容易用程序來(lái)模擬.（K，Σ，f，S，Z）的行為的模擬程序；;c<>{();;};KZ(‘’)(‘’)?={}

不確定的有窮自動(dòng)機(jī)定義K，，f，S，Z，其中K為狀態(tài)的有窮非空集，為有窮輸入字母表，f為K*到K的子集（2K）的一種映射，SK是初始狀態(tài)集，ZK為終止?fàn)顟B(tài)集.例子（{S，P，Z}，{0，1}，f，{S，P}，{Z}）其中f（S，0）={P}f（S，1）={S，Z}f（P，1）={Z}f（Z，0）={P}f（Z，1）={P}

狀態(tài)圖表示SPZ00,1111矩陣表示矩陣表示簡(jiǎn)化為具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)f為K*到K的子集（2K）的一種映射

12

3abc有如下定理:對(duì)任何一個(gè)具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)N，一定存在一個(gè)不具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)Ｍ，使得L(M)(N)。與上例等價(jià)的一個(gè).2acbb31acacbb類似,對(duì)K，，f，S，Z也有如下定義∑*上的符號(hào)串t在M上運(yùn)行..一個(gè)輸入符號(hào)串t，（我們將它表示成1的形式，其中T∈∑，t1∈∑*）在M上運(yùn)行的定義為：f（Q，1）（f（Q，T），t1）其中Q∈K.∑*上的符號(hào)串t被M接受若t∑*，f(S0，t)，其中S0∈S，PZ，則稱t為M所接受（識(shí)別）

∑*上的符號(hào)串t被M接受也可以這樣理解

對(duì)于Σ﹡中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為ε的弧)等于t，則稱t可為M所識(shí)別(讀出或接受)。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的道路,其上所有弧的標(biāo)記均為ε，那么空字可為M所接受。0001111100000010001100

M所能接受的符號(hào)串的全體記為L(zhǎng)(M)結(jié)論：上一個(gè)符號(hào)串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)上的不確定的有窮自動(dòng)機(jī)M，使得(M)。(0|1)*(000|111)(0|1)*確定有限自動(dòng)機(jī)和不確定有限自動(dòng)機(jī)是的特例.對(duì)每個(gè)N一定存在一個(gè)Ｍ，使得L(M)(N)。對(duì)每個(gè)N存在著與之等價(jià)的M。有一種算法，將轉(zhuǎn)換成接受同樣語(yǔ)言的.這種算法稱為子集法.與某一等價(jià)的不唯一.確定化算法:假設(shè)(K,0)按如下辦法構(gòu)造一個(gè)(S,0)，使得L(M)(N)：1.M的狀態(tài)集S由K的一些子集組成。用[S1S2...]表示S的元素，其中S1,S2,,...是K的狀態(tài)。并且約定，狀態(tài)S1,S2,,...是按某種規(guī)則排列的，即對(duì)于子集{S1,S2}={S2,S1,}來(lái)說(shuō)，S的狀態(tài)就是[S1S2]；2M和N的輸入字母表是相同的，即是；3轉(zhuǎn)換函數(shù)是這樣定義的： d([S1S2,...])=[R1R2...] 其中{R12,...,}=(({S1,S2,,...}))4S0=(K0)為M的開(kāi)始狀態(tài)；5{[...]，其中[...]S且{,,,...}}

定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：

1.狀態(tài)集合I的ε-閉包，表示為ε(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條ε弧而能到達(dá)的狀態(tài)的集合。狀態(tài)集合I的任何狀態(tài)S都屬于ε(I)。2.狀態(tài)集合I的a弧轉(zhuǎn)換，表示為()定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。狀態(tài)集合I的有關(guān)運(yùn)算的例子{1},(I)={1,2}；{5},(I)={5,6,2}；({1,2})={5,3,4}({5,3,4})={2,3,4,5,6,7,8}；12534687aa

a構(gòu)造N的狀態(tài)K的子集的算法：假定所構(gòu)造的子集族為C，即(T1,T2,,...),其中T1,T2,,...為狀態(tài)K的子集。1開(kāi)始，令(K0)為C中唯一成員，并且它是未被標(biāo)記的。2（C中存在尚未被標(biāo)記的子集T） { 標(biāo)記T； 每個(gè)輸入字母a { (())； U不在C中 將U作為未標(biāo)記的子集加在C中 } }的確定化例子4f35621i

aaaabbbb4f35621i

aaaabbbb等價(jià)的aCDBAEFSbaaaaabbbbbabF確定有窮自動(dòng)機(jī)的化簡(jiǎn)

說(shuō)一個(gè)有窮自動(dòng)機(jī)是化簡(jiǎn)了的，即是說(shuō)，它沒(méi)有多余狀態(tài)并且它的狀態(tài)中沒(méi)有兩個(gè)是互相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。所謂有窮自動(dòng)機(jī)的多余狀態(tài)，是指這樣的狀態(tài)：從自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒(méi)有通路到達(dá)終態(tài)。

的最小化就是尋求最小狀態(tài)最小狀態(tài)的含義:沒(méi)有多余狀態(tài)(死狀態(tài))沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）兩個(gè)狀態(tài)s和t可區(qū)別：不滿足兼容性——同是終態(tài)或同是非終態(tài)傳播性——從s出發(fā)讀入某個(gè)aa和從 t出發(fā)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。C和D同是終態(tài),讀入a到達(dá)C和F,C和F同是終態(tài),C和F讀入a都到達(dá)C,讀入b都到達(dá)E.C和D等價(jià)aCDBAEFSbaaaaabbbbbabF最小狀態(tài)對(duì)于一個(gè)M=（K,∑,k0)，存在一個(gè)最小狀態(tài)M’=（K’,∑’,k0’’)，,使L(M’)(M).結(jié)論接受L的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)是唯一的。“分割法”的最小化算法的核心把一個(gè)的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的.算法假定每個(gè)狀態(tài)射出的弧都是完全的,否則,引入一個(gè)新?tīng)顟B(tài),叫死狀態(tài),該狀態(tài)是非終態(tài)，將不完全的輸入弧都射向該狀態(tài)，對(duì)所有輸入，該狀態(tài)射出的弧還回到自己.的最小化算法M=（K,∑,k0,,),最小狀態(tài)M’1.構(gòu)造狀態(tài)的一初始劃分：終態(tài)和非終態(tài)兩組()2.對(duì)∏施用過(guò)程構(gòu)造新劃分∏3.如∏=∏,則令∏∏并繼續(xù)步驟4，否則∏∏重復(fù)2.4.為∏中的每一組選一代表，這些代表構(gòu)成M’的狀態(tài)。若k是一代表且f(),令r是t組的代表，則M’中有一轉(zhuǎn)換f’()M’的開(kāi)始狀態(tài)是含有S0的那組的代表M’的終態(tài)是含有F的那組的代表5.去掉M’中的死狀態(tài).過(guò)程:∏G∏

1GstGa,sta∏*,aa*/2G∏

的最小化—例子∏0:{}{}∏1:{} {} ∏2:CDBAEFSbaaaaaabbbbbba}{}{AS,BbB{{S}}DBASaaabbbbaa詞法分析程序的自動(dòng)構(gòu)造對(duì)有窮自動(dòng)機(jī)和正規(guī)表達(dá)式進(jìn)行了上述討論之后,我們介紹詞法分析程序的自動(dòng)構(gòu)造方法,這個(gè)方法基于有窮自動(dòng)機(jī)和正規(guī)表達(dá)式的等價(jià)性,即：1.對(duì)于∑上的一個(gè)M，可以構(gòu)造一個(gè)∑上的正規(guī)式R,使得L(R)(M)。2.對(duì)于∑上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)∑上的M，使的L(M)(R)。從Σ上的一個(gè)正規(guī)式R構(gòu)造Σ上的一個(gè)M，使得L(M)(R)的方法?！罢Z(yǔ)法制導(dǎo)”的方法，即按正規(guī)式的語(yǔ)法結(jié)構(gòu)指引構(gòu)造過(guò)程，構(gòu)造規(guī)則具體描述如下：.“對(duì)于∑上的一個(gè)正規(guī)式R,可以構(gòu)造一個(gè)∑上的M，，使得L(M)(R).”說(shuō)明一種構(gòu)造方法：(1),構(gòu)造任一具有空終態(tài)集的M(2），構(gòu)造的({k0},∑0.{k0}):f（k0)對(duì)于所有a∑都沒(méi)定義。(3）,構(gòu)造的({k01},∑0.{k1}):f(k0)=k1(4)R1|R2,將步驟（1）（2）（3）分別應(yīng)用到R12產(chǎn)生M1==(K1,∑111),M2=(K2,∑222),其中K12不相交.構(gòu)造的(K1K2{k},∑):k是新增加的狀態(tài)符號(hào)，f包含f1和f2,且f()1(k1)f2(k2).若k1F1且k2F2則1F2，否則1F2{k}(5)12將步驟（1）（2）（3）分別應(yīng)用到R12產(chǎn)生M1(K1,∑111),M2=(K2,∑222),其中K12不相交.構(gòu)造的(K1K2,∑12):f包含f1和f2,且f()1(),當(dāng)kF1時(shí);f()2(),當(dāng)k∈K2時(shí);f(k1,)2,(6)1*將步驟（1）（2）（3）分別應(yīng)用到R1,產(chǎn)生M1(K1,∑111),構(gòu)造的(K1{k00},∑00)其中k00是新增加的兩個(gè)狀態(tài),f()1(),當(dāng)kF1時(shí);f(k0,)(F1,)={k10},,對(duì)于正規(guī)式,構(gòu)造的

FS對(duì)于正規(guī)式,構(gòu)造的