第3章詞法分析

1、第三章 詞法分析u3.1 詞法分析概述u3.2 詞法分析程序的設(shè)計(jì) u3.3 正規(guī)式與有限自動(dòng)機(jī)u3.4 詞法分析程序的實(shí)現(xiàn)u3.5 詞法分析器的自動(dòng)生成22022-3-173.1 詞法分析概述詞法分析概述u一、詞法分析程序的任務(wù)u二、詞法分析程序的功能u三、詞法分析程序的安排u四、詞法分析程序的實(shí)現(xiàn)方式u五、詞法分析程序的輸出形式32022-3-17詞法分析程序n詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行 ，也可以和語(yǔ)法分析結(jié)合在一起作為一遍。n輸入：源程序字符串n輸出：等價(jià)的屬性字序列（內(nèi)部表示形式）3.1 詞法分析概述詞法分析概述42022-3-17q一、詞法分析程序的任務(wù)一、詞法

2、分析程序的任務(wù)從左至右逐個(gè)字符地掃描源程序，產(chǎn)生一從左至右逐個(gè)字符地掃描源程序，產(chǎn)生一個(gè)個(gè)單詞符號(hào)。把作為字符的源程序改造為個(gè)個(gè)單詞符號(hào)。把作為字符的源程序改造為單詞符號(hào)串組成的中間程序，執(zhí)行詞法分析單詞符號(hào)串組成的中間程序，執(zhí)行詞法分析任務(wù)的程序稱為詞法分析器或稱掃描器。任務(wù)的程序稱為詞法分析器或稱掃描器。 3.1 詞法分析概述詞法分析概述52022-3-17q二、詞法分析程序的功能二、詞法分析程序的功能n詞法分析程序主要執(zhí)行以下功能：讀入源程序字符串，識(shí)別開(kāi)具有獨(dú)立含義的最小語(yǔ)法單位單詞（符號(hào)）；把單詞變換成長(zhǎng)度統(tǒng)一的且為定長(zhǎng)的屬性字；n其他功能：濾掉空格，跳過(guò)注釋、換行符某些預(yù)加工處理3

3、.1 詞法分析概述詞法分析概述62022-3-17q三、詞法分析程序的安排三、詞法分析程序的安排n常常把詞法分析程序作為獨(dú)立的一遍或作為被語(yǔ)法分析程序所調(diào)用的子程序。n1、作為獨(dú)立的一遍： 語(yǔ)法分析前進(jìn)行詞法分析，把單詞符號(hào)串形成中間文件存貯。3.1 詞法分析概述詞法分析概述72022-3-17q三、詞法分析程序的安排三、詞法分析程序的安排n2、作為被語(yǔ)法分析器詞用的子程序： 3.1 詞法分析概述詞法分析概述82022-3-17n相對(duì)獨(dú)立方式：把詞法分析程序作為語(yǔ)法分析程序的一個(gè)獨(dú)立子程序。語(yǔ)法分析程序需要新符號(hào)時(shí)調(diào)用這個(gè)子程序。n完全獨(dú)立方式：詞法分析程序作為單獨(dú)一趟來(lái)實(shí)現(xiàn)。詞法分析程序讀入

4、整個(gè)源程序，它的輸出作為語(yǔ)法分析程序的輸入。q四、詞法分析程序的實(shí)現(xiàn)方式四、詞法分析程序的實(shí)現(xiàn)方式3.1 詞法分析概述詞法分析概述92022-3-17相對(duì)獨(dú)立方式n當(dāng)采用遞歸下降分析等技術(shù)實(shí)現(xiàn)一趟編譯程序時(shí)常采用這種方式。源程序詞法分析程序語(yǔ)法分析程序Tokenget token.q四、詞法分析程序的實(shí)現(xiàn)方式四、詞法分析程序的實(shí)現(xiàn)方式3.1 詞法分析概述詞法分析概述102022-3-17完全獨(dú)立方式n采用詞法分析工作完全獨(dú)立的原因：簡(jiǎn)化設(shè)計(jì)，降低語(yǔ)法分析的復(fù)雜性提高編譯效率增加編譯系統(tǒng)的可移植性 源程序詞法分析程序語(yǔ)法分析程序?qū)傩宰中蛄袑傩宰中蛄?q四、詞法分析程序的實(shí)現(xiàn)方式四、詞法分析程序的

5、實(shí)現(xiàn)方式3.1 詞法分析概述詞法分析概述112022-3-17n單詞-是程序語(yǔ)言的基本語(yǔ)法符號(hào)。n如：基本字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符等。n詞法分析器中單詞的輸出形式： （單詞類別、單詞內(nèi)部碼值） q五、詞法分析程序的輸出形式五、詞法分析程序的輸出形式3.1 詞法分析概述詞法分析概述122022-3-17n詞法分析程序輸出的單詞符號(hào)通常用二元式表示：（單詞種別，單詞自身的值）n單詞種別：表示單詞種類，常用整數(shù)編碼，它是語(yǔ)法分析需要的n單詞自身的值：是編譯中其他階段所需要的信息如果一個(gè)種別只含一個(gè)單詞符號(hào)，那么該單詞符號(hào)的種別編碼就完全代表它自身的值。如果一個(gè)種別含有多個(gè)單詞符號(hào)，那么還應(yīng)給出

6、該單詞符號(hào)的自身值：標(biāo)識(shí)符自身值是標(biāo)識(shí)符自身的字符串；常數(shù)自身值是常數(shù)的二進(jìn)制數(shù)值。q五、詞法分析程序的輸出形式五、詞法分析程序的輸出形式3.1 詞法分析概述詞法分析概述132022-3-17語(yǔ)言的單詞符號(hào)n單詞符號(hào)是程序語(yǔ)言的基本語(yǔ)法單位，一般分為下面5種：關(guān)鍵字（基本字）：（個(gè)數(shù)確定，可全體編為一類，也可一字一類)標(biāo)識(shí)符：（個(gè)數(shù)不確定，作為一類）常數(shù)：各種類型的常數(shù) 。(個(gè)數(shù)不確定，按類型分類)運(yùn)算符：如+、-、*、/、0THEN b1:=c1*d1 ELSE b1:=5 經(jīng)詞法分析后的輸出。經(jīng)詞法分析后的輸出。q五、詞法分析程序的輸出形式五、詞法分析程序的輸出形式3.1 詞法分析概述詞法

