編譯原理第3章

1、第章詞法分析第章詞法分析 任務：從左至右逐個字符地對源程序進行掃任務：從左至右逐個字符地對源程序進行掃描，產(chǎn)生一個個的單詞符號，把作為描，產(chǎn)生一個個的單詞符號，把作為字符串的源程序改造成為單詞符號串字符串的源程序改造成為單詞符號串。內(nèi)容簡介：內(nèi)容簡介：3.1 對于詞法分析器的要求對于詞法分析器的要求 一功能和輸出形式一功能和輸出形式 二接口設計二接口設計3.2 詞法分析器的設計詞法分析器的設計 一輸入和預處理一輸入和預處理 二單詞符號的識別二單詞符號的識別 三狀態(tài)轉(zhuǎn)換圖及其實現(xiàn)三狀態(tài)轉(zhuǎn)換圖及其實現(xiàn)3.3 正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機 一單詞符號的描述一單詞符號的描述 1. 正規(guī)

2、式與正規(guī)集正規(guī)式與正規(guī)集 2. 正規(guī)文法正規(guī)文法 二有限自動機二有限自動機 1. . 3. NFA與與DFA的等價的等價 4. DFA的化簡的化簡 三正規(guī)式與有限自動機的等價性三正規(guī)式與有限自動機的等價性 四正規(guī)文法與有限自動機的等價性四正規(guī)文法與有限自動機的等價性3.4 詞法分析器的自動產(chǎn)生（）詞法分析器的自動產(chǎn)生（） 略略. .對于詞法分析器的要求對于詞法分析器的要求一、功能和輸出形式、功能：輸入源程序，輸出單詞符號、單詞符號的分類（）（）關(guān)鍵字:由程序語言定義的具有固定意義的標識符，也 稱為保留字或基本字。 例如：Pascal 語言中 begin end if while 等。（）（）標

3、識符：用來表示各種名字。如變量名、數(shù)組名、過程名等。（）（）常數(shù)：整型、實型、布爾型、文字型等例：100 3.14159 true sample（）（）運算符：+、-、*、/（）（）界符：，；（）等、輸出的單詞符號形式二元式：（單詞種別，單詞符號的屬性值）. .對于詞法分析器的要求對于詞法分析器的要求單詞符號的編碼：單詞符號的編碼：標識符：一般統(tǒng)歸為一種標識符：一般統(tǒng)歸為一種常數(shù)：常按整型、實型、布爾型等分類常數(shù)：常按整型、實型、布爾型等分類關(guān)鍵字：全體視為一種一字一種關(guān)鍵字：全體視為一種一字一種運算符：一符一種運算符：一符一種界符：一符一種界符：一符一種通常用通常用“整數(shù)編碼整數(shù)編碼”“單詞

4、符號的特征或特性單詞符號的特征或特性”例：例：考慮下述+代碼段：while ( i = j ) i - -;. .對于詞法分析器的要求對于詞法分析器的要求經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：符號序列： = , - . .對于詞法分析器的要求對于詞法分析器的要求二、接口設計、詞法分析器作為獨立的一遍、詞法分析器作為獨立的一遍、詞法分析器作為一個獨立的子程序，但并不、詞法分析器作為一個獨立的子程序，但并不一定作為獨立的一遍一定作為獨立的一遍語法分析器詞法分析器調(diào)用（取下一個單詞）調(diào)用（取下一個單詞）單詞單詞優(yōu)點：優(yōu)點：使整個編譯程序的結(jié)構(gòu)更

5、簡潔、清晰和條理化.詞法分析字符流單詞序列（源程序）（輸出在一個中間文件上）、預處理：剔掉空白符、跳格符、回車符、換、預處理：剔掉空白符、跳格符、回車符、換行符、注解部分等行符、注解部分等.一、輸入、預處理. .詞法分析器的設計詞法分析器的設計 編輯性字符除了出現(xiàn)在文字常數(shù)中之外，在別編輯性字符除了出現(xiàn)在文字常數(shù)中之外，在別處的任何出現(xiàn)都無意義處的任何出現(xiàn)都無意義. 注解部分不是程序的必要組成部分，它的作用注解部分不是程序的必要組成部分，它的作用僅在于改善程序的易讀性和易理解性僅在于改善程序的易讀性和易理解性. 每當詞法分析器調(diào)用時，就處理出一串確定長每當詞法分析器調(diào)用時，就處理出一串確定長度

