語(yǔ)法制導(dǎo)翻譯及中間代碼生成

1、2022-5-5莆田學(xué)院許振和1第第5 5章語(yǔ)法制導(dǎo)翻譯和中間代碼生成章語(yǔ)法制導(dǎo)翻譯和中間代碼生成2022-5-5莆田學(xué)院許振和2一、語(yǔ)義處理概述一、語(yǔ)義處理概述二、屬性文法二、屬性文法三、語(yǔ)法制導(dǎo)翻譯概論三、語(yǔ)法制導(dǎo)翻譯概論四、中間代碼的形式四、中間代碼的形式五、聲明語(yǔ)句的翻譯五、聲明語(yǔ)句的翻譯六、賦值語(yǔ)句的翻譯六、賦值語(yǔ)句的翻譯七、布爾表達(dá)式的翻譯七、布爾表達(dá)式的翻譯八、分支語(yǔ)句的翻譯八、分支語(yǔ)句的翻譯主要內(nèi)容主要內(nèi)容2022-5-5莆田學(xué)院許振和3指出：按照編譯程序的邏輯工作過(guò)程，語(yǔ)法分析后，接指出：按照編譯程序的邏輯工作過(guò)程，語(yǔ)法分析后，接下來(lái)就要進(jìn)行下來(lái)就要進(jìn)行語(yǔ)義分析語(yǔ)義分析了，語(yǔ)

2、義分析后，再生成中間了，語(yǔ)義分析后，再生成中間代碼。實(shí)際應(yīng)用中，往往在語(yǔ)法分析的同時(shí)，進(jìn)行語(yǔ)代碼。實(shí)際應(yīng)用中，往往在語(yǔ)法分析的同時(shí)，進(jìn)行語(yǔ)義分析并生成中間代碼，這就是義分析并生成中間代碼，這就是語(yǔ)法制導(dǎo)翻譯。語(yǔ)法制導(dǎo)翻譯。語(yǔ)法制導(dǎo)翻譯過(guò)程中，需要借助于語(yǔ)法制導(dǎo)翻譯過(guò)程中，需要借助于屬性文法屬性文法進(jìn)行語(yǔ)義描進(jìn)行語(yǔ)義描述和語(yǔ)義處理。述和語(yǔ)義處理。一、語(yǔ)義處理概述一、語(yǔ)義處理概述 應(yīng)用最廣的語(yǔ)義分析方法是語(yǔ)法制導(dǎo)翻譯，它的基本思想是將語(yǔ)言結(jié)構(gòu)的語(yǔ)義以屬性(attribute)的形式賦予代表此結(jié)構(gòu)的文法符號(hào)，而屬性的計(jì)算以語(yǔ)義規(guī)則(semantic rules)的形式賦予由文法符號(hào)組成的產(chǎn)生式。在語(yǔ)

3、法分析推導(dǎo)或歸約的每一步驟中，通過(guò)語(yǔ)義規(guī)則實(shí)現(xiàn)對(duì)屬性的計(jì)算，以達(dá)到對(duì)語(yǔ)義的處理。2022-5-5莆田學(xué)院許振和4 雖然語(yǔ)義的形式化工作已經(jīng)有相當(dāng)?shù)倪M(jìn)展，但由于語(yǔ)義雖然語(yǔ)義的形式化工作已經(jīng)有相當(dāng)?shù)倪M(jìn)展，但由于語(yǔ)義的復(fù)雜性，使得的復(fù)雜性，使得語(yǔ)義分析不能像語(yǔ)法分析那樣語(yǔ)義分析不能像語(yǔ)法分析那樣規(guī)范規(guī)范。到目前到目前為止，語(yǔ)義的形式化描述并沒(méi)有語(yǔ)法的形式化描述那樣成熟，為止，語(yǔ)義的形式化描述并沒(méi)有語(yǔ)法的形式化描述那樣成熟，使得使得語(yǔ)義的描述處于一種自然語(yǔ)言的描述或者半形式化描述語(yǔ)義的描述處于一種自然語(yǔ)言的描述或者半形式化描述的狀態(tài)的狀態(tài)。而沒(méi)有基于數(shù)學(xué)抽象的形式化描述，就很難設(shè)計(jì)出。而沒(méi)有基于數(shù)學(xué)抽

4、象的形式化描述，就很難設(shè)計(jì)出基于數(shù)學(xué)模型的統(tǒng)一算法來(lái)實(shí)現(xiàn)語(yǔ)義分析器的自動(dòng)生成。詞基于數(shù)學(xué)模型的統(tǒng)一算法來(lái)實(shí)現(xiàn)語(yǔ)義分析器的自動(dòng)生成。詞/語(yǔ)法分析器生成器語(yǔ)法分析器生成器LEX和和YACC為使用者提供用于描述屬性為使用者提供用于描述屬性的偽變量和語(yǔ)義棧，以支持語(yǔ)法制導(dǎo)翻譯，但是語(yǔ)義規(guī)則的的偽變量和語(yǔ)義棧，以支持語(yǔ)法制導(dǎo)翻譯，但是語(yǔ)義規(guī)則的書(shū)寫(xiě)，仍屬于普通程序設(shè)計(jì)的范疇。書(shū)寫(xiě)，仍屬于普通程序設(shè)計(jì)的范疇。 2022-5-5莆田學(xué)院許振和5源語(yǔ)言程序源語(yǔ)言程序匯編代碼匯編代碼詞法分析詞法分析語(yǔ)義分析語(yǔ)義分析語(yǔ)法分析語(yǔ)法分析代碼生成代碼生成前端處理前端處理后端處理后端處理 語(yǔ)義處理語(yǔ)義處理語(yǔ)義處理語(yǔ)義處理

5、2022-5-5莆田學(xué)院許振和6語(yǔ)義處理語(yǔ)義處理語(yǔ)義處理的環(huán)境：符號(hào)表語(yǔ)義處理的環(huán)境：符號(hào)表為語(yǔ)義分析提供類型、作用域等信息。為語(yǔ)義分析提供類型、作用域等信息。為代碼生成提供類型、作用域、存儲(chǔ)類別、存儲(chǔ)（相對(duì)）為代碼生成提供類型、作用域、存儲(chǔ)類別、存儲(chǔ)（相對(duì)）位置等信息。位置等信息。 語(yǔ)法制導(dǎo)翻譯的基本思想語(yǔ)法制導(dǎo)翻譯的基本思想是，為每一個(gè)產(chǎn)生式配上是，為每一個(gè)產(chǎn)生式配上語(yǔ)義規(guī)則并且在適當(dāng)?shù)臅r(shí)候執(zhí)行這些規(guī)則。即當(dāng)歸約語(yǔ)義規(guī)則并且在適當(dāng)?shù)臅r(shí)候執(zhí)行這些規(guī)則。即當(dāng)歸約(或或推導(dǎo)推導(dǎo))到某產(chǎn)生式時(shí)，除了按照產(chǎn)生式進(jìn)行相應(yīng)的代換之到某產(chǎn)生式時(shí)，除了按照產(chǎn)生式進(jìn)行相應(yīng)的代換之外，還要按照產(chǎn)生式所對(duì)應(yīng)的外，

