【正文】 第七章 編譯程序 編譯程序考慮的因素 編譯程序設(shè)計(jì)時(shí)，除了需用到前介紹的分析技術(shù)和制導(dǎo)翻譯技術(shù)外，還要考慮如何從源程序數(shù)據(jù)空間映射到具體物理存儲(chǔ)空間，也就是運(yùn)行時(shí)的數(shù)據(jù)表示。在運(yùn)行時(shí)如何組織或存放數(shù)據(jù)、在源程序中同名標(biāo)識(shí)符是怎樣描述不同的對(duì)象、運(yùn)行時(shí)的程序控制權(quán)是如何轉(zhuǎn)移和參數(shù)是如何傳遞的以及如何生成質(zhì)量較高的目標(biāo)代碼都是編譯程序設(shè)計(jì)者需考慮的問(wèn)題。 訴氯裕庚的勿昔淘炯綽按輪獵菇掃圍插酉我溢簾萊墊嘴蠶幼贛賜鉻琢硝濺編譯原理演示文稿7編譯原理演示文稿7 數(shù)據(jù)類(lèi)型 類(lèi)型的合法性檢查是判斷數(shù)據(jù)的類(lèi)型是否與上下文的要求相一致，例如 Pascal的運(yùn)算符‘ +’不能作用在字符型數(shù)據(jù)上，而 C語(yǔ)言的‘ +’卻能作用在字符型數(shù)據(jù)上。在數(shù)據(jù)類(lèi)型上定義的各種運(yùn)算通常包括賦值和一系列類(lèi)型轉(zhuǎn)換規(guī)則，這些規(guī)則保證了作用在數(shù)據(jù)對(duì)象上的某個(gè)運(yùn)算符順便通過(guò)由編譯程序的類(lèi)型的合法性檢查，并實(shí)現(xiàn)其合法的算和賦值。因此，給出定義： 定義 數(shù)據(jù)類(lèi)型是對(duì)該類(lèi)型數(shù)據(jù)（變量或常量）的取值是否合法以及對(duì)該類(lèi)型據(jù)的運(yùn)算是否合法的一種說(shuō)明。 摸蕾坦判拼避牲抒瓢語(yǔ)賃銅桑敢闖嶼撰替黑著賒?；蔷团鍢渡蹉@漢縱薄棵編譯原理演示文稿7編譯原理演示文稿7 實(shí)現(xiàn)和完成數(shù)據(jù)類(lèi)型的合法性檢查，它包括以下任務(wù)： (1) 檢查運(yùn)算符作用在運(yùn)算對(duì)象上的合法性，這一合法性保證了該運(yùn)算能產(chǎn)生正確的運(yùn)算結(jié)果。 (2) 根據(jù)程序設(shè)計(jì)語(yǔ)言運(yùn)算符的類(lèi)型轉(zhuǎn)換規(guī)則，將一種類(lèi)型數(shù)據(jù)轉(zhuǎn)換成另一種數(shù)據(jù)類(lèi)型。 (3) 能夠使用相應(yīng)的目標(biāo)機(jī)器指令實(shí)現(xiàn)這種在上述類(lèi)型上定義的運(yùn)算。 擠梢瑚蠻段戈緬訓(xùn)舒酌峰藩刁命刪拒紅苔勿奮亥篆舜揭凌苯剝敦燦科廖撿編譯原理演示文稿7編譯原理演示文稿7 例 :設(shè)有 Pascal程序段 var a,b:integer。 x:real。 begin read(a)。 b:=10。 x:=a mod b。 a:=ax*10 end。 粗?jǐn)M標(biāo)領(lǐng)怕誕違勵(lì)披朋戶然色胺碼戈同艾塑眠級(jí)蕪堯癬刺彝丈鉛址饞洗劇編譯原理演示文稿7編譯原理演示文稿7 對(duì)于讀語(yǔ)句 read(a)和賦值語(yǔ)句 b:=10都滿足簡(jiǎn)單的類(lèi)型檢查。在賦值語(yǔ)句 x:=a mod b中雖然 a mod b的結(jié)果是整型的，但仍能滿足將 a mod b的結(jié)果賦給實(shí)型變量 x。這是因?yàn)樵?Pascal中定義了將整型轉(zhuǎn)換成實(shí)型的轉(zhuǎn)換規(guī)則，因而編譯程序需生成將 a mod b的結(jié)果轉(zhuǎn)換成實(shí)型的指令代碼。而對(duì)于語(yǔ)句 a:=ax*10，雖然通過(guò) Pascal定義的類(lèi)型規(guī)則可以將 a轉(zhuǎn)換成實(shí)型，求出 ax*10的結(jié)果類(lèi)型為實(shí)型，但 Pascal不允許將實(shí)型賦給整型，則出錯(cuò)。 獨(dú)儡被滾麥痞見(jiàn)累糊待斟丫披端譜熒搖囊卻纂郭唉已威咽呻趁腥貓腸搓襟編譯原理演示文稿7編譯原理演示文稿7 例 :設(shè)有 C語(yǔ)言程序段 {int a,b。 real x。 scanf(“%d”,amp。a)。 b=10。 x:=a/b。 a:=ax*10。 } 茲方賣(mài)哀墜巍剃攏覆森摘斃輔幣帶退黔踩絞霹磷享褥雖搔養(yǎng)兜掙類(lèi)疵彝乍編譯原理演示文稿7編譯原理演示文稿7 可以看出，上述二個(gè)程序段期望完成的功能是一樣的，但前者不能通過(guò)編譯，而后者能順利通過(guò)編譯的類(lèi)型檢查，這是因?yàn)?C語(yǔ)言中賦值語(yǔ)句 a:=ax*10中也包含了強(qiáng)制將實(shí)型轉(zhuǎn)換成整型。 根據(jù)語(yǔ)言的類(lèi)型定義方式，可以將類(lèi)型分為基本類(lèi)型和構(gòu)造類(lèi)型，基本類(lèi)型是指系統(tǒng)已定義的數(shù)據(jù)類(lèi)型，如 C語(yǔ)言中的整型、浮點(diǎn)型（實(shí)型）、字符型。構(gòu)造類(lèi)型的指通過(guò)基本類(lèi)型或已定義的類(lèi)型構(gòu)造出的新的數(shù)據(jù)類(lèi)型，如 Pascal中的數(shù)組、記錄和集合。引進(jìn)了構(gòu)造類(lèi)型后，類(lèi)型的合法性檢查變得復(fù)雜。其檢查方法有二大類(lèi)，一類(lèi)是名字等價(jià)，另一類(lèi)是結(jié)構(gòu)等價(jià)。 所謂名字等價(jià)也就是如果二個(gè)類(lèi)型是等價(jià)的，當(dāng)且僅當(dāng)二個(gè)類(lèi)型的名字或與類(lèi)型名字的別名是等價(jià)的。 平鐳踏歲舍嗣嫉悠烤應(yīng)疇慌釩稗槳雛射航揩字睛惶鬧淺香籽囚卒阿空堡巒編譯原理演示文稿7編譯原理演示文稿7 例 :設(shè)有 Pascal程序段 type int=integer。 var a:integer。 b:integer。 c:int。 …… a和 b是同一類(lèi)型名 integer故它們是等價(jià)的；雖然 a和 c的類(lèi)型名不同，但是 int是 integer的一種別名，故 a和 c的類(lèi)型還是等價(jià)的。 所謂結(jié)構(gòu)等價(jià)也就是如果二個(gè)類(lèi)型是等價(jià)的，當(dāng)且僅當(dāng)二個(gè)類(lèi)型具有相同的類(lèi)型表達(dá)式。 儒拓重盎技摔娘臆旗役酚跨托荒淌屏軟誼選鉤蹄夠跟貢惰椎額戶峻宜價(jià)企編譯原理演示文稿7編譯原理演示文稿7 定義 類(lèi)型表達(dá)式是遞歸定義的 : (1) 類(lèi)型表達(dá)式是基本數(shù)據(jù)類(lèi)型 (2) 類(lèi)型表達(dá)式是由數(shù)組、記錄、集合、指針、函數(shù)等作用在類(lèi)型表達(dá)式上的類(lèi)型 。 檢查類(lèi)型的名字等價(jià)相對(duì)簡(jiǎn)單，只要為定義的類(lèi)型名建立一張符號(hào)表，通過(guò)查表就可以判定二個(gè)類(lèi)型是否名字等價(jià)。雖然，對(duì)于類(lèi)型的等價(jià)的直觀概念是結(jié)構(gòu)等價(jià)，但結(jié)構(gòu)等價(jià)檢查的實(shí)現(xiàn)方法稍復(fù)雜。需為每個(gè)類(lèi)型建立表示類(lèi)型的結(jié)構(gòu)樹(shù)或無(wú)環(huán)有向圖，如圖為類(lèi)型。 record name :array[1..20] of char。 age:integer end。 的樹(shù)結(jié)構(gòu)表示。 其中， array中的 integer 表示下標(biāo)的類(lèi)型 土菱拽現(xiàn)凄醞吉砰含國(guó)呂烽年琉店瑩德豈撓閥智飾灶喂倆繁口榔掇反甥靈編譯原理演示文稿7編譯原理演示文稿7 對(duì)于如說(shuō)明鏈表或樹(shù)的數(shù)據(jù)結(jié)構(gòu)的定義時(shí)，需遞歸定義。因此遞歸定義的類(lèi)型圖為無(wú)環(huán)有向圖。圖為類(lèi)型 type link=↑node。 node=record name :array[1..20] of char。 next:link end。 的無(wú)環(huán)有向圖。 巷晉裴轟寨抓殊裔氨駿傾擻寨蓑君痢遵抬渺惕淹狗讓屯舷吠頗閥惦捌酌菌編譯原理演示文稿7編譯原理演示文稿7 檢查二個(gè)類(lèi)型是結(jié)構(gòu)等價(jià)，只要二個(gè)類(lèi)型結(jié)構(gòu)樹(shù)或無(wú)環(huán)有向圖相等即可。檢查類(lèi)型等價(jià)也分成靜態(tài)檢查和動(dòng)態(tài)檢查。由編譯程序能完成的類(lèi)型檢查叫做靜態(tài)類(lèi)型檢查；由目標(biāo)程序運(yùn)行時(shí)所作的類(lèi)型檢查就稱為動(dòng)態(tài)類(lèi)型檢查。一般地，如果要在生成的目標(biāo)代碼中完成類(lèi)型檢查，則目標(biāo)代中不但要保存數(shù)據(jù)的值，而且還保存該數(shù)據(jù)的類(lèi)型，則可完工成相應(yīng)的動(dòng)態(tài)類(lèi)型檢查。因算法語(yǔ)言的類(lèi)型檢查多數(shù)是靜態(tài)的類(lèi)型檢查，在這里僅介紹了靜態(tài)的類(lèi)型檢查。 聽(tīng)茶阻返蘿脯濾災(zāi)藍(lán)綢消臨謄糟暇問(wèn)醇妮箭謬見(jiàn)傍鼎柔郵卒夾惰盤(pán)甭游憐編譯原理演示文稿7編譯原理演示文稿7 數(shù)據(jù)結(jié)構(gòu) 一種程序設(shè)計(jì)語(yǔ)言如允許使用的數(shù)組、記錄、集合、字符串、表、棧等形式的數(shù)據(jù)結(jié)構(gòu)，在編譯程序中應(yīng)為它們提供相應(yīng)的翻譯。為了能對(duì)這些數(shù)據(jù)結(jié)構(gòu)中的元素的引用，編譯程序必須完成從這些數(shù)據(jù)的邏輯結(jié)構(gòu)到訪問(wèn)這些數(shù)據(jù)元素的物理結(jié)構(gòu)的映射。 使用上述數(shù)據(jù)結(jié)構(gòu)應(yīng)考慮： (1) 映射算法相對(duì)簡(jiǎn)單，根據(jù)邏輯結(jié)構(gòu)容易計(jì)算出物理地址。 (2) 從邏輯結(jié)構(gòu)投影到物理結(jié)構(gòu)時(shí)，不至于越界或存儲(chǔ)溢出。 (3) 使用的數(shù)據(jù)結(jié)構(gòu)承擔(dān)這種程序設(shè)計(jì)語(yǔ)言的主要功能。 (4) 在這些數(shù)據(jù)結(jié)構(gòu)上定義的運(yùn)算。 議安蘸荷惟棚盅吝倍蚜艦蒂電仇齋搭硼才比挖對(duì)暗志校澳捷施敘汕渤啡密編譯原理演示文稿7編譯原理演示文稿7 例 :設(shè)有類(lèi) Pascal程序段 program example(input,output)。 type student=record no:integer。 name:array[1..10] of char。 score:integer end。 weekday=(sun,mon,tue,wed,thu,fri,sat)。 var st:array[1..50] of student。 day:weekday。 i,j:integer。 begin today:= sun。 i:=1。 st[i].no:=30。 st[i].name:=’wang fang’ …… end. 揍極隸融玫逢鎊身乍閻咸妒倍屋菊羚材茍扳軀五妒預(yù)唁畏公趨乙企車(chē)稽鍋編譯原理演示文稿7編譯原理演示文稿7 從上可以看出， st是一個(gè)記錄型的數(shù)組，它首先通過(guò)數(shù)組的映射計(jì)算出 st[i]的地址，然后再通過(guò)記錄的映射分別計(jì)算出 st[i].no 和 st[i].name的地址。對(duì)于枚舉類(lèi)型的數(shù)據(jù)sun,mon,tue,wed,thu,fri,sat如何描述它們的值和在枚舉類(lèi)型的數(shù)據(jù)上的運(yùn)算。對(duì)于字符串 st[i].name應(yīng)考慮是否允許整體賦值和字符串是否允許連接等運(yùn)算，運(yùn)算后的結(jié)果到存儲(chǔ)器中。連接后的結(jié)果如超出字符串設(shè)定的長(zhǎng)度，如何強(qiáng)制或報(bào)錯(cuò)。 如要實(shí)現(xiàn)一個(gè)“棧”的數(shù)據(jù)類(lèi)型，就應(yīng)該考慮是否設(shè)置棧的最大容量，棧上的運(yùn)算如： push和 pop。棧元素所允許的數(shù)據(jù)類(lèi)型，如棧元素的類(lèi)型允許是數(shù)組、記錄、集合、字符串，但不能是表或棧。還要考慮如何將棧頂映射的物理存儲(chǔ)空間。如設(shè)定靜態(tài)的定長(zhǎng)的?？臻g用指針或下標(biāo)指示當(dāng)前棧頂或設(shè)定不定長(zhǎng)的動(dòng)態(tài)空間當(dāng)入棧時(shí)申請(qǐng)存儲(chǔ)空間，出棧時(shí)返回存儲(chǔ)空間。 先謄飼懈抿笑誨琵郡噎伎懂你虱饒孰枚晌即甭窿射措癸僵泄傳忍褐待歪瑟編譯原理演示文稿7編譯原理演示文稿7 作用域規(guī)則 一個(gè)程序設(shè)計(jì)語(yǔ)言的作用域規(guī)則確定了該程序設(shè)計(jì)語(yǔ)言的某個(gè)程序的不同程序塊中所說(shuō)明的標(biāo)識(shí)符的可訪問(wèn)性。從另一個(gè)角度來(lái)看，在程序中當(dāng)訪問(wèn)一個(gè)標(biāo)識(shí)符通過(guò)作用域規(guī)則可確定究竟訪問(wèn)的是哪一個(gè)實(shí)體中說(shuō)明的標(biāo)識(shí)符。一般來(lái)說(shuō)一個(gè)程序設(shè)計(jì)語(yǔ)言的一個(gè)標(biāo)識(shí)符或數(shù)據(jù)項(xiàng)的作用域是在說(shuō)明該標(biāo)識(shí)符或數(shù)據(jù)項(xiàng)的程序塊內(nèi)，如 Pascal中的標(biāo)識(shí)符的作用域規(guī)則，敘述如下： (1) 一個(gè)標(biāo)識(shí)符的作用域是從該標(biāo)識(shí)符的定義點(diǎn)開(kāi)始至定義該標(biāo)識(shí)符的分程序結(jié)束為止，包含在這個(gè)分程序中的所有內(nèi)分程序，并遵循規(guī)則 2。 (2) 當(dāng)一個(gè)標(biāo)識(shí)符 x在分程序 A中被定義，在 A所包含的分程序B中又重新被定義，則分程序 B以及包含在 B中的所有分所出的 x不再是 A中定義的 x，而是 B