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

1、青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)第第8章章屬性文法和語(yǔ)義分析屬性文法和語(yǔ)義分析 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)2主要內(nèi)容主要內(nèi)容u語(yǔ)義分析概況語(yǔ)義分析概況 u屬性與屬性文法屬性與屬性文法u屬性的計(jì)算屬性的計(jì)算 u數(shù)據(jù)類型與類型檢查數(shù)據(jù)類型與類型檢查 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)38.1 語(yǔ)義分析概況語(yǔ)義分析概況 語(yǔ)義分析在編譯程序中的位置語(yǔ)義分析在編譯程序中的位置 程序的語(yǔ)義涉及兩個(gè)方面，即數(shù)據(jù)結(jié)構(gòu)的語(yǔ)程序的語(yǔ)義涉及兩個(gè)方面，即數(shù)據(jù)結(jié)構(gòu)的語(yǔ)義域控制結(jié)構(gòu)的語(yǔ)義。義域控制結(jié)構(gòu)的語(yǔ)義。數(shù)

2、據(jù)結(jié)構(gòu)的語(yǔ)義主要指域標(biāo)識(shí)符相關(guān)聯(lián)的數(shù)數(shù)據(jù)結(jié)構(gòu)的語(yǔ)義主要指域標(biāo)識(shí)符相關(guān)聯(lián)的數(shù)據(jù)對(duì)象，也即量的含義?？刂平Y(jié)構(gòu)的語(yǔ)義是據(jù)對(duì)象，也即量的含義。控制結(jié)構(gòu)的語(yǔ)義是語(yǔ)言定義的。語(yǔ)言定義的。 語(yǔ)法分析器語(yǔ)義分析器中間代碼生成器語(yǔ)法樹語(yǔ)法樹單詞記號(hào)中間代碼青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)48.1 語(yǔ)義分析概況語(yǔ)義分析概況量涉及類型與值，值在程序運(yùn)行時(shí)刻確定，而類型則由程序的量涉及類型與值，值在程序運(yùn)行時(shí)刻確定，而類型則由程序的說明部分來規(guī)定。說明部分來規(guī)定。 例如，例如，int x, y;float z;char array100;把把x、y、z和和array分別與整型、整型

3、、實(shí)型和字符數(shù)組型關(guān)聯(lián)分別與整型、整型、實(shí)型和字符數(shù)組型關(guān)聯(lián)起來，它們分別代表相應(yīng)類型的數(shù)據(jù)對(duì)象。起來，它們分別代表相應(yīng)類型的數(shù)據(jù)對(duì)象。不同類型的數(shù)據(jù)對(duì)象有不同的機(jī)器內(nèi)部表示，占用不同的存儲(chǔ)不同類型的數(shù)據(jù)對(duì)象有不同的機(jī)器內(nèi)部表示，占用不同的存儲(chǔ)空間，有不同的取值范圍，對(duì)它們所能進(jìn)行的運(yùn)算也不同。只空間，有不同的取值范圍，對(duì)它們所能進(jìn)行的運(yùn)算也不同。只有相同類型、因而具有相同機(jī)內(nèi)表示的數(shù)據(jù)對(duì)象，或符合特定有相同類型、因而具有相同機(jī)內(nèi)表示的數(shù)據(jù)對(duì)象，或符合特定要求的數(shù)據(jù)對(duì)象才能進(jìn)行相應(yīng)的運(yùn)算。要求的數(shù)據(jù)對(duì)象才能進(jìn)行相應(yīng)的運(yùn)算。當(dāng)考慮標(biāo)識(shí)符的相關(guān)含義時(shí)還必須要考慮到作用域的問題。當(dāng)考慮標(biāo)識(shí)符的相關(guān)含

4、義時(shí)還必須要考慮到作用域的問題。確定標(biāo)識(shí)符所關(guān)聯(lián)的類型、作用域等屬性信息，進(jìn)行類型正確確定標(biāo)識(shí)符所關(guān)聯(lián)的類型、作用域等屬性信息，進(jìn)行類型正確性的檢查成為語(yǔ)義分析的一個(gè)基本工作。性的檢查成為語(yǔ)義分析的一個(gè)基本工作。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)58.1 語(yǔ)義分析概況語(yǔ)義分析概況例如，對(duì)于例如，對(duì)于C的的while循環(huán)語(yǔ)句：循環(huán)語(yǔ)句：while () ；規(guī)定了首先計(jì)算規(guī)定了首先計(jì)算的值，如果為真的值，如果為真（或非（或非0）時(shí)，就執(zhí)行）時(shí)，就執(zhí)行；然后再計(jì)算然后再計(jì)算的值，并重復(fù)以上過程，的值，并重復(fù)以上過程，直到直到的值為假（或?yàn)榈闹禐榧伲ɑ驗(yàn)?），便結(jié)束

5、循），便結(jié)束循環(huán)語(yǔ)句，執(zhí)行環(huán)語(yǔ)句，執(zhí)行while語(yǔ)句之后的語(yǔ)句。語(yǔ)句之后的語(yǔ)句。語(yǔ)義分析將分析各個(gè)語(yǔ)法結(jié)構(gòu)的含義并做出語(yǔ)義分析將分析各個(gè)語(yǔ)法結(jié)構(gòu)的含義并做出相應(yīng)的語(yǔ)義處理。相應(yīng)的語(yǔ)義處理。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)68.1 語(yǔ)義分析概況語(yǔ)義分析概況u語(yǔ)義分析的基本功能語(yǔ)義分析的基本功能 確定類型確定類型 確定標(biāo)識(shí)符所關(guān)聯(lián)對(duì)象的數(shù)據(jù)類型。這部分工作有確定標(biāo)識(shí)符所關(guān)聯(lián)對(duì)象的數(shù)據(jù)類型。這部分工作有時(shí)由掃描器完成，掃描器將處理源程序的聲明部分。時(shí)由掃描器完成，掃描器將處理源程序的聲明部分。類型檢查類型檢查 按照語(yǔ)言的類型規(guī)則，對(duì)參加運(yùn)算的運(yùn)算分量進(jìn)行按照語(yǔ)言的

