編譯原理講義 (5).ppt

1、5 類(lèi)型檢查,學(xué)時(shí)：4 知識(shí)點(diǎn)：類(lèi)型體制 各語(yǔ)法成分的類(lèi)型檢查 符號(hào)表,2,5 類(lèi)型檢查,5.1 語(yǔ)義分析的概念 5.2 類(lèi)型體制 5.3 簡(jiǎn)單類(lèi)型檢查器的說(shuō)明 5.4 類(lèi)型表達(dá)式的等價(jià) 5.5 類(lèi)型檢查有關(guān)的其他主題 5.6 符號(hào)表 小 結(jié) 作 業(yè),3,5.1 語(yǔ)義分析的概念,程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)由上下文無(wú)關(guān)文法來(lái)描述 程序結(jié)構(gòu)正確與否與該結(jié)構(gòu)的上下文有關(guān)，如： 變量的作用域問(wèn)題 同一作用域內(nèi)同名變量的重復(fù)聲明問(wèn)題 表達(dá)式、賦值語(yǔ)句中的操作數(shù)的類(lèi)型一致性問(wèn)題 思考： 設(shè)計(jì)上下文有關(guān)文法來(lái)描述語(yǔ)言中上下文有關(guān)的結(jié)構(gòu)？ 理論上可行，構(gòu)造有困難，構(gòu)造相應(yīng)的分析器更困難 解決辦法： 設(shè)計(jì)專(zhuān)門(mén)的語(yǔ)義動(dòng)作

2、補(bǔ)充上下文無(wú)關(guān)文法的分析器 利用語(yǔ)法制導(dǎo)翻譯技術(shù)實(shí)現(xiàn)語(yǔ)義分析,4,上下文有關(guān)信息的記錄與使用,符號(hào)表 記錄編譯過(guò)程中識(shí)別出的上下文有關(guān)的信息，如： 變量的類(lèi)型 相對(duì)地址 信息的引用 根據(jù)詞法分析器識(shí)別出的標(biāo)識(shí)符的屬性值（標(biāo)識(shí)符在符號(hào)表中的入口），查找符號(hào)表中對(duì)應(yīng)該標(biāo)識(shí)符的記錄，從而可以取得該標(biāo)識(shí)符有關(guān)的信息。 如果編譯的程序塊處于該變量的作用域內(nèi)，則這個(gè)變量將一直保留在符號(hào)表中,5,動(dòng)態(tài)檢查：目標(biāo)程序運(yùn)行時(shí)進(jìn)行的檢查 靜態(tài)檢查：讀入源程序、但不執(zhí)行源程序的情況下進(jìn)行的檢查，包括： 類(lèi)型檢查 對(duì)訪(fǎng)問(wèn)數(shù)據(jù)的操作和被訪(fǎng)問(wèn)數(shù)據(jù)的類(lèi)型進(jìn)行檢查，檢查操作的合法性和數(shù)據(jù)類(lèi)型的相容性。 控制流檢查 檢查控制流

3、語(yǔ)句是否使控制轉(zhuǎn)移到一個(gè)合法的位置。 一致性檢查 有些場(chǎng)合要求所定義的對(duì)象恰好被定義一次 一個(gè)標(biāo)識(shí)符在同一程序塊中必須而且只能被說(shuō)明一次 CASE語(yǔ)句中用于匹配選擇表達(dá)式的常量必須各不相同 枚舉類(lèi)型定義中的各元素不允許重復(fù) 有些場(chǎng)合要求標(biāo)識(shí)某結(jié)構(gòu)的名字必須出現(xiàn)兩次或兩次以上,靜態(tài)檢查,6,類(lèi)型檢查,由類(lèi)型檢查器完成 檢驗(yàn)結(jié)構(gòu)的類(lèi)型是否和它的上下文所期望的一致 算術(shù)運(yùn)算符mod 用戶(hù)定義的函數(shù)，實(shí)參與形參一致 類(lèi)型檢查器的位置,生成目標(biāo)代碼時(shí)可能用到類(lèi)型檢查器產(chǎn)生的信息 重載運(yùn)算符：一個(gè)運(yùn)算符在不同的上下文中表示不同的運(yùn)算 類(lèi)型強(qiáng)制：編譯器把運(yùn)算對(duì)象變換為上下文所期望的類(lèi)型,7,5.2 類(lèi)型體制

4、,設(shè)計(jì)類(lèi)型檢查器時(shí)要考慮的因素： 語(yǔ)法結(jié)構(gòu) 類(lèi)型概念 把類(lèi)型指派給語(yǔ)言結(jié)構(gòu)的規(guī)則 Pascal、C語(yǔ)言報(bào)告中關(guān)于類(lèi)型的描述： 如果算術(shù)運(yùn)算符加、減和乘的兩個(gè)運(yùn)算對(duì)象都是整型，那么結(jié)果是整型。 一元運(yùn)算符 與A相關(guān)的類(lèi)型表達(dá)式為：array(1.10,integer) 笛卡兒乘積：如果T1和T2是類(lèi)型表達(dá)式，那么它們的笛卡兒乘積T1T2也是類(lèi)型表達(dá)式，假定是左結(jié)合的。,9,如Pascal的程序片段：,type row=record address:integer; lexeme:array1.15 of char end; var table:array1.10 of row;,類(lèi)型名row代表

