1、第2章 詞法分析,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,2.1.1 單詞類型及二元式編碼 單詞類型 基本字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符 單詞的性質(zhì) 個(gè)數(shù)確定和不確定 單字符或多字符構(gòu)成,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,單詞二元式編碼 經(jīng)詞法分析后，單詞用二元式 (code,val) 表示。 code表示單詞的種別，用整數(shù)碼表示，在語法分析時(shí)使用。 val表示單詞的值，在本書中用字符串表示，在語義分析時(shí)使用。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,編碼原則 通常將標(biāo)識(shí)符歸為一種，常數(shù)按類型分種，基本字、運(yùn)算符及界符采用一符一種。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,實(shí)例-設(shè)有某一

2、程序設(shè)計(jì)語言，其部分單詞二元式編碼如下所示：,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,用該程序設(shè)計(jì)語言編制的計(jì)算園柱體表面積的源程序（輸入輸出略）如下所示： Begin/*S=2*3.14* R* R +2*3.14* R*H */ Real r,h,s; s=2*3.14*r*(r+h) End,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,根據(jù)單詞二元式編碼，上述程序的單詞二元式序列應(yīng)為： (,NUL)(c,NUL)(i,r)(,NUL) (i,h) (,NUL)(i, s)(;,NUL)(i, s)(=,NUL) (x, 2)(*,NUL)(y, 3.1

3、4)(*,NUL) (i, r)(*,NUL) (,NUL)(i, r) (+,NUL)(i, h)(),NUL)(,NUL),2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,2.1.2 源程序的輸入及預(yù)處理 源程序的輸入 l 分段讀入處理（早期） l 全部讀入后處理 設(shè)源程序如下所示，其中為續(xù)行符。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,源程序讀入后，輸入緩沖區(qū)的內(nèi)容如下所示：,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,預(yù)處理 詞法分析器通常由二個(gè)部分構(gòu)成： 預(yù)處理程序 掃描器（單詞識(shí)別程序）,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,分成二部分的理由 詞法分析

4、可在輸入緩沖區(qū)上直接進(jìn)行，但從程序進(jìn)行的角度來講，若是把輸入串預(yù)處理一下，則單詞識(shí)別就會(huì)比較容易，故詞法分析器通常由預(yù)處理程序和掃描器（單詞識(shí)別程序）兩部分組成。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,預(yù)處理主要工作 1.刪除注釋 2.刪除續(xù)行符以及后續(xù)換行符（0AH） 3.Tab的作用相當(dāng)于多個(gè)空格，換行符、Tab和空格具有界符作用，預(yù)處理時(shí)通常予以保留。在后面的分析中可以看到，它們的存在給后續(xù)的單詞識(shí)別帶來方便。為了簡(jiǎn)化判斷，可在預(yù)處理時(shí)將換行符和Tab統(tǒng)一替換為空格。 4.大多數(shù)語言（除C語言外）不區(qū)分大小寫，可在預(yù)處理時(shí)大寫字母變換成小寫字母，或相反，以方便后續(xù)處理。 5.對(duì)于受書寫

5、格式限制的語言（如FORTRAN和COBOL），還應(yīng)識(shí)別標(biāo)號(hào)區(qū)，正確給出語句標(biāo)號(hào)；識(shí)別續(xù)行標(biāo)志，把相繼行連接在一起，給出語句結(jié)束符。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,上述源程序經(jīng)預(yù)處理后，掃描緩沖區(qū)中的內(nèi)容如下所示：,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,預(yù)處理程序 下面用C/C+語言來編寫一個(gè)預(yù)處理程序，其作用是去除源程序中的注釋和續(xù)行符，將Tab和換行符替換為空格，將大寫字母變換成小寫字母。每調(diào)用一次，將經(jīng)預(yù)處理的源程序全部送入內(nèi)存中的掃描緩沖區(qū)，供掃描區(qū)識(shí)別單詞。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,程序?qū)崿F(xiàn)，由兩個(gè)函數(shù)構(gòu)成： 主函數(shù)main是測(cè)試驅(qū)動(dòng)程序，調(diào)用預(yù)處理函數(shù)p