6、類型規(guī)則，對(duì)參加運(yùn)算的運(yùn)算分量進(jìn)行類型檢查，檢查運(yùn)算的合法性、運(yùn)算分量類型的一致性（相容類型檢查，檢查運(yùn)算的合法性、運(yùn)算分量類型的一致性（相容性），對(duì)于不相容的運(yùn)算對(duì)象，報(bào)告錯(cuò)誤，必要時(shí)進(jìn)行相應(yīng)的性），對(duì)于不相容的運(yùn)算對(duì)象，報(bào)告錯(cuò)誤，必要時(shí)進(jìn)行相應(yīng)的類型轉(zhuǎn)換。類型轉(zhuǎn)換。l例如，對(duì)于數(shù)組變量個(gè)函數(shù)變量的加法運(yùn)算額出現(xiàn)，報(bào)告語(yǔ)義錯(cuò)例如，對(duì)于數(shù)組變量個(gè)函數(shù)變量的加法運(yùn)算額出現(xiàn)，報(bào)告語(yǔ)義錯(cuò)誤；對(duì)于整型與實(shí)型數(shù)據(jù)對(duì)象的加法，把它們轉(zhuǎn)換成同一類型。誤；對(duì)于整型與實(shí)型數(shù)據(jù)對(duì)象的加法，把它們轉(zhuǎn)換成同一類型。控制流檢查控制流檢查 對(duì)于任何引起控制流離開一個(gè)結(jié)構(gòu)的語(yǔ)句，程序?qū)τ谌魏我鹂刂屏麟x開一個(gè)結(jié)構(gòu)的語(yǔ)句，程

7、序中必須由該控制轉(zhuǎn)移可以轉(zhuǎn)到的地方。中必須由該控制轉(zhuǎn)移可以轉(zhuǎn)到的地方。l例如，例如，C的的break語(yǔ)句引起控制離開最小包圍的語(yǔ)句引起控制離開最小包圍的while、for或或switch語(yǔ)句，如果這樣的包圍語(yǔ)句不存在，則是一個(gè)錯(cuò)誤。語(yǔ)句，如果這樣的包圍語(yǔ)句不存在，則是一個(gè)錯(cuò)誤。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)78.1 語(yǔ)義分析概況語(yǔ)義分析概況u語(yǔ)義分析的基本功能語(yǔ)義分析的基本功能唯一性檢查唯一性檢查 有些場(chǎng)合，對(duì)象必須正好被定義一次。有些場(chǎng)合，對(duì)象必須正好被定義一次。例如，集合中的元素只能出現(xiàn)一次，對(duì)象類的名字不例如，集合中的元素只能出現(xiàn)一次，對(duì)象類的名字不

8、能重復(fù)，分支語(yǔ)句的分情形常量必須區(qū)分能重復(fù)，分支語(yǔ)句的分情形常量必須區(qū)分.l在在Pascal語(yǔ)言中，標(biāo)識(shí)符只能唯一第定義一次。語(yǔ)言中，標(biāo)識(shí)符只能唯一第定義一次。關(guān)聯(lián)名字檢查關(guān)聯(lián)名字檢查 有時(shí)，同樣的名字必須出現(xiàn)兩次或更有時(shí)，同樣的名字必須出現(xiàn)兩次或更多次。多次。l例如，在例如，在C+語(yǔ)言中，構(gòu)造函數(shù)的名字必須和類型一致；在語(yǔ)言中，構(gòu)造函數(shù)的名字必須和類型一致；在Ada語(yǔ)言中，循環(huán)或程序塊可以有名字出現(xiàn)在其開始和結(jié)束，語(yǔ)言中，循環(huán)或程序塊可以有名字出現(xiàn)在其開始和結(jié)束，編譯程序必須檢查兩個(gè)地方的名字是否相同。編譯程序必須檢查兩個(gè)地方的名字是否相同。識(shí)別含義識(shí)別含義 根據(jù)程序語(yǔ)言的形式或非形式語(yǔ)義規(guī)

9、則，根據(jù)程序語(yǔ)言的形式或非形式語(yǔ)義規(guī)則，識(shí)別程序中各個(gè)構(gòu)造成分組合到一起的含義，并做相識(shí)別程序中各個(gè)構(gòu)造成分組合到一起的含義，并做相應(yīng)的語(yǔ)義處理，應(yīng)的語(yǔ)義處理， 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)88.2 屬性與屬性文法屬性與屬性文法 u屬性的引入屬性的引入為了解釋程序的語(yǔ)義、把程序翻譯成可執(zhí)行的代碼，需要對(duì)為了解釋程序的語(yǔ)義、把程序翻譯成可執(zhí)行的代碼，需要對(duì)文法符號(hào)引進(jìn)一些表示程序語(yǔ)言結(jié)構(gòu)性質(zhì)的屬性。文法符號(hào)引進(jìn)一些表示程序語(yǔ)言結(jié)構(gòu)性質(zhì)的屬性。例如變量數(shù)據(jù)類型、表達(dá)式值、存儲(chǔ)地址、過程體代碼以及例如變量數(shù)據(jù)類型、表達(dá)式值、存儲(chǔ)地址、過程體代碼以及數(shù)的有效數(shù)字

10、個(gè)數(shù)等數(shù)的有效數(shù)字個(gè)數(shù)等. 計(jì)算屬性的值并把它和語(yǔ)言結(jié)構(gòu)聯(lián)系起來的過程稱作屬性的計(jì)算屬性的值并把它和語(yǔ)言結(jié)構(gòu)聯(lián)系起來的過程稱作屬性的綁定。屬性綁定發(fā)生在編譯或運(yùn)行過程的時(shí)刻叫做綁定時(shí)刻。綁定。屬性綁定發(fā)生在編譯或運(yùn)行過程的時(shí)刻叫做綁定時(shí)刻。不同屬性的綁定時(shí)刻不同，對(duì)于不同的語(yǔ)言，甚至同樣的屬不同屬性的綁定時(shí)刻不同，對(duì)于不同的語(yǔ)言，甚至同樣的屬性也有不同的綁定時(shí)刻。性也有不同的綁定時(shí)刻。在程序運(yùn)行前綁定的屬性稱為靜態(tài)的，只能在程序運(yùn)行期間在程序運(yùn)行前綁定的屬性稱為靜態(tài)的，只能在程序運(yùn)行期間才能綁定的屬性是動(dòng)態(tài)的。才能綁定的屬性是動(dòng)態(tài)的。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯

11、原理與技術(shù)98.2 屬性與屬性文法屬性與屬性文法u屬性的引入屬性的引入在靜態(tài)類型語(yǔ)言諸如在靜態(tài)類型語(yǔ)言諸如C和和Pascal中，變量或表達(dá)式的中，變量或表達(dá)式的數(shù)據(jù)類型是主要的編譯時(shí)刻的屬性，類型檢查器就數(shù)據(jù)類型是主要的編譯時(shí)刻的屬性，類型檢查器就是一個(gè)語(yǔ)義分析器，它計(jì)算語(yǔ)言實(shí)體的數(shù)據(jù)類型屬是一個(gè)語(yǔ)義分析器，它計(jì)算語(yǔ)言實(shí)體的數(shù)據(jù)類型屬性并驗(yàn)證這些類型符合語(yǔ)言的類型規(guī)則。性并驗(yàn)證這些類型符合語(yǔ)言的類型規(guī)則。而而LISP或或Smalltalk中的數(shù)據(jù)類型是動(dòng)態(tài)的，它們的中的數(shù)據(jù)類型是動(dòng)態(tài)的，它們的編譯必須產(chǎn)生計(jì)算類型的代碼，然后在程序的運(yùn)行編譯必須產(chǎn)生計(jì)算類型的代碼，然后在程序的運(yùn)行過程中進(jìn)行類型

12、檢查。過程中進(jìn)行類型檢查。表達(dá)式的值通常是動(dòng)態(tài)的，編譯只產(chǎn)生在程序運(yùn)行表達(dá)式的值通常是動(dòng)態(tài)的，編譯只產(chǎn)生在程序運(yùn)行期間計(jì)算表達(dá)式的值的代碼。然而，有些表達(dá)式可期間計(jì)算表達(dá)式的值的代碼。然而，有些表達(dá)式可能是常數(shù)，例如，能是常數(shù)，例如，3.12*5+10，語(yǔ)義分析器可以在編，語(yǔ)義分析器可以在編譯的時(shí)候計(jì)算它們的值。譯的時(shí)候計(jì)算它們的值。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)108.2 屬性與屬性文法屬性與屬性文法u屬性的引入屬性的引入對(duì)于不同的語(yǔ)言或者變量自身的性質(zhì)，變量的存儲(chǔ)分對(duì)于不同的語(yǔ)言或者變量自身的性質(zhì)，變量的存儲(chǔ)分配可以是靜態(tài)的、也可以是動(dòng)態(tài)的。由于屬性的

13、計(jì)算配可以是靜態(tài)的、也可以是動(dòng)態(tài)的。由于屬性的計(jì)算依賴與程序的運(yùn)行環(huán)境，甚至?xí)r目標(biāo)機(jī)的細(xì)節(jié)，所以依賴與程序的運(yùn)行環(huán)境，甚至?xí)r目標(biāo)機(jī)的細(xì)節(jié)，所以編譯通常把屬性的計(jì)算推遲到代碼生成期間。編譯通常把屬性的計(jì)算推遲到代碼生成期間。過程的目標(biāo)碼顯然是靜態(tài)屬性。編譯的代碼產(chǎn)生器全過程的目標(biāo)碼顯然是靜態(tài)屬性。編譯的代碼產(chǎn)生器全權(quán)負(fù)責(zé)這類屬性的計(jì)算。權(quán)負(fù)責(zé)這類屬性的計(jì)算。數(shù)的有效數(shù)字個(gè)數(shù)這個(gè)屬性一般不在編譯期間處理，數(shù)的有效數(shù)字個(gè)數(shù)這個(gè)屬性一般不在編譯期間處理，它隱含在編譯程序構(gòu)造期間對(duì)這些數(shù)值實(shí)現(xiàn)的處理，它隱含在編譯程序構(gòu)造期間對(duì)這些數(shù)值實(shí)現(xiàn)的處理，通常是運(yùn)行環(huán)境的一部分。然而，如果要正確地翻譯通常是運(yùn)行環(huán)

14、境的一部分。然而，如果要正確地翻譯常數(shù)，掃描器也需要知道允許的有效數(shù)字的個(gè)數(shù)。常數(shù)，掃描器也需要知道允許的有效數(shù)字的個(gè)數(shù)。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)118.2 屬性與屬性文法屬性與屬性文法u屬性文法的定義屬性文法的定義定義定義8.1 如果用如果用X表示一個(gè)文法符號(hào)，表示一個(gè)文法符號(hào)，a代表代表X的一的一個(gè)屬性，那么，個(gè)屬性，那么，X.a代表代表X的關(guān)聯(lián)屬性的關(guān)聯(lián)屬性a。定義定義8.2 對(duì)于一組屬性對(duì)于一組屬性a1,a2,.,am和文法和文法G的每個(gè)產(chǎn)的每個(gè)產(chǎn)生式生式X0X1X2.Xn（X0是非終結(jié)符，其它的是非終結(jié)符，其它的Xi是是任意符號(hào)），意味著每

15、個(gè)屬性任意符號(hào)），意味著每個(gè)屬性Xi. aj的值都和產(chǎn)生的值都和產(chǎn)生式中其它屬性有關(guān)系，每個(gè)關(guān)系可以表示成屬性等式中其它屬性有關(guān)系，每個(gè)關(guān)系可以表示成屬性等式或語(yǔ)義規(guī)則的形式：式或語(yǔ)義規(guī)則的形式：Xi. aj i(a1,a2,.,am)定義定義8.3 屬性文法就是對(duì)于一組屬性屬性文法就是對(duì)于一組屬性a1,a2,.,am和文和文法法G的每個(gè)產(chǎn)生式的所有的語(yǔ)義規(guī)則，其中文法的每個(gè)產(chǎn)生式的所有的語(yǔ)義規(guī)則，其中文法G稱為基礎(chǔ)文法。稱為基礎(chǔ)文法。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)128.2 屬性與屬性文法屬性與屬性文法u屬性文法通常寫成下列表格形式：屬性文法通常寫成下列