5、類(lèi)型表達(dá)式: record(addressinteger)(lexemearray(1.15,char) 和變量table相關(guān)的類(lèi)型表達(dá)式為： array(1.10,row) 指針：如果T是類(lèi)型表達(dá)式，那么pointer(T)是表示“指向T類(lèi)型對(duì)象的指針”的類(lèi)型表達(dá)式。 Pascal的例子：var p:row; 與P相關(guān)的類(lèi)型表達(dá)式為：pointer(row),記錄：記錄類(lèi)型是它的各域類(lèi)型的笛卡兒乘積，記錄的域有名，每個(gè)域是一個(gè)二元組（域名類(lèi)型）,10,函數(shù)：從定義域類(lèi)型D到值域類(lèi)型R的映射 類(lèi)型由類(lèi)型表達(dá)式 DR 表示。,Pascal的內(nèi)部函數(shù)mod： intintint 用戶(hù)定義的Pasc

6、al函數(shù)：function f(a,b:char):integer; f的類(lèi)型表達(dá)式：charcharpointer(integer) 函數(shù)g： 參數(shù)是把整數(shù)映射成整數(shù)的函數(shù) 返回結(jié)果是和參數(shù)類(lèi)型相同的另一函數(shù) g的類(lèi)型表達(dá)式為： (integerinteger)(integerinteger) 類(lèi)型表達(dá)式可以包含變量（稱(chēng)為類(lèi)型變量），變量的值是類(lèi)型表達(dá)式。,11,類(lèi)型表達(dá)式的有向圖,利用語(yǔ)法制導(dǎo)翻譯技術(shù)為類(lèi)型表達(dá)式構(gòu)造樹(shù)或dag 內(nèi)部結(jié)點(diǎn)：類(lèi)型構(gòu)造器 葉結(jié)點(diǎn)：基本類(lèi)型、類(lèi)型名、或類(lèi)型變量 如： charchar pointer(integer),12,二、類(lèi)型體制,把類(lèi)型表達(dá)式指派到程序各部

7、分的一組規(guī)則 由類(lèi)型檢查器實(shí)現(xiàn) 同一語(yǔ)言的不同編譯器使用的類(lèi)型體制可能不同 數(shù)組作為變?cè)獋鬟f時(shí)，數(shù)組的下標(biāo)集合可以指明，也可以不指明 原因：不同的Pascal語(yǔ)言編譯器實(shí)現(xiàn)的類(lèi)型體制不同 UNIX系統(tǒng)中，lint命令實(shí)現(xiàn)的類(lèi)型體制比C語(yǔ)言編譯器本身所實(shí)現(xiàn)的更詳細(xì)。,13,三、靜態(tài)和動(dòng)態(tài)類(lèi)型檢查,靜態(tài)類(lèi)型檢查：由編譯器完成的檢查 動(dòng)態(tài)類(lèi)型檢查：目標(biāo)程序運(yùn)行時(shí)完成的檢查 如果目標(biāo)代碼把每個(gè)對(duì)象的類(lèi)型和該對(duì)象的值一起保存，那么任何檢查都可以動(dòng)態(tài)完成。 一個(gè)健全的類(lèi)型體制不需要?jiǎng)討B(tài)檢查類(lèi)型錯(cuò)誤 如果一種語(yǔ)言的編譯器能夠保證它所接受的程序不會(huì)有運(yùn)行時(shí)的類(lèi)型錯(cuò)誤，則稱(chēng)這種語(yǔ)言是強(qiáng)類(lèi)型語(yǔ)言。 有些檢查只能動(dòng)

8、態(tài)完成 table: array0.255 of char; i: integer; 計(jì)算tablei,14,四、錯(cuò)誤恢復(fù),類(lèi)型錯(cuò)誤不直觀，必須報(bào)告錯(cuò)誤的性質(zhì)和位置，希望能從錯(cuò)誤中恢復(fù)，檢查剩余的輸入 出錯(cuò)處理會(huì)影響類(lèi)型檢查的規(guī)則，必須將其正確地設(shè)計(jì)進(jìn)類(lèi)型體制中 包含出錯(cuò)處理的類(lèi)型體制可能比說(shuō)明正確程序所需要的類(lèi)型體制大得多 類(lèi)型檢查器必須應(yīng)付缺少信息的局面，我們可能不知道錯(cuò)誤程序片段的類(lèi)型 使用的技術(shù)類(lèi)似于支持變量隱式聲明的語(yǔ)言所需要的技術(shù),15,5.3 簡(jiǎn)單類(lèi)型檢查器的說(shuō)明,利用語(yǔ)法制導(dǎo)方法說(shuō)明類(lèi)型體制 一、語(yǔ)言說(shuō)明 二、確定標(biāo)識(shí)符的類(lèi)型 三、表達(dá)式的類(lèi)型檢查 四、語(yǔ)句的類(lèi)型檢查,16,一