6、還要按照產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義規(guī)則執(zhí)行相應(yīng)的語(yǔ)義動(dòng)語(yǔ)義規(guī)則執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作作，如計(jì)算、查填符號(hào)表、產(chǎn)生中間代碼、發(fā)布出錯(cuò)信息，如計(jì)算、查填符號(hào)表、產(chǎn)生中間代碼、發(fā)布出錯(cuò)信息等。等。2022-5-5莆田學(xué)院許振和7二、屬性文法二、屬性文法1、編譯中的、編譯中的語(yǔ)義處理語(yǔ)義處理是指兩個(gè)是指兩個(gè)功能功能： 審查每個(gè)語(yǔ)法結(jié)構(gòu)的審查每個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義靜態(tài)語(yǔ)義，即驗(yàn)證語(yǔ)法結(jié)，即驗(yàn)證語(yǔ)法結(jié)構(gòu)合法的程序是否真正有意義（靜態(tài)語(yǔ)義分析構(gòu)合法的程序是否真正有意義（靜態(tài)語(yǔ)義分析/靜靜態(tài)審查）。態(tài)審查）。 如果靜態(tài)語(yǔ)義正確，語(yǔ)義處理的工作是要執(zhí)行如果靜態(tài)語(yǔ)義正確，語(yǔ)義處理的工作是要執(zhí)行真正的翻譯，即真正的翻譯，即生成

7、中間代碼或目標(biāo)代碼生成中間代碼或目標(biāo)代碼。2、有的編譯程序直接生成目標(biāo)代碼，有的編譯程、有的編譯程序直接生成目標(biāo)代碼，有的編譯程序采用中間代碼。序采用中間代碼。2022-5-5莆田學(xué)院許振和8 3、語(yǔ)法制導(dǎo)翻譯是指在語(yǔ)法分析過(guò)程中，、語(yǔ)法制導(dǎo)翻譯是指在語(yǔ)法分析過(guò)程中，完成附加在所使用的產(chǎn)生式上的語(yǔ)義規(guī)則描述的完成附加在所使用的產(chǎn)生式上的語(yǔ)義規(guī)則描述的動(dòng)作。動(dòng)作。 4、屬性屬性，常用以描述事物或人的特征、性質(zhì)，常用以描述事物或人的特征、性質(zhì)、品質(zhì)等，對(duì)編譯程序使用的語(yǔ)法樹(shù)的結(jié)點(diǎn)，可、品質(zhì)等，對(duì)編譯程序使用的語(yǔ)法樹(shù)的結(jié)點(diǎn)，可以用類型、值或存儲(chǔ)位置來(lái)描述它。以用類型、值或存儲(chǔ)位置來(lái)描述它。 5、當(dāng)把

8、每個(gè)文法符號(hào)和一組屬性相關(guān)聯(lián)，、當(dāng)把每個(gè)文法符號(hào)和一組屬性相關(guān)聯(lián)，并把產(chǎn)生式附加以并把產(chǎn)生式附加以語(yǔ)義規(guī)則語(yǔ)義規(guī)則的時(shí)候，就得到的時(shí)候，就得到屬性屬性文法。文法。2022-5-5莆田學(xué)院許振和96 6、一個(gè)、一個(gè)屬性文法屬性文法是一個(gè)三元組是一個(gè)三元組A A（G G，V V，F(xiàn) F），其中），其中G G：一個(gè)上下文無(wú)關(guān)文法，屬性文法的基礎(chǔ)。一個(gè)上下文無(wú)關(guān)文法，屬性文法的基礎(chǔ)。V:V:有窮的屬性集有窮的屬性集每個(gè)屬性與一個(gè)文法符號(hào)相關(guān)聯(lián)每個(gè)屬性與一個(gè)文法符號(hào)相關(guān)聯(lián)這些屬性代表與文法符號(hào)相關(guān)的語(yǔ)義信息這些屬性代表與文法符號(hào)相關(guān)的語(yǔ)義信息 如類型、地址、值、代碼、符號(hào)表內(nèi)容等等如類型、地址、值、代碼

9、、符號(hào)表內(nèi)容等等屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程屬性加工與語(yǔ)法分析同時(shí)進(jìn)行屬性加工與語(yǔ)法分析同時(shí)進(jìn)行 F:F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則( (稱為稱為語(yǔ)語(yǔ)義規(guī)則義規(guī)則) )斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián)斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián), ,只引用該產(chǎn)生式只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。2022-5-5莆田學(xué)院許振和107 7、例如文法、例如文法G G為：為： E E T T1 1+T+T

10、2 2| T| T1 1 or T or T2 2 T T num| true |falsenum| true |false對(duì)輸入串對(duì)輸入串3+43+4的語(yǔ)法樹(shù)如圖的語(yǔ)法樹(shù)如圖8.18.12022-5-5莆田學(xué)院許振和11 屬性文法記號(hào)屬性文法記號(hào)中常使用中常使用Ntt的形式表示與非終結(jié)符的形式表示與非終結(jié)符N N相聯(lián)的屬相聯(lián)的屬性性t t。 文法符號(hào)屬性的抽象表示采用點(diǎn)加標(biāo)識(shí)符文法符號(hào)屬性的抽象表示采用點(diǎn)加標(biāo)識(shí)符(.屬性屬性)的方法。例如，的方法。例如，對(duì)于表達(dá)式對(duì)于表達(dá)式E，可以用，可以用E.val、E.type、E.place、E.code等分別表等分別表示表達(dá)式的示表達(dá)式的值、類型、存

11、儲(chǔ)空間、代碼序列值、類型、存儲(chǔ)空間、代碼序列等屬性。而屬性在程序等屬性。而屬性在程序設(shè)計(jì)中的具體表示，可以根據(jù)實(shí)際情況采用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)或者程設(shè)計(jì)中的具體表示，可以根據(jù)實(shí)際情況采用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)或者程序代碼來(lái)實(shí)現(xiàn)。序代碼來(lái)實(shí)現(xiàn)。 比如可把完成對(duì)上面表達(dá)式的類型檢查的屬性文法寫(xiě)成圖比如可把完成對(duì)上面表達(dá)式的類型檢查的屬性文法寫(xiě)成圖8.28.2的形式：的形式：2022-5-5莆田學(xué)院許振和128 8、屬性文法最早由克努特、屬性文法最早由克努特(D.E.Knuth)(D.E.Knuth)提出，他把屬性分提出，他把屬性分成：成：繼承屬性、綜合屬性繼承屬性、綜合屬性。 屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式屬性文

12、法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A A a a都有一套與之相都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條規(guī)則的形式為關(guān)聯(lián)的語(yǔ)義規(guī)則，每條規(guī)則的形式為b:=f(cb:=f(c1 1,c,c2 2,c,ck k) )。 f f是一個(gè)函數(shù)，是一個(gè)函數(shù)，b b和和c c1 1,c,c2 2,c,ck k是該產(chǎn)生式文法符號(hào)的是該產(chǎn)生式文法符號(hào)的屬性。屬性。（1 1）如果）如果b b是是A A的一個(gè)屬性，的一個(gè)屬性，c c1 1,c,c2 2,c,ck k是產(chǎn)生式右部文法是產(chǎn)生式右部文法符號(hào)的屬性或符號(hào)的屬性或A A的其他屬性，則稱的其他屬性，則稱b b是是A A的的綜合屬性。綜合屬性。（2 2）如果）如果b b是產(chǎn)生式右部

