北郵計算機(jī)科學(xué)與技術(shù)專業(yè)課設(shè)要求大三編譯原理ch06

第6章語義分析知識點(diǎn)：符號表

類型體制

各語法成分的類型檢查

2語義分析6.1語義分析的任務(wù)和地位6.2符號表6.3符號表的建立6.4類型檢查6.5一個簡單類型檢查程序的說明6.6類型檢查有關(guān)的其他主題小結(jié)36.1語義分析的任務(wù)和地位程序設(shè)計語言的結(jié)構(gòu)由上下文無關(guān)文法來描述程序結(jié)構(gòu)正確與否與該結(jié)構(gòu)的上下文有關(guān)，如：變量的作用域問題同一作用域內(nèi)同名變量的重復(fù)聲明問題表達(dá)式、賦值語句中的操作數(shù)的類型一致性問題思考：設(shè)計上下文有關(guān)文法來描述語言中上下文有關(guān)的結(jié)構(gòu)？理論上可行，構(gòu)造有困難，構(gòu)造相應(yīng)的分析程序更困難解決辦法：設(shè)計專門的語義動作補(bǔ)充上下文無關(guān)文法的分析程序利用語法制導(dǎo)翻譯技術(shù)實(shí)現(xiàn)語義分析4上下文有關(guān)信息的記錄與使用符號表記錄編譯過程中識別出的上下文有關(guān)的信息，如：變量的類型相對地址信息的引用根據(jù)詞法分析程序識別出的標(biāo)識符的屬性值（標(biāo)識符在符號表中的入口），查找符號表中對應(yīng)該標(biāo)識符的記錄，從而可以取得該標(biāo)識符有關(guān)的信息。如果編譯的程序塊處于該變量的作用域內(nèi)，則這個變量將一直保留在符號表中5語義檢查動態(tài)檢查：目標(biāo)程序運(yùn)行時進(jìn)行的檢查靜態(tài)檢查：讀入源程序、但不執(zhí)行源程序的情況下進(jìn)行的檢查類型檢查對訪問數(shù)據(jù)的操作和被訪問數(shù)據(jù)的類型進(jìn)行檢查，檢查操作的合法性和數(shù)據(jù)類型的相容性?？刂屏鳈z查檢查控制語句是否使控制轉(zhuǎn)移到一個合法的位置。唯一性檢查一個標(biāo)識符在同一程序塊中必須而且只能被說明一次CASE語句中用于匹配選擇表達(dá)式的常量必須各不相同枚舉類型定義中的各元素不允許重復(fù)關(guān)聯(lián)名字的檢查6類型檢查由類型檢查程序完成檢驗(yàn)結(jié)構(gòu)的類型是否和它的上下文所期望的一致，如：表達(dá)式中各運(yùn)算對象的類型算術(shù)運(yùn)算符mod的運(yùn)算對象的類型用戶定義函數(shù)的各參數(shù)類型、返回值類型7語義分析程序的作用和地位語義分析程序的作用符號表的建立和管理類型檢查語義分析程序的地位語法分析程序語義分析程序中間代碼生成程序記號流語法樹語法樹中間代碼生成目標(biāo)代碼時會用到語義分析的結(jié)果重載運(yùn)算符：一個運(yùn)算符在不同的上下文中表示不同的運(yùn)算類型強(qiáng)制：編譯程序把運(yùn)算對象變換為上下文所期望的類型86.2符號表符號表在翻譯過程中起兩方面的重要作用：檢查語義（即上下文有關(guān)）的正確性輔助正確地生成代碼通過在符號表中插入和檢索變量的屬性來實(shí)現(xiàn)的符號表是一張動態(tài)表在編譯期間符號表的入口不斷地增加在某些情況下又在不斷地刪除編譯程序需要頻繁地與符號表進(jìn)行交互，符號表的效率直接影響編譯程序的效率。9符號表一、符號表的建立和訪問時機(jī)二、符號表內(nèi)容三、符號表操作四、符號表組織10一、符號表的建立和訪問時機(jī)1.多遍編譯程序變量在符號表中的位置作為詞法分析程序產(chǎn)生的記號的屬性112.合并遍的編譯程序兩方面的優(yōu)點(diǎn)：對語法分析程序來講降低了文法的復(fù)雜性允許用更系統(tǒng)的方法對上下文有關(guān)的錯誤進(jìn)行檢測和校正。12二、符號表內(nèi)容符號表中記錄的是和標(biāo)識符相關(guān)的屬性出現(xiàn)在符號表中的屬性種類，在一定程度上取決于程序設(shè)計語言的性質(zhì)。符號表的典型形式：