9、、語(yǔ)言說(shuō)明,源語(yǔ)言文法： PD;S DD;D|id:T Tchar|integer|boolean|arraynum of T|T|T1T2 Sid:=E|if E then S1|while E do S1|S1;S2 Eliteral|num|id|id1id2|E1andE2|E1modE2|E1E2|E|E1(E2) 該文法產(chǎn)生的一個(gè)程序： k:integer; k mod 1999,17,二、確定標(biāo)識(shí)符的類(lèi)型,語(yǔ)言中的類(lèi)型： 基本類(lèi)型： char、integer、和boolean type_error和void 構(gòu)造類(lèi)型： 數(shù)組、指針和函數(shù) 假定： 數(shù)組下標(biāo)從1開(kāi)始 類(lèi)型array2

10、56 of char的類(lèi)型表達(dá)式是： array(1.256,char) 前綴算符用于建立指針類(lèi)型 integer的類(lèi)型表達(dá)式是pointer(integer) 函數(shù)類(lèi)型由定義域類(lèi)型和值域類(lèi)型確定,18,翻譯方案中 確定并保存標(biāo)識(shí)符類(lèi)型的部分,PD;S DD;D Did:T Tchar Tinteger Tboolean Tarraynum of T1 TT1 TT1 T2, addtype(id.entry,T.type) , T.type:=char , T.type:=integer , T.type:=boolean , T.type:=array(num.val,T1.type) ,

11、 T.type:=pointer(T1.type) , T.type:=T1.typeT2.type ,引入綜合屬性T.type，記錄類(lèi)型表達(dá)式,下標(biāo)缺省為1,19,三、表達(dá)式的類(lèi)型檢查,Eliteral Enum Eid Eid1id2 EE1andE2 EE1modE2 EE1E2 EE1 EE1(E2),綜合屬性E.type，類(lèi)型體制指派給E產(chǎn)生的表達(dá)式的類(lèi)型表達(dá)式, E.type:=char , E.type:=integer , E.type:=lookup(id.entry) , E.type:=if lookup(id1.entry)=integer and lookup(id2

12、.entry)=integer or lookup(id1.entry)=char and lookup(id2.entry)=char then boolean else type_error ,20,EE1andE2,EE1modE2 EE1E2 EE1 EE1(E2), E.type:=if E1.type=boolean and E2.type=boolean then boolean else type_error , E.type:=if E1.type=integer and E2.type=integer then integer else type_error , E.typ

13、e:=if E2.type=integer and E1.type=array(s,t) then t else type_error ,21,EE1,EE1(E2), E.type:=if E1.type=pointer(t) then t else type_error , E.type:=if E1.type=st and E2.type=s then t else type_error ,22,四、語(yǔ)句的類(lèi)型檢查,Sid:=E Sif E then S1 Swhile E do S1 SS1;S2, S.type:=if lookup(id.entry)=E.type then voi

14、d else type_error , S.type:=if E.type=boolean then S1.type else type_error , S.type:=if E.type=boolean then S1.type else type_error , S.type:=if S1.type=void and S2.type=void then void else type_error ,23,5.4 類(lèi)型表達(dá)式的等價(jià),語(yǔ)義規(guī)則的形式： if 兩個(gè)類(lèi)型表達(dá)式相同 then 返回某一個(gè)類(lèi)型 else 返回 type_error 關(guān)鍵： 精確地定義什么情況下兩個(gè)類(lèi)型表達(dá)式等價(jià) 問(wèn)題：

15、類(lèi)型表達(dá)式可以命名，且這個(gè)名字可用于隨后的類(lèi)型表達(dá)式中 名字代表它自己？代表另一個(gè)類(lèi)型表達(dá)式？ 新的名稱(chēng)是一個(gè)類(lèi)型表達(dá)式，這個(gè)表達(dá)式與名稱(chēng)所代表的類(lèi)型表達(dá)式是否總是等價(jià)的？,24,一、結(jié)構(gòu)等價(jià),如果類(lèi)型表達(dá)式僅由類(lèi)型構(gòu)造器作用于基本類(lèi)型組成，則兩個(gè)類(lèi)型表達(dá)式等價(jià)的自然概念是結(jié)構(gòu)等價(jià) 兩個(gè)類(lèi)型表達(dá)式要么是同樣的基本類(lèi)型 要么是同樣的構(gòu)造器作用于結(jié)構(gòu)上等價(jià)的類(lèi)型表達(dá)式。 兩個(gè)類(lèi)型表達(dá)式結(jié)構(gòu)等價(jià)當(dāng)且僅當(dāng)它們完全相同 例如： integer 僅等價(jià)于 integer pointer(integer) 僅等價(jià)于 pointer(integer),25,測(cè)試兩個(gè)類(lèi)型表達(dá)式結(jié)構(gòu)等價(jià)的算法,輸入：兩個(gè)類(lèi)型表達(dá)

16、式s和t 輸出：如果s和t結(jié)構(gòu)等價(jià)，則返回true，否則返回false 方法： function sequiv(s,t):boolean begin if s和t是同樣的基本類(lèi)型 then return true else if s=array(s1,s2) 且t=array(t1,t2) then return sequiv(s1,t1) and sequiv(s2,t2) else if s=s1s2且t=t1t2 then return sequiv(s1,t1) and sequiv(s2,t2) else if s=pointer(s1)且t=pointer(t1) then ret

