編譯原理第三章 詞法分析

1、編譯原理第三章 詞法分析第1頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 幾個(gè)概念:考慮一個(gè)有窮 字母表 字符集其中每一個(gè)元素稱為一個(gè)字符上的字(也叫字符串) 是指由中的字符所構(gòu)成的一個(gè)有窮序列不包含任何字符的序列稱為空字，記為用*表示上的所有字的全體,包含空字第2頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 *的子集U和V的連接（積）定義為UV | U & V V自身的 n次積記為Vn=VVV規(guī)定V0=，令 V*=V0V1V2V3 稱V*是V的閉包;記 VVV* ，稱V+是V的正規(guī)閉包。第3頁(yè)，共111頁(yè)，202

2、2年，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 上下文無(wú)關(guān)文法的定義： 一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式 G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT VN=S：文法的開(kāi)始符號(hào)，SVNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為P， PVN， (VT VN)*開(kāi)始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。第4頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 定義：稱A直接推出，即A 僅當(dāng)A 是一個(gè)產(chǎn)生式， 且， (VT VN)* 。如果1 2 n，則我們稱這個(gè)序列是從1到n的一個(gè)推導(dǎo)。若存在一個(gè)從1到n

3、的推導(dǎo)，則稱1可以推導(dǎo)出n 。第5頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二通常，用 表示：從1出發(fā)，經(jīng)過(guò)一步或若干步，可以推出n。 用 表示：從1出發(fā)，經(jīng)過(guò)0步或若干步，可以推出n。 所以 ： 即 或定義：假定G是一個(gè)文法，S 是它的開(kāi)始符號(hào)。如果 ，則稱是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，將它記為 L(G)。第6頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 最左推導(dǎo)：任何一步 都是對(duì)中的最左非終結(jié)符進(jìn)行替換。 最右推導(dǎo)：任何一步 都是對(duì)中的最右非終結(jié)符進(jìn)行替換。第7頁(yè)，共111頁(yè)，2022年

