編譯原理：第4章 詞法分析

1、第4章 詞法分析 詞法分析器 完成詞法分析任務(wù)的程序段；可作為獨(dú)立的程序；可作為獨(dú)立的子程序： 對(duì)源程序進(jìn)行掃描，從中識(shí)別各個(gè)單詞符號(hào)。輸出數(shù)對(duì)（單詞類別，單詞號(hào)值）單詞符號(hào) 程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法單位和最小語(yǔ)義單位單詞符號(hào)的種類： 關(guān)鍵字 用戶標(biāo)識(shí)符 常量 運(yùn)算符 分界符掃描程序的設(shè)計(jì) 狀態(tài)轉(zhuǎn)換圖4.4 詞法分析程序的直接分析方法由正規(guī)文法設(shè)計(jì)詞法分析程序正規(guī)文法FADFA最小化 例：用戶標(biāo)識(shí)符文法( l字母，d數(shù)字) GI: IlA | l AlA | dA | l | d4.4 詞法分析程序的直接分析方法由正規(guī)表達(dá)式設(shè)計(jì)詞法分析程序正規(guī)表達(dá)式NDFADFA最小化 例：用戶標(biāo)識(shí)符正規(guī)表達(dá)式

2、( l字母，d數(shù)字) l(l |d)* 詞法分析的主要任務(wù)是對(duì)源程序進(jìn)行掃描，從中識(shí)別出單詞，它是編譯過(guò)程的第一步，也是編譯過(guò)程中不可缺少的部分。本章介紹詞法分析程序的手工構(gòu)造和自動(dòng)構(gòu)造原理。 4.1 詞法分析概述 詞法分析的任務(wù)是：從左至右逐個(gè)字符地掃描源程序形式的字符流，將這些單個(gè)字符組合成一個(gè)個(gè)單詞符號(hào)，把作為字符串的源程序轉(zhuǎn)換成由單詞符號(hào)串組成的中間語(yǔ)言程序供語(yǔ)法分析使用。因此，詞法分析是編譯程序的基礎(chǔ)。把詞法分析從語(yǔ)法分析中獨(dú)立出來(lái)有下述優(yōu)點(diǎn)： 部分編譯時(shí)間花費(fèi)在掃描字符上。 單詞符號(hào)的語(yǔ)法可以用非常簡(jiǎn)單的文法加以描述。 對(duì)同一語(yǔ)言來(lái)說(shuō)，常有不同的表示方法。 高級(jí)語(yǔ)言時(shí)，需要考慮詞法

3、和語(yǔ)法兩方面的特性，若把兩者分開，有利于分別地研究它們?？梢园言~法分析程序作為獨(dú)立的一遍去編寫，它實(shí)現(xiàn)源程序的全部詞法分析工作，并把轉(zhuǎn)換后的內(nèi)部形式的源程序傳遞給語(yǔ)法分析程序。也可以把它設(shè)計(jì)成一個(gè)子程序 (如有圖所示)。4.2 單詞符號(hào)單詞符號(hào)是語(yǔ)言的基本符號(hào)，它具有獨(dú)立的意義且是不可再分的。程序語(yǔ)言中的大部分單詞符號(hào)都屬于下述幾類之一。 標(biāo)識(shí)符。用以表示各種名字，如變量名，過(guò)程名等等； 保留字（或鍵字）。如if，goto，begin，end等等，它實(shí)質(zhì)上是標(biāo)識(shí)符的一個(gè)子集。 整數(shù)。125，38，0，1等等； 單分界符。如，*，/，（，），；，等等； 復(fù)合分界符。如+，/*，+等等。例4.1

4、識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖如下左圖所示：其中0為初態(tài)，2為終態(tài)，它識(shí)別標(biāo)識(shí)符的過(guò)程為：從初態(tài)0開始，若輸入符號(hào)識(shí)一字母，則讀進(jìn)它，并轉(zhuǎn)到狀態(tài)1；在狀態(tài)1下，若下一個(gè)輸入符號(hào)是字母或數(shù)字則讀進(jìn)它，并重新進(jìn)入狀態(tài)1；重復(fù)這個(gè)過(guò)程，直至在狀態(tài)1下發(fā)現(xiàn)讀入的符號(hào)不再是字母或數(shù)字時(shí)(注意，此時(shí)該字符已被讀出)，就進(jìn)入狀態(tài)2。狀態(tài)2是終態(tài)，它意指至此已識(shí)別出一個(gè)標(biāo)識(shí)符，識(shí)別過(guò)程終止。若在狀態(tài)0下輸入符號(hào)不是字母，則意味著識(shí)別不出所給的輸入串是一個(gè)標(biāo)識(shí)符。4.3 掃描程序的設(shè)計(jì)下面用一個(gè)比較簡(jiǎn)單的語(yǔ)言作為例子來(lái)討論掃描程序的設(shè)計(jì)。假定該語(yǔ)言中有分界符或運(yùn)算符（如，*，/，（，），鍵字（如begin，abs，en

5、d），標(biāo)識(shí)符（非保留字）以及整數(shù)。至少要有一個(gè)空白符將相鄰的標(biāo)識(shí)符、整數(shù)和（或）鍵字隔開，但不能用空白符將符號(hào)中的相鄰字符分開。此外，注解是以符號(hào)/*開始，并以符號(hào)*/的第一次出現(xiàn)作為結(jié)束的。 掃描程序構(gòu)造每個(gè)單詞符號(hào)的內(nèi)部表示，這種表示通常是一個(gè)定長(zhǎng)的整數(shù)。編譯程序的其余部分將只加工這些定長(zhǎng)的整數(shù)。下表給出了這些符號(hào)的內(nèi)部表示。 例 4.3 對(duì)于程序段begin A+B*C/* Comment */ end掃描程序?qū)a(chǎn)生下面的結(jié)果：狀態(tài)轉(zhuǎn)換圖可用于識(shí)別符號(hào)串，而且使識(shí)別工作直觀化。因此我們先畫一個(gè)用于識(shí)別符號(hào)的轉(zhuǎn)換圖。 添加動(dòng)作后的狀態(tài)轉(zhuǎn)換圖: 根據(jù)轉(zhuǎn)換圖編寫出掃描程序。該程序有兩個(gè)參數(shù)：S