17、urn sequiv(s1,t1) else if s=s1s2且t=t1t2 then return sequiv(s1,t1) and sequiv(s2,t2) else return false end.,26,實(shí)際應(yīng)用中結(jié)構(gòu)等價(jià)概念的修改,當(dāng)數(shù)組作為參數(shù)傳遞時(shí)，數(shù)組的界不作為類(lèi)型的一部分 算法調(diào)整 else if s=array(s1,s2) 且t=array(t1,t2) then return sequiv(s2,t2),27,編碼測(cè)試方法,對(duì)基本類(lèi)型規(guī)定確定位數(shù)、確定位置的二進(jìn)制編碼； 對(duì)類(lèi)型構(gòu)造器規(guī)定確定位數(shù)的二進(jìn)制編碼 類(lèi)型表達(dá)式可用一組二進(jìn)制編碼表示 例：D.M.Ritc

18、hie的C編譯器中類(lèi)型表達(dá)式的編碼方式 類(lèi)型構(gòu)造器： pointer(t) 指向類(lèi)型t的指針 freturn(t) 含有參數(shù)的函數(shù)，返回類(lèi)型t的對(duì)象 array(t) 元素類(lèi)型為t的數(shù)組（不定長(zhǎng)度） 一元運(yùn)算符，類(lèi)型表達(dá)式具有統(tǒng)一的結(jié)構(gòu) char freturn(char) pointer(freturn(char) array(pointer(freturn(char),28,編碼方式,類(lèi)型構(gòu)造器的編碼,基本類(lèi)型的編碼,類(lèi)型表達(dá)式及其二進(jìn)制編碼示例,29,有些語(yǔ)言(如Pascal)允許用戶(hù)定義類(lèi)型名 Pascal類(lèi)型定義和變量聲明： type link=cell; var next :lin

19、k; last :link; p :cell; q, r :cell; 問(wèn)題：next、last、p、q和r是否具有相同的類(lèi)型 關(guān)鍵：類(lèi)型表達(dá)式link和類(lèi)型表達(dá)式cell是否等價(jià) 回答：依賴(lài)于具體的實(shí)現(xiàn)系統(tǒng) 原因：在Pascal報(bào)告中沒(méi)有定義“類(lèi)型等價(jià)”這個(gè)術(shù)語(yǔ),二、名字等價(jià),30,名字等價(jià)把每個(gè)類(lèi)型名看成是一個(gè)可區(qū)別的類(lèi)型,兩個(gè)類(lèi)型表達(dá)式名字等價(jià)，當(dāng)且僅當(dāng)它們完全相同 所有的名字被替換后，兩個(gè)類(lèi)型表達(dá)式成為結(jié)構(gòu)等價(jià)的類(lèi)型表達(dá)式，那么這兩個(gè)表達(dá)式結(jié)構(gòu)等價(jià)。 聲明中的變量及其類(lèi)型表達(dá)式：,考慮名字等價(jià)的情形,考慮結(jié)構(gòu)等價(jià)的情形,31,標(biāo)識(shí)符與類(lèi)型通過(guò)聲明相聯(lián)系的規(guī)則舉例,Pascal的許多編譯

20、器用隱含的類(lèi)型名與每個(gè)聲明的標(biāo)識(shí)符相聯(lián)系 如果聲明中出現(xiàn)了沒(méi)有名字的類(lèi)型表達(dá)式，則建立一個(gè)隱含的類(lèi)型名。 每當(dāng)聲明中出現(xiàn)類(lèi)型表達(dá)式時(shí)，就建立一個(gè)新的類(lèi)型名。 type link=cell; np =cell; nqr =cell; var next:link; last:link; p :np; q,r :nqr; next,last等價(jià)；q,r等價(jià)；next,last和p和q,r互不等價(jià) 結(jié)構(gòu)等價(jià)和名字等價(jià)這兩個(gè)概念，可以用來(lái)揭示各種語(yǔ)言中通過(guò)說(shuō)明使類(lèi)型和標(biāo)識(shí)符相關(guān)的規(guī)則 C語(yǔ)言采用結(jié)構(gòu)等價(jià)，Pascal采用名字等價(jià),32,類(lèi)型圖,類(lèi)型圖表示類(lèi)型 構(gòu)造方法： 每當(dāng)出現(xiàn)一個(gè)類(lèi)型構(gòu)造器或基本類(lèi)型

21、，就建立一個(gè)新的結(jié)點(diǎn)； 每當(dāng)出現(xiàn)一個(gè)新的類(lèi)型名時(shí)，就建立一個(gè)葉結(jié)點(diǎn)； 要跟蹤該名字所代表的類(lèi)型表達(dá)式。 在類(lèi)型圖中，如果兩個(gè)類(lèi)型表達(dá)式用相同的結(jié)點(diǎn)表示，則它們是名字等價(jià)的。,type link=cell; np =cell; nqr =cell; var next:link; last:link; p :np; q,r :nqr;,link,pointer,cell,=,pointer,pointer,33,三、類(lèi)型表示中的環(huán),指針和結(jié)點(diǎn)的類(lèi)型定義用Pascal語(yǔ)言描述如下： type link=cell; cell=record info:integer; next:link end; ce

22、ll的類(lèi)型表達(dá)式：,34,C語(yǔ)言的處理,C語(yǔ)言對(duì)除結(jié)構(gòu)（記錄)以外的所有類(lèi)型采用結(jié)構(gòu)等價(jià)的概念，避免在類(lèi)型圖中出現(xiàn)環(huán)路 C語(yǔ)言中對(duì)于cell的類(lèi)型定義如下： struct cell int info; struct cell *next; ,35,5.5 類(lèi)型檢查有關(guān)的其他主題,一、類(lèi)型轉(zhuǎn)換 二、重載 三、多態(tài)性類(lèi)型,36,一、類(lèi)型轉(zhuǎn)換,表達(dá)式：x+i，x為real，i為integer 整型數(shù)和實(shí)型數(shù)在計(jì)算機(jī)中的表示不同，運(yùn)算的機(jī)器指令也不同 編譯程序必須首先轉(zhuǎn)換一個(gè)操作數(shù)，以保證類(lèi)型相同 語(yǔ)言定義指出什么轉(zhuǎn)換是必需的 賦值語(yǔ)句：把賦值號(hào)右邊的對(duì)象轉(zhuǎn)換成左邊對(duì)象的類(lèi)型 表達(dá)式：把整數(shù)轉(zhuǎn)換成實(shí)數(shù)

23、，然后在這一對(duì)實(shí)型對(duì)象上進(jìn)行實(shí)數(shù)運(yùn)算 類(lèi)型檢查器在源程序的中間表示里插入這些轉(zhuǎn)換操作 X+I的后綴式可能是：x i inttoreal real+ 如果從一種數(shù)據(jù)類(lèi)型轉(zhuǎn)換成另一種數(shù)據(jù)類(lèi)型可以由編譯器自動(dòng)完成，則這種類(lèi)型轉(zhuǎn)換是隱式的，隱式轉(zhuǎn)換也叫做強(qiáng)制轉(zhuǎn)換。 一般要求隱式轉(zhuǎn)換原則上不丟失信息 如果轉(zhuǎn)換必須由程序員顯式地寫(xiě)在源程序中，則這種轉(zhuǎn)換叫做顯式轉(zhuǎn)換。 顯式的類(lèi)型轉(zhuǎn)換對(duì)類(lèi)型檢查器來(lái)說(shuō)好象函數(shù)調(diào)用,37,常數(shù)的隱式轉(zhuǎn)換,for I:=1 to N do XI:=1 執(zhí)行時(shí)間：48.4Ns for I:=1 to N do XI:=1.0 執(zhí)行時(shí)間：5.4Ns 編譯器為第一個(gè)語(yǔ)句產(chǎn)生的目標(biāo)代碼含

24、運(yùn)行時(shí)的例程調(diào)用，該例程把1的整型表示轉(zhuǎn)換為實(shí)型表示 大多數(shù)編譯器都在編譯時(shí)把1轉(zhuǎn)換為1.0,38,從整型到實(shí)型的類(lèi)型檢查規(guī)則,39,二、重載,操作符的重載：如果同一操作符名用于了兩個(gè)不同的操作 在數(shù)學(xué)中，加法運(yùn)算符+是重載的 當(dāng)A和B是整數(shù)、實(shí)數(shù)、復(fù)數(shù)或矩陣時(shí)，表達(dá)式A+B中的+具有不同的含義。 重載符號(hào)的含義依賴(lài)于上下文 在重載符號(hào)的引用點(diǎn)，其含義能夠確定到唯一，叫做重載的消除。 重載的消除有時(shí)也稱(chēng)為算符的辨別，因?yàn)樗_定了運(yùn)算符號(hào)表示哪種運(yùn)算。 大多數(shù)語(yǔ)言中，算術(shù)運(yùn)算符是重載的，并且它們的重載可以通過(guò)查看其操作對(duì)象來(lái)消除。,40,函數(shù)或過(guò)程的重載,重載可以擴(kuò)展到用戶(hù)說(shuō)明的函數(shù)或過(guò)程，相關(guān)

25、的操作使用相同的名字，但說(shuō)明不同的參數(shù)或不同的類(lèi)型 例，對(duì)兩個(gè)整數(shù)和實(shí)數(shù)值，定義取最大值的函數(shù) function max(x, y:integer): integer; function max(x, y: real): real; 在Pascal和C中是非法的，在Ada和C+中是合法的，類(lèi)型檢查器可以根據(jù)參數(shù)的類(lèi)型確定要使用哪一個(gè)max函數(shù) 實(shí)現(xiàn)：符號(hào)表保持名字所有可能類(lèi)型的集合，并把這個(gè)集合返回給類(lèi)型檢查器，由類(lèi)型檢查器根據(jù)上下文確定類(lèi)型,41,三、多態(tài)性類(lèi)型,如果允許語(yǔ)言的構(gòu)造有多種類(lèi)型，則語(yǔ)言是多態(tài)性的 如果所有的名字和表達(dá)式都要求有唯一的類(lèi)型，則語(yǔ)言是單態(tài)性的 重載是單態(tài)性要求的一種

26、放松，只能用于相同名字多種獨(dú)立說(shuō)明的情形，當(dāng)單個(gè)說(shuō)明需要用于任意的類(lèi)型時(shí)就出現(xiàn)了另一種不同情形,42,多態(tài)性例子,交換兩個(gè)變量值的過(guò)程在原理上可以用于任何類(lèi)型的變量，只要它們類(lèi)型相同 Procedure swap(var x, y: anytype); 這里anytype被看作是類(lèi)型變量，能假設(shè)成任意實(shí)際的類(lèi)型 可以這樣表達(dá)這個(gè)過(guò)程的類(lèi)型 function swap(var: anytype, var: anytype): void 這樣的類(lèi)型實(shí)際上是類(lèi)型模式或類(lèi)型方案，而不是實(shí)際類(lèi)型 類(lèi)型檢查器對(duì)每次使用swap的情形都需要確定實(shí)際的類(lèi)型，匹配這個(gè)類(lèi)型模式，或說(shuō)明一個(gè)類(lèi)型錯(cuò)誤,43,給定代碼

27、 Var x,y: integer; a,b: char; swap(x,y); swap(a,b); swap(a,x); 在調(diào)用swap(x,y)時(shí)，根據(jù)其給定的多態(tài)性類(lèi)型模式“指定”到單態(tài)類(lèi)型： function swap(var: integer, var: integer): void 在調(diào)用swap(a,b)時(shí)，它被指定類(lèi)型： function swap(var: char, var: char): void 在調(diào)用swap(a,x)時(shí)，它的類(lèi)型為： function swap(var: char, var: integer): void 這個(gè)類(lèi)型不能從swap的類(lèi)型模式通過(guò)替代類(lèi)

28、型變量anytype來(lái)產(chǎn)生 在類(lèi)型檢查算法進(jìn)行這種一般的多態(tài)性類(lèi)型檢查，其中包括復(fù)雜的模式匹配技術(shù)，在現(xiàn)代函數(shù)式語(yǔ)言中有應(yīng)用,44,5.6 符號(hào)表,符號(hào)表在翻譯過(guò)程中起兩方面的重要作用： 檢查語(yǔ)義（即上下文有關(guān)）的正確性 輔助正確地生成代碼 通過(guò)在符號(hào)表中插入和檢索變量的屬性來(lái)實(shí)現(xiàn)的 符號(hào)表是一張動(dòng)態(tài)表 在編譯期間符號(hào)表的入口不斷地增加 在某些情況下又在不斷地刪除 編譯器需要頻繁地與符號(hào)表進(jìn)行交互，符號(hào)表的效率直接影響編譯器的效率。,45,本節(jié)內(nèi)容安排,一、建立和訪(fǎng)問(wèn)符號(hào)表的時(shí)機(jī) 二、符號(hào)表的內(nèi)容 三、在符號(hào)表上的操作 四、符號(hào)表的組織,46,一、建立和訪(fǎng)問(wèn)符號(hào)表的時(shí)機(jī),1. 多遍編譯器,符號(hào)

29、表在詞法分析遍內(nèi)創(chuàng)建，變量在符號(hào)表中的位置作為詞法分析器所產(chǎn)生的記號(hào)的屬性,47,2. 合并遍的編譯器,兩方面的優(yōu)點(diǎn)： 對(duì)語(yǔ)法分析器來(lái)講降低了文法的復(fù)雜性 允許用更系統(tǒng)的方法對(duì)上下文有關(guān)的錯(cuò)誤進(jìn)行檢測(cè)和校正。,48,二、符號(hào)表的內(nèi)容,符號(hào)表中記錄的是和標(biāo)識(shí)符相關(guān)的屬性 出現(xiàn)在符號(hào)表中的屬性種類(lèi)，在一定程度上取決于程序設(shè)計(jì)語(yǔ)言的性質(zhì)。 符號(hào)表的典型形式：,49,變量名,變量名必須常駐內(nèi)存 問(wèn)題： 標(biāo)識(shí)符長(zhǎng)度是可變的 解決辦法： 標(biāo)識(shí)符長(zhǎng)度有限制：設(shè)置一個(gè)長(zhǎng)度固定的域，它的長(zhǎng)度為該語(yǔ)言允許的標(biāo)識(shí)符最大長(zhǎng)度。 標(biāo)識(shí)符長(zhǎng)度沒(méi)有限制：設(shè)置一個(gè)長(zhǎng)度固定的域，域內(nèi)存放一個(gè)串描述符，包含位置指針和長(zhǎng)度兩個(gè)子域

30、，指針域指示該標(biāo)識(shí)符在總的串區(qū)內(nèi)的開(kāi)始位置，長(zhǎng)度域記錄該標(biāo)識(shí)符中的字符數(shù)。,存取速度較高， 存儲(chǔ)空間利用率較低,存取速度較慢， 節(jié)省存儲(chǔ)空間。,50,使用串描述符表示變量,51,目標(biāo)地址,指示運(yùn)行時(shí)變量值存放的相對(duì)位置 對(duì)于靜態(tài)存儲(chǔ)分配的語(yǔ)言（如Fortran），目標(biāo)地址按連續(xù)的順序分配，從1開(kāi)始到m（m是分配給一個(gè)程序的數(shù)據(jù)區(qū)的最大值）。 對(duì)于塊結(jié)構(gòu)的語(yǔ)言(如Pascal)，通常采用二元地址 BL：塊的嵌套深度，用于確定分配給聲明變量的塊的數(shù)據(jù)區(qū)的基址。 NO：變量的目標(biāo)地址偏移量，指示該變量的存儲(chǔ)單元在數(shù)據(jù)區(qū)中相對(duì)于基址的位置。,52,數(shù)據(jù)類(lèi)型,當(dāng)所編譯的語(yǔ)言有數(shù)據(jù)類(lèi)型（隱式或顯式的）時(shí)，

31、必須把類(lèi)型屬性存放到符號(hào)表中。 對(duì)于無(wú)類(lèi)型的語(yǔ)言，可刪除該域。 變量的類(lèi)型屬性用于： 類(lèi)型檢查 生成代碼 空間分配 變量的類(lèi)型以一種編碼形式存放在符號(hào)表中。,53,數(shù)組的維數(shù)/參數(shù)的個(gè)數(shù),數(shù)組引用時(shí)，其維數(shù)應(yīng)當(dāng)與數(shù)組聲明時(shí)定義的維數(shù)一致。 類(lèi)型檢查階段必須對(duì)這種一致性（維數(shù)、每維的長(zhǎng)度）進(jìn)行檢查 維數(shù)用于數(shù)組元素地址的計(jì)算。 過(guò)程調(diào)用時(shí)，實(shí)參必須與形參一致。 實(shí)參的個(gè)數(shù)與形參的個(gè)數(shù)一致 實(shí)參的類(lèi)型與相應(yīng)形參的類(lèi)型一致 在符號(hào)表組織中： 把參數(shù)的個(gè)數(shù)看作它的維數(shù)是很方便的，因此，可將這兩個(gè)屬性合并成一個(gè)。 這種方法也是協(xié)調(diào)的，因?yàn)閷?duì)這兩種屬性所做的類(lèi)型檢查是類(lèi)似的。,54,交叉引用表,編譯程序可

