編譯原理與技術(shù)講義 第8章 屬性文法和語(yǔ)義分析

1、編譯原理與技術(shù)第8章屬性文法和語(yǔ)義分析 青島大學(xué)信息工程學(xué)院主要內(nèi)容語(yǔ)義分析概況 屬性與屬性文法屬性的計(jì)算 數(shù)據(jù)類型與類型檢查 編譯原理與技術(shù)28.1 語(yǔ)義分析概況 語(yǔ)義分析在編譯程序中的位置 程序的語(yǔ)義涉及兩個(gè)方面，即數(shù)據(jù)結(jié)構(gòu)的語(yǔ)義域控制結(jié)構(gòu)的語(yǔ)義。數(shù)據(jù)結(jié)構(gòu)的語(yǔ)義主要指域標(biāo)識(shí)符相關(guān)聯(lián)的數(shù)據(jù)對(duì)象，也即量的含義?？刂平Y(jié)構(gòu)的語(yǔ)義是語(yǔ)言定義的。 語(yǔ)法分析器語(yǔ)義分析器中間代碼生成器語(yǔ)法樹(shù)語(yǔ)法樹(shù)單詞記號(hào)中間代碼編譯原理與技術(shù)38.1 語(yǔ)義分析概況量涉及類型與值，值在程序運(yùn)行時(shí)刻確定，而類型則由程序的說(shuō)明部分來(lái)規(guī)定。 例如，int x, y;float z;char array100;把x、y、z和arr

2、ay分別與整型、整型、實(shí)型和字符數(shù)組型關(guān)聯(lián)起來(lái)，它們分別代表相應(yīng)類型的數(shù)據(jù)對(duì)象。不同類型的數(shù)據(jù)對(duì)象有不同的機(jī)器內(nèi)部表示，占用不同的存儲(chǔ)空間，有不同的取值范圍，對(duì)它們所能進(jìn)行的運(yùn)算也不同。只有相同類型、因而具有相同機(jī)內(nèi)表示的數(shù)據(jù)對(duì)象，或符合特定要求的數(shù)據(jù)對(duì)象才能進(jìn)行相應(yīng)的運(yùn)算。當(dāng)考慮標(biāo)識(shí)符的相關(guān)含義時(shí)還必須要考慮到作用域的問(wèn)題。確定標(biāo)識(shí)符所關(guān)聯(lián)的類型、作用域等屬性信息，進(jìn)行類型正確性的檢查成為語(yǔ)義分析的一個(gè)基本工作。 編譯原理與技術(shù)48.1 語(yǔ)義分析概況例如，對(duì)于C的while循環(huán)語(yǔ)句：while () ；規(guī)定了首先計(jì)算的值，如果為真（或非0）時(shí)，就執(zhí)行；然后再計(jì)算的值，并重復(fù)以上過(guò)程，直到的值

3、為假（或?yàn)?），便結(jié)束循環(huán)語(yǔ)句，執(zhí)行while語(yǔ)句之后的語(yǔ)句。語(yǔ)義分析將分析各個(gè)語(yǔ)法結(jié)構(gòu)的含義并做出相應(yīng)的語(yǔ)義處理。編譯原理與技術(shù)58.1 語(yǔ)義分析概況語(yǔ)義分析的基本功能 確定類型 確定標(biāo)識(shí)符所關(guān)聯(lián)對(duì)象的數(shù)據(jù)類型。這部分工作有時(shí)由掃描器完成，掃描器將處理源程序的聲明部分。類型檢查 按照語(yǔ)言的類型規(guī)則，對(duì)參加運(yùn)算的運(yùn)算分量進(jìn)行類型檢查，檢查運(yùn)算的合法性、運(yùn)算分量類型的一致性（相容性），對(duì)于不相容的運(yùn)算對(duì)象，報(bào)告錯(cuò)誤，必要時(shí)進(jìn)行相應(yīng)的類型轉(zhuǎn)換。例如，對(duì)于數(shù)組變量個(gè)函數(shù)變量的加法運(yùn)算額出現(xiàn)，報(bào)告語(yǔ)義錯(cuò)誤；對(duì)于整型與實(shí)型數(shù)據(jù)對(duì)象的加法，把它們轉(zhuǎn)換成同一類型。控制流檢查 對(duì)于任何引起控制流離開(kāi)一個(gè)結(jié)構(gòu)的

4、語(yǔ)句，程序中必須由該控制轉(zhuǎn)移可以轉(zhuǎn)到的地方。例如，C的break語(yǔ)句引起控制離開(kāi)最小包圍的while、for或switch語(yǔ)句，如果這樣的包圍語(yǔ)句不存在，則是一個(gè)錯(cuò)誤。編譯原理與技術(shù)68.1 語(yǔ)義分析概況語(yǔ)義分析的基本功能唯一性檢查 有些場(chǎng)合，對(duì)象必須正好被定義一次。例如，集合中的元素只能出現(xiàn)一次，對(duì)象類的名字不能重復(fù)，分支語(yǔ)句的分情形常量必須區(qū)分.在Pascal語(yǔ)言中，標(biāo)識(shí)符只能唯一第定義一次。關(guān)聯(lián)名字檢查 有時(shí)，同樣的名字必須出現(xiàn)兩次或更多次。例如，在C+語(yǔ)言中，構(gòu)造函數(shù)的名字必須和類型一致；在Ada語(yǔ)言中，循環(huán)或程序塊可以有名字出現(xiàn)在其開(kāi)始和結(jié)束，編譯程序必須檢查兩個(gè)地方的名字是否相同。

5、識(shí)別含義 根據(jù)程序語(yǔ)言的形式或非形式語(yǔ)義規(guī)則，識(shí)別程序中各個(gè)構(gòu)造成分組合到一起的含義，并做相應(yīng)的語(yǔ)義處理， 編譯原理與技術(shù)78.2 屬性與屬性文法 屬性的引入為了解釋程序的語(yǔ)義、把程序翻譯成可執(zhí)行的代碼，需要對(duì)文法符號(hào)引進(jìn)一些表示程序語(yǔ)言結(jié)構(gòu)性質(zhì)的屬性。例如變量數(shù)據(jù)類型、表達(dá)式值、存儲(chǔ)地址、過(guò)程體代碼以及數(shù)的有效數(shù)字個(gè)數(shù)等. 計(jì)算屬性的值并把它和語(yǔ)言結(jié)構(gòu)聯(lián)系起來(lái)的過(guò)程稱作屬性的綁定。屬性綁定發(fā)生在編譯或運(yùn)行過(guò)程的時(shí)刻叫做綁定時(shí)刻。不同屬性的綁定時(shí)刻不同，對(duì)于不同的語(yǔ)言，甚至同樣的屬性也有不同的綁定時(shí)刻。在程序運(yùn)行前綁定的屬性稱為靜態(tài)的，只能在程序運(yùn)行期間才能綁定的屬性是動(dòng)態(tài)的。 編譯原理與技術(shù)

