編譯原理課程設(shè)計(jì)之-第二章-詞法分析

1、mcy1 w課程內(nèi)容課程內(nèi)容 第一章第一章 概論概論 第二章第二章 詞法分析詞法分析 第三章上下文無(wú)關(guān)文法及分析第三章上下文無(wú)關(guān)文法及分析 第四章自上而下的語(yǔ)法分析第四章自上而下的語(yǔ)法分析 第五章自下而上的語(yǔ)法分析第五章自下而上的語(yǔ)法分析 第六章語(yǔ)義分析第六章語(yǔ)義分析 第七章運(yùn)行時(shí)環(huán)境第七章運(yùn)行時(shí)環(huán)境 第八章代碼生成第八章代碼生成 mcy2 第第2 2章章 詞法分析詞法分析 2.1 詞法分析器的作用詞法分析器的作用 2.2 正規(guī)表達(dá)式正規(guī)表達(dá)式 2.3 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 2.4 從正規(guī)表達(dá)式到從正規(guī)表達(dá)式到DFA 2.5 用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī)用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī) 2.6 利用利用lex自動(dòng)

2、生成詞法分析自動(dòng)生成詞法分析 程序程序 單詞的描單詞的描 述工具述工具 單詞單詞的識(shí)的識(shí) 別系統(tǒng)別系統(tǒng) 設(shè)計(jì)和設(shè)計(jì)和 實(shí)現(xiàn)詞實(shí)現(xiàn)詞 法分析法分析 程序程序 作業(yè)作業(yè) 課程設(shè)計(jì)課程設(shè)計(jì)1 1 mcy3 2.1 2.1 詞法分析器的作用詞法分析器的作用 詞法分析器詞法分析器( (詞法分析程序詞法分析程序) )的任務(wù)的任務(wù)：從源從源 代碼中讀取輸入字符，產(chǎn)生單詞序列代碼中讀取輸入字符，產(chǎn)生單詞序列(生生 成獨(dú)立的有意義的邏輯單元稱作單詞成獨(dú)立的有意義的邏輯單元稱作單詞 (token)，提交給語(yǔ)法分析使用。，提交給語(yǔ)法分析使用。 mcy4 任務(wù)任務(wù)：逐個(gè)讀入源程序字符并按照：逐個(gè)讀入源程序字符并按照構(gòu)

3、詞規(guī)則構(gòu)詞規(guī)則切分切分 成一系列單詞。單詞是語(yǔ)言中具有獨(dú)立意義的成一系列單詞。單詞是語(yǔ)言中具有獨(dú)立意義的 最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo) 點(diǎn)符號(hào)和常量等。點(diǎn)符號(hào)和常量等。 w識(shí)別出源程序中的單詞；識(shí)別出源程序中的單詞； w刪除無(wú)用的空白字符及注釋（空格、回車刪除無(wú)用的空白字符及注釋（空格、回車 等），這些信等），這些信 息僅增加了源程序的可讀性，便于程序員閱讀和維護(hù)程息僅增加了源程序的可讀性，便于程序員閱讀和維護(hù)程 序，而對(duì)于語(yǔ)法分析是完全無(wú)用的。序，而對(duì)于語(yǔ)法分析是完全無(wú)用的。 w進(jìn)行詞法檢查，能夠檢測(cè)出輸入中不能形成進(jìn)行詞法檢查，能夠檢測(cè)出

4、輸入中不能形成源語(yǔ)言任何源語(yǔ)言任何 單詞的錯(cuò)誤字符串單詞的錯(cuò)誤字符串。 mcy5 The big elephant ate the peanut.The big elephant ate the peanut. big 詞法分析的結(jié)果：詞法分析的結(jié)果： mcy6 token表示的字符串表示的字符串（串值或詞義串值或詞義）：）： if , y, ,3,then,x,=,0 token的的類型（詞法）類型（詞法）： 關(guān)鍵字（關(guān)鍵字（if, else, for,int,return） 操作符（操作符（+ , -, ） 數(shù)字?jǐn)?shù)字 （3, 45,） 標(biāo)示符（標(biāo)示符（x, y, ） 詞法分析器的輸出詞法分

5、析器的輸出: : token序列序列 mcy7 if y3 then x=0 LT, 詞法分析器詞法分析器 例如：例如：C源代碼源代碼:if y3 then x=0,詞法詞法 分析器的輸出是？分析器的輸出是？ mcy8 定義邏輯項(xiàng)定義邏輯項(xiàng)token的數(shù)據(jù)類型的數(shù)據(jù)類型： typedef struct union char *stringval; int numval; attribute; TokenRecord; TokenType tokenval; Token 類型類型 Token 詞義詞義 mcy9 詞法分析程序的函數(shù)接口：詞法分析程序的函數(shù)接口： TokenRecord getTo

6、ken(void); Token getToken() 源程序源程序 詞法分析程序詞法分析程序語(yǔ)法分析程序語(yǔ)法分析程序 符號(hào)表符號(hào)表 mcy10 第第2 2章章 詞法分析詞法分析 2.1 詞法分析器的作用詞法分析器的作用 2.2 正規(guī)表達(dá)式正規(guī)表達(dá)式 2.3 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 2.4 從正規(guī)表達(dá)式到從正規(guī)表達(dá)式到DFA 2.5 用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī)用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī) 2.6 利用利用lex自動(dòng)生成詞法分析自動(dòng)生成詞法分析 程序程序 記號(hào)的描記號(hào)的描 述工具述工具 記號(hào)的識(shí)記號(hào)的識(shí) 別系統(tǒng)別系統(tǒng) 設(shè)計(jì)和設(shè)計(jì)和 實(shí)現(xiàn)詞實(shí)現(xiàn)詞 法分析法分析 程序程序 作業(yè)作業(yè) 課程設(shè)計(jì)課程設(shè)計(jì)1 1 mcy1

7、1 正規(guī)表達(dá)式的引入：正規(guī)表達(dá)式的引入： 對(duì)自動(dòng)生成詞法分析程序而言，正規(guī)表達(dá)對(duì)自動(dòng)生成詞法分析程序而言，正規(guī)表達(dá) 式也是非常有用的工具。式也是非常有用的工具。 所謂所謂正規(guī)表達(dá)式正規(guī)表達(dá)式就是用特定的就是用特定的運(yùn)算符運(yùn)算符及及運(yùn)算運(yùn)算 對(duì)象對(duì)象按某種規(guī)則構(gòu)造的表達(dá)式。例如：按某種規(guī)則構(gòu)造的表達(dá)式。例如：c-語(yǔ)語(yǔ) 言的詞法言的詞法。 正規(guī)表達(dá)式用來(lái)描述單詞正規(guī)表達(dá)式用來(lái)描述單詞結(jié)構(gòu)結(jié)構(gòu)( (定義單詞定義單詞) )。 mcy12 2.2.1 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ) 2.2.2 正規(guī)表達(dá)式的定義正規(guī)表達(dá)式的定義 2.2.3 正規(guī)表達(dá)式基本等價(jià)關(guān)系正規(guī)表達(dá)式基本等價(jià)關(guān)系 2.2.4 正規(guī)表達(dá)

8、式的擴(kuò)展正規(guī)表達(dá)式的擴(kuò)展 2.2.5 單詞的正規(guī)表達(dá)式舉例單詞的正規(guī)表達(dá)式舉例 2.22.2正規(guī)表達(dá)式正規(guī)表達(dá)式 單詞的描述工具單詞的描述工具 mcy13 2.2.1 2.2.1 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ) 字母表（符號(hào)表、符號(hào)集）字母表（符號(hào)表、符號(hào)集） 由若干元素由若干元素 （符號(hào)、字母）組成的有限非空集合。（符號(hào)、字母）組成的有限非空集合。 不同的語(yǔ)言可以有不同的字母表，例如不同的語(yǔ)言可以有不同的字母表，例如 漢語(yǔ)的字母表中包括漢字、數(shù)字及標(biāo)點(diǎn)漢語(yǔ)的字母表中包括漢字、數(shù)字及標(biāo)點(diǎn) 符號(hào)等。符號(hào)等。 mcy14 符號(hào)串符號(hào)串 由字母表中的符號(hào)組成的任何有由字母表中的符號(hào)組成的任何有 窮序列

