第二章詞法分析

1、1第一章第一章 總結(jié)總結(jié) 語(yǔ)言與語(yǔ)言的翻譯編譯器的基本組成編譯器的分析/綜合模式(編譯器基礎(chǔ)架構(gòu))掃描遍數(shù)編譯器的編寫2第二章第二章 詞法分析詞法分析詞法的雙重含義詞法的雙重含義規(guī)定單詞形成的規(guī)則，被稱為構(gòu)詞規(guī)則或詞法規(guī)則。相當(dāng)于立法，規(guī)定語(yǔ)言所允許的合法單詞。 根據(jù)構(gòu)詞規(guī)則識(shí)別輸入序列，被稱為詞法分析。相當(dāng)于執(zhí)法，識(shí)別出合法的單詞、指出非法的輸入序列。主要內(nèi)容主要內(nèi)容詞法分析中的若干問(wèn)題模式的形式化描述記號(hào)的識(shí)別從正規(guī)式到詞法分析器上機(jī)： DBMS的設(shè)計(jì)與實(shí)現(xiàn)SQL的詞法分析器x := y + z * 60.0 ;id1 := id2 + id3 * 60.0 ;32.1 詞法分析中的若干問(wèn)

2、題詞法分析中的若干問(wèn)題F記號(hào)、模式與單詞記號(hào)、模式與單詞單詞的基本分類：關(guān)鍵字kw(key word, or reserved word) 標(biāo)識(shí)符id(identifier)字面量literal特殊符號(hào)ks(key symbol, or special symbol)例2.1語(yǔ)句position := initial + rate * 60記號(hào) id ks id ks id ks number注意：稱識(shí)別出id而不是rate或initial問(wèn)題：根據(jù)什么識(shí)別這些詞法的基本單位（詞法元素）？42.1 詞法分析中的若干問(wèn)題詞法分析中的若干問(wèn)題三個(gè)術(shù)語(yǔ)：模式模式(pattern)：產(chǎn)生和識(shí)別元素的規(guī)

3、則 記號(hào)記號(hào)(token)： 按照某個(gè)模式(或規(guī)則)識(shí)別出的元素(一組) 單詞單詞(lexeme)：被識(shí)別出的元素自身的值(一個(gè))，也稱為詞值 記號(hào)的類別記號(hào)的類別單詞舉例單詞舉例模式的非形式化描述模式的非形式化描述const(01)constconstif(03)ififrelation(81), =, =, , , =, =, =, .id(82)pi, count, D2字母打頭的字母數(shù)字串num(83)3.1416, 0, 6.02E23任何數(shù)值常數(shù)literal(84)“core dumped”雙引號(hào)間的任意字符串Commentx is an integer括號(hào)間的任意字符串52.1

4、 詞法分析中的若干問(wèn)題詞法分析中的若干問(wèn)題F記號(hào)的屬性記號(hào)的屬性記號(hào)是按照某個(gè)模式識(shí)別出的元素。賦值句position := initial + rate * 60position、initial和rate均為標(biāo)識(shí)符，種類均是id。問(wèn)題：當(dāng)識(shí)別出一個(gè)id時(shí)，如何判定是哪個(gè)id ？ 當(dāng)識(shí)別出一個(gè)relation時(shí)，究竟是 = 還是 25 由三個(gè)記號(hào)組成類別 82 81 83屬性 “mycount” 5 25注意：5與25的區(qū)別（根據(jù)記號(hào)的類別） 25與“25”的區(qū)別（如何區(qū)別？）記號(hào)的類別relation(81)id(82)num(83)62.1 詞法分析中的若干問(wèn)題詞法分析中的若干問(wèn)題F詞法分

5、析器的作用與工作方式詞法分析器的作用與工作方式 詞法分析器是編譯器中唯一與源程序打交道的部分。濾掉源程序中的無(wú)用成分，如注釋、空格、回車等；處理與平臺(tái)有關(guān)的輸入，如文件結(jié)束符的不同表示等；根據(jù)模式識(shí)別記號(hào)，并交給語(yǔ)法分析器；調(diào)用符號(hào)表管理器或出錯(cuò)處理器，進(jìn)行相關(guān)處理 。工作方式：?jiǎn)为?dú)掃描，作為語(yǔ)法分析器的子程序，并行工作72.2 模式的形式化描述模式的形式化描述F字符串與語(yǔ)言字符串與語(yǔ)言 從詞法分析的角度看程序設(shè)計(jì)語(yǔ)言，它是由記號(hào)組成的集合。定義定義2.1 語(yǔ)言L是有限字母表上有限長(zhǎng)度字符串的集合說(shuō)明說(shuō)明：F字母表是字符的集合，這些字符可以組成字符串。F兩個(gè)有限（計(jì)算機(jī)的表達(dá)能力有限）：字母表