6、88.2 屬性與屬性文法屬性的引入在靜態(tài)類型語(yǔ)言諸如C和Pascal中，變量或表達(dá)式的數(shù)據(jù)類型是主要的編譯時(shí)刻的屬性，類型檢查器就是一個(gè)語(yǔ)義分析器，它計(jì)算語(yǔ)言實(shí)體的數(shù)據(jù)類型屬性并驗(yàn)證這些類型符合語(yǔ)言的類型規(guī)則。而LISP或Smalltalk中的數(shù)據(jù)類型是動(dòng)態(tài)的，它們的編譯必須產(chǎn)生計(jì)算類型的代碼，然后在程序的運(yùn)行過(guò)程中進(jìn)行類型檢查。表達(dá)式的值通常是動(dòng)態(tài)的，編譯只產(chǎn)生在程序運(yùn)行期間計(jì)算表達(dá)式的值的代碼。然而，有些表達(dá)式可能是常數(shù)，例如，3.12*5+10，語(yǔ)義分析器可以在編譯的時(shí)候計(jì)算它們的值。編譯原理與技術(shù)98.2 屬性與屬性文法屬性的引入對(duì)于不同的語(yǔ)言或者變量自身的性質(zhì)，變量的存儲(chǔ)分配可以是靜

7、態(tài)的、也可以是動(dòng)態(tài)的。由于屬性的計(jì)算依賴與程序的運(yùn)行環(huán)境，甚至?xí)r目標(biāo)機(jī)的細(xì)節(jié)，所以編譯通常把屬性的計(jì)算推遲到代碼生成期間。過(guò)程的目標(biāo)碼顯然是靜態(tài)屬性。編譯的代碼產(chǎn)生器全權(quán)負(fù)責(zé)這類屬性的計(jì)算。數(shù)的有效數(shù)字個(gè)數(shù)這個(gè)屬性一般不在編譯期間處理，它隱含在編譯程序構(gòu)造期間對(duì)這些數(shù)值實(shí)現(xiàn)的處理，通常是運(yùn)行環(huán)境的一部分。然而，如果要正確地翻譯常數(shù)，掃描器也需要知道允許的有效數(shù)字的個(gè)數(shù)。編譯原理與技術(shù)108.2 屬性與屬性文法屬性文法的定義定義8.1 如果用X表示一個(gè)文法符號(hào)，a代表X的一個(gè)屬性，那么，X.a代表X的關(guān)聯(lián)屬性a。定義8.2 對(duì)于一組屬性a1,a2,.,am和文法G的每個(gè)產(chǎn)生式X0X1X2.Xn（

8、X0是非終結(jié)符，其它的Xi是任意符號(hào)），意味著每個(gè)屬性Xi. aj的值都和產(chǎn)生式中其它屬性有關(guān)系，每個(gè)關(guān)系可以表示成屬性等式或語(yǔ)義規(guī)則的形式：Xi. aji(a1,a2,.,am)定義8.3 屬性文法就是對(duì)于一組屬性a1,a2,.,am和文法G的每個(gè)產(chǎn)生式的所有的語(yǔ)義規(guī)則，其中文法G稱為基礎(chǔ)文法。編譯原理與技術(shù)118.2 屬性與屬性文法屬性文法通常寫成下列表格形式：語(yǔ)法產(chǎn)生式語(yǔ)義規(guī)則X 關(guān)聯(lián)的屬性等式編譯原理與技術(shù)128.2 屬性與屬性文法數(shù)的最重要的屬性就是它的值，命名為val。每個(gè)數(shù)字都有一個(gè)值，可以直接從它表示的實(shí)際數(shù)字得到。所以，文法規(guī)則 digit 0意味著在這個(gè)情況下digit有0

9、值，可以表示成屬性等式digit.val := 0，并把它和文法規(guī)則 digit 0關(guān)聯(lián)在一起。如果運(yùn)用規(guī)則number digit得到了數(shù)，那么，這個(gè)數(shù)就值包含一個(gè)數(shù)字，其值就等于這個(gè)數(shù)字的值，它的屬性等式可以表示成number.val = digit.val。如果數(shù)從文法規(guī)則number number digit得到，那么我們必須規(guī)則左邊符號(hào)的值和文法規(guī)則右邊符號(hào)的值之間的關(guān)系。注意，文法規(guī)則兩邊出現(xiàn)的number完全不同（用下標(biāo)表示），這是由于它們具有不同的值。 考慮數(shù)83的最右推導(dǎo)：number number digit digit digit digit3 83在第一步使用的文法規(guī)則

10、number1 number2 digit，其中number2表示數(shù)字8，而digit對(duì)應(yīng)3，它們的值分別是8和3。為了得到number1的值83，必須使用的下列計(jì)算： 838*10 + 3。這對(duì)應(yīng)了屬性等式：number1.val := number2 .val 10 + digit.val例8.1 考慮下列無(wú)符號(hào)數(shù)的簡(jiǎn)單語(yǔ)法G8.1number number digit | digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9編譯原理與技術(shù)138.2 屬性與屬性文法表8.2 例8.1的屬性文法文法規(guī)則語(yǔ)義規(guī)則number1 number2 dig

11、itnumber1.val := number2 .val 10 + digit.valnumber digitnumber.val := digit.valdigit 0digit.val := 0digit 1digit.val := 1.digit 8digit.val := 8digit 9digit.val := 9number(val = 81*10+3 = 813)number(val = 8*10+1 = 81)digit(val= 3)digit(val = 1 )digit(val = 8)digit(val = 8)83 1 圖8.1 數(shù)813帶屬性計(jì)算的的語(yǔ)法分析樹(shù) 編

12、譯原理與技術(shù)148.2 屬性與屬性文法例8.2 考慮的簡(jiǎn)單算術(shù)表達(dá)式的語(yǔ)法G5.1：E E + T |E - T | TT T F | FF (E) | num文法規(guī)則語(yǔ)義規(guī)則E1 E2 + TE1.val := E2 .val + T.valE1 E2 - TE1.val := E2 .val T.valE TE.val := T.valT1 T2 FT1.val := T2 .val * F.valT FT.val := F.valF (E)F.val := E.valF numF.val := num.val主要屬性就是所有非終結(jié)符的數(shù)值，記做val。這些屬性等式描述了表達(dá)式的語(yǔ)法關(guān)系以