7、分析概述152022-3-17n解：輸出的單詞串為：解：輸出的單詞串為：q五、詞法分析程序的輸出形式五、詞法分析程序的輸出形式3.1 詞法分析概述詞法分析概述162022-3-17一、狀態(tài)轉(zhuǎn)換圖n狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。用結(jié)點(diǎn)代表狀態(tài)，狀態(tài)之間用箭弧連接，箭弧上的標(biāo)記（字符）代表在射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。n一個(gè)狀態(tài)轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，有一個(gè)初態(tài)，終態(tài)用雙圈表示。一個(gè)狀態(tài)轉(zhuǎn)換圖可識(shí)別一定的字符串。 SIE字母字母數(shù)字?jǐn)?shù)字字母或數(shù)字字母或數(shù)字狀態(tài)都是非終結(jié)符號(hào)S：開(kāi)始狀態(tài)E：終止?fàn)顟B(tài)，用雙圈表示I：標(biāo)識(shí)符狀態(tài)3.2 詞法分析程序的設(shè)計(jì)詞法分析程序的設(shè)計(jì)例例1：172022-

8、3-17一、狀態(tài)轉(zhuǎn)換圖例例2：例例3：182022-3-17n方法：每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一段程序，前面狀態(tài)結(jié)的程方法：每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一段程序，前面狀態(tài)結(jié)的程序調(diào)用其后繼結(jié)點(diǎn)的程序。序調(diào)用其后繼結(jié)點(diǎn)的程序。n例例1：二、狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)PROCEDURE Proc0;Getchar; case char of AZ : proc1; 09: proc2;otherwise error;end of case;192022-3-17q為了描述方便，引入一些標(biāo)準(zhǔn)過(guò)程（函數(shù)）與變量為了描述方便，引入一些標(biāo)準(zhǔn)過(guò)程（函數(shù)）與變量:n1.全程字符變量全程字符變量Char：存放最新讀入的源程序字符；：存放最新讀入的源程

9、序字符；n2.字符串字符串TOKEN：存放構(gòu)成單詞符號(hào)的字符串；：存放構(gòu)成單詞符號(hào)的字符串；n3.過(guò)程過(guò)程GETChar：讀入一個(gè)源程序字符，放入：讀入一個(gè)源程序字符，放入Char中，中，搜索指針前移；搜索指針前移；n4.過(guò)程過(guò)程GETNBC：反復(fù)調(diào)用：反復(fù)調(diào)用 GETChar，直接讀入的，直接讀入的 Char 為止；為止；n5.過(guò)程過(guò)程CONCAT：把：把Char中字符連到中字符連到TOKEN末尾去；末尾去；n6.函數(shù)函數(shù)Letter/digit：判別：判別Char中是否為字母中是否為字母/數(shù)數(shù)字；字；n7.過(guò)程過(guò)程Return (c, val );n8.過(guò)程過(guò)程Retract：搜索器指針回

10、拔一個(gè)字符。：搜索器指針回拔一個(gè)字符。 二、狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)202022-3-17n例例2：PROCEDURE Pro0;BEGIN Getchar;IF char IN A.Z then pro1 else error;END;Procedure pro1;begin getchar; while char IN A.Z, o.g DO begin concat;getchar;End;pro2;End; procedure pro2;begin retract; return(101,TOKEN );end;212022-3-17三、為正則文法構(gòu)造狀態(tài)轉(zhuǎn)換圖n什么是正則文法？（U:=T 或

11、U:=WT）n步驟如下：以S為開(kāi)始狀態(tài)作結(jié)點(diǎn)；把文法中的每一個(gè)非終結(jié)符號(hào)作為狀態(tài)結(jié)點(diǎn)；對(duì)于形如Q:=T的每個(gè)規(guī)則，引一條開(kāi)始狀態(tài)S到狀態(tài)Q的弧，弧上標(biāo)記為T(mén)；對(duì)于形如Q:=RT的規(guī)則引一條從狀態(tài)R到Q的弧，弧上標(biāo)記為T(mén)，其中R為非終結(jié)符號(hào)，T為終結(jié)符號(hào)。以識(shí)別符號(hào)為終止?fàn)顟B(tài)。222022-3-17構(gòu)造狀態(tài)轉(zhuǎn)換圖舉例n例如：對(duì)于正則文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|bSABabSABaZZaSABabZbaabaaaba(1)(2)(3)232022-3-17四、應(yīng)用狀態(tài)轉(zhuǎn)換圖識(shí)別句子n如果x是相應(yīng)文法的句子便必須能從開(kāi)始狀態(tài)出發(fā)，順著弧的方向行進(jìn)到終止?fàn)顟B(tài)。其步驟

12、如下: (1)從開(kāi)始狀態(tài)開(kāi)始，以它作為當(dāng)前狀態(tài)，并從x的最左字符開(kāi)始重復(fù)步驟2，直到到達(dá)x的右端為止； (2)掃描x的下一字符，在當(dāng)前狀態(tài)射出的各個(gè)弧中找出標(biāo)記有該字符的弧，并沿此弧前進(jìn)，以達(dá)到的狀態(tài)作為下一當(dāng)前狀態(tài)。n步驟2存在的兩種可能：可能找不到一條弧的標(biāo)記與當(dāng)前字符相同；總能找到一個(gè)弧，其標(biāo)記與當(dāng)前字符相同。242022-3-17應(yīng)用狀態(tài)轉(zhuǎn)換圖識(shí)別句子舉例n例如：對(duì)于正則文法GZ： Z:=Za|Aa|Bb A:=Ba|a B:=Ab|babSABabZbaaabSABabZbaa(1)識(shí)別字符串a(chǎn)babaaaFba,b(2)識(shí)別字符串bababbb252022-3-17狀態(tài)轉(zhuǎn)換圖識(shí)別句

13、子的實(shí)質(zhì)n是一個(gè)規(guī)約過(guò)程，運(yùn)用自底向上的識(shí)別算法：如： S A與A Z表示：a直接規(guī)約為A，Aa直接規(guī)約為Z。n從開(kāi)始狀態(tài)S出發(fā)逐步到達(dá)終止?fàn)顟B(tài)Z的過(guò)程，也是從終結(jié)符號(hào)串出發(fā)，規(guī)約到非終結(jié)符號(hào)的過(guò)程。aa262022-3-17對(duì)句子ababaaa的分析步驟 當(dāng)前狀態(tài) 輸入的其余部分n S ababaaan A babaaan B abaaan A baaan B aaan A aan Z a1 Za b a b a a aABABAZZ(a) 分析過(guò)程分析過(guò)程(b) 語(yǔ)法樹(shù)語(yǔ)法樹(shù)272022-3-17五、用狀態(tài)轉(zhuǎn)換圖為正則語(yǔ)言構(gòu)造正則文法n從上面狀態(tài)轉(zhuǎn)換圖，可得到相應(yīng)的正則文法： GZ: Z:

14、=Cb C:=Bb|b B:=Ab A:=Ba|aSABCZabbbban例如：正則語(yǔ)言(ab)nb2|n0 基于其句子的一般形式，為其構(gòu)造狀態(tài)轉(zhuǎn)換圖：282022-3-17六、轉(zhuǎn)換系統(tǒng)n定義：轉(zhuǎn)換系統(tǒng)是具有下列三個(gè)特征的狀態(tài)轉(zhuǎn)換圖，即 1) 開(kāi)始狀態(tài)S和終止?fàn)顟B(tài)Z 唯一; 2) 無(wú)弧進(jìn)入S，也無(wú)弧自Z射出； 3)可能存在標(biāo)記為空串（）的弧。n轉(zhuǎn)換系統(tǒng)與狀態(tài)轉(zhuǎn)換圖的區(qū)別： 弧SS1S2ZAZ2Z1292022-3-17u一、基本概念u二、確定有窮狀態(tài)自動(dòng)機(jī)（DFA）u三、非確定有窮狀態(tài)自動(dòng)機(jī)（NFA）u四、NFA和DFA的轉(zhuǎn)換u五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性u(píng)六、DFA的化簡(jiǎn)3.3 正規(guī)式與有

15、限自動(dòng)機(jī)正規(guī)式與有限自動(dòng)機(jī)302022-3-17q一、基本概念一、基本概念n1.字母表字母表： 元素的非空有限集合。如元素的非空有限集合。如=A, B, On2.字符：字符： 字母表字母表的一個(gè)元素稱為一個(gè)字符（符號(hào)）的一個(gè)元素稱為一個(gè)字符（符號(hào)）n3. 上的字：上的字： 上字符的有窮序列；例：上字符的有窮序列；例：=a,b,cn4.空字空字： 不含任何字符的字不含任何字符的字 n5.字的長(zhǎng)度：字的長(zhǎng)度： |n6.上字的全體：上字的全體： *n7.字的連接：字的連接： 字字與字與字的連接記為的連接記為3.3 正規(guī)式與有限自動(dòng)機(jī)正規(guī)式與有限自動(dòng)機(jī)312022-3-17q一、基本概念一、基本概念n

16、8.字的方冪：字字的方冪：字的的n次連接稱為次連接稱為的的n次方冪次方冪,記記為為 ,特別地特別地 =n9.字的集合字的集合A與與B的乘積：的乘積： 記作記作 ,其中其中n10. *子集的方冪：子集的方冪： A=,A1=A, ,n11.*子集的正則閉包：子集的正則閉包：n12.*子集的閉包：子集的閉包：3.3 正規(guī)式與有限自動(dòng)機(jī)正規(guī)式與有限自動(dòng)機(jī)n0322022-3-17q正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集n正規(guī)集是字母表正規(guī)集是字母表上的一個(gè)特殊字集，通常我們借助正上的一個(gè)特殊字集，通常我們借助正規(guī)式來(lái)描述它。關(guān)于正規(guī)式與正規(guī)集的定義是遞歸的。規(guī)式來(lái)描述它。關(guān)于正規(guī)式與正規(guī)集的定義是遞歸的。n1.

17、和和都是都是上的正規(guī)式，它們所表示的正規(guī)集分別為上的正規(guī)式，它們所表示的正規(guī)集分別為和和n2.任何任何a,a是是上的正規(guī)式，它所表示的正規(guī)式為上的正規(guī)式，它所表示的正規(guī)式為n3.假定假定u和和v是正規(guī)式，它們所代表的正規(guī)集分別是是正規(guī)式，它們所代表的正規(guī)集分別是L(u)和和L(v)，則，則u|v, uv, u*都是都是上的正規(guī)式，它上的正規(guī)式，它們所表示的正規(guī)集分別為們所表示的正規(guī)集分別為L(zhǎng)(u)L(v), L(u)L(v), L(u)*n僅由有限次使用上述三步而定義的表達(dá)式才是僅由有限次使用上述三步而定義的表達(dá)式才是上的正上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是規(guī)式，僅由這些正規(guī)式所表示的

18、字集才是上的正規(guī)集上的正規(guī)集332022-3-17q正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集n優(yōu)先級(jí)遞增：優(yōu)先級(jí)遞增： |(或或)，（連接），（連接），*,（正規(guī)式）（正規(guī)式） , , *, （正規(guī)集）（正規(guī)集）n例例1. =0, 1，則正規(guī)式有，則正規(guī)式有0, 1, , 1*,，正規(guī)集有正規(guī)集有0, 1, , , 1*, n若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)才是等價(jià)才是上的正規(guī)集上的正規(guī)集342022-3-17q正規(guī)式的性質(zhì)：正規(guī)式的性質(zhì)：n1交換律：交換律：U|V=V|U 證：證：L(u|v)=L(u)L(v) = L(v)L(u)=L(v|u)

19、因此，因此，u|v=v|un2結(jié)合律：結(jié)合律：(u|v)|w=u|(v|w),(uv)w=u(vw)n3分配律：分配律：u(v|w)=uv|uw,(u|v)w=u(vw)n4u=u=u 證：證：L(u)=L()L(u)=L(u)0 L(u)=L(u) 352022-3-17二、確定型有窮狀態(tài)自動(dòng)機(jī)q一個(gè)確定的有窮自動(dòng)機(jī)（DFA）D是一個(gè)五元組：M=（S，S0，F(xiàn)）其中 S：有窮非空的狀態(tài)集合；：有窮非空的輸入符號(hào)字母表； ：轉(zhuǎn)換函數(shù)，是在SS上的映像，即，如 (s,a)=s,(sS,sS)就意味著，當(dāng)前狀態(tài)為s，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)s，我們把s稱作s的一個(gè)后繼狀態(tài)； S0S是唯一的