4、，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 用一張圖表示一個(gè)句型的推導(dǎo),稱為語(yǔ)法樹(shù)。E (E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E (E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)第8頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩顆不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的。語(yǔ)言的二義性：一個(gè)語(yǔ)言是二義性的，如果對(duì)它不存在無(wú)二義性的文法。第9頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 形式語(yǔ)言鳥(niǎo)瞰0型(短語(yǔ)文法，圖靈機(jī)

5、)： 產(chǎn)生式形如： 其中： (VT VN)*且至少含有一個(gè)非終結(jié)符； (VT VN)*1型(上下文有關(guān)文法，線性界限自動(dòng)機(jī))： 產(chǎn)生式形如： 其中：| |，僅 S 例外。第10頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二復(fù)習(xí)：程序語(yǔ)言的語(yǔ)法描述 形式語(yǔ)言鳥(niǎo)瞰2型(上下文無(wú)關(guān)文法，非確定下推自動(dòng)機(jī))： 產(chǎn)生式形如： A 其中：A VN； (VT VN)*。3型(正規(guī)文法，有限自動(dòng)機(jī))： 產(chǎn)生式形如： A B 或 A 其中： VT*；A，BVN 產(chǎn)生式形如： A B 或 A 其中： VT*；A，BVN第11頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二第三章 詞法分析

6、詞法分析是編譯的第一個(gè)階段，在單詞的級(jí)別上分析和翻譯源程序。理論基礎(chǔ)：有限自動(dòng)機(jī)理論；有限自動(dòng)機(jī)理論與正規(guī)文法、正規(guī)式之間在描述語(yǔ)言方面有一一對(duì)應(yīng)的關(guān)系。學(xué)習(xí)目標(biāo)：掌握有限自動(dòng)機(jī)與正規(guī)文法、正規(guī)式之間的轉(zhuǎn)換能夠構(gòu)造詞法分析程序。第12頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二第三章 詞法分析詞法分析的任務(wù)：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符號(hào)。詞法分析器(Lexical Analyzer) 又稱掃描器(Scanner)：執(zhí)行詞法分析的程序第13頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.1 對(duì)于詞法分析器的要求一、詞法分析器的功能和輸出形

7、式功能:輸入源程序、輸出單詞符號(hào)單詞符號(hào)的種類：基本字：如 begin，repeat，標(biāo)識(shí)符表示各種名字：如變量名、數(shù)組名和過(guò)程名常數(shù)：各種類型的常數(shù)運(yùn)算符：+，-，*，/，界符：逗號(hào)、分號(hào)、括號(hào)和空白第14頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二輸出的單詞符號(hào)的表示形式:(單詞種別，單詞自身的值)單詞種別通常用整數(shù)編碼表示。若一個(gè)種別只有一個(gè)單詞符號(hào)，則種別編碼就代表該單詞符號(hào)。假定基本字、運(yùn)算符和界符都是一符一種。若一個(gè)種別有多個(gè)單詞符號(hào)，則對(duì)于每個(gè)單詞符號(hào)，給出種別編碼和自身的值。標(biāo)識(shí)符單列一種；標(biāo)識(shí)符自身的值表示成按機(jī)器字節(jié)劃分的內(nèi)部碼。常數(shù)按類型分種；常數(shù)的值則表

8、示成標(biāo)準(zhǔn)的二進(jìn)制形式。第15頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二例 C程序 while (i=j) i-;輸出單詞符號(hào)：=, - 第16頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二例 FORTRAN程序IF (5.EQ.M) GOTO 100輸出單詞符號(hào)：邏輯IF(34，-)左括號(hào)(2，-)整常數(shù)(20， 5的二進(jìn)制)等號(hào)(6，-)標(biāo)識(shí)符(26， M)右括號(hào)(16，-)GOTO(30，-)標(biāo)號(hào)(19， 100的二進(jìn)制)第17頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二二、詞法分析器作為一個(gè)獨(dú)立子程序詞法分析是作為一個(gè)獨(dú)立的階段，是否應(yīng)當(dāng)將

9、其處理為一遍呢？作為獨(dú)立階段的優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)潔、清晰和條理化，有利于集中考慮詞法分析一些枝節(jié)問(wèn)題。不作為一遍：將其處理為一個(gè)子程序。第18頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二詞法分析器詞法分析器語(yǔ)法分析器符號(hào)表源程序單詞符號(hào)取下一單詞.第19頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二詞法分析器的結(jié)構(gòu)預(yù)處理子程序掃描器輸入緩沖區(qū)掃描緩沖區(qū)單詞符號(hào)輸入列表3.2 詞法分析器的設(shè)計(jì)第20頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二輸入串放在輸入緩沖區(qū)中。預(yù)處理子程序：剔除無(wú)用的空白、跳格、回車和換行等編輯性字符;區(qū)分標(biāo)號(hào)區(qū)、捻接續(xù)行和給出句末符

10、等掃描緩沖區(qū) 起點(diǎn) 搜索指示器 指示器一、輸入、預(yù)處理第21頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二 WhatALongWord WhatALongWo rdrd WhatALongWord WhatALongWo第22頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二二、單詞符號(hào)的識(shí)別:超前搜索1 基本字識(shí)別:例如:DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能確定哪些是基本字第23頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分

11、，星期二2 標(biāo)識(shí)符識(shí)別:字母開(kāi)頭的字母數(shù)字串，后跟界符或算符3 常數(shù)識(shí)別:識(shí)別出算術(shù)常數(shù)并將其轉(zhuǎn)變?yōu)槎M(jìn)制內(nèi)碼表示。有些也要超前搜索。 5.E084 算符和界符的識(shí)別把多個(gè)字符符合而成的算符和界符拼合成一個(gè)單一單詞符號(hào)。:=， *， .EQ. ， +，-，=第24頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二三、狀態(tài)轉(zhuǎn)換圖1 概念狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。213XY結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連結(jié)，箭弧上的標(biāo)記(字符)代表射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)為初態(tài)，至少要有一個(gè)終態(tài)。第25頁(yè)，共111頁(yè)，2022年，5月20

12、日，20點(diǎn)32分，星期二識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖123字母其他字母或數(shù)字*識(shí)別整常數(shù)的狀態(tài)轉(zhuǎn)換圖123數(shù)字其他數(shù)字*一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別(或接受)一定的字符串。第26頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二2 例子助憶符：直接用編碼表示不便于記憶，因此用助憶符來(lái)表示編碼。第27頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二第28頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二123456789101112130空白字母字母或數(shù)字非字母與數(shù)字?jǐn)?shù)字非數(shù)字?jǐn)?shù)字=+*非*,()其它*第29頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二幾點(diǎn)重