6、是有限的；字符串的長(zhǎng)度是有限的。例2.3字母表=a, b, c，則其上的語(yǔ)言L=, a, b, c, aa, ab, ac, ba, bb, bc, .82.2 模式的形式化描述模式的形式化描述字符串的基本概念字符串的基本概念術(shù)語(yǔ)術(shù)語(yǔ)示例示例|S| |abc| = 3 | = 0S1S2 abc def = abcdefSn (abc)3 = abcabcabcS的前綴的前綴X abc的前綴有：，a，ab, abcS的后綴的后綴X abc的后綴有：，c，bc, abcS的子串的子串X abc的子串有： ，a，b, c, S的真前綴的真前綴abc的真前綴有：a，abS的真后綴的真后綴？S的真子串

7、的真子串 ？S的子序列的子序列Xabdf是abcdef的一個(gè)子序列92.2 模式的形式化描述模式的形式化描述若 L = a, b, M = c, d，則 LM = ac, bc, ad, bd，LM = L* = , a, b, aa, bb, ab, ba, aaa, . L+ = a, b, aa, bb, ab, ba, aaa, .術(shù)語(yǔ)術(shù)語(yǔ)意義意義 空集合 空串是唯一元素X=LM 并: X=s| sL or sM X=LM 交: X=s|sL and sMX=LM 連接: X=st|sL and tM X=L* (星)閉包: X=L0L1L2. X=L+ 正閉包: X=L1L2L3.