20、一個(gè)初態(tài)； F S是非空的終態(tài)集合。362022-3-17n例例1DFA M=(0, 1, 2, a, b,f,0, 2)，其中，其中(s,a)=S,(s,b)=S,s=0,1, 2n注：一個(gè)注：一個(gè)DFA可表示為一個(gè)狀態(tài)轉(zhuǎn)換矩陣，行表示可表示為一個(gè)狀態(tài)轉(zhuǎn)換矩陣，行表示狀態(tài)，列表示輸入字符，矩陣元素狀態(tài)，列表示輸入字符，矩陣元素Ms, a的值的值為為(s, a)。n例例2二、確定型有窮狀態(tài)自動(dòng)機(jī)372022-3-17n一個(gè)一個(gè)DFA M也可用一張狀態(tài)轉(zhuǎn)換圖表示，也可用一張狀態(tài)轉(zhuǎn)換圖表示，DFA的的每個(gè)狀態(tài)對(duì)于狀態(tài)轉(zhuǎn)換圖的一個(gè)接點(diǎn)，圖中箭弧每個(gè)狀態(tài)對(duì)于狀態(tài)轉(zhuǎn)換圖的一個(gè)接點(diǎn)，圖中箭弧上的標(biāo)記為輸入

21、字符，若上的標(biāo)記為輸入字符，若(s, a)=S，則從狀，則從狀態(tài)態(tài)s畫(huà)一條箭弧到畫(huà)一條箭弧到S，弧上標(biāo)記為，弧上標(biāo)記為a。n對(duì)對(duì)*中的任何字中的任何字，若存在一條從初態(tài)到某一終，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上標(biāo)記連接成的字態(tài)的道路，且這條路上所有弧上標(biāo)記連接成的字等于等于，則稱，則稱可為可為DFA M所識(shí)別，或稱所識(shí)別，或稱DFA M可可讀出（或接受、識(shí)別）字讀出（或接受、識(shí)別）字。nDFA M識(shí)別的字的全體記為識(shí)別的字的全體記為L(zhǎng)(M)。二、確定型有窮狀態(tài)自動(dòng)機(jī)382022-3-17n如果一個(gè)如果一個(gè)DFA M的輸入字母表為的輸入字母表為，則我們也稱，則我們也稱M是是上

22、的一個(gè)上的一個(gè)DFA?？梢宰C明：。可以證明：上的一個(gè)子集是正規(guī)的，上的一個(gè)子集是正規(guī)的，當(dāng)且僅當(dāng)存在當(dāng)且僅當(dāng)存在上的上的DFA M，使得，使得V=L（M）。）。nDFA的確定性表現(xiàn)在映射的確定性表現(xiàn)在映射：SS是一個(gè)單值函數(shù)。是一個(gè)單值函數(shù)。也就是說(shuō)，對(duì)任何狀態(tài)也就是說(shuō)，對(duì)任何狀態(tài)sS和輸入符號(hào)和輸入符號(hào)a，(s, a)唯一地確定了下一狀態(tài)。唯一地確定了下一狀態(tài)。n特別地，若特別地，若DFA M的初態(tài)同時(shí)又是終態(tài)，改的初態(tài)同時(shí)又是終態(tài)，改DFA M可識(shí)別空字可識(shí)別空字。n顯然，若顯然，若DFA M中字母表中字母表含含n個(gè)字母，則任何一個(gè)個(gè)字母，則任何一個(gè)狀態(tài)頂多只有狀態(tài)頂多只有n條發(fā)出弧。條發(fā)

23、出弧。 二、確定型有窮狀態(tài)自動(dòng)機(jī)392022-3-17從狀態(tài)轉(zhuǎn)換圖構(gòu)造有窮狀態(tài)自動(dòng)機(jī)n例如：從下面狀態(tài)圖構(gòu)造DFAnDFA D=（S，Z，A，B，a，b，S，Z） 其中定義為： （S，a）=A （S，b）=B （A，a）=Z （A，b）=B （B，a）=A （B，b）=Z （Z，a）=ZabSABabZbaa402022-3-17運(yùn)行DFA與識(shí)別一個(gè)字符串n擴(kuò)充的映像定義： (R, )=R (R, Tt)=(R, T), t)，其中t*， Tn以上兩個(gè)式子的含義是什么？n定義： 對(duì)于某DFA D=（K,S,F），如果(S，t)=P, PF，則稱符號(hào)串t可被DFA D所接受。n運(yùn)行一個(gè)DFA的過(guò)

24、程：識(shí)別一個(gè)符號(hào)串是否被接受412022-3-17舉例n如前例：DFA D=（S，Z，A，B，a，b，S，Z） （S，a）=A （S，b）=B （A，a）=Z （A，b）=B （B，a）=A （B，b）=Z （Z，a）=Z 則：(S, ababaa)=(S,a), babaa) =(A,babaa)= (A,b), abaa)= (B,abaa)=(A,baa)= (B,aa)=(A,a)= Z 422022-3-17正則集n正則集：L(D)，是一個(gè)DFA接受的字符串集合n正則語(yǔ)言與正則集：L(G)=L(D)n最小狀態(tài)自動(dòng)機(jī)：狀態(tài)個(gè)數(shù)最少，唯一n如何減少自動(dòng)機(jī)的狀態(tài)數(shù)而不改變自動(dòng)機(jī)所接受的語(yǔ)言

25、呢？432022-3-17如何在計(jì)算機(jī)內(nèi)表示映像？n映像：含義？n映像在計(jì)算機(jī)內(nèi)的表示法：矩陣表示法表結(jié)構(gòu)表示法442022-3-17DFA 的矩陣表示法字符字符狀態(tài)狀態(tài)abSABabZbaa矩陣行代表狀態(tài)，列代表輸入字符，矩陣行代表狀態(tài)，列代表輸入字符，矩陣元素是映像得到的新?tīng)顟B(tài)。矩陣元素是映像得到的新?tīng)顟B(tài)。452022-3-17表結(jié)構(gòu)表示法狀態(tài)名狀態(tài)名射出的弧數(shù)射出的弧數(shù)標(biāo)記標(biāo)記1指向的下一狀態(tài)指向的下一狀態(tài)1標(biāo)記標(biāo)記K指向的下一狀態(tài)指向的下一狀態(tài)k對(duì)每一個(gè)狀態(tài)結(jié)點(diǎn)而言對(duì)每一個(gè)狀態(tài)結(jié)點(diǎn)而言若某結(jié)點(diǎn)有若某結(jié)點(diǎn)有K個(gè)射出的弧，個(gè)射出的弧，則相應(yīng)表長(zhǎng)為則相應(yīng)表長(zhǎng)為2k+2462022-3-17引

