程序設(shè)計語言與編譯原理-第六章詞法分析課件

第六章詞法分析主要內(nèi)容1.介紹詞法分析的過程2.討論詞法分析器的設(shè)計與實現(xiàn)3.介紹實現(xiàn)詞法分析器的主要工具：狀態(tài)轉(zhuǎn)換圖第六章詞法分析主要內(nèi)容第一節(jié)詞法分析概述一.詞法分析的功能1.功能掃描源程序的字符串,按照詞法規(guī)則,識別出單詞符號作為輸出;對識別過程中發(fā)現(xiàn)的詞法錯誤,則輸出有關(guān)的錯誤信息。

第一節(jié)詞法分析概述一.詞法分析的功能1.功能掃描源程序功能：輸入源程序，輸出單詞符號。單詞符號是一個程序語言的基本語法符號。3功能：輸入源程序，輸出單詞符號。單詞符號是一個程序語言的基本詞法分析器的功能：輸入源程序，輸出單詞符號。單詞符號：一個程序語言的基本語法符號。分為以下5種。

1、保留字(關(guān)鍵字)：由程序語言定義的具有固定意義的標(biāo)識符。也可稱為保留字或基本字。例如：Pascal中的begin，end，if等。它是確定的。

2、標(biāo)識符：用來表示各種名字，如變量名、數(shù)組名、過程名等。它是不限的。

3、常數(shù)：常數(shù)的類型一般有整型、實型、布爾型、文字型等。它是不限的。

4、運算符：如+、-、*、/等。它是確定的。

5、界符：如逗號、分號、括號、/*，*/等。它是確定的。確定不限二.詞法分析器的輸出形式詞法分析器的功能：輸入源程序，輸出單詞符號。確定不限二.詞55

(單詞類別,單詞的屬性)區(qū)分單詞所屬的類(整數(shù)編碼)單詞的值2.單詞的輸出形式(1)二元式

單詞符號的表示形式：詞法分析器所輸出的單詞符號常常表示成

二元式（單詞種別，單詞自身的值）。單詞種別可以用以下形式表示：

1、一類單詞統(tǒng)一用一個整數(shù)值代表其屬性。例如：1代表關(guān)鍵字，2代表標(biāo)識符等。

2、每一個單詞一個類別。例如：1代表BEGIN，2代表END等。單詞自身的值可以表示成：常量的二進(jìn)制表示；常量、變量等在符號表種的地址碼，等等。(單詞類別,單詞的屬性)區(qū)分（2）單詞類別的劃分基本字、運算符、界符:一字一碼標(biāo)識符:單列一種常數(shù):按類型分類

（2）單詞類別的劃分基本字、運算符、界符:一字一碼一個例子A:=B50+10；的輸出為：（標(biāo)識符的編碼，‘A’）（:=的編碼，—）（標(biāo)識符的編碼，‘B50’）（＋的編碼，—）（整數(shù)的編碼，‘10’）（；的編碼，—）

一個例子注意：一個語言的單詞符號如何分種，分幾種，怎樣編碼，是一個技術(shù)問題。標(biāo)識符一般同歸為一種。常數(shù)則宜按類型（整、實、布爾）分。關(guān)鍵字可以將其全體視為一種，也可一字一種。運算符可采用一符一種，但也可把具有一定共性的視為一種。界符則一般采用一符一種。如何進(jìn)行分種主要取決于處理上的方便。

若是一符一種分種，單詞自身值就不需要了。否則，要查符號表。注意：一個語言的單詞符號如何分種，分幾種，怎樣編碼，是一個技例：151－FORTRAN編譯程序的詞法分析器在掃描輸入串

IF(5·EQ·M)GOTO100

后，它輸出的單詞符號串是：

邏輯IF（34，_）左括號（2，_）整常數(shù)（20，‘5’的二進(jìn)制表示）等號（6，_）標(biāo)識符（26，‘M’）右括號（16，_）

GOTO（30，_）標(biāo)號（19，‘100’的二進(jìn)制表示）IF為關(guān)鍵字，種別編碼34，采用一符一種的編碼方式。常數(shù)類型，種別編碼20，單詞自身的值為‘5’的二進(jìn)制表示?！?’為界符，種別編碼2，采用一符一種的編碼方式。等號為運算符，種別編碼6，采用一符一種的編碼方式。M為標(biāo)識符，種別編碼26，單詞自身值為‘M’?！?’為界符，種別編碼16，采用一符一種的編碼方式。GOTO為關(guān)鍵字，種別編碼30，采用一符一種的編碼方式。100為標(biāo)號，種別編碼19，單詞內(nèi)部的值用100的二進(jìn)制表示。例：151－FORTRAN編譯程序的詞法分析器在掃描輸入串例