13、要限制不必使用超前搜索所有基本字都是保留字;用戶不能用它們作自己的標(biāo)識(shí)符基本字作為特殊的標(biāo)識(shí)符來(lái)處理;不用特殊的狀態(tài)圖來(lái)識(shí)別，只要查保留字表。如果基本字、標(biāo)識(shí)符和常數(shù)(或標(biāo)號(hào))之間沒(méi)有確定的運(yùn)算符或界符作間隔，則必須使用一個(gè)空白符作間隔。DO99K=1，10 要寫成 DO 99 K=1，10第30頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)思想：每個(gè)狀態(tài)結(jié)對(duì)應(yīng)一小段程序。做法:1)對(duì)不含回路的分叉結(jié)，可用一個(gè)CASE語(yǔ)句或一組IF-THEN-ELSE語(yǔ)句實(shí)現(xiàn)GetChar( );if (IsLetter( ) 狀態(tài)j的對(duì)應(yīng)程序段;else if (IsDig

14、it( ) 狀態(tài)k的對(duì)應(yīng)程序段;else if (ch=/) 狀態(tài)l的對(duì)應(yīng)程序段;else 錯(cuò)誤處理;ijkl字母數(shù)字第31頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)2)對(duì)含回路的狀態(tài)結(jié)，可對(duì)應(yīng)一段由WHILE結(jié)構(gòu)和IF語(yǔ)句構(gòu)成的程序.i字母或數(shù)字其它jGetChar( );while (IsLetter( ) or IsDigit( )GetChar( );狀態(tài)j的對(duì)應(yīng)程序段第32頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)3)終態(tài)結(jié)表示識(shí)別出某種單詞符號(hào)，因此，對(duì)應(yīng)語(yǔ)句為 RETURN (C，VAL) 其中，C為單詞

15、種別，VAL為單詞自身值.第33頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二全局變量與過(guò)程1)ch 字符變量、存放最新讀入的源程序字符2)strToken 字符數(shù)組，存放構(gòu)成單詞符號(hào)的字符串3)GetChar 子程序過(guò)程，把下一個(gè)字符讀入到 ch 中4)GetBC 子程序過(guò)程，跳過(guò)空白符，直至 ch 中讀入一非空白符5)Concat 子程序，把ch中的字符連接到 strToken 第34頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二6)IsLetter和 IsDisgital 布爾函數(shù)，判斷ch中字符是否為字母和數(shù)字7) Reserve 整型函數(shù)，對(duì)于 strTo