26、入n(R,T)是K到K的單值函數(shù)，即唯一確定下一狀態(tài)n如果在當(dāng)前狀態(tài)下，同一個(gè)輸入字符確定的下一狀態(tài)不止一個(gè)呢？如 V:=UT W:=UTUWVTTabSABabZbaaaan例如：文法G3.2: Z:=Za|Aa|Bb A:=Ba|Za|a B:=Ab|Ba|b三、非確定有窮狀態(tài)自動(dòng)機(jī)472022-3-17一個(gè)非確定的有窮自動(dòng)機(jī)（NFA）D是一個(gè)五元組：N=（S，S0，F(xiàn)）其中S：有窮非空的狀態(tài)集合；：有窮非空的輸入字母表；：轉(zhuǎn)換函數(shù)，是在S到S的子集所組成集合的映像， (R, T)=Q1,Q2,.QnS0S是非空的初態(tài)集合；FS是非空的終態(tài)集合.三、非確定有窮狀態(tài)自動(dòng)機(jī)482022-3-1

27、7DFA與NFA的區(qū)別DFANFA開(kāi)始狀態(tài)開(kāi)始狀態(tài)唯一唯一一個(gè)或多個(gè)一個(gè)或多個(gè)映像映像單個(gè)狀態(tài)單個(gè)狀態(tài)狀態(tài)集合狀態(tài)集合492022-3-17舉例n前述文法G3.2對(duì)應(yīng)的自動(dòng)機(jī)NFA N=(S,A,B,Z,a,b,S,Z) 其中：(S,a)=A (S,b)=B(A,a)=Z (A,b)=B(B,a)=A,B (B,b)=Z(Z,a)=A,ZabSABabZbaaaa502022-3-17擴(kuò)充映像n定義： (R, )=R R為任意的狀態(tài) (R,Tt)=(Q1,t)(Q2,t)(Qn,t) 其中t*，T， (R, T)=Q1,Q2,.Qn (R, Tt)=(Q1,Q2,Qn, t)=(Qi,t)51

28、2022-3-17舉例(字符串被NFA所接受)n對(duì)于輸入字符串babbabb，運(yùn)行G3.2的NFA步驟步驟當(dāng)前狀態(tài)當(dāng)前狀態(tài)輸入的其余部分輸入的其余部分可能的后繼可能的后繼 選擇選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ522022-3-17運(yùn)行NFAn運(yùn)行NFA：識(shí)別一個(gè)字符串是否被NFA所接受，是否能達(dá)到終態(tài)集合中的某個(gè)狀態(tài)n實(shí)質(zhì)：用自底向上方法識(shí)別句子n狀態(tài)轉(zhuǎn)換的下一狀態(tài)不唯一，如何解決？532022-3-17單狀態(tài)n(R,T)=Q1,Q2,Qn 變?yōu)?R,T)=Q1,Q2,Qn （單狀態(tài)） 表示當(dāng)前狀態(tài)為R

29、輸入字符T時(shí)，下一狀態(tài)可能是這些狀態(tài)中的某一狀態(tài)。542022-3-17怎樣把NFA變?yōu)镈FA?n定理3.6 NFA N=(K, , , S0, F) 對(duì)應(yīng)DFA N=(K, , , S, F) 其中K是有窮非空狀態(tài)集合，由k的一切子集組成；用Q1,Q2,Q表示K的元素， QiK(R1,R2,Ri,T)= Q1,Q2,.QjS=S1, S2, , SnF=Sj, Sk, , Sl|Sj, Sk, , SlK, Sj, Sk, , SlF 則 L(N)=L(N)四、NFA與DFA的轉(zhuǎn)換552022-3-17舉例n例: 為NFA N=(S,A,B,Z, a,b, , S, Z)構(gòu)造DFA. 設(shè)它對(duì)

30、應(yīng)的DFA N=(K, a,b, , S, F)abSABabZbaaaanK=S (S,a)=A (S,b)=B K=S,A,B (A,a)=Z (A,b)=B (B,a)=AB (B,b)=Z K=S,A,B,Z,AB (Z,a)=AZ (Z,b)= (AB,a)=ABZ (AB,b)=BZK=S,A,B,Z,AB,AZ, BZ,ABZ(AZ,a)=AZ (AZ,b)=B (BZ,a)=ABZ (BZ,b)=Z(ABZ,a)=ABZ(ABZ,b)=BZ562022-3-17舉例（續(xù)1） 輸入輸入狀態(tài)狀態(tài)abSABAZBBABZZAZABABZBZAZAZBBZABZZABZABZBZabS

31、ABabZbaaaa根據(jù)左邊狀態(tài)轉(zhuǎn)根據(jù)左邊狀態(tài)轉(zhuǎn)換矩陣，可以得換矩陣，可以得到到DFA N的狀態(tài)的狀態(tài)集合（表的左列集合（表的左列狀態(tài)），即狀態(tài)），即K=S,A,b,Z,AB,AZ,BZ,ABZ572022-3-17舉例（續(xù)2）SBABABZAZBZAZbbbbbbbaaaaaaaa開(kāi)始狀態(tài)開(kāi)始狀態(tài):S終止?fàn)顟B(tài)終止?fàn)顟B(tài):Z,AZ,BZ,ABZl 根據(jù)上面狀態(tài)轉(zhuǎn)換矩陣，同時(shí)可以得到根據(jù)上面狀態(tài)轉(zhuǎn)換矩陣，同時(shí)可以得到N的映像函數(shù)，根的映像函數(shù)，根據(jù)該映像可以畫(huà)出它的狀態(tài)轉(zhuǎn)換圖（如下）。據(jù)該映像可以畫(huà)出它的狀態(tài)轉(zhuǎn)換圖（如下）。l 終態(tài)集合中的元素為：由新映像得到的狀態(tài)、終態(tài)集合中的元素為：由新映像得

32、到的狀態(tài)、 且這些狀態(tài)且這些狀態(tài)包含原包含原NFA N的終態(tài)集合中的狀態(tài)。的終態(tài)集合中的狀態(tài)。582022-3-17q1上上NFA M所能識(shí)別的字的全體是所能識(shí)別的字的全體是上的一個(gè)上的一個(gè)正規(guī)集正規(guī)集n證明：設(shè)轉(zhuǎn)換圖中每條弧上可用一個(gè)正規(guī)式作標(biāo)證明：設(shè)轉(zhuǎn)換圖中每條弧上可用一個(gè)正規(guī)式作標(biāo)記，讓記，讓NFA M的轉(zhuǎn)換圖中加進(jìn)兩節(jié)點(diǎn)的轉(zhuǎn)換圖中加進(jìn)兩節(jié)點(diǎn)X和和Y，形成，形成新的新的NFA M，從，從X畫(huà)畫(huà)弧指向原弧指向原NFA M的所有初的所有初態(tài)，從原態(tài)，從原NFA M的所有終態(tài)畫(huà)的所有終態(tài)畫(huà)弧指向弧指向Y，顯然，顯然L(M)=L(M) 然后，對(duì)然后，對(duì)NFA M消結(jié)，直至只剩下消結(jié)，直至只剩下X