變量名目標(biāo)地址類型維數(shù)聲明行引用行指針

1count021 29,14,1572x_total410 312,1403form832 436,37,3864b_loop4810 510,11,1315able_n5210 511,23,2546mlist5660 617,2127flag6410 728,29313變量名變量名必須常駐內(nèi)存問題：標(biāo)識符長度是可變的解決辦法：標(biāo)識符長度有限制：設(shè)置一個長度固定的域，它的長度為該語言允許的標(biāo)識符最大長度。標(biāo)識符長度沒有限制：設(shè)置一個長度固定的域，域內(nèi)存放一個串描述符，包含位置指針和長度兩個子域，指針域指示該標(biāo)識符在總的串區(qū)內(nèi)的開始位置，長度域記錄該標(biāo)識符中的字符數(shù)。14使用串描述符表示變量countx_totalb_loop位置長度變量名其他屬性1567136………15目標(biāo)地址指示運(yùn)行時變量值存放的相對位置對于靜態(tài)存儲分配的語言（如Fortran），目標(biāo)地址按連續(xù)的順序分配，從0開始到m（m是分配給一個程序的數(shù)據(jù)區(qū)的最大值）。對于塊結(jié)構(gòu)的語言(如Pascal)，通常采用二元地址<BL,NO>BL：塊的嵌套深度，用于確定分配給聲明變量的塊的數(shù)據(jù)區(qū)的基址。NO：變量的目標(biāo)地址偏移量，指示該變量的存儲單元在數(shù)據(jù)區(qū)中相對于基址的位置。16數(shù)據(jù)類型當(dāng)所編譯的語言有數(shù)據(jù)類型（隱式或顯式的）時，必須把類型屬性存放到符號表中。對于無類型的語言，可刪除該域。變量的類型屬性用于：類型檢查生成代碼空間分配變量的類型以一種編碼形式存放在符號表中。17數(shù)組的維數(shù)/參數(shù)的個數(shù)數(shù)組引用時，其維數(shù)應(yīng)當(dāng)與數(shù)組聲明時定義的維數(shù)一致。類型檢查階段必須對這種一致性（維數(shù)、每維的長度）進(jìn)行檢查維數(shù)用于數(shù)組元素地址的計算。過程調(diào)用時，實(shí)參必須與形參一致。實(shí)參的個數(shù)與形參的個數(shù)一致實(shí)參的類型與相應(yīng)形參的類型一致在符號表組織中：把參數(shù)的個數(shù)看作它的維數(shù)是很方便的，因此，可將這兩個屬性合并成一個。這種方法也是協(xié)調(diào)的，因?yàn)閷@兩種屬性所做的類型檢查是類似的。18交叉引用表編譯程序可以提供的一個十分重要的程序設(shè)計輔助工具：交叉引用表編譯程序一般設(shè)一個選項，用戶可以選擇是否生成交叉引用表

變量名類型維數(shù)聲明行引用行

able_n10511,23,25 b_loop10510,11,13 count2129,14,15 flag10728,29 form32436,37,38 mlist60617,21 x_total10312,1419鏈域?yàn)榱吮阌诋a(chǎn)生按字母順序排列的交叉引用表如果編譯程序不產(chǎn)生交叉引用表，則鏈域以及語句的行號屬性都可以從符號表中刪除。20三、符號表操作最常執(zhí)行的操作：插入和檢索要求變量顯式聲明的強(qiáng)類型語言：編譯程序在處理聲明語句時調(diào)用兩種操作檢索：查重、確定新表目的位置插入：建立新的表目在程序中引用變量名時，調(diào)用檢索操作查找信息，進(jìn)行語義分析、代碼生成可以發(fā)現(xiàn)未定義的名字允許變量隱式聲明的語言：標(biāo)識符的每次出現(xiàn)都按首次出現(xiàn)處理檢索：已經(jīng)聲明，進(jìn)行類型檢查，...首次出現(xiàn)，插入操作，從其作用推測出該變量的全部屬性21定位和重定位操作對于塊結(jié)構(gòu)的語言，在建立和刪除符號表時還要使用兩種附加的操作，即定位和重定位。當(dāng)編譯程序識別出塊的開始時，執(zhí)行定位操作。當(dāng)編譯程序遇到塊的結(jié)束時，執(zhí)行重定位操作。定位操作：建立一個新的子表（包含于符號表中），在該塊中聲明的所有變量的屬性都存放在此子表中。重定位操作：“刪除”存放該塊中局部變量的子表這些變量的作用域局部于該塊，出了該塊后這些變量不能再被引用。22programsort(input,output);vara:array[0..10]ofinteger;x:integer;procedurereadarray;vari:integer;beginfori:=1to9doread(a[i])end;procedureexchange(i,j:integer)beginx:=a[i];a[i]:=a[j];a[j]:=xend;peocedurequicksort(m,n:integer);vark,v:integer;functionpartition(y,z:integer):integer;vari,j:integer;begin…a…；

