1、第三章第三章 詞法分析詞法分析n對于詞法分析器的要求對于詞法分析器的要求n詞法分析器的設計詞法分析器的設計n正規表達式與有窮自動機正規表達式與有窮自動機n詞法分析器的自動產生詞法分析器的自動產生-LEX-LEX詞法分析詞法分析n詞法分析的任務：從左至右逐個字符地詞法分析的任務：從左至右逐個字符地對源程序進行掃描，產生一個個單詞符對源程序進行掃描，產生一個個單詞符號。號。n詞法分析器詞法分析器(Lexical Analyzer) (Lexical Analyzer) 又稱掃又稱掃描器描器(Scanner)(Scanner)：執行詞法分析的程序：執行詞法分析的程序3.13.1 對于詞法分析器的要求

2、對于詞法分析器的要求一、詞法分析器的功能和輸出形式一、詞法分析器的功能和輸出形式功能功能: :輸入源程序、輸出單詞符號輸入源程序、輸出單詞符號單詞符號的種類：單詞符號的種類：基本字：如基本字：如 begin begin，repeatrepeat，標識符標識符表示各種名字：如變量名、數表示各種名字：如變量名、數組名和過程名組名和過程名常數：各種類型的常數常數：各種類型的常數運算符：運算符：+ +，- -，* *，/ /，界符：逗號、分號、括號和空白界符：逗號、分號、括號和空白n輸出的單詞符號的表示形式輸出的單詞符號的表示形式: :n( (單詞種別，單詞自身的值單詞種別，單詞自身的值) )n單詞種

3、別通常用整數編碼表示。單詞種別通常用整數編碼表示。n若一個種別只有一個單詞符號，則種別編若一個種別只有一個單詞符號，則種別編碼就代表該單詞符號。假定基本字、運算碼就代表該單詞符號。假定基本字、運算符和界符都是一符一種。符和界符都是一符一種。n若一個種別有多個單詞符號，則對于每個若一個種別有多個單詞符號，則對于每個單詞符號，給出種別編碼和自身的值。單詞符號，給出種別編碼和自身的值。n標識符單列一種；標識符自身的值表示成標識符單列一種；標識符自身的值表示成按機器字節劃分的內部碼。按機器字節劃分的內部碼。n常數按類型分種；常數的值則表示成標準常數按類型分種；常數的值則表示成標準的二進制形式。的二進制

4、形式。例例 FORTRAN FORTRAN程序程序nIF (5.EQ.M) GOTO 100IF (5.EQ.M) GOTO 100n輸出單詞符號：輸出單詞符號：n邏輯邏輯IFIF(34(34，-)-)n左括號左括號(2(2，-)-)n整常數整常數(20(20， 5 5的二進制的二進制) )n等號等號(6(6，-)-)n標識符標識符(26(26， M) M)n右括號右括號(16(16，-)-)nGOTOGOTO(30(30，-)-)n標號標號(19(19， 100 100的二進制的二進制) )n助憶符：直接用編碼表示不便于記憶，因此用助憶助憶符：直接用編碼表示不便于記憶，因此用助憶符來表示編碼

5、。符來表示編碼。例：例：IFIF(34(34，-) (IF-) (IF，-) -) 左括號左括號(2(2，-) (-) (，-) -) 等號等號(6(6，-) (=-) (=，-) -) 例例 C C程序程序n while (i=j) i-;n輸出單詞符號：輸出單詞符號：nnnn=, - nnnnn二、詞法分析器作為一個獨立子程序二、詞法分析器作為一個獨立子程序n詞法分析是作為一個獨立的階段，是否詞法分析是作為一個獨立的階段，是否應當將其處理為一遍呢？應當將其處理為一遍呢？n作為獨立階段的優點：結構簡潔、清晰作為獨立階段的優點：結構簡潔、清晰和條理化，有利于集中考慮詞法分析一和條理化，有利于集

6、中考慮詞法分析一些枝節問題。些枝節問題。n不作為一遍：將其處理為一個子程序。不作為一遍：將其處理為一個子程序。詞法分析器詞法分析器詞法分詞法分析器析器語法分語法分析器析器符號表符號表源程序源程序單詞符號單詞符號取下一單詞取下一單詞.詞法分析器的結構詞法分析器的結構預處理預處理子程序子程序掃描器掃描器輸入緩沖區輸入緩沖區掃描緩沖區掃描緩沖區單詞符號單詞符號輸入輸入3.2 詞法分析器的設計刪除無用的空白、跳格、回刪除無用的空白、跳格、回車和換行等編輯性字符車和換行等編輯性字符區分標號區、捻接續行和給區分標號區、捻接續行和給出句末符等出句末符等 WhatALongWord WhatALongWord