33、、Y兩兩個(gè)結(jié)點(diǎn)為止，符上標(biāo)記為一正規(guī)式。個(gè)結(jié)點(diǎn)為止，符上標(biāo)記為一正規(guī)式。 所以，所以，NFA M識(shí)別的為一正規(guī)式；識(shí)別的為一正規(guī)式；NFA M識(shí)別的是一正規(guī)集。識(shí)別的是一正規(guī)集。 五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性592022-3-17q消結(jié)規(guī)則為消結(jié)規(guī)則為五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性602022-3-17q例例1.消結(jié)點(diǎn)消結(jié)點(diǎn)五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性q例例2.消結(jié)點(diǎn)消結(jié)點(diǎn)612022-3-17n2對(duì)于對(duì)于上的每個(gè)正規(guī)集上的每個(gè)正規(guī)集V，存在一個(gè)，存在一個(gè)上的上的DFA M，使得，使得V=L(M)。n證明：第一步，用替代辦法構(gòu)造一個(gè)證明：第一步，用替代辦法構(gòu)造一個(gè)NFA M，使使V=L(M

34、)，因?yàn)檎?guī)集，因?yàn)檎?guī)集V可用正規(guī)式可用正規(guī)式u來(lái)描述，來(lái)描述，而而u由一系列單個(gè)字符連接而成，故可用下述方由一系列單個(gè)字符連接而成，故可用下述方法分解之：法分解之：五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性SZe1e2SZe1e2SZe1|e2SZeSZ SZe1e2e622022-3-17n具體方法：構(gòu)造如下轉(zhuǎn)換圖：具體方法：構(gòu)造如下轉(zhuǎn)換圖： 逐步分解，便可得到一個(gè)逐步分解，便可得到一個(gè)NFA M，有，有L(u)=V=L(M)。n例例1n第二步，把第二步，把NFA M確定化為確定化為DFA M，得證。，得證。五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性632022-3-17舉例n例：正則表達(dá)式(A|B)A|B|0

35、|1的轉(zhuǎn)換系統(tǒng)的構(gòu)造過(guò)程如下：SZ(A|B)A|B|0|1SZ(A|B)A|B|0|1SZAB A|B|0|1SZAB 10AB642022-3-17n概念概念1. 假設(shè)假設(shè)I是是NFA M的狀態(tài)集的一個(gè)子集，的狀態(tài)集的一個(gè)子集，我們定義我們定義-CLOSURE(I)為（為（I的的-閉包）。閉包）。n（1）若）若SI，則，則S-CLOSURE(I)n（2）若）若SI ，則從，則從s出發(fā)經(jīng)過(guò)任意條出發(fā)經(jīng)過(guò)任意條弧而達(dá)弧而達(dá)到的狀態(tài)到的狀態(tài)s，有，有s-CLOSURE(I)n例例1.五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性若若I=1, 3，則，則-CLOSURE(I) =1, 3, 2, 8652022-3

36、-17n概念概念2. 假定假定I是是M的狀態(tài)子集，的狀態(tài)子集，a是是中的中的字符，定義字符，定義Ia= -CLOSURE(J),其中其中J是是I中任意狀態(tài)出發(fā)（跳過(guò)前面任意多條中任意狀態(tài)出發(fā)（跳過(guò)前面任意多條?。?，?。?，經(jīng)過(guò)一條經(jīng)過(guò)一條a弧而能達(dá)到的狀態(tài)結(jié)的全體?；《苓_(dá)到的狀態(tài)結(jié)的全體。n例例2同例同例1 DFA， Ia=5,6,2n利用概念利用概念1和概念和概念2，便可把，便可把NFA確定化。確定化。五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性662022-3-17五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性n令令 ，構(gòu)造一張如下的表，此表第，構(gòu)造一張如下的表，此表第0列為狀態(tài)子集列為狀態(tài)子集I，第，第1至至m列分別

37、為狀態(tài)子列分別為狀態(tài)子集集 ，設(shè)第一行第，設(shè)第一行第0列為列為-CLOSURE(X),，其中，其中X為為NFA M的初態(tài)，求出的初態(tài)，求出第一個(gè)的第一個(gè)的 ，如果某個(gè)，如果某個(gè)Iai(i=1,m)未曾在第未曾在第0列中列出，則把列中列出，則把Iai補(bǔ)入狀態(tài)子集集合補(bǔ)入狀態(tài)子集集合I中，即列于第中，即列于第0列新的一行。列新的一行。n重復(fù)上述各步，直至所有行的重復(fù)上述各步，直至所有行的Iai(i=1,m)均均在第在第0列列I中出現(xiàn)過(guò)為止。這種循環(huán)必將在有限步中出現(xiàn)過(guò)為止。這種循環(huán)必將在有限步內(nèi)中止。（因?yàn)閮?nèi)中止。（因?yàn)镾是有限狀態(tài)集，所以是有限狀態(tài)集，所以S中狀態(tài)的中狀態(tài)的組合數(shù)也是有限的）組合

38、數(shù)也是有限的） 672022-3-17n顯然，這張表可以看成一個(gè)狀態(tài)轉(zhuǎn)換表，顯然，這張表可以看成一個(gè)狀態(tài)轉(zhuǎn)換表，也就是說(shuō)可把也就是說(shuō)可把I中每個(gè)子集看成一個(gè)狀態(tài)，中每個(gè)子集看成一個(gè)狀態(tài)，而狀態(tài)轉(zhuǎn)換表唯一地刻劃了一個(gè)而狀態(tài)轉(zhuǎn)換表唯一地刻劃了一個(gè)DFA M，其初態(tài)為該表的第其初態(tài)為該表的第1行第行第0列，含有原列，含有原NFA M終態(tài)的子集為新的終態(tài)。（證畢）終態(tài)的子集為新的終態(tài)。（證畢）n推論：一個(gè)子集是正規(guī)的，當(dāng)且僅當(dāng)它可推論：一個(gè)子集是正規(guī)的，當(dāng)且僅當(dāng)它可由一個(gè)由一個(gè)DFA（或（或NFA）所識(shí)別。）所識(shí)別。五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性682022-3-17n例：設(shè)計(jì)一個(gè)例：設(shè)計(jì)一個(gè)DFA