6、（如度（如120個字符）的輸入字符，并將其裝進詞法個字符）的輸入字符，并將其裝進詞法分析器所確定的分析器所確定的掃描緩沖區(qū)掃描緩沖區(qū)中。中。、預處理子程序：、預處理子程序：. .詞法分析器的設計詞法分析器的設計 起點指示器起點指示器搜索搜索指示器指示器 一個指向當前正在識別的單詞的一個指向當前正在識別的單詞的開始位置開始位置（即新（即新單詞的首字符）單詞的首字符）起點指示器起點指示器一個用于向當前搜索以尋找單詞的一個用于向當前搜索以尋找單詞的終點終點搜索指示器搜索指示器圖 _ 源程序輸入緩沖區(qū)的對半互補結(jié)構(gòu). .詞法分析器的設計詞法分析器的設計二. 單詞符號的識別超前搜索 1關(guān)鍵字的識別 2標

7、識符的識別 3常數(shù)的識別 4算符和界符的識別. .詞法分析器的設計詞法分析器的設計三、狀態(tài)轉(zhuǎn)換圖及其實現(xiàn)1 1、狀態(tài)轉(zhuǎn)換圖及其示例、狀態(tài)轉(zhuǎn)換圖及其示例 . .詞法分析器的設計詞法分析器的設計例例: : 數(shù)字數(shù)字數(shù)字數(shù)字 其它其它 * 字母或數(shù)字字母或數(shù)字字母字母 其它其它 *例例: : ( (課本課本4242頁表頁表3.1; 433.1; 43頁圖頁圖3.3)3.3). .詞法分析器的設計詞法分析器的設計2 2、狀態(tài)轉(zhuǎn)換圖的實現(xiàn)、狀態(tài)轉(zhuǎn)換圖的實現(xiàn) 實現(xiàn)方法實現(xiàn)方法: :用程序?qū)崿F(xiàn)用程序?qū)崿F(xiàn), ,讓每個狀態(tài)結(jié)點對應一小段程序。讓每個狀態(tài)結(jié)點對應一小段程序。A、變量和過程說明、變量和過程說明ch字

8、符變量，存放最新讀進的源程序字符。字符變量，存放最新讀進的源程序字符。strToken 字符數(shù)組，存放構(gòu)成單詞符號的字符串。字符數(shù)組，存放構(gòu)成單詞符號的字符串。GetChar 子程序過程，將下一輸入字符讀到子程序過程，將下一輸入字符讀到ch中，搜索指中，搜索指 示器前移一字符位置。示器前移一字符位置。 GetBC子程序過程，檢查子程序過程，檢查ch中的字符是否為空白。若是，中的字符是否為空白。若是， 則調(diào)用則調(diào)用GetChar直至直至ch中進入一個非空白字符。中進入一個非空白字符。 Concat子程序過程，將子程序過程，將ch中的字符連接到中的字符連接到strToken之后之后. .詞法分析器

9、的設計詞法分析器的設計IsLetter和和IsDigit 布爾函數(shù)過程，它們分別判斷布爾函數(shù)過程，它們分別判斷ch中的中的字符是否為字母和數(shù)字。字符是否為字母和數(shù)字。Reserve整型函數(shù)過程，對整型函數(shù)過程，對strToken中的字符串查找中的字符串查找保留字表，若它是一個保留字則返回它的編碼，否則返保留字表，若它是一個保留字則返回它的編碼，否則返回回0值（假定值（假定0不是保留字的編碼）。不是保留字的編碼）。Retract 子程序過程，將搜索指示器回調(diào)一個字符位置，子程序過程，將搜索指示器回調(diào)一個字符位置，將將ch置為空白字符。置為空白字符。InsertId整型函數(shù)過程，將整型函數(shù)過程，將