32、以提供的一個(gè)十分重要的程序設(shè)計(jì)輔助工具：交叉引用表 編譯器一般設(shè)一個(gè)選項(xiàng)，用戶(hù)可以選擇是否生成交叉引用表,55,鏈域,為了于便產(chǎn)生按字母順序排列的交叉引用表 如果編譯程序不產(chǎn)生交叉引用表，則鏈域以及語(yǔ)句的行號(hào)屬性都可以從符號(hào)表中刪除。,56,三、在符號(hào)表上的操作,基本操作：插入和檢索 要求變量顯式聲明的強(qiáng)類(lèi)型語(yǔ)言： 編譯器在處理聲明語(yǔ)句時(shí)調(diào)用兩種操作 檢索：查重、確定新表目的位置 插入：建立新的表目 在程序中引用變量名時(shí)，調(diào)用檢索操作 查找信息，進(jìn)行語(yǔ)義分析、代碼生成 可以發(fā)現(xiàn)未定義的名字 允許變量隱式聲明的語(yǔ)言： 標(biāo)識(shí)符的每次出現(xiàn)都按首次出現(xiàn)處理 檢索： 已經(jīng)聲明，進(jìn)行類(lèi)型檢查，. 首次出現(xiàn)

33、，插入操作，從其作用推測(cè)出該變量的全部屬性,57,定位和重定位操作,對(duì)于塊結(jié)構(gòu)的語(yǔ)言，在建立和刪除符號(hào)表時(shí)還要使用兩種附加的操作，即定位和重定位。 當(dāng)編譯器識(shí)別出塊的開(kāi)始時(shí)，執(zhí)行定位操作。 當(dāng)編譯器遇到塊的結(jié)束時(shí)，執(zhí)行重定位操作。 定位操作： 建立一個(gè)新的子表（包含于符號(hào)表中），在該塊中聲明的所有變量的屬性都存放在此子表中。 重定位操作： 刪除存放該塊中局部變量的子表 這些變量的作用域局部于該塊，出了該塊后這些變量不能再被引用。 不同分程序中的相同變量名問(wèn)題的解決方法： 分程序是按層次嵌套的，如果多層嵌套（如n層），那么這些子符號(hào)表也是多層嵌套，并按序生成（即先產(chǎn)生子符號(hào)表1，最后產(chǎn)生子符號(hào)表