16、表格形式：語(yǔ)法產(chǎn)生式語(yǔ)法產(chǎn)生式語(yǔ)義規(guī)則語(yǔ)義規(guī)則X 關(guān)聯(lián)的屬性等式關(guān)聯(lián)的屬性等式青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)138.2 屬性與屬性文法屬性與屬性文法數(shù)的最重要的屬性就是它的值，命名為數(shù)的最重要的屬性就是它的值，命名為val。每個(gè)數(shù)字都有一個(gè)值，可以直接從它表。每個(gè)數(shù)字都有一個(gè)值，可以直接從它表示的實(shí)際數(shù)字得到。所以，文法規(guī)則示的實(shí)際數(shù)字得到。所以，文法規(guī)則 digit 0意味著在這個(gè)情況下意味著在這個(gè)情況下digit有有0值，可值，可以表示成屬性等式以表示成屬性等式digit.val := 0，并把它和文法規(guī)則，并把它和文法規(guī)則 digit 0關(guān)聯(lián)在一起。

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

18、標(biāo)表示），這是由于它們具有不同的值。同的值。 考慮數(shù)考慮數(shù)83的最右推導(dǎo)：的最右推導(dǎo)：number number digit digit digit digit3 83在第一步使用的文法規(guī)則在第一步使用的文法規(guī)則number1 number2 digit，其中，其中number2表示數(shù)字表示數(shù)字8，而而digit對(duì)應(yīng)對(duì)應(yīng)3，它們的值分別是，它們的值分別是8和和3。為了得到。為了得到number1的值的值83，必須使用的下列，必須使用的下列計(jì)算：計(jì)算： 838*10 + 3。這對(duì)應(yīng)了屬性等式：。這對(duì)應(yīng)了屬性等式：number1.val := number2 .val 10 + digit.val

19、例例8.1 考慮下列無符號(hào)數(shù)的簡(jiǎn)單語(yǔ)法G8.1number number digit | digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)148.2 屬性與屬性文法屬性與屬性文法表8.2 例8.1的屬性文法文法規(guī)則語(yǔ)義規(guī)則number1 number2 digitnumber1.val := number2 .val 10 + digit.valnumber digitnumber.val := digit.valdigit 0digit.val := 0digit 1digit

20、.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ǔ)法分析樹 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)158.2 屬性與屬性文法屬性與屬性文法u例例8.2 考慮的簡(jiǎn)單算術(shù)表達(dá)式考慮的簡(jiǎn)單算術(shù)表達(dá)式的語(yǔ)法的語(yǔ)法G5.1：E E + T |E - T | TT T

21、 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ù)值，記做主要屬性就是所有非終結(jié)符的數(shù)值，記做val。這些屬性等式描述了表達(dá)式的語(yǔ)法關(guān)系以及要執(zhí)行的算術(shù)運(yùn)算的語(yǔ)義。這些屬性等式描述了表達(dá)式的語(yǔ)法關(guān)系以及要執(zhí)行的算術(shù)運(yùn)算的語(yǔ)義。注

22、意，這個(gè)文法沒有把注意，這個(gè)文法沒有把num當(dāng)作非終結(jié)符，也就沒有當(dāng)作非終結(jié)符，也就沒有num.val在等號(hào)在等號(hào)左邊的屬性等式，所以，使用該屬性文法時(shí)左邊的屬性等式，所以，使用該屬性文法時(shí)num.val的值必須在語(yǔ)義的值必須在語(yǔ)義分析前（通常由詞法分析器）得到。分析前（通常由詞法分析器）得到。 如果想明顯地在文法中計(jì)算如果想明顯地在文法中計(jì)算num的屬性值，可以增加產(chǎn)生式規(guī)則，并的屬性值，可以增加產(chǎn)生式規(guī)則，并對(duì)這個(gè)屬性文法增加如同例子對(duì)這個(gè)屬性文法增加如同例子8.1一樣的屬性等式。一樣的屬性等式。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)168.2 屬性與屬性文

23、法屬性與屬性文法 (52 3) 30的計(jì)算語(yǔ)義的計(jì)算語(yǔ)義表示在如圖表示在如圖8.2的語(yǔ)法的語(yǔ)法分析樹中。分析樹中。 自底向上地遍歷樹就可以自底向上地遍歷樹就可以得到表達(dá)式的值。得到表達(dá)式的值。 E(val =1470) E (val = 523= 49)num(val= 30)T(val = 1)E(val = 52)E(val = 49*30 = 1470)F(val= 30)T(val = 49)() F(val = 3)num(val = 3)F(val = 53)num(val = 52)T(val = 52)青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)178.

24、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)造屬性等式來表達(dá)數(shù)據(jù)類型屬性與聲明類型的關(guān)系。定義的dtype表示數(shù)據(jù)類型屬性。屬性dtype的取值范圍是集合integer, real，對(duì)應(yīng)了符號(hào)int和float。非終結(jié)符type的屬性dtype由其所代表的符號(hào)給定。根據(jù)語(yǔ)法規(guī)則decl type var-list，這個(gè)屬性dtype對(duì)應(yīng)了變量表var-list的dtyp

25、e。變量表中的每個(gè)標(biāo)識(shí)符id都有相同的屬性dtype。注意，非終結(jié)符decl沒有屬性定義。事實(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.type := var-list1.dtypevar-list2.type := var-list1.dtypevar-list idid.type := var-list.dtype

26、青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)188.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è)新的表示底數(shù)的屬性base，用于計(jì)算值屬性val。 文法規(guī)則語(yǔ)義規(guī)則based-num num basecharbase

27、d-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.base := num1.basenum digitnum.val := digit.valdigit 0dig

28、it.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青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)198.2 屬性與屬性文法屬性與屬性文法u這個(gè)屬性文法出現(xiàn)了兩個(gè)新的特性這個(gè)屬性文法出現(xiàn)了兩個(gè)新的特性 這個(gè)文法沒有排除八進(jìn)制數(shù)時(shí)錯(cuò)誤的數(shù)字這個(gè)文法沒有排除八進(jìn)制數(shù)時(shí)錯(cuò)誤的數(shù)字8和和9。例如，按照語(yǔ)。例如

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

30、 if digit.val = error or num2 .val = errorthen errorelse num2 .val num1.base + digit.val表達(dá)了如下的情況：如果表達(dá)了如下的情況：如果digit.val或或num2 .val其中的一個(gè)是其中的一個(gè)是error，那么，那么num1.val也必須是也必須是error；否則，；否則，num1.val的值由公的值由公式式num2 .val num1.base + digit.val給出。給出。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)208.2 屬性與屬性文法屬性與屬性文法u屬性文法的形式化