9、稱為符號(hào)串窮序列稱為符號(hào)串: 例如例如00 11 10 是字母表是字母表 =0，1上上 的符號(hào)串。的符號(hào)串。 字母表字母表A=a，b，c上的符號(hào)串有：上的符號(hào)串有： a，b，c，ab，aaca。 在符號(hào)串中，符號(hào)的順序是很重要的，符在符號(hào)串中，符號(hào)的順序是很重要的，符 號(hào)串號(hào)串a(chǎn)b就不同于就不同于ba，abca和和aabc也不同。也不同。 mcy15 符號(hào)串的長(zhǎng)度符號(hào)串的長(zhǎng)度 如果某符號(hào)串如果某符號(hào)串x x中有中有m m個(gè)符號(hào)，個(gè)符號(hào)， 則稱其長(zhǎng)度為則稱其長(zhǎng)度為m m，表示為表示為x x=m=m，如如001110001110 的長(zhǎng)度是的長(zhǎng)度是6 6。 空符號(hào)串空符號(hào)串，即不包含任何符號(hào)的符號(hào)串

10、，用，即不包含任何符號(hào)的符號(hào)串，用 表示，其長(zhǎng)度為表示，其長(zhǎng)度為0 0，即，即=0=0。 mcy16 w符號(hào)串的連接符號(hào)串的連接：設(shè)：設(shè)x和和y是符號(hào)串，它們的連是符號(hào)串，它們的連 接接xy是把是把y的符號(hào)寫在的符號(hào)寫在x的符號(hào)之后得到的符的符號(hào)之后得到的符 號(hào)串。號(hào)串。 例如例如 x=ST，y=abu，則它們的連接則它們的連接 xy=STabu，x=2，y=3，xy=5 由于由于的含義，顯然有的含義，顯然有x=x=x。 w符號(hào)串的方冪符號(hào)串的方冪：符號(hào)串自身連接符號(hào)串自身連接n次得到的符次得到的符 號(hào)串號(hào)串xn 定義為定義為 xxxx； n個(gè)個(gè)x x1=x, x2=xx 且且x0= mcy1

11、7 例；若例；若x=ab x=ab 則則: : x x0 0 = = x x1 1 =ab =ab x x2 2 = abab = abab x x3 3 = ababab = ababab x xn n = xx = xxn-1 n-1 = x = xn-1 n-1x (n0) x (n0) mcy18 符號(hào)串集合符號(hào)串集合：若集合若集合A A中所有元素都是中所有元素都是 某字母表某字母表 上的符號(hào)串，則稱上的符號(hào)串，則稱A A為字母表為字母表 上的符號(hào)串集合。上的符號(hào)串集合。 符號(hào)串集合的和與積符號(hào)串集合的和與積 設(shè)設(shè)A A，B B為兩個(gè)符號(hào)串集合，定義為兩個(gè)符號(hào)串集合，定義 和和 A A

12、+B(+B(或或A A B)B) =w|w =w|w A A，或或w w BB 積積AB=xy|xAB=xy|x A,yA,y BB mcy19 v若用若用表示空集，則有：表示空集，則有： A+ = +A = A A = A = A = A = A v 例：若集合例：若集合A= = ab,cde ，集合集合B = B = 0,1 ， 則則AB = ab1,ab0,cde0,cde1 ； mcy20 的閉包：的閉包：用用 * *表示表示 上的一切符號(hào)串（包括上的一切符號(hào)串（包括 ）組成的集合，組成的集合，* *稱為稱為的閉包的閉包。 例如例如：=a,b =a,b * *=,a,b,aa,ab,b

13、a,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, 的正閉包：的正閉包： 上上除除外的所有符號(hào)串組成的外的所有符號(hào)串組成的 集合記為集合記為 + + ， ，+ +稱為稱為的正閉包的正閉包。 例如例如：=a,b =a,b + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab, mcy21 2.2.1 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ) 2.2.2 正規(guī)表達(dá)式的定義正規(guī)表達(dá)式的定義 2.2.3 正規(guī)表達(dá)式基本等價(jià)關(guān)系正規(guī)表達(dá)式基本等價(jià)關(guān)系 2.2.4 正規(guī)表達(dá)式的擴(kuò)展正規(guī)表達(dá)式的擴(kuò)展 2.2.5 單詞的正規(guī)表達(dá)式舉例單詞的正

14、規(guī)表達(dá)式舉例 2.22.2正規(guī)表達(dá)式正規(guī)表達(dá)式 mcy22 w正規(guī)表達(dá)式正規(guī)表達(dá)式(也稱正則表達(dá)式也稱正則表達(dá)式)就是用特定的就是用特定的運(yùn)算運(yùn)算 符符及及運(yùn)算對(duì)象運(yùn)算對(duì)象按某種規(guī)則構(gòu)造的表達(dá)式。按某種規(guī)則構(gòu)造的表達(dá)式。 w每個(gè)正規(guī)表達(dá)式代表一個(gè)每個(gè)正規(guī)表達(dá)式代表一個(gè)字符串的集合字符串的集合，我們，我們 把其稱為正規(guī)集。把其稱為正規(guī)集。 w語(yǔ)言語(yǔ)言(Language)是字符串組成的集合，我們也可是字符串組成的集合，我們也可 以把正規(guī)表達(dá)式表示的以把正規(guī)表達(dá)式表示的正規(guī)集正規(guī)集稱為該正規(guī)表達(dá)稱為該正規(guī)表達(dá) 式表示的式表示的語(yǔ)言語(yǔ)言。 2.2.22.2.2正規(guī)表達(dá)式的定義正規(guī)表達(dá)式的定義 mcy2

15、3 w正規(guī)表達(dá)式和它所表示的正規(guī)集正規(guī)表達(dá)式和它所表示的正規(guī)集(字符串的集字符串的集 合合)的遞歸定義如下的遞歸定義如下： 設(shè)有字母表為設(shè)有字母表為，輔助字母表輔助字母表=, | , . , * , ( , ) mcy24 (1)和和是是上的正規(guī)式，它們所表示的正規(guī)集上的正規(guī)式，它們所表示的正規(guī)集 分別為分別為和和; (2) 若若a，則則a是是上的正規(guī)式，它所表示的上的正規(guī)式，它所表示的 正規(guī)集為正規(guī)集為a; 若若r和和s都是都是上的上的正規(guī)式正規(guī)式，且它們所表示的，且它們所表示的 正規(guī)集正規(guī)集分別為分別為L(zhǎng)(r)和和L(s)，那么：那么： mcy25 r|s 是是正規(guī)式正規(guī)式，表示的，表示的