13、及要執(zhí)行的算術(shù)運(yùn)算的語(yǔ)義。注意，這個(gè)文法沒(méi)有把num當(dāng)作非終結(jié)符，也就沒(méi)有num.val在等號(hào)左邊的屬性等式，所以，使用該屬性文法時(shí)num.val的值必須在語(yǔ)義分析前（通常由詞法分析器）得到。 如果想明顯地在文法中計(jì)算num的屬性值，可以增加產(chǎn)生式規(guī)則，并對(duì)這個(gè)屬性文法增加如同例子8.1一樣的屬性等式。 編譯原理與技術(shù)158.2 屬性與屬性文法 (523)30的計(jì)算語(yǔ)義表示在如圖8.2的語(yǔ)法分析樹(shù)中。 自底向上地遍歷樹(shù)就可以得到表達(dá)式的值。 E(val =1470) E (val = 523= 49)num(val= 30)T(val = 1)E(val = 52)E(val = 49*30

14、= 1470)F(val= 30)T(val = 49)() F(val = 3)num(val = 3)F(val = 53)num(val = 52)T(val = 52)編譯原理與技術(shù)168.2 屬性與屬性文法例8.3: 考慮下面這個(gè)表示變量聲明的語(yǔ)法G8.2：decl type var-listtype int | floatvar-list id, var-list | id我們希望為聲明中標(biāo)識(shí)符代表的每個(gè)變量定義一個(gè)數(shù)據(jù)類型的屬性，并且構(gòu)造屬性等式來(lái)表達(dá)數(shù)據(jù)類型屬性與聲明類型的關(guān)系。定義的dtype表示數(shù)據(jù)類型屬性。屬性dtype的取值范圍是集合integer, real，對(duì)應(yīng)了符

15、號(hào)int和float。非終結(jié)符type的屬性dtype由其所代表的符號(hào)給定。根據(jù)語(yǔ)法規(guī)則decl type var-list，這個(gè)屬性dtype對(duì)應(yīng)了變量表var-list的dtype。變量表中的每個(gè)標(biāo)識(shí)符id都有相同的屬性dtype。注意，非終結(jié)符decl沒(méi)有屬性定義。事實(shí)上，并非每個(gè)文法符號(hào)都需要定義屬性和屬性等式。文法規(guī)則語(yǔ)義規(guī)則decl type var-listvar-list.dtype := type .dtypetype inttype.dtype := integertype floattype.dtype := realvar-list1 id, var-list2id.t

16、ype := var-list1.dtypevar-list2.type := var-list1.dtypevar-list idid.type := var-list.dtype編譯原理與技術(shù)178.2 屬性與屬性文法例8.4 考慮下面這個(gè)對(duì)文法G8.1做了改動(dòng)的文法G8.3：based-num num basecharbasechar o | dnum num digit | digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9定義的數(shù)可以是8進(jìn)制（末尾是記號(hào)o）、也以是10進(jìn)制（末尾是記號(hào)d）。在這中情況下，num和digit需要一個(gè)新的表示

17、底數(shù)的屬性base，用于計(jì)算值屬性val。 文法規(guī)則語(yǔ)義規(guī)則based-num num basecharbased-num.val := num.valnum.base := basechar.basebasechar obasechar.base := 8basechar dbasechar.base := 10num1 num2 digitnum1.val := if digit.val = error or num2 .val = errorthen errorelse num2 .val num1.base + digit.valnum2.base := num1.basedigit.

18、base := num1.basenum digitnum.val := digit.valdigit 0digit.val := 0digit 1digit.val := 1.digit 7digit.val := 7digit 8digit.val := if digit.base = 8 then error else 8digit 9digit.val := if digit.base = 8 then error else 9編譯原理與技術(shù)188.2 屬性與屬性文法這個(gè)屬性文法出現(xiàn)了兩個(gè)新的特性 這個(gè)文法沒(méi)有排除八進(jìn)制數(shù)時(shí)錯(cuò)誤的數(shù)字8和9。例如，按照語(yǔ)法規(guī)則298o是個(gè)正確的符號(hào)串，

19、但是不能賦予任何值，這就需要引進(jìn)一個(gè)新值error，表示出錯(cuò)。屬性文法必須描述對(duì)于后綴o，一旦符號(hào)串包含了數(shù)字8或9就出錯(cuò)這中事實(shí)。它的最簡(jiǎn)單的實(shí)現(xiàn)方法是在屬性等式的函數(shù)中使用一個(gè)if-then-else表達(dá)式或類似C中的條件表達(dá)式運(yùn)算“?:”。例如，對(duì)應(yīng)文法num num digit的屬性等式num1.val := if digit.val = error or num2 .val = errorthen errorelse num2 .val num1.base + digit.val表達(dá)了如下的情況：如果digit.val或num2 .val其中的一個(gè)是error，那么num1.val也

20、必須是error；否則，num1.val的值由公式num2 .val num1.base + digit.val給出。編譯原理與技術(shù)198.2 屬性與屬性文法屬性文法的形式化定義一個(gè)屬性文法AG是一個(gè)三元組，其中G是一個(gè)上下文無(wú)關(guān)文法，稱作基礎(chǔ)文法，當(dāng)同一個(gè)符號(hào)在產(chǎn)生式中多次出現(xiàn)時(shí)要用序號(hào)加以區(qū)別；A是有限的屬性集合，G中的符號(hào)X關(guān)聯(lián)于屬性集A(X)，X的一個(gè)屬性a記做X.a；R是有限的屬性等式的集合。對(duì)于一組屬性a1,a2,.,am和文法G的每個(gè)產(chǎn)生式X0X1X2.Xn（X0是非終結(jié)符，其它的Xi是任意符號(hào)），屬性等式或語(yǔ)義規(guī)則的形式：Xi. aji(a1,a2,.,am)。i一般是表達(dá)式，

21、可以函數(shù)甚至是子程序。編譯原理與技術(shù)208.2 屬性與屬性文法屬性文法的簡(jiǎn)化與擴(kuò)展可以在屬性等式中使用這些的元語(yǔ)言盡量地接近實(shí)際的程序語(yǔ)言，以便把屬性等式轉(zhuǎn)換成語(yǔ)義分析器中的工作代碼 。在屬性等式中應(yīng)用在定義好的函數(shù) 。使用二義性的更加簡(jiǎn)單的基礎(chǔ)文法 。編譯原理與技術(shù)218.2 屬性與屬性文法抽象語(yǔ)法樹(shù)在參考文獻(xiàn)中，通常把抽象語(yǔ)法樹(shù)AST（Abstract Syntax Tree）簡(jiǎn)稱為語(yǔ)法樹(shù)，而把語(yǔ)法分析樹(shù)（parsing tree）簡(jiǎn)稱為分析樹(shù)。在語(yǔ)法樹(shù)中，算符和關(guān)鍵字不是作為葉結(jié)點(diǎn)，而是作為內(nèi)部結(jié)點(diǎn)，它們對(duì)應(yīng)分析樹(shù)中的這些葉結(jié)點(diǎn)的父結(jié)點(diǎn)?？砂聪旅娴牟襟E從分析樹(shù)構(gòu)造出相應(yīng)的語(yǔ)法樹(shù)：去掉與單