7、 WhatALongWord WhatALongWon掃描緩沖區掃描緩沖區 起點起點 搜索搜索指示器指示器 指示器指示器一、掃描緩沖區一、掃描緩沖區 二、單詞符號的識別二、單詞符號的識別: :超前搜索超前搜索以基本字的識別為例：以基本字的識別為例：例如例如:DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M) GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能確定哪些是基本字需要超前搜索才能確定哪些是基本字幾點限制幾點限制不必使用超前搜索不必使用超前搜索n所有基本字都是保留字；用戶不能用它們作自己所有基本字都是保留字；用戶

8、不能用它們作自己的標識符；的標識符；n 基本字作為特殊的標識符來處理基本字作為特殊的標識符來處理;不用特殊的狀不用特殊的狀態圖來識別，只要查保留字表。態圖來識別，只要查保留字表。n如果基本字、標識符和常數或標號之間沒有如果基本字、標識符和常數或標號之間沒有確定的運算符或界符作間隔，則必須使用一個空確定的運算符或界符作間隔，則必須使用一個空白符作間隔白符作間隔三、狀態轉換圖三、狀態轉換圖1 1 概念概念狀態轉換圖是一張有限方向圖。狀態轉換圖是一張有限方向圖。213a數字數字結點代表狀態，用圓圈表示。結點代表狀態，用圓圈表示。狀態之間用箭弧連結，箭弧狀態之間用箭弧連結，箭弧上的標記上的標記( (字

9、符字符) )代表射出結代表射出結狀態下可能出現的輸入字符狀態下可能出現的輸入字符或字符類。或字符類。一張轉換圖只包含有限個狀態，其中一張轉換圖只包含有限個狀態，其中有一個為初態，至少要有一個終態。有一個為初態，至少要有一個終態。識別標識符的狀態轉換圖識別標識符的狀態轉換圖123字母字母其他其他字母或數字字母或數字*識別整常數的狀態轉換圖識別整常數的狀態轉換圖123數字數字其他其他數字數字*n一個狀態轉換圖可用于識別一個狀態轉換圖可用于識別( (或接受或接受) )一定一定的字符串。的字符串。詞法分析器設計流程詞法分析器設計流程 某程序設計語言的某程序設計語言的單詞符號串集單詞符號串集 分析詞法規

10、則分析詞法規則 畫出識別單詞的狀態圖畫出識別單詞的狀態圖 根據狀態圖寫詞法分析器程序根據狀態圖寫詞法分析器程序單單 詞詞 符符 號號 種種 別別 編編 碼碼 助助 憶憶 符符 內內 碼碼 值值 D DI IM M 1 1 $ $D DI IM M - - I IF F 2 2 $ $I IF F - - D DO O 3 3 $ $D DO O - - S ST TO OP P 4 4 $ $S ST TO OP P - - E EN ND D 5 5 $ $E EN ND D - - 標標 識識 符符 6 6 $ $I ID D 內內 部部 字字 符符 串串 常常 數數 ( (數數 ) )

11、7 7 $ $I IN NT T 標標 準準 二二 進進 制制 形形 式式 = = 8 8 $ $A AS SS SI IG GN N - - _ _ 9 9 $ $P PL LU US S - - * * 1 10 0 $ $S ST TA AR R - - * * * 1 11 1 $ $P PO OW WE ER R - - ， 1 12 2 $ $C CO OM MM MA A - - ( ( 1 13 3 $ $L LP PA AR R - - ) ) 1 14 4 $ $R RP PA AR R - - 1 12 23 34 45 56 67 78 89 9101011111212

12、13130 0空白空白字母字母字母或數字字母或數字非字母與數字非字母與數字數字數字非數字非數字數字數字= =+ +* *非非* *, ,( () )其它其它* * * * *3 狀態轉換圖的實現狀態轉換圖的實現思想：每個狀態結對應一小段程序。思想：每個狀態結對應一小段程序。做法做法:1)對不含回路的分叉結，可用一個對不含回路的分叉結，可用一個CASE語句語句或一組或一組IF-THEN-ELSE語句實現語句實現GetChar( );if (IsLetter( ) 狀態狀態j的對應程序段的對應程序段;else if (IsDigit( ) 狀態狀態k的對應程序段的對應程序段;else if (ch

13、=/) 狀態狀態l的對應程序段的對應程序段;else 錯誤處理錯誤處理;ijkl字母字母數字數字/3 狀態轉換圖的實現狀態轉換圖的實現2)對含回路的狀態結，可對應一段由對含回路的狀態結，可對應一段由WHILE語句構成的程序語句構成的程序.i字母或數字字母或數字其它其它jGetChar( );while (IsLetter( ) or IsDigit( )GetChar( );狀態狀態j的對應程序段的對應程序段3 狀態轉換圖的實現狀態轉換圖的實現3)終態結表示識別出某種單詞符號，因此，終態結表示識別出某種單詞符號，因此，對應語句為對應語句為 RETURN (C，VAL) 其中，其中，C為單詞種別

14、，為單詞種別，VAL為單詞自身值為單詞自身值.n全局變量與過程全局變量與過程n1)ch 字符變量、存放最新讀入的源程字符變量、存放最新讀入的源程序字符序字符n2)strToken 字符數組，存放構成單詞字符數組，存放構成單詞符號的字符串符號的字符串n3)GetChar 子程序過程，把下一個字子程序過程，把下一個字符讀入到符讀入到 ch 中中n4)GetBC 子程序過程，跳過空白符，直子程序過程，跳過空白符，直至至 ch 中讀入一非空白符中讀入一非空白符n5)Concat 子程序，把子程序，把ch中的字符連接中的字符連接到到 strToken 6)IsLetter和和 IsDisgital 布爾