：下述C++代碼段：while(i>=j)i--；經(jīng)詞法分析器處理以后，它將被轉(zhuǎn)換為如下的單詞符號串

(while，_)((，_)(id，指向i的符號表指針)(>=，_)(id，指向j的符號表指針)()，_)(id，指向i的符號表指針)(--，_)(；，_)例：下述C++代碼段：while(i>=j)i詞法分析程序的實現(xiàn)方式完全獨立方式：詞法分析程序作為單獨一趟來實現(xiàn)。詞法分析程序讀入整個源程序，它的輸出作為語法分析程序的輸入。相對獨立方式：把詞法分析程序作為語法分析程序的一個獨立子程序。語法分析程序需要新符號時調(diào)用這個子程序。2.詞法分析器作為一個獨立子程序12詞法分析程序的實現(xiàn)方式完全獨立方式：詞法分析程序作為單獨一趟完全獨立方式采用詞法分析工作完全獨立的原因：簡化設(shè)計，降低語法分析的復(fù)雜性提高編譯效率增加編譯系統(tǒng)的可移植性源程序詞法分析程序語法分析程序?qū)傩宰中蛄小?13完全獨立方式采用詞法分析工作完全獨立的原因：源程序詞法分析程相對獨立方式當(dāng)采用遞歸下降分析等技術(shù)實現(xiàn)一趟編譯程序時常采用這種方式。詞法分析器語法分析器符號表源程序單詞符號取下一單詞...14相對獨立方式當(dāng)采用遞歸下降分析等技術(shù)實現(xiàn)一趟編譯程序時常采用詞法分析器的設(shè)計設(shè)計前提：

把scanner作為一個獨立的子程序；詞法分析器的任務(wù)為輸出單詞符號。預(yù)處理必要性：編輯性字符如空白符、回車符等，除了出現(xiàn)在文字和常數(shù)中以外，在別處出現(xiàn)都沒有意義。功能：剔除無用字符。實現(xiàn)：預(yù)處理子程序。詞法分析器的設(shè)計設(shè)計前提：預(yù)處理必要性：編輯性字符如空白符、輸入列表預(yù)處理子程序掃描器掃描緩沖區(qū)輸入緩沖區(qū)單詞符號圖

詞法分析器語法分析器預(yù)處理部分掃描器輸入列表預(yù)處理掃描器掃描緩沖區(qū)輸入緩沖區(qū)單詞符號圖詞法分析一.掃描緩沖區(qū)1.輸入緩沖區(qū)：源程序輸入緩沖區(qū)2.預(yù)處理程序：取消注解，剔除無用的空白、跳格、回車、換行等

一.掃描緩沖區(qū)1.輸入緩沖區(qū)：源程序輸入緩沖區(qū)3.掃描緩沖區(qū)：從輸入緩沖區(qū)輸入固定長度的字符串到另一個緩沖區(qū)（掃描緩沖區(qū)），詞法分析可以直接在此緩沖區(qū)中進(jìn)行符號識別。掃描緩沖區(qū)的結(jié)構(gòu)：起點指針：用來指示正在掃描的單詞的起點；搜索指針：用于向前搜索，尋找單詞的結(jié)束；雙緩沖區(qū)結(jié)構(gòu)：設(shè)置左右兩個緩沖區(qū)，當(dāng)左緩沖區(qū)讀完后，新讀入的字符存入右緩沖區(qū)；反之，存放在左緩沖區(qū)；左緩沖區(qū)右緩沖區(qū)起點指示器搜索指示器

3.掃描緩沖區(qū)：從輸入緩沖區(qū)輸入固定長度的字符串到另一個緩沖掃描緩沖區(qū)的大小應(yīng)當(dāng)保證單詞符號不被緩沖區(qū)的邊界打斷掃描緩沖區(qū)使用一個一分為二的區(qū)域使用循環(huán)鏈表實現(xiàn)規(guī)定單詞符號的大小不超過整個鏈表的容量起始指針?biāo)阉髦羔?9掃描緩沖區(qū)的大小起始指針?biāo)阉髦羔?9二.符號的識別根據(jù)語言規(guī)定的詞法規(guī)則，進(jìn)行識別；對不同類型的單詞符號，有不同的識別要求。超前搜索

