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

第6章語(yǔ)義分析知識(shí)點(diǎn)：符號(hào)表

類(lèi)型體制

各語(yǔ)法成分的類(lèi)型檢查

2語(yǔ)義分析6.1語(yǔ)義分析的任務(wù)和地位6.2符號(hào)表6.3符號(hào)表的建立6.4類(lèi)型檢查6.5一個(gè)簡(jiǎn)單類(lèi)型檢查程序的說(shuō)明6.6類(lèi)型檢查有關(guān)的其他主題小結(jié)36.1語(yǔ)義分析的任務(wù)和地位程序設(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)作補(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語(yǔ)義檢查動(dòng)態(tài)檢查：目標(biāo)程序運(yùn)行時(shí)進(jìn)行的檢查靜態(tài)檢查：讀入源程序、但不執(zhí)行源程序的情況下進(jìn)行的檢查類(lèi)型檢查對(duì)訪問(wèn)數(shù)據(jù)的操作和被訪問(wèn)數(shù)據(jù)的類(lèi)型進(jìn)行檢查，檢查操作的合法性和數(shù)據(jù)類(lèi)型的相容性?？刂屏鳈z查檢查控制語(yǔ)句是否使控制轉(zhuǎn)移到一個(gè)合法的位置。唯一性檢查一個(gè)標(biāo)識(shí)符在同一程序塊中必須而且只能被說(shuō)明一次CASE語(yǔ)句中用于匹配選擇表達(dá)式的常量必須各不相同枚舉類(lèi)型定義中的各元素不允許重復(fù)關(guān)聯(lián)名字的檢查6類(lèi)型檢查由類(lèi)型檢查程序完成檢驗(yàn)結(jié)構(gòu)的類(lèi)型是否和它的上下文所期望的一致，如：表達(dá)式中各運(yùn)算對(duì)象的類(lèi)型算術(shù)運(yùn)算符mod的運(yùn)算對(duì)象的類(lèi)型用戶定義函數(shù)的各參數(shù)類(lèi)型、返回值類(lèi)型7語(yǔ)義分析程序的作用和地位語(yǔ)義分析程序的作用符號(hào)表的建立和管理類(lèi)型檢查語(yǔ)義分析程序的地位語(yǔ)法分析程序語(yǔ)義分析程序中間代碼生成程序記號(hào)流語(yǔ)法樹(shù)語(yǔ)法樹(shù)中間代碼生成目標(biāo)代碼時(shí)會(huì)用到語(yǔ)義分析的結(jié)果重載運(yùn)算符：一個(gè)運(yùn)算符在不同的上下文中表示不同的運(yùn)算類(lèi)型強(qiáng)制：編譯程序把運(yùn)算對(duì)象變換為上下文所期望的類(lèi)型86.2符號(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)表的效率直接影響編譯程序的效率。9符號(hào)表一、符號(hào)表的建立和訪問(wèn)時(shí)機(jī)二、符號(hào)表內(nèi)容三、符號(hào)表操作四、符號(hào)表組織10一、符號(hào)表的建立和訪問(wèn)時(shí)機(jī)1.多遍編譯程序變量在符號(hào)表中的位置作為詞法分析程序產(chǎn)生的記號(hào)的屬性112.合并遍的編譯程序兩方面的優(yōu)點(diǎn)：對(duì)語(yǔ)法分析程序來(lái)講降低了文法的復(fù)雜性允許用更系統(tǒng)的方法對(duì)上下文有關(guān)的錯(cuò)誤進(jìn)行檢測(cè)和校正。12二、符號(hào)表內(nèi)容符號(hào)表中記錄的是和標(biāo)識(shí)符相關(guān)的屬性出現(xiàn)在符號(hào)表中的屬性種類(lèi)，在一定程度上取決于程序設(shè)計(jì)語(yǔ)言的性質(zhì)。符號(hào)表的典型形式：

變量名目標(biāo)地址類(lèi)型維數(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)存問(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è)子域，指針域指示該標(biāo)識(shí)符在總的串區(qū)內(nèi)的開(kāi)始位置，長(zhǎng)度域記錄該標(biāo)識(shí)符中的字符數(shù)。14使用串描述符表示變量countx_totalb_loop位置長(zhǎng)度變量名其他屬性1567136………15目標(biāo)地址指示運(yùn)行時(shí)變量值存放的相對(duì)位置對(duì)于靜態(tài)存儲(chǔ)分配的語(yǔ)言（如Fortran），目標(biāo)地址按連續(xù)的順序分配，從0開(kāi)始到m（m是分配給一個(gè)程序的數(shù)據(jù)區(qū)的最大值）。對(duì)于塊結(jié)構(gòu)的語(yǔ)言(如Pascal)，通常采用二元地址<BL,NO>BL：塊的嵌套深度，用于確定分配給聲明變量的塊的數(shù)據(jù)區(qū)的基址。NO：變量的目標(biāo)地址偏移量，指示該變量的存儲(chǔ)單元在數(shù)據(jù)區(qū)中相對(duì)于基址的位置。16數(shù)據(jù)類(lèi)型當(dāng)所編譯的語(yǔ)言有數(shù)據(jù)類(lèi)型（隱式或顯式的）時(shí)，必須把類(lèi)型屬性存放到符號(hào)表中。對(duì)于無(wú)類(lèi)型的語(yǔ)言，可刪除該域。變量的類(lèi)型屬性用于：類(lèi)型檢查生成代碼空間分配變量的類(lèi)型以一種編碼形式存放在符號(hào)表中。17數(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)似的。18交叉引用表編譯程序可以提供的一個(gè)十分重要的程序設(shè)計(jì)輔助工具：交叉引用表編譯程序一般設(shè)一個(gè)選項(xiàng)，用戶可以選擇是否生成交叉引用表

變量名類(lèi)型維數(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)生交叉引用表，則鏈域以及語(yǔ)句的行號(hào)屬性都可以從符號(hào)表中刪除。20三、符號(hào)表操作最常執(zhí)行的操作：插入和檢索要求變量顯式聲明的強(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)，插入操作，從其作用推測(cè)出該變量的全部屬性21定位和重定位操作對(duì)于塊結(jié)構(gòu)的語(yǔ)言，在建立和刪除符號(hào)表時(shí)還要使用兩種附加的操作，即定位和重定位。當(dāng)編譯程序識(shí)別出塊的開(kāi)始時(shí)，執(zhí)行定位操作。當(dāng)編譯程序遇到塊的結(jié)束時(shí)，執(zhí)行重定位操作。定位操作：建立一個(gè)新的子表（包含于符號(hào)表中），在該塊中聲明的所有變量的屬性都存放在此子表中。重定位操作：“刪除”存放該塊中局部變量的子表這些變量的作用域局部于該塊，出了該塊后這些變量不能再被引用。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符號(hào)表的邏輯結(jié)構(gòu)sortnilheadarea

readarrayreadarrayheadareaiexchangeexchangeheadareaquicksortquicksortheadareakvpartitionpartitionheadarea

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

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

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

名字映射到地址

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

>=：在當(dāng)前子表中，報(bào)告錯(cuò)誤

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

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

D；SD

D；D|D

id：T|D

procid；D；ST

integer|real

|array[num]ofT1

|

T1

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

D；S D

D；D D

id：T T

integer T

real T

array[num]ofT1

T

T139設(shè)計(jì)翻譯方案的目的識(shí)別出被聲明實(shí)體記錄實(shí)體的名字、類(lèi)型、在數(shù)據(jù)區(qū)中的位置引入：全局變量offset，記錄下一個(gè)可用單元的相對(duì)地址T.width：記錄實(shí)體的域?qū)扵.type：記錄實(shí)體的類(lèi)型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二、過(guò)程定義的處理作用域信息的保存文法P