15、函數，布爾函數，判斷判斷ch中字符是否為字母和數字中字符是否為字母和數字7) Reserve 整型函數，對于整型函數，對于 strToken 中的字符串查找保留字表，若它是保留字中的字符串查找保留字表，若它是保留字則給出它的編碼，否則回送則給出它的編碼，否則回送08) Retract 子程序，把搜索指針回調一子程序，把搜索指針回調一個字符位置個字符位置9)InsertId 整型函數，將整型函數，將strToken中中的標識符插入符號表，返回符號表指針的標識符插入符號表，返回符號表指針10)InsertConst 整型函數過程，將整型函數過程，將strToken中的常數插入常數表，返回常中的常數

16、插入常數表，返回常數表指針。數表指針。 int code, value;strToken := “ ”; /*置置strToken為空串為空串*/GetChar(); GetBC();if (IsLetter()beginwhile (IsLetter() or IsDigit()beginConcat(); GetChar(); endRetract();/搜索指針回調搜索指針回調code := Reserve(); /判斷是否為保留字判斷是否為保留字if (code = 0) /標識符標識符beginvalue := InsertId(strToken);return ($ID, valu

17、e);endelsereturn (code, -); /保留字保留字endelse if (IsDigit()begin while (IsDigit() begin Concat( ); GetChar( ); endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) return ($PLUS, -);5=*6*+else if (ch =*)beginGetChar();if (ch =*) return ($

18、POWER, -);Retract(); return ($STAR, -);endelse if (ch =;) return ($SEMICOLON, -);else if (ch =() return ($LPAR, -);else if (ch =) return ($RPAR, -);else ProcError( );/* 錯誤處理錯誤處理*/將狀態圖的代碼一般化將狀態圖的代碼一般化n變量變量curState用于保存現有的狀態用于保存現有的狀態n用二維數組表示狀態圖：用二維數組表示狀態圖：n stateTransstatecharcurState=初態初態GetChar();Whi

19、le(stateTranscurStatech有定義有定義)/存在后繼狀態，讀入，拼接存在后繼狀態，讀入，拼接Contact();/轉入下一狀態，讀入下一字符轉入下一狀態，讀入下一字符curState=stateTranscurStatech；If curState是終態是終態 then 返回返回strToken中的單詞中的單詞GetChar(); FA正規集正規集正規式正規式DFANFA正規文法正規文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.63.3 3.3 正規表達式與有限自動機正規表達式與有限自動機3.3 3.3 正規表達式與有限自動機正規表達式與有限自動機n幾個

20、概念幾個概念: :n考慮一個有窮考慮一個有窮 字母表字母表 字符集字符集n其中每一個元素稱為一個字符其中每一個元素稱為一個字符n上的字上的字( (也叫字符串也叫字符串) ) 是指由是指由中的字中的字符所構成的一個有窮序列符所構成的一個有窮序列n不包含任何字符的序列稱為空字，記為不包含任何字符的序列稱為空字，記為n用用* *表示表示上的所有字的全體上的所有字的全體, ,包含空字包含空字n例如例如: : 設設 =a =a， b b，那么，那么 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n*的子集的子集U和和V的連接積定義為的連接積定義為nUV

21、 | U & V nV自身的自身的 n次積記為次積記為nVn=VVVn規定規定V0=，令，令n V*=V0V1V2V3 n稱稱V*是是V的閉包的閉包;n記記 VVV* ，稱，稱V+是是V的正規閉包。的正規閉包。3.3.1 正規式和正規集正規式和正規集n正規集可以用正規表達式簡稱正規式正規集可以用正規表達式簡稱正規式表示。表示。n正規表達式是表示正規集一種方法。一正規表達式是表示正規集一種方法。一個字集合是正規集當且僅當它能用正規個字集合是正規集當且僅當它能用正規式表示。式表示。n正規式和正規集的遞歸定義：正規式和正規集的遞歸定義：n對給定的字母表對給定的字母表n1)1) 和和都是都是上

22、的正規式，它們所表上的正規式，它們所表示的正規集為示的正規集為 和和; ;n2) 2) 任何任何a a ，a a是是上的正規式，它上的正規式，它所表示的正規集為所表示的正規集為a ;a ;3) 假定假定e1和和e2都是都是 上的正規式，它們所表示上的正規式，它們所表示的正規集為的正規集為L(e1)和和L(e2)，那么，那么i) (e1|e2)為正規式，它所表示的正規集為為正規式，它所表示的正規集為L(e1)L(e2)，ii) (e1.e2)為正規式，它所表示的正規集為為正規式，它所表示的正規集為L(e1)L(e2)(連接積連接積)，iii) (e1)*為正規式，它所表示的正規集為為正規式，它所