22、非產(chǎn)生式相關(guān)的子樹(shù)，并上提相關(guān)分支上的終結(jié)符結(jié)點(diǎn)；對(duì)于直接包含運(yùn)算符的多個(gè)子樹(shù)，用算符取代其父結(jié)點(diǎn)；去掉括號(hào)并上提算符，讓它代替父結(jié)點(diǎn)。 編譯原理與技術(shù)228.2 屬性與屬性文法對(duì)于產(chǎn)生式S if E then S1 else S2，可以看成是一個(gè)三元算符的式子，它的語(yǔ)法樹(shù)如下圖表達(dá)式8+1*3的語(yǔ)法樹(shù)示意在下圖S1if-then-elseS2B3+*81編譯原理與技術(shù)238.2 屬性與屬性文法例8.5 對(duì)于例8.2中的算術(shù)表達(dá)式的文法G5.1，可以用表8.7的屬性文法定義表達(dá)式的抽象語(yǔ)法樹(shù)。其中number.lexval指出它是由掃描器構(gòu)造出來(lái)的；輔助函數(shù)mknode(op, left, r

23、ight)把輸入的三個(gè)參數(shù)構(gòu)造成一個(gè)樹(shù)結(jié)點(diǎn)，標(biāo)號(hào)是第一個(gè)參數(shù)，兩個(gè)域left和right分別指向左子樹(shù)和右子樹(shù)；mkleaf(num, num.lexval)構(gòu)造一個(gè)標(biāo)記為num的葉結(jié)點(diǎn)，其中的一個(gè)域代表具有參數(shù)值的數(shù)。表8.7 構(gòu)造算術(shù)表達(dá)式抽象語(yǔ)法樹(shù)的屬性文法文法規(guī)則語(yǔ)義規(guī)則E1 E2 + TE1.tree := mknode(+, E2 .tree, T.tree)E1 E2 - TE1.tree := mknode(, E2 .tree, T.tree)E TE.tree := T.treeT1 T2 FT1.tree := mknode(*, T2 .tree, F.tree)T F

24、T.tree := F.treeF (E)F. tree := E. treeF numF. tree := mkleaf(num.lexval)編譯原理與技術(shù)248.2 屬性與屬性文法圖8.6給出了表達(dá)式(523)30根據(jù)表8.6的規(guī)則構(gòu)造的抽象語(yǔ)法樹(shù)，同時(shí)也畫出了相應(yīng)的分析樹(shù)（虛線）。 num30 num 52num 3E treeE tree E treeE tree T treenumnumnum * E treeF tree *編譯原理與技術(shù)258.2 屬性與屬性文法利用屬性文法說(shuō)明屬性的一個(gè)中心問(wèn)題是：如何確保一個(gè)特定的屬性文法一致性和完整性，即唯一地定義可給定的屬性？對(duì)于這個(gè)問(wèn)題

25、我們目前無(wú)法給出簡(jiǎn)單的答案。這個(gè)問(wèn)題類似于確定一個(gè)文法是否是二義的。在實(shí)踐中，我們使用的語(yǔ)法分析算法決定一個(gè)文法的適應(yīng)性，類似的情況出現(xiàn)在屬性文法：計(jì)算屬性的算法決定一個(gè)屬性文法的一致性和完整性。 編譯原理與技術(shù)268.3 屬性的計(jì)算 依賴圖和計(jì)算順序名字的訪問(wèn)前面描述的屬性等式Xi. aji(a1,a2,.,am)可以看作是把等號(hào)右部的函數(shù)表達(dá)式的值賦給等號(hào)左部的屬性Xi.aj。為了可以賦值，出現(xiàn)在右部函數(shù)中的所有屬性的值必須已經(jīng)存在。實(shí)現(xiàn)屬性文法的算法必須為屬性的計(jì)算找到一個(gè)合適順序，確保在進(jìn)行計(jì)算的時(shí)候每個(gè)需要的屬性值都可以得到。屬性等式本身已經(jīng)蘊(yùn)含了計(jì)算屬性順序的約束，屬性計(jì)算的首要任

26、務(wù)是利用有向圖把這些隱含的順序約束明確地表示出來(lái)，這個(gè)有向圖就叫做屬性依賴圖。圖的結(jié)點(diǎn)標(biāo)號(hào)是一個(gè)屬性，如果屬性a的計(jì)算依賴于屬性b，那么，存在從結(jié)點(diǎn)a到結(jié)點(diǎn)b的一條有向邊。 編譯原理與技術(shù)278.3 屬性的計(jì)算語(yǔ)法產(chǎn)生式var-list id, var-list有兩條關(guān)聯(lián)的屬性等式：id.type := var-list1.dtype var-list2.type := var-list1.dtype對(duì)應(yīng)這個(gè)候選產(chǎn)生式的依賴圖是語(yǔ)法規(guī)則var-list id和decl type var-list的依賴圖分別var-list.dtypevar-list.dtypid.dtypevar-list.

27、dtype id.dtypetype.dtypevar-list.dtype編譯原理與技術(shù)288.3 屬性的計(jì)算如果依賴圖和分析樹(shù)同時(shí)畫出，通常把樹(shù)結(jié)點(diǎn)標(biāo)記的屬性省去，而把它寫在結(jié)點(diǎn)的旁邊比如，串float x,y分析樹(shù)的依賴圖如圖8.7所示decltype dtype var-listid(x), var-listfloatid (y)dtypedtypedtypedtype編譯原理與技術(shù)298.3 屬性的計(jì)算例8.7 下面四個(gè)產(chǎn)生式based-num num basecharnum num digitnum digitdigit 9和串813o構(gòu)造依賴圖。(1)為based-num num

28、 basechar構(gòu)造依賴圖： valvalbasebasebasecharnumbased-num(2) 為語(yǔ)法產(chǎn)生式num num digit構(gòu)造對(duì)應(yīng)的依賴圖 valvalbasevaldigitnumnumbasebase這個(gè)圖表達(dá)了下面三個(gè)屬性等式的依賴關(guān)系：num1.val := if digit.val = error or num2 .val = error then error else num2 .val num1.base + digit.valnum2.base := num1.basedigit.base: = num1.base編譯原理與技術(shù)308.3 屬性的計(jì)算(3

29、) 語(yǔ)法規(guī)則num digit和digit 1的依賴圖分別如下 basebasebasenumdigit val valvaldigit 9(4) 為數(shù)字串813o構(gòu)造的分析樹(shù)的依賴圖顯示如下 valvalbasebasebasecharnum based-numvalbasevaldigitnumbasevalbasevaldigitnumbaseo3valdigitbase81編譯原理與技術(shù)318.3 屬性的計(jì)算定義8.5 對(duì)于包含了k結(jié)點(diǎn)的有向圖，結(jié)點(diǎn)的拓?fù)渑判騧1, m2,., mk使得任何一條邊在這個(gè)序列中都是mi在mj之前出現(xiàn)例8.8 圖8.8的依賴圖是一個(gè)有向無(wú)環(huán)圖。圖8.9只畫