6、ro_process，模擬詞法分析器工作； 函數(shù)pro_process執(zhí)行預(yù)處理任務(wù)，借助于傳地址獲得掃描緩沖區(qū)的首址，將經(jīng)預(yù)處理的源程序送入掃描緩沖區(qū)。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,由于算法需要，在源程序尾部添加字符#，這是一個(gè)特殊的單詞，表示源程序的結(jié)束。 源程序中的注釋用/*.*/標(biāo)記，不允許嵌套使用，這和大多數(shù)高級(jí)語言的規(guī)定一致。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,源程序的輸入及預(yù)處理 #include #include void pro_process(char *); void main( )/測(cè)試驅(qū)動(dòng)程序 /定義掃描緩沖區(qū) char buf4048=0; /緩沖

7、區(qū)清0 /調(diào)用預(yù)處理程序 pro_process(buf); /在屏幕上顯示掃描緩沖區(qū)的內(nèi)容 coutbufendl; ,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,void pro_process(char *buf)/預(yù)處理程序 ifstream cinf(source.txt,ios:in); int i=0; /計(jì)數(shù)器 char old_c=0,cur_c; /前一個(gè)字符，當(dāng)前字符。 bool in_comment=false;/false表示當(dāng)前字符未處于注釋中。 while(cinf.read(/在源程序尾部添加字符# ,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,while(cinf.r

8、ead( /保留前一個(gè)字符 /end of while,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,數(shù)據(jù)說明 source.txt（源程序文件） char buf（掃描緩沖區(qū)） bool in_comment（狀態(tài)標(biāo)志） 若in_comment的值為false，表示當(dāng)前從文件讀入的字符未處于注釋中，此時(shí)應(yīng)將讀入的字符存入掃描區(qū)；若in_comment的值為ture，則表示當(dāng)前讀入的字符處于注釋中，此時(shí)讀入的字符應(yīng)丟棄。 XXXXX/*XXXXX*/XXXXX f .f/t. t/f f 當(dāng)讀入“/*”時(shí)，布爾變量in_comment的值由false變?yōu)閠rue；當(dāng)讀入“*/”時(shí)，布爾變量in_co

9、mment的值由ture變?yōu)閒alse。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,上機(jī)練習(xí) 用高級(jí)語言編寫一詞法分析預(yù)處理程序。從文件讀入源程序，去除源程序中的注釋（注釋用標(biāo)記），用空格取代源程序中的Tab和換行符，將預(yù)處理結(jié)果顯示在屏幕上。源程序中無續(xù)行符，字母無須處理，源程序尾部需要添加字符。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,2.1.3 基本字的識(shí)別和超前搜索 程序設(shè)計(jì)語言單詞以基本字識(shí)別最為困難，原因如下： 有些語言對(duì)基本字不加保護(hù)，用戶可用作普通標(biāo)識(shí)符。 基本字、用戶定義的標(biāo)識(shí)符和常數(shù)之間沒有分隔符。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,解決辦法： 所有基本字均為保留字(R

10、eserved word)，用戶不得使用它們作為標(biāo)識(shí)符。 將空格、TAB和換行符視為界符。在基本字、用戶定義的標(biāo)識(shí)符和常數(shù)之間，若沒有運(yùn)算符或界符，則至少用一個(gè)空格（或TAB、換行符）加以分隔。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,遍的基本概念 由外存獲得前一遍的工作結(jié)果，完成后把結(jié)果存于外設(shè)。 遍引入的歷史背景 早期內(nèi)存較小，編譯程序相對(duì)較大 遍和編譯程序的結(jié)構(gòu) 1.一遍工作后，內(nèi)存大部分釋放，下一遍后，可以使用全部存儲(chǔ)空間 2.使得編譯程序的邏輯結(jié)構(gòu)比較清晰 3.但增加了輸入輸出所耗費(fèi)時(shí)間,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,2.1.5 狀態(tài)轉(zhuǎn)換圖和詞法分析器的手工構(gòu)造 引入狀態(tài)轉(zhuǎn)

11、換圖的必要性 程序設(shè)計(jì)語言的無符號(hào)實(shí)型常數(shù)有三種書寫形式： 無小數(shù)部分形式：134 無整數(shù)部分形式：.12 完全形式：3.14 直接編寫識(shí)別程序有難度，使用狀態(tài)轉(zhuǎn)換圖是構(gòu)造單詞識(shí)別程序的好途徑。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,狀態(tài)轉(zhuǎn)換圖基本概念及應(yīng)用 狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖。 在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。 狀態(tài)之間用箭弧連接 箭弧上的標(biāo)記代表在射出結(jié)點(diǎn)狀態(tài)下可能出現(xiàn)的合法的輸入字符,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,例1，識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖如下所示：,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,例2，識(shí)別實(shí)常數(shù)和整常數(shù)的狀態(tài)轉(zhuǎn)換圖,2.1 詞法分析器的設(shè)計(jì)考慮及手

12、工構(gòu)造,例3，識(shí)別#、+和+的狀態(tài)轉(zhuǎn)換圖,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,利用狀態(tài)轉(zhuǎn)換圖識(shí)別單詞 狀態(tài)轉(zhuǎn)換圖每次只能識(shí)別一個(gè)單詞，若源程序中有N個(gè)單詞，則需使用狀態(tài)轉(zhuǎn)換圖N次。設(shè)源程序?yàn)閤+y#（#是預(yù)處理程序添加的），單詞識(shí)別程序（掃描器）共使用狀態(tài)轉(zhuǎn)換圖5次。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,1.從初態(tài)0出發(fā)，讀入x進(jìn)入狀態(tài)1，在狀態(tài)1讀入+，進(jìn)入終態(tài)2，識(shí)別出標(biāo)識(shí)符x，退回+； 2. 從初態(tài)0出發(fā)，讀入+進(jìn)入狀態(tài)10，在狀態(tài)10讀入+，進(jìn)入終態(tài)11，識(shí)別出運(yùn)算符+；,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,3. 從初態(tài)0出發(fā)，讀入+進(jìn)入狀態(tài)10，在狀態(tài)10讀入y，進(jìn)入終態(tài)

13、12，識(shí)別出運(yùn)算符+，退回y； 4. 從初態(tài)0出發(fā)，讀入y進(jìn)入狀態(tài)1，在狀態(tài)1讀入#，進(jìn)入終態(tài)2，識(shí)別出標(biāo)識(shí)符y，退回#；,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,5.從初態(tài)0出發(fā)，讀入#進(jìn)入狀態(tài)13，識(shí)別出單詞“#”，識(shí)別出單詞“#”意味著整個(gè)源程序中字符處理完畢。 為什么在C語言中x+y解釋為(x+)+y,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,根據(jù)狀態(tài)轉(zhuǎn)換圖編制程序 （見“識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖編制的掃描程序”WORD文件）,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,詞法分析器手工構(gòu)造實(shí)例 1.字符集 a.z 0.9 + = * ，； （ ） # 發(fā)現(xiàn)集合以外的字符，即非法字符，應(yīng)終止詞法

14、分析器,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,詞法分析器手工構(gòu)造實(shí)例 2.單詞集 基本字：begin,end,integer,real 標(biāo)識(shí)符：以字母開始的數(shù)字字母串 無符號(hào)整常數(shù) 無符號(hào)實(shí)常數(shù) 運(yùn)算符 + * + = 界符 ， ； （ ） # 錯(cuò)誤形式 . 前后無數(shù)字字符的小數(shù)點(diǎn) 出現(xiàn)錯(cuò)誤形式，終止詞法分析器運(yùn)行,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,詞法分析器手工構(gòu)造實(shí)例 3.單詞編碼 基本字：begin(,NUL),end(,NUL),integer(a,NUL),real(c,NUL) 標(biāo)識(shí)符(i,字符串) 無符號(hào)整常數(shù)(x,字符串) 無符號(hào)實(shí)常數(shù)(y,字符串) 運(yùn)算符 +(+,N

15、UL) *(*,NUL) +($,NUL) =(=,NUL) 界符 , (,NUL) ; (;,NUL) ( (,NUL) ) (),NUL) # (#,NUL),2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,詞法分析器手工構(gòu)造實(shí)例 4.狀態(tài)轉(zhuǎn)換圖 對(duì)單字符單詞可以不畫狀態(tài)轉(zhuǎn)換圖， 多字符單詞需要畫出狀態(tài)轉(zhuǎn)換圖,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,詞法分析器手工構(gòu)造實(shí)例 5.程序?qū)崿F(xiàn) 詞法分析器由5個(gè)函數(shù)構(gòu)成： 主函數(shù)main 預(yù)處理函數(shù)pro_process 掃描函數(shù)scanner 拼接函數(shù)concat 查基本字表函數(shù)reserve,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,主函數(shù)先調(diào)用預(yù)處理函