D；SD

D；DD

id：TD

procid；D；ST

integer T

real T

array[num]ofT1T

T142數(shù)據(jù)結(jié)構(gòu)及過(guò)程記錄符號(hào)表嵌套關(guān)系的、便于操作的結(jié)構(gòu)：棧tableptroffsett1offset1t2offset2Pqrqrt1t2t3t3offset3過(guò)程：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類(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ò)誤，則稱這種語(yǔ)言是強(qiáng)類(lèi)型語(yǔ)言。有些檢查只能動(dòng)態(tài)完成table:array[0..255]ofchar;i:integer;計(jì)算table[i]47靜態(tài)類(lèi)型檢查設(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)算符&的結(jié)果是指向運(yùn)算對(duì)象所代表的實(shí)體的指針，如果運(yùn)算對(duì)象的類(lèi)型是‘…’，結(jié)果類(lèi)型就是指向‘…’的指針。暗示的概念：每一個(gè)表達(dá)式有一個(gè)類(lèi)型類(lèi)型有結(jié)構(gòu)48類(lèi)型體制把類(lèi)型表達(dá)式指派到程序各部分的一組規(guī)則由類(lèi)型檢查程序?qū)崿F(xiàn)同一語(yǔ)言的不同編譯程序使用的類(lèi)型體制可能不同數(shù)組作為變?cè)獋鬟f時(shí)，數(shù)組的下標(biāo)集合可以指明，也可以不指明原因：不同的Pascal語(yǔ)言編譯程序?qū)崿F(xiàn)的類(lèi)型體制不同UNIX系統(tǒng)中，lint命令實(shí)現(xiàn)的類(lèi)型體制比C語(yǔ)言編譯程序本身所實(shí)現(xiàn)的更詳細(xì)。49一、類(lèi)型表達(dá)式類(lèi)型表達(dá)式的定義：基本類(lèi)型是類(lèi)型表達(dá)式boolean、char、integer、和real錯(cuò)誤類(lèi)型type_error、回避類(lèi)型void類(lèi)型名是類(lèi)型表達(dá)式，因?yàn)轭?lèi)型表達(dá)式可以命名。類(lèi)型構(gòu)造器作用于類(lèi)型表達(dá)式的結(jié)果仍是類(lèi)型表達(dá)式數(shù)組：如果T是類(lèi)型表達(dá)式，那么array(I，T)是元素類(lèi)型為T(mén)和下標(biāo)集合為I的數(shù)組的類(lèi)型表達(dá)式，I通常是一個(gè)整數(shù)域。