8、102.2 模式的形式化描述模式的形式化描述F正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集定義定義2.2 令是一個(gè)有限字母表，則上的正規(guī)式及其表示的集合遞歸定義如下: 1. 是正規(guī)式，它表示集合L()= 2. 若a是上的字符，則a是正規(guī)式，它表示集合L(a)=a 3. 若正規(guī)式r和s分別表示集合L(r)和L(s)，則 （a） r|s是正規(guī)式，表示集合L(r)L(s)， （b） rs是正規(guī)式，表示集合L(r)L(s)， （c） r*是正規(guī)式，表示集合(L(r)*， （d）(r)是正規(guī)式，表示的集合仍然是L(r)可用正規(guī)式描述的語(yǔ)言稱為正規(guī)語(yǔ)言正規(guī)語(yǔ)言或正規(guī)集正規(guī)集。 112.2 模式的形式化描述模式的形式化描述

9、定義定義2.2說(shuō)明：說(shuō)明：F運(yùn)算的優(yōu)先級(jí)與結(jié)合性三種運(yùn)算均具有左結(jié)合性質(zhì)；優(yōu)先級(jí)從高到低：閉包、連接、或。正規(guī)式中不必要的括號(hào)可以被省略。例如：( a ) | ( ( ( b )* ) ( c ) )可以簡(jiǎn)化成 a | b* c。 F正規(guī)式的等價(jià)不同算術(shù)表達(dá)式可以表示同一個(gè)數(shù)，如3+5、5+3、2+6等均表示8。不同正規(guī)式也可以表示同一個(gè)正規(guī)集，即正規(guī)式與正規(guī)集之間是多對(duì)一的關(guān)系。122.2 模式的形式化描述模式的形式化描述定義定義2.3 若正規(guī)式P和Q表示了同一個(gè)正規(guī)集，則稱P和Q是等價(jià)的，記為P = Q。例2.4 設(shè)字母表 = a，b，c，則上有：正規(guī)式正規(guī)式 正規(guī)集正規(guī)集 a，b，ca，

10、b，c a|b，b|aab=a，b a(a|b)*a，aa，ab，aba，abb，aab，.，a為首的ab串 *，a，b，c，aa，ab，ac，ba，bb，bc，. 例2.5 令 L(x) = a，b，L(y) = c，d，則 L( x | y )=a，b，c，d L( y | x )=a，b，c，d 132.2 模式的形式化描述模式的形式化描述利用正規(guī)式的等價(jià)性可以化簡(jiǎn)復(fù)雜的正規(guī)式。正規(guī)式的等價(jià)性判定可以采用兩種方法：根據(jù)定義，證明不同的正規(guī)式表示同一集合（例2.5）根據(jù)下述正規(guī)式的代數(shù)性質(zhì)進(jìn)行運(yùn)算公理公理公理公理r | s = s | r( r s ) t = r ( s t )r | (

11、 s | t ) = ( r | s ) | t r = r, r = rr ( s | t ) = r s | r tr* = ( r+ | )( s | t ) r = s r | t rr* = r*142.2 模式的形式化描述模式的形式化描述F記號(hào)的說(shuō)明記號(hào)的說(shuō)明自然語(yǔ)言對(duì)模式的非形式化描述很不精確，而正規(guī)式可以嚴(yán)格地規(guī)定記號(hào)的模式，用正規(guī)式說(shuō)明記號(hào)的公式為：記號(hào)記號(hào) = 正規(guī)式正規(guī)式讀作 （左邊）記號(hào)定義為（右邊）正規(guī)式（左邊）記號(hào)定義為（右邊）正規(guī)式或者 記號(hào)是正規(guī)式記號(hào)是正規(guī)式例如，id=a ( a | b )* 可以讀作為 id定義為定義為a ( a | b )*注：注：在不引

12、起混淆的情況下，把說(shuō)明記號(hào)的公式簡(jiǎn)稱為正規(guī)式，或者規(guī)則。152.2 模式的形式化描述模式的形式化描述例2.6 記號(hào)relation、id和num分別是Pascal的關(guān)系運(yùn)算符、標(biāo)識(shí)符和無(wú)符號(hào)數(shù)，它們的正規(guī)式表示如下所示。 relation = | = | | | = | =id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z) (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|

13、z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z |0|1|2|3|4|5|6|7|8|9)*num = (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* (|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)(|E(+|-|)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)返回返回162.2 模式的形式化描述模式的形式化描述簡(jiǎn)化正規(guī)式描述簡(jiǎn)化正規(guī)式描述F正閉包正閉包若r是表示L(r)的正規(guī)式，則r+是表示( L( r

14、 ) )+的正規(guī)式：r+ = r r* = r* r，r* = r+ | 例如： (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*化簡(jiǎn)為：(0|1|2|3|4|5|6|7|8|9)+F可缺省可缺省若r是正規(guī)式，則r?是表示L(r)的正規(guī)式： r?=r|例如： E( + | - | ) 可改寫為：E( + | - )?注：注：+、?、*具有相同的結(jié)合性和優(yōu)先級(jí)引入？的原因在于字符無(wú)法使用鍵盤輸入。172.2 模式的形式化描述模式的形式化描述F字符組字符組若r是僅由|運(yùn)算構(gòu)成的正規(guī)式，則可改寫為r，其中r可以有如下兩種形式：枚舉：如abc，等價(jià)于 a | b

15、| c分段: 如0-9a-z，等價(jià)于0123456789abcdefghijklmnopqrstuvwxyzF非字符組非字符組若r是一個(gè)字符組形式的正規(guī)式，則r是表示 - L(r)的正規(guī)式。 例如：若 =a, b, c, d, e, f, g，則 L(abc) = d, e, f, g 182.2 模式的形式化描述模式的形式化描述輔助定義輔助定義 通俗地講，輔助定義的作用是為復(fù)雜的或重復(fù)出現(xiàn)的正規(guī)式命名，并在以后的使用中用名字代替該正規(guī)式。輔助定義的形式與正規(guī)式一樣： 輔助定義名字輔助定義名字 = 正規(guī)式正規(guī)式注：輔助定義不與任何模式匹配；作為輔助定義的正規(guī)式僅供內(nèi)部使用，而不用于說(shuō)明記號(hào)。輔

16、助定義：輔助定義：內(nèi)部名內(nèi)部名 = 正規(guī)式正規(guī)式規(guī)則：規(guī)則：記號(hào)名記號(hào)名= 正規(guī)式正規(guī)式192.2 模式的形式化描述模式的形式化描述例2.6 引入正規(guī)式的縮寫形式和輔助定義式后，id和num的正規(guī)定義式可重寫如下： char= a-zA-Zdigit= 0-9digits= digit+optional_fraction = ( . digits )?optional_exponent= ( E (+|-)? digits )?id= char ( char|digit )*num= digits optional_fraction optional_exponent對(duì)比原來(lái)對(duì)比原來(lái)20上次課

17、總結(jié)上次課總結(jié)F詞法的雙重含義； F模式、記號(hào)與單詞；F形式化描述：正規(guī)式與正規(guī)集；F正規(guī)式描述；正規(guī)式簡(jiǎn)化表示、輔助定義212.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)模式的描述正規(guī)式記號(hào)的識(shí)別有限自動(dòng)機(jī)（不確定、確定）F不確定的有限自動(dòng)機(jī)不確定的有限自動(dòng)機(jī)（Nondeterministic Finite Automaton, NFA） 定義定義2.4 NFA是一個(gè)五元組（5-tuple）：M =（S，move，s0，F(xiàn)），其中（1） S是有限個(gè)狀態(tài)（state）的集合；（2） 是有限個(gè)輸入字符（包括）的集合；（3） move是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)，move(si，ch)=sj表示，當(dāng)前狀態(tài)