16、數(shù)進(jìn)行預(yù)處理，然后不斷調(diào)用掃描函數(shù)，獲得單詞二元式編碼，然后將輸出到文件Lex_r.txt，直到源程序全部處理完成。,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,void main() char buf4048=0;/掃描緩沖區(qū) pro_process(buf); /預(yù)處理 coutbufendl; /顯示buf ofstream coutf(Lex_r.txt,ios:out); /單詞識(shí)別 code_val t;/臨時(shí)變量 dot=scanner(buf);/調(diào)用一次掃描器獲得一個(gè)單詞二元式 coutt.codett.valendl;/屏幕顯示單詞二元式 coutft.codett.valen

17、dl;/單詞二元式輸出至文件 while(t.code!=#); coutEnd of lexical analysis!endl; getch(); ,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,掃描函數(shù)scanner中調(diào)用： 拼接函數(shù)concat和查基本字表函數(shù)reserve,2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造,上機(jī)練習(xí) 請(qǐng)手工構(gòu)造一個(gè)詞法分析器，要求： 1.從文件讀入源程序 2.去除源程序中的注釋（注釋用標(biāo)記） 3.用空格取代源程序中的Tab和換行符 4.將預(yù)處理結(jié)果顯示在屏幕上。 5.源程序尾部需要添加字符。 6.識(shí)別以下單詞，并轉(zhuǎn)換成二元式： 基本字begin(a,NUL),end(

18、b,NUL),integer(c,NUL),real(d,NUL) 標(biāo)識(shí)符(z,字符串) 無符號(hào)整常數(shù)(x,字符串) 無符號(hào)實(shí)常數(shù)(y,字符串) 運(yùn)算符 +(+,NUL) *(*,NUL) +(,NUL) =(=,NUL) 界符 , (,NUL) ; (;,NUL) ( (,NUL) ) (),NUL) # (#,NUL),2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,2.2.1 基本概念 有窮字母表 設(shè)是一個(gè)有窮字母表，它的每個(gè)元素稱為字符。即符號(hào)的非空有限集 例：=a，b，c 符號(hào)：字母表中的元素 例： a，b，c 符號(hào)串：符號(hào)的有窮序列 例：a, aa, ac, abc，. 空字 空集 ,