10、strToken中的標識符插入中的標識符插入符號表，返回符號表指針。符號表，返回符號表指針。InsertConst 整型函數(shù)過程，將整型函數(shù)過程，將strToken中的常數(shù)插入中的常數(shù)插入常數(shù)表，返回常數(shù)表指針。常數(shù)表，返回常數(shù)表指針。. .詞法分析器的設計詞法分析器的設計B、示例、示例圖中結(jié)點圖中結(jié)點i所對應的程序段可表示為：所對應的程序段可表示為：GetChar （）（）; if ( IsLetter( ) ) 狀態(tài)狀態(tài)j的對應程序段的對應程序段； else if ( IsDigit( ) ) 狀態(tài)狀態(tài)k的對應程序段的對應程序段； else if ( ch=/ ) 狀態(tài)狀態(tài)l的對應程序段的

11、對應程序段； else 錯誤處理錯誤處理;圖中結(jié)點圖中結(jié)點i所對應的程序段可表示為：所對應的程序段可表示為： GetChar （）（）; while (IsLetter ( ) or IsDigit ( ) ) GetChar ( );狀態(tài)狀態(tài)j的對應程序段的對應程序段字母字母數(shù)字數(shù)字/字母或數(shù)字字母或數(shù)字 其它其它. .詞法分析器的設計詞法分析器的設計C、例、例課本課本43頁圖頁圖3.3；45-46頁頁. .詞法分析器的設計詞法分析器的設計. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機一、正規(guī)式，正規(guī)集，正規(guī)文法二、確定有限自動機（DFA)三、非確定有限自動機(NFA)四、NFA=DFA