30、出了依賴圖，按照結(jié)點(diǎn)編號(hào)的順序得到的結(jié)點(diǎn)排序就是這個(gè)依賴圖的一個(gè)拓?fù)渑判?。另外一個(gè)拓?fù)渑判蚴窍铝薪Y(jié)點(diǎn)編號(hào)的序列：12，6，9，1，2，11，3，8，4，5，7，10，13，14valvalbasebase113 14valbaseval1210basevalbaseval97basevalbase23456811編譯原理與技術(shù)328.3 屬性的計(jì)算使用依賴圖的拓?fù)渑判蛴?jì)算屬性值的一個(gè)關(guān)鍵問(wèn)題是，如何找到圖的根的屬性值。一個(gè)圖的根是沒(méi)有前驅(qū)的結(jié)點(diǎn)。例如，圖8.9中編號(hào)為1、6、9和12的結(jié)點(diǎn)都沒(méi)有前驅(qū)，是圖的根。這些結(jié)點(diǎn)上的屬性值獨(dú)立于其它任何屬性，必須利用可以直接得到的信息求值。而這些信息通常

31、就是對(duì)應(yīng)分析樹(shù)中結(jié)點(diǎn)子女的終結(jié)符串的形式。例如，圖8.9中結(jié)點(diǎn)6的屬性val依賴于于符號(hào)8，它是屬性val對(duì)應(yīng)的結(jié)點(diǎn)digit的子女（參見(jiàn)圖8.8）。所以，結(jié)點(diǎn)6的屬性值是8。所有這種根的屬性值都必須在其它任何屬性求值之前計(jì)算出來(lái)。這些計(jì)算通常由掃描器或語(yǔ)法分析器完成。 編譯原理與技術(shù)338.3 屬性的計(jì)算綜合屬性和S-屬性文法定義8.6 一個(gè)屬性是綜合屬性，如果它的所有依賴點(diǎn)都是從分析樹(shù)的子女到父母結(jié)點(diǎn)。換句話，屬性a是綜合屬性，如果對(duì)于文法AX1X2.Xn，a在左邊的與a關(guān)聯(lián)的屬性等式只有下列形式：A.a( X1.a1,., X1.ak,., Xn.a1,., Xn.ak)其中a1,. a

32、k是所有的屬性。其它屬性叫做繼承屬性。所有屬性都是綜合屬性的屬性文法稱作S-屬性文法。按照定義可知，全部非終結(jié)符的屬性都是綜合屬性；同一產(chǎn)生式中相同符號(hào)的個(gè)綜合屬性之間沒(méi)有依賴關(guān)系；如果b使某個(gè)產(chǎn)生式中符號(hào)X的繼承屬性，那么屬性b的值僅僅依賴于該產(chǎn)生式右部位于符號(hào)X的左邊的符號(hào)的屬性。編譯原理與技術(shù)348.3 屬性的計(jì)算S-屬性文法的屬性計(jì)算可以用自底向上或者后序遍歷（深度優(yōu)先）分析樹(shù)/語(yǔ)法樹(shù)的方式一趟完成。這可以表達(dá)成下列的遞歸后序遍歷屬性求值的算法：procedure postEvaluation (T: treenode)beginfor T中的每個(gè)子女結(jié)點(diǎn)C dopostEvaluat

33、ion (C); 計(jì)算T的所有綜合屬性；end postEvaluation;編譯原理與技術(shù)358.3 屬性的計(jì)算例8.9 可以用C語(yǔ)言實(shí)現(xiàn)構(gòu)造表達(dá)式的語(yǔ)法樹(shù)。首先定義語(yǔ)法數(shù)的數(shù)據(jù)結(jié)構(gòu)typedef enumPlus, Minus, Times OPKind;typedef enumOPKind, COnstKind ExpKind;typedef struct treenodeExpKind kind;OPKind op;struct treenode *lchild, * rchild;int val; Treenode;typedef Treenode *SyntaxTree;然后，把算

34、法postEvaluation翻譯成下列C代碼。void postEval(SyntaxTree tree) int temp; if (tree kind = = OPKind) postEval(tree lchild); postEval(tree rchild); switch (tree op) case Plus: tree val = tree lchildval + tree rchildval; case Minus: tree val = tree lchildval tree rchildval; case Times: tree val = tree lchildval

35、 * tree rchildval; 編譯原理與技術(shù)368.3 屬性的計(jì)算單純計(jì)算繼承屬性可以通過(guò)前序遍歷，或者前序遍歷和中序遍歷分析樹(shù)來(lái)完成，如下列算法所示：procedure preEval (T: treenode)beginfor T中的每個(gè)子女結(jié)點(diǎn)C do計(jì)算T的所有繼承屬性；preEval (C);end for;end preEval;由于繼承屬性可能依賴于子女的屬性，與綜合屬性求值不同，在計(jì)算繼承屬性的時(shí)候，子女繼承屬性的計(jì)算順序非常重要。上述代碼中對(duì)于T中的每個(gè)子女結(jié)點(diǎn)C的訪問(wèn)順序必須滿足這些依賴關(guān)系。編譯原理與技術(shù)378.3 屬性的計(jì)算例8.11 考慮表達(dá)式文法的一個(gè)簡(jiǎn)單版

36、本G8.5：exp exp / exp | num | num. num設(shè)計(jì)這個(gè)文法的想法是，運(yùn)算符依據(jù)操作數(shù)是浮點(diǎn)數(shù)還是整數(shù)可以有完全不同的解釋。特別是除法運(yùn)算，是否允許小數(shù)部分，是有區(qū)別的。如果不允許有小數(shù)部分，除法符號(hào)通常記做div，這樣，5/4就是5div4=1。否則，就是浮點(diǎn)除法，5/4 =1.2。描述這些語(yǔ)義需要三個(gè)屬性：綜合的布爾屬性isFloat指出一個(gè)表達(dá)式的任何部分是否是浮點(diǎn)數(shù)；一個(gè)具有值int和float的繼承屬性etype，根據(jù)isFloat的值指出每個(gè)子表達(dá)式的類型；最后一個(gè)是依據(jù)etype而計(jì)算每個(gè)子表達(dá)式得到的值。 文法規(guī)則語(yǔ)義規(guī)則exp1 exp2 / exp3

37、exp1.isFloat := exp2.isFloat OR exp3.isFloatexp2.etype := exp1.etypeexp3.etype := exp1.etypeexp1.val := if exp1.etype = int then exp2.val div exp3.val else exp2.val / exp3.valexp numexp.isFloat := Falseexp.val := if exp.etype = int then num.val else float(num.val)exp num. num exp.isFloat := Trueexp.