31、定義屬性文法的形式化定義一個(gè)屬性文法一個(gè)屬性文法AG是一個(gè)三元組是一個(gè)三元組，其中，其中G是一個(gè)上下文無關(guān)文法，稱作基礎(chǔ)文法，當(dāng)同一個(gè)是一個(gè)上下文無關(guān)文法，稱作基礎(chǔ)文法，當(dāng)同一個(gè)符號(hào)在產(chǎn)生式中多次出現(xiàn)時(shí)要用序號(hào)加以區(qū)別；符號(hào)在產(chǎn)生式中多次出現(xiàn)時(shí)要用序號(hào)加以區(qū)別；A是有限的屬性集合，是有限的屬性集合，G中的符號(hào)中的符號(hào)X關(guān)聯(lián)于屬性集關(guān)聯(lián)于屬性集A(X)，X的一個(gè)屬性的一個(gè)屬性a記做記做X.a；R是有限的屬性等式的集合。是有限的屬性等式的集合。對(duì)于一組屬性對(duì)于一組屬性a1,a2,.,am和文法和文法G的每個(gè)產(chǎn)生式的每個(gè)產(chǎn)生式X0X1X2.Xn（X0是非終結(jié)符，其它的是非終結(jié)符，其它的Xi是任意符是

32、任意符號(hào)），屬性等式或語(yǔ)義規(guī)則的形式：號(hào)），屬性等式或語(yǔ)義規(guī)則的形式：Xi. aj i(a1,a2,.,am)。 i一般是表達(dá)式，可以函數(shù)甚至是子一般是表達(dá)式，可以函數(shù)甚至是子程序。程序。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)218.2 屬性與屬性文法屬性與屬性文法u屬性文法的簡(jiǎn)化與擴(kuò)展屬性文法的簡(jiǎn)化與擴(kuò)展可以在屬性等式中使用這些的元語(yǔ)言盡量地可以在屬性等式中使用這些的元語(yǔ)言盡量地接近實(shí)際的程序語(yǔ)言，以便把屬性等式轉(zhuǎn)換接近實(shí)際的程序語(yǔ)言，以便把屬性等式轉(zhuǎn)換成語(yǔ)義分析器中的工作代碼成語(yǔ)義分析器中的工作代碼 。在屬性等式中應(yīng)用在定義好的函數(shù)在屬性等式中應(yīng)用在定義好的函

33、數(shù) 。使用二義性的更加簡(jiǎn)單的基礎(chǔ)文法使用二義性的更加簡(jiǎn)單的基礎(chǔ)文法 。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)228.2 屬性與屬性文法屬性與屬性文法u抽象語(yǔ)法樹抽象語(yǔ)法樹在參考文獻(xiàn)中，通常把抽象語(yǔ)法樹在參考文獻(xiàn)中，通常把抽象語(yǔ)法樹AST（Abstract Syntax Tree）簡(jiǎn)稱為語(yǔ)法樹，而把語(yǔ)法分析樹）簡(jiǎn)稱為語(yǔ)法樹，而把語(yǔ)法分析樹（parsing tree）簡(jiǎn)稱為分析樹。）簡(jiǎn)稱為分析樹。在語(yǔ)法樹中，算符和關(guān)鍵字不是作為葉結(jié)點(diǎn)，而是作在語(yǔ)法樹中，算符和關(guān)鍵字不是作為葉結(jié)點(diǎn)，而是作為內(nèi)部結(jié)點(diǎn)，它們對(duì)應(yīng)分析樹中的這些葉結(jié)點(diǎn)的父結(jié)為內(nèi)部結(jié)點(diǎn)，它們對(duì)應(yīng)分析樹中的這些葉

34、結(jié)點(diǎn)的父結(jié)點(diǎn)?？砂聪旅娴牟襟E從分析樹構(gòu)造出相應(yīng)的語(yǔ)法樹：點(diǎn)?？砂聪旅娴牟襟E從分析樹構(gòu)造出相應(yīng)的語(yǔ)法樹：l去掉與單非產(chǎn)生式相關(guān)的子樹，并上提相關(guān)分支上的終結(jié)符去掉與單非產(chǎn)生式相關(guān)的子樹，并上提相關(guān)分支上的終結(jié)符結(jié)點(diǎn)；結(jié)點(diǎn)；l對(duì)于直接包含運(yùn)算符的多個(gè)子樹，用算符取代其父結(jié)點(diǎn)；對(duì)于直接包含運(yùn)算符的多個(gè)子樹，用算符取代其父結(jié)點(diǎn)；l去掉括號(hào)并上提算符，讓它代替父結(jié)點(diǎn)。去掉括號(hào)并上提算符，讓它代替父結(jié)點(diǎn)。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)238.2 屬性與屬性文法屬性與屬性文法對(duì)于產(chǎn)生式對(duì)于產(chǎn)生式S if E then S1 else S2，可以看成是一個(gè)三元算符，可以

35、看成是一個(gè)三元算符的式子，它的語(yǔ)法樹如下圖的式子，它的語(yǔ)法樹如下圖表達(dá)式表達(dá)式8+1*3的語(yǔ)法樹示意在下圖的語(yǔ)法樹示意在下圖S1if-then-elseS2B3+*81青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)248.2 屬性與屬性文法屬性與屬性文法例例8.5 對(duì)于例對(duì)于例8.2中的算術(shù)表達(dá)式的文法中的算術(shù)表達(dá)式的文法G5.1，可以用表，可以用表8.7的屬性文法定義表達(dá)式的屬性文法定義表達(dá)式的抽象語(yǔ)法樹。的抽象語(yǔ)法樹。其中其中number.lexval指出它是由掃描器構(gòu)造出來的；指出它是由掃描器構(gòu)造出來的；輔助函數(shù)輔助函數(shù)mknode(op, left, right)

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

37、2 .tree, T.tree)E TE.tree := T.treeT1 T2 FT1.tree := mknode(*, T2 .tree, F.tree)T FT.tree := F.treeF (E)F. tree := E. treeF numF. tree := mkleaf(num.lexval)青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)258.2 屬性與屬性文法屬性與屬性文法圖8.6給出了表達(dá)式(523)30根據(jù)表8.6的規(guī)則構(gòu)造的抽象語(yǔ)法樹，同時(shí)也畫出了相應(yīng)的分析樹（虛線）。 num30 num 52num 3E treeE tree E treeE

