編譯原理王曉斌編譯第八章

1、第八章 詞法分析第一節(jié) 詞法分析概述一. 詞法分析的功能1. 功能 掃描源程序的字符串,按照詞法規(guī)則,識(shí)別出單詞符號(hào)作為輸出;對(duì)識(shí)別過程中發(fā)現(xiàn)的詞法錯(cuò)誤,則輸出有關(guān)的錯(cuò)誤信息。2. 詞法分析器和語法分析器的關(guān)系（1）詞法分析作為單獨(dú)的一遍輸入串詞法分析器語法分析器單詞流第八章 詞法分析（2）詞法分析作為子程序輸入串詞法分析器語法分析器符號(hào)表取下一單詞返回下一單詞第八章 詞法分析二. 詞法分析器的輸出形式1. 單詞的種類 (1)標(biāo)識(shí)符:用來命名程序中出現(xiàn)的變量、數(shù)組、函數(shù)、過程、標(biāo)號(hào)等 (2)基本字:也可稱關(guān)鍵字或保留字, 如if、while、for、do、goto等 (3)常數(shù):各種類型的常數(shù)

2、, 如216、3.14159、true等 (4)運(yùn)算符:如+、-、*、/等 (5)界符:如;、:、/*、*/等第八章 詞法分析2.單詞的輸出形式（1） 二元式 (單詞類別,單詞的屬性)區(qū)分單詞所屬的類(整數(shù)編碼) 單詞的值（2） 單詞類別的劃分u基本字、運(yùn)算符、界符:一字一碼u標(biāo)識(shí)符:單列一種u常數(shù):按類型分類一個(gè)例子：a:=b50+10； 的輸出為：（標(biāo)識(shí)符的編碼，a）（:=的編碼，）（標(biāo)識(shí)符的編碼，b50）（的編碼，）（整數(shù)的編碼，10）（；的編碼，）第二節(jié) 詞法分析器的結(jié)構(gòu)一. 掃描緩沖區(qū)1. 輸入緩沖區(qū)：源程序輸入緩沖區(qū)2. 預(yù)處理程序：取消注解，剔除無用的空白、跳格、回車、換行等3.

3、 掃描緩沖區(qū)：從輸入緩沖區(qū)輸入固定長(zhǎng)度的字符串到另一個(gè)緩沖區(qū)（掃描緩沖區(qū)），詞法分析可以直接在此緩沖區(qū)中進(jìn)行符號(hào)識(shí)別。其結(jié)構(gòu)為：左緩沖區(qū)右緩沖區(qū)起點(diǎn)指示器搜索指示器二. 符號(hào)的識(shí)別1. 詞法分析技術(shù)超前搜索 為了判定一個(gè)單詞符號(hào)的類別,必須掃描到某一地方,而該單詞符號(hào)并沒有這么長(zhǎng),這種掃描方式叫做“超前搜索”。（1）基本字的識(shí)別 do100i=1,10 do100i=1.10 if(5.eq.m)goto 100 if(5)=100（2）標(biāo)識(shí)符的識(shí)別：讀到非字母數(shù)字（3）常數(shù)的識(shí)別：根據(jù)常數(shù)的格式；大多數(shù)常數(shù)后都有運(yùn)算符或界符（4）運(yùn)算符的識(shí)別：需要超前搜索，如*（5）界符的識(shí)別：需要超前搜索

4、，如/*三. 詞法分析器的結(jié)構(gòu)預(yù)處理子程序詞法分析器輸入緩沖區(qū)掃描緩沖區(qū)單詞符號(hào)輸入第三節(jié) 狀態(tài)轉(zhuǎn)換圖一. 狀態(tài)轉(zhuǎn)換圖的定義u有限的有向圖u有向邊上標(biāo)記字符u唯一初態(tài)u若干終態(tài)（至少一個(gè)）123xy二. 狀態(tài)轉(zhuǎn)換圖識(shí)別的串 從初態(tài)出發(fā)到某一終態(tài)路徑上字符的連接。下圖是識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖：012字母其它字符字母或數(shù)字*第四節(jié) 詞法分析器的設(shè)計(jì)一. 單詞符號(hào) 第四章設(shè)計(jì)的語言允許下述單詞： 標(biāo)識(shí)符、數(shù)字串、begin、end、integer、if、 then、else、function、read、write、 、*、=、 =、=、:=、；、（、）單詞符號(hào)單詞符號(hào)類別編碼類別編碼助記符助記符標(biāo)識(shí)

5、符數(shù)字串beginendintegerifthenelse12345678$id$int$begin$end$integer$if$then$else單詞符號(hào)單詞符號(hào)類別編碼類別編碼助記符助記符functionreadwrite*=910111213141516$function$read$write$sub$mul$lt$le$ne單詞符號(hào)單詞符號(hào)類別編碼類別編碼助記符助記符=:=；（）17181920212223$eq$gt$ge$assign$sem$lpar$rpar04123567開始空白字母/數(shù)字字母非字母數(shù)字?jǐn)?shù)字非數(shù)字=-*數(shù)字二. 狀態(tài)轉(zhuǎn)換圖89()101112=1314151

6、6其它=171819：其它=其它2021；其它* 三. 實(shí)現(xiàn)方法 每個(gè)狀態(tài)結(jié)對(duì)應(yīng)一小段程序u分支狀態(tài)if或case語句u循環(huán)狀態(tài)while語句u終態(tài)return語句 四. 一個(gè)示意算法start: token:= ; getchar;getnb; case character of az: begin while letter or digit do begin concatenate;getchar end; retract; c:= reserve; if c = 0 then begin buildlist; return($id,val) end else return(c,) end

7、;09: begin while digit do begin concatenate;getchar end; retract; dtb; return($int,val) end; = : return($eq,); - : return($sub,); * : return($mul,); ( : return($lpar,); ) : return($rpar,); then return($ne, ); retract; return($lt, ) end; : begin getchar; if character = = then return($ge, ); retract;

8、return($gt, ) end; : : begin getchar; if character = = then return($assign,) else error end; ; : return($sem,)other: errorend of case;goto start;全局量及過程:(1)token：字符數(shù)組(2)character：字符變量(3)getchar：取一字符(4)getnb：讀到非空白字符(5)concatenate：連接(6)letter和digit：布爾函數(shù)(7)reserve：查保留字表(8)retract:退一字符;character置空 (9)bui

9、ldlist:將token中的標(biāo)識(shí)符存入符號(hào)表，并將其在符號(hào)表中的位置填入val (10)dtb:將token中的數(shù)字串轉(zhuǎn)換成二進(jìn)制，并存入常數(shù)表，位置填入val (11)val:存放標(biāo)識(shí)符在符號(hào)表中的位置，或常數(shù)在常數(shù)表中的位置 (12)return(c,val)：返回二元式 (13)error：出錯(cuò)處理第五節(jié) 符號(hào)表 在程序中,用戶用標(biāo)識(shí)符定義了不少名字來代表不同的數(shù)據(jù)對(duì)象,編譯程序?qū)⑦@些名字保存在符號(hào)表中。符號(hào)表除了記錄名字本身而外,還記錄了與名字關(guān)聯(lián)的各種屬性信息。一. 符號(hào)表的一般形式 每個(gè)名字對(duì)應(yīng)一個(gè)表項(xiàng),一個(gè)表項(xiàng)包括名字域和信息域。名字信息其中,信息域通常設(shè)若干子域及標(biāo)志位，其內(nèi)容可以是和名字有關(guān)的任何信息： 類型,種屬,長(zhǎng)度,相對(duì)地址,數(shù)組的內(nèi)情向量,記錄