12、=化簡五、正規(guī)式有限自動機六、左線性正規(guī)文法有限自動機 左線性正規(guī)文法有限自動機. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機一、正規(guī)式與正規(guī)集、遞歸定義、遞歸定義正規(guī)式正規(guī)式，a (a）若若U U，V V是正規(guī)式是正規(guī)式 U U. .V ,U|V, UV ,U|V, U* * 正規(guī)集正規(guī)集，a L(U)L(U)，L(V)L(V) L(U)L(V) ,L(U)L(V), (L(U)L(U)L(V) ,L(U)L(V), (L(U)* * . .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機例題：例題：、令，下面是，下面是上的正規(guī)式和相應的正規(guī)集上的正規(guī)式和相應的正規(guī)集ba*a(a|b)* (

13、a|b)*(aa|bb)(a|b)*上所有以上所有以b為首后跟任為首后跟任意多個意多個a的字的字上所有以上所有以a為首的字為首的字上所有含有兩個相繼的上所有含有兩個相繼的a或兩個相繼的或兩個相繼的b的字的字. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機 (A|B)(A|B|0|1)* (0|1)(0|1)*、令，則：，則：一個正規(guī)式的正規(guī)集與之完全等價，只是表達形式不同一個正規(guī)式的正規(guī)集與之完全等價，只是表達形式不同上的“標識符”的全體上的“數(shù)”的全體. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機、運算、運算“”（或）：表示從各選擇對象中選擇（或）：表示從各選擇對象中選擇“”（連接積）

14、：表示（連接積）：表示“連接連接”起來起來（）（閉包）：任意有限次的自重復連接（）（閉包）：任意有限次的自重復連接注：注：S*= Sn= SSSL(r*)=L(r)*優(yōu)先級：優(yōu)先級：*”|”n=0. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機例題：例題：、L(r|s) L(rs) L(a|b)c)B、L(a|b)*)=,a,b,aa,ab,ba,bb, L(a|(b*)=,a,b,bb,bbb,C、a|bc* a|(b(c*) ab|c*d (ab)|(c*)d)=L(r) L(s)=r s=r,s=L(r) L(s)=r s=rs=L(a|b) L(c)=a,bc=ac,bc3、等價：、

15、等價：若兩個正規(guī)式所表示的正規(guī)集相同，則認若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價為二者等價兩個等價的正規(guī)式和，記為兩個等價的正規(guī)式和，記為. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機例：例：b(ab)*=(ba)*b(a|b)*=(a*b*)*(a*b*)*=(a|b)* L(a*b*)*=(L(a)*(L(b)*=,a,b,aa,bb,.*=,a,b,ab,. L(a|b)* =a,b*=,a,b,ab, 、令、均為正規(guī)式，則：、令、均為正規(guī)式，則： （交換律）（交換律） （）（）（）（）（結(jié)合律）（結(jié)合律） （）（）（）（）（結(jié)合律）（結(jié)合律） U（V|W）=UV|UW（分配

16、律）（分配律） （V|W）U=VU|WU U=U =U U*=（U| ）*(U*)*=U*. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機例題：例題：、已知字母表=a，b，c，試求在該字母表上的僅包括一個b的所有串的集合相對應的正規(guī)式. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機B、已知字母表=a，b，c，若集合是包括了最多一個b的所有串，求其相應的正規(guī)式(a|c)*b(a|c)*(a|c)*(b|)(a|c)*. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機補充：正規(guī)文法補充：正規(guī)文法單詞符號單詞符號1、正規(guī)文法的形式、正規(guī)文法的形式左線性文法左線性文法:任何產(chǎn)生式為任何產(chǎn)生式為AB

17、或或A,其中其中VT*,A、B VN右線性文法右線性文法:任何產(chǎn)生式為任何產(chǎn)生式為AB或或A,其中其中VT*,A、BVN2、描述能力、描述能力（1）正規(guī)文法所描述的是）正規(guī)文法所描述的是(VNVT)上的正規(guī)集。上的正規(guī)集。（2）多數(shù)程序設計語言的單詞的詞法都能用正規(guī)文法來描述。）多數(shù)程序設計語言的單詞的詞法都能用正規(guī)文法來描述。. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機3、例題、例題例例.程序設計語言中的幾類單詞可用下述規(guī)則描述程序設計語言中的幾類單詞可用下述規(guī)則描述:標識符標識符 字母數(shù)字字母數(shù)字字母數(shù)字字母數(shù)字字母數(shù)字字母數(shù)字字母數(shù)字字母數(shù)字無符號整數(shù)無符號整數(shù)無符號整數(shù)無符號整數(shù)

18、運算符運算符= = | = | = | = | 界符界符，；（），；（）中的任一英文字母；中的任一英文字母；中的任一數(shù)字中的任一數(shù)字. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機二、確定有限自動機DFA（Deterministic Finite Aufomofa）1、DFA M是一個五元式是一個五元式M=（S， ，S0，F(xiàn)）其中：其中：SS有限集，其中的每個元素稱為一個狀態(tài)有限集，其中的每個元素稱為一個狀態(tài)有窮字母表，其中的每個元素稱為一個輸入字符有窮字母表，其中的每個元素稱為一個輸入字符：S SS S（即（即狀態(tài)狀態(tài)SSSS，aa，（S S，a a）唯一的確定下一狀態(tài)）唯一的確定下一狀態(tài)

19、）（s s，a a）=s:=s:當現(xiàn)行狀態(tài)為當現(xiàn)行狀態(tài)為s s，輸入字符為，輸入字符為a a時，將轉(zhuǎn)換到下一狀時，將轉(zhuǎn)換到下一狀態(tài)態(tài)sss s0 0SS，唯一的初態(tài)，唯一的初態(tài) F FS S，是一個終態(tài)集（可空），是一個終態(tài)集（可空）. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機2、DFA的兩種表達方式的兩種表達方式（1）狀態(tài)轉(zhuǎn)換矩陣）狀態(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)換矩陣為：則其狀態(tài)轉(zhuǎn)換矩陣為：狀態(tài)狀態(tài)ab01

20、2132213333. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機（0，a）=1 （0，b）=2（1，a）=3 （1，b）=2（2，a）=1 （2，b）=3（3，a）=3 （3，b）=3（2）狀態(tài)轉(zhuǎn)換圖）狀態(tài)轉(zhuǎn)換圖. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機DFA M:m個狀態(tài)：圖中有個狀態(tài)：圖中有 個狀態(tài)結(jié)點個狀態(tài)結(jié)點;n個輸入符號：個輸入符號： 每個結(jié)點頂多有每個結(jié)點頂多有 條箭弧射出條箭弧射出; 每條箭弧用每條箭弧用中的一個中的一個 （相同（相同/不同不同) 輸入字符輸入字符作標記作標記; 整張圖含有整張圖含有 個初態(tài)結(jié)點和若干個個初態(tài)結(jié)點和若干個 （可為（可為0）終態(tài)結(jié)點）終

21、態(tài)結(jié)點. a a a a b a a b a a， b b b b. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機3、識別（讀出、識別（讀出/接受）接受）對于任何對于任何*中的任何字中的任何字，若存在一條從初態(tài)，若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標記符連接成的字等于的標記符連接成的字等于。則成。則成可為可為DFA M所識所識別（接受別（接受/讀出）。讀出）。若若MM的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字 可為可為MM所識別所識別/ /接接受。受。DFA MDFA M所能識別的字的全體記為所能

22、識別的字的全體記為L L（MM）。）。若一個若一個DFA MDFA M的輸入字母表為的輸入字母表為，則稱，則稱MM是是上的一個上的一個DFADFA。 a a a a b a a b a a， b b b b. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機4、定理、定理上的一個字集上的一個字集V*是正規(guī)的，當且僅是正規(guī)的，當且僅當存在當存在上的上的DFA M，使得，使得V=L（M）. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機三、非確定有限自動機（NFA）1、一個、一個NFA是一個五元式是一個五元式M=（S， ，S0，F(xiàn)）其中：其中：SS有限集，其中每個元素稱為一個狀態(tài)有限集，其中每個元素

23、稱為一個狀態(tài)有窮字母表，其中的每個元素稱為一個輸入字符有窮字母表，其中的每個元素稱為一個輸入字符：S S* *2 2S S S S0 0S S，是一個非空初態(tài)集，是一個非空初態(tài)集 F FS S，是一個終態(tài)集（可空），是一個終態(tài)集（可空）. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機三、非確定有限自動機（NFA）DFANFAS初態(tài)終態(tài)F有限狀態(tài)集字母表SS初態(tài)唯一初態(tài)唯一可為空可為空 同左同左S*2S初態(tài)不一定唯一初態(tài)不一定唯一同左同左. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機2、狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換圖注：注：（1）每條弧用）每條弧用 的作為輸入字的作為輸入字,箭箭弧上的標記弧上的標

24、記 （ 允許允許/不允許）相同。不允許）相同。（2）整張圖）整張圖至少至少含有一個初態(tài)結(jié)點以及含有一個初態(tài)結(jié)點以及若干個若干個（可為（可為0個）個） 終態(tài)結(jié)點終態(tài)結(jié)點（3）某些結(jié)點既可為初態(tài)結(jié)點也可為終態(tài)結(jié)點）某些結(jié)點既可為初態(tài)結(jié)點也可為終態(tài)結(jié)點*中一個字（可以是空字中一個字（可以是空字）允許允許例：q0q111000DFA? NFA?. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機3、識別（讀出、識別（讀出/接受）接受）對于對于*中的任何一個中的任何一個，若存在一條從某，若存在一條從某一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標記字依序連

25、接成的字（忽略那些標上所有弧的標記字依序連接成的字（忽略那些標記為記為的?。┑扔诘幕。┑扔冢瑒t稱，則稱可為可為NFA M所識別所識別（讀出（讀出/接受）。接受）。若若MM的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或者存在的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或者存在 一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的通路，則空字通路，則空字 可為可為MM所接受。所接受。. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機四、NFA=DFA(確定化）=化簡（最少化）1、_CLOSURE（I）：I中的每個狀態(tài)；若s _CLOSURE（I），則狀態(tài)s經(jīng)過任意條標記為的弧到達的狀態(tài)s _CLO

26、SURE（I）。_CLOSURE（x）=x,5,12、Ia=_CLOSURE（J）若sIs經(jīng)過1條標記為a的弧到達的狀態(tài)s JI=x,5,1Ia=x,5,1a= _CLOSURE（5,3)=5,3,1Ib=x,5,1b= _CLOSURE（5,4)=5,4,1IIaIbX,5,1_CLOSURE(初態(tài)）（一）NFA=DFA5,3,15,4,15,3,15,4,15,2,3,1,6,Y5,4,15,2,3,1,6,Y5, 3,15,2,4,1,6,Y5,2,4,1,6,Y5,2,3,6,1,Y5, 4,6,1,Y5, 4,6,1,Y5, 3,6,1,Y5,2,4,6,1,Y5, 3,6,1,Y5

27、,6,3,1,Y5, 2,6,4,1,Y5,2,6,3,1,Y5,6,4,1,Y. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機解解：（：（1）構(gòu)造構(gòu)造DFA的狀態(tài)轉(zhuǎn)換矩陣的狀態(tài)轉(zhuǎn)換矩陣(2)構(gòu)造重新命名后的狀態(tài)轉(zhuǎn)換矩陣構(gòu)造重新命名后的狀態(tài)轉(zhuǎn)換矩陣DFA M L(M)=L(M)=L(M)Sab012132214335464564635（二）DFA的化簡狀態(tài)s和t等價： s和t到達終態(tài)能夠識別相同的字。1、首先分為非終態(tài)集和終態(tài)集0，1，2和3，4，5，62、分別對每個集合進行試探：（1）0，1，2a=1,3,1 把集合分為0，2和1 0，2b=2,5 把集合劃分為0和2 把集合0，1，2劃分

28、為0、1和22、（1）0、1、2、3，4，5，6 （2）3，4，5，6a=3，6，6，3 3，4，5，6b=4，5，5，4 集合3，4，5，6不可再劃分。3、最終形成的劃分0123，4，5，60123，4，5，6用一個狀態(tài)代表一個狀態(tài)子集。abababa,b. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機五、正規(guī)式有限自動機關(guān)系定理定理： 上的NFA M所能識別的語言L(M)可以用上的正規(guī)式來表示。即：對上的NFA M ，可構(gòu)造一個正規(guī)式，使得L()=L(M)定理： 上任何正規(guī)式 ，存在DFA M使得L(M)=L()。即：由 正規(guī)式可以構(gòu)造一個DFA M，使得L(M)L(). .正規(guī)表達式與

29、有限自動機正規(guī)表達式與有限自動機五、正規(guī)式有限自動機1 1、 有限自動機有限自動機=正規(guī)式正規(guī)式1) 1)把狀態(tài)轉(zhuǎn)換圖的概念拓廣把狀態(tài)轉(zhuǎn)換圖的概念拓廣，令每條弧上都可以用一個，令每條弧上都可以用一個正規(guī)式作標記。正規(guī)式作標記。2) 2)在在MM的轉(zhuǎn)換圖上加兩個結(jié)點：的轉(zhuǎn)換圖上加兩個結(jié)點：x,yx,y。從從 x x用用 弧連接到弧連接到MM的所有初態(tài)結(jié)點；從的所有初態(tài)結(jié)點；從MM的終態(tài)結(jié)點用的終態(tài)結(jié)點用 弧連接到弧連接到y(tǒng) y。這。這個新的個新的NFANFA為為MM，且，且L(M)=L(M)L(M)=L(M)3) 3)通過引入的通過引入的3 3條有限自動機替換規(guī)則條有限自動機替換規(guī)則逐步消去逐步