23、表示的正規集為(L(e1)*（閉包，即任意有限次的自重復連（閉包，即任意有限次的自重復連接），接），僅由有限次使用上述三步驟而定義的表達式才僅由有限次使用上述三步驟而定義的表達式才是是 上的正規式，僅由這些正規式表示的字集上的正規式，僅由這些正規式表示的字集才是才是 上的正規集。上的正規集。n所有詞法結構一般都可以用正規式描述。所有詞法結構一般都可以用正規式描述。n若兩個正規式所表示的正規集相同，則稱若兩個正規式所表示的正規集相同，則稱這兩個正規式等價。如這兩個正規式等價。如nb(ab)b(ab)* *=(ba)=(ba)* *b b(a(a* *b b* *) )* *=(a|b)=(a|b

24、)* *n L( (ba)*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)*bn對正規式，下列等價成立：對正規式，下列等價成立：ne1|e2 =

25、 e2|e1 交換律交換律ne1 |(e2|e3) = (e1|e2)|e3 結合律結合律ne1(e2e3) = (e1e2)e3 結合律結合律ne1(e2|e3) = e1e2|e1e3 分配律分配律n(e2|e3)e1 = e2e1|e3 e1分配律分配律ne = e = e e1e2 e2 e1 L(e1|e2) = L(e1 ) L(e2)= L(e2 ) L(e1)= L(e2|e1)FA正規集正規集正規式正規式DFANFA3.3.13.3.23.3.33.3.2 確定有限自動機確定有限自動機(DFA)n對狀態圖進行形式化，則可以下定義：對狀態圖進行形式化，則可以下定義：n自動機自動

26、機M M是一個五元式是一個五元式M=(S, M=(S, , f, S0, F), f, S0, F),其中：其中：n1. S: 1. S: 有窮狀態集，有窮狀態集，n2. 2. ：輸入字母表：輸入字母表( (有窮有窮) )，n3. f: 3. f: 狀態轉換函數，為狀態轉換函數，為S SS S的單值部的單值部分映射，分映射，f(sf(s，a)=sa)=s表示：當現行狀態為表示：當現行狀態為s s，輸入字符為輸入字符為a a時，將狀態轉換到下一狀態時，將狀態轉換到下一狀態s s。我們把我們把s s稱為稱為s s的一個后繼狀態。的一個后繼狀態。n4. S04. S0S S是唯一的一個初態；是唯一的

27、一個初態； n5 F5 FS S ：終態集：終態集( (可空可空) )。n例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：其中：f定義如下：定義如下：nf(0，a)=1f(0，b)=2nf(1，a)=3 f(1，b)=2nf(2，a)=1f(2，b)=3nf(3，a)=3 f(3，b)=3ab012132213333狀態轉換矩陣狀態轉換矩陣0312aaaa狀態轉換圖狀態轉換圖bbbbn對于對于 * *中的任何字符串中的任何字符串，若存在一條從，若存在一條從初態到某一終態的道路，且這條路上所有初態到某一終態的道路，且這條路上所有弧上的標記符連接成的字符串等于弧上的標記符連

28、接成的字符串等于，則，則稱稱為為DFA MDFA M所識別所識別( (接納接納) )。nDFA MDFA M所識別的字符串的全體記為所識別的字符串的全體記為L(M)L(M)。142300011011練習練習下圖下圖DFADFA識別的識別的L(M)L(M)是什么？是什么？A.L(M)=A.L(M)=以以aaaa或或bbbb開頭的字符串開頭的字符串B.L(M)=B.L(M)=含含aaaa或或bbbb的字符串的字符串C.L(M)=C.L(M)=以以aaaa或或bbbb結尾的字符串結尾的字符串答案：答案：B B0312aaaaDFADFAbbbb3.3.3 3.3.3 非確定有限自動機非確定有限自動機

29、(NFA) (NFA) 1976年圖靈獎年圖靈獎 For their joint paper“Finite automata and their decision problemswhich introduced the idea of nondeterministic machines，which has proved to be an enormously valuable concept. Their classic paper has been a continuous source of inspiration for subsequent work in this field.3.

30、3.3 3.3.3 非確定有限自動機非確定有限自動機(NFA) (NFA) n定義：一個非確定有限自動機定義：一個非確定有限自動機(NFA) M(NFA) M是是一個五元式一個五元式M=(S, M=(S, , f, S0, F), f, S0, F)，其中：，其中：n1 S: 1 S: 有窮狀態集；有窮狀態集；n2 2 ：輸入字母表：輸入字母表( (有窮有窮) )；n3 f: 3 f: 狀態轉換函數，為狀態轉換函數，為S S* *2S2S的的部分映射部分映射( (非單值非單值) )；n4 S04 S0S S是非空的初態集；是非空的初態集；n5 F 5 F S S ：終態集：終態集( (可空可空

31、) )。n從狀態圖可看出從狀態圖可看出NFA 和和DFA的區別：的區別：n 1 可有多個初態可有多個初態n 2 弧上的標記可以是弧上的標記可以是 *中的一個字甚至可中的一個字甚至可以是一個正規式），而不一定是單個字符；以是一個正規式），而不一定是單個字符；n 3 同一個字可能出現在同狀態射出的多條弧同一個字可能出現在同狀態射出的多條弧上。上。nDFA是是NFA的特例。的特例。021 aaa|bb*cabNFADFAn對于對于 * *中的任何字中的任何字，若存在一條從初態，若存在一條從初態到某一終態的道路，且這條路上所有弧上到某一終態的道路，且這條路上所有弧上的標記符連接成的字等于的標記符連接成

32、的字等于（忽略那些標（忽略那些標記為記為的弧），則稱的弧），則稱為為NFA MNFA M所識別所識別( (接接納納) )nNFA MNFA M所識別的字符串的全體記為所識別的字符串的全體記為L(M)L(M)。021 a|baaa|bbba|b012abab識別所有含相繼兩個識別所有含相繼兩個a a或相繼兩個或相繼兩個b b的字的字ambn | m，n1NFA示例示例n定義：對于任何兩個有限自動機定義：對于任何兩個有限自動機M和和M，如果如果L(M)=L(M)，則稱，則稱M與與M等價。等價。n自動機理論中一個重要的結論：判定兩自動機理論中一個重要的結論：判定兩個自動機等價性的算法是存在的。個自動

33、機等價性的算法是存在的。n對于每個對于每個NFA M存在一個存在一個DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA與與NFA描述能力描述能力相同。相同。NFA與與DFA1. 假定假定NFA M=，我們對，我們對NFA M的狀態轉換圖進行以下改造：的狀態轉換圖進行以下改造： 1) 引進新的初態結點引進新的初態結點X和終態結點和終態結點Y，X,YS， 從從X到到S0中任意狀態結點連一條中任意狀態結點連一條箭弧，箭弧， 從從F中任意狀態結點連一條中任意狀態結點連一條箭弧到箭弧到Y。 2) 按以下按以下3條規則對條規則對NFA M的狀態轉換圖進一的狀態轉換圖進一步施行替換，直到把這個圖轉