16、ken 中的字符串查找保留字表，若它是保留字則給出它的編碼，否則回送08) Retract 子程序，把搜索指針回調(diào)一個(gè)字符位置9)InsertId 整型函數(shù)，將strToken中的標(biāo)識(shí)符插入符號(hào)表，返回符號(hào)表指針10)InsertConst 整型函數(shù)過(guò)程，將strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針。 第35頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二int code, value;strToken := “ ”;/*置strToken為空串*/GetChar(); GetBC();if (IsLetter()beginwhile (IsLetter() or IsDi

17、git()beginConcat(); GetChar(); endRetract();code := Reserve();if (code = 0)beginvalue := InsertId(strToken);return ($ID, value);endelsereturn (code, -);end第36頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二else if (IsDigit()beginwhile (IsDigit()beginConcat( ); GetChar( );endRetract();value := InsertConst(strToken);re

18、turn($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) return ($PLUS, -);第37頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二else if (ch =*)beginGetChar();if (ch =*) return ($POWER, -);Retract(); return ($STAR, -);endelse if (ch =;) return ($SEMICOLON, -);else if (ch =() return ($LPAR, -);else if (ch

19、=) return ($RPAR, -);else ProcError( );/* 錯(cuò)誤處理*/第38頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)幾個(gè)概念:考慮一個(gè)有窮 字母表 字符集其中每一個(gè)元素稱為一個(gè)字符上的字(也叫字符串) 是指由中的字符所構(gòu)成的一個(gè)有窮序列不包含任何字符的序列稱為空字，記為用*表示上的所有字的全體,包含空字例如: 設(shè) =a， b，則 *=,a,b,aa,ab,ba,bb,aaa,.第39頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二*的子集U和V的連接（積）定義為UV | U & V V自身的 n次積記為Vn

20、=VVV規(guī)定V0=，令 V*=V0V1V2V3 稱V*是V的閉包;記 VVV* ，稱V+是V的正規(guī)閉包。第40頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.3.1 正規(guī)式和正規(guī)集正規(guī)集可以用正規(guī)表達(dá)式（簡(jiǎn)稱正規(guī)式）表示。正規(guī)表達(dá)式是表示正規(guī)集一種方法。一個(gè)字集合是正規(guī)集當(dāng)且僅當(dāng)它能用正規(guī)式表示。第41頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二正規(guī)式和正規(guī)集的遞歸定義：對(duì)給定的字母表1) 和都是上的正規(guī)式，它們所表示的正規(guī)集為和;2) 任何a ，a是上的正規(guī)式，它所表示的正規(guī)集為a ;第42頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3) 假定

21、e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集為L(zhǎng)(e1)和L(e2)，則i) (e1|e2)為正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1)L(e2)，ii) (e1.e2)為正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1)L(e2)，iii) (e1)*為正規(guī)式，它所表示的正規(guī)集為(L(e1)*，僅由有限次使用上述三步驟而定義的表達(dá)式才是上的正規(guī)式，僅由這些正規(guī)式表示的字集才是上的正規(guī)集。第43頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二所有詞法結(jié)構(gòu)一般都可以用正規(guī)式描述。若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則稱這兩個(gè)正規(guī)式等價(jià)。如b(ab)*=(ba)*b(a*b*)*=(a|b)* L( (ba)

22、*b) = L(ba)*) L(b)= (L(ba)*L(b) = (L(b)L(a)* L(b) = ba* b = , ba, baba, bababa, b= b, bab, babab, bababab, L(b(ab)*) = L(b)L(ab)*) = L(b) (L(ab)*= L(b) (L(a)L(b)*=b ab* = b , ab, abab, ababab, = b, bab, babab, bababab, L(b(ab)*)= L( (ba)*b) b(ab)*=(ba)*b第44頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二對(duì)正規(guī)式，下列等價(jià)成立：e

23、1|e2 = e2|e1 交換律e1 |(e2|e3) = (e1|e2)|e3 結(jié)合律e1(e2e3) = (e1e2)e3 結(jié)合律e1(e2|e3) = e1e2|e1e3 分配律(e2|e3)e1 = e2e1|e3 e1分配律e = e = e e1e2 e2 e1 L(e1|e2) = L(e1 ) L(e2)= L(e2 ) L(e1)= L(e2|e1)第45頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二正規(guī)集正規(guī)式第46頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.3.2 確定有限自動(dòng)機(jī)(DFA)對(duì)狀態(tài)圖進(jìn)行形式化，則可以下定義：自動(dòng)機(jī)M是一個(gè)五

24、元式M=(S, , f, S0, F),其中：1. S: 有窮狀態(tài)集，2. ：輸入字母表(有窮)，3. f: 狀態(tài)轉(zhuǎn)換函數(shù)，為SS的單值部分映射，f(s，a)=s表示：當(dāng)現(xiàn)行狀態(tài)為s，輸入字符為a時(shí)，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s。我們把s稱為s的一個(gè)后繼狀態(tài)。4. S0S是唯一的一個(gè)初態(tài)； 5 FS ：終態(tài)集(可空)。第47頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：f定義如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3狀態(tài)轉(zhuǎn)換矩

25、陣0312aaaa狀態(tài)轉(zhuǎn)換圖bbbb第48頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二DFA可以表示為狀態(tài)轉(zhuǎn)換圖。假定DFA M含有m個(gè)狀態(tài)和n個(gè)輸入字符，那么，這個(gè)圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)頂多含有n條箭弧射出，且每條箭弧用上的不同的輸入字符來(lái)作標(biāo)記。第49頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二對(duì)于*中的任何字，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上的標(biāo)記符連接成的字等于，則稱為DFA M所識(shí)別(接收)DFA M所識(shí)別的字的全體記為L(zhǎng)(M)?？梢宰C明：上的字集V*是正規(guī)集，當(dāng)且僅當(dāng)存在上的DFA M，使得VL(M)。第50頁(yè)，共111頁(yè)，

26、2022年，5月20日，20點(diǎn)32分，星期二3.3.3 非確定有限自動(dòng)機(jī)(NFA) 定義：一個(gè)非確定有限自動(dòng)機(jī)(NFA) M是一個(gè)五元式M=(S, , f, S0, F)，其中：1 S: 有窮狀態(tài)集；2 ：輸入字母表(有窮)；3 f: 狀態(tài)轉(zhuǎn)換函數(shù)，為S*2S的部分映射(非單值)；4 S0S是非空的初態(tài)集；5 F S ：終態(tài)集(可空)。第51頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二從狀態(tài)圖中看NFA 和DFA的區(qū)別： 1 弧上的標(biāo)記可以是*中的一個(gè)字，而不一定是單個(gè)字符； 2 同一個(gè)字可能出現(xiàn)在同狀態(tài)射出的多條弧上。DFA是NFA的特例。第52頁(yè)，共111頁(yè)，2022年，5

27、月20日，20點(diǎn)32分，星期二021 a，baaa，bbba，b012abab識(shí)別所有含相繼兩個(gè)a或相繼兩個(gè)b的字ambn | m，n1第53頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二定義：對(duì)于任何兩個(gè)有限自動(dòng)機(jī)M和M，如果L(M)=L(M)，則稱M與M等價(jià)。自動(dòng)機(jī)理論中一個(gè)重要的結(jié)論：判定兩個(gè)自動(dòng)機(jī)等價(jià)性的算法是存在的。對(duì)于每個(gè)NFA M存在一個(gè)DFA M，使得 L(M)=L(M)。亦即DFA與NFA描述能力相同。第54頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二1. 假定NFA M=，我們對(duì)M的狀態(tài)轉(zhuǎn)換圖進(jìn)行以下改造： 1) 引進(jìn)新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)Y