30、消去MM中的中的所有結(jié)點，直到只剩下所有結(jié)點，直到只剩下x x和和y y為止。為止。這樣，在這樣，在x x至至y y的弧的弧線上的標記就是線上的標記就是 上的正規(guī)式，也就是上的正規(guī)式，也就是MM接受的正規(guī)式。接受的正規(guī)式。. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機五、正規(guī)式有限自動機1 1、 有限自動機有限自動機=正規(guī)式正規(guī)式替換規(guī)則替換規(guī)則: :ABAB A|BA|B A A* *A A B B A A代之以代之以代之以代之以代之以代之以A AB B 例：將下面的DFA M所接受的語言表示為正規(guī)式xy111113200 00 0 x0 310|0101|1000|1100|11yx0

31、 310|0101|1000|1100|11y x 0 y00|11(10|01)(00|11)*(01|10) x y (10|01)(00|11)*(01|10)|(00|11)*練習1：練習1：練習2：練習2：. .正規(guī)表達式與有限自動機正規(guī)表達式與有限自動機五、正規(guī)式有限自動機2 2、正規(guī)式、正規(guī)式=有限自動機有限自動機證明過程證明過程如下：（1）若正規(guī)式有零個運算符時： 正規(guī)式，構(gòu)造NFA為： 對應正規(guī)式，構(gòu)造NFA為： 對應正規(guī)式a，構(gòu)造NFA為： （2）假設正規(guī)式有k(k=1)個運算符時結(jié)論成立。（3）則正規(guī)式有k+1(k=1)個運算符時：xyxyxya R=stR=s*xyN(

32、s)N(s)N(t)xyN(s)N(t)R=s|t 書上例子P56轉(zhuǎn)換規(guī)則： 1)由正規(guī)式 構(gòu)造一個如下僅有兩個結(jié)點x,y的狀態(tài)圖。2)按所引入的3條正規(guī)式分裂規(guī)則分裂 。3)重復步驟2直到每個弧上的標記是上的一個字符或為止。4)將所得的NFA M(因為包含弧)進行確定化就得到DFA。 x y 正規(guī)式分裂規(guī)則 12| 1 22 1 123 1 12 * 23例：根據(jù)正規(guī)式(a|b)*(aa|bb)(a|b)*, 構(gòu)造DFA M，使之等價. x y (a|b)*(aa|bb)(a|b)* 1y(a|b)*(a|b)* 2 x(aa|bb) 1y 2 xaa 5 bba|b 6 a|b 1y 2