16、正規(guī)集正規(guī)集為為 L(r|s)=L(r)L(s) ； rs 是是正規(guī)式正規(guī)式，表示的，表示的正規(guī)集正規(guī)集為為 L(rs)=L(r)L(s) ； r *是是正規(guī)式正規(guī)式，表示的，表示的正規(guī)集正規(guī)集為為(L(r)*。 (r) 是是正規(guī)式正規(guī)式，表示的，表示的正規(guī)集正規(guī)集為為L(zhǎng)(r)； “.”運(yùn)算符運(yùn)算符 常省略常省略 mcy26 (4)僅由有限次使用上述三步驟而定義的表僅由有限次使用上述三步驟而定義的表 達(dá)式才是達(dá)式才是上的上的正規(guī)式正規(guī)式，僅由這些正規(guī)式僅由這些正規(guī)式 所表示的符號(hào)串集合才是所表示的符號(hào)串集合才是上的上的正規(guī)集。正規(guī)集。 注：算符的優(yōu)先級(jí)為先注：算符的優(yōu)先級(jí)為先“ * ”，再，再

17、“ . ” 最后最后“ | ” ,都是左結(jié)合的，它們滿足結(jié)合都是左結(jié)合的，它們滿足結(jié)合 律。律。 舉例：舉例： C-語(yǔ)言的詞法語(yǔ)言的詞法 mcy27 例例1，令，令 =a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集的例子：上的正規(guī)式和相應(yīng)的正規(guī)集的例子： 正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 aa a b ab (a b)(a b) a a,b ab aa,ab,ba,bb ,a,aa, 任意個(gè)任意個(gè)a的串的串 (a b) a,b* 即即,a,b,aa,ab,ba,bb, mcy28 例例2，正規(guī)式，正規(guī)式(a)| (b) * (c)它所表示的正規(guī)集為：它所表示的正規(guī)集為： 根據(jù)運(yùn)算符的優(yōu)先級(jí)，上述正規(guī)式可以表示根

18、據(jù)運(yùn)算符的優(yōu)先級(jí)，上述正規(guī)式可以表示 成成 a|b*c a|b*c所表示的正規(guī)集為：字符串所表示的正規(guī)集為：字符串a(chǎn)以及由零個(gè)以及由零個(gè) 或多個(gè)或多個(gè)b后跟一個(gè)后跟一個(gè)c 形成的字符串的集合形成的字符串的集合 或?qū)懗苫驅(qū)懗蒐(a|b*c)=a bnc | 其中其中n是大于或等是大于或等 于于0的整數(shù)的整數(shù) mcy29 給定一個(gè)正規(guī)式給定一個(gè)正規(guī)式, ,它唯一確定一個(gè)正規(guī)集；它唯一確定一個(gè)正規(guī)集； 反之不成立。即一個(gè)正規(guī)集可由多個(gè)不同反之不成立。即一個(gè)正規(guī)集可由多個(gè)不同 的正規(guī)式表示。的正規(guī)式表示。 aaaa a,aa, aaa,任意個(gè)任意個(gè)a的串的串 a|aaa|aa a,aa, aaa,任意

19、個(gè)任意個(gè)a的串的串 例如：例如： mcy30 若若二正規(guī)式二正規(guī)式描述同一正規(guī)集，則稱二式描述同一正規(guī)集，則稱二式等等 價(jià)價(jià)( (相等相等) )。 判斷下列正規(guī)表達(dá)式判斷下列正規(guī)表達(dá)式e e1 1和和e e2 2是否等價(jià)？是否等價(jià)？ e1= (a b)， e2 = b a e1= b(ab) ,e2 =(ba) b e1= (a b) , e2 =(a b ) mcy31 w正規(guī)表達(dá)式正規(guī)表達(dá)式是表示模式的一種重要方法，每是表示模式的一種重要方法，每 個(gè)模式匹配一個(gè)字符串集合個(gè)模式匹配一個(gè)字符串集合(即正規(guī)集即正規(guī)集)。 w正規(guī)集正規(guī)集是正規(guī)表達(dá)式所定義的語(yǔ)言。是正規(guī)表達(dá)式所定義的語(yǔ)言。 w正

20、規(guī)表達(dá)式正規(guī)表達(dá)式可以作為字符串集合可以作為字符串集合(即正規(guī)集即正規(guī)集) 的名字。的名字。 mcy32 2.2.1 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ) 2.2.2 正規(guī)表達(dá)式的定義正規(guī)表達(dá)式的定義 2.2.3 正規(guī)表達(dá)式基本等價(jià)關(guān)系正規(guī)表達(dá)式基本等價(jià)關(guān)系 2.2.4 正規(guī)表達(dá)式的擴(kuò)展正規(guī)表達(dá)式的擴(kuò)展 2.2.5 單詞的正規(guī)表達(dá)式舉例單詞的正規(guī)表達(dá)式舉例 2.22.2正規(guī)表達(dá)式正規(guī)表達(dá)式 mcy33 A1. r|s=s|r A2. r|r=r A3. r| =rA4. (r|s)|t=r|(s|t) A5. (rs)t=r(st)A6. r(s|t)=rs|rt A7. (s|t)r=sr|trA8

21、. r = r= A9. r = r=rA10. r*=( |r)*= |rr* 2.2.3 2.2.3 正規(guī)式基本等價(jià)關(guān)系正規(guī)式基本等價(jià)關(guān)系 mcy34 2.2.1 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ) 2.2.2 正規(guī)表達(dá)式的定義正規(guī)表達(dá)式的定義 2.2.3 正規(guī)表達(dá)式基本等價(jià)關(guān)系正規(guī)表達(dá)式基本等價(jià)關(guān)系 2.2.4 正規(guī)表達(dá)式的擴(kuò)展正規(guī)表達(dá)式的擴(kuò)展 2.2.5 單詞的正規(guī)表達(dá)式舉例單詞的正規(guī)表達(dá)式舉例 2.22.2正規(guī)表達(dá)式正規(guī)表達(dá)式 mcy35 2.2.4 2.2.4 正規(guī)表達(dá)式的擴(kuò)展正規(guī)表達(dá)式的擴(kuò)展 w1.一個(gè)或多個(gè)重復(fù)（一個(gè)或多個(gè)重復(fù)（+，*）：）： 假設(shè)假設(shè)r是正則表達(dá)式是正則表達(dá)式， r

22、的重復(fù)是通過(guò)使用標(biāo)準(zhǔn)的閉包運(yùn)算來(lái)描述，的重復(fù)是通過(guò)使用標(biāo)準(zhǔn)的閉包運(yùn)算來(lái)描述， 寫作寫作r*。它允許它允許r被重復(fù)被重復(fù)0次或更多次次或更多次。 用用r +表示表示r 被重復(fù)被重復(fù)1次或更多次次或更多次。因此有：。因此有： (0|1)+=(0|1)(0|1)* mcy36 2.任意字符（任意字符（.）: 句點(diǎn)句點(diǎn)“ .”表示可以匹配除換行符之外的任意單個(gè)符。表示可以匹配除換行符之外的任意單個(gè)符。 利用這個(gè)字符就可為利用這個(gè)字符就可為所有包含至少一個(gè)所有包含至少一個(gè)b 的串的串寫出寫出 一個(gè)一個(gè)正則表達(dá)式正則表達(dá)式，如下所示：，如下所示： .*b .* 3.引號(hào)引號(hào)“ ”，引號(hào)中的字符串表示文本字

23、符，引號(hào)中的字符串表示文本字符 串本身。例如：串本身。例如：“.”表示要匹配表示要匹配.字符本身。字符本身。 mcy37 字符字符范圍范圍： 表示法表示法a|b|z 表示所有小寫字母；表示所有小寫字母； 0|1|9表示表示0到到9間的所有數(shù)字；間的所有數(shù)字； 常見的表示法是利用常見的表示法是利用方括號(hào)方括號(hào)和和一個(gè)連字符一個(gè)連字符，如，如 a-z是指所有小寫字母，是指所有小寫字母，0-9則指數(shù)字。則指數(shù)字。 第二種表示法還可用作表示單個(gè)的解，第二種表示法還可用作表示單個(gè)的解， a|b|c可寫成可寫成abc，它還可用于多個(gè)范圍，它還可用于多個(gè)范圍， 如如 a - z A - Z 代表所有的大小寫