18、si下若遇到輸入字符ch，則轉(zhuǎn)移到狀態(tài)sj；（4） s0是唯一的初態(tài)（也稱開始狀態(tài)）；（5） F是終態(tài)集（也稱接受狀態(tài)集），它是S的子集，包含了所有的終態(tài)。222.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)NFA兩種直觀的表示方式兩種直觀的表示方式 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖NFA中的每個(gè)狀態(tài)，對(duì)應(yīng)轉(zhuǎn)換圖中的一個(gè)節(jié)點(diǎn)；NFA中的每個(gè)move(si, a)=sj，對(duì)應(yīng)轉(zhuǎn)換圖中的一條有向邊；表示從節(jié)點(diǎn)si出發(fā)進(jìn)入節(jié)點(diǎn)sj ，字符a(或)是邊上的標(biāo)記。 狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣每個(gè)矩陣元素Msi,a中的內(nèi)容，是從狀態(tài)si出發(fā)，經(jīng)字符a(或)所到達(dá)的下一狀態(tài)sj； 在轉(zhuǎn)換矩陣中，一般以矩陣第一行所對(duì)應(yīng)的狀

19、態(tài)為初態(tài)，而終態(tài)需要特別指出。狀態(tài)轉(zhuǎn)換圖中如何表示呢？狀態(tài)轉(zhuǎn)換圖中如何表示呢？232.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)例2.7 識(shí)別正規(guī)式(a|b)*abb所描述正規(guī)集的NFA的三種表示形式分別如下。(其中轉(zhuǎn)換矩陣表示中0為初態(tài)，3為終態(tài))S = 0, 1, 2, 3, = a, bmove = move(0, a) = 0, move(0, a) = 1, move(0, b) = 0, move(1, b) = 2, move(2, b) = 3 s0 = 0, F = 3242.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)NFA如何識(shí)別記號(hào)如何識(shí)別記號(hào)? 對(duì)字符串，從初態(tài)開始

20、，經(jīng)一系列狀態(tài)轉(zhuǎn)移到達(dá)終態(tài)。例如：對(duì)于字符串a(chǎn)bb，有定義定義：move = move(0, a) = 0, move(0, a) = 1, move(0, b) = 0, move(1, b) = 2, move(2, b) = 3 move(0, a)=1, move(1, b)=2, move(2, b)=3轉(zhuǎn)換矩陣轉(zhuǎn)換矩陣：m0, a=0, 1, m1, b=2, m2, b=3轉(zhuǎn)換圖轉(zhuǎn)換圖：0a1b2b3，最直觀開始識(shí)別能是開始識(shí)別能是0a0嗎？嗎？252.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)例2.8 識(shí)別表2.1中記號(hào)relation、id和num的轉(zhuǎn)換圖。relation

21、 = | = | | | = | =id = char(char|digit)*=能被識(shí)別為和=嗎？最長(zhǎng)識(shí)別原則最長(zhǎng)識(shí)別原則262.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)optional_fraction = ( . digits )?optional_exponent = ( E (+ | -)? digits )?num = digits optional_fraction optional_exponent272.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)NFA識(shí)別記號(hào)的最大特點(diǎn)是它的不確定性不確定性，即在當(dāng)前狀態(tài)下對(duì)同一字符有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移。 定義：move函數(shù)是1對(duì)多

22、的；move = move(0, a) = 0, move(0, a) = 1, move(0, b) = 0,.狀態(tài)轉(zhuǎn)換圖：同一狀態(tài)有多于一條邊標(biāo)記相同字符轉(zhuǎn)移到不同的狀態(tài)；狀態(tài)轉(zhuǎn)換矩陣：Msi,a是一個(gè)狀態(tài)的集合282.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)NFA識(shí)別輸入序列的一般方法：反復(fù)試探所有路徑，直到到達(dá)終態(tài)，或者到達(dá)不了終態(tài)。不確定性帶來(lái)的問(wèn)題：識(shí)別輸入序列時(shí)，在當(dāng)前狀態(tài)下遇到同一字符，應(yīng)轉(zhuǎn)移到哪個(gè)下一狀態(tài)？ 例2.9 在正規(guī)式 (a|b)*abb的NFA上識(shí)別輸入序列abb和abab。292.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)NFA識(shí)別記號(hào)存在的問(wèn)題只有嘗試了全