33、xa 5 ba 6 abb34ab練習練習1：L(R) =(a|b)*abb，構(gòu)造，構(gòu)造NFA使使L(N)=L(R)練習練習2：L(R) =a*b*abb，構(gòu)造，構(gòu)造NFA使使L(N)=L(R)練習練習1：L(R) =(a|b)*abb，構(gòu)造，構(gòu)造NFA使使L(N)=L(R)解：解：xy(a|b)*abbxyabbabxyabba,bxyababbxy(a|b)*abb練習練習2：L(R) =a*b*abb，構(gòu)造，構(gòu)造NFA使使L(N)=L(R)解：解：xybab abxa*b*abby1、右線性正規(guī)文法GR-有限自動機2、左線性正規(guī)文法GL- 有限自動機3、有限自動機-右線性正規(guī)文法GR4、

34、有限自動機-左線性正規(guī)文法GL.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機1、右線性正規(guī)文法GR-有限自動機.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例：GR: S aA A bB B cSABfabc（S，a）=A（A，b）=B（B，c）=f1、右線性正規(guī)文法GR-有限自動機.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機GR(VT,VN,S,P)P:A aBBbFA(,S, ,S0,F)字母表:VT狀態(tài)集S: VN fS0：開始符號：開始符號S對應的狀態(tài)對應的狀態(tài)F：f:（A，a）=B（B，b）=f GR: A 0|0B|1D B 0D|1C C 0|0B|1D D0D|1D2、左線