19、2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,字（符號(hào)串）:上字符所構(gòu)成的有限序列。 空字：不包含任何字符的字， *： 上所有字的全體。空字屬于*,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,符號(hào)串和符號(hào)串集合的運(yùn)算 1.符號(hào)串相等：若x、y是集合上的兩個(gè)符號(hào)串，則xy iff（當(dāng)且僅當(dāng)）組成x的每一個(gè)符號(hào)和組成y的每一個(gè)符號(hào)依次相等。 2.符號(hào)串的長(zhǎng)度：x為符號(hào)串，其長(zhǎng)度|x|等于組成該符號(hào)串的符號(hào)個(gè)數(shù)。 例： xSTV ， |x|=3,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,3.符號(hào)串的聯(lián)接： 若x、y是定義在是上的符號(hào)串，且xXY，yYX，則x和y的聯(lián)接 xyXYYX也是上的符號(hào)串。

20、注意：一般xyyx，而xx,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,符號(hào)串集合的乘積運(yùn)算： 令A(yù)、B為符號(hào)串集合，定義 AB xy |xA,yB,ac，ad，bc，bd 因?yàn)閤xx，所以A=A=A,例：Aa,b,B=c,d, AB= ？,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,5. 符號(hào)串集合的冪運(yùn)算： 有符號(hào)串集合A，定義 A0 = A1=A A2=AA A3=AAA AnAn-1A=AAn-1 ，n0,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,6.符號(hào)串集合的閉包運(yùn)算：設(shè)A是符號(hào)串集合，定義 A A1 A2 A3 An 稱為集合A的正閉包。 A* A0 A稱為集合A的閉包。,例：