28、，X,YS， 從X到S0中任意狀態(tài)結(jié)點(diǎn)連一條箭弧， 從F中任意狀態(tài)結(jié)點(diǎn)連一條箭弧到Y(jié)。 2) 對(duì)M的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行替換，其中k是新引入的狀態(tài)。證明:第55頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二代之為ikABjijAB代之為ijA|BijBA代之為ijA*ikjA按下面的三條規(guī)則對(duì)V進(jìn)行分裂:第56頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為上的一個(gè)字符或，最后得到一個(gè)NFA M，顯然L(M)=L(M)第57頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二識(shí)別所有含相繼兩個(gè)a或相繼兩個(gè)b的字XY514236a

29、bababab5126ababaabb第58頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二2. 把上述NFA確定化采用子集法.設(shè)I是的狀態(tài)集的一個(gè)子集，定義I的-閉包-closure(I)為: i) 若sI，則s-closure(I)； ii) 若sI，則從s出發(fā)經(jīng)過(guò)任意條弧而能到達(dá)的任何狀態(tài)s都屬于-closure(I) 即 -closure(I)=Is|從某個(gè)sI出發(fā)經(jīng)過(guò)任意條弧能到達(dá)s第59頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二設(shè)a是中的一個(gè)字符，定義Ia= -closure(J) 其中，J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)集合。第60頁(yè)，共

30、111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二-closure(1)=1，2=I J=5，4，3 Ia= -closure(J)= -closure(5，4，3) =5，4，3，6，2，7，861a234578aa設(shè)a是中的一個(gè)字符，定義Ia= -closure(J) 其中，J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)集合。第61頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二把確定化的過(guò)程: 不失一般性，設(shè)字母表只包含兩個(gè)a和b，我們構(gòu)造一張表:第62頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二首先，置第1行第1列為-closure(X)求出這一列的Ia

31、，Ib；然后，檢查這兩個(gè)Ia，Ib，看它們是否已在表中的第一列中出現(xiàn)，把未曾出現(xiàn)的填入后面的空行的第1列上，求出每行第2，3列上的集合.重復(fù)上述過(guò)程，直到所有第2，3列子集全部出現(xiàn)在第一列為止。第63頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,

32、6,Y5,4,6,1,YXY514236abababab第64頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二現(xiàn)在把這張表看成一個(gè)狀態(tài)轉(zhuǎn)換矩陣，把其中的每個(gè)子集看成一個(gè)狀態(tài)。這張表唯一刻劃了一個(gè)確定的有限自動(dòng)機(jī)M，它的初態(tài)是-closure(X) ，它的終態(tài)是含有原終態(tài)Y的子集。不難看出，這個(gè)DFA M與M等價(jià)。第65頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二Iab0121322153344655656340123546aabbbabaababab第66頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二FA正規(guī)集正規(guī)式DFANFA正規(guī)文法第67頁(yè)，共11