23、部可能的路徑，才能確定一個(gè)輸入序列不被接受，而這些路徑的條數(shù)隨著路徑長(zhǎng)度的增長(zhǎng)成指數(shù)增長(zhǎng)。識(shí)別過(guò)程中需要進(jìn)行大量回溯，時(shí)間復(fù)雜度升高且算法趨于復(fù)雜。問(wèn)題問(wèn)題：是否可以構(gòu)造這樣的有限自動(dòng)機(jī)，它識(shí)別正規(guī)式所描述的字符串，且在任何一個(gè)狀態(tài)下遇到同一字符最多有一個(gè)狀態(tài)轉(zhuǎn)移？302.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)F確定的有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī)（Deterministic Finite Automaton, Deterministic Finite Automaton, DFADFA）定義定義2.5 DFA是NFA的一個(gè)特例，其中： （1）沒(méi)有狀態(tài)具有 狀態(tài)轉(zhuǎn)移（-transition）

24、，即狀態(tài)轉(zhuǎn)換圖中沒(méi)有標(biāo)記 的邊；（2）對(duì)每個(gè)狀態(tài) s 和每個(gè)字符 a ，最多有一個(gè)下一狀態(tài)。與NFA相比，DFA的特征是其確定性確定性定義：move（si, a）函數(shù)是1對(duì)1的；轉(zhuǎn)換圖： 從一個(gè)節(jié)點(diǎn)出發(fā)的邊上標(biāo)記均不相同； 轉(zhuǎn)換矩陣：M si , a 是一個(gè)狀態(tài)。 且字母表不包括 。312.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)DFA對(duì)NFA施加的兩條限制：限制1：沒(méi)有狀態(tài)轉(zhuǎn)移限制2：同一狀態(tài)下沒(méi)有重復(fù)字符的狀態(tài)轉(zhuǎn)移例2.10 正規(guī)式(a|b)*abb的DFA，識(shí)別輸入序列abb和abab： 識(shí)別abb：0a1b2b3，狀態(tài)，接受識(shí)別abab：0a1b2a1b2，？322.3 記號(hào)的識(shí)別

25、有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)DFA識(shí)別輸入序列的算法被稱為DFA模擬器或驅(qū)動(dòng)器，它與DFA共同構(gòu)成詞法分析器的核心，特點(diǎn)是算法與模式無(wú)關(guān)。算法算法2.1 模擬DFA輸入DFA D和輸入字符串x (eof)。D的初態(tài)為s0，終態(tài)集為F輸出若 D 接受 x，回答“yes”，否則回答“no”。 方法用下述過(guò)程識(shí)別x：s := s0; ch := nextchar;- 初值while cheof- x結(jié)束?loop s := move(s, ch); ch := nextchar;- 循環(huán)轉(zhuǎn)移end loop;if s is in F- 終態(tài)返回then return “yes”; else ret

26、urn “no”;end if;332.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)識(shí)別abb：1. s = 0, ch = a2. s = 1, ch = b3. s = 2, ch = b4. s = 3, ch = eof5. yes識(shí)別abab：1. s = 0, ch = a2. s = 1, ch = b3. s = 2, ch = a4. s = 1, ch = b5. s = 2, ch = eof6. no(a|b)*abb的的DFA342.3 記號(hào)的識(shí)別有限自動(dòng)機(jī)記號(hào)的識(shí)別有限自動(dòng)機(jī)F有限自動(dòng)機(jī)的等價(jià)有限自動(dòng)機(jī)的等價(jià)定義定義2.6 若有限自動(dòng)機(jī)M和M識(shí)別同一正規(guī)集，則稱M和

27、M是等價(jià)的，記為M=M。提示提示：正規(guī)式與有限自動(dòng)機(jī)從兩個(gè)側(cè)面表示正規(guī)集。正規(guī)式是描述，自動(dòng)機(jī)是識(shí)別。因此，當(dāng)它們表示相同集合時(shí)，均存在等價(jià)的問(wèn)題。有幾種可能的等價(jià)？ 352.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器構(gòu)造詞法分析器的一般方法和步驟：描述描述：用正規(guī)式對(duì)模式進(jìn)行描述；構(gòu)造構(gòu)造NFA：為每個(gè)正規(guī)式構(gòu)造一個(gè)NFA；確定化確定化：將NFA轉(zhuǎn)換成等價(jià)的DFA；最小化最小化：優(yōu)化DFA，使其狀態(tài)數(shù)最少；構(gòu)造詞法分析器構(gòu)造詞法分析器：由DFA構(gòu)造詞法分析器。問(wèn)題問(wèn)題：為何不直接從正規(guī)式構(gòu)造DFA？機(jī)器構(gòu)造需要規(guī)范的算法；正規(guī)式NFA：有規(guī)范的一對(duì)一的構(gòu)造算法；1.DFA分析器：有便于記號(hào)