21、A=x,y A？ A* ？,x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A1 A2 A3 , x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, A0 A1 A2 A3,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,為什么對(duì)符號(hào)、符號(hào)串、符號(hào)串集合以及它們的運(yùn)算感興趣？ 若A為某語言的基本字符集 Aa,b,z,0,1,9, +,_/, ( , ), = B為單詞集 B =begin, end, if, then,else,for, 則B A* 。 語言的句子是定義在B上的符號(hào)串。 若令C為句子集合，則C B * , 程序 C,2.2正規(guī)式、自動(dòng)機(jī)及

22、詞法分析器的自動(dòng)生成,2.2.2 正規(guī)式與正規(guī)集 正規(guī)式和正規(guī)集的定義： l和是上的正規(guī)式，相應(yīng)的正規(guī)集為、。 l 若a，則a是正規(guī)式，相應(yīng)正規(guī)集為a。 l若、為正規(guī)式，相應(yīng)正規(guī)集分別記為L(zhǎng)()和L()，則|是正規(guī)式，其相應(yīng)正規(guī)集記為L(zhǎng)(|) ，且令L(|)=L()L(),2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,l若、為正規(guī)式，相應(yīng)正規(guī)集分別記為L(zhǎng)()和L()，則(或)是正規(guī)式，其相應(yīng)正規(guī)集記為L(zhǎng)()，且令L()=L()L()。正規(guī)式自身的n次積是正規(guī)式，記為n，其相應(yīng)正規(guī)集記為L(zhǎng)(n)，顯然L(n)= L() n。 l 若為正規(guī)式，相應(yīng)正規(guī)集記為L(zhǎng)()，則*= 0|1|2|n是正規(guī)式，規(guī)

23、定0 =，其相應(yīng)正規(guī)集記為L(zhǎng)(*)，且令L(*) =L() *。 l *，可用園括號(hào)改變運(yùn)算順序。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,正規(guī)式有3個(gè)運(yùn)算符： |或，連接，*閉包。 優(yōu)先級(jí)依次為：*， ，|。 連接可以省略。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,為什么要定義所謂的正規(guī)集和正規(guī)式 有窮字母表是程序設(shè)計(jì)語言所使用的字符集的抽象 正規(guī)集是程序設(shè)計(jì)語言單詞集的抽象 正規(guī)式是程序設(shè)計(jì)語言構(gòu)詞規(guī)則的抽象 詞法分析器自動(dòng)構(gòu)造的輸入正是描述單詞的正規(guī)式 Abcdefdog,godn:dog,god,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,正規(guī)式相等原理 二個(gè)正規(guī)式是相等的，當(dāng)

24、且僅當(dāng)二個(gè)正規(guī)式所表示的正規(guī)集是相等的。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,正規(guī)式滿足下列關(guān)系 交換律：| = | 結(jié)合律：|(|) = (|)|，() = () 分配律：(|) = |，(|) = | = = ,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,正規(guī)式，其中=a|b|z, =0|1|9 1.(| ) * 2. * 3. *. * . * *. *(E|e)(+|-| ) . * . *(E|e)(+|-| ) . * * (E|e)(+|-| ) . * 4.(0|1)(0|1) *,標(biāo)識(shí)符,無符號(hào)整常數(shù),無符號(hào)實(shí)常數(shù),二進(jìn)制數(shù),2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成