33、1頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.3.4 正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M，如果L(G)L(M)，則稱G和M是等價(jià)的。關(guān)于正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性，有以下結(jié)論：第68頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.3.4 正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性定理： 1.對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)(FA) M，使得L(M)L(G)。 2.對(duì)每一個(gè)FA M，都存在一個(gè)右線性正規(guī)文法GR和左線性正規(guī)文法GL，使得L(M)L(GR)L(GL)。第69頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二

34、證明： 1. 對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都構(gòu)造一個(gè)有限自動(dòng)機(jī)（FA） M，使得L(M)L(G)。(1) 設(shè)右線性正規(guī)文法G=。將VN中的每一非終結(jié)符號(hào)視為狀態(tài)符號(hào)，并增加一個(gè)新的終結(jié)狀態(tài)符號(hào)f，fVN。 令M=，其中狀態(tài)轉(zhuǎn)換函數(shù)由以下規(guī)則定義：第70頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二(a) 若對(duì)某個(gè)AVN及aVT，P中有產(chǎn)生式Aa，則令(A,a)=f(b) 對(duì)任意的AVN及aVT，設(shè)P中左端為A，右端第一符號(hào)為a的所有產(chǎn)生式為：AaA1|aAk （不包括Aa）， 則令(A,a)=A1,Ak。 顯然，上述M是一個(gè)NFA。第71頁(yè)，共111頁(yè)，2022年

35、，5月20日，20點(diǎn)32分，星期二對(duì)于右線性正規(guī)文法G，在S w的最左推導(dǎo)過(guò)程中:利用AaB一次就相當(dāng)于在M中從狀態(tài)A經(jīng)過(guò)標(biāo)記為a的箭弧到達(dá)狀態(tài)B（包括a=的情形）;在推導(dǎo)的最后，利用Aa一次則相當(dāng)于在M中從狀態(tài)A經(jīng)過(guò)標(biāo)記為a的箭弧到達(dá)終結(jié)狀態(tài)f（包括a=的情形）。綜上，在正規(guī)文法G中，S w的充要條件是：在M中，從狀態(tài)S到狀態(tài)f有一條通路，其上所有箭弧的標(biāo)記符號(hào)依次連接起來(lái)恰好等于w，這就是說(shuō)，wL(G)當(dāng)且僅當(dāng)wL(M)，故L(G)L(M)。第72頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二(2) 設(shè)左線性正規(guī)文法G=。將VN中的每一符號(hào)視為狀態(tài)符號(hào)，并增加一個(gè)初始狀態(tài)符號(hào)

36、q0，q0VN。 令M=，其中狀態(tài)轉(zhuǎn)換函數(shù)由以下規(guī)則定義：(a) 若對(duì)某個(gè)AVN及aVT，若P中有產(chǎn)生式Aa，則令(q0,a)=A(b) 對(duì)任意的AVN及aVT，若P中所有右端第一符號(hào)為A，第二個(gè)符號(hào)為a的產(chǎn)生式為：A1Aa, , AkAa， 則令(A,a)=A1,Ak。與(1)類似，可以證明L(G)L(M)。第73頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二GR(A) ：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1D從GR出發(fā)構(gòu)造NFA M = ，M的狀態(tài)轉(zhuǎn)換圖如右圖所示。顯然 L(M) = L(GR)。例:ABCD100,1110f000第

37、74頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.3.4 正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性定理： 1.對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)(FA) M，使得L(M)L(G)。 2.對(duì)每一個(gè)FA M，都存在一個(gè)右線性正規(guī)文法GR和左線性正規(guī)文法GL，使得L(M)L(GR)L(GL)。第75頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二證明2：對(duì)每一個(gè)DFA M，都存在一個(gè)右線性正規(guī)文法GR和左線性正規(guī)文法GL，使得L(M)L(GR)L(GL)。 設(shè)DFA M= (1) 若s0F，我們令GR=，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對(duì)任何a及A