…v…；

exchange(i,j);……end;begin……end;{quicksort}begin……end.{sort}讀入數(shù)據(jù)，并進(jìn)行排序的PASCAL程序23符號表的邏輯結(jié)構(gòu)sortnilheadarea

readarrayreadarrayheadareaiexchangeexchangeheadareaquicksortquicksortheadareakvpartitionpartitionheadarea

ijax24四、符號表組織1.非塊結(jié)構(gòu)語言的符號表組織2.塊結(jié)構(gòu)語言的符號表組織251.非塊結(jié)構(gòu)語言的符號表組織非塊結(jié)構(gòu)語言：編寫的每一個可獨(dú)立編譯的程序單元是一個不含子模塊的單一模塊模塊中聲明的所有變量屬于整個模塊符號表組織無序線形表屬性記錄按變量聲明/出現(xiàn)的先后順序填入表中插入前都要進(jìn)行檢索，若發(fā)現(xiàn)同名變量對顯式聲明的語言：錯誤對隱式聲明的語言：引用適用于程序中出現(xiàn)的變量很少的情況26散列表查找時間與表中記錄數(shù)無關(guān)的一種符號表組織方式名字空間K地址空間A散列函數(shù)H有序線形表按字母順序?qū)ψ兞棵判虻谋肀苊饬藢φ麄€表的查找線性查找：當(dāng)遇到第一個比查找變量名值大的項目時，就可以判定該變量名不在表中了。當(dāng)執(zhí)行插入操作時，要增加額外的比較和移動操作。若使用單鏈結(jié)構(gòu)表的話，可省去表記錄的移動，但需要在每個表記錄中增加一個鏈接字段。折半查找：首先把變量名與中間項進(jìn)行比較，結(jié)果或是找到該變量名，或是指出下一次要在哪半張表中進(jìn)行。重復(fù)此過程，直到找到該變量名或確定該變量名不在表中為止。272.塊結(jié)構(gòu)語言的符號表組織塊結(jié)構(gòu)語言：模塊中可嵌套子塊子塊中可以定義局部變量。每個塊應(yīng)有一個子表符號表組織棧式符號表當(dāng)遇到變量聲明時，將包含變量屬性的記錄入棧當(dāng)?shù)竭_(dá)塊結(jié)尾時，將該塊中聲明的所有變量的記錄出棧因?yàn)檫@些變量是局部于該塊的，在塊外已不可用的。28棧式符號表10j9i8partition7v6k5quicksort4exchange3readarray2x1a961top

棧式符號表塊索引表變量名屬性29操作插入檢查子表中是否有重名變量無，將新記錄推入棧頂單元有，報告錯誤檢索從棧頂?shù)綏５拙€性檢索在當(dāng)前子表中找到，局部變量在其他子表中找到，非局部名字根據(jù)最近嵌套作用域原則，選擇變量的記錄30

定位將下一個可用的棧頂單元的地址壓入塊索引表的頂端塊索引表的元素是指針，指向相應(yīng)塊的子表中第一個記錄在棧中的位置重定位有效地清除剛剛被編譯完的塊在棧式符號表中的所有記錄用塊索引表頂端元素的值恢復(fù)棧頂指針top，完成重定位操作top指示符號表棧頂?shù)谝粋€空閑的記錄存儲單元。31棧式散列符號表假設(shè)散列表的大小為11，散列函數(shù)執(zhí)行如下變換：

名字映射到地址

a、quicksort1 x、v、j3partition4 i5 k、readarray8 exchange113210top61toptoptoptop棧式散列符號表示意圖109876543219top棧式符號表塊索引表1234567891011Hash表變量名屬性鏈axreadarrayexchangequicksortkvpartitionij64top5toptop8top9top33操作插入散列函數(shù)將變量名映射到散列表單元是否存在沖突？該表單元是否為空？無沖突：將棧指針的值記入該散列表單元將新記錄推入棧頂有沖突檢查沖突鏈中是否有同名變量沒有：將新記錄插入沖突鏈的鏈頭有：檢查同名變量是否屬于當(dāng)前子表同名變量在棧中的位置>=塊索引表頂端元素的值？

