有窮自動(dòng)機(jī)與詞法分析器

1、第三章 有窮自動(dòng)機(jī)與詞法分析器,任課教師王養(yǎng)廷,主要內(nèi)容,詞法分析有窮自動(dòng)機(jī),3.1 詞法分析,詞法分析功能源程序文件ASCII編碼文本文件例如：“A1”保存為4131單詞源程序的語法成分例如：if, (, …,3.1 詞法分析,詞法分析功能Token單詞的內(nèi)部表示，例如：,3.1 詞法分析,詞法分析功能標(biāo)識(shí)符用戶定義的符號(hào)作為一類來處理常量可以作為一類或多類保留字用來分隔語法成分一般每個(gè)一

2、類與保留字的區(qū)別（算法設(shè)計(jì)？）,3.1 詞法分析,詞法分析功能詞法分析輸入：源程序詞法分析輸出：Token序列詞法分析功能：把源程序轉(zhuǎn)換成Token序列詞法分析器種類作為語法分析的一個(gè)子程序，每次產(chǎn)生一個(gè)Token作為編譯器獨(dú)立的一遍、生成Token序列,3.1 詞法分析,詞法分析功能單詞識(shí)別從字符串中分離出單個(gè)單詞主要的單詞標(biāo)識(shí)符正整數(shù)保留字符號(hào)……,3.1 詞法分析,詞法分析功能詞法分析復(fù)雜性，

3、例子：DO 10 I = 1 , 100DO 10 I = 1. 100,3.1 詞法分析(續(xù)),單詞內(nèi)部表示標(biāo)識(shí)符的內(nèi)部表示指針方法其它符號(hào)的內(nèi)部表示為什么單獨(dú)處理標(biāo)識(shí)符,,,3.1 詞法分析(續(xù)),保留字什么識(shí)保留字分析保留子的方法保留字表，數(shù)據(jù)實(shí)現(xiàn)非保留字表，程序?qū)崿F(xiàn)空格、制表符、換行符它們可以作為分隔符有的語言空格符無詞法意義例如：下面兩行等價(jià)beginxbegin x字符串中

4、的空格需要單獨(dú)處理換行可以用于行計(jì)數(shù),3.1 詞法分析(續(xù)),括號(hào)類配對(duì)Pascal語言中的括號(hào)類begin ......endrecord......endif......then[......](......){......}檢查配對(duì)使用計(jì)數(shù)器更準(zhǔn)確地方法如何實(shí)現(xiàn)？,3.1 詞法分析(續(xù)),向前看多個(gè)字符詞法分析有時(shí)需要向前看多個(gè)字符，例如：1010.1210..12有時(shí)需要看到第一個(gè)‘.’后的字

5、符才能確定處理技術(shù)沿著收到的字符倒退到終態(tài)把回退字符集如緩沖區(qū)，以便下一次掃描引入Token標(biāo)志例如：12.3e+q的分析,3.1 詞法分析(續(xù)),字符串空間字符串的存儲(chǔ)問題一般方法使用緩沖區(qū)記錄開始地址和長(zhǎng)度注意檢查是否有重復(fù)存儲(chǔ)的字符串字符編碼問題,mart:,mask:,word:,3.1 詞法分析(續(xù)),詞法錯(cuò)誤校正目的：發(fā)現(xiàn)更多的錯(cuò)誤，分析繼續(xù)下去手段：刪去已讀過的字符刪去已讀過的第一個(gè)

6、字符特別注意越行字符串的處理,3.1 詞法分析(續(xù)),詞法分析結(jié)束使用程序結(jié)束標(biāo)志例如：Pascal中的end.使用文件結(jié)束標(biāo)志可以有效處理錯(cuò)誤程序,3.1 詞法分析(續(xù)),使用詞法分析的好處使語法分析與語義分析更簡(jiǎn)練便于使用自動(dòng)機(jī)理論描述有利于提高編譯器的效率有利于編譯器的移植,3.2 確定有窮自動(dòng)機(jī),說明有窮自動(dòng)機(jī)（FA）確定有窮自動(dòng)機(jī)（DFA）非確定有窮自動(dòng)機(jī)（NFA）,3.2 確定有窮自動(dòng)機(jī)（續(xù)）

7、,定義確定有窮自動(dòng)機(jī)（DFA）有以下幾個(gè)部分組成：符號(hào)集Σ（輸入符號(hào)集）;狀態(tài)集合SS={S0, S1, S2, S3... Sn};開始狀態(tài)： S0 ;轉(zhuǎn)換函數(shù)Φ：SS X Σ →SS;終止?fàn)顟B(tài)集：{Si1, Si2... Sik};其中Φ表示給定一個(gè)狀態(tài)和輸入字符就可以唯一確定下一個(gè)狀態(tài),3.2 確定有窮自動(dòng)機(jī)（續(xù)）,自動(dòng)機(jī)定義方式圖形法轉(zhuǎn)換表法函數(shù)法,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,DFA例子（函數(shù)法）符號(hào)

8、集Σ={0, 1, 2, ...... ,9};狀態(tài)集合SS={S0, S1};開始狀態(tài)： S0 ;轉(zhuǎn)換函數(shù)Φ：SS X Σ →SS; Φ(S0, d)= S1 , Φ(S1, d)= S1終止?fàn)顟B(tài)集：{S1};,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,DFA有向圖表示 狀態(tài) 開始狀態(tài) 轉(zhuǎn)換邊 接受（或終止）狀態(tài),,,3.2

9、確定有窮自動(dòng)機(jī)（續(xù)）,接受自動(dòng)機(jī)接受字符串作用？？,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,特殊例子,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,DFA舉例,,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,練習(xí)實(shí)數(shù)的DFA第二個(gè)位置上為2的所有正整數(shù)標(biāo)識(shí)符，由字母字符引導(dǎo)的數(shù)字、字母字符串。接受偶數(shù)個(gè)0的DFA接受奇數(shù)個(gè)1的DFA接受偶數(shù)個(gè)0和偶數(shù)個(gè)1的DFA,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,實(shí)數(shù)的DFA,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,第二個(gè)位置上為2

10、的正整數(shù)（包括一位）,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,思考將上題改成不包括一位，對(duì)應(yīng)的DFA是什么？,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,標(biāo)識(shí)符,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,思考:標(biāo)識(shí)符（帶下劃線）？,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,接受偶數(shù)個(gè)0,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,思考與練習(xí)奇數(shù)個(gè)0？偶數(shù)個(gè)0和偶數(shù)個(gè)1？,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,確定有窮自動(dòng)機(jī)狀態(tài)表狀態(tài)轉(zhuǎn)換可以使用函數(shù)來表示轉(zhuǎn)換函數(shù)Φ：SS X Σ →

11、SS;狀態(tài)轉(zhuǎn)換可以使用圖形來表示狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換還可以使用表來表示,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,狀態(tài)轉(zhuǎn)換表示例,1 確定有窮自動(dòng)機(jī)（續(xù)）,狀態(tài)表說明主要狀態(tài)：第一列輸入字符：第一行終結(jié)狀態(tài)：帶有*號(hào)每個(gè)單元的狀態(tài)表示某個(gè)狀態(tài)接受某個(gè)字符后的狀態(tài)狀態(tài)表便于機(jī)器處理,3.2 確定有窮自動(dòng)機(jī)（續(xù)）,有向圖與狀態(tài)表的區(qū)別DFA的兩種表示形式有向圖：直觀易于理解狀態(tài)表便于計(jì)算和處理便于計(jì)算機(jī)表示,總結(jié),內(nèi)容