13、某個(gè)文法符號(hào)是產(chǎn)生式右部某個(gè)文法符號(hào)X X的一個(gè)屬性，并且的一個(gè)屬性，并且c c1 1,c,c2 2,c,ck k是是A A或產(chǎn)生式右邊任何文法符號(hào)的屬性，則稱或產(chǎn)生式右邊任何文法符號(hào)的屬性，則稱b b是文法符號(hào)是文法符號(hào)X X的的繼承屬性。繼承屬性。2022-5-5莆田學(xué)院許振和13 (1) (1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法文法開(kāi)始符號(hào)沒(méi)有繼承屬性。開(kāi)始符號(hào)沒(méi)有繼承屬性。 （2 2）終結(jié)符只有綜合屬性終結(jié)符只有綜合屬性，它們由詞法程序提供。例，它們由詞法程序提供。例8.18.1中，中，E E、T T和和F F的的valval屬性是綜合

14、屬性，例屬性是綜合屬性，例8.28.2中的中的L L的的inin是繼承屬性。是繼承屬性。 結(jié)點(diǎn)的綜合屬性值通過(guò)分析樹(shù)中該結(jié)點(diǎn)的結(jié)點(diǎn)的綜合屬性值通過(guò)分析樹(shù)中該結(jié)點(diǎn)的子結(jié)點(diǎn)子結(jié)點(diǎn)的屬的屬性值計(jì)算。繼承屬性值由該結(jié)點(diǎn)的性值計(jì)算。繼承屬性值由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和父結(jié)點(diǎn)兄弟結(jié)點(diǎn)和父結(jié)點(diǎn)的屬的屬性值計(jì)算。性值計(jì)算。綜合屬性：歸約型屬性，用于綜合屬性：歸約型屬性，用于“自下而上自下而上”傳遞信傳遞信息。息。繼承屬性：推導(dǎo)型屬性，用于繼承屬性：推導(dǎo)型屬性，用于“自上而下自上而下”傳遞信傳遞信息。息。2022-5-5莆田學(xué)院許振和14例例5.15.1簡(jiǎn)單算術(shù)表達(dá)式求值的語(yǔ)義描述簡(jiǎn)單算術(shù)表達(dá)式求值的語(yǔ)義描述綜合屬性

15、的例子綜合屬性的例子語(yǔ) 義 規(guī) 則 L EE E1+TETT T1 * FTFF(E)FdigitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn) 生 式非終結(jié)符非終結(jié)符E、T及及F都有一個(gè)綜合屬性都有一個(gè)綜合屬性val,符號(hào)符號(hào)digit僅有僅有一個(gè)綜合屬性一個(gè)綜合屬性，它，它的值由詞法分析器的值由詞法分析器提供。產(chǎn)生式提供。產(chǎn)生式L E語(yǔ)義規(guī)則是一個(gè)語(yǔ)義規(guī)則是一個(gè)過(guò)程過(guò)程,打印打印E的值的值,也可以理解也可以理解L的屬的

16、屬性是空的或虛的。性是空的或虛的。2022-5-5莆田學(xué)院許振和15綜合屬性的自下而上定值綜合屬性的自下而上定值LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹(shù)的帶注釋的分析樹(shù)2022-5-5莆田學(xué)院許振和16例例5.2繼承屬性的例子繼承屬性的例子產(chǎn) 生 式語(yǔ) 義 規(guī) 則D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.

17、in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)L.in 屬性值置為該說(shuō)明語(yǔ)句指定的類型，是繼承屬性繼承屬性。Addtype是一個(gè)過(guò)程，功能是把每個(gè)標(biāo)識(shí)符的類型信息登陸在符號(hào)表的的相關(guān)項(xiàng)中。在表所示的語(yǔ)法制導(dǎo)翻譯中，非終結(jié)符在表所示的語(yǔ)法制導(dǎo)翻譯中，非終結(jié)符D D產(chǎn)生的聲明由產(chǎn)生的聲明由關(guān)鍵字關(guān)鍵字intint或或realreal及標(biāo)識(shí)符表組成，非終結(jié)符及標(biāo)識(shí)符表組成，非終結(jié)符T T有綜合屬有綜合屬性性typetype，它的值由聲明中的關(guān)鍵字決定。，它的值由聲明中的關(guān)鍵字決定。 2022-5-5莆田學(xué)院許振和17繼承屬性的自上而下定值

18、繼承屬性的自上而下定值Real id1,id2,id3DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.，2022-5-5莆田學(xué)院許振和18三、語(yǔ)法制導(dǎo)翻譯概論三、語(yǔ)法制導(dǎo)翻譯概論基于屬性文法的處理過(guò)程（基于屬性文法的處理過(guò)程（語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯）：）：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，然對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語(yǔ)法樹(shù)并在語(yǔ)法樹(shù)的后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語(yǔ)法樹(shù)并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。 根據(jù)屬性表示的抽象程度，語(yǔ)義規(guī)則可以

19、有兩種表示方式。用根據(jù)屬性表示的抽象程度，語(yǔ)義規(guī)則可以有兩種表示方式。用抽抽象的屬性和運(yùn)算符號(hào)象的屬性和運(yùn)算符號(hào)表示的語(yǔ)義規(guī)則稱之為表示的語(yǔ)義規(guī)則稱之為語(yǔ)法制導(dǎo)定義語(yǔ)法制導(dǎo)定義，而用，而用具體具體屬性和運(yùn)算屬性和運(yùn)算表示的語(yǔ)義規(guī)則稱之為表示的語(yǔ)義規(guī)則稱之為翻譯方案翻譯方案，語(yǔ)義規(guī)則也被習(xí)慣地稱，語(yǔ)義規(guī)則也被習(xí)慣地稱為語(yǔ)義動(dòng)作。語(yǔ)法制導(dǎo)定義是為語(yǔ)義動(dòng)作。語(yǔ)法制導(dǎo)定義是抽象抽象的翻譯說(shuō)明，它隱蔽一些實(shí)現(xiàn)的翻譯說(shuō)明，它隱蔽一些實(shí)現(xiàn)細(xì)節(jié)細(xì)節(jié)，翻譯方案指明方案中語(yǔ)義規(guī)則的計(jì)算次序和實(shí)現(xiàn)翻譯方案指明方案中語(yǔ)義規(guī)則的計(jì)算次序和實(shí)現(xiàn)細(xì)節(jié)細(xì)節(jié)。2022-5-5莆田學(xué)院許振和191、計(jì)算語(yǔ)義規(guī)則、計(jì)算語(yǔ)義規(guī)則 所

20、謂依賴圖是一個(gè)有向圖，用于描述分析所謂依賴圖是一個(gè)有向圖，用于描述分析樹(shù)中的屬性和屬性間的相互依賴關(guān)系。樹(shù)中的屬性和屬性間的相互依賴關(guān)系。屬性之間的依賴關(guān)系，屬性之間的依賴關(guān)系，實(shí)質(zhì)上反映了屬性計(jì)算實(shí)質(zhì)上反映了屬性計(jì)算的先后次序的先后次序 如果分析樹(shù)中一結(jié)點(diǎn)的屬性如果分析樹(shù)中一結(jié)點(diǎn)的屬性b依賴于屬性依賴于屬性c，那么這個(gè)結(jié)點(diǎn)的屬性那么這個(gè)結(jié)點(diǎn)的屬性b的語(yǔ)義規(guī)則的計(jì)算必須的語(yǔ)義規(guī)則的計(jì)算必須在定義屬性在定義屬性c的語(yǔ)義規(guī)則的計(jì)算之后。分析樹(shù)的語(yǔ)義規(guī)則的計(jì)算之后。分析樹(shù)結(jié)點(diǎn)的繼承屬性和綜合屬性間的互相依賴關(guān)系結(jié)點(diǎn)的繼承屬性和綜合屬性間的互相依賴關(guān)系可以用名為依賴圖的有向圖來(lái)描繪。可以用名為依賴圖的