28、識(shí)別的算法。36上次課總結(jié)上次課總結(jié)FNFA定義M =（S，move，s0，F(xiàn)）FNFA直觀表示：狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣FNFA識(shí)別記號(hào)FNFA的不確定性FDFANFA的特例F模擬DFA的算法F自動(dòng)機(jī)的等價(jià)F構(gòu)造詞法分析器的步驟372.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器F從正規(guī)式到從正規(guī)式到NFA 算法算法2.2 Thompson 算法輸入字母表上的正規(guī)式 r輸出接受 L(r) 的NFA N方法首先分解 r，然后根據(jù)下述步驟構(gòu)造NFA：對(duì)，構(gòu)造NFA N() 接受； 對(duì)上的每個(gè)字符a，構(gòu)造NFA N(a) 接受a；1.若N(p)和N(q)是正規(guī)式p和q的NFA，則ar|srsr*(

29、r)382.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器（a）對(duì)正規(guī)式p|q，構(gòu)造NFA N(p|q) 接受L(p)L(q)；（b）對(duì)正規(guī)式pq，構(gòu)造NFA N(pq) 接受L(p)L(q)； （c）對(duì)正規(guī)式p*，構(gòu)造NFA N(p*) 接受L(p*)； （d）對(duì)于正規(guī)式(p)，使用p本身的NFA，不再構(gòu)造。ar|srsr*(r)392.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器例2.11 用Thompson算法構(gòu)造正規(guī)式r = (a | b)* a b b的NFA N(r) 。先分解正規(guī)式，再自下而上構(gòu)造NFA注意注意：算法的構(gòu)造與正規(guī)式一一對(duì)應(yīng)構(gòu)造一個(gè)新的NFA最多增加兩個(gè)狀態(tài)402.4

30、 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器F從從NFA到到DFAFNFA識(shí)別記號(hào)的識(shí)別記號(hào)的“并行并行”方法方法例2.12 從甲地到乙地，可以乘汽車也可以騎自行車，具體路線如右圖。其中c表示乘車，b表示騎自行車?，F(xiàn)在要求從甲地到乙地，只許乘車而不許騎自行車，該如何走？抽象：識(shí)別是否有從甲到乙標(biāo)記為全c的路徑串行（試探）：甲 c 2 無(wú)路可走，退回甲 c 1 c 3 無(wú)路可走，退回甲 c 1 c 乙 到達(dá)乙地，成功 并行：有多輛汽車，每次到達(dá)汽車能到達(dá)的全體甲 c 1, 2c 3, 乙到達(dá)乙地，成功412.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器由于并行的方法在每試探一步時(shí)，考慮了所有的下一

31、狀態(tài)轉(zhuǎn)移（所有下一狀態(tài)作為一個(gè)狀態(tài)集合），因此所走的每一步都是確定的。用NFA識(shí)別記號(hào)，并不采用串行的方法（算法不易構(gòu)造，復(fù)雜度高且回溯），而是采用并行的方法，核心思想是將不確定的下一狀態(tài)確定化。NFA上識(shí)別記號(hào)的確定化方法是在計(jì)算下一狀態(tài)轉(zhuǎn)移時(shí)，實(shí)施如下確定化的兩個(gè)步驟：消除 狀態(tài)轉(zhuǎn)移：-閉包(T) 消除多于一個(gè)的下一狀態(tài)轉(zhuǎn)移：smove(S, a)422.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器-閉包(T)：從狀態(tài)T出發(fā)，不經(jīng)任何字符達(dá)到的狀態(tài)全體。smove(S, a)：從狀態(tài)集S出發(fā)，標(biāo)記為a的下一狀態(tài)全體。與move(s, a)的唯一區(qū)別：用狀態(tài)集取代狀態(tài)。定義定義2.6 狀態(tài)集

32、T的-閉包(T)是一個(gè)狀態(tài)集，且滿足：（1）T中所有狀態(tài)屬于-閉包(T)；（2）任何smove(-閉包(T)，)屬于-閉包(T)；（3）再無(wú)其他狀態(tài)屬于-閉包(T)。 根據(jù)定義，-閉包(s2)應(yīng)包括：1. s2自身s2（1）2. s4s2, s4（2）3. s5s2, s4, s5（2）432.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器算法算法2.4 求-閉包輸入狀態(tài)集T輸出狀態(tài)集T的-閉包方法for T中每個(gè)狀態(tài)t loop 加入t到U; push(t); end loop;while 棧不空 looppop(t); for 每個(gè)u = move(t, ) loop if u不在U中 th