24、字母。代表所有的大小寫字母。 mcy38 正規(guī)表達(dá)式的正規(guī)表達(dá)式的名字名字 為較長(zhǎng)的正則表達(dá)式提供一個(gè)簡(jiǎn)化的名字很有用為較長(zhǎng)的正則表達(dá)式提供一個(gè)簡(jiǎn)化的名字很有用 處，這樣就不用每次使用正則表達(dá)式書寫較長(zhǎng)的處，這樣就不用每次使用正則表達(dá)式書寫較長(zhǎng)的 表達(dá)式本身了；表達(dá)式本身了； 如要寫一個(gè)正則表達(dá)式如要寫一個(gè)正則表達(dá)式: a - z A - Z ( a - z A - Z 0-9 ) 它定義的正規(guī)集為：以字母打頭后跟若干字母或它定義的正規(guī)集為：以字母打頭后跟若干字母或 數(shù)字組成的符號(hào)串的集合數(shù)字組成的符號(hào)串的集合。 mcy39 上述正規(guī)式上述正規(guī)式定義的是程序設(shè)計(jì)語(yǔ)言定義的是程序設(shè)計(jì)語(yǔ)言標(biāo)識(shí)符標(biāo)

25、識(shí)符的的詞法詞法 規(guī)則規(guī)則，通過(guò)為，通過(guò)為正規(guī)表達(dá)式提供一個(gè)簡(jiǎn)化的名字，正規(guī)表達(dá)式提供一個(gè)簡(jiǎn)化的名字， 上述正規(guī)表達(dá)式可寫作：上述正規(guī)表達(dá)式可寫作： letter= a - z A - Z digit=0-9 r=letter(letter digit) mcy40 例：寫出正則表達(dá)式例：寫出正則表達(dá)式signedNat nat=0-9+ signedNat=nat|+ nat|- nat 對(duì)應(yīng)的正規(guī)集？對(duì)應(yīng)的正規(guī)集？ mcy41 w可選的子表達(dá)式（可選的子表達(dá)式（？）：）： w如果在特定的串中包括既可能出現(xiàn)又可能不出現(xiàn)如果在特定的串中包括既可能出現(xiàn)又可能不出現(xiàn) 的可選部分。例如，的可選部分。

26、例如， nat=0-9+ signedNat=nat|+nat|-nat w我們可以引入問(wèn)號(hào)我們可以引入問(wèn)號(hào)?來(lái)表示來(lái)表示r 匹配的串是可選的；上面的匹配的串是可選的；上面的 例子可寫成：例子可寫成： nat=0-9 + signedNat=(+|-)？nat mcy42 2.2.1 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ) 2.2.2 正規(guī)表達(dá)式的定義正規(guī)表達(dá)式的定義 2.2.3 正規(guī)表達(dá)式基本等價(jià)關(guān)系正規(guī)表達(dá)式基本等價(jià)關(guān)系 2.2.4 正規(guī)表達(dá)式的擴(kuò)展正規(guī)表達(dá)式的擴(kuò)展 2.2.5 單詞的正規(guī)表達(dá)式舉例單詞的正規(guī)表達(dá)式舉例 2.22.2正規(guī)表達(dá)式正規(guī)表達(dá)式 mcy43 2.2.5 2.2.5 單詞的正規(guī)

27、表達(dá)式舉例單詞的正規(guī)表達(dá)式舉例 每一種程序設(shè)計(jì)語(yǔ)言都有自己的字符集每一種程序設(shè)計(jì)語(yǔ)言都有自己的字符集( (字母表字母表) ) 。 語(yǔ)言中的各個(gè)語(yǔ)言中的各個(gè)單詞單詞或是或是 上的單個(gè)字符上的單個(gè)字符( (如運(yùn)算符、如運(yùn)算符、 分隔符等分隔符等) )，或是，或是 上的字符串上的字符串( (如常數(shù)、表示符和關(guān)如常數(shù)、表示符和關(guān) 鍵字等鍵字等) )。 程序設(shè)計(jì)語(yǔ)言的程序設(shè)計(jì)語(yǔ)言的單詞單詞都能用都能用正規(guī)式正規(guī)式來(lái)定義來(lái)定義. .由正規(guī)式由正規(guī)式 描述的描述的單詞類單詞類也稱為也稱為正規(guī)集正規(guī)集。 例如：例如：C-語(yǔ)言的詞法語(yǔ)言的詞法 mcy44 1.1.數(shù)：數(shù)： nat= 0-9+ signedNat

28、=(+|-)? nat number=signedNat(“.”nat)?(“E” signedNat)? 例如：例如：3, 3.5, 2.71E-2 2.2.保留字：保留字： reserved=else|if |int|return|void|while mcy45 3.3.標(biāo)示符：標(biāo)示符： letter=a-zA-Z digit=0-9 identifier=letter(letter|digit)* mcy46 包含單詞詞法描述的包含單詞詞法描述的語(yǔ)言手冊(cè)語(yǔ)言手冊(cè)是編譯是編譯 器的程序員最常見的。在下面的示例器的程序員最常見的。在下面的示例 中，被匹配的串是漢語(yǔ)描述，其任務(wù)中，被匹配的串

29、是漢語(yǔ)描述，其任務(wù) 是將描述是將描述翻譯為正則表達(dá)式翻譯為正則表達(dá)式。 mcy47 在字母表在字母表 = a, b, c中，考慮在這個(gè)字中，考慮在這個(gè)字 母表上的母表上的僅包括一個(gè)僅包括一個(gè)b 的所有串的集合的所有串的集合， 這個(gè)集合所對(duì)應(yīng)的正則表達(dá)式為：這個(gè)集合所對(duì)應(yīng)的正則表達(dá)式為： 串串b、abc、abaca、 baaaac、ccbaca和和 ccccccb等都是滿要求的等都是滿要求的 符號(hào)串。符號(hào)串。 (a|c)*b(a|c)* mcy48 在字母表在字母表 = a, b, c中，中，如果字符串集合是如果字符串集合是包括最包括最 多一個(gè)多一個(gè)b 的所有串的所有串，則這個(gè)集合的正則表達(dá)式為

30、：，則這個(gè)集合的正則表達(dá)式為： 僅包括一個(gè)僅包括一個(gè)b 的串的集合對(duì)應(yīng)的正則表達(dá)式的串的集合對(duì)應(yīng)的正則表達(dá)式 (a|c)*b(a|c)* 不包括不包括b 的串的集合對(duì)應(yīng)的正則表達(dá)式的串的集合對(duì)應(yīng)的正則表達(dá)式 (a|c)* 故所求表達(dá)式為：故所求表達(dá)式為：(a|c)* | (a|c)*b(a|c)* 或者為或者為:(a|c)*(b| )(a|c)* mcy49 在在字母表字母表 = a, b上串上串S的集合是由一個(gè)的集合是由一個(gè)b及及 在其前后有相同數(shù)目的在其前后有相同數(shù)目的a 組成：組成： S = b, aba, aabaa, aaabaaa, . . . = anban | n0 正則表達(dá)式

31、并不能描述這個(gè)集合正則表達(dá)式并不能描述這個(gè)集合，其原因在于重復(fù)運(yùn)，其原因在于重復(fù)運(yùn) 算只有閉包運(yùn)算算只有閉包運(yùn)算*一種，它允許有任意次的重復(fù)。因此一種，它允許有任意次的重復(fù)。因此 如要寫出表達(dá)式如要寫出表達(dá)式a*ba*，就不能保證在，就不能保證在b 前后的前后的a 的數(shù)的數(shù) 量是否相等了。量是否相等了。 mcy50 w并非用簡(jiǎn)單術(shù)語(yǔ)描述的所有串都可由并非用簡(jiǎn)單術(shù)語(yǔ)描述的所有串都可由 正則表正則表 達(dá)式產(chǎn)生，因此為了與其他集合相區(qū)分，作達(dá)式產(chǎn)生，因此為了與其他集合相區(qū)分，作 為正則表達(dá)式描述的串集合稱作正規(guī)集為正則表達(dá)式描述的串集合稱作正規(guī)集 (regular set)。 w非正規(guī)集偶爾也作為串