34、n）。 在第n層分程序需要查找某一標(biāo)識(shí)符時(shí)，先從子符號(hào)表n開(kāi)始查找，如果未查到，再依次查子符號(hào)表n-1,n-2,1，如果在符號(hào)表i首先出現(xiàn)該標(biāo)識(shí)符名，這便正是所要查找的結(jié)果,58,符號(hào)表的邏輯結(jié)構(gòu),59,四、符號(hào)表的組織,1. 非塊結(jié)構(gòu)語(yǔ)言的符號(hào)表組織 2. 塊結(jié)構(gòu)語(yǔ)言的符號(hào)表組織,60,1. 非塊結(jié)構(gòu)語(yǔ)言的符號(hào)表組織,非塊結(jié)構(gòu)語(yǔ)言： 編寫(xiě)的每一個(gè)可獨(dú)立編譯的程序單元是一個(gè)不含子模塊的單一模塊 模塊中聲明的所有變量屬于整個(gè)模塊 符號(hào)表組織 無(wú)序線(xiàn)性表 屬性記錄按變量聲明/出現(xiàn)的先后順序填入表中 插入前都要進(jìn)行檢索，若發(fā)現(xiàn)同名變量 對(duì)顯式聲明的語(yǔ)言：錯(cuò)誤 對(duì)隱式聲明的語(yǔ)言：引用 適用于程序中出現(xiàn)