38、 tree T treenumnumnum * E treeF tree *青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)268.2 屬性與屬性文法屬性與屬性文法利用屬性文法說明屬性的一個(gè)中心問題是：利用屬性文法說明屬性的一個(gè)中心問題是：如何確保一個(gè)特定的屬性文法一致性和完整如何確保一個(gè)特定的屬性文法一致性和完整性，即唯一地定義可給定的屬性？性，即唯一地定義可給定的屬性？對(duì)于這個(gè)問題我們目前無法給出簡(jiǎn)單的答案。這個(gè)問對(duì)于這個(gè)問題我們目前無法給出簡(jiǎn)單的答案。這個(gè)問題類似于確定一個(gè)文法是否是二義的。題類似于確定一個(gè)文法是否是二義的。在實(shí)踐中，我們使用的語(yǔ)法分析算法決定一個(gè)文法

39、的在實(shí)踐中，我們使用的語(yǔ)法分析算法決定一個(gè)文法的適應(yīng)性，類似的情況出現(xiàn)在屬性文法：計(jì)算屬性的算適應(yīng)性，類似的情況出現(xiàn)在屬性文法：計(jì)算屬性的算法決定一個(gè)屬性文法的一致性和完整性。法決定一個(gè)屬性文法的一致性和完整性。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)278.3 屬性的計(jì)算屬性的計(jì)算 u依賴圖和計(jì)算順序名字的訪問依賴圖和計(jì)算順序名字的訪問前面描述的屬性等式前面描述的屬性等式Xi. aj i(a1,a2,.,am)可以看作是把等號(hào)右部的函數(shù)表達(dá)式的值賦給等號(hào)左部的屬可以看作是把等號(hào)右部的函數(shù)表達(dá)式的值賦給等號(hào)左部的屬性性Xi.aj。為了可以賦值，出現(xiàn)在右部函數(shù)中的所

40、有屬性的值。為了可以賦值，出現(xiàn)在右部函數(shù)中的所有屬性的值必須已經(jīng)存在。必須已經(jīng)存在。實(shí)現(xiàn)屬性文法的算法必須為屬性的計(jì)算找到一個(gè)合適順序，實(shí)現(xiàn)屬性文法的算法必須為屬性的計(jì)算找到一個(gè)合適順序，確保在進(jìn)行計(jì)算的時(shí)候每個(gè)需要的屬性值都可以得到。確保在進(jìn)行計(jì)算的時(shí)候每個(gè)需要的屬性值都可以得到。屬性等式本身已經(jīng)蘊(yùn)含了計(jì)算屬性順序的約束，屬性計(jì)算的屬性等式本身已經(jīng)蘊(yùn)含了計(jì)算屬性順序的約束，屬性計(jì)算的首要任務(wù)是利用有向圖把這些隱含的順序約束明確地表示出首要任務(wù)是利用有向圖把這些隱含的順序約束明確地表示出來，這個(gè)有向圖就叫做屬性依賴圖。圖的結(jié)點(diǎn)標(biāo)號(hào)是一個(gè)屬來，這個(gè)有向圖就叫做屬性依賴圖。圖的結(jié)點(diǎn)標(biāo)號(hào)是一個(gè)屬性，

41、如果屬性性，如果屬性a的計(jì)算依賴于屬性的計(jì)算依賴于屬性b，那么，存在從結(jié)點(diǎn)，那么，存在從結(jié)點(diǎn)a到結(jié)到結(jié)點(diǎn)點(diǎn)b的一條有向邊。的一條有向邊。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)288.3 屬性的計(jì)算屬性的計(jì)算語(yǔ)法產(chǎn)生式語(yǔ)法產(chǎn)生式var-list id, var-list有兩條關(guān)聯(lián)的屬性等式：有兩條關(guān)聯(lián)的屬性等式：id.type := var-list1.dtype var-list2.type := var-list1.dtype對(duì)應(yīng)這個(gè)候選產(chǎn)生式的依賴圖是對(duì)應(yīng)這個(gè)候選產(chǎn)生式的依賴圖是語(yǔ)法規(guī)則語(yǔ)法規(guī)則var-list id和和decl type var-list的

42、依賴圖分別的依賴圖分別var-list.dtypevar-list.dtypid.dtypevar-list.dtype id.dtypetype.dtypevar-list.dtype青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)298.3 屬性的計(jì)算屬性的計(jì)算如果依賴圖和分析樹同時(shí)畫出，通常把樹結(jié)如果依賴圖和分析樹同時(shí)畫出，通常把樹結(jié)點(diǎn)標(biāo)記的屬性省去，而把它寫在結(jié)點(diǎn)的旁邊點(diǎn)標(biāo)記的屬性省去，而把它寫在結(jié)點(diǎn)的旁邊比如，串比如，串float x,y分析樹的依賴圖如圖分析樹的依賴圖如圖8.7所示所示decltype dtype var-listid(x), var-listf

43、loatid (y)dtypedtypedtypedtype青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)308.3 屬性的計(jì)算屬性的計(jì)算例例8.7 下面四個(gè)產(chǎn)生式based-num num basecharnum num digitnum digitdigit 9和串813o構(gòu)造依賴圖。(1)為based-num num basechar構(gòu)造依賴圖： valvalbasebasebasecharnumbased-num(2) 為語(yǔ)法產(chǎn)生式num num digit構(gòu)造對(duì)應(yīng)的依賴圖 valvalbasevaldigitnumnumbasebase這個(gè)圖表達(dá)了下面三個(gè)屬性等

44、式的依賴關(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青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)318.3 屬性的計(jì)算屬性的計(jì)算(3) 語(yǔ)法規(guī)則num digit和digit 1的依賴圖分別如下 basebasebasenumdigit val valvaldigit 9(4) 為數(shù)字串813o構(gòu)造的分析樹的依賴圖顯示如

45、下 valvalbasebasebasecharnum based-numvalbasevaldigitnumbasevalbasevaldigitnumbaseo3valdigitbase81青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)328.3 屬性的計(jì)算屬性的計(jì)算定義定義8.5 對(duì)于包含了對(duì)于包含了k結(jié)點(diǎn)的有向圖，結(jié)點(diǎn)的拓?fù)渑判蚪Y(jié)點(diǎn)的有向圖，結(jié)點(diǎn)的拓?fù)渑判騧1, m2,., mk使得任何一條邊使得任何一條邊在這個(gè)序列中都是在這個(gè)序列中都是mi在在mj之前出現(xiàn)之前出現(xiàn)例例8.8 圖圖8.8的依賴圖是一個(gè)有向無環(huán)圖。圖的依賴圖是一個(gè)有向無環(huán)圖。圖8.9只畫出了依賴圖，