32、出現(xiàn)在需要由掃描程非正規(guī)集偶爾也作為串出現(xiàn)在需要由掃描程 序識(shí)別的程序設(shè)計(jì)語(yǔ)言中。序識(shí)別的程序設(shè)計(jì)語(yǔ)言中。 mcy51 第第2 2章章 詞法分析詞法分析 2.1 詞法分析器的作用詞法分析器的作用 2.2 正規(guī)表達(dá)式正規(guī)表達(dá)式 2.3 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 2.4 從正規(guī)表達(dá)式到從正規(guī)表達(dá)式到DFA 2.5 用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī)用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī) 2.6 利用利用lex自動(dòng)生成詞法分析程序自動(dòng)生成詞法分析程序 記號(hào)的描記號(hào)的描 述工具述工具 記號(hào)的識(shí)記號(hào)的識(shí) 別系統(tǒng)別系統(tǒng) 設(shè)計(jì)和設(shè)計(jì)和 實(shí)現(xiàn)詞實(shí)現(xiàn)詞 法分析法分析 程序程序 作業(yè)作業(yè) 課程設(shè)計(jì)課程設(shè)計(jì)1 1 mcy52 2.3.1有窮自動(dòng)機(jī)的引

33、入有窮自動(dòng)機(jī)的引入 2.3.2確定性有窮自動(dòng)機(jī)確定性有窮自動(dòng)機(jī)(DFA)的定義的定義 2.3.3非確定性有窮自動(dòng)機(jī)非確定性有窮自動(dòng)機(jī)(NFA) 2.32.3有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) mcy53 2.3.1 2.3.1 有窮自動(dòng)機(jī)的引入有窮自動(dòng)機(jī)的引入 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)( (也稱有限自動(dòng)機(jī)也稱有限自動(dòng)機(jī)) )作為一種數(shù)學(xué)模作為一種數(shù)學(xué)模 型型，它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)式所它能準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)式所 表示的集合。表示的集合。 有窮自動(dòng)機(jī)是有窮自動(dòng)機(jī)是設(shè)計(jì)和實(shí)現(xiàn)詞法分析器設(shè)計(jì)和實(shí)現(xiàn)詞法分析器的有效的有效 工具，其直觀圖是一種狀態(tài)轉(zhuǎn)換圖。工具，其直觀圖是一種狀態(tài)轉(zhuǎn)換圖。 引入有窮自動(dòng)

34、機(jī)理論，也是為詞法分析程序引入有窮自動(dòng)機(jī)理論，也是為詞法分析程序 的自動(dòng)構(gòu)造尋找方法和工具。的自動(dòng)構(gòu)造尋找方法和工具。 mcy54 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)( (Finite Automata,or finite-state machines) ) 有窮自動(dòng)機(jī)分為兩類：有窮自動(dòng)機(jī)分為兩類： 確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)( (Deterministic Finite Automata) )。 不確定的有窮自動(dòng)機(jī)不確定的有窮自動(dòng)機(jī)( (Nondeterministic Finite Automata) )。 mcy55 在程序設(shè)計(jì)語(yǔ)言中，用正規(guī)式在程序設(shè)計(jì)語(yǔ)言中，用正規(guī)式定義定義的標(biāo)示符的標(biāo)示符

35、如下：如下： letter=a-zA-Z digit=0-9 identifier=letter(letter|digit)* 該正規(guī)式匹配的標(biāo)示符是以一個(gè)字母開頭且該正規(guī)式匹配的標(biāo)示符是以一個(gè)字母開頭且 其后為任意字母、數(shù)字序列形成的字符串。其后為任意字母、數(shù)字序列形成的字符串。 mcy56 1 2 letterletter digit 標(biāo)示符的有窮自動(dòng)機(jī)標(biāo)示符的有窮自動(dòng)機(jī) 變量變量xtemp xtemp 識(shí)別為標(biāo)示符的過(guò)程可表示為：識(shí)別為標(biāo)示符的過(guò)程可表示為： 1 x 2 t 2 e 2m2 p 2 標(biāo)示符模式的標(biāo)示符模式的識(shí)別識(shí)別過(guò)程：過(guò)程： mcy57 2.3.1有窮自動(dòng)機(jī)的引入有窮自

36、動(dòng)機(jī)的引入 2.3.2確定性有窮自動(dòng)機(jī)確定性有窮自動(dòng)機(jī)(DFA)的定義的定義 2.3.3非確定性有窮自動(dòng)機(jī)非確定性有窮自動(dòng)機(jī)(NFA) 2.32.3有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) mcy58 2.3.22.3.2確定性有窮自動(dòng)機(jī)（確定性有窮自動(dòng)機(jī)（DFADFA）的定義的定義 DFA(DFA(確定性有窮自動(dòng)機(jī)確定性有窮自動(dòng)機(jī)) )有五個(gè)部分組成：有五個(gè)部分組成： (1)(1)有限個(gè)輸入符號(hào)組成的字母表有限個(gè)輸入符號(hào)組成的字母表, ,記作記作 ; ; (2)(2)有限個(gè)狀態(tài)的集合有限個(gè)狀態(tài)的集合, ,記作記作S S; ; (3)(3)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)T T T: T: S S S S 即：即：T(s,c)=