38、val := num. num.val屬性isFloat、etype和val需要兩次遍歷分析樹(shù)或語(yǔ)法樹(shù)才能計(jì)算出來(lái)。第一遍后序遍歷計(jì)算出綜合屬性isFloat的值；第二遍混合的前序遍歷和后序遍歷計(jì)算出繼承屬性etype與綜合屬性val的值編譯原理與技術(shù)388.3 屬性的計(jì)算S-屬性文法的自底向上計(jì)算 在LR分析方法中，我們通常使用一個(gè)棧來(lái)存放已經(jīng)分析過(guò)的子樹(shù)的信息?，F(xiàn)在，增加一個(gè)屬性值棧，或者在分析棧中增加一個(gè)子域，存放屬性值。這個(gè)屬性值棧和分析棧被同步地操作，每當(dāng)分析棧發(fā)生移進(jìn)或歸約時(shí)，就根據(jù)屬性等式計(jì)算新的屬性值，并存放在屬性值棧內(nèi)。圖8.10給出了一個(gè)示意圖 。 狀態(tài) 屬性值 . . Z

39、 Z.z Y Y.y X X.x . .棧top圖8.10 帶綜合屬性域的分析棧設(shè)當(dāng)前的棧頂由指針top指示，并假定綜合屬性剛好在每次歸約前計(jì)算。譬如產(chǎn)生式A XYZ的語(yǔ)義規(guī)則是A.a = (X.x, Y.y, Z.z)那么，在XYZ歸約成A之前，屬性Z.z的值在棧頂即，valtop，屬性Y.y的值在valtop1，屬性X.x的值在valtop2。如果某個(gè)符號(hào)沒(méi)有綜合屬性，那么，數(shù)組val對(duì)應(yīng)的元素就沒(méi)有定義。歸約后，top的值減2，代表A的狀態(tài)放在當(dāng)前棧頂statetop（即原先X的位置），根據(jù)相應(yīng)屬性等式計(jì)算得到的綜合屬性A.a的值放在valtop。 編譯原理與技術(shù)398.3 屬性的計(jì)算例

40、8.12 考慮下列一個(gè)臺(tái)式計(jì)算器的文法G8.5及其語(yǔ)義規(guī)則：文法規(guī)則語(yǔ)義規(guī)則語(yǔ)義分析代碼段L Enprint(E.val)print (valtop-1)E E1 + TE.val := E1.val + T.valvaltop-2 := valtop-2 + valtopE TE.val := T.valT T1 FT.val := T1.val * F.valvaltop-2 := valtop-2 * valtopT FT.val := F.valF (E)F.val := E.valvaltop-2 := valtop-1F digitF.val := digit.lexval每個(gè)非終

41、結(jié)符都有一個(gè)存放數(shù)值的綜合屬性val，終結(jié)符digit的綜合屬性lexval由詞法掃描器給出，就是每個(gè)數(shù)字的值。語(yǔ)義分析代碼段是把語(yǔ)義規(guī)則中的屬性用val數(shù)組替換得到的。屬性計(jì)算的結(jié)果都是放在valtop2，這是因?yàn)榍『脤?duì)應(yīng)的產(chǎn)生式的右部都是3個(gè)符號(hào)。這里的top指歸約前的棧頂，歸約以后它的值會(huì)根據(jù)右部符號(hào)的多少進(jìn)行調(diào)整。 編譯原理與技術(shù)408.3 屬性的計(jì)算我們用相應(yīng)的文法符號(hào)代替state的狀態(tài)，給出實(shí)際的輸入數(shù)字的值而不是符號(hào)digit，而且假定分析器把digit移進(jìn)棧時(shí)，記號(hào)digit進(jìn)入statetop，其屬性值放在valtop。我們討論看第一個(gè)符號(hào)8時(shí)的動(dòng)作序列。第一步，分析器把對(duì)

42、符號(hào)digit對(duì)應(yīng)的狀態(tài)（用8表示，其值8存放val域）移入棧中；第二步，分析器按照產(chǎn)生式F digit進(jìn)行歸約，并執(zhí)行語(yǔ)義規(guī)則F.val := digit.lexval的計(jì)算；第三步，分析器按照產(chǎn)生式T F進(jìn)行歸約，沒(méi)有代碼段與這個(gè)產(chǎn)生式對(duì)應(yīng)，所以val數(shù)組的值沒(méi)有改變。注意，每次歸約后val棧頂存放的都是所用產(chǎn)生式左部符號(hào)的屬性值。輸入狀態(tài)state屬性值val用到的產(chǎn)生式8+1*3n+1*3n88+1*3nF8F digit+1*3nT8T F+1*3nE8E T1*3nE+8+*3nE+18+1*3nE+F8+1F digit*3nE+T8+1T F3nE+T*8+1*nE+T*38+

43、1*3nE+T*F8+1*3F digitnE+T8+3T T*FnE11E E+TEn18-L18L En對(duì)輸入串8+1*3n基于LR分析器的語(yǔ)義動(dòng)作 編譯原理與技術(shù)418.3 屬性的計(jì)算翻譯模式與L-屬性文法自頂向下計(jì)算 定義8.7 對(duì)于一組屬性a1,a2,.,am的屬性文法AG是L-屬性文法，如果對(duì)于每個(gè)繼承屬性aj以及每個(gè)產(chǎn)生式X0 X1X2.Xn（X0是非終結(jié)符，其它的Xi是任意符號(hào)），和aj關(guān)聯(lián)的屬性等式的形式都是：Xi. aj( X1.a1,., X1.ak, X1.a1,., X1.ak,., Xi-1.a1,., Xi-1.ak) 即，Xi的aj僅僅依賴于出現(xiàn)在Xi左邊符號(hào)X

44、0，X1，.，Xi-1的屬性。S-屬性文法作為一個(gè)特例也是L-屬性文法。編譯原理與技術(shù)428.3 屬性的計(jì)算對(duì)于一個(gè)L-屬性文法，它的繼承屬性都不依賴綜合屬性，可以在自頂向下的遞歸下降分析過(guò)程計(jì)算出所有的屬性值。但是，LR分析器，如yacc生成的LALR(1)分析器，卻主要適合處理綜合屬性或S-屬性文法。LL分析技術(shù)只有在推導(dǎo)過(guò)程知道了使用的語(yǔ)法規(guī)則時(shí)才能計(jì)算屬性，因?yàn)橹挥心菚r(shí)才有確定的計(jì)算屬性的等式。而LR分析器在推導(dǎo)過(guò)程推遲決定使用哪個(gè)產(chǎn)生式，直到一個(gè)產(chǎn)生式的右部完全形成。這就難易得到繼承屬性的值，除非它們的性質(zhì)對(duì)于所有右邊的候選式都是固定的。編譯原理與技術(shù)438.3 屬性的計(jì)算上面介紹的