varA:array[1..10]ofinteger;

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

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

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

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

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

integer)

(lexeme

array(1..15,char)))

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

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

varp:

row;

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

pointer(row)51

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

類(lèi)型由類(lèi)型表達(dá)式D

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

int

int

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

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

char

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

(integer

integer)

(integer

integer)類(lèi)型表達(dá)式可以包含變量（稱為類(lèi)型變量），變量的值是類(lèi)型表達(dá)式。52類(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)型變量如：char

char

pointer(integer)

pointercharcharinteger

pointercharinteger樹(shù)：dag：53二、類(lèi)型等價(jià)關(guān)鍵：精確地定義什么情況下兩個(gè)類(lèi)型表達(dá)式等價(jià)問(wèn)題：類(lèi)型表達(dá)式可以命名，且這個(gè)名字可用于隨后的類(lèi)型表達(dá)式中名字代表它自己？代表另一個(gè)類(lèi)型表達(dá)式？新的名稱是一個(gè)類(lèi)型表達(dá)式，這個(gè)表達(dá)式與名稱所代表的類(lèi)型表達(dá)式是否總是等價(jià)的？541.結(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à)于integerpointer(integer)僅等價(jià)于pointer(integer)55測(cè)試兩個(gè)類(lèi)型表達(dá)式結(jié)構(gòu)等價(jià)的算法輸入：兩個(gè)類(lèi)型表達(dá)式s和t輸出：如果s和t結(jié)構(gòu)等價(jià)，則返回true，否則返回false方法：boolsequiv(bexprs,t){if(s和t是同樣的基本類(lèi)型)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)等價(jià)概念的修改當(dāng)數(shù)組作為參數(shù)傳遞時(shí)，數(shù)組的界不作為類(lèi)型的一部分算法調(diào)整elseif(s==array(s1,s2))&&(t==array(t1,t2))returnsequiv(s2,t2);57編碼測(cè)試方法對(duì)基本類(lèi)型規(guī)定確定位數(shù)、確定位置的二進(jìn)制編碼；對(duì)類(lèi)型構(gòu)造器規(guī)定確定位數(shù)的二進(jìn)制編碼類(lèi)型表達(dá)式可用一組二進(jìn)制編碼表示例：D.M.Ritchie的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)

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

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

pointer01array10freturn11基本類(lèi)型的編碼

基本類(lèi)型編碼

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

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

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

typelink=