34、變為每條弧只步施行替換，直到把這個圖轉變為每條弧只標記為標記為 上的一個字符或上的一個字符或；其中；其中k是新引入是新引入的狀態。的狀態。NFA轉換為等價的轉換為等價的DFA代之為代之為ikABjijAB代之為代之為ijA|BijBA代之為代之為ijA*ik jA按下面的按下面的3條規則對箭弧進行分裂條規則對箭弧進行分裂:n例：識別所有含相繼兩個例：識別所有含相繼兩個a或相繼兩個或相繼兩個b的字的字XY 514236ab ababab5126ab abaabb2. 把上述把上述NFA確定化確定化采用子集法采用子集法.設設I是是NFA的狀態集的一個子集，定義的狀態集的一個子集，定義I的的-閉包閉

35、包-closure(I)為為: i) 若若sI，則，則s-closure(I)； ii) 若若sI，則從，則從s出發經過任意條出發經過任意條弧弧而能到達的任何狀態而能到達的任何狀態s都屬于都屬于-closure(I) 即即 -closure(I)=Is|從某個從某個sI出發經過任出發經過任意條意條弧能到達弧能到達sn設設a是是中的一個字符，定義中的一個字符，定義nIa= -closure(J)n 其中，其中，J為為I中的某個狀態出發經過一條中的某個狀態出發經過一條a弧而到達的狀態集合。弧而到達的狀態集合。IIaaIJaK n -closure(1)=1，2=I n J=5，4，3n Ia= -