21、有向圖來(lái)描繪。 2022-5-5莆田學(xué)院許振和20例例8.2的句子的句子Real id1,id2,id3分析樹(shù)的依賴圖（圖中分析樹(shù)的依賴圖（圖中的結(jié)點(diǎn)用數(shù)字表示）如圖的結(jié)點(diǎn)用數(shù)字表示）如圖8.4：2022-5-5莆田學(xué)院許振和21vL.inL.in屬性屬性依賴依賴T.type (L.in:=T.type)T.type (L.in:=T.type)，L1.inL1.in依賴依賴L.in (L1.in:=L.in) ,L.in (L1.in:=L.in) ,語(yǔ)義規(guī)則語(yǔ)義規(guī)則addtype(id.entry,L.in)addtype(id.entry,L.in)產(chǎn)生結(jié)點(diǎn)產(chǎn)生結(jié)點(diǎn)6,8,106,8,1

22、0為虛擬為虛擬屬性結(jié)點(diǎn)。屬性結(jié)點(diǎn)。v從依賴圖的拓?fù)渑判蛑校梢缘玫剿杏?jì)算語(yǔ)從依賴圖的拓?fù)渑判蛑?，可以得到所有?jì)算語(yǔ)義規(guī)則的順序。用這個(gè)順序來(lái)計(jì)算語(yǔ)義規(guī)則就得義規(guī)則的順序。用這個(gè)順序來(lái)計(jì)算語(yǔ)義規(guī)則就得到輸入符號(hào)串的翻譯。到輸入符號(hào)串的翻譯。v屬性計(jì)算有樹(shù)遍歷的和一遍掃描屬性計(jì)算有樹(shù)遍歷的和一遍掃描的方法。的方法。2022-5-5莆田學(xué)院許振和222 2、S S屬性文法和自下而上翻譯屬性文法和自下而上翻譯 適用于指導(dǎo)自下而上的分析適用于指導(dǎo)自下而上的分析 一個(gè)屬性文法稱為一個(gè)屬性文法稱為S屬性文法屬性文法,當(dāng)且僅當(dāng)滿足當(dāng)且僅當(dāng)滿足如下條件：如下條件：（1）所有非終結(jié)符的屬性是）所有非終結(jié)符的屬性

23、是綜合屬性綜合屬性；（2）同一產(chǎn)生式中相同符號(hào)的各綜合屬性之）同一產(chǎn)生式中相同符號(hào)的各綜合屬性之間無(wú)相互依賴關(guān)系；間無(wú)相互依賴關(guān)系；（3）如果）如果q是某個(gè)產(chǎn)生式中文法符號(hào)是某個(gè)產(chǎn)生式中文法符號(hào)V的繼承的繼承屬性，則屬性屬性，則屬性q的值僅僅依賴于該產(chǎn)生式右部的值僅僅依賴于該產(chǎn)生式右部位于位于V左邊的符號(hào)的屬性。左邊的符號(hào)的屬性。2022-5-5莆田學(xué)院許振和23 綜合屬性可在分析輸入符號(hào)串的同時(shí)自下而上來(lái)計(jì)算綜合屬性可在分析輸入符號(hào)串的同時(shí)自下而上來(lái)計(jì)算 S S屬性文法的翻譯器通常可借助于屬性文法的翻譯器通?？山柚贚RLR分析器分析器實(shí)現(xiàn)。實(shí)現(xiàn)。 在在S S屬性文法的基礎(chǔ)上，屬性文法的基礎(chǔ)

24、上，LRLR分析器可以改造為一個(gè)翻分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。算。 需要對(duì)需要對(duì)LRLR分析器增加分析器增加語(yǔ)義棧語(yǔ)義棧, ,以保存與棧中文法符號(hào)以保存與棧中文法符號(hào)有關(guān)的綜合屬性值。有關(guān)的綜合屬性值。 每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約歸約的產(chǎn)的產(chǎn)生式右邊符號(hào)的屬性值來(lái)計(jì)算生式右邊符號(hào)的屬性值來(lái)計(jì)算2022-5-5莆田學(xué)院許振和24對(duì)例對(duì)例5.1的輸入串的輸入串2+3*5語(yǔ)法樹(shù)如圖語(yǔ)法樹(shù)如圖8.5：2022-5-5莆田學(xué)院許振和25假定有一個(gè)假定有一個(gè)LR語(yǔ)

25、法分析器，現(xiàn)在把它的分析棧擴(kuò)充，語(yǔ)法分析器，現(xiàn)在把它的分析棧擴(kuò)充，使得每個(gè)文法符號(hào)都跟有語(yǔ)義值，即把棧的結(jié)構(gòu)看成使得每個(gè)文法符號(hào)都跟有語(yǔ)義值，即把棧的結(jié)構(gòu)看成圖圖8.6所示：所示：S S屬性的自下而上計(jì)算，帶綜合屬性的分析屬性的自下而上計(jì)算，帶綜合屬性的分析棧：棧：2022-5-5莆田學(xué)院許振和26采用的采用的LR分析表為表分析表為表7.8，不過(guò)要將其中的，不過(guò)要將其中的i改為改為digit，分析和計(jì)值，分析和計(jì)值2+3*5的過(guò)程列在圖的過(guò)程列在圖8.7所示：所示：2022-5-5莆田學(xué)院許振和27u適合于指導(dǎo)自上而下的分析適合于指導(dǎo)自上而下的分析 一個(gè)屬性文法稱為一個(gè)屬性文法稱為L(zhǎng) L屬性文

26、法，如果對(duì)于每個(gè)產(chǎn)生屬性文法，如果對(duì)于每個(gè)產(chǎn)生式式A AX X1 1X X2 2XXn n, ,其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是屬性，或者是X Xj j(1j n)(1j n)的一個(gè)繼承屬性且這個(gè)繼承的一個(gè)繼承屬性且這個(gè)繼承屬性僅依賴于：屬性僅依賴于： （1 1）產(chǎn)生式）產(chǎn)生式X Xj j在左邊符號(hào)在左邊符號(hào)X X1 1,X,X2 2,X,Xn n的屬性的屬性 （2 2）A A的繼承屬性的繼承屬性 S S屬性文法一定是屬性文法一定是L L屬性文法，屬性文法，L L屬性文法允許屬性文法允許一次遍歷就計(jì)算出所有屬性值。一次遍歷就計(jì)算出所有屬性值。

27、3 3、L L屬性文法在自上而下分析屬性文法在自上而下分析中的實(shí)現(xiàn)中的實(shí)現(xiàn)2022-5-5莆田學(xué)院許振和28 L L屬性文法的翻譯器通?？山柚趯傩晕姆ǖ姆g器通?？山柚贚LLL分析器分析器實(shí)現(xiàn)。實(shí)現(xiàn)。 在在L L屬性文法的基礎(chǔ)上，屬性文法的基礎(chǔ)上，LLLL分析器可以改造分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。時(shí)對(duì)屬性進(jìn)行計(jì)算。 需要對(duì)需要對(duì)LLLL分析器增加分析器增加語(yǔ)義棧語(yǔ)義棧, ,以保存與棧中文以保存與棧中文法符號(hào)有關(guān)的繼承屬性值。法符號(hào)有關(guān)的繼承屬性值。 每當(dāng)進(jìn)行推導(dǎo)時(shí)，新的屬性值就由棧中正在推每當(dāng)進(jìn)行推導(dǎo)時(shí)，新