35、的變量很少的情況,61,散列表 查找時(shí)間與表中記錄數(shù)無(wú)關(guān)的一種符號(hào)表組織方式,有序線(xiàn)性表 按字母順序?qū)ψ兞棵判虻谋?避免了對(duì)整個(gè)表的查找 線(xiàn)性查找： 當(dāng)遇到第一個(gè)比查找變量名值大的項(xiàng)目時(shí)，就可以判定該變量名不在表中了。 當(dāng)執(zhí)行插入操作時(shí)，要增加額外的比較和移動(dòng)操作。 若使用單鏈結(jié)構(gòu)表的話(huà)，可省去表記錄的移動(dòng)，但需要在每個(gè)表記錄中增加一個(gè)鏈接字段。 折半查找： 首先把變量名與中間項(xiàng)進(jìn)行比較，結(jié)果或是找到該變量名，或是指出下一次要在哪半張表中進(jìn)行。 重復(fù)此過(guò)程，直到找到該變量名或確定該變量名不在表中為止。,62,散列函數(shù)H,除法：最常用的散列函數(shù)，H(x)=(x mod m)+1，通常m為 一個(gè)

36、大的素?cái)?shù)，這樣可使標(biāo)識(shí)符盡可能均勻地分散在表中 中平方散列法：先將標(biāo)識(shí)符進(jìn)行平方運(yùn)算，然后將結(jié)果的兩頭幾個(gè)值或數(shù)字去掉，直到剩下的位數(shù)或數(shù)字等于所期望的地址，必須對(duì)所有的標(biāo)識(shí)符的平方值進(jìn)行同樣的處理。 折疊法：標(biāo)識(shí)符被分成若干段，可能除最后一段外，每一段與所需地址具有同樣長(zhǎng)度，然后各段加起來(lái)，忽略最后的進(jìn)位，以構(gòu)成一個(gè)地址。 長(zhǎng)度相關(guān)法：變量名的長(zhǎng)度和名字的某個(gè)部分一起用來(lái)直接產(chǎn)生一個(gè)表地址，或更普遍的方法是產(chǎn)生一個(gè)有用的中間字，然后用除法產(chǎn)生一個(gè)最終的表地址。,63,解決沖突的方法,變量名被映射到一個(gè)存儲(chǔ)單元d中，而這個(gè)單元已被占用 開(kāi)放地址法 分離鏈表法,按照順序d,d+1,m,1,2,d