>=：在當(dāng)前子表中，報告錯誤

<：不在當(dāng)前子表中，將新記錄插入沖突鏈的鏈頭34名字引用時檢索散列函數(shù)將變量名映射到散列表單元該散列表單元是否為空？空：名字未定義，報告錯誤不空：沿沖突鏈檢索未找到：名字未定義，報告錯誤找到：名字在棧中的位置>=塊索引表頂端元素的值>=：局部名字

<：非局部名字35定位與重定位定位當(dāng)識別到一個新塊時，要為之創(chuàng)建子表將下一個可用的棧頂單元的地址壓入塊索引表的頂端標(biāo)識新塊符號子表的開始位置重定位當(dāng)一個塊編譯完成時，它的有關(guān)記錄必須邏輯上或物理上從符號表中除去。用塊索引表頂端單元的值確定要刪除的棧單元依次取出棧單元中的名字通過散列函數(shù)將該名字映射到散列表單元從鏈中把鏈頭記錄刪除重復(fù)，直到新鏈頭在棧中的位置<塊索引表頂端單元的值用塊索引表頂端單元的值設(shè)置棧頂指針TOP366.3符號表的建立處理聲明語句時，編譯程序的任務(wù)分離出每一個被聲明的實(shí)體，并將它的名字填入符號表中；盡可能多地將有關(guān)該實(shí)體的信息填入符號表。聲明語句的形式類型關(guān)鍵字的位置標(biāo)識符表的前面標(biāo)識符表的后面標(biāo)識符表單一實(shí)體多個同類型的實(shí)體不同種類的實(shí)體37源語言的說明聲明部分的文法P

D；SD

D；D|D

id：T|D

procid；D；ST

integer|real

|array[num]ofT1

|

T1

|recordDend所有名字必須先聲明后引用變量聲明、每個聲明語句聲明一個名字過程聲明、過程聲明允許嵌套38一、過程中的聲明語句假定最內(nèi)層過程暫時不考慮記錄結(jié)構(gòu)的聲明聲明語句的文法P

D；S D

D；D D

id：T T

integer T

real T

array[num]ofT1

T

T139設(shè)計翻譯方案的目的識別出被聲明實(shí)體記錄實(shí)體的名字、類型、在數(shù)據(jù)區(qū)中的位置引入：全局變量offset，記錄下一個可用單元的相對地址T.width：記錄實(shí)體的域?qū)扵.type：記錄實(shí)體的類型enter(，T.type，offset)name1name2name3...0n1n1n2n3n1+n240翻譯方案1P

D;S D

D;D D

id:T

T

integer T

real T

array[num]ofT1T

T1 {enter(,T.type,offset); offset=offset+T.width}{T.type=integer;T.width=4}{T.type=real;T.width=8}{T.type=array(num.val,T1.type);T.width=num.val

T1.width}{T.type=pointer(T1.type);T.width=4} {offset=0}P

MDM

{offset=0}41二、過程定義的處理作用域信息的保存文法P

D；SD

D；DD

id：TD

procid；D；ST

integer T

real T

array[num]ofT1T

T142數(shù)據(jù)結(jié)構(gòu)及過程記錄符號表嵌套關(guān)系的、便于操作的結(jié)構(gòu)：棧tableptroffsett1offset1t2offset2Pqrqrt1t2t3t3offset3過程：maketable(previous)enter(table,name,type,offset)addwidth(table,width)enterproc(table,name,newtable)43翻譯方案2PMDM

D

D；DD

id：TD

procid；ND；SN

{t=maketable(nil);push(t,tableptr);push(0,offset)}{enter(top(tableptr),,T.type,top(offset));top(offset)=top(offset)+T.width}{t=maketable(top(tableptr));push(t,tableptr);push(0,offset)}{t=top(tableptr);addwidth(t,top(offset));pop(tableptr);pop(offset);enterproc(top(tableptr),,t)}{addwidth(top(tableptr),top(offset));pop(tableptr);pop(offset)}44三、記錄聲明的處理文法P

D；SD

D；DD

id：TD

procid；D；ST

recordDend翻譯方案3T

recordLDendL

{t=mktable(nil);push(t,tableptr);push(0,offset)}{T.type=record(top(tableptr));T.width=top(offset);pop(tableptr);pop(offset)}45舉例聲明x:integer;q:recordi:integer;x:realend；y:real;tableptroffsett4txinteger0iinteger0t