28、的屬性值就由棧中正在推導(dǎo)的產(chǎn)生式左邊符號(hào)的屬性值來(lái)計(jì)算。導(dǎo)的產(chǎn)生式左邊符號(hào)的屬性值來(lái)計(jì)算。2022-5-5莆田學(xué)院許振和29例子例子5.3: 將中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式的屬性文法將中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式的屬性文法,其中其中addop表示表示+或或- EE addop T print(addop,Lexeme) | T Tnum print(num,val) 比如對(duì)串比如對(duì)串2+3-5的分析同時(shí)執(zhí)行語(yǔ)義動(dòng)作打印出的分析同時(shí)執(zhí)行語(yǔ)義動(dòng)作打印出23+5-，語(yǔ)法分析樹(shù)中加虛線聯(lián)結(jié)的語(yǔ)義結(jié)點(diǎn)，形成一個(gè)，語(yǔ)法分析樹(shù)中加虛線聯(lián)結(jié)的語(yǔ)義結(jié)點(diǎn)，形成一個(gè)可說(shuō)明語(yǔ)義動(dòng)作的樹(shù)，如圖可說(shuō)明語(yǔ)義動(dòng)作的樹(shù)

29、，如圖8.8：2022-5-5莆田學(xué)院許振和302022-5-5莆田學(xué)院許振和31 上面是一個(gè)含左遞歸規(guī)則的文法，如采用上面是一個(gè)含左遞歸規(guī)則的文法，如采用LL（1）分析必須改寫(xiě)文法如下：）分析必須改寫(xiě)文法如下： E TR R addop TR1 T num這時(shí)這時(shí)2+3-5的語(yǔ)法樹(shù)如圖的語(yǔ)法樹(shù)如圖8.9：2022-5-5莆田學(xué)院許振和32將后綴式將后綴式23+5-輸出的動(dòng)作在語(yǔ)法樹(shù)中應(yīng)輸出的動(dòng)作在語(yǔ)法樹(shù)中應(yīng)出現(xiàn)的位置如圖出現(xiàn)的位置如圖8.10所示：所示：2022-5-5莆田學(xué)院許振和33例例5.4（中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式）：（中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式）： E TR R ad

30、dop Tprint(addop,Lexeme)R1 T num print(num.val) 把把語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作嵌在右部文法符號(hào)嵌在右部文法符號(hào)T和和R之間，這種語(yǔ)義處理之間，這種語(yǔ)義處理的描述形式稱為的描述形式稱為翻譯模式（翻譯模式（也稱翻譯方案）也稱翻譯方案） 翻譯方案是適合語(yǔ)法制導(dǎo)翻譯的另一種描述形式。翻譯方案是適合語(yǔ)法制導(dǎo)翻譯的另一種描述形式。 翻譯翻譯模式給出了使用語(yǔ)義規(guī)則進(jìn)行模式給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次序計(jì)算的次序，可把某些實(shí)現(xiàn)，可把某些實(shí)現(xiàn)細(xì)節(jié)細(xì)節(jié)表示出來(lái)。表示出來(lái)。翻譯方案和語(yǔ)法制導(dǎo)定義不同的是它的語(yǔ)義翻譯方案和語(yǔ)法制導(dǎo)定義不同的是它的語(yǔ)義動(dòng)作（而不是語(yǔ)義規(guī)則）放在括

31、號(hào)動(dòng)作（而不是語(yǔ)義規(guī)則）放在括號(hào)“ ” ”內(nèi)，并且可以插在產(chǎn)生式右部的任何地方。內(nèi)，并且可以插在產(chǎn)生式右部的任何地方。2022-5-5莆田學(xué)院許振和34一般轉(zhuǎn)換左遞歸翻譯模式的方法簡(jiǎn)述如下：一般轉(zhuǎn)換左遞歸翻譯模式的方法簡(jiǎn)述如下： 假設(shè)翻譯模式為：假設(shè)翻譯模式為： A A1YA.a:=g(A1.a,Y.y) A X A.a:=f(X.x)每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用相應(yīng)的小寫(xiě)字母每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用相應(yīng)的小寫(xiě)字母表示表示，g和和f是任意函數(shù)。消除左遞歸，文法轉(zhuǎn)換成：是任意函數(shù)。消除左遞歸，文法轉(zhuǎn)換成： A XR R YR刪除翻譯方案的左遞歸方法刪除翻譯方案的左遞歸方法2022-5

32、-5莆田學(xué)院許振和35再考慮語(yǔ)義動(dòng)作，則翻譯模式為，其中使再考慮語(yǔ)義動(dòng)作，則翻譯模式為，其中使用了用了R的的繼承屬性繼承屬性i和綜合屬性和綜合屬性s: A XR.i:=f(X.x) R A.a:=R.s R Y R1.i:=g(R.i,Y.y) R1 R.s:=R1.s R R.s:=R.i下面例子幫助理解：下面例子幫助理解：2022-5-5莆田學(xué)院許振和36 例例5-55-5下面將圖下面將圖5-135-13的翻譯方案變換成圖的翻譯方案變換成圖5-145-14的翻譯方案。新的翻譯方案為表達(dá)式的翻譯方案。新的翻譯方案為表達(dá)式9-5+29-5+2產(chǎn)生圖產(chǎn)生圖5-155-15的注釋分析樹(shù)，圖的注釋分

33、析樹(shù)，圖5-155-15中的箭頭暗示了計(jì)算中的箭頭暗示了計(jì)算表達(dá)式值的一種方法。表達(dá)式值的一種方法。2022-5-5莆田學(xué)院許振和37 E E TR TR R R addopaddop TR1 TR1 T T numnum2022-5-5莆田學(xué)院許振和38實(shí)現(xiàn)自下而上計(jì)算繼承屬性方法：實(shí)現(xiàn)自下而上計(jì)算繼承屬性方法：從翻譯模式中從翻譯模式中去掉嵌入去掉嵌入在產(chǎn)生式中間的在產(chǎn)生式中間的動(dòng)作動(dòng)作： 引入新的非終結(jié)符引入新的非終結(jié)符N N和產(chǎn)生式和產(chǎn)生式N N ，把嵌入在生產(chǎn)式中，把嵌入在生產(chǎn)式中間的動(dòng)作用非終結(jié)符間的動(dòng)作用非終結(jié)符N N代替，并把這個(gè)動(dòng)作放在產(chǎn)生式后面代替，并把這個(gè)動(dòng)作放在產(chǎn)生式后面

34、例如下面的翻譯模式：例如下面的翻譯模式：E E T RT RR R +Tprint(+)R+Tprint(+)R1 1R R -T -T print(-)Rprint(-)R1 1R R T T numprint(num,val)numprint(num,val)4、L屬性文法在自下而上分析中的實(shí)現(xiàn)屬性文法在自下而上分析中的實(shí)現(xiàn)（1 1） 刪除翻譯方案中嵌入的動(dòng)作刪除翻譯方案中嵌入的動(dòng)作2022-5-5莆田學(xué)院許振和39引入引入M和和N，變換后的翻譯模式如下，原嵌入在產(chǎn)生，變換后的翻譯模式如下，原嵌入在產(chǎn)生式中間的動(dòng)作都在產(chǎn)生式后面了式中間的動(dòng)作都在產(chǎn)生式后面了 E T R R +TMR1 R