37、 sT(s,c)= s 其中 其中s s S S，s s S S， ， c c 上述轉(zhuǎn)換函數(shù)表示若當(dāng)前狀態(tài)為上述轉(zhuǎn)換函數(shù)表示若當(dāng)前狀態(tài)為s s, ,且當(dāng)前識(shí)別的輸入且當(dāng)前識(shí)別的輸入 符號(hào)為符號(hào)為c c, ,識(shí)別識(shí)別c c后進(jìn)入的下一個(gè)狀態(tài)為后進(jìn)入的下一個(gè)狀態(tài)為s s ; ; mcy59 (4)(4)初始狀態(tài)初始狀態(tài)s s0 0 S S; ;指示識(shí)別符號(hào)串的開始狀態(tài)指示識(shí)別符號(hào)串的開始狀態(tài); ; (5)(5)若干個(gè)若干個(gè)識(shí)別符號(hào)串的識(shí)別符號(hào)串的接受狀態(tài)接受狀態(tài)( (或稱為終止?fàn)罨蚍Q為終止?fàn)?態(tài)態(tài)) )的集合的集合 A A S S ; ; ( (由上述五個(gè)要素組成的五元式由上述五個(gè)要素組成的五元式

38、M=(S;M=(S; ;T;s;T;s0 0;A);A)稱為一稱為一 個(gè)確定的有限自動(dòng)機(jī)個(gè)確定的有限自動(dòng)機(jī) ( (DFADFA: : D Deterministic eterministic F Finite inite A Automatautomata) )。 mcy60 DFA MDFA M= =（ss1 1,s,s2 2 ,s ,s3 3 ,s ,s4 4,a,b,T,s,a,b,T,s1 1,s,s4 4 ） 其中其中轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)T T定義為：定義為： T(s1,a)= s2 T(s3,a)=s2 T(s1,b)=s3 T(s3,b)=s4 T(s2,a)=s4 T(s4,a)=

39、s4 T(s2,b)=s3 T(s4 ,b)=s4 一個(gè)一個(gè)DFA DFA 的例子：的例子： 有限個(gè)狀有限個(gè)狀 態(tài)的集合態(tài)的集合s s 字母表字母表 初始狀態(tài)初始狀態(tài)接受狀接受狀 態(tài)的集合態(tài)的集合A A mcy61 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖 一個(gè)一個(gè)DFADFA可以表示成一個(gè)狀態(tài)圖可以表示成一個(gè)狀態(tài)圖( (或稱或稱狀狀 態(tài)轉(zhuǎn)換圖態(tài)轉(zhuǎn)換圖) )。狀態(tài)轉(zhuǎn)換圖是由一組矢線。狀態(tài)轉(zhuǎn)換圖是由一組矢線 連結(jié)的有限個(gè)結(jié)點(diǎn)所組成的有向圖。連結(jié)的有限個(gè)結(jié)點(diǎn)所組成的有向圖。 例如：例如： s s0 0 s s2 2 0 s s1 1 1 0 mcy62 假定假定DFA MDFA M含有含有m m個(gè)狀態(tài)，那么這個(gè)狀態(tài)圖

40、個(gè)狀態(tài)，那么這個(gè)狀態(tài)圖 就含有就含有m m個(gè)結(jié)點(diǎn)；結(jié)點(diǎn)用小圓圈表示，個(gè)結(jié)點(diǎn)；結(jié)點(diǎn)用小圓圈表示，圓圈圓圈 中標(biāo)入狀態(tài)的名字中標(biāo)入狀態(tài)的名字或編號(hào)?；蚓幪?hào)。 為了醒目起見，用為了醒目起見，用箭頭指示初始狀箭頭指示初始狀 態(tài)，用雙圓圈表示終止轉(zhuǎn)態(tài)。態(tài)，用雙圓圈表示終止轉(zhuǎn)態(tài)。 s s 結(jié)點(diǎn)結(jié)點(diǎn) s s0 0 初始狀態(tài)初始狀態(tài) s sn n 接受狀態(tài)接受狀態(tài) mcy63 s s a s s 狀態(tài)轉(zhuǎn)換的圖形表示狀態(tài)轉(zhuǎn)換的圖形表示 w若若 T(s,a)=s ，則從狀態(tài)結(jié)點(diǎn)則從狀態(tài)結(jié)點(diǎn)s到狀態(tài)結(jié)點(diǎn)到狀態(tài)結(jié)點(diǎn) s畫標(biāo)記為畫標(biāo)記為a的矢線。的矢線。 表示當(dāng)詞法分析器處于該矢線的結(jié)點(diǎn)所指示的表示當(dāng)詞法分析器處于該矢

41、線的結(jié)點(diǎn)所指示的 狀態(tài)狀態(tài)s時(shí)，可能要識(shí)別的輸入字符為時(shí)，可能要識(shí)別的輸入字符為a，而矢線而矢線 進(jìn)入的結(jié)點(diǎn)進(jìn)入的結(jié)點(diǎn)s則指示識(shí)別相應(yīng)的輸入字符則指示識(shí)別相應(yīng)的輸入字符a后后 進(jìn)入的下一個(gè)狀態(tài)。進(jìn)入的下一個(gè)狀態(tài)。 mcy64 例：例： M=(s0 0, s1 1, s2 2, 0,1, T, s0 0, s2 2) 其其 中中, ,T的定義如下：的定義如下： T(s0 0,0)= s1 1 T(s1 1,0)= s1 1 T(s1 1,1)= s2 2 s s0 0 s s2 2 0 s s1 1 1 0 狀態(tài)轉(zhuǎn)換圖舉例狀態(tài)轉(zhuǎn)換圖舉例 上述上述DFADFA對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖：對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖：

42、mcy65 w在狀態(tài)轉(zhuǎn)換圖中，從一個(gè)結(jié)點(diǎn)可以同時(shí)引出若干在狀態(tài)轉(zhuǎn)換圖中，從一個(gè)結(jié)點(diǎn)可以同時(shí)引出若干 條矢線到有向圖中的其余結(jié)點(diǎn)條矢線到有向圖中的其余結(jié)點(diǎn)(也可從一結(jié)點(diǎn)引矢也可從一結(jié)點(diǎn)引矢 線到其自身線到其自身)； w每一矢線上均標(biāo)記一個(gè)字符或字符類記號(hào)，表示每一矢線上均標(biāo)記一個(gè)字符或字符類記號(hào)，表示 當(dāng)詞法分析器處于該矢線的結(jié)點(diǎn)所指示的狀態(tài)時(shí)，當(dāng)詞法分析器處于該矢線的結(jié)點(diǎn)所指示的狀態(tài)時(shí)， 可能要識(shí)別的輸入字符，而矢線進(jìn)入的結(jié)點(diǎn)則指可能要識(shí)別的輸入字符，而矢線進(jìn)入的結(jié)點(diǎn)則指 示識(shí)別相應(yīng)的輸入字符后進(jìn)入的下一個(gè)狀態(tài)。示識(shí)別相應(yīng)的輸入字符后進(jìn)入的下一個(gè)狀態(tài)。 mcy66 DFADFA的接受集的接受集

43、( (即識(shí)別的字符串集合即識(shí)別的字符串集合) ) DFA識(shí)別的字符串識(shí)別的字符串c c1 1 c c2 2 c cn n的集合 的集合滿足如滿足如 下條件：每個(gè)下條件：每個(gè)c ci i ，且存在狀態(tài)，且存在狀態(tài) s1= T(s0 ，c1), s2= T(s1 ，c2), , sn= T(sn-1 ，cn), 其中其中s0 是初態(tài)，是初態(tài)， sn 是終態(tài)。是終態(tài)。 mcy67 s s0 0 c c1 1 s s1 1 c c2 2 s s2 2s sn-1 n-1 c cn n s sn n c c3 3c cn-1 n-1 v字符串字符串c c1 1 c c2 2 c cn n若被 若被DFA

44、識(shí)別，則在狀態(tài)識(shí)別，則在狀態(tài) 轉(zhuǎn)換圖中存在一條從初態(tài)到終態(tài)的有向路經(jīng)，轉(zhuǎn)換圖中存在一條從初態(tài)到終態(tài)的有向路經(jīng)， 該路徑上所有該路徑上所有矢線上方的字符連接在一起即是矢線上方的字符連接在一起即是 字符串字符串c c1 1 c c2 2 c cn n vDFA M識(shí)別的字符串的集合識(shí)別的字符串的集合 記作記作L(M) mcy68 b s1 s2 s3 s4a b b a | b a a 例：證明字符串序列例：證明字符串序列baabbaab被下圖的被下圖的DFADFA所接受。所接受。 任意列出它接受的另外兩個(gè)輸入串？任意列出它接受的另外兩個(gè)輸入串？ 任意列出它拒絕接受的兩個(gè)輸入串？任意列出它拒絕接受