t

04xreal412T.type=record(t

)T.width=12qrecord(t

)416yreal1624466.4類型檢查靜態(tài)類型檢查：由編譯程序完成的檢查動態(tài)類型檢查：目標(biāo)程序運(yùn)行時完成的檢查如果目標(biāo)代碼把每個對象的類型和該對象的值一起保存，那么任何檢查都可以動態(tài)完成。一個健全的類型體制不需要動態(tài)檢查類型錯誤如果一種語言的編譯程序能夠保證它所接受的程序不會有運(yùn)行時的類型錯誤，則稱這種語言是強(qiáng)類型語言。有些檢查只能動態(tài)完成table:array[0..255]ofchar;i:integer;計算table[i]47靜態(tài)類型檢查設(shè)計類型檢查程序時要考慮的因素：語法結(jié)構(gòu)類型概念把類型指派給語言結(jié)構(gòu)的規(guī)則Pascal、C語言報告中關(guān)于類型的描述：如果算術(shù)運(yùn)算符加、減和乘的兩個運(yùn)算對象都是整型，那么結(jié)果是整型。一元運(yùn)算符&的結(jié)果是指向運(yùn)算對象所代表的實(shí)體的指針，如果運(yùn)算對象的類型是‘…’，結(jié)果類型就是指向‘…’的指針。暗示的概念：每一個表達(dá)式有一個類型類型有結(jié)構(gòu)48類型體制把類型表達(dá)式指派到程序各部分的一組規(guī)則由類型檢查程序?qū)崿F(xiàn)同一語言的不同編譯程序使用的類型體制可能不同數(shù)組作為變元傳遞時，數(shù)組的下標(biāo)集合可以指明，也可以不指明原因：不同的Pascal語言編譯程序?qū)崿F(xiàn)的類型體制不同UNIX系統(tǒng)中，lint命令實(shí)現(xiàn)的類型體制比C語言編譯程序本身所實(shí)現(xiàn)的更詳細(xì)。49一、類型表達(dá)式類型表達(dá)式的定義：基本類型是類型表達(dá)式boolean、char、integer、和real錯誤類型type_error、回避類型void類型名是類型表達(dá)式，因?yàn)轭愋捅磉_(dá)式可以命名。類型構(gòu)造器作用于類型表達(dá)式的結(jié)果仍是類型表達(dá)式數(shù)組：如果T是類型表達(dá)式，那么array(I，T)是元素類型為T和下標(biāo)集合為I的數(shù)組的類型表達(dá)式，I通常是一個整數(shù)域。

varA:array[1..10]ofinteger;

與A相關(guān)的類型表達(dá)式為：array(1..10,integer)笛卡兒積：如果T1和T2是類型表達(dá)式，那么它們的笛卡兒積T1

T2也是類型表達(dá)式，假定

是左結(jié)合的。記錄：記錄類型是它的各域類型的笛卡兒積把類型構(gòu)造器record作用于由域名和與之相關(guān)的類型表達(dá)式組成的二元組，就形成記錄的類型表達(dá)式50

如Pascal的程序片段：typerow=recordaddress:integer;lexeme:array[1..15]ofcharend;vartable:array[1..10]ofrow;

類型名row代表類型表達(dá)式:record((address

integer)

(lexeme

array(1..15,char)))

和變量table相關(guān)的類型表達(dá)式為：

array(1..10,row)指針：如果T是類型表達(dá)式，那么pointer(T)是類型“指向類型T的對象的指針”的類型表達(dá)式。

varp:

row;

與P相關(guān)的類型表達(dá)式為：

pointer(row)51

函數(shù)：從定義域類型D到值域類型R的映射

類型由類型表達(dá)式D

R表示。Pascal的內(nèi)部函數(shù)mod：

int

int

int用戶定義的Pascal函數(shù)：functionf(a,b:char):

integer;f的類型表達(dá)式：char

char

pointer(integer)函數(shù)g：參數(shù)是把整數(shù)映射成整數(shù)的函數(shù)返回結(jié)果是和參數(shù)類型相同的另一函數(shù)g的類型表達(dá)式為：

(integer

integer)

(integer

integer)類型表達(dá)式可以包含變量（稱為類型變量），變量的值是類型表達(dá)式。52類型表達(dá)式的有向圖利用語法制導(dǎo)翻譯技術(shù)為類型表達(dá)式構(gòu)造樹或dag內(nèi)部結(jié)點(diǎn)：類型構(gòu)造器葉結(jié)點(diǎn)：基本類型、類型名、或類型變量如：char