46、只畫出了依賴圖，按照結(jié)點(diǎn)編號(hào)的順序得到的結(jié)點(diǎn)排序就是這個(gè)依賴圖的一個(gè)拓按照結(jié)點(diǎn)編號(hào)的順序得到的結(jié)點(diǎn)排序就是這個(gè)依賴圖的一個(gè)拓?fù)渑判?。另外一個(gè)拓?fù)渑判蚴窍铝薪Y(jié)點(diǎn)編號(hào)的序列：撲排序。另外一個(gè)拓?fù)渑判蚴窍铝薪Y(jié)點(diǎn)編號(hào)的序列：12，6，9，1，2，11，3，8，4，5，7，10，13，14valvalbasebase113 14valbaseval1210basevalbaseval97basevalbase23456811青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)338.3 屬性的計(jì)算屬性的計(jì)算使用依賴圖的拓?fù)渑判蛴?jì)算屬性值的一個(gè)關(guān)鍵問題是，如何找使用依賴圖的拓?fù)渑判蛴?jì)算屬性

47、值的一個(gè)關(guān)鍵問題是，如何找到圖的根的屬性值。一個(gè)圖的根是沒有前驅(qū)的結(jié)點(diǎn)。到圖的根的屬性值。一個(gè)圖的根是沒有前驅(qū)的結(jié)點(diǎn)。例如，圖例如，圖8.9中編號(hào)為中編號(hào)為1、6、9和和12的結(jié)點(diǎn)都沒有前驅(qū)，是圖的的結(jié)點(diǎn)都沒有前驅(qū)，是圖的根。這些結(jié)點(diǎn)上的屬性值獨(dú)立于其它任何屬性，必須利用可以根。這些結(jié)點(diǎn)上的屬性值獨(dú)立于其它任何屬性，必須利用可以直接得到的信息求值。直接得到的信息求值。而這些信息通常就是對(duì)應(yīng)分析樹中結(jié)點(diǎn)子女的終結(jié)符串的形式。而這些信息通常就是對(duì)應(yīng)分析樹中結(jié)點(diǎn)子女的終結(jié)符串的形式。例如，圖例如，圖8.9中結(jié)點(diǎn)中結(jié)點(diǎn)6的屬性的屬性val依賴于于符號(hào)依賴于于符號(hào)8，它是屬性，它是屬性val對(duì)對(duì)應(yīng)的結(jié)點(diǎn)

48、應(yīng)的結(jié)點(diǎn)digit的子女（參見圖的子女（參見圖8.8）。所以，結(jié)點(diǎn)）。所以，結(jié)點(diǎn)6的屬性值是的屬性值是8。所有這種根的屬性值都必須在其它任何屬性求值之前計(jì)算出來。所有這種根的屬性值都必須在其它任何屬性求值之前計(jì)算出來。這些計(jì)算通常由掃描器或語(yǔ)法分析器完成。這些計(jì)算通常由掃描器或語(yǔ)法分析器完成。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)348.3 屬性的計(jì)算屬性的計(jì)算u綜合屬性和綜合屬性和S-屬性文法屬性文法定義定義8.6 一個(gè)屬性是綜合屬性，如果它的所有依賴點(diǎn)都是從分一個(gè)屬性是綜合屬性，如果它的所有依賴點(diǎn)都是從分析樹的子女到父母結(jié)點(diǎn)。換句話，屬性析樹的子女到父母結(jié)點(diǎn)

49、。換句話，屬性a是綜合屬性，如果對(duì)于是綜合屬性，如果對(duì)于文法文法AX1X2.Xn，a在左邊的與在左邊的與a關(guān)聯(lián)的屬性等式只有下列形關(guān)聯(lián)的屬性等式只有下列形式：式：A.a ( X1.a1,., X1.ak,., Xn.a1,., Xn.ak)其中其中a1,. ak是所有的屬性。其它屬性叫做繼承屬性。所有屬性是所有的屬性。其它屬性叫做繼承屬性。所有屬性都是綜合屬性的屬性文法稱作都是綜合屬性的屬性文法稱作S-屬性文法屬性文法。按照定義可知，全部非終結(jié)符的屬性都是綜合屬性；同一產(chǎn)生按照定義可知，全部非終結(jié)符的屬性都是綜合屬性；同一產(chǎn)生式中相同符號(hào)的個(gè)綜合屬性之間沒有依賴關(guān)系；如果式中相同符號(hào)的個(gè)綜合屬

50、性之間沒有依賴關(guān)系；如果b使某個(gè)產(chǎn)使某個(gè)產(chǎn)生式中符號(hào)生式中符號(hào)X的繼承屬性，那么屬性的繼承屬性，那么屬性b的值僅僅依賴于該產(chǎn)生式的值僅僅依賴于該產(chǎn)生式右部位于符號(hào)右部位于符號(hào)X的左邊的符號(hào)的屬性。的左邊的符號(hào)的屬性。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)358.3 屬性的計(jì)算屬性的計(jì)算S-屬性文法的屬性計(jì)算可以用自底向上或者屬性文法的屬性計(jì)算可以用自底向上或者后序遍歷（深度優(yōu)先）分析樹后序遍歷（深度優(yōu)先）分析樹/語(yǔ)法樹的方式語(yǔ)法樹的方式一趟完成。這可以表達(dá)成下列的遞歸后序遍一趟完成。這可以表達(dá)成下列的遞歸后序遍歷屬性求值的算法：歷屬性求值的算法：procedure

51、 postEvaluation (T: treenode)beginfor T中的每個(gè)子女結(jié)點(diǎn)中的每個(gè)子女結(jié)點(diǎn)C dopostEvaluation (C); 計(jì)算計(jì)算T的所有綜合屬性；的所有綜合屬性；end postEvaluation;青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)368.3 屬性的計(jì)算屬性的計(jì)算例例8.9 可以用C語(yǔ)言實(shí)現(xiàn)構(gòu)造表達(dá)式的語(yǔ)法樹。首先定義語(yǔ)法數(shù)的數(shù)據(jù)結(jié)構(gòu)typedef enumPlus, Minus, Times OPKind;typedef enumOPKind, COnstKind ExpKind;typedef struct tree

