有窮自動機與詞法分析器

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

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

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

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

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

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

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

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

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

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

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