6、YN和SEM，其中，SYN表示所標(biāo)識(shí)的那個(gè)單詞符號(hào)的內(nèi)部表示；SEM是組成該符號(hào)的字符串。SYN和SEM可以是兩個(gè)全局量，它們的作用域即掃描程序本身以及所有調(diào)用它的地方。該過(guò)程使用了Case語(yǔ)句，它根據(jù)Char中字符的類型數(shù)進(jìn)行判斷處理。Procedure SCAN(SYN:integer;SEM:string); begin start:GETNB;Token:= ;Case Class of1:begin while Calss=1 do begin Token:=Token CAT Char; GETCHAR; end; SYN:=$INT; end;2:begin while clas

7、s=2 do begin Token:=Token CAT Char; GETCHAR; end;SYN:=$ID; LOOKUP(Token); if add0 then SYN:=add; end;3:begin Token:=Char;GETCHAR; if Char= * then begin h1:GETCHAR; h2:if Char*then go to h1; GETCHAR; if Char/ then goto h2; GETCHAR;goto start; end else SYN:=$SLASH end;4:begin LOOKUP(Token); SYN:=add;G

8、ETCHAR; end;other:begin ERROR;GETCHAR;goto start; end;end of case;SEM:=Token;end.4.4 標(biāo)識(shí)符的處理在詞法分析中，標(biāo)識(shí)符的處理比其它單詞的處理復(fù)雜得多，且涉及得面也很廣，因此，在編譯程序中，標(biāo)識(shí)符得處理占有極為重要得位置。標(biāo)識(shí)符得處理主要包括其語(yǔ)義表示、作用域處理、符號(hào)表構(gòu)造以及內(nèi)存單元分配等工作。標(biāo)識(shí)符處理得難易程度依賴于語(yǔ)言的數(shù)據(jù)結(jié)構(gòu)的復(fù)雜程度。一般，數(shù)據(jù)結(jié)構(gòu)越復(fù)雜，標(biāo)識(shí)符的處理也就越復(fù)雜。 4.4.1 類型的機(jī)內(nèi)表示所討論的PASCAL子集只有如下類型：整型 integer實(shí)型 real布爾型 boolea

9、n數(shù)組 arrayn1n2 of T;記錄 record id1:T1;idn:Tn end(j=1,2,n)其中n1,n2為整型數(shù)；T，T1為上述五種類型之一；idj(j=1,2,n)為標(biāo)識(shí)符。我們用一種稱之為類型信息表的表格TypeTab來(lái)登陸類型信息，它的每一項(xiàng)的結(jié)構(gòu)為： 其中Tclass用以指明類型的五種種類，即：這里，我們采用一種簡(jiǎn)化的數(shù)組信息表AinfTab，它的每一項(xiàng)的結(jié)構(gòu)為：簡(jiǎn)化的記錄信息表RinfTab中的每一項(xiàng)的結(jié)構(gòu)為：綜合上述內(nèi)容，類型的內(nèi)部表示可概括為： 設(shè)某記錄類型的RinfTab表如下：RinfTabrp: 用length(ftp)表示類型ftp的長(zhǎng)度，則有此外，我