36、closure(J)= -closure(5，4，3)n =5，4，3，6，2，7，861a 234578aa n設設a是是中的一中的一個字符，定義個字符，定義nIa= -closure(J)n 其中，其中，J為為I中的中的某個狀態出發經某個狀態出發經過一條過一條a弧而到弧而到達的狀態集合。達的狀態集合。Ia=？n確定化的過程確定化的過程: :n 不失一般性，設字母表只包含兩個不失一般性，設字母表只包含兩個a a和和b b，我們構造一張表，我們構造一張表: :IIaIb -C losure(X )u首先，置第首先，置第1行第行第1列為列為-closure(X)求出這一列的求出這一列的Ia，Ib

37、；u然后，檢查這兩個然后，檢查這兩個Ia，Ib，看，看它們是否已在表中的第一列中出它們是否已在表中的第一列中出現，把未曾出現的填入后面的空現，把未曾出現的填入后面的空行的第行的第1列上，求出每行第列上，求出每行第2，3列列上的集合上的集合.u重復上述過程，知道所有第重復上述過程，知道所有第2，3列子集全部出現在第一列為止。列子集全部出現在第一列為止。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,

38、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,YXY 514236ab abababn現在把這張表看成一個狀態轉換矩陣，把其中的每個子現在把這張表看成一個狀態轉換矩陣，把其中的每個子集看成一個狀態。集看成一個狀態。n這張表唯一刻劃了一個確定的有限自動機這張表唯一刻劃了一個確定的有限自動機M，它的初態，它的初態是是-closure(X) ，它的終態是含有原終態，它的終態是含有原終態Y的子集。的子集。n不難看出，這個不難看出，這個DFA M與與M等價。等價。IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5

39、,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,6,Y5,4,6,1,YIIaIbX,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,

40、3,6,1,Y5,2,3,1,6,Y5,4,6,1,YIab012132214334465565634Iab0121322143344655656340123546aabbbabaabababFA正規集正規集正規式正規式DFANFA3.3.13.3.23.3.33.3.53.3.5 正規式與有限自動機的等價性正規式與有限自動機的等價性n定理：定理：n 1. 對任何對任何FA M，都存在一個正規式，都存在一個正規式r，使得使得L(r)=L(M)。n 2. 對任何正規式對任何正規式r，都存在一個，都存在一個FA M，使得使得L(M)=L(r)。n對轉換圖概念拓廣，令每條弧可用一個對轉換圖概念拓廣，

41、令每條弧可用一個正規式作標記。正規式作標記。(對一類輸入符號對一類輸入符號)n證明：證明： n 1 1 對對 上任一上任一NFA MNFA M，構造一個，構造一個 上的正規上的正規式式r r，使得，使得L(r)=L(M)L(r)=L(M)。n首先，在首先，在M M的轉換圖上加進兩個狀態的轉換圖上加進兩個狀態X X和和Y Y，從從X X用用弧連接到弧連接到M M的所有初態結點，從的所有初態結點，從M M的所有終態結點用的所有終態結點用弧連接到弧連接到Y Y，從而形，從而形成一個新的成一個新的NFANFA，記為，記為M M，它只有一個初態，它只有一個初態X X和一個終態和一個終態Y Y，顯然，顯然

42、L(M)=L(ML(M)=L(M) )。n然后，反復使用下面的一條規則，逐步消然后，反復使用下面的一條規則，逐步消去的所有結點，直到只剩下去的所有結點，直到只剩下X X和和Y Y為止；為止；代之為代之為ijr1r2kikr1r2代之為代之為ijr1|r2ijr2r1代之為代之為ikr1r2*r3ijr1r3kr212354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1q最后，最后，X到到Y的弧上標記的正規式即為的弧上標記的正規式即為所構造的正規式所構造的正規式rq顯然顯然L(r)=L(M)=L(M)XYrn定理：

43、定理：n 1. 對任何對任何FA M，都存在一個正規式，都存在一個正規式r，使得，使得L(r)=L(M)。n 2. 對任何正規式對任何正規式r，都存在一個，都存在一個FA M，使得，使得L(M)=L(r)。n證明證明2: 對于對于 上的正規式上的正規式r，構造一個，構造一個NFA M，使，使L(M)=L(r)，并且，并且M只有一個只有一個終態，而且沒有從該終態出發的箭弧。終態，而且沒有從該終態出發的箭弧。n 下面使用關于下面使用關于r中運算符數目的歸納法中運算符數目的歸納法證明上述結論。證明上述結論。n(1) 若若r具有零個運算符，則具有零個運算符，則r=或或r=或或r=a，其中，其中a。此時

