第三章有限自動機和詞法分析器

1、主要內容：主要內容：l 詞法分析過程涉及的幾個問題詞法分析過程涉及的幾個問題l 詞法分析器的生成技術詞法分析器的生成技術 正則表達式正則表達式 有限自動機有限自動機l 有關詞法分析器的幾個問題和處理方法：有關詞法分析器的幾個問題和處理方法： 詞法分析器的功能、分類詞法分析器的功能、分類 單詞的分類、單詞的分類、Token表示表示 保留字保留字 空格符、制表符和換行符空格符、制表符和換行符 復合型符號復合型符號 括號類匹配預檢括號類匹配預檢 字符串空間字符串空間 詞法錯誤校正詞法錯誤校正 詞法分析結束詞法分析結束l詞法分析器功能：詞法分析器功能：l 讀源程序的字符序列讀源程序的字符序列, ,逐個

2、拼出單詞逐個拼出單詞, ,并并構造相應的內部表示構造相應的內部表示TOKEN.TOKEN.同時檢查源程序同時檢查源程序中的詞法錯誤中的詞法錯誤. .l引入引入TokenToken的原因：的原因：l 編譯程序總是用某種程序語言書寫的程編譯程序總是用某種程序語言書寫的程序，語言的操作對象只能是該語言規(guī)定的各序，語言的操作對象只能是該語言規(guī)定的各種數(shù)據(jù)。而編譯程序的操作對象是程序中的種數(shù)據(jù)。而編譯程序的操作對象是程序中的各種語法單位，因此，必須把它們表示成某各種語法單位，因此，必須把它們表示成某種數(shù)據(jù)結構形式。種數(shù)據(jù)結構形式。 CharList 獨獨 立立詞法分析器詞法分析器語法分析語法分析Toke

3、nList 附附 屬屬詞法分析器詞法分析器語法分析語法分析callTokenCharListlTokenToken表示最小的語義單位表示最小的語義單位- - -單詞的信息。單詞的信息。即單詞內部表示的數(shù)據(jù)結構形式。即單詞內部表示的數(shù)據(jù)結構形式。 單詞不是程序設計語言中的語法概念，是編譯程單詞不是程序設計語言中的語法概念，是編譯程序中引進的一個概念。是最小的語義單位，不能序中引進的一個概念。是最小的語義單位，不能分割分割lTokenToken中需要記錄有關單詞的信息：中需要記錄有關單詞的信息： 單詞的標志碼單詞的標志碼($($id,$intCid,$intC, ,) )標識單詞的種類標識單詞的種

4、類-詞法信息詞法信息 單詞的特征屬性（標識符名，符號表地址等）單詞的特征屬性（標識符名，符號表地址等） - - -語義信息語義信息l標識符：字母打頭的字母標識符：字母打頭的字母/ /數(shù)字串數(shù)字串l整常數(shù)：數(shù)字打頭的數(shù)字串整常數(shù)：數(shù)字打頭的數(shù)字串l實常數(shù)：整數(shù)實常數(shù)：整數(shù). .整數(shù)整數(shù)l保留字：保留字：beginbegin，endend，varvar，readread，writewrite，integerinteger，realreall符號符號 ：+ +，* *，( (，) )，: :，:=:=，; ;l控制控制 ： ( (換行符）換行符）l標識符的標識符的TokenToken: : （$id

5、,$id,標識符）如標識符）如($($id,x)id,x)l整常數(shù)的整常數(shù)的Token: ($Token: ($intCintC, ,整常數(shù)）如整常數(shù)）如 （$ $intC,5)intC,5)l實常數(shù)的實常數(shù)的Token: ($Token: ($realCrealC, ,實常數(shù)）如實常數(shù)）如 $ $realC,0.5)realC,0.5)l保留字的保留字的Token: ($begin,-),($end,-)Token: ($begin,-),($end,-)l符號詞的符號詞的Token: ($plus,-),($Token: ($plus,-),($multmult,-),-), ($ ($L

6、parenLparen,-),-)l換行符的換行符的Token: ($line,-)Token: ($line,-) ($begin,-) ($var,-) ($id, x) ($colon,-) ($real,-) ($semi,-) l例如下述例如下述MicroMicro的代碼：的代碼： begin begin varvar x : real; x : real; 經詞法分析器處理后，它將轉換為如下的經詞法分析器處理后，它將轉換為如下的 TokenToken序列：序列：v標識符和常量的處理標識符和常量的處理： 詞法信息可確定，語義信息形式的確定詞法信息可確定，語義信息形式的確定： a a

7、語義信息的長度有限制時，直接用語義信息的長度有限制時，直接用 標識符或常量本身標識符或常量本身 b b 沒有長度限制時，構造標識符或常沒有長度限制時，構造標識符或常 量表，語義信息中為其在表中的地量表，語義信息中為其在表中的地 址（字符串空間址（字符串空間節(jié)省存貯空間）節(jié)省存貯空間）v保留字的處理保留字的處理：識別保留字的方法：識別保留字的方法： 1.建立保留字表；順序、散列、散列順序建立保留字表；順序、散列、散列順序 2.拼寫的同時進行判斷拼寫的同時進行判斷 自動機自動機 v 運算符的處理運算符的處理： 不區(qū)分，統(tǒng)一成一類不區(qū)分，統(tǒng)一成一類 區(qū)分，每個運算符為一類區(qū)分，每個運算符為一類v 空

8、格符和制表符以及換行符的處理空格符和制表符以及換行符的處理 1.無用的空格符和制表符要刪掉；無用的空格符和制表符要刪掉； 2.字符串內的空格不能刪；字符串內的空格不能刪； 3.換行符不能刪。用于錯誤定位換行符不能刪。用于錯誤定位v 復合型特殊符，如復合型特殊符，如“:=”的處理的處理 讀到讀到“:”時不能判斷是否為冒號，必須讀下時不能判斷是否為冒號，必須讀下 一字符。一字符。v括號類配對預檢括號類配對預檢l括號類：括號類： begin begin end ,if end ,if then, , ,( ) then, , ,( )l處理方法：處理方法： 對每類括號設置一個計數(shù)器（初值對每類括號設

9、置一個計數(shù)器（初值=0=0） 每當遇到開括號，則計數(shù)器加每當遇到開括號，則計數(shù)器加1 1 每當遇到閉括號時，計數(shù)器減每當遇到閉括號時，計數(shù)器減1 1 詞法分析結束時，如果計數(shù)器詞法分析結束時，如果計數(shù)器 0 0，則，則 表明括號不匹配。表明括號不匹配。v字符串空間字符串空間l目的：減少冗余，節(jié)省空間，提高訪問速度目的：減少冗余，節(jié)省空間，提高訪問速度l方法：字符數(shù)組存放字符串，描述字符串信息：方法：字符數(shù)組存放字符串，描述字符串信息： 下標下標 長度長度 l詞法錯誤種類：詞法錯誤種類：l 語言不允許的符號：語言不允許的符號：# #l 括號類配對錯誤：括號類配對錯誤：l 單詞的后繼符錯（偶爾）：單詞的后繼符錯（偶爾）：l詞法錯誤校正：詞法錯誤校正：l a a 刪除已被讀過的字符，并重新掃刪除已被讀過的字符