cell;varnext:link;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à)回答：依賴于具體的實(shí)現(xiàn)系統(tǒng)原因：Pascal報(bào)告中沒(méi)有定義“類(lèi)型等價(jià)”這個(gè)術(shù)語(yǔ)2.名字等價(jià)60名字等價(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á)式：

變量類(lèi)型表達(dá)式

nextlinklastlinkppointer(cell)qpointer(cell)rpointer(cell)考慮名字等價(jià)的情形考慮結(jié)構(gòu)等價(jià)的情形61標(biāo)識(shí)符與類(lèi)型通過(guò)聲明相聯(lián)系的規(guī)則舉例Pascal的許多編譯程序用隱含的類(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)型名。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類(lèi)型圖類(lèi)型圖表示類(lèi)型構(gòu)造方法：每當(dāng)出現(xiàn)一個(gè)類(lèi)型構(gòu)造器或基本類(lèi)型，就建立一個(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à)的。typelink=

cell;np=

cell;nqr=

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

cell;cell=recordinfo:integer;next:linkend;cell的類(lèi)型表達(dá)式：cell=record×××infointnextlinkcell=record×××infointnextpointercellcell=record×××infointnextpointer646.5一個(gè)簡(jiǎn)單類(lèi)型檢查程序的說(shuō)明利用語(yǔ)法制導(dǎo)方法說(shuō)明類(lèi)型體制一、語(yǔ)言說(shuō)明二、確定標(biāo)識(shí)符的類(lèi)型三、表達(dá)式的類(lèi)型檢查四、語(yǔ)句的類(lèi)型檢查五、類(lèi)型轉(zhuǎn)換65一、語(yǔ)言說(shuō)明源語(yǔ)言文法：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)生的一個(gè)程序：k:integer;k:=kmod200766二、確定標(biāo)識(shí)符的類(lèi)型語(yǔ)言中的類(lèi)型：基本類(lèi)型：char、integer、和booleantype_error和void構(gòu)造類(lèi)型：數(shù)組、指針和函數(shù)假定：數(shù)組下標(biāo)從1開(kāi)始類(lèi)型array[256]ofchar的類(lèi)型表達(dá)式是：array(1..256,char)前綴算符

用于建立指針類(lèi)型

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

確定并保存標(biāo)識(shí)符類(lèi)型的部分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，記錄類(lèi)型表達(dá)式68三、表達(dá)式的類(lèi)型檢查E

literalE

numE

idE

id1>id2E

E1andE2E

E1modE2E

E1[E2]E

E1

E

E1(E2)綜合屬性E.type，類(lèi)型體制指派給E產(chǎn)生的表達(dá)式的類(lèi)型表達(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四、語(yǔ)句的類(lèi)型檢查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五、類(lèi)型轉(zhuǎn)換表達(dá)式：x+i整型數(shù)和實(shí)型數(shù)在計(jì)算機(jī)中的表示不同用于整型運(yùn)算和實(shí)型運(yùn)算的機(jī)器指令也不同xiinttorealreal+如果從一種數(shù)據(jù)類(lèi)型轉(zhuǎn)換成另一種數(shù)據(jù)類(lèi)型可以由編譯程序自動(dòng)完成，則這種類(lèi)型轉(zhuǎn)換是隱式的，隱式轉(zhuǎn)換也叫做強(qiáng)制轉(zhuǎn)換。如果轉(zhuǎn)換必須由程序員顯式地寫(xiě)在源程序中，則這種轉(zhuǎn)換叫做顯式轉(zhuǎn)換。顯式的類(lèi)型轉(zhuǎn)換對(duì)類(lèi)型檢查程序來(lái)說(shuō)好象函數(shù)調(diào)用73常數(shù)的隱式轉(zhuǎn)換forI:=1toNdoX[I]:=1執(zhí)行時(shí)間：48.4N

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

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

產(chǎn)生式語(yǔ)義規(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類(lèi)型檢查有關(guān)的其他主題一、函數(shù)和運(yùn)算符的重載二、多態(tài)函數(shù)三、錯(cuò)誤處理76一、函數(shù)和運(yùn)算符的重載在數(shù)學(xué)中，加法運(yùn)算符

+

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

+

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

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

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

產(chǎn)生式語(yǔ)義規(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á)式的類(lèi)型集合的語(yǔ)法制導(dǎo)定義產(chǎn)生式語(yǔ)義規(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