35、 -T NR1 R T numprint(num.val) M print(+) N print(-)2022-5-5莆田學(xué)院許振和40（2) 2) 分析棧上的繼承屬性分析棧上的繼承屬性 例例5-6 5-6 如圖如圖5-195-19所示，使用繼承屬性，標(biāo)識(shí)符的類型所示，使用繼承屬性，標(biāo)識(shí)符的類型屬性可通過(guò)復(fù)制規(guī)則來(lái)傳遞。見(jiàn)教材屬性可通過(guò)復(fù)制規(guī)則來(lái)傳遞。見(jiàn)教材P167P1672022-5-5莆田學(xué)院許振和41四、中間代碼的形式四、中間代碼的形式1、逆波蘭記號(hào)（也稱后綴式）、逆波蘭記號(hào)（也稱后綴式） 這種表示法將這種表示法將運(yùn)算對(duì)象寫(xiě)在前面，把運(yùn)算符號(hào)寫(xiě)在后面運(yùn)算對(duì)象寫(xiě)在前面，把運(yùn)算符號(hào)寫(xiě)在后面逆

36、波蘭表示的例子逆波蘭表示的例子A+b A+b ab+ab+A+bA+b* *c c abcabc* *+ +(a+b)(a+b)* *c c ab+cab+c* *a+ba+b* *c/(d+e) c/(d+e) abcabc* *de+/+de+/+A + B A + B * * ( C - D ) + E / ( C - D ) N ( C - D ) + E / ( C - D ) NA B C D - A B C D - * * + E C D N / + + E C D N / +后綴表示是語(yǔ)法樹(shù)的線性化表示，下圖（后綴表示是語(yǔ)法樹(shù)的線性化表示，下圖（a a）中語(yǔ)）中語(yǔ)法樹(shù)的后綴表示

37、為：法樹(shù)的后綴表示為： abc uminus abc uminus * * b c uminus b c uminus * * + := + :=2022-5-5莆田學(xué)院許振和42例把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴波蘭表示： EE+T E T T TF T F F (E) F a E=ET+ E=T T=TF T=F F=E F=a 產(chǎn)生式 翻譯規(guī)則翻譯規(guī)則2022-5-5莆田學(xué)院許振和43 確定輸入確定輸入a+aa+a a a的輸出：的輸出： (E,E)(E,E)(E+T,ET+)(E+T,ET+)(T+T,TT+)(T+T,TT+) (F+T,FT+)(F+T,FT+)(a+T,aT

38、+)(a+T,aT+) (a+T(a+T F,aTFF,aTF +)+) (a+F(a+F F,aFFF,aFF +)+) (a+a(a+a F,aaFF,aaF +) +) (a+a(a+a a,aaaa,aaa +)+)2022-5-5莆田學(xué)院許振和442 2、四元式、四元式 四元式的組成：算符四元式的組成：算符opop，第一和第二運(yùn)算對(duì)象，第一和第二運(yùn)算對(duì)象ARG1ARG1和和ARG2ARG2及及運(yùn)算結(jié)果運(yùn)算結(jié)果RESULTRESULT例如：例如：a:=ba:=b* *c+bc+b* *d d (1) ( (1) (* *, b,c,t1), b,c,t1) (2) ( (2) (* *

39、，b,d,t2)b,d,t2) (3) (+ (3) (+，t1,t2,t3)t1,t2,t3) (4) (:= (4) (:=， t3,t3,a),a)為了直觀，也把四元式的形式寫(xiě)成簡(jiǎn)單賦值形式（三地址碼）：為了直觀，也把四元式的形式寫(xiě)成簡(jiǎn)單賦值形式（三地址碼）： (1) t1:=b(1) t1:=b* *c (2) t2:=bc (2) t2:=b* *d d (3) t3:=t1+t2 (4) a:=t3 (3) t3:=t1+t2 (4) a:=t3表示空表示空看作看作a:=t3a:=t32022-5-5莆田學(xué)院許振和45四元式的語(yǔ)法制導(dǎo)翻譯四元式的語(yǔ)法制導(dǎo)翻譯將簡(jiǎn)單賦值句的求值翻譯成

40、四元式的語(yǔ)法制導(dǎo)翻譯如下所示：將簡(jiǎn)單賦值句的求值翻譯成四元式的語(yǔ)法制導(dǎo)翻譯如下所示：(1) A id := E A.code := newtemp; emit(:=，entry()，E.code, A.code) (2) E E1 + E2 E.code := newtemp; emit( +， E1.code，E2.code, E.code) (3) E E1 * E2 E.code := newtemp; emit( *， E1.code，E2.code, E.code) (4) E ( E1 ) E.code := E1.code (5) E E1 E.code := ne

41、wtemp; emit( ，E1.code， , E.code) (6) E id E.code := entry() 屬性屬性.code：表示存放運(yùn)算結(jié)果的變量；：表示存放運(yùn)算結(jié)果的變量；函數(shù)函數(shù)newtemp：返回一個(gè)新的臨時(shí)變量，如：返回一個(gè)新的臨時(shí)變量，如T1，T2，等；等；過(guò)程過(guò)程emit( op，arg1，arg2, result)：生成一個(gè)四元式。若運(yùn)算是一元的，如：生成一個(gè)四元式。若運(yùn)算是一元的，如EE1，則則arg2可以為空?？梢詾榭?。2022-5-5莆田學(xué)院許振和46四元式表示的例子四元式表示的例子A + B A + B * * ( C - D ) + E /

42、 ( C - D ) N ( C - D ) + E / ( C - D ) N（1 1） ( - ( - ，C C，D D，T1)T1)（2 2） ( ( * * ，B B，T1T1，2)2)（3 3） ( + ( + ，A A，T2T2，T3)T3)（4 4） ( - ( - ，C C，D D，T4)T4)（5 5） ( ( ，T4T4，N N，T5)T5)（6 6） ( /( /，E E，T5T5，T6)T6)（7 7） ( +( +，T3T3，T6T6，T7)T7)2022-5-5莆田學(xué)院許振和473 3、三元式表示、三元式表示 每個(gè)三元式的組成：算符每個(gè)三元式的組成：算符opop，第