45、的兩個(gè)輸入串？ mcy69 證明：由于存在證明：由于存在 T(sT(s1 1,b,b）= s= s3 3 T(sT(s3 3,a,a）= s= s2 2 T(sT(s2 2,a,a）= s= s4 4 T(sT(s4 4,b,b）= s= s4 4 s s4 4屬于終態(tài)，得證。屬于終態(tài)，得證。 mcy70 (1).狀態(tài)轉(zhuǎn)換圖中的狀態(tài)轉(zhuǎn)換圖中的狀態(tài)狀態(tài)可以使用可以使用任何標(biāo)識(shí)任何標(biāo)識(shí) 系統(tǒng)系統(tǒng)來(lái)標(biāo)識(shí)來(lái)標(biāo)識(shí) (2).狀態(tài)轉(zhuǎn)換圖中的狀態(tài)轉(zhuǎn)換圖中的轉(zhuǎn)換轉(zhuǎn)換可以使用可以使用字符集合字符集合 的名字的名字標(biāo)出標(biāo)出 關(guān)于關(guān)于DFADFA的狀態(tài)轉(zhuǎn)換圖的的狀態(tài)轉(zhuǎn)換圖的2 2點(diǎn)說(shuō)明點(diǎn)說(shuō)明 startin_id l

46、etter letter digit mcy71 1 2 digitdigit 例例1：自然數(shù)的集合自然數(shù)的集合被下圖所示的被下圖所示的DFA接受。接受。 注：注：digit=0-9 DFADFA的示例的示例 mcy72 例例2：字母表字母表 = a, b, c上上有且僅有一個(gè)有且僅有一個(gè)b構(gòu)成構(gòu)成 的字符串集合的字符串集合被下圖所示的被下圖所示的DFA接受。接受。 1 2 bnotb notb 注：注：notb= a, c mcy73 例例3：字母表字母表 = a, b, c上上包含最多一個(gè)包含最多一個(gè)b構(gòu)構(gòu) 成的字符串的集合成的字符串的集合被下圖所示的被下圖所示的DFA接受。接受。 2 b

47、notb notb 1 注：注：notb= a, c mcy74 例例4：有：有C風(fēng)格注釋的風(fēng)格注釋的DFA 15 / other1 2 * 3 * 4 * / other2 注：注：other1other1表示除表示除* *之外的所有字符的集合的名字；之外的所有字符的集合的名字； other2 other2表示除表示除* *,/,/之外的所有字符的集合的名字。之外的所有字符的集合的名字。 mcy75 2.3.1有窮自動(dòng)機(jī)的引入有窮自動(dòng)機(jī)的引入 2.3.2確定性有窮自動(dòng)機(jī)確定性有窮自動(dòng)機(jī)(DFA)的定義的定義 2.3.3非確定性有窮自動(dòng)機(jī)非確定性有窮自動(dòng)機(jī)(NFA) 2.32.3有窮自動(dòng)機(jī)有窮

48、自動(dòng)機(jī) mcy76 2.3.32.3.3非確定性有窮自動(dòng)機(jī)（非確定性有窮自動(dòng)機(jī)（NFANFA） 下圖是識(shí)別下圖是識(shí)別 = =、, , 字符串的一個(gè)字符串的一個(gè) 有窮自動(dòng)機(jī)，對(duì)于輸入符號(hào)有窮自動(dòng)機(jī)，對(duì)于輸入符號(hào),在狀態(tài)在狀態(tài)0 0上上 存在不止一種轉(zhuǎn)換。存在不止一種轉(zhuǎn)換。 1 5 3 0 2 4 mcy77 w有窮自動(dòng)機(jī)對(duì)于某個(gè)輸入符號(hào)，如果有窮自動(dòng)機(jī)對(duì)于某個(gè)輸入符號(hào)，如果 在同一個(gè)狀態(tài)上存在不止一種轉(zhuǎn)換，在同一個(gè)狀態(tài)上存在不止一種轉(zhuǎn)換， 我們稱該有窮自動(dòng)機(jī)為不確定的有窮我們稱該有窮自動(dòng)機(jī)為不確定的有窮 自動(dòng)機(jī)。自動(dòng)機(jī)。 w在給出非確定性有窮自動(dòng)機(jī)的定義之在給出非確定性有窮自動(dòng)機(jī)的定義之 前先引

49、入前先引入 - -轉(zhuǎn)換轉(zhuǎn)換的概念。的概念。 mcy78 - -轉(zhuǎn)換轉(zhuǎn)換是無(wú)需考慮輸入串就有可能發(fā)生的是無(wú)需考慮輸入串就有可能發(fā)生的 轉(zhuǎn)換。它可看作是一個(gè)空串轉(zhuǎn)換。它可看作是一個(gè)空串 的的“匹配匹配”， - -轉(zhuǎn)換的圖形表示為：轉(zhuǎn)換的圖形表示為： 0 0 1 1 - -轉(zhuǎn)換的引入轉(zhuǎn)換的引入 - -轉(zhuǎn)換轉(zhuǎn)換可以清晰地描述出空串的匹配：可以清晰地描述出空串的匹配： 0 0 1 1 mcy79 0 - -轉(zhuǎn)換轉(zhuǎn)換可以通過(guò)添加一個(gè)新的初始狀態(tài)來(lái)鏈接各個(gè)可以通過(guò)添加一個(gè)新的初始狀態(tài)來(lái)鏈接各個(gè) 自動(dòng)機(jī)，從而將它們合并為一個(gè)自動(dòng)機(jī)。自動(dòng)機(jī)，從而將它們合并為一個(gè)自動(dòng)機(jī)。將識(shí)別數(shù)字將識(shí)別數(shù)字 和字符的兩個(gè)和字符的

50、兩個(gè)DFADFA和并為一個(gè)非確定的有窮自動(dòng)機(jī)：和并為一個(gè)非確定的有窮自動(dòng)機(jī)： letterletter letterletter DONE2DONE2 START2START2 START1START1 digitdigit digitdigit DONE1DONE1 mcy80 0 1 2 3 : := = 6 7 5 = = 8 9 = = 通過(guò)通過(guò) - -轉(zhuǎn)換將識(shí)別轉(zhuǎn)換將識(shí)別:=:=、=、= =的的DFADFA合并為：合并為： mcy81 NFA( (非確定性有窮自動(dòng)機(jī)非確定性有窮自動(dòng)機(jī)) )有五個(gè)部分組成：有五個(gè)部分組成： (1)(1)有限個(gè)輸入符號(hào)組成的字母表有限個(gè)輸入符號(hào)組成的字母

51、表, ,記作記作 ; ; (2)(2)有限個(gè)狀態(tài)的集合有限個(gè)狀態(tài)的集合, ,記作記作S S; ; (3)(3)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)T T; ; T: T: S S ( ( )(S)(S), , T(s,c)= s T(s,c)= sk1, s skm 表示若當(dāng)前狀態(tài)為表示若當(dāng)前狀態(tài)為s s S S, ,且要識(shí)別的輸入符號(hào)為且要識(shí)別的輸入符號(hào)為c c , , 識(shí)識(shí) 別別c c后進(jìn)入的狀態(tài)是后進(jìn)入的狀態(tài)是S S的一個(gè)狀態(tài)的一個(gè)狀態(tài)子集子集ssk1, s skm ; ; 2.3.22.3.2非確定性有窮自動(dòng)機(jī)（非確定性有窮自動(dòng)機(jī)（NFANFA）的定義的定義 mcy82 (4)(4)初始狀態(tài)初始狀態(tài)s s

52、0 0 S S; ; (5)(5)若干個(gè)接受狀態(tài)的集合若干個(gè)接受狀態(tài)的集合: : A A S S 由上述五個(gè)要素組成的五元式由上述五個(gè)要素組成的五元式 M=(SM=(S； ； T T； s s0 0 ； ； A )A )稱為一個(gè)非確定的有限稱為一個(gè)非確定的有限 自動(dòng)機(jī)自動(dòng)機(jī) ( (NFANFA: : Nondeterministicondeterministic F Finite inite A Automatautomata),),由上述定義由上述定義可以看出，可以看出，DFADFA是是NFANFA的一個(gè)的一個(gè) 特例。特例。 mcy83 一個(gè)一個(gè)NFA NFA 的例子：的例子： NFA M=

53、NFA M=（SS，P P，ZZ，00，11，T T，SS，ZZ） 其中其中 T T（S S，0 0）=P; =P; T T（Z Z，0 0）=P;=P; T T（P P，1 1）=Z; T=Z; T（Z Z，1 1）=P;=P; T T（S S，1 1）=S=S，Z;Z; mcy84 NFANFA的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖 例：例：M=( , = , 0，1，2，3，4，5 , T, 0, 2，4，5 ) 其中其中T的定義如下：的定義如下： T(0,) = 4 1 5 3 0 2 4 mcy85 NFA M 的的接受集接受集記作記作L(M)L(M) L(M)定義為定義為字符串字符串c c1 1

54、c c2 2 c cn n的集合 的集合，其中每個(gè)，其中每個(gè) c ci i ，且存在：，且存在： s s1 1 T(sT(s0 0 , ,c c1 1) ), , s s2 2 T(sT(s1 1, ,c c2 2),), , s sn n T(sT(sn-1 n-1 , ,c cn n), ), 其中其中s s0 0是初態(tài)，是初態(tài)， s sn n是終態(tài)集中的一個(gè)元素。是終態(tài)集中的一個(gè)元素。 NFANFA的接受集的接受集 mcy86 例：考慮下面的例：考慮下面的NFA圖。圖。 2 3 1 a a a a b b 4 這個(gè)這個(gè)NFA接受集與正接受集與正 則表達(dá)式則表達(dá)式 ab+|ab*|b*對(duì)應(yīng)

55、的對(duì)應(yīng)的 正規(guī)集相同。正規(guī)集相同。 列舉兩個(gè)轉(zhuǎn)換序列都可接受串列舉兩個(gè)轉(zhuǎn)換序列都可接受串a(chǎn)bb？ 1 a 2 b 4 2 b 4 1 a 3 4 2 b 4 2 b 4 mcy87 第第2 2章章 詞法分析詞法分析 2.1 詞法分析器的作用詞法分析器的作用 2.2 正規(guī)表達(dá)式正規(guī)表達(dá)式 2.3 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 2.4 從正規(guī)表達(dá)式到從正規(guī)表達(dá)式到DFA 2.5 用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī)用代碼實(shí)現(xiàn)有窮自動(dòng)機(jī) 2.6 利用利用lex自動(dòng)生成詞法分析自動(dòng)生成詞法分析 程序程序 記號(hào)的描記號(hào)的描 述工具述工具 記號(hào)的識(shí)記號(hào)的識(shí) 別系統(tǒng)別系統(tǒng) 設(shè)計(jì)和設(shè)計(jì)和 實(shí)現(xiàn)詞實(shí)現(xiàn)詞 法分析法分析 程序程序 作業(yè)作

56、業(yè) 課程設(shè)計(jì)課程設(shè)計(jì)1 1 mcy88 2.42.4從正規(guī)表達(dá)式到從正規(guī)表達(dá)式到DFADFA 正規(guī)表達(dá)式正規(guī)表達(dá)式 DFA詞法分析程序詞法分析程序NFA 正規(guī)式正規(guī)式是單詞的一種描述工具。由于正規(guī)是單詞的一種描述工具。由于正規(guī) 式的簡(jiǎn)潔性，趨向于先用式的簡(jiǎn)潔性，趨向于先用正規(guī)式來(lái)描述單正規(guī)式來(lái)描述單 詞詞，然后，然后構(gòu)造等價(jià)的有限自動(dòng)機(jī)構(gòu)造等價(jià)的有限自動(dòng)機(jī)。 有限自動(dòng)機(jī)有限自動(dòng)機(jī)可以描述輸入串被識(shí)別的過(guò)可以描述輸入串被識(shí)別的過(guò) 程，我們可以根據(jù)有限自動(dòng)機(jī)程，我們可以根據(jù)有限自動(dòng)機(jī)構(gòu)造構(gòu)造我們的我們的 詞法分析程序詞法分析程序。 mcy89 正規(guī)式正規(guī)式和和有限自動(dòng)機(jī)有限自動(dòng)機(jī)之間可以之間可以相

57、互轉(zhuǎn)換相互轉(zhuǎn)換， 也就是說(shuō)它們之間存在著也就是說(shuō)它們之間存在著等價(jià)性等價(jià)性，即，即： 對(duì)于對(duì)于上的上的NFA M，可以構(gòu)造一個(gè)可以構(gòu)造一個(gè)上的上的 正規(guī)式正規(guī)式R，使得：使得：L(R)=L(M) 對(duì)于對(duì)于上的每個(gè)正規(guī)式上的每個(gè)正規(guī)式R，可以構(gòu)造一個(gè)可以構(gòu)造一個(gè) 上的上的NFA M，使得：使得：L(M)=L(R) mcy90 2.4.1 從正規(guī)表達(dá)式到從正規(guī)表達(dá)式到NFA 2.4.2 從從NFA 到到DFA 2.4.3 將將DFA中的狀態(tài)數(shù)最小化中的狀態(tài)數(shù)最小化 2.42.4從正規(guī)表達(dá)式到從正規(guī)表達(dá)式到DFADFA mcy91 2.4.1 2.4.1 從正規(guī)表達(dá)式到從正規(guī)表達(dá)式到NFANFA 從

58、正規(guī)表達(dá)式到從正規(guī)表達(dá)式到NFA的轉(zhuǎn)化方法按正規(guī)式的運(yùn)算的轉(zhuǎn)化方法按正規(guī)式的運(yùn)算 指引構(gòu)造過(guò)程，指引構(gòu)造過(guò)程，將正規(guī)式分解為一系列子表達(dá)式，將正規(guī)式分解為一系列子表達(dá)式， 然后將子表達(dá)式對(duì)應(yīng)的然后將子表達(dá)式對(duì)應(yīng)的NFA依次連接而成依次連接而成，正規(guī)正規(guī) 式式R轉(zhuǎn)化為轉(zhuǎn)化為NFA M 的基本步驟：的基本步驟： mcy92 (b)對(duì)正規(guī)式對(duì)正規(guī)式，等價(jià)的等價(jià)的NFA為：為： 0 0 1 1 (a)對(duì)正規(guī)式對(duì)正規(guī)式，等價(jià)的等價(jià)的NFA為：為： 0 01 1 (c)對(duì)正規(guī)式對(duì)正規(guī)式a，等價(jià)的等價(jià)的NFA為：為： 0 0 a a 1 1 1. 基本正規(guī)式轉(zhuǎn)換為基本正規(guī)式轉(zhuǎn)換為NFA M的方法：的方法：

59、mcy93 0 0 R R 1 1 2. 復(fù)合正規(guī)式復(fù)合正規(guī)式R轉(zhuǎn)換為轉(zhuǎn)換為NFA M的方法：首先將復(fù)的方法：首先將復(fù) 合正規(guī)表達(dá)式表示成如下拓廣的狀態(tài)轉(zhuǎn)換圖，合正規(guī)表達(dá)式表示成如下拓廣的狀態(tài)轉(zhuǎn)換圖， 然后按照正規(guī)式的運(yùn)算然后按照正規(guī)式的運(yùn)算(以下以下(a),(b),(c),(d)四種四種 情況情況)遞歸生成遞歸生成NFA M mcy94 (b)若若R=rs,則將則將 代之以代之以 0 01 1 rsrs 0 0 1 1 r r 2 2 s s (a)若若R=r|s,則將則將 代之以代之以 0 01 1 r|sr|s 0 0 1 1 r r s s mcy95 (c)若若R=r*,則將則將 代

60、之以代之以 0 01 1 r r* 0 0 1 1 2 2 r r (d)正規(guī)式正規(guī)式R=（r）的的NFA同正規(guī)式同正規(guī)式 R=r 的的NFA相同相同 mcy96 例例1 1, ,設(shè)有正規(guī)表達(dá)式設(shè)有正規(guī)表達(dá)式R=ab|a, ,試構(gòu)造試構(gòu)造NFA M， 使使L(R)=L(M)。 （1 1） 0 0 ab|aab|a 1 1 （2 2）0 0 abab 1 1 a a （3 3）0 0 1 1 a a 2 2a a b b mcy97 例例2 2，設(shè)有正規(guī)表達(dá)式，設(shè)有正規(guī)表達(dá)式 letter(letter|digit)letter(letter|digit)* *, ,試構(gòu)造與之等試構(gòu)造與之等 價(jià)