38、,BS，若有(A,a)=B，則： (a) 當(dāng)BF時(shí)，令A(yù)aB， (b) 當(dāng)BF時(shí)，令A(yù)a|aB。第76頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二對(duì)任何w*，不妨設(shè)w=a1ak，其中ai (i=1,k)。若s0 w，則存在一個(gè)最左推導(dǎo)： s0a1A1a1a2A2a1aiAia1ai+1Ai+1a1ak因而，在M中有一條從s0出發(fā)依次經(jīng)過(guò)A1，Ak-1到達(dá)終態(tài)的通路，該通路上所有箭弧的標(biāo)記依次為a1,ak。反之亦然。所以，wL(GR)當(dāng)且僅當(dāng)wL(M)。第77頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二 現(xiàn)在考慮s0F的情形： 因?yàn)?s0, )=s0，所以L(M)

39、。但不屬于上面構(gòu)造的GR所產(chǎn)生的語(yǔ)言L(GR)。不難發(fā)現(xiàn)，L(GR)=L(M)-。 所以，我們?cè)谏鲜鯣R中添加新的非終結(jié)符號(hào)s0，(s0S)和產(chǎn)生式s0s0|，并用s0代替s0作開(kāi)始符號(hào)。這樣修正GR后得到的文法GR仍是右線性正規(guī)文法，并且L(GR)=L(M)。 (2) 類似于(1)，從DFA M出發(fā)可構(gòu)造左線性正規(guī)文法GL，使得L(GL)=L(M)。 最后，由DFA和NFA之間的等價(jià)性，結(jié)論2得證。若有(A,a)=B：(a) 當(dāng)A= q0時(shí)，令Ba，(b) 當(dāng)A q0時(shí)，令BAa第78頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二L(M) = 0(10)*GR = ，其中P由下

40、列產(chǎn)生式組成：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1DL(GR) = L(M) = 0(10)*例3.4 設(shè)DFA M = 。M的狀態(tài)轉(zhuǎn)換圖如下圖所示。ABCD100,11100第79頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二從NFA M出發(fā)構(gòu)造左線性正規(guī)文法GL = ，其中P由下列產(chǎn)生式組成：f0 | C0CB1B0 | C0D1 | C1 | D0 | D1 | B0易證 L(GL) = L(M)。例3.4 設(shè)DFA M = 。M的狀態(tài)轉(zhuǎn)換圖如圖3.9(a)所示。ABCD100,1110f000第80頁(yè)，共111頁(yè)，2022年，5月

41、20日，20點(diǎn)32分，星期二FA正規(guī)集正規(guī)式DFANFA正規(guī)文法第81頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.3.5 正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性定理： 1. 對(duì)任何FA M，都存在一個(gè)正規(guī)式r，使得L(r)=L(M)。 2. 對(duì)任何正規(guī)式r，都存在一個(gè)FA M，使得L(M)=L(r)。對(duì)轉(zhuǎn)換圖概念拓廣，令每條弧可用一個(gè)正規(guī)式作標(biāo)記。(對(duì)一類輸入符號(hào))第82頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二證明： 1 對(duì)上任一NFA M，構(gòu)造一個(gè)上的正規(guī)式r，使得L(r)=L(M)。首先，在M的轉(zhuǎn)換圖上加進(jìn)兩個(gè)狀態(tài)X和Y，從X用弧連接到M的所有初態(tài)結(jié)點(diǎn)，從M的所

42、有終態(tài)結(jié)點(diǎn)用弧連接到Y(jié)，從而形成一個(gè)新的NFA，記為M，它只有一個(gè)初態(tài)X和一個(gè)終態(tài)Y，顯然L(M)=L(M)。然后，反復(fù)使用下面的一條規(guī)則，逐步消去的所有結(jié)點(diǎn)，直到只剩下X和Y為止；第83頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二代之為ijr1r2kikr1r2代之為ijr1|r2ijr2r1代之為ikr1r2*r3ijr1r3kr2第84頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二12354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1第85頁(yè)，共111頁(yè)，2022年，5月20

43、日，20點(diǎn)32分，星期二最后，X到Y(jié)的弧上標(biāo)記的正規(guī)式即為所構(gòu)造的正規(guī)式r顯然L(r)=L(M)=L(M)第86頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二證明2: 對(duì)于上的正規(guī)式r，構(gòu)造一個(gè)NFA M，使L(M)=L(r)，并且M只有一個(gè)終態(tài)，而且沒(méi)有從該終態(tài)出發(fā)的箭弧。 下面使用關(guān)于r中運(yùn)算符數(shù)目的歸納法證明上述結(jié)論。(1) 若r具有零個(gè)運(yùn)算符，則r=或r=或r=a，其中a。此時(shí)下圖所示的三個(gè)有限自動(dòng)機(jī)顯然符合上述要求。q0q0qfaq0qf第87頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二(2) 假設(shè)結(jié)論對(duì)于少于k(k1)個(gè)運(yùn)算符的正規(guī)式成立。 當(dāng)r中含有