詞法分析程序在讀取單詞時，為了判斷是否已讀入整個單詞的全部字符，常采取向前多讀取字符并通過讀取的字符來判別，即所謂超前搜索技術(shù)。二.符號的識別根據(jù)語言規(guī)定的詞法規(guī)則，進(jìn)行識別；對不同類型的（1）關(guān)鍵字識別：

例如：在標(biāo)準(zhǔn)FORTRAN中

1、DO99K=1,102、IF(5.EQ.M)I=103、DO99K=1.104、IF(5)=55

其中的DO、IF為關(guān)鍵字其中的DO、IF為標(biāo)識符的一部分其中的DO、IF為關(guān)鍵字其中的DO、IF為標(biāo)識符的一部分（2）標(biāo)識符的識別：多數(shù)語言的標(biāo)識符是字母開頭的“字母/數(shù)字”串，而且在程序中標(biāo)識符的出現(xiàn)后都跟著算符或界符。因此，不難識別。（3）常數(shù)的識別：根據(jù)常數(shù)的格式；大多數(shù)常數(shù)后都有運算符或界符。如FORTRAN的5.E08與5.EQ.M也必須超前搜索。（4）運算符的識別：需要超前搜索，對于諸如C++語言中的“++”、“--”，這種復(fù)合成的算符，需要超前搜索。（5）界符的識別：需要超前搜索，如/*

（2）標(biāo)識符的識別：多數(shù)語言的標(biāo)識符是字母開頭的“字母/數(shù)字三狀態(tài)轉(zhuǎn)換圖

是設(shè)計詞法分析器的有效工具。轉(zhuǎn)換圖：是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中，結(jié)點代表狀態(tài)，用圓圈表示。狀態(tài)之間用箭弧連接。箭弧上的標(biāo)記（字符）代表在射出結(jié)狀態(tài)下可能出現(xiàn)的輸入字符或字符類。狀態(tài)轉(zhuǎn)換圖的功能:用于識別一定的字符串。初態(tài)：一張轉(zhuǎn)換圖的啟動條件，至少有一個,用圓圈表示。終態(tài)：一張轉(zhuǎn)換圖的結(jié)束條件，至少有一個，用雙圈表示。*：表示多讀進(jìn)了一個字符。三狀態(tài)轉(zhuǎn)換圖 是設(shè)計詞法分析器的有效工具。

1.結(jié)點(node)：圓圈表示結(jié)點，代表狀態(tài)（state）2.有向邊（?。?連接結(jié)點，邊上的標(biāo)記字符表示該狀態(tài)下可能接收或識別的字符；123xy狀態(tài)轉(zhuǎn)換圖有限的有向圖有向邊上標(biāo)記字符唯一初態(tài)若干終態(tài)（至少一個）123xy狀態(tài)轉(zhuǎn)換圖有限的有向圖123XY(a)轉(zhuǎn)換圖示例201字母其他字母或數(shù)字*（b）識別標(biāo)識符的轉(zhuǎn)換圖其他201數(shù)字?jǐn)?shù)字*（c）識別整數(shù)的轉(zhuǎn)換圖簡單的狀態(tài)轉(zhuǎn)換圖示例：初態(tài)終態(tài)從0狀態(tài)到1狀態(tài)可能出現(xiàn)字母123XY(a)轉(zhuǎn)換圖示例201字母其他字母或數(shù)字*（b）識7*65·數(shù)字101數(shù)字?jǐn)?shù)字2數(shù)字3E或D+或－數(shù)字其他E或D·數(shù)字其他數(shù)字例：識別FORTRAN實型常數(shù)的轉(zhuǎn)換圖：例如下列實型常數(shù)可以被以下轉(zhuǎn)換圖識別：

1.23E+4.56E-77*65·數(shù)字101數(shù)字?jǐn)?shù)字2數(shù)字3E或D+或－數(shù)字其他第四章設(shè)計的語言允許下述單詞：標(biāo)識符、數(shù)字串、begin、end、integer、if、

then、else、function、read、write、

-、*、<、<=、<>、

=、>、>=、:=、；、（、）詞法分析器的設(shè)計與實現(xiàn)一.單詞符號

第四章設(shè)計的語言允許下述單詞：詞法分析器的設(shè)計與實現(xiàn)一.

單詞符號種別編碼助憶符內(nèi)碼值begin01$BEGIN-end02$END-integer03$INTEGER-if04$IF-then05$THEN-else06$ELSE-function07$FUNCTION-read08$READ-write09$WRITE-單詞符號種別編碼助憶符內(nèi)碼值標(biāo)識符10$ID字符串常數(shù)11$INT二進(jìn)制值=12$EQ-<>13$NE-<=14$LE-<15$LT->=16$GE>17$GT-單詞符號種別編碼助憶符內(nèi)碼值begin01$BEGIN-e

單詞符號種別編碼助憶符內(nèi)碼值-18$SUB-*19$MUL-:=20$ASSIGN-(21$LPAR-)22$RPAR-;23$SEM-單詞符號種別編碼助憶符內(nèi)碼值-18$SUB-*19$MUL

012字母字母/數(shù)字其它字符34數(shù)字?jǐn)?shù)字非數(shù)字5=67<非=8=9>1011>非=12=13-14*1516:=17非=18(19)20;21其他退一字符；查保留字表；若是，返回(保留字種別，-)若不是，返回($ID，標(biāo)識符在符號表中的位置)退一字符；返回($INT，常數(shù)在常數(shù)表中的位置)返回($EQ，-)返回($LT，-)，退一字符返回($LE，-)返回($NE，-)返回($GT，-)，退一字符返回($GE，-)返回($SUB，-)返回($MUL，-)返回($ASSIGN，-)出錯處理返回($LPAR，-)返回($RPAR，-)返回($SEM，-)ERROR，非法字符二.狀態(tài)轉(zhuǎn)換圖*****012字母字母/數(shù)字其它字符34數(shù)字?jǐn)?shù)字非數(shù)字5=67<非

為了把狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)化成程序，每個狀態(tài)要建立一段程序，它要做的工作如下：第一步：從輸入緩沖區(qū)中取一個字符。為此，我們使用函數(shù)GETCHAR，每次調(diào)用它，推進(jìn)先行指針，送回一個字符。第二步：確定在本狀態(tài)下，哪一條箭弧是用剛剛來的輸入字符標(biāo)識的。如果找到，控制就轉(zhuǎn)到該弧所指向的狀態(tài)；若找不到，那么尋找該單詞的企圖就失敗了。失?。合刃兄羔槺仨氈匦禄氐介_始指針處，并用另一狀態(tài)圖來搜索另一單詞。如果所有的狀態(tài)轉(zhuǎn)換圖都試過之后，還沒有匹配的，就表明這是一個詞法錯誤，此時，調(diào)用錯誤校正程序。GETCHAR是過程，將下一輸入字符讀入CHAR，搜索指示器前移一個字符。為了把狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)化成程序，每個狀態(tài)要建立一段GET每個狀態(tài)結(jié)對應(yīng)一小段程序分支狀態(tài)——if或case語句循環(huán)狀態(tài)——while語句終態(tài)——return語句三.實現(xiàn)方法

每個狀態(tài)結(jié)對應(yīng)一小段程序三.實現(xiàn)方法33狀態(tài)轉(zhuǎn)換圖的實現(xiàn)思想：每個狀態(tài)結(jié)點對應(yīng)一小段程序。做法:1)對不含回路的分叉結(jié)，可用一個CASE語句或一組IF-THEN-ELSE語句實現(xiàn)GetChar();if(IsLetter()){…狀態(tài)j的對應(yīng)程序段…;}elseif(IsDigit()){…狀態(tài)k的對應(yīng)程序段…;}elseif(ch=‘/’){…狀態(tài)l的對應(yīng)程序段…;}else{…錯誤處理…;}ijkl字母數(shù)字/33狀態(tài)轉(zhuǎn)換圖的實現(xiàn)GetChar();ijkl字母數(shù)字/342)對含回路的狀態(tài)結(jié)，可對應(yīng)一段由WHILE結(jié)構(gòu)和IF語句構(gòu)成的程序.i字母或數(shù)字其它jGetChar();while(IsLetter()orIsDigit()) GetChar();…狀態(tài)j的對應(yīng)程序段…3)終態(tài)結(jié)點表示識別出某種單詞符號，因此，對應(yīng)語句為

RETURN(C，VAL)

其中，C為單詞種別，VAL為單詞自身值.342)對含回路的狀態(tài)結(jié)，可對應(yīng)一段由WHILE結(jié)構(gòu)和IF語鍛煉012字母其它字符字母或數(shù)字*數(shù)字23*其它符號

入口字母？取字符字母？數(shù)字？出口出口否是是否是否鍛煉012字母其它字符字母或數(shù)字*數(shù)字23*其它符號入口字

9.查保留字子程序reserve10.語句return(c,val)11.二進(jìn)制轉(zhuǎn)換子程序dtb12.標(biāo)識符存符號表子程序id13.指針變量val14.錯誤處理子程序error1.字符串變量char2.字符數(shù)組token3.讀一字符子程序getchar4.刪除空白子程序getnbc5.連接字符串子程序concat6.判定字母函數(shù)letter7.判定數(shù)字函數(shù)digit8.回退一字符子程序retract全局量及過程:用來存放最新讀入的字符用來存放單詞符號從掃描緩沖區(qū)讀一個字符進(jìn)入char，并將搜索指針移向下一個字符檢查char中字符是否為空白；若是，調(diào)用getchar，直到char中的字符不是空白符把char中的字符連接到token布爾函數(shù)；若char中的字符為字母，返回真；否則，為假；布爾函數(shù)；若char中的字符為數(shù)字，返回真；否則，為假；將搜索指針回退一個字符，并把已讀入char的字符用空白代替。用token中的字符串查保留字表，若查到，則返回該保留字的種別編碼；否則返回0值其中c是種別編碼，val或者是token在符號表中位置，或者是在常數(shù)表中的位置，或者無定義將token中的數(shù)字串轉(zhuǎn)換成二進(jìn)制值，并存入常數(shù)表中將token中的字符串存入符號表中存放標(biāo)識符在符號表中的位置，或常數(shù)在常數(shù)表中的位置處理出現(xiàn)的詞法錯誤9.查保留字子程序reserve10.語句return(cstart:token:=‘‘;getchar;getnb;casecharacterof‘a(chǎn)’…’z’:beginwhileletterordigitdobeginconcatenate;getcharend;retract;c:=reserve;ifc=0thenbeginbuildlist;return($ID,val)endelsereturn(c,—)end;‘0’…’9’:beginwhiledigitdobeginconcatenate;getcharend;retract;dtb;return($INT,val)end;‘=’:return($EQ,—);‘-’:return($SUB,—);‘*’:return($MUL,—);‘(’:return($LPAR,—);‘)’:return($RPAR,—);

start:token:=‘‘;‘0’…’9’:beg‘<‘:begingetchar;ifcharacter=‘=‘thenreturn($LE,—)elseifcharacter=‘>’thenreturn($NE,—);retract;return($LT,—)end;‘>‘:begingetchar;ifcharacter=‘=‘thenreturn($GE,—);retract;return($GT,—)end;‘:‘:begingetchar;ifcharacter=‘=‘thenreturn($ASSIGN,—)elseerrorend;‘;‘:return($SEM,—)other:errorendofcase;gotostart;

‘<‘:begingetchar;‘;‘:將詞法分析器實現(xiàn)為一個函數(shù)LexAnalyze()，函數(shù)每執(zhí)行一次，就會從輸入字符串中識別出一個單詞符號并按二元式形式返回。將詞法分析器實現(xiàn)為一個函數(shù)實際詞法分析中，可連續(xù)調(diào)用該函數(shù)，將輸入字符串中的所有單詞符號識別出來，并輸出相應(yīng)的二元式序列；也可將其作為語法分析程序的一個子程序，當(dāng)語法分析需要下一個新單詞時，就調(diào)用該函數(shù)，從輸入字符串中識別一個單詞后返回。實際詞法分析中，可連續(xù)調(diào)用該函數(shù)，將輸入字符串中的所有單詞符

符號表符號表42編譯過程中編譯程序需要不斷匯集和反復(fù)查證出現(xiàn)在源程序中各種名字的屬性和特征等有關(guān)信息。這些信息通常記錄在一張或多張符號表中，每一項分兩部分：名字(標(biāo)識符)和此名字的有關(guān)信息。每個名字的有關(guān)信息一般指種屬(如簡單變量、數(shù)組、過程等)、類型(如整、實、布爾等)等等。這些信息將用于語義檢查、產(chǎn)生中間代碼以及最終生成目標(biāo)代碼等階段。42編譯過程中編譯程序需要不斷匯集和反復(fù)查證出現(xiàn)在源程序中各43在編譯程序中符號表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識符的屬性信息，這些信息集中反映了標(biāo)識符的語義特征屬性。在詞法分析及語法在分析過程中不斷積累和更新表中的信息，并在詞法分析到代碼生成的各階段，按各自的需要從表中獲取不同的屬性信息。不論編譯策略是否分趟，符號表的作用和地位是完全一致的。

①收集符號屬性

②上下文語義的合法性檢查的依據(jù)

③作為目標(biāo)代碼生成階段地址分配的依據(jù)

43在編譯程序中符號表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識符的屬44①收集符號屬性

編譯程序掃描說明部分收集有關(guān)標(biāo)識符的屬性，并在符號表中建立符號的相應(yīng)屬性信息。例如，編譯程序分析到下述兩個說明語句

intA;

floatB[5];

44①收集符號屬性45上下文語義的合法性檢查的依據(jù)同一個標(biāo)識符可能在程序的不同地方出現(xiàn)，而有關(guān)該符號的屬性是在這些不同情況下收集的。特別是在多趟編譯及程序分段編譯（在PASCAL及C中以文件為單位）的情況下，更需檢查標(biāo)識符屬性在上下文中的一致性和合法性。通過符號表中屬性記錄可進(jìn)行相應(yīng)上下文的語義檢查。

例如，在一個C語言程序中出現(xiàn)

…

inti[3,5];//定義整型數(shù)組i

…

floati[4,2];//定義實型數(shù)組i,重定義沖突

…

inti[3,5];//定義整型數(shù)組i,重定義沖突45上下文語義的合法性檢查的依據(jù)46③作為目標(biāo)代碼生成階段地址分配的依據(jù)

每個符號變量在目標(biāo)代碼生成時需要確定其在存儲分配的位置（主要是相對位置）。首先要確定其被分配的區(qū)域。在C語言中首先要確定該符號變量是分配在公共區(qū)（extern）、文件靜態(tài)區(qū)（externstatic）、函數(shù)靜態(tài)區(qū)（函數(shù)中static）、還是函數(shù)運行時的動態(tài)區(qū)（auto）等。其次是根據(jù)變量出現(xiàn)的次序決定該變量在某個區(qū)中所處的具體位置，這通常使用在該區(qū)域中相對區(qū)頭的相對位置確定。而有關(guān)區(qū)域的標(biāo)志及相對位置都是作為該變量的語義信息被收集在該變量的符號表屬性中。46③作為目標(biāo)代碼生成階段地址分配的依據(jù)47符號表的組織與作用在編譯的各個分析階段，每當(dāng)遇到一個名字都要查找符號表。若是新名字或發(fā)現(xiàn)已有名字的新信息，則要加入(填入)。因此，合理組織符號表，使其存儲占用最少，同時提高編譯期間對符號表的訪問效率，至關(guān)重要。一、符號表的作用47符號表的組織與作用在編譯的各個分析階段，每當(dāng)遇到一個名字48概括地說，符號表的每一項(或稱入口)包含兩大欄(或稱區(qū)段、字域)，即名字欄和信息欄。表格的形式如下：第1項(入口1)第2項(入口2)第n項(入口n)名字欄(NAME)信息欄(INFORMATION)…48概括地說，符號表的每一項(或稱入口)包含兩大欄(或稱49信息欄包含許多子欄和標(biāo)志位，記錄相應(yīng)名字的種種不同屬性。由于查填符號表一般是通過匹配名字來實現(xiàn)的，故名字欄也稱主欄，其內(nèi)容稱為關(guān)鍵字(keyword)。符號表中每一項都是關(guān)于名字的說明。因為所保存的關(guān)于名字的信息取決于名字的用途，所以各表項的格式不一定統(tǒng)一，為使表中的每個記錄格式統(tǒng)一，可采用指針技術(shù)，在記錄中設(shè)置指針，把某些信息放在表的外邊，用指針指向存放另外信息的空間。49信息欄包含許多子欄和標(biāo)志位，記錄相應(yīng)名字的種種不同屬性。50對符號表的操作大致可以分為五類：·查詢某個名字是否已在表中?！ぬ钊胍粋€新的名字?！ぬ砑踊蚋履硞€名字的某些信息?！h除一個或一組無用的項?！ぴL問某個名字的某些信息。50對符號表的操作大致可以分為五類：·查詢某個名字是否已在51對符號表進(jìn)行操作的時機(jī)：定義性出現(xiàn)使用性出現(xiàn)按名字的不同種屬建立多張符號表，如常數(shù)表、變量名表、過程名表、…符號的組織方式:1.安排各項各欄的存儲單元為固定長度2.用間接方式安排各欄存儲單元51對符號表進(jìn)行操作的時機(jī)：52最簡單的組織方式：各項各欄長度固定——易于組織、填寫和查找。這種表格，每一欄的內(nèi)容可直接填寫在有關(guān)的區(qū)段內(nèi)。例如，對于名字欄，其大小可按標(biāo)識符最大允許長度來確定。如標(biāo)準(zhǔn)FORTRAN語言規(guī)定每一標(biāo)識符不得超過6個字符，因此就可用6個字符的空間作為名字欄的長度。若標(biāo)識符長度不足6個字符，則以空白符補(bǔ)齊。二、符號表的組織方式52最簡單的組織方式：各項各欄長度固定——易于組織、填寫和查53但是，有許多語言對標(biāo)識符的長度幾乎不加以限制，或者說，標(biāo)識符的長度范圍很寬。比如說，最長可允許由100個字符組成的名字。此時，如果名字欄的長度設(shè)為100個字符，則勢必會大量浪費存儲空間。因此，最好采用指針技術(shù)。用另外一獨立的字符串?dāng)?shù)組，把所有標(biāo)識符都存放其中。在符號表的主欄放一指示器和一整數(shù)，或僅放一指示器，同時在標(biāo)識符前放一個整數(shù)。指示器指出標(biāo)識符在字符串?dāng)?shù)組中的位置；整數(shù)代表此標(biāo)識符的長度。53但是，有許多語言對標(biāo)識符的長度幾乎不加以限制，或者說，標(biāo)54SAMPLELOOPINFORMATIONNAME，6，4在符號表的主欄放一指示器和一整數(shù)54SAMPLELOOPINFORMATIONNAME，6，55INFORMATIONNAME6SAMPLE4LOOP在符號表的主欄放一指示器，同時在標(biāo)識符前放一個整數(shù)55INFORMATIONNAME6SAMPLE4LOOP在56

類似地，如果各種名字所需的信息空間長短不一，則將共同屬性直接登記在信息欄中，而特殊屬性登記在別的地方。在信息欄中附設(shè)一指示器，指向存放特殊屬性的地方。

例如對于數(shù)組標(biāo)識符，需存儲的信息包含維數(shù)等，如果將它們與其它名字全部集中在一張符號表中，處理起來很不方便。因此，常另辟一個信息表區(qū)，稱數(shù)組信息表(或內(nèi)情向量表)

，用來保存數(shù)組的有關(guān)信息。在符號表的地址欄內(nèi)存入符號表與內(nèi)情向量表連接的入口地址。當(dāng)填寫或查詢數(shù)組有關(guān)信息時，通過符號表來訪問此內(nèi)情向量表。56類似地，如果各種名字所需的信息空間長短不一，則將共同屬57

對過程名以及其它一些含信息較多的名字，都可類似地開辟專用信息表，存放那些不宜全部存放在符號表中的信息，而在符號表中保留與信息表相聯(lián)系的地址信息。57對過程名以及其它一些含信息較多的名字，都可類似地開辟專58

一張可容納N項的符號表在存儲器中可用下述兩種不同方式之一表示(假定每項需用K個字)(1)把每一項置于連續(xù)的

K個字中。K*N個字表示。(2)分成M個子表T1，T2，…，Tm。每個子表含N項。假定子表Ti的每一項所需的字?jǐn)?shù)為Ki

，則K=K1+K2+…+Km

。對于任何i,T1[i],T2[i],…,Tm[i]的并置就構(gòu)成了符號表第i項的全部內(nèi)容。58一張可容納N項的符號表在存儲器中可用下述兩種不同方59

編譯過程中，每一遍所用的符號表可能略有差別。一般說來，主欄和某些基本屬性欄大多不會改變，但另外一些信息欄可能在不同階段有不同的內(nèi)容，為了合理使用存儲空間，特別是重新利用那些已經(jīng)過時的信息欄所占用的空間，最好采用第二種存儲表示方式。

若用高級語言實現(xiàn)的話，用記錄數(shù)組或變體記錄的數(shù)組來實現(xiàn)是比較合適的。59編譯過程中，每一遍所用的符號表可能略有差別。一般說來，60

在編譯時，雖然從原則上說，使用一張統(tǒng)一的符號表就夠了。但許多編譯程序按名字的不同種屬分別使用許多符號表。如常數(shù)表、變量名表、過程名表等等。這是因為，不同種屬名字的相應(yīng)信息往往不同，信息欄的長度也各有差異。因而，按不同種屬建立不同的符號表在處理上常常是比較方便的。60在編譯時，雖然從原則上說，使用一張統(tǒng)一的符號表就夠了。61例:PASCAL程序段：PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.61例:PASCAL程序段：PROCEDUREINCWA62PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.62PROCEDUREINCWAP(M，N:INTEGER63PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.63PROCEDUREINCWAP(M，N:INTEGER64PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.64PROCEDUREINCWAP(M，N:INTEGER65PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.65PROCEDUREINCWAP(M，N:INTEGER666667PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.67PROCEDUREINCWAP(M，N:INTEGER68§整理與查找構(gòu)造符號表最簡單、最容易的辦法是按關(guān)鍵字出現(xiàn)的順序依次填寫各個項。用一個一維數(shù)組或多個一維數(shù)組來存放名字及有關(guān)信息。當(dāng)碰到一個新名字時就按順序?qū)⑺钊氡碇?，若需要了解一個名字的有關(guān)信息，則就從第一項開始順序查找。這種構(gòu)造方式稱為線性表，其結(jié)構(gòu)如下：(其中AVAILABLE總是指向空白區(qū)的首地址)一、線性表68§整理與查找構(gòu)造符號表最簡單、最容易的辦法是按關(guān)鍵字69項數(shù)1AVAILABLE234NAMEINFORMATIONJ1…XYZ…I…BC……69項數(shù)1AVAILABLE234NAMEINFORMATI70線性表中每一項的先后順序是按先來者先填的原則安排的，編譯程序不做任何整理次序的工作。如果是顯式說明的程序設(shè)計語言，則根據(jù)各名字在說明部分出現(xiàn)的先后順序填入表中(表尾)；如果是隱式說明的程序設(shè)計語言，則根據(jù)各名字首次引用的先后順序填入表中。當(dāng)需要查找某個名字時，就從第一項開始順序查找，若一直查到AVAILABLE還未找到這個名字，就說明該名字不在表中。70線性表中每一項的先后順序是按先來者先填的原則安排的，編譯71按照編程習(xí)慣，新定義的名字往往要立即使用。所以，反序查找效率也許更高。當(dāng)需要填進(jìn)一個新說明的名字時，必須先對這個名字進(jìn)行查找，如果已在表中，則不重新填入(通常要報告重名錯誤)。如果不在表中，則填入AVAILABLE所指位置，然后累增AVAILABLE，使其指向下一空白項的單元地址。71按照編程習(xí)慣，新定義的名字往往要立即使用。所以，反序查找72對一張含N項的線性表，欲從中查找一項，則平均比較次數(shù)為n/2，所以效率很低，但由于結(jié)構(gòu)簡單且節(jié)省存儲空間，所以許多編譯程序仍采用。提高效率方法之一：每項附設(shè)一指示器，按“最新最近”訪問原則，建立一鏈表，使得在任何時候，鏈的第一元素指向最新最近查詢過的項——自適應(yīng)線性表。72對一張含N項的線性表，欲從中查找一項，則平均比較次數(shù)為73按名字大小建立有序表，則可采用對折查找法(折半查找)

最多比較次數(shù)1+log2N(對數(shù)查找)。要保持有序，需要每次填入新名字時都進(jìn)行排序，因此采用二叉樹組織法，左大右小。查找效率比對折查找低了一些，且所需存儲空間增大，但其所需順序化的時間要少得多，且比較次數(shù)仍和log2N成比例，因此可取。二、對折查找與二叉樹73按名字大小建立有序表，則可采用對折查找法(折半查找)74對表格處理，查表與填表都能高效進(jìn)行是最理想的。線性表填表快、查表慢，而對折法填表慢、查表快，兩方面綜合——雜湊技術(shù)(哈希表或散列表)：假定有一足夠大的區(qū)域，可填寫一張含N項的符號表，希望構(gòu)造一個地址函數(shù)H，對任何名字SYM，H(SYM)都可獲得一個0和N-1之間的值。也就是說，不論對SYM是查表還是填表，都希望通過H(SYM)獲得它在表中的位置?！s湊函數(shù)，哈希函數(shù)。三、雜湊技術(shù)74對表格處理，查表與填表都能高效進(jìn)行是最理想的。線性表填表75假設(shè)用無符號整數(shù)作為項名，若取N為質(zhì)數(shù)，則H(SYM)定義為SYM/N的余數(shù)就是一個相當(dāng)理想的函數(shù)(