10、們假定，integer,real,boolean作為標(biāo)準(zhǔn)類型，其內(nèi)部表示已預(yù)先存放在類型表TypeTab中，且其地址分別為itp,rtp和btp,并假定length(itp)=length(rtp)= length(btp)=1為直觀起見，總是用常數(shù)本身和標(biāo)識(shí)符本身代替它們?cè)谙鄳?yīng)表中的地址。4.4.2 標(biāo)識(shí)符的語(yǔ)義表示程序中標(biāo)識(shí)符的出現(xiàn)分為定義性出現(xiàn)和使用性出現(xiàn)兩大類，前者系指在說(shuō)明部分出現(xiàn)的標(biāo)識(shí)符，后者是指在語(yǔ)句部分出現(xiàn)的標(biāo)識(shí)符。 標(biāo)識(shí)符定義性部分確定定義性標(biāo)識(shí)符的語(yǔ)義，主要包括標(biāo)識(shí)符的種類，類型及地址等信息。在我們假定的語(yǔ)言中，標(biāo)識(shí)符的種類有：常量；類型；變量；過(guò)程或函數(shù)。標(biāo)識(shí)符語(yǔ)義字的一

11、種參考結(jié)構(gòu)為：其中class的具體結(jié)構(gòu)可考慮為：綜上所述，我們可得到如下形式的標(biāo)識(shí)符的語(yǔ)義字：4.4.3 符號(hào)表（標(biāo)識(shí)符表）符號(hào)表在編譯程序中具有十分重要的意義，它是編譯程序中不可缺少的部分。在編譯程序中，符號(hào)表用來(lái)存放在程序中出現(xiàn)的各種標(biāo)識(shí)符及其語(yǔ)義屬性。 標(biāo)識(shí)符表SymbTab的一般結(jié)構(gòu)如下所示：如前所述，在程序中，標(biāo)識(shí)符分為定義性出現(xiàn)和實(shí)用性出現(xiàn)兩大類。在我們假定的語(yǔ)言中，定義性標(biāo)識(shí)符的出現(xiàn)情況如下： CONST id=，id=; TYPE id=，id=; VAR id,id,，id,:T; id,id,，id,:T; PROCEDURE id(VAR id,，id:T;id,id:T

12、;PROCEDURE id();FUNCTION id():T):T; FUNCTION id(VAR id,，id:T;id,id:T;PROCEDURE id();FUNCTION id():T): T; RECORD id1:T1,idn:Tn END;標(biāo)識(shí)符的作用域由以下四種語(yǔ)法單位劃定： PROGRAMEND,程序段在其首部定義性出現(xiàn)的標(biāo)識(shí)符為全局量。 PROCEDUREEND；過(guò)程段 FUNCTIONEND；函數(shù)段在過(guò)程段和函數(shù)段中可包含形參、局部量和全局量。 RECORDEND；記錄類型域名的作用域是包含它的最小記錄類型。 4.4.4 標(biāo)識(shí)符處理的基本思想標(biāo)識(shí)符處理的基本思想是：

13、 每當(dāng)進(jìn)入新的一層時(shí)，記住本層標(biāo)識(shí)符表SympTab的初始地址； 當(dāng)遇到定義性標(biāo)識(shí)符時(shí)，構(gòu)造其語(yǔ)義字并去查本層的標(biāo)識(shí)符表。 當(dāng)編譯程序遇到使用性標(biāo)識(shí)符時(shí)，也要去查標(biāo)識(shí)符表，在標(biāo)識(shí)符表中必須已登記過(guò)此標(biāo)識(shí)符，否則會(huì)出現(xiàn)“此標(biāo)識(shí)符未定義”的錯(cuò)誤。 每當(dāng)結(jié)束（退出）一層的時(shí)，“刪除”本層的SymbTab表。4.5 設(shè)計(jì)詞法分析程序的直接方法在具體實(shí)現(xiàn)過(guò)程中，可把詞法分析設(shè)計(jì)成一個(gè)子程序，即在掃描源程序時(shí)，一旦識(shí)別出標(biāo)識(shí)符、保留字、常數(shù)和分界符之一，就可形成相應(yīng)的單詞并傳遞給所需部分。 在具體實(shí)現(xiàn)時(shí)，可將各類單詞設(shè)計(jì)成結(jié)構(gòu)和長(zhǎng)度均相同的形式，例如，每一單詞可設(shè)計(jì)成如下形式：(type,pointer)其中type指明單詞的種類，例如： k 關(guān)鍵字（可事先構(gòu)造好） i標(biāo)識(shí)符 c常數(shù)s分界符（可事先構(gòu)造好）point指向本單詞存放處的開始位置。 將詞法分析程序設(shè)計(jì)成子程序的框圖 :4.6 與設(shè)計(jì)掃描程序相關(guān)的幾個(gè)問題設(shè)計(jì)掃描程序時(shí)，會(huì)遇到下面一些問題。首先，應(yīng)注意的是一般應(yīng)構(gòu)造盡