char

pointer(integer)

pointercharcharinteger

pointercharinteger樹：dag：53二、類型等價關(guān)鍵：精確地定義什么情況下兩個類型表達(dá)式等價問題：類型表達(dá)式可以命名，且這個名字可用于隨后的類型表達(dá)式中名字代表它自己？代表另一個類型表達(dá)式？新的名稱是一個類型表達(dá)式，這個表達(dá)式與名稱所代表的類型表達(dá)式是否總是等價的？541.結(jié)構(gòu)等價如果類型表達(dá)式僅由類型構(gòu)造器作用于基本類型組成，則兩個類型表達(dá)式等價的自然概念是結(jié)構(gòu)等價兩個類型表達(dá)式要么是同樣的基本類型要么是同樣的構(gòu)造器作用于結(jié)構(gòu)等價的類型表達(dá)式。兩個類型表達(dá)式結(jié)構(gòu)等價當(dāng)且僅當(dāng)它們完全相同例如：

integer僅等價于integerpointer(integer)僅等價于pointer(integer)55測試兩個類型表達(dá)式結(jié)構(gòu)等價的算法輸入：兩個類型表達(dá)式s和t輸出：如果s和t結(jié)構(gòu)等價，則返回true，否則返回false方法：boolsequiv(bexprs,t){if(s和t是同樣的基本類型)return1;elseif(s==array(s1,s2))&&(t==array(t1,t2))returnsequiv(s1,t1)&&sequiv(s2,t2);elseif(s==s1

s2)&&(t==t1

t2)returnsequiv(s1,t1)&&sequiv(s2,t2);elseif(s==pointer(s1))&&(t==pointer(t1))returnsequiv(s1,t1);elseif(s==s1

s2)&&(t==t1

t2)returnsequiv(s1,t1)&&sequiv(s2,t2);elsereturn0;}.56實(shí)際應(yīng)用中結(jié)構(gòu)等價概念的修改當(dāng)數(shù)組作為參數(shù)傳遞時，數(shù)組的界不作為類型的一部分算法調(diào)整elseif(s==array(s1,s2))&&(t==array(t1,t2))returnsequiv(s2,t2);57編碼測試方法對基本類型規(guī)定確定位數(shù)、確定位置的二進(jìn)制編碼；對類型構(gòu)造器規(guī)定確定位數(shù)的二進(jìn)制編碼類型表達(dá)式可用一組二進(jìn)制編碼表示例：D.M.Ritchie的C編譯程序中類型表達(dá)式的編碼方式類型構(gòu)造器：pointer(t)指向類型t的指針freturn(t)含有參數(shù)的函數(shù)，返回類型t的對象array(t)元素類型為t的數(shù)組（不定長度）一元運(yùn)算符，類型表達(dá)式具有統(tǒng)一的結(jié)構(gòu)

charfreturn(char)pointer(freturn(char))array(pointer(freturn(char)))58編碼方式類型構(gòu)造器的編碼

類型構(gòu)造器編碼

pointer01array10freturn11基本類型的編碼

基本類型編碼

Boolean0000Char0001Integer0010Real0011類型表達(dá)式及其二進(jìn)制編碼示例

類型表達(dá)式二進(jìn)制編碼

char0000000001freturn(char)0000110001pointer(freturn(char))0001110001array(pointer(freturn(char)))100111000159有些語言(如Pascal)允許用戶定義類型名Pascal類型定義和變量聲明：

typelink=

cell;varnext:link;last:link;p:

cell;q,r:

cell;問題：next、last、p、q和r是否具有相同的類型關(guān)鍵：類型表達(dá)式link和類型表達(dá)式

cell是否等價回答：依賴于具體的實(shí)現(xiàn)系統(tǒng)原因：Pascal報告中沒有定義“類型等價”這個術(shù)語2.名字等價60名字等價把每個類型名看成是一個可區(qū)別的類型兩個類型表達(dá)式名字等價，當(dāng)且僅當(dāng)它們完全相同所有的名字被替換后，兩個類型表達(dá)式成為結(jié)構(gòu)等價的類型表達(dá)式，那么這兩個表達(dá)式結(jié)構(gòu)等價。聲明中的變量及其類型表達(dá)式：

變量類型表達(dá)式