44、下圖所示的三個有。此時下圖所示的三個有限自動機顯然符合上述要求。限自動機顯然符合上述要求。q0q0qfaq0qf(2) 假設結論對于少于假設結論對于少于k(k1)個運算符的正個運算符的正規式成立。規式成立。 當當r中含有中含有k個運算符時，個運算符時，r有三種情形：有三種情形：情形情形1：r=r1|r2，r1,r2中運算符個數少于中運算符個數少于k。從而，由歸納假設，對從而，由歸納假設，對ri存在存在Mi=，使得，使得L(Mi)=L(ri)，并且，并且Mi沒沒有從終態出發的箭弧有從終態出發的箭弧i=1,2）。不妨設）。不妨設S1S2=，在，在S1 S2中加入兩個新狀態中加入兩個新狀態q0，f0

45、。 令令M=，其中，其中定義如下：定義如下：(a) (q0, )=q1,q2(b) (q,a)= 1(q,a), 當當qS1-f1, a1(c) (q,a)= 2(q,a), 當當qS2-f2, a2(d) (f1,)=(f2,)=f0。 M的狀態轉換如右圖所示。的狀態轉換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r) q0f0M1q1f1M2q2f2 l情形情形2：r=r1r2, 設設Mi同情形同情形1(i=1,2)。l 令令M=，其中其中定義如下：定義如下：l(a) (q,a)= 1(q,a), 當當qS1-f1, a1l(b) (q,a)= 2(q,a),

46、 當當qS2, a2l(c) (f1,)=q2l M的狀態轉換如右圖所示。的狀態轉換如右圖所示。l L(M)=L(M1)L(M2)l =L(r1)L(r2)=L(r)。 M1q1f1M2q2f2l情形情形3：r=r1*。設。設M1同情形同情形1。l令令M=，其，其中中q0, f0S1，定義如下：定義如下：l(a) (q0,)=(f1,)=q1, f0l(b) (q,a)= 1(q, a), 當當qS1-f1, a1。lM的狀態轉換如右圖所示。的狀態轉換如右圖所示。lL(M) = L(M1)* = L(r1)* = L(r)l至此，結論至此，結論2獲證。獲證。 M1q1f1q0f0 1) 1)

47、構造構造 上的上的NFA M NFA M 使得使得 L(V)=L(M) L(V)=L(M)首先，把首先，把V V表示成表示成XYV上述證明過程實質上是一個將正規表達式上述證明過程實質上是一個將正規表達式轉換為有限自動機的算法。轉換為有限自動機的算法。代之為代之為ijV1V2kikV1V2代之為代之為ijV1|V2ijV2V1代之為代之為ikV1*ij kV1然后，按下面的三條規則對然后，按下面的三條規則對V進行分裂進行分裂n逐步把這個圖轉變為每條弧只標記為逐步把這個圖轉變為每條弧只標記為 上的上的一個字符或一個字符或，最后得到一個，最后得到一個NFA M，顯，顯然然L(M)=L(V)n(a|b

48、)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY 514236ab abababIIaIbX,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,6,Y5,4,6,1,YXY 514236ab abababIab0121322143344655656340123546aabbbabaabababF

49、A正規集正規集正規式正規式DFANFA3.3.13.3.23.3.33.3.5DFA3.3.63.3.6 確定有限自動機的化簡確定有限自動機的化簡n對對DFA M的化簡的化簡:尋找一個狀態數比尋找一個狀態數比M少少的的DFA M，使得，使得L(M)=L(M)n假設假設s和和t為為M的兩個狀態，稱的兩個狀態，稱s和和t等價等價:如果從狀態如果從狀態s出發能讀出某個字出發能讀出某個字而停止而停止于終態，那么同樣，從于終態，那么同樣，從t出發也能讀出出發也能讀出而停止于終態；反之亦然。而停止于終態；反之亦然。n兩個狀態不等價，則稱它們是可區別的。兩個狀態不等價，則稱它們是可區別的。n對一個對一個DF

50、A M最少化的基本思想最少化的基本思想:n 把把M的狀態集劃分為一些不相交的子集，的狀態集劃分為一些不相交的子集，使得任何兩個不同子集的狀態是可區別使得任何兩個不同子集的狀態是可區別的，而同一子集的任何兩個狀態是等價的，而同一子集的任何兩個狀態是等價的。最后，讓每個子集選出一個代表，的。最后，讓每個子集選出一個代表，同時消去其他狀態。同時消去其他狀態。n具體做法具體做法: 對對M的狀態集進行劃分的狀態集進行劃分n首先，把首先，把S劃分為終態和非終態兩個子集，劃分為終態和非終態兩個子集，形成基本劃分形成基本劃分。 n假定到某個時候，假定到某個時候，已含已含m個子集，記個子集，記為為=I(1)，I