39、M，它識(shí)別二進(jìn)制偶數(shù)（不以，它識(shí)別二進(jìn)制偶數(shù)（不以0開(kāi)頭的無(wú)符號(hào)數(shù)）開(kāi)頭的無(wú)符號(hào)數(shù)）n解：解：n1寫(xiě)出正規(guī)式寫(xiě)出正規(guī)式 1（1|0）* 0 n2畫(huà)出畫(huà)出NFA M 細(xì)化為：細(xì)化為：3. 確定化為確定化為DFA M五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性692022-3-17五、正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性或：或：702022-3-17舉例n正則表達(dá)式a|(a|b)a的相應(yīng)轉(zhuǎn)換系統(tǒng)與狀態(tài)轉(zhuǎn)換圖的構(gòu)造過(guò)程。ABa|(a|b)aAB(a|b)aaABDCa(a|b)a ABDCaa Eab(a)(b)(c)(d)開(kāi)始狀態(tài)：開(kāi)始狀態(tài)：A終止?fàn)顟B(tài)：終止?fàn)顟B(tài)：B712022-3-17前例續(xù)nNFA N = (A,C,

40、D,E, a,b, M, A,C,D, A,C,D) M: M(A,a)=C,E M(A,b)=E M(C,a)=C M(D,a)=E M(D,b)=E M(E,a)=DABDCaa EabACaaa b(e)(f)DaEab開(kāi)始狀態(tài)：開(kāi)始狀態(tài)：A, B終止?fàn)顟B(tài)：終止?fàn)顟B(tài)：B, C, D開(kāi)始狀態(tài)：開(kāi)始狀態(tài)：A, C, D終止?fàn)顟B(tài)：終止?fàn)顟B(tài)：A, C, D722022-3-17正則表達(dá)式的值與有窮自動(dòng)機(jī)所接受的語(yǔ)言n定理3.11：上的NFA A所接受的字符串集合L(A)是上的某個(gè)正則表達(dá)式e的值，即L(A)=|e|。n例: NFA N相應(yīng)的狀態(tài)轉(zhuǎn)換圖為圖(a)，則N所接受的語(yǔ)言為合成所得到的正則

41、表達(dá)式 (aa|bb)|(ab|ba)aa|bb(ab|ba) 的值。ZTab, baab, baaa, bbaa, bb(a)ZTab|baab|baaa|bbaa|bbXY (b)732022-3-17前例續(xù)n正則表達(dá)式與有窮狀態(tài)自動(dòng)機(jī)是等價(jià)的。Zaa|bbXY (ab|ba)aa|bb(ab|ba)XY(d)(c)(aa|bb)|(ab|ba)aa|bb(ab|ba)742022-3-17n字符串W把狀態(tài)P和狀態(tài)Q區(qū)別開(kāi)：n等價(jià)狀態(tài)：無(wú)法區(qū)別開(kāi)的兩個(gè)狀態(tài)n基本思想：把狀態(tài)集劃分成互不相交的子集，使子集中的狀態(tài)是等價(jià)的n化簡(jiǎn)DFA的算法步驟：劃分狀態(tài)集合并狀態(tài):取每組狀態(tài)中的代表狀態(tài)，刪去

42、其他等價(jià)狀態(tài)若有死狀態(tài)或不可達(dá)狀態(tài)，則把它們刪去。n死狀態(tài)：無(wú)法達(dá)到終止?fàn)顟B(tài)的非終止?fàn)顟B(tài)n不可達(dá)狀態(tài)：不能從開(kāi)始狀態(tài)達(dá)到它的那些狀態(tài)六、DFA的化簡(jiǎn)752022-3-17舉例n劃分狀態(tài)集為4和 0,1,2,3n對(duì)于0,1,2,3和輸入字符a和b:M(0,a)=1 M(1,a)=1M(2,a)=1 M(3,a)=1M(0,b)=2 M(1,b)=3M(2,b)=2 M(3,b)=4只有狀態(tài)3在輸入為b時(shí)映像的后繼狀態(tài)不在0,1,2,3中，因此該狀態(tài)集劃分為3和0,1,2n對(duì)于0,1,2:狀態(tài)1在輸入為b時(shí)的后繼狀態(tài)不在0,1,2中，因此劃分為1和0,202314bbbbbaaaaan對(duì)于對(duì)于0,

43、2:對(duì)于相同輸對(duì)于相同輸入字符，該子集中每一狀入字符，該子集中每一狀態(tài)映像得到的后繼狀態(tài)都態(tài)映像得到的后繼狀態(tài)都相同，因此不再可劃分相同，因此不再可劃分n最后劃分為：最后劃分為： 4 3 1 0,2 六、DFA的化簡(jiǎn)762022-3-17舉例（續(xù)1）n對(duì)于劃分結(jié)果4, 3, 1, 0,2，把0,2合并為一個(gè)狀態(tài)，其狀態(tài)轉(zhuǎn)換圖如圖：0213aaaabbb02314bbbbbaaaaab六、DFA的化簡(jiǎn)772022-3-17構(gòu)造詞法分析程序的方法n用手工方式，即根據(jù)識(shí)別語(yǔ)言單詞的狀態(tài)轉(zhuǎn)換圖，使用某種高級(jí)語(yǔ)言，例如，C語(yǔ)言直接編寫(xiě)詞法分析程序。n利用自動(dòng)生成工具LEX自動(dòng)生成詞法分析程序。3.4 詞

44、法分析程序的實(shí)現(xiàn)詞法分析程序的實(shí)現(xiàn)782022-3-17詞法分析程序?qū)崿F(xiàn)中要考慮的問(wèn)題n確定實(shí)現(xiàn)詞法分析程序的執(zhí)行方式n確定屬性字的結(jié)構(gòu)n緩沖區(qū)預(yù)處理，超前搜索,n關(guān)鍵字的處理，符號(hào)表的實(shí)現(xiàn)n查找效率，算法的優(yōu)化實(shí)現(xiàn)n詞法錯(cuò)誤處理3.4 詞法分析程序的實(shí)現(xiàn)詞法分析程序的實(shí)現(xiàn)792022-3-17屬性字n詞法分析程序?qū)φf(shuō)明部分不做語(yǔ)義處理。n詞法分析程序輸出屬性字一般采用下面的形式： （符號(hào)類，符號(hào)值）n屬性字是符號(hào)的機(jī)內(nèi)表示，有統(tǒng)一固定的長(zhǎng)度3.4 詞法分析程序的實(shí)現(xiàn)詞法分析程序的實(shí)現(xiàn)802022-3-17源程序的輸入n在內(nèi)存開(kāi)辟緩沖區(qū)，將程序文本放進(jìn)該緩沖區(qū)n預(yù)處理：刪除無(wú)用字符等n詞法分析