nextlinklastlinkppointer(cell)qpointer(cell)rpointer(cell)考慮名字等價的情形考慮結(jié)構(gòu)等價的情形61標(biāo)識符與類型通過聲明相聯(lián)系的規(guī)則舉例Pascal的許多編譯程序用隱含的類型名與每個聲明的標(biāo)識符相聯(lián)系如果聲明中出現(xiàn)了沒有名字的類型表達(dá)式，則建立一個隱含的類型名。每當(dāng)聲明中出現(xiàn)類型表達(dá)式時，就建立一個新的類型名。typelink=

cell;varnext:link;last:link;p:

cell;q,r:

cell;typelink=

cell;np=

cell;nqr=

cell;varnext:link;last:link;p:np;q,r:nqr;62類型圖類型圖表示類型構(gòu)造方法：每當(dāng)出現(xiàn)一個類型構(gòu)造器或基本類型，就建立一個新的結(jié)點(diǎn)；每當(dāng)出現(xiàn)一個新的類型名時，就建立一個葉結(jié)點(diǎn)；要跟蹤該名字所代表的類型表達(dá)式。在類型圖中，如果兩個類型表達(dá)式用相同的結(jié)點(diǎn)表示，則它們是名字等價的。typelink=

cell;np=

cell;nqr=

cell;varnext:link;last:link;p:np;q,r:nqr;linkpointercell=pointerpointernextlastqrp633.類型表示中的環(huán)指針和結(jié)點(diǎn)的類型定義用Pascal語言描述如下：typelink=

cell;cell=recordinfo:integer;next:linkend;cell的類型表達(dá)式：cell=record×××infointnextlinkcell=record×××infointnextpointercellcell=record×××infointnextpointer646.5一個簡單類型檢查程序的說明利用語法制導(dǎo)方法說明類型體制一、語言說明二、確定標(biāo)識符的類型三、表達(dá)式的類型檢查四、語句的類型檢查五、類型轉(zhuǎn)換65一、語言說明源語言文法：P

D;SD

D;D|id:TT

char|integer|boolean|array[num]ofT|

T|T1’’T2S

id:=E|ifEthenS1|whileEdoS1|S1;S2E

literal|num|id|id1<id2|E1andE2

|E1modE2|E1[E2]|E

|E1(E2)該文法產(chǎn)生的一個程序：k:integer;k:=kmod200766二、確定標(biāo)識符的類型語言中的類型：基本類型：char、integer、和booleantype_error和void構(gòu)造類型：數(shù)組、指針和函數(shù)假定：數(shù)組下標(biāo)從1開始類型array[256]ofchar的類型表達(dá)式是：array(1..256,char)前綴算符

用于建立指針類型

integer的類型表達(dá)式是pointer(integer)函數(shù)類型由定義域類型和值域類型確定67翻譯方案中

確定并保存標(biāo)識符類型的部分P

D;SD

D;DD

id:TT

charT

integerT

booleanT

array[num]ofT1T

T1T

T1

T2{addtype(id.entry,T.type)}{T.type=char}{T.type=integer}{T.type=boolean}{T.type=array(num.val,T1.type)}{T.type=pointer(T1.type)}{T.type=T1.type

T2.type}引入綜合屬性T.type，記錄類型表達(dá)式68三、表達(dá)式的類型檢查E

literalE

numE

idE

id1>id2E

E1andE2E

E1modE2E

E1[E2]E

E1

E

E1(E2)綜合屬性E.type，類型體制指派給E產(chǎn)生的表達(dá)式的類型表達(dá)式{E.type=char}{E.type=integer}{E.type=lookup(id.entry)}{if(lookup(id1.entry)==integer)&&(lookup(id2.entry)==integer)||

(lookup(id1.entry)==char)&&(lookup(id2.entry)==char)

E.type=boolean;elseE.type=type_error;}69E

E1andE2E

E1modE2E

E1[E2]E

E1

E

E1(E2){if(E1.type==Boolean)&&(E2.type==Boolean)

E.type=Boolean;elseE.type=type_error;}{if(E1.type==integer)&&(E2.type==integer)

E.type=integer;elseE.type=type_error;}{if(E1.type==array(s,t))&&(E2.type==integer)

E.type=t;elseE.type=type_error;}70E

E1

E

E1(E2){if(E1.type==pointer(t))

E.type=t;elseE.type=type_error;}{if(E1.type==s

t)&&(E2.type==s)

E.type=t;elseE.type=type_error;}71四、語句的類型檢查S

id:=ES

ifEthenS1

S

whileEdoS1S

