第三章有限自動(dòng)機(jī)和詞法分析器

1、主要內(nèi)容：主要內(nèi)容：l 詞法分析過程涉及的幾個(gè)問題詞法分析過程涉及的幾個(gè)問題l 詞法分析器的生成技術(shù)詞法分析器的生成技術(shù) 正則表達(dá)式正則表達(dá)式 有限自動(dòng)機(jī)有限自動(dòng)機(jī)l 有關(guān)詞法分析器的幾個(gè)問題和處理方法：有關(guān)詞法分析器的幾個(gè)問題和處理方法： 詞法分析器的功能、分類詞法分析器的功能、分類 單詞的分類、單詞的分類、Token表示表示 保留字保留字 空格符、制表符和換行符空格符、制表符和換行符 復(fù)合型符號(hào)復(fù)合型符號(hào) 括號(hào)類匹配預(yù)檢括號(hào)類匹配預(yù)檢 字符串空間字符串空間 詞法錯(cuò)誤校正詞法錯(cuò)誤校正 詞法分析結(jié)束詞法分析結(jié)束l詞法分析器功能：詞法分析器功能：l 讀源程序的字符序列讀源程序的字符序列, ,逐個(gè)

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

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

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

5、,$id,標(biāo)識(shí)符）如標(biāo)識(shí)符）如($($id,x)id,x)l整常數(shù)的整常數(shù)的Token: ($Token: ($intCintC, ,整常數(shù)）如整常數(shù)）如 （$ $intC,5)intC,5)l實(shí)常數(shù)的實(shí)常數(shù)的Token: ($Token: ($realCrealC, ,實(shí)常數(shù)）如實(shí)常數(shù)）如 $ $realC,0.5)realC,0.5)l保留字的保留字的Token: ($begin,-),($end,-)Token: ($begin,-),($end,-)l符號(hào)詞的符號(hào)詞的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; 經(jīng)詞法分析器處理后，它將轉(zhuǎn)換為如下的經(jīng)詞法分析器處理后，它將轉(zhuǎn)換為如下的 TokenToken序列：序列：v標(biāo)識(shí)符和常量的處理標(biāo)識(shí)符和常量的處理： 詞法信息可確定，語義信息形式的確定詞法信息可確定，語義信息形式的確定： a a

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

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

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