43、，第1 1運(yùn)算對(duì)象運(yùn)算對(duì)象ARG1ARG1，第，第2 2運(yùn)算對(duì)象運(yùn)算對(duì)象ARG2ARG2 例如：例如：a:=ba:=b* *c+bc+b* *d d (1)(1) ( (* *, b,c), b,c) (2)(2) ( (* * ,b,d) ,b,d) (3)(3) (+ ,(1),(2) (+ ,(1),(2) (4)(4) (:= ,(3),a) (:= ,(3),a) 和四元式的比較：和四元式的比較：無(wú)須臨時(shí)變量；無(wú)須臨時(shí)變量；占用存儲(chǔ)空間少；占用存儲(chǔ)空間少；相互引用太多，使得難以進(jìn)行代碼優(yōu)化。相互引用太多，使得難以進(jìn)行代碼優(yōu)化。2022-5-5莆田學(xué)院許振和48三元式表示的例子三元式表

44、示的例子A + B A + B * * ( C - D ) + E / ( C - D ) N ( C - D ) + E / ( C - D ) N(1) ( -(1) ( -，C C，D)D)(2) ( (2) ( * *，B B，(1)(1)(3) ( +(3) ( +，A A，(2)(2)(4) ( -(4) ( -，C C，D)D)(5) ( (5) ( ，(4)(4)，N)N)(6) ( /(6) ( /，E E，(5)(5)(7) ( +(7) ( +，(3)(3)，(6)(6)2022-5-5莆田學(xué)院許振和49簡(jiǎn)單賦值句的求值翻譯成三元式的語(yǔ)法制導(dǎo)翻譯如下所示簡(jiǎn)單賦值句的求值翻

45、譯成三元式的語(yǔ)法制導(dǎo)翻譯如下所示：(1) Aid := E A.code := trip(:=(1) Aid := E A.code := trip(:=，entry()entry()，E.code) E.code) (2) EE1+E2 E.code := trip( +(2) EE1+E2 E.code := trip( +， E1.codeE1.code，E2.code ) E2.code ) (3) EE1(3) EE1* *E2 E.code := trip( E2 E.code := trip( * *， E1.codeE1.code，E2.code )

46、 E2.code ) (4) E( E1 ) E.code := E1.code (4) E( E1 ) E.code := E1.code (5) EE1 E.code := trip( (5) EE1 E.code := trip( ，E1.codeE1.code， ) ) (6) Eid E.code := entry() (6) Eid E.code := entry() 2022-5-5莆田學(xué)院許振和504 4、樹(shù)形表示、樹(shù)形表示( (圖表示法圖表示法) )樹(shù)形表示的定義：樹(shù)形表示的定義： 表達(dá)式的樹(shù)形表示很容易實(shí)現(xiàn)：簡(jiǎn)單變量或常數(shù)的表達(dá)式的樹(shù)形表示很容易

47、實(shí)現(xiàn)：簡(jiǎn)單變量或常數(shù)的樹(shù)就是該變量或常數(shù)自身，如果表達(dá)式樹(shù)就是該變量或常數(shù)自身，如果表達(dá)式e e1 1和和e e2 2的樹(shù)分別的樹(shù)分別為為T T1 1和和T T2 2，那么，那么e e1 1+e+e2 2,e,e1 1* *e e2 2,-e,-e1 1的樹(shù)分別為：的樹(shù)分別為：2022-5-5莆田學(xué)院許振和51 采用樹(shù)形表示作為一種中間代碼形式，有助于代碼采用樹(shù)形表示作為一種中間代碼形式，有助于代碼的產(chǎn)生和優(yōu)化。的產(chǎn)生和優(yōu)化。 樹(shù)形表示是三元式表示的翻版，上述三元式可表示樹(shù)形表示是三元式表示的翻版，上述三元式可表示成右邊的樹(shù)表示：成右邊的樹(shù)表示：2022-5-5莆田學(xué)院許振和52 三地址代碼一

48、般形式為如下的語(yǔ)句序列：三地址代碼一般形式為如下的語(yǔ)句序列： x := y op zx := y op z 其中其中x x、y y和和z z是名字、常數(shù)或編譯器產(chǎn)生的臨時(shí)變量，是名字、常數(shù)或編譯器產(chǎn)生的臨時(shí)變量，opop代表運(yùn)算符。代表運(yùn)算符。5 5、三地址碼、三地址碼P174-175P174-175 例例 如圖如圖5-265-26所示的語(yǔ)法樹(shù)和所示的語(yǔ)法樹(shù)和dagdag由如圖由如圖5-275-27所示的三地址代所示的三地址代碼序列表示。碼序列表示。 2022-5-5莆田學(xué)院許振和535.1 5.1 三地址語(yǔ)句的類型三地址語(yǔ)句的類型P175P175 三地址語(yǔ)句類似于匯編代碼。語(yǔ)句可以有符號(hào)標(biāo)號(hào)

49、，三地址語(yǔ)句類似于匯編代碼。語(yǔ)句可以有符號(hào)標(biāo)號(hào)，而且可以有控制流語(yǔ)句。符號(hào)標(biāo)號(hào)代表中間代碼數(shù)組中而且可以有控制流語(yǔ)句。符號(hào)標(biāo)號(hào)代表中間代碼數(shù)組中三地址語(yǔ)句的下標(biāo)。三地址語(yǔ)句的下標(biāo)。 常用的三地址語(yǔ)句：常用的三地址語(yǔ)句： （1 1）形如）形如x :x :y op zy op z的賦值語(yǔ)句，其中的賦值語(yǔ)句，其中opop是二元算術(shù)運(yùn)算是二元算術(shù)運(yùn)算或邏輯運(yùn)算?；蜻壿嬤\(yùn)算。（2 2）形如）形如x :x :op yop y的賦值語(yǔ)句，其中的賦值語(yǔ)句，其中opop是一元運(yùn)算。是一元運(yùn)算。（3 3）形如）形如x := yx := y的復(fù)寫(xiě)語(yǔ)句。的復(fù)寫(xiě)語(yǔ)句。（4 4）無(wú)條件轉(zhuǎn)移）無(wú)條件轉(zhuǎn)移goto Lgoto

50、 L。（5 5）形如：）形如：if x relop y goto Lif x relop y goto L的條件轉(zhuǎn)移。的條件轉(zhuǎn)移。2022-5-5莆田學(xué)院許振和54（6 6）param xparam x和和“call pcall p，n”n”用于過(guò)程調(diào)用，其中用于過(guò)程調(diào)用，其中n n表表示實(shí)參個(gè)數(shù)，示實(shí)參個(gè)數(shù)，return yreturn y用于過(guò)程返回，用于過(guò)程返回，y y代表返回值，它代表返回值，它也可以不出現(xiàn)，它們的典型使用是：也可以不出現(xiàn)，它們的典型使用是： param x1param x1 param x2 param x2 param xn param xn call p call

51、 p，n n 這些語(yǔ)句是作為過(guò)程這些語(yǔ)句是作為過(guò)程p(x1,x2,xn)p(x1,x2,xn)調(diào)用的一部分。調(diào)用的一部分。（7 7）形如）形如x := yix := yi和和xi := yxi := y的索引賦值。的索引賦值。（8 8）形如）形如x := &yx := &y、x := x := * *y y和和* *x := yx := y的地址和指針賦的地址和指針賦值。值。 2022-5-5莆田學(xué)院許振和555.2 5.2 語(yǔ)法制導(dǎo)翻譯生成三地址碼語(yǔ)法制導(dǎo)翻譯生成三地址碼P176P176 表表5-125-12中的中的S S屬性定義生成賦值語(yǔ)句的三地址碼。綜合屬性屬性定義生成賦

52、值語(yǔ)句的三地址碼。綜合屬性S.codeS.code代表賦值代表賦值S S的三地址碼。的三地址碼。非終結(jié)符非終結(jié)符E E具具有兩個(gè)屬性：有兩個(gè)屬性：表中符號(hào)表中符號(hào)gen(x;=y+z)表示三地址語(yǔ)句表示三地址語(yǔ)句x:=y+z2022-5-5莆田學(xué)院許振和565.3 5.3 三地址語(yǔ)句與四元式三地址語(yǔ)句與四元式P176-177P176-177 三地址語(yǔ)句的表示形式分別有四元式、三元式和間三地址語(yǔ)句的表示形式分別有四元式、三元式和間接三元式。接三元式。 例例 表表5-135-13中的四元式是賦值語(yǔ)句中的四元式是賦值語(yǔ)句a := ba := b* *-c+b-c+b* *-c-c的四元式，它們從圖的

53、四元式，它們從圖5-265-26（a a）的三地址代碼得到。）的三地址代碼得到。 2022-5-5莆田學(xué)院許振和57 編譯程序把說(shuō)明語(yǔ)句中定義的名字和性質(zhì)登記在符編譯程序把說(shuō)明語(yǔ)句中定義的名字和性質(zhì)登記在符號(hào)表中，用以檢查名字的引用和說(shuō)明是否一致。號(hào)表中，用以檢查名字的引用和說(shuō)明是否一致。 過(guò)程說(shuō)明和動(dòng)態(tài)數(shù)組的說(shuō)明有相應(yīng)的代碼過(guò)程說(shuō)明和動(dòng)態(tài)數(shù)組的說(shuō)明有相應(yīng)的代碼1 1、簡(jiǎn)單說(shuō)明語(yǔ)句的翻譯、簡(jiǎn)單說(shuō)明語(yǔ)句的翻譯 程序設(shè)計(jì)語(yǔ)言中最簡(jiǎn)單的說(shuō)明語(yǔ)句的語(yǔ)法描述為：程序設(shè)計(jì)語(yǔ)言中最簡(jiǎn)單的說(shuō)明語(yǔ)句的語(yǔ)法描述為： DDintegerinteger | |realreal ,id | id,id | id 即使用

54、關(guān)鍵字即使用關(guān)鍵字integerinteger和和realreal定義一串名字的性質(zhì)定義一串名字的性質(zhì) 對(duì)這種說(shuō)明語(yǔ)句的翻譯是指在符號(hào)表中登錄該名和性對(duì)這種說(shuō)明語(yǔ)句的翻譯是指在符號(hào)表中登錄該名和性質(zhì)質(zhì), ,把上述文法改寫(xiě)成：把上述文法改寫(xiě)成： D D D1,id|integer id|real idD1,id|integer id|real id五、聲明語(yǔ)句的翻譯五、聲明語(yǔ)句的翻譯2022-5-5莆田學(xué)院許振和58 給非終結(jié)符給非終結(jié)符D D一個(gè)語(yǔ)義變量一個(gè)語(yǔ)義變量D.attD.att，用以記錄說(shuō)明語(yǔ)，用以記錄說(shuō)明語(yǔ)句所引入的名字的性質(zhì)（句所引入的名字的性質(zhì)（intint還是還是realrea

55、l），使用過(guò)程），使用過(guò)程enter(id,A)enter(id,A)把名字把名字idid和性質(zhì)和性質(zhì)A A登錄在名表中。登錄在名表中。（1 1）Dinteger id enter(id,int); Dinteger id enter(id,int); D.att:=int D.att:=int（2 2）Dreal id enter(id,real); Dreal id enter(id,real); D.att:=real D.att:=real（3 3）D D D D1 1, id enter(id,D, id enter(id,D1 1.att);.att); D.att:=D D.at

56、t:=D1 1.att.att2022-5-5莆田學(xué)院許振和592 2、過(guò)程中的聲明語(yǔ)句、過(guò)程中的聲明語(yǔ)句 在在FORTRANFORTRAN、PascalPascal、C C、C#C#和和JavaJava等語(yǔ)言中，語(yǔ)法等語(yǔ)言中，語(yǔ)法允許一個(gè)允許一個(gè)“過(guò)程過(guò)程”或程序塊把所有的局部聲明作為一組集或程序塊把所有的局部聲明作為一組集中在一起進(jìn)行處理。例如，對(duì)于一個(gè)中在一起進(jìn)行處理。例如，對(duì)于一個(gè)C/C+C/C+的聲明序列：的聲明序列： int offsetint offset； double sumdouble sum； char tokenchar token； 如果該聲明在內(nèi)存中得到的首地址為如

57、果該聲明在內(nèi)存中得到的首地址為10001000，那么局部，那么局部名的地址計(jì)算如下：名的地址計(jì)算如下： offsetoffset的地址是的地址是1000;1000; sum sum的地址為的地址為1000+offset1000+offset的字節(jié)數(shù)的字節(jié)數(shù)=1000+4=1004;=1000+4=1004; token token的地址是的地址是1004+sum1004+sum的字節(jié)數(shù)的字節(jié)數(shù)=1004+8=1012;=1004+8=1012;2022-5-5莆田學(xué)院許振和60 在如圖在如圖5-295-29所示的翻譯方案中，非終結(jié)符所示的翻譯方案中，非終結(jié)符P P產(chǎn)生形如產(chǎn)生形如idid：T

58、T的聲明序列，用全局變量的聲明序列，用全局變量offsetoffset來(lái)記住下一個(gè)可用來(lái)記住下一個(gè)可用的相對(duì)地址。的相對(duì)地址。 每看見(jiàn)一個(gè)新名字，則把名字連同每看見(jiàn)一個(gè)新名字，則把名字連同offsetoffset的當(dāng)前值登的當(dāng)前值登入符號(hào)表，然后入符號(hào)表，然后offsetoffset增加增加. . 一般，一般，offsetoffset增加由該增加由該名字類型決定名字類型決定的量，稱為數(shù)據(jù)的量，稱為數(shù)據(jù)對(duì)象的寬度，用屬性對(duì)象的寬度，用屬性widthwidth表示表示. .2022-5-5莆田學(xué)院許振和61賦值語(yǔ)句的執(zhí)行有以下幾個(gè)步驟：賦值語(yǔ)句的執(zhí)行有以下幾個(gè)步驟：（1 1）計(jì)算右部表達(dá)式）計(jì)算右

59、部表達(dá)式E E的值；的值；（2 2）必要時(shí)對(duì)）必要時(shí)對(duì)E E的值進(jìn)行類型轉(zhuǎn)換，強(qiáng)制到的值進(jìn)行類型轉(zhuǎn)換，強(qiáng)制到V V的的類型；類型；（3 3）計(jì)算變量）計(jì)算變量V V的地址；的地址；（4 4）把）把E E的值送入的值送入V V的地址。的地址。六、賦值語(yǔ)句的翻譯六、賦值語(yǔ)句的翻譯一般語(yǔ)法定義是：一般語(yǔ)法定義是： V := E ;V := E ;2022-5-5莆田學(xué)院許振和62產(chǎn)生式產(chǎn)生式語(yǔ)義規(guī)則語(yǔ)義規(guī)則E E1+TE.val:=E1.val+T.val； E.type:=E1.typeETE.val:=T.val； E.type:=T.typeT T1 * FT.val:=T1.val F.va

60、l； T.type:=T1.typeTFT.val:=F.val； T.type:=F.typeF(E)F.val:=E.val； F.type:=E.typeFdigitF.val:=digit.lexval； F.type:= digit.lexval1、簡(jiǎn)單算術(shù)表達(dá)式的屬性文法、簡(jiǎn)單算術(shù)表達(dá)式的屬性文法(復(fù)習(xí)復(fù)習(xí))2022-5-5莆田學(xué)院許振和63 首先對(duì)首先對(duì)id表示的單詞定義屬性表示的單詞定義屬性，用做語(yǔ)義，用做語(yǔ)義變量，用變量，用Lookup()語(yǔ)義函數(shù)審查語(yǔ)義函數(shù)審查是否出現(xiàn)是否出現(xiàn)符號(hào)表中，如在，則返回一指向該登錄項(xiàng)的指針，否則符號(hào)表中，如在，則返回一