33、en 加入u到U; push(u); end if; end loop;end loop; return U;閉包U和模擬遞歸的stack問(wèn)題問(wèn)題：試將函數(shù)直接寫為遞歸的-閉包(s2)Ustack1s2s22s2, s4s43 s2, s4, s5s54 s2, s4, s5442.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器算法算法2.3 模擬NFA輸入NFA N，x(eof)，s0，F(xiàn) 輸出若N接受x，回答“yes”，否則“no” 方法用下邊的過(guò)程對(duì)x進(jìn)行識(shí)別。S是一個(gè)狀態(tài)的集合 S := -閉包(s0);- 所有可能初態(tài)的集合a := nextchar;while a eof loop

34、S := -閉包(smove(S，a); - 所有下一狀態(tài)的集合a := nextchar;end loop;if SF then return “yes”; else return “no”; end if; 模擬DFA模擬NFA開始初態(tài)(s0)初態(tài)集(S)下一狀態(tài)轉(zhuǎn)移下一狀態(tài)下一狀態(tài)集結(jié)束s is in FSF452.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器識(shí)別abb: 計(jì)算初態(tài)集：-閉包(0)= 0,1,2,4,7 A從A出發(fā)經(jīng)a到達(dá)：-閉包(smove(A, a)= 3,8,6,7,1,2,4 B從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b)= 5,9,6,7,1,2,4 C從C

35、出發(fā)經(jīng)b到達(dá)：-閉包(smove(C, b)= 5,10,6,7,1,2,4 D結(jié)束且D10=10，接受。識(shí)別的路徑為：A a B b C b D例2.13 在NFA上識(shí)別輸入序列abb和abab462.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器識(shí)別abab: 初態(tài)集：-閉包(s0)=0,1,2,4,7 A從A出發(fā)經(jīng)a到達(dá)：-閉包(smove(A, a) = 3,8,6,7,1,2,4 B從B出發(fā)經(jīng)b到達(dá)：-閉包(smove(B, b) = 5,9,6,7,1,2,4 C從C出發(fā)經(jīng)a到達(dá)：-閉包(smove(C, a) = 3,8,6,7,1,2,4 B從B出發(fā)經(jīng)b到達(dá)：-閉包閉包(smov

36、e(B, b) = 5,9,6,7,1,2,4 C識(shí)別路徑為：A a B b C a B b C。由于C10=，所以不接受例2.13 在NFA上識(shí)別輸入序列abb和abab472.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器F子集法子集法構(gòu)造構(gòu)造DFA并行模擬NFA的弱點(diǎn)：每次動(dòng)態(tài)計(jì)算下一狀態(tài)轉(zhuǎn)移的集合，效率低。改進(jìn)方法：將NFA上的全部路徑均確定化并且記錄下來(lái)，得到與NFA等價(jià)的DFA。 從甲地到乙地的路徑是一個(gè)NFA ，可找到一個(gè)等價(jià)的DFA。例2.14 用DFA識(shí)別cc和cbc：甲 c 1,2 c 3,乙， 接受 甲 c 1,2 b 3 c ?，不接受 消除了不確定性無(wú)需動(dòng)態(tài)計(jì)算狀態(tài)集合

37、48算法算法2.5 從NFA構(gòu)造DFA（子集法）輸入 NFA N輸出等價(jià)的DFA D，其初態(tài)含有NFA初態(tài)，終態(tài)是含有NFA終態(tài)的狀態(tài)集合。方法用下述過(guò)程構(gòu)造DFADstates = -閉包(s0) ;-是唯一狀態(tài)且未標(biāo)記while Dstates有未標(biāo)記狀態(tài)T loop 標(biāo)記T; for 每一個(gè)字符a loopU := -閉包(smove(T，a);if U非空 thenDtranT，a := U; if U不在Dstates中 then U作為未標(biāo)記狀態(tài)加入Dstates;end if;end if;end loop;end loop;狀態(tài)集狀態(tài)集Dstates和轉(zhuǎn)換矩陣和轉(zhuǎn)換矩陣Dtra

38、n49-閉包(0)=0,1,2,4,7*A-閉包(smove(A, a)=3,8,6,7,1,2,4*B-閉包(smove(A, b)=5,6,7,1,2,4*C-閉包(smove(B, a)=3,8,6,7,1,2,4B-閉包(smove(B, b)=5,9,6,7,1,2,4*D-閉包(smove(C, a)=3,8,6,7,1,2,4B-閉包(smove(C, b)=5,6,7,1,2,4C-閉包(smove(D, a)=3,8,6,7,1,2,4B-閉包(smove(D, b)=5,10,6,7,1,2,4*E-閉包(smove(E, a)=3,8,6,7,1,2,4B-閉包(smov

39、e(E, b)=5,6,7,1,2,4C例2.15 用算法2.5構(gòu)造(a|b)*abb的DFA 選擇哪一個(gè)選擇哪一個(gè)DFA？50上次課總結(jié)上次課總結(jié)F由正規(guī)式構(gòu)造NFA：Tompson算法FNFA的確定化NFA并行識(shí)別記號(hào)：smove， -閉包子集法構(gòu)造DFA 512.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器F最小化最小化DFA對(duì)于若干個(gè)等價(jià)的DFA，總是希望由狀態(tài)數(shù)最小的DFA構(gòu)造詞法分析器。將一個(gè)DFA等價(jià)變換為另一個(gè)狀態(tài)數(shù)最小的DFA的過(guò)程被稱為最小化最小化DFA。定義定義2.7 對(duì)于任何兩個(gè)狀態(tài)t和s，若從一狀態(tài)出發(fā)接受輸入字符串，而從另一狀態(tài)出發(fā)不接受，或者從t出發(fā)和從s出發(fā)到達(dá)

40、不同的接受狀態(tài)，則稱對(duì)狀態(tài)t和s是可區(qū)分可區(qū)分的。設(shè)想任何輸入序列對(duì)s和t均是不可區(qū)分不可區(qū)分的，則說(shuō)明從s出發(fā)和從t出發(fā)，分析任何輸入序列均得到相同結(jié)果。因此，s和t可以合并成一個(gè)狀態(tài)。 最小化最小化DFA的實(shí)質(zhì)的實(shí)質(zhì)：在狀態(tài)集S上找到一個(gè)基于不可區(qū)分基于不可區(qū)分的等價(jià)關(guān)系R，S/R即是最小DFA的狀態(tài)集。522.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器算法算法2.6 最小化DFA的狀態(tài)數(shù)輸入DFA D=S，move，s0，F(xiàn)。輸出等價(jià)的D=S，move，s0，F(xiàn)(D狀態(tài)數(shù)最少狀態(tài)數(shù)最少)方法執(zhí)行如下步驟：1. 初始劃分=S-F，F(xiàn)1，F(xiàn)2，.，其中，F(xiàn)i是F的子集，接受不同記號(hào)；2.

41、應(yīng)用下述過(guò)程構(gòu)造新的劃分new：for 的每一個(gè)組G loop劃分G，G的兩個(gè)狀態(tài)s和t在同一組中的充要條件是: a.(move(s,a)Gimove(t,a)Gi)；用新劃分的組替代G，形成新的劃分new； end loop；3.若 new= 則final:=且轉(zhuǎn)4； 否則=:new且轉(zhuǎn)2；532.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器4. 在final每個(gè)組Gi中選一個(gè)代表si，使得D中從Gi所有狀態(tài)出發(fā)的狀態(tài)轉(zhuǎn)移在D中均從si出發(fā)，D中所有轉(zhuǎn)向Gi中的狀態(tài)轉(zhuǎn)移在D中均轉(zhuǎn)向si。含有D中s0的狀態(tài)組G0的代表s0稱為D的初態(tài)的初態(tài)，D中所有含F(xiàn)中狀態(tài)的Gj的代表sj構(gòu)成D的終態(tài)集的終

42、態(tài)集F； 5. 刪除死狀態(tài)，即不是終態(tài)且對(duì)所有輸入字符均轉(zhuǎn)向其自身，或從初態(tài)不可到達(dá)的狀態(tài)。最小化最小化DFA算法的主要步驟算法的主要步驟F初始劃分：終態(tài)與非終態(tài)；F利用可區(qū)分的概念，反復(fù)分裂劃分中的組Gi，直到不可再分裂；F由最終劃分構(gòu)造D，關(guān)鍵是選代表和修改狀態(tài)轉(zhuǎn)移；1.消除可能的死狀態(tài)和不可達(dá)狀態(tài)。542.4 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器例2.17 用算法2.6化簡(jiǎn)DFA1初始化劃分1=ABCD，E2反復(fù)分裂劃分中的組： m(D, b)=E 2=ABC，D，E m(B, b)=D 3=AC，B，D，E 3？ 于是：final=AC，B，D，E 4根據(jù)final構(gòu)造D： 選代表，用A代表AC組； 修改狀態(tài)轉(zhuǎn)移：用0123代替ABDEm(A,a)=B, m(A,b)=Cm(B,a)=B, m(B,b)=Dm(C,a)=B, m(C,b)=Cm(D,a)=B, m(