51、(2)，I(m)，檢查，檢查中中的每個子集看是否能進一步劃分的每個子集看是否能進一步劃分:n對某個對某個I(i)，令，令I(i)=s1,s2, ,sk，若存，若存在一個輸入字符在一個輸入字符a使得使得Ia(i) 不會包含在現不會包含在現行行的某個子集的某個子集I(j)中即，中即， Ia(i)中的元中的元素分布在現行劃分的多個子集中），則素分布在現行劃分的多個子集中），則至少應把至少應把I(i)分為兩個部分。分為兩個部分。n例如，假定狀態例如，假定狀態s1和和s2經經a弧分別到達弧分別到達t1和和t2，而，而t1和和t2屬于現行屬于現行中的兩個不同中的兩個不同子集，說明有一個字子集，說明有一個字

52、， t1讀出讀出后到后到達終態，而達終態，而t2讀出讀出后不能到達終態，或后不能到達終態，或者反之，那么對于字者反之，那么對于字a ， s1讀出讀出a后后到達終態，而到達終態，而s2讀出讀出a不能到達終態，不能到達終態，或者反之，所以或者反之，所以s1和和s2不等價。不等價。s1t1as2t2a j in則將則將I(i)分成兩半，使得一半含有分成兩半，使得一半含有s1 :n I(i1)=s|sI(i)且且s經經a弧到達弧到達t, n 且且t與與t1屬于現行屬于現行中的同一子集中的同一子集n 另一半含有另一半含有s2 : I(i2)=I(i)-I(i1)s1t1as2t2a j in一般地，對某

53、個一般地，對某個a和和I(i)，若，若Ia(i) 落入現行落入現行中中 N個不同子集，則應把個不同子集，則應把I(i)劃分成劃分成N個不相個不相交的組，使得每個組交的組，使得每個組J的的Ja都落入的都落入的同一同一子集。這樣構成新的劃分。子集。這樣構成新的劃分。n重復上述過程，直到重復上述過程，直到所含子集數不再增長。所含子集數不再增長。n對于上述最后劃分對于上述最后劃分中的每個子集，我們選中的每個子集，我們選取每個子集取每個子集I中的一個狀態代表其他狀態，中的一個狀態代表其他狀態，則可得到化簡后的則可得到化簡后的DFA M。n若若I含有原來的初態，則其代表為新的初態，含有原來的初態，則其代表

54、為新的初態，若若I含有原來的終態，則其代表為新的終態。含有原來的終態，則其代表為新的終態。0123546aabbbabaabababI(1)=0, 1, 2 I(2)=3, 4, 5, 6 Ia(1) =1, 3 I(11) =0, 2 I(12) =1I(2)=3, 4, 5, 6 I(11) =0, 2Ia(11) =1 Ib(11) =2, 5 I(111) =0 I(112) =2 I(12) =1 I(2)=3, 4, 5, 6 Ia(2) =3, 6 Ib(2) =4, 5 0123546aabbbabaababab0123aabbbaabFA正規集正規集正規式正規式DFANFA3

55、.3.13.3.23.3.33.3.5DFA3.3.685一一. .原理原理 單詞的詞法規則用正規式描述單詞的詞法規則用正規式描述 正規式正規式 NFA NFA DFA DFA min DFAmin DFALEXLEX編譯器編譯器LEXLEX源程序源程序lex.1lex.1詞法分析程序詞法分析程序Lex.yy.c二二. .用用LEXLEX建立詞法分析程序的過程建立詞法分析程序的過程3.4 詞法分析器的自動產生詞法分析器的自動產生-LEXC編譯器編譯器詞法分析程序詞法分析程序Lex.yy.c詞法分析程序詞法分析程序Lex.out或或lex.exe 詞法分析程序詞法分析程序L L單詞符號單詞符號輸

56、入串輸入串狀態轉換矩陣狀態轉換矩陣控制執行程序控制執行程序3.4 詞法分析器的自動產生詞法分析器的自動產生-LEX3.4 詞法分析器的自動產生詞法分析器的自動產生-LEXlexlex源程序源程序 lex lex源程序由三部分組成源程序由三部分組成聲明聲明% % 識別規則識別規則( (翻譯規則）翻譯規則）%輔助過程輔助過程 聲明包括變量，符號常量和正規定義式。聲明包括變量，符號常量和正規定義式。正規定義式是形式如下的一系列定義：正規定義式是形式如下的一系列定義： d1 d1 r1 r1 d2 d2 r2 r2 dn dn rn rn其中，其中， di di 表示不同的名字，表示不同的名字， ri ri 是正規式是正規式識別規則翻譯規則的形式為：識別規則翻譯規則的形式為： p1 p1 動作動作1 1 p2 p2 動作動作22 p n p n 動作動作nn 每個每個pi是一個正規式，稱為詞形。是一個正規式，稱為詞形。 每個每個動作動