45、程序?qū)彌_區(qū)掃描時(shí)，設(shè)置兩個(gè)指示器，一個(gè)指向當(dāng)前正在識(shí)別的單詞的開(kāi)始位置，稱為起始指針；另一個(gè)用于向前搜索，以尋找單詞的終點(diǎn)，稱為掃描指針。起始指針起始指針?biāo)阉髦羔標(biāo)阉髦羔?.4 詞法分析程序的實(shí)現(xiàn)詞法分析程序的實(shí)現(xiàn)812022-3-17超前搜索n詞法分析程序在讀取單詞時(shí)，為了判斷是否已讀入整個(gè)單詞的全部字符，常采取向前多讀取字符并通過(guò)讀取的字符來(lái)判別，即所謂超前搜索技術(shù)。3.4 詞法分析程序的實(shí)現(xiàn)詞法分析程序的實(shí)現(xiàn)822022-3-17關(guān)鍵字的識(shí)別與查表算法n對(duì)于關(guān)鍵字，先把它們當(dāng)成標(biāo)識(shí)符，然后去查關(guān)鍵字表。若在表中查到，則為關(guān)鍵字，獲取相應(yīng)的類別碼；否則，認(rèn)為是標(biāo)識(shí)符。n查找算法：線性查找

46、折半查找Hash函數(shù)3.4 詞法分析程序的實(shí)現(xiàn)詞法分析程序的實(shí)現(xiàn)832022-3-17出錯(cuò)處理n對(duì)定義外的（如，對(duì)首字符不是字母的，不是數(shù)字的，不是運(yùn)算符和分界符的）單詞進(jìn)行出錯(cuò)處理。3.4 詞法分析程序的實(shí)現(xiàn)詞法分析程序的實(shí)現(xiàn)842022-3-17使用狀態(tài)圖設(shè)計(jì)詞法分析程序n多數(shù)語(yǔ)言的詞法規(guī)則可用正則文法和正則表達(dá)式來(lái)描述。正則文法或正則表達(dá)式定義的語(yǔ)言都可以被狀態(tài)圖識(shí)別。n使用狀態(tài)圖設(shè)計(jì)詞法分析程序的步驟如下：對(duì)程序設(shè)計(jì)語(yǔ)言的單詞按類構(gòu)造相應(yīng)的狀態(tài)圖。（這里把關(guān)鍵字與標(biāo)識(shí)符作為一類）合并各類單詞的狀態(tài)圖，增加一個(gè)出錯(cuò)處理終態(tài)，構(gòu)成一個(gè)識(shí)別該語(yǔ)言所有單詞的狀態(tài)轉(zhuǎn)換圖對(duì)狀態(tài)圖的每一個(gè)終點(diǎn)編一段

47、相應(yīng)的子程序。3.4 詞法分析程序的實(shí)現(xiàn)詞法分析程序的實(shí)現(xiàn)852022-3-17201字母字母|數(shù)字其它3456數(shù)字?jǐn)?shù)字其它+-78*/9101113:;1617其它13=舉例舉例862022-3-17n本節(jié)討論：本節(jié)討論： 用正規(guī)式描述單詞符號(hào)，并研究如何用正規(guī)式描述單詞符號(hào)，并研究如何從正規(guī)產(chǎn)生識(shí)別這些單詞符號(hào)的詞法分析從正規(guī)產(chǎn)生識(shí)別這些單詞符號(hào)的詞法分析程序。程序。3.5 詞法分析器的自動(dòng)生成詞法分析器的自動(dòng)生成872022-3-17一、一、LEX語(yǔ)言語(yǔ)言n一個(gè)一個(gè)LEX語(yǔ)言程序經(jīng)過(guò)編譯后得到的結(jié)果程序，語(yǔ)言程序經(jīng)過(guò)編譯后得到的結(jié)果程序，其作用相當(dāng)于一個(gè)其作用相當(dāng)于一個(gè)DFA，可用來(lái)識(shí)別

48、和產(chǎn)生單詞，可用來(lái)識(shí)別和產(chǎn)生單詞也就是說(shuō)其功能即為一個(gè)詞法分析器。也就是說(shuō)其功能即為一個(gè)詞法分析器。 882022-3-17n一個(gè)一個(gè)LEX源程序包括兩部分：輔助定義式和識(shí)別規(guī)則源程序包括兩部分：輔助定義式和識(shí)別規(guī)則n1、輔助定義式、輔助定義式 D1R1 DnRn 其中其中Ri為正規(guī)式，只允許出現(xiàn)為正規(guī)式，只允許出現(xiàn)上字符上字符D1,Di-1；Di為這個(gè)正規(guī)式為這個(gè)正規(guī)式Ri的簡(jiǎn)名的簡(jiǎn)名n例例1LetterA|B|Z Digit 0|1|9 Id Letter(Letter|Digit)*. . . .892022-3-17n2.識(shí)別規(guī)則識(shí)別規(guī)則 P1A1 . . . PmAmn其中，其中，P

49、i稱為詞形，為正規(guī)式稱為詞形，為正規(guī)式(D1,Dm) Ai稱為詞形稱為詞形Pi的動(dòng)作（程序）的動(dòng)作（程序）n顯然：一個(gè)顯然：一個(gè)LEX源程序產(chǎn)生的詞法分析器只能識(shí)源程序產(chǎn)生的詞法分析器只能識(shí)別形如別形如Pi的單詞。的單詞。902022-3-17二、二、LEX的實(shí)現(xiàn)的實(shí)現(xiàn)nLEX編譯程序的目的是把一個(gè)編譯程序的目的是把一個(gè)LEX程序改造為一個(gè)詞程序改造為一個(gè)詞法分析器法分析器L，這個(gè)詞法分析器，這個(gè)詞法分析器L將象自動(dòng)機(jī)一樣工作。將象自動(dòng)機(jī)一樣工作。n1詞法分析器詞法分析器L的工作方法的工作方法 L逐個(gè)地掃描輸入串的每個(gè)字符，尋找一個(gè)最大逐個(gè)地掃描輸入串的每個(gè)字符，尋找一個(gè)最大的子串匹配某個(gè)的子串匹配某個(gè)Pi（即：當(dāng)輸入串已匹配某個(gè)詞形（即：當(dāng)輸入串已匹配某個(gè)詞形時(shí)，并不立即返回，而是沿著此道路繼續(xù)前進(jìn)，直時(shí)，