52、nodeExpKind kind;OPKind op;struct treenode *lchild, * rchild;int val; Treenode;typedef Treenode *SyntaxTree;然后，把算法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 lchild

53、val + tree rchildval; case Minus: tree val = tree lchildval tree rchildval; case Times: tree val = tree lchildval * tree rchildval; 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)378.3 屬性的計(jì)算屬性的計(jì)算單純計(jì)算繼承屬性可以通過前序遍歷，或者前序遍歷單純計(jì)算繼承屬性可以通過前序遍歷，或者前序遍歷和中序遍歷分析樹來完成，如下列算法所示：和中序遍歷分析樹來完成，如下列算法所示：procedure preEval (T: treenode)b

54、eginfor T中的每個(gè)子女結(jié)點(diǎn)中的每個(gè)子女結(jié)點(diǎn)C do計(jì)算計(jì)算T的所有繼承屬性；的所有繼承屬性；preEval (C);end for;end preEval;由于繼承屬性可能依賴于子女的屬性，與綜合屬性求由于繼承屬性可能依賴于子女的屬性，與綜合屬性求值不同，在計(jì)算繼承屬性的時(shí)候，子女繼承屬性的計(jì)值不同，在計(jì)算繼承屬性的時(shí)候，子女繼承屬性的計(jì)算順序非常重要。上述代碼中對(duì)于算順序非常重要。上述代碼中對(duì)于T中的每個(gè)子女結(jié)中的每個(gè)子女結(jié)點(diǎn)點(diǎn)C的訪問順序必須滿足這些依賴關(guān)系。的訪問順序必須滿足這些依賴關(guān)系。青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)388.3 屬性的計(jì)算屬

55、性的計(jì)算u例例8.11 考慮表達(dá)式文法的考慮表達(dá)式文法的一個(gè)簡(jiǎn)單版本一個(gè)簡(jiǎn)單版本G8.5：exp exp / exp | num | num. numu設(shè)計(jì)這個(gè)文法的想法是，運(yùn)算符依據(jù)設(shè)計(jì)這個(gè)文法的想法是，運(yùn)算符依據(jù)操作數(shù)是浮點(diǎn)數(shù)還是整數(shù)可以有完全操作數(shù)是浮點(diǎn)數(shù)還是整數(shù)可以有完全不同的解釋。特別是除法運(yùn)算，是否不同的解釋。特別是除法運(yùn)算，是否允許小數(shù)部分，是有區(qū)別的。如果不允許小數(shù)部分，是有區(qū)別的。如果不允許有小數(shù)部分，除法符號(hào)通常記做允許有小數(shù)部分，除法符號(hào)通常記做div，這樣，這樣，5/4就是就是5div4=1。否則，。否則，就是浮點(diǎn)除法，就是浮點(diǎn)除法，5/4 =1.2。u描述這些語(yǔ)義需要

56、三個(gè)屬性：綜合的描述這些語(yǔ)義需要三個(gè)屬性：綜合的布爾屬性布爾屬性isFloat指出一個(gè)表達(dá)式的任指出一個(gè)表達(dá)式的任何部分是否是浮點(diǎn)數(shù)；一個(gè)具有值何部分是否是浮點(diǎn)數(shù)；一個(gè)具有值int和和float的繼承屬性的繼承屬性etype，根據(jù)，根據(jù)isFloat的值指出每個(gè)子表達(dá)式的類型；最后的值指出每個(gè)子表達(dá)式的類型；最后一個(gè)是依據(jù)一個(gè)是依據(jù)etype而計(jì)算每個(gè)子表達(dá)式而計(jì)算每個(gè)子表達(dá)式得到的值。得到的值。 文法規(guī)則語(yǔ)義規(guī)則exp1 exp2 / exp3exp1.isFloat := exp2.isFloat OR exp3.isFloatexp2.etype := exp1.etypeexp3.et

57、ype := 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.val := num. num.val屬性isFloat、etype和val需要兩次遍歷分析樹或語(yǔ)法樹才能計(jì)算出來。第一遍后序遍歷計(jì)算出綜合屬性isF

58、loat的值；第二遍混合的前序遍歷和后序遍歷計(jì)算出繼承屬性etype與綜合屬性val的值青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)398.3 屬性的計(jì)算屬性的計(jì)算uS-屬性文法的自底屬性文法的自底向上計(jì)算向上計(jì)算 在在LR分析方法中，我們通常分析方法中，我們通常使用一個(gè)棧來存放已經(jīng)分析使用一個(gè)棧來存放已經(jīng)分析過的子樹的信息?，F(xiàn)在，增過的子樹的信息。現(xiàn)在，增加一個(gè)屬性值棧，或者在分加一個(gè)屬性值棧，或者在分析棧中增加一個(gè)子域，存放析棧中增加一個(gè)子域，存放屬性值。這個(gè)屬性值棧和分屬性值。這個(gè)屬性值棧和分析棧被同步地操作，每當(dāng)分析棧被同步地操作，每當(dāng)分析棧發(fā)生移進(jìn)或歸約時(shí)，就

59、析棧發(fā)生移進(jìn)或歸約時(shí)，就根據(jù)屬性等式計(jì)算新的屬性根據(jù)屬性等式計(jì)算新的屬性值，并存放在屬性值棧內(nèi)。值，并存放在屬性值棧內(nèi)。圖圖8.10給出了一個(gè)示意圖給出了一個(gè)示意圖 。 狀態(tài) 屬性值 . . Z 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)沒有綜合屬性，那么，數(shù)組val對(duì)應(yīng)的元素就沒

60、有定義。歸約后，top的值減2，代表A的狀態(tài)放在當(dāng)前棧頂statetop（即原先X的位置），根據(jù)相應(yīng)屬性等式計(jì)算得到的綜合屬性A.a的值放在valtop。 青島大學(xué)信息工程學(xué)院青島大學(xué)信息工程學(xué)院編譯原理與技術(shù)編譯原理與技術(shù)408.3 屬性的計(jì)算屬性的計(jì)算例例8.12 考慮下列一個(gè)臺(tái)式計(jì)算器的文法考慮下列一個(gè)臺(tái)式計(jì)算器的文法G8.5及其及其語(yǔ)義規(guī)則：語(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 :=