35、性正規(guī)文法GL-有限自動機.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例：GL: S Ac A Bb B aSABfcba（A，c）=S（B，b）=A（q0，a）=Bq0S2、左線性正規(guī)文法GL-有限自動機.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機GL(VT,VN,S,P)P:A BaBbFA(,S, ,S0,F)字母表:VT狀態(tài)集S: VN q0S0： q0F：開始符號：開始符號S對應的狀態(tài)對應的狀態(tài):（B，a）=A（ q0 ，b)=B GL: A 0|C0 B 0|C0 C B1 D1|C1|D0|D1|B03、有限自動機-右線性正規(guī)文法GR.正規(guī)表達式與有限自動機六、正規(guī)文法有限

36、自動機引例1：SABCabc引例2：SABCabcd3、有限自動機-右線性正規(guī)文法GR.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例1：SABCabc GR: S aA A bB B cC C 3、有限自動機-右線性正規(guī)文法GR.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機 GR: S aA A bB B cC C dB|引例2：SABCabcd規(guī)則：3、有限自動機-右線性正規(guī)文法GRFA(,S, ,s0,F)（A，a）=BGR(VT,VN,S,P)VT: VN:狀態(tài)集S對應的符號集S：初態(tài)s0對應的符號P： A aB當C是終態(tài)時，增加： C ABDabaabbbC GR: AaB|bD B bC C aA|bD D aB|bD|4、有限自動機-左線性正規(guī)文法GL.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例1：SABCabc引例2：SABCabcd4、有限自動機-左線性正規(guī)文法GL.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機引例1：SABCabc GL: CBc B Ab A Sa S 4、有限自動機-左線性正規(guī)文法GL.正規(guī)表達式與有限自動機六、正規(guī)文法有限自動機 GL: CBc B Ab A Sa S Ad|引例2：SABCabc