45、根據(jù)語(yǔ)義規(guī)則編寫的語(yǔ)義分析代碼段是放在文法產(chǎn)生式的后面，只能在歸約前執(zhí)行。翻譯模式把代碼段表示的語(yǔ)義動(dòng)作放在花括弧內(nèi)，如同yacc的語(yǔ)義動(dòng)作，并且可以插在產(chǎn)生式右部的任何地方。這樣，翻譯模式就給出了語(yǔ)義動(dòng)作的執(zhí)行順序。若A.，則.中的語(yǔ)義動(dòng)作在的推導(dǎo)（或向的歸約）結(jié)束后、在的推導(dǎo)（或向的歸約）開(kāi)始前執(zhí)行?？梢园阎g的語(yǔ)義動(dòng)作想象測(cè)繪那個(gè)為一個(gè)文法符號(hào)，在分析過(guò)程對(duì)該“符號(hào)”的推導(dǎo)或歸約就是執(zhí)行器語(yǔ)義動(dòng)作。編譯原理與技術(shù)448.3 屬性的計(jì)算例8.13 面是一個(gè)簡(jiǎn)單的翻譯模式的例子，它把有加號(hào)和減號(hào)的中綴表達(dá)式翻譯成后綴表達(dá)式。E TRE addop T print (addop.lexval

46、R | E id print (id.lexval第二行的動(dòng)作print (addop.lexval必須放在T和R之間，移到別的位置都不會(huì)得到正確的結(jié)果。例如，如果輸入a+bc，該翻譯模式的輸出是ab+c。 編譯原理與技術(shù)458.3 屬性的計(jì)算圖8.11表示了分析輸入串a(chǎn)+bc的語(yǔ)法樹(shù)，每個(gè)語(yǔ)義動(dòng)作都作為相應(yīng)產(chǎn)生式左部符號(hào)的結(jié)點(diǎn)的子女。這樣，把語(yǔ)義動(dòng)作看作是終結(jié)符號(hào)，表示在什么時(shí)候執(zhí)行哪些動(dòng)作。為了便于說(shuō)明，圖中用實(shí)際的數(shù)字和運(yùn)算符代替了單詞id和addop。當(dāng)按照深度優(yōu)先或后序遍歷語(yǔ)法樹(shù)的時(shí)候，就執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作，打印出ab+c。 ETR+EabEprint()Tprint(a)print

47、(b)print(+)print(c)Rc編譯原理與技術(shù)468.3 屬性的計(jì)算對(duì)于既有綜合屬性、又有繼承屬性的更一般的L-屬性文法，在建立翻譯模式時(shí)必須遵循下列三個(gè)條件：產(chǎn)生式右部符號(hào)的繼承屬性必須在這個(gè)符號(hào)之前的動(dòng)作中計(jì)算；一個(gè)動(dòng)作不能引用該動(dòng)作左邊符號(hào)的綜合屬性；產(chǎn)生式左邊非終結(jié)符的綜合屬性只能在它所引用的所有屬性都計(jì)算完后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通常放在產(chǎn)生式右部的末端。編譯原理與技術(shù)478.3 屬性的計(jì)算例8.14 表8.12是根據(jù)表8.3設(shè)計(jì)的翻譯模式，它的基礎(chǔ)文法是含左遞歸的簡(jiǎn)單算術(shù)文法G5.1（為了簡(jiǎn)化省去了減法），其中的屬性val是綜合屬性。文法規(guī)則語(yǔ)義規(guī)則翻譯模式E1 E

48、2 + TE1.val := E2 .val + T.valE1.val := E2 .val + T.valE TE.val := T.valE.val := T.valT1 T2 FT1.val := T2 .val * F.valT1.val := T2 .val * F.valT FT.val := F.valT.val := F.valF (E)F.val := E.valF.val := E.valF numF.val := num.valF.val := num.val編譯原理與技術(shù)488.3 屬性的計(jì)算為了能夠用LL方法分析，必須消去基礎(chǔ)文法的左遞歸，這就導(dǎo)致產(chǎn)生了繼承屬性。改

49、造后的翻譯模式如下所示。我們?yōu)樾碌姆墙K結(jié)符R引入了繼承屬性i和綜合屬性s，作用就是對(duì)應(yīng)產(chǎn)生式R 把R的繼承屬性值傳給其綜合屬性。這個(gè)翻譯模式中，每個(gè)數(shù)都是由T產(chǎn)生的，而且T.val的值就是由屬性num.lexval給出的數(shù)的詞法值。E T R.i := T.val R E.val := R.sR + T R1.i := R.i +T.val R1 R.s := R1.s R * T R1.i := R.i *T.val R1 R.s := R1.s R R.s := R.i T (E) T.val := E.val T num T.val := num.lexval 編譯原理與技術(shù)498.3

50、屬性的計(jì)算圖8.13給出了按照上述翻譯模式對(duì)輸入串(8+1)*3的計(jì)算。子表達(dá)式8+1中的數(shù)8是由最左邊的T生成的，但是加號(hào)和1卻是由根的右結(jié)點(diǎn)R生成的。繼承屬性R.i從T.val得到值8。計(jì)算8+1并把結(jié)果9傳遞到中間的R結(jié)點(diǎn)，這是通過(guò)產(chǎn)生式中嵌入的動(dòng)作 R1.i := R.i +T.val完成的。類似的動(dòng)作把3乘到8+1的值上，在最下面的R結(jié)點(diǎn)中產(chǎn)生結(jié)果R.i=27；這個(gè)結(jié)果通過(guò)動(dòng)作 R.s := R.i 和E.val := R.s向上復(fù)制完成。E.val =27R.i =8*+T.val =1R.i =9num.val =8num.val =1T.val =3R.i =27T.val =

51、8 num.val =3R.s =27R.s =27R.s =27編譯原理與技術(shù)508.3 屬性的計(jì)算根據(jù)L-屬性構(gòu)造遞歸下降屬性求值器的方法為每個(gè)非終結(jié)符A構(gòu)造一個(gè)函數(shù)，其形式參數(shù)是A的所有繼承屬性，返回值是A的綜合屬性（可以是記錄，或者指向記錄的一個(gè)指針，每個(gè)綜合屬性對(duì)應(yīng)一個(gè)子域）；在函數(shù)體內(nèi)為含A的產(chǎn)生式中其它文法符號(hào)的每個(gè)屬性都聲明一個(gè)局部變量，把屬性B.b對(duì)應(yīng)的局部變量記做B.b。每個(gè)產(chǎn)生式對(duì)應(yīng)的程序代碼，是從左到右依次考察單詞記號(hào)、非終結(jié)符和語(yǔ)義動(dòng)作，按照下列方法編寫的：（1）對(duì)于帶有綜合屬性c的符號(hào)X，把c的值存入聲明為X.c的局部變量中；然后產(chǎn)生匹配X的調(diào)用，并掃描下一個(gè)輸入符

52、號(hào)；（2）對(duì)于非終結(jié)符B，產(chǎn)生一個(gè)右邊是函數(shù)調(diào)用的賦值語(yǔ)句c := B(b1,b2, ., bk)，其中c是為B的綜合屬性設(shè)置的變量，輸入?yún)?shù)b1,b2, ., bk是B的繼承屬性；（3）對(duì)于每個(gè)語(yǔ)義動(dòng)作，把代碼復(fù)寫到求值器中，把對(duì)屬性的引用改成對(duì)相應(yīng)局部變量的引用。編譯原理與技術(shù)518.3 屬性的計(jì)算例8.15 圖8.12的基礎(chǔ)文法是LL(1)文法，適合自頂向下的分析和屬性求值。非終結(jié)符E、R和T的函數(shù)聲明如下，其中E和T沒(méi)有繼承屬性，所以，它們的函數(shù)沒(méi)有輸入?yún)?shù)，Number表示類型。function E : Number;function R (i: Number): Number;fu