37、-1進(jìn)行掃描，直到找到一個(gè)空閑的存儲(chǔ)單元為止，或者在掃描完m個(gè)單元之后搜索停止 在查找一個(gè)記錄時(shí)，按同樣的順序掃描，或找到要找的記錄、或找到一個(gè)空閑單元（從未使用過(guò)）為止,將發(fā)生沖突的記錄鏈到一個(gè)專(zhuān)門(mén)的溢出區(qū)，該溢出區(qū)與主區(qū)相分離 為每一組沖突的記錄設(shè)置一個(gè)鏈表，主區(qū)和溢出區(qū)的每一個(gè)記錄都必須有一個(gè)鏈接字段。 為節(jié)省存儲(chǔ)空間，建立一個(gè)中間表（散列表），所有記錄都存入溢出區(qū)，而主區(qū)（散列表）只有鏈域,64,示意圖,65,2. 塊結(jié)構(gòu)語(yǔ)言的符號(hào)表組織,塊結(jié)構(gòu)語(yǔ)言： 模塊中可嵌套子塊 子塊中可以定義局部變量。 每個(gè)塊應(yīng)有一個(gè)子表 符號(hào)表組織 棧式符號(hào)表 當(dāng)遇到變量聲明時(shí)，將包含變量屬性的記錄入棧 當(dāng)?shù)竭_(dá)塊結(jié)尾時(shí)，將該塊中聲明的所有變量的記錄出棧 因?yàn)檫@些變量是局部于該塊的，在塊外已不可用的。,66,棧式符號(hào)表,readarray x a,exchange,quicksort,67,操作,插入 檢查子表中是否有重名變量 無(wú)，將新記錄推入棧頂單元 有，報(bào)告錯(cuò)誤 檢索 從