S1;S2{if(lookup(id.entry)==E.type)

S.type=void;elseS.type=type_error;}{if(E.type==boolean)

S.type=S1.type;elseS.type=type_error;}{if(E.type==boolean)

S.type=S1.type;elseS.type=type_error;}{if(S1.type==void)&&(S2.type==void)

S.type=void;elseS.type=type_error;}72五、類型轉(zhuǎn)換表達(dá)式：x+i整型數(shù)和實(shí)型數(shù)在計算機(jī)中的表示不同用于整型運(yùn)算和實(shí)型運(yùn)算的機(jī)器指令也不同xiinttorealreal+如果從一種數(shù)據(jù)類型轉(zhuǎn)換成另一種數(shù)據(jù)類型可以由編譯程序自動完成，則這種類型轉(zhuǎn)換是隱式的，隱式轉(zhuǎn)換也叫做強(qiáng)制轉(zhuǎn)換。如果轉(zhuǎn)換必須由程序員顯式地寫在源程序中，則這種轉(zhuǎn)換叫做顯式轉(zhuǎn)換。顯式的類型轉(zhuǎn)換對類型檢查程序來說好象函數(shù)調(diào)用73常數(shù)的隱式轉(zhuǎn)換forI:=1toNdoX[I]:=1執(zhí)行時間：48.4N

sforI:=1toNdoX[I]:=1.0執(zhí)行時間：5.4N

s編譯程序?yàn)榈谝粋€語句產(chǎn)生的目標(biāo)代碼含運(yùn)行時的例程調(diào)用，該例程把1的整型表示轉(zhuǎn)換為實(shí)型表示大多數(shù)編譯程序都在編譯時把1轉(zhuǎn)換為1.074從整型到實(shí)型的類型檢查規(guī)則

產(chǎn)生式語義規(guī)則E

numE.type=integerE

num.numE.type=realE

idE.type=lookup(id.entry)E

E1opE2if(E1.type==integer)&&(E2.type==integer)E.type=integer;elseif(E1.type==integer)&&(E2.type==real)E.type=real;elseif(E1.type==real)&&(E2.type==integer)E.type=real;elseif(E1.type==real)&&(E2.type==real)E.type=real;elseE.type=type_error;756.6類型檢查有關(guān)的其他主題一、函數(shù)和運(yùn)算符的重載二、多態(tài)函數(shù)三、錯誤處理76一、函數(shù)和運(yùn)算符的重載在數(shù)學(xué)中，加法運(yùn)算符

+

是重載的當(dāng)A和B是整數(shù)、實(shí)數(shù)、復(fù)數(shù)或矩陣時，表達(dá)式A+B中的

+

具有不同的含義。重載符號的含義依賴于上下文在重載符號的引用點(diǎn)，其含義能夠確定到唯一，叫做重載的消除。重載的消除有時也稱為算符的辨別，因?yàn)樗_定了運(yùn)算符號表示哪種運(yùn)算。大多數(shù)語言中，算術(shù)運(yùn)算符是重載的，并且它們的重載可以通過查看其操作對象來消除。77類型集合僅通過檢查函數(shù)的參數(shù)類型并不一定能消除重載因?yàn)橐粋€子表達(dá)式可能有不止一個類型，而是有一個可能的類型集合。上下文要提供足夠的信息來縮小這個集合到唯一的類型例：在Ada語言中，算符*的一個標(biāo)準(zhǔn)解釋是一對整數(shù)到一個整數(shù)的函數(shù)。加入如下的聲明：function"*"(i,j:integer)returncomplexfunction"*"(plex)returncomplex*可能的類型包括：integerintegerintegerintegerintegercomplexcomplexcomplexcomplex78確定表達(dá)式的可能類型集合的語法制導(dǎo)定義函數(shù)引用的類型檢查規(guī)則E

E1(E2){if(E1.type==s

t)&&(E2.type==s)E.type=t;elseE.type=type_error;}確定表達(dá)式的可能類型集合的語法制導(dǎo)定義

產(chǎn)生式語義規(guī)則

E

EE

.types=E.typesE

idE.types=lookup(id.entry)E

E1(E2)E.types={t|s

E2.typesands

t

E1.types}79縮小表達(dá)式的類型集合的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則E

EE

.types=E.typesif(E

.types=={t})E.unique=t;elseE.unique=type_errorE

.code=E.codeE

idE.types=lookup(id.entry)E.code=gen(id.lexeme

:

E.unique)E

E1(E2)E.types={s

|s

E2.typ