53、nction T : Number;圖8.14是根據(jù)上述方法編寫的算術(shù)表達(dá)式的遞歸下降屬性求值器。其中g(shù)etchar超前搜索下一個(gè)符號(hào)并存入變量token，函數(shù)isNumber判斷輸入?yún)?shù)是否是一個(gè)數(shù)值，過(guò)程error報(bào)錯(cuò)。function E : Number;Number i, s, val1, val2;/* val1是T的屬性，val2是E的屬性*/begin val1 := T; i := val1；/* 把語(yǔ)義動(dòng)作拷貝過(guò)來(lái)，用臨時(shí)變量取代屬性 */ s := R(i); val2 := send;function R (i: Number): Number;Number i1, i

54、, s1, s, val; 編譯原理與技術(shù)528.3 屬性的計(jì)算function R (i: Number): Number;Number i1, i, s1, s, val;begin switch token of case +: /* 對(duì)應(yīng)產(chǎn)生式R + T R1 */ getchar;val := T;i1 := i + val;s1 := R(i1);s := s1; case *: /* 對(duì)應(yīng)產(chǎn)生式R * T R1 */getchar;val := T;i1 := i * val;s1 := R(i1);s := s1; default: s := i；/* 對(duì)應(yīng)產(chǎn)生式R */ en

55、d switch;end;function T : Number;Number val1, val2, val3;/* val1是T的屬性，val2是E的屬性, val3是num的屬性*/begin if token = ( then /* 對(duì)應(yīng)產(chǎn)生式T (E) */getchar;val1 := E;if token = ) then getchar; val2 : = val1;else error; else if isNumber(token) /* 對(duì)應(yīng)產(chǎn)生式T num */then getchar; val1 := val3;else error;end;編譯原理與技術(shù)538.3

56、屬性的計(jì)算刪除翻譯模式中嵌入的動(dòng)作對(duì)于屬性文法中每個(gè)嵌入的語(yǔ)義動(dòng)作，用一個(gè)不在原基礎(chǔ)文法的非終結(jié)符號(hào)比如M代替，增加一個(gè)產(chǎn)生式M ，并把嵌入的語(yǔ)義動(dòng)作放在該產(chǎn)生式的末尾。對(duì)于翻譯模式E TRE + T print (+ R | T print ( R | E id print (id.lexval新增兩個(gè)非終結(jié)符M和N后，轉(zhuǎn)換為E TRE + T M R | T N R | M print (+N print (E idprint (id.lexval 編譯原理與技術(shù)548.3 屬性的計(jì)算用綜合屬性代替繼承屬性例8.16 前面多次討論過(guò)的簡(jiǎn)單聲明語(yǔ)句的文法G8.3：decl type var-

57、listtype int | floatvar-list id, var-list | id文法規(guī)則語(yǔ)義規(guī)則decl var-list idid.type = var-list.dtypevar-list1 var-list2 id,var-list1.dtype = var-list2.dtypeid.type = var-list1.dtypevar-list typevar-list.dtype = type.dtypetype intdtype = integertype floatdtype = real在語(yǔ)義規(guī)則表8.3中的屬性dtype是繼承屬性。然而，重寫文法如下：decl v

58、ar-list idvar-list var-list id, | typetype int | float編譯原理與技術(shù)558.4 數(shù)據(jù)類型與類型檢查 類型推斷：計(jì)算并維持?jǐn)?shù)據(jù)類型的信息。類型檢查：使用這些信息來(lái)確保程序的每個(gè)部分語(yǔ)言類型規(guī)則下都有意義。類型化語(yǔ)言：每個(gè)變量都給出了確定類型的語(yǔ)言。類型化語(yǔ)言的優(yōu)點(diǎn)：可以早期發(fā)現(xiàn)程序的錯(cuò)誤，特別是在編譯是發(fā)現(xiàn)程序的語(yǔ)義錯(cuò)誤，避免在程序運(yùn)行時(shí)出錯(cuò)。類型信息可以組織在大型軟件系統(tǒng)中模塊的接口中，便于程序模塊的獨(dú)立開(kāi)發(fā)和集成；同時(shí)，聲明了標(biāo)識(shí)符和表達(dá)式的類型，這些信息有助于理解程序?？梢詫?shí)現(xiàn)各個(gè)模塊的獨(dú)立編譯，一個(gè)模塊的修改不會(huì)引起其它模塊的的重新編

59、譯，有效地提高了大型軟件系統(tǒng)的編譯和開(kāi)發(fā)。在編譯時(shí)搜集的類型信息可以更加合理地安排存儲(chǔ)空間的大小和組織，提高目標(biāo)代碼的時(shí)空效率。編譯原理與技術(shù)568.4 數(shù)據(jù)類型與類型檢查類型表達(dá)式與類型構(gòu)造器 一個(gè)程序變量在程序運(yùn)行期間的值可以想象為有一個(gè)范圍，這個(gè)范圍的界叫做該變量的類型。一個(gè)數(shù)據(jù)類型是一組值以及在這些值上的特定操作。 在實(shí)際的編譯構(gòu)造中，類型的值通常被一個(gè)類型表達(dá)式描述，它可以是一個(gè)類型名，例如integer，或者是結(jié)構(gòu)化表達(dá)式，例如array 1.100 of real，而且隱含了操作。 一個(gè)類型表達(dá)式或者是基本類型，或者由類型構(gòu)造符作用于其類型表達(dá)式組成。編譯原理與技術(shù)578.4 數(shù)

60、據(jù)類型與類型檢查典型的類型構(gòu)造符 數(shù)組 如果I和T都是類型表達(dá)式，I是一個(gè)整數(shù)域，那么，array(I, T)是一個(gè)表示數(shù)組元素為T的類型表達(dá)式 。乘積 如果T1和T2是兩個(gè)類型表達(dá)式，則它們的笛卡兒積T1T2也是一個(gè)類型表達(dá)式。 記錄 記錄或結(jié)構(gòu)類型是通過(guò)作用在一組二元式得到的。 例如，Pascal的紀(jì)錄類型type student = recordname: array 1.20 of char;birthday: Date;sex: integer；end;聲明了一個(gè)student類型，它包含三個(gè)成員。可以表示成：record (name(array(I, char)(birthdayD