44、k個(gè)運(yùn)算符時(shí)，r有三種情形：情形1：r=r1|r2，r1,r2中運(yùn)算符個(gè)數(shù)少于k。從而，由歸納假設(shè)，對(duì)ri存在Mi=，使得L(Mi)=L(ri)，并且Mi沒(méi)有從終態(tài)出發(fā)的箭弧（i=1,2）。不妨設(shè)S1S2=，在S1 S2中加入兩個(gè)新?tīng)顟B(tài)q0，f0。第88頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二 令M=，其中定義如下：(a) (q0, )=q1,q2(b) (q,a)= 1(q,a), 當(dāng)qS1-f1, a1(c) (q,a)= 2(q,a), 當(dāng)qS2-f2, a2(d) (f1,)=(f2,)=f0。 M的狀態(tài)轉(zhuǎn)換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)

45、L(r2)=L(r)q0f0M1q1f1M2q2f2第89頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二情形2：r=r1r2, 設(shè)Mi同情形1(i=1,2)。 令M=，其中定義如下：(a) (q,a)= 1(q,a), 當(dāng)qS1-f1, a1(b) (q,a)= 2(q,a), 當(dāng)qS2, a2(c) (f1,)=q2 M的狀態(tài)轉(zhuǎn)換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。M1q1f1M2q2f2第90頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二情形3：r=r1*。設(shè)M1同情形1。令M=，其中q0, f0S1，定義如下：(a)

46、 (q0,)=(f1,)=q1, f0(b) (q,a)= 1(q, a), 當(dāng)qS1-f1, a1。M的狀態(tài)轉(zhuǎn)換如右圖所示。L(M) = L(M1)* = L(r1)* = L(r)至此，結(jié)論2獲證。M1q1f1q0f0第91頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二1) 構(gòu)造上的NFA M 使得 L(V)=L(M)首先，把V表示成XYV上述證明過(guò)程實(shí)質(zhì)上是一個(gè)將正規(guī)表達(dá)式轉(zhuǎn)換為有限自動(dòng)機(jī)的算法。第92頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二代之為ijV1V2kikV1V2代之為ijV1|V2ijV2V1代之為ikV1*ijkV1然后，按下面的三條規(guī)則對(duì)

47、V進(jìn)行分裂第93頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為上的一個(gè)字符或，最后得到一個(gè)NFA M，顯然L(M)=L(V)第94頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二(a|b)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY514236abababab第95頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y

48、5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY514236abababab第96頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二Iab0121322153344655656340123546aabbbabaababab第97頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二FA正規(guī)集正規(guī)式DFANFA正規(guī)文法DFA第98頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二3.3.6 確定有限自動(dòng)機(jī)的化簡(jiǎn)對(duì)DFA M的化簡(jiǎn):尋找一個(gè)

49、狀態(tài)數(shù)比M少的DFA M，使得L(M)=L(M)兩個(gè)狀態(tài)s和t等價(jià)的條件為：一致性條件狀態(tài)s和t必須同時(shí)為終態(tài)或非終態(tài)；蔓延性條件對(duì)于所有輸入符號(hào)，狀態(tài)s和t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。兩個(gè)狀態(tài)不等價(jià)，則稱它們是可區(qū)別的。第99頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二對(duì)一個(gè)DFA M最少化的基本思想（劃分法）:把M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個(gè)狀態(tài)是等價(jià)的。讓每個(gè)子集選出一個(gè)代表，同時(shí)消去其他狀態(tài)。把那些原來(lái)射入其他等價(jià)狀態(tài)的弧改為射入相應(yīng)的代表狀態(tài)。第100頁(yè)，共111頁(yè)，2022年，5月20日，20點(diǎn)32分，星期二具體做法: 對(duì)M的狀態(tài)集進(jìn)行劃分首先，把S劃分為終態(tài)和非終態(tài)兩個(gè)子集，形成基本劃分。 假定到某個(gè)時(shí)候，