25、,2.2.3 確定有限自動(dòng)機(jī)（DFA） 形式化狀態(tài)轉(zhuǎn)換圖 DFA定義 一個(gè)確定有限自動(dòng)機(jī)M是一個(gè)五元式 M = ( S，f，s0，Z ) l S是一個(gè)有限集，它的每一個(gè)元素稱為狀態(tài)。 l 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符。 l f是一個(gè)從S至S的映照，即， f：SS（單值函數(shù)）,有限自動(dòng)機(jī)：一種識(shí)別器，準(zhǔn)確識(shí)別正規(guī)集，是詞法分析器自動(dòng)構(gòu)造所需要的特殊方法和工具。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,例f (si,a) = sj，表示當(dāng)現(xiàn)行狀態(tài)為si，若輸入字符為a，則轉(zhuǎn)移到下一狀態(tài)sj，sj稱為si的后繼狀態(tài)。 l s0S，是唯一的一個(gè)初態(tài)。 l ZS，是一個(gè)終態(tài)集。,2

26、.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,狀態(tài)轉(zhuǎn)換矩陣 函數(shù)f可以使用矩陣表示，行表示狀態(tài)，列表示輸入字符，矩陣元素表示下一個(gè)狀態(tài)。 只要對(duì)初態(tài)和終態(tài)做標(biāo)記，就可以用一個(gè)狀態(tài)轉(zhuǎn)換矩陣來表示DFA,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,DFA M也可用一個(gè)（確定的）狀態(tài)轉(zhuǎn)換圖表示 假定DFA M含有m個(gè)狀態(tài)和n個(gè)輸入字符，那這個(gè)圖含有m個(gè)狀態(tài)結(jié)，每個(gè)狀態(tài)結(jié)最多有n條箭弧射出和其他狀態(tài)相連接，包括該狀態(tài)本身。每條弧用中的一個(gè)不同輸入字符做標(biāo)記，整個(gè)圖含有唯一一個(gè)初態(tài)和若干個(gè)終態(tài)。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,字可為DFA M識(shí)別 對(duì)于一個(gè)字，如果存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的

27、路徑，且路徑上的所有弧的標(biāo)記按照順序連接成的字為，則稱可為DFA M識(shí)別或接受。 若DFA M的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則稱空字可為DFA M所識(shí)別或接受。 DFA M所識(shí)別的字的全體稱為L(zhǎng)（M）,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,DFA的確定性 表現(xiàn)在映射SS是一個(gè)單值函數(shù)。即對(duì)任何狀態(tài) sS和輸入符號(hào)a ，f(s,a)唯一確定下一個(gè)狀態(tài)。 從狀態(tài)轉(zhuǎn)換圖來看，假定字母表含有n個(gè)輸入字符，那么一個(gè)狀態(tài)最多只有n條弧射出，并且每條弧以不同的輸入字符為標(biāo)記。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,2.2.4 非確定有限自動(dòng)機(jī)（NFA） f是一個(gè)多值函數(shù)，得到NFA 定義 一個(gè)非確定的

28、有限自動(dòng)機(jī)M是一個(gè)五元式 M=（S，f，S0，Z） lS是一個(gè)有限集，它的每一個(gè)元素稱為狀態(tài)。 l是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,l f是一個(gè)從S*到S的子集影射，即， f：S*2S（多值函數(shù)） 2S表示冪集，若S=0，1，則2S =，0，1，0，1。 l S0S，是一個(gè)非空初態(tài)集，即NFA的初態(tài)不一定唯一。 lZS，是一個(gè)終態(tài)集。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,NFA M可用一個(gè)（非確定的）狀態(tài)轉(zhuǎn)換圖表示 一個(gè)含有m個(gè)狀態(tài)和n個(gè)輸入字符的NFA可唯一表示成一個(gè)（非確定的）狀態(tài)轉(zhuǎn)換圖，這個(gè)圖含有m個(gè)狀態(tài)結(jié)，每個(gè)結(jié)可射出若干個(gè)箭弧與別的結(jié)相連接，每條弧用*中的一個(gè)字做標(biāo)記（輸入字），不一定要不同的字，還可以是空字。 一個(gè)DFA可以含有多個(gè)初態(tài)結(jié)，初態(tài)結(jié)同時(shí)也可以是終態(tài)結(jié)。,2.2正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成,字可為NFA M識(shí)別 對(duì)于*中一個(gè)