Ch屬性文法和語法制導(dǎo)翻譯

1、第第4 4章章 語義語義分析和中間代分析和中間代碼生成碼生成本章在編譯程序中的地位本章在編譯程序中的地位表格管理詞法分析器語法分析器語義分析與中間代碼產(chǎn)生優(yōu)化器目標代碼生成器源程序單詞符號語法單位中間代碼中間代碼目標代碼出錯處理3教學(xué)內(nèi)容教學(xué)內(nèi)容n4.1 4.1 概述概述n4.2 4.2 屬性文法屬性文法 重點重點n4.34.3 幾種常用的中間語言幾種常用的中間語言 重點重點n4.44.4 表達式及賦值語句的翻譯表達式及賦值語句的翻譯 重點難點重點難點n4.54.5 控制語句的翻譯控制語句的翻譯 重點難點重點難點n4.64.6 數(shù)組元素的翻譯數(shù)組元素的翻譯 重點難點重點難點n4.7 4.7 過

2、程或函數(shù)調(diào)用語句的翻譯過程或函數(shù)調(diào)用語句的翻譯n4.8 4.8 說明語句的翻譯說明語句的翻譯n4.9 4.9 遞歸下降語法制導(dǎo)翻譯方法簡介遞歸下降語法制導(dǎo)翻譯方法簡介4教學(xué)要求：教學(xué)要求：掌握掌握n語法制導(dǎo)翻譯方法語法制導(dǎo)翻譯方法n屬性文法，兩種屬性：綜合屬性、繼承屬性屬性文法，兩種屬性：綜合屬性、繼承屬性n幾種中間語言：抽象語法樹，逆波蘭表示，幾種中間語言：抽象語法樹，逆波蘭表示，三地址代碼，四元式，三元式，間接三元式三地址代碼，四元式，三元式，間接三元式n簡單算術(shù)表達式和賦值語句的翻譯簡單算術(shù)表達式和賦值語句的翻譯n布爾表達式的翻譯布爾表達式的翻譯n幾種控制流語句的翻譯幾種控制流語句的翻譯

3、n數(shù)組元素引用的翻譯數(shù)組元素引用的翻譯n過程或函數(shù)調(diào)用語句的翻譯以及參數(shù)的處理過程或函數(shù)調(diào)用語句的翻譯以及參數(shù)的處理n說明語句的翻譯說明語句的翻譯4.1 4.1 概述概述n4.1.1 4.1.1 語義分析的概念語義分析的概念 參見參見P91.P91.n一個源程序經(jīng)過詞法分析、語法分析后，表明源一個源程序經(jīng)過詞法分析、語法分析后，表明源程序在書寫上是正確的，并且符合程序語言所規(guī)程序在書寫上是正確的，并且符合程序語言所規(guī)定的語法。但是，語法分析并未對程序內(nèi)部的邏定的語法。但是，語法分析并未對程序內(nèi)部的邏輯含義加以分析，因此編譯程序接下來的工作是輯含義加以分析，因此編譯程序接下來的工作是語義分析，即

4、審查每個語法成分的靜態(tài)語義語義分析，即審查每個語法成分的靜態(tài)語義。n如果靜態(tài)語義正確，則如果靜態(tài)語義正確，則生成與該語言成分等效的生成與該語言成分等效的中間代碼，或者直接生成目標代碼中間代碼，或者直接生成目標代碼。n直接生成機器語言或匯編語言形式的目標代碼的直接生成機器語言或匯編語言形式的目標代碼的優(yōu)點是編譯時間短且無需中間代碼到目標代碼的優(yōu)點是編譯時間短且無需中間代碼到目標代碼的翻譯，而翻譯，而中間代碼的優(yōu)點是使編譯結(jié)構(gòu)在邏輯上中間代碼的優(yōu)點是使編譯結(jié)構(gòu)在邏輯上更為簡單明確，特別是使目標代碼的優(yōu)化比較容更為簡單明確，特別是使目標代碼的優(yōu)化比較容易實現(xiàn)易實現(xiàn)。6靜態(tài)語義檢查靜態(tài)語義檢查n語義分

5、析和中間代碼生成階段，編譯程序要語義分析和中間代碼生成階段，編譯程序要做的工作是進行做的工作是進行靜態(tài)語義檢查靜態(tài)語義檢查和和翻譯翻譯。把經(jīng)。把經(jīng)過語過語 法分析和語義分析而獲得的源程序中間法分析和語義分析而獲得的源程序中間表示翻譯為中間代碼表示。表示翻譯為中間代碼表示。n靜態(tài)語義檢查通常包括靜態(tài)語義檢查通常包括：參見參見P91.P91.n(1). 類型檢查，如參與運算的操作數(shù)及其類型；類型檢查，如參與運算的操作數(shù)及其類型；n(2). 控制流檢查，如控制轉(zhuǎn)移到合法轉(zhuǎn)向點；控制流檢查，如控制轉(zhuǎn)移到合法轉(zhuǎn)向點；n(3). 一致性檢查，如相同作用域中標識符只能說一致性檢查，如相同作用域中標識符只能說

6、明一次；明一次；n(4). 相關(guān)名字檢查，如同一名字必須出現(xiàn)兩次相關(guān)名字檢查，如同一名字必須出現(xiàn)兩次;n(5). 其他檢查，如名字的作用域分析。其他檢查，如名字的作用域分析。74.1.2 4.1.2 語法制導(dǎo)翻譯方法語法制導(dǎo)翻譯方法n語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法：是由源程序的語法結(jié)構(gòu)所驅(qū)動的：是由源程序的語法結(jié)構(gòu)所驅(qū)動的語義處理辦法。語義處理辦法。n語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法：直觀上說是為基礎(chǔ)文法的每個產(chǎn)：直觀上說是為基礎(chǔ)文法的每個產(chǎn)生式配上一個翻譯子程序生式配上一個翻譯子程序(稱為稱為語義子程序語義子程序或或語義動語義動作作，是一組，是一組語義規(guī)則語義規(guī)則)，并且在語法分析的同時執(zhí)行，并且

7、在語法分析的同時執(zhí)行這些語義子程序。這樣，語法分析工作和語義子程這些語義子程序。這樣，語法分析工作和語義子程序的執(zhí)行穿插進行。但序的執(zhí)行穿插進行。但以語法分析為主導(dǎo)以語法分析為主導(dǎo)。n語義動作語義動作(語義子程序、語義規(guī)則語義子程序、語義規(guī)則)：是為文法產(chǎn)生：是為文法產(chǎn)生式賦予具體意義的手段，它一方面指出了一個產(chǎn)生式賦予具體意義的手段，它一方面指出了一個產(chǎn)生式所產(chǎn)生的符號串的意義，另一方面又按照這種意式所產(chǎn)生的符號串的意義，另一方面又按照這種意義規(guī)定了生成某種中間代碼應(yīng)該做那些基本動作。義規(guī)定了生成某種中間代碼應(yīng)該做那些基本動作。8兩種語法制導(dǎo)翻譯方法兩種語法制導(dǎo)翻譯方法n語法制導(dǎo)翻譯法是在語

8、法分析的同時進行語義語法制導(dǎo)翻譯法是在語法分析的同時進行語義處理處理( (即翻譯即翻譯) )。因此，。因此，語法制導(dǎo)翻譯與兩個因語法制導(dǎo)翻譯與兩個因素密切相關(guān)素密切相關(guān): :n1. 所采用的語法分析方法所采用的語法分析方法(自上而下或自下而上自上而下或自下而上)n2. 語法分析到什么時候執(zhí)行語義動作語法分析到什么時候執(zhí)行語義動作n語義動作執(zhí)行的時間語義動作執(zhí)行的時間: :n1. 在自上而下語法分析中，當一個在自上而下語法分析中，當一個產(chǎn)生式匹配輸產(chǎn)生式匹配輸入串成功時入串成功時，執(zhí)行與此產(chǎn)生式相應(yīng)的語義動作。，執(zhí)行與此產(chǎn)生式相應(yīng)的語義動作。n2. 在自下而上語法分析中，當一個在自下而上語法分析

9、中，當一個產(chǎn)生式被用于產(chǎn)生式被用于進行歸約時進行歸約時，此產(chǎn)生式相應(yīng)的語義動作被執(zhí)行。，此產(chǎn)生式相應(yīng)的語義動作被執(zhí)行。n兩種語法制導(dǎo)翻譯法：自上而下、兩種語法制導(dǎo)翻譯法：自上而下、自下而上。自下而上。重點：自下而上語法制導(dǎo)翻譯重點：自下而上語法制導(dǎo)翻譯結(jié)合自下而上語法分析的結(jié)合自下而上語法分析的語法制導(dǎo)翻譯器語法制導(dǎo)翻譯器的實現(xiàn)的實現(xiàn)語法分析語法分析的同時完成的同時完成語義分析語義分析自下而上語法分析器自下而上語法分析器(如如LR分析器分析器)自下而上建立語法樹自下而上建立語法樹的結(jié)點的結(jié)點自下而上計算文法符自下而上計算文法符號號(結(jié)點結(jié)點)的語義值的語義值用用歸約歸約作為掛鉤作為掛鉤, 把語

10、法分析和語義分析結(jié)合起來，把語法分析和語義分析結(jié)合起來，在歸約時計算并保存文法符號的語義值在歸約時計算并保存文法符號的語義值 - 翻譯器翻譯器!10LR分析器改造為翻譯器分析器改造為翻譯器n在自下而上的分析器在自下而上的分析器(比如比如LR分析器分析器)中中, 要使用了一要使用了一個個分析棧分析棧來存放已經(jīng)分析過的符號串的語法信息。來存放已經(jīng)分析過的符號串的語法信息。n現(xiàn)在擴大現(xiàn)在擴大LR分析器的能力，使它能在分析器的能力，使它能在用某個產(chǎn)生式用某個產(chǎn)生式進行歸約的同時調(diào)用相應(yīng)的語義子程序進行有關(guān)的翻進行歸約的同時調(diào)用相應(yīng)的語義子程序進行有關(guān)的翻譯工作譯工作。n每個產(chǎn)生式的語義子程序執(zhí)行之后，

11、某些結(jié)果每個產(chǎn)生式的語義子程序執(zhí)行之后，某些結(jié)果(語義語義信息信息)必須作為此必須作為此產(chǎn)生式的左部符號的語義值產(chǎn)生式的左部符號的語義值暫時保暫時保存下來，以便以后語義子程序引用這些信息。存下來，以便以后語義子程序引用這些信息。n在在LR分析棧中增加使用一個分析棧中增加使用一個語義棧語義棧(val棧棧)存放文法存放文法符號相應(yīng)的語義值符號相應(yīng)的語義值；再擴充總控程序功能，于是就可；再擴充總控程序功能，于是就可以以將將LR分析器改造為一個翻譯器分析器改造為一個翻譯器。設(shè)置語義棧設(shè)置語義棧Val (參見參見P92.圖圖4-1)例如：產(chǎn)生式例如：產(chǎn)生式 AXYZ AXYZ語義子程序：語義子程序：A.

12、a = f(X.x,Y.y,Z.z)A.a = f(X.x,Y.y,Z.z)A.aX.xZ.zY.y sk Xk Xk.val s1 X1 X1.val s0 # _狀 態(tài)狀 態(tài)棧棧文法符號文法符號棧棧語義值語義值棧棧valtoptop sm Z Z.z sj Y Y.y si X X.x 狀 態(tài)狀 態(tài)棧棧文法符號文法符號棧棧語義值語義值棧棧 如果一個文法符號沒有語義值，那么語義棧如果一個文法符號沒有語義值，那么語義棧 val中相應(yīng)的元素就不定義中相應(yīng)的元素就不定義, 用用“_”表示表示, 占位置。占位置。用用AXYZAXYZ歸約之前的棧歸約之前的棧TopToptopstatevalZZ.zY

13、Y.yXX.xn在把在把XYZ歸約成歸約成A前前, 屬性屬性Z.z的值放在的值放在valtop中中, Y.y的值放在的值放在valtop-1中中, X.x的值放在的值放在valtop-2中。中。n當用當用AXYZ歸約時歸約時, 調(diào)用語義子程序計算語義值調(diào)用語義子程序計算語義值A(chǔ).a并保存在棧中。并保存在棧中。歸約后，歸約后，top值修改，語義值值修改，語義值A(chǔ).a存放存放在新的棧頂項在新的棧頂項valntop中。中。語義棧語義棧Val的作用的作用- 計算保存語義值計算保存語義值statevalA.aAntop用用AXYZ歸約后的語義棧歸約后的語義棧用用AXYZ歸約前的語義棧歸約前的語義棧 產(chǎn)生

14、式產(chǎn)生式 語義動作語義動作(使用了語義棧使用了語義棧) . (0) SE print(valtop) (1) E E(1)+ E(2) valntop:=valtop+valtop-2 (2) E E(1) * E(2) valntop:=valtop*valtop-2 (3) E (E(1) valntop:=valtop-1 (4) E i valntop:=lexval lexval為為 i 的整型內(nèi)部值，由詞法分析器提供的整型內(nèi)部值，由詞法分析器提供 top是歸約前的棧頂，是歸約前的棧頂，ntop是歸約后的棧頂是歸約后的棧頂例例: :用用LRLR分析器實現(xiàn)分析器實現(xiàn)臺式計算器臺式計算器

15、( (參見參見P92.P92.) )n例：計算表達式例：計算表達式7+9*5的值。用的值。用P83.表表3.20的分析表的分析表nP92.圖圖4-2，語法制導(dǎo)翻譯計算，語法制導(dǎo)翻譯計算7+9*5的帶附注語法樹的帶附注語法樹nP93.表表4.1，表達式，表達式7+9*5的語義分析和計值過程的語義分析和計值過程下頁下頁翻譯翻譯7+97+9* *5#, 5#, 求表達式的值求表達式的值i lexval=7i lexval=9E val=7E val=9E val=45+E val=52E val=5*i lexval=5參見參見P92.P92.圖圖4-2 4-2 結(jié)合自下而上分析語法制導(dǎo)翻譯結(jié)合自下

16、而上分析語法制導(dǎo)翻譯計算表達式計算表達式7+97+9* *5#5#值的值的帶語義注釋的語法樹以帶語義注釋的語法樹以及計值過程及計值過程。Print(E.val)上頁上頁 (4) (4) (4) (2) (1)步驟步驟 狀態(tài)棧狀態(tài)棧 符號棧符號棧 語義棧語義棧 輸入串輸入串 動作動作 1 0 # _ 7+9*5# s3 2 03 #7 _ 7 +9*5# r4 3 01 #E _ 7 +9*5# s4 4 014 #E+ _ 7 _ 9*5# s3 5 0143 #E+9 _ 7 _ 9 *5# r4 6 0147 #E+E _ 7 _9 *5# s5 7 01475 #E+E* _ 7 _9

17、_ 5# s3P93.P93.表表4.1 7+94.1 7+9* *5#5#的語義分析和計值過程的語義分析和計值過程 8 014753 #E+E*5 _ 7 _9_ 5 # r4 9 014758 #E+E*E _ 7 _9_ 5 # r2 10 0147 #E+E _ 7 _45 # r1 11 01 #E _ 52 # acc164.2 4.2 屬性文法屬性文法n屬性文法屬性文法(屬性翻譯文法屬性翻譯文法、語法制導(dǎo)定義語法制導(dǎo)定義)n屬性文法是編譯技術(shù)中用來說明程序語言語義屬性文法是編譯技術(shù)中用來說明程序語言語義的工具，也是當前實際應(yīng)用中比較流行的的工具，也是當前實際應(yīng)用中比較流行的一種一

18、種語義描述工具語義描述工具。n屬性文法是一種適用于定義語言語義的特殊文屬性文法是一種適用于定義語言語義的特殊文法，即在語言的文法中增加了屬性的文法。實法，即在語言的文法中增加了屬性的文法。實際上，際上，屬性文法是對上下文無關(guān)文法的推廣屬性文法是對上下文無關(guān)文法的推廣。n屬性文法屬性文法：是以一個上下文無關(guān)文法為基礎(chǔ)：是以一個上下文無關(guān)文法為基礎(chǔ), 為每個文法符號引進一組屬性為每個文法符號引進一組屬性(語義值語義值)，對文，對文法的每個產(chǎn)生式都配備一組與之相關(guān)聯(lián)的屬性法的每個產(chǎn)生式都配備一組與之相關(guān)聯(lián)的屬性的計算規(guī)則的計算規(guī)則(語義規(guī)則語義規(guī)則), 這樣得到的文法。這樣得到的文法。174.2.1

19、 4.2.1 文法符號的屬性文法符號的屬性n屬性屬性：是指與文法符號的類型和值等有關(guān)的一：是指與文法符號的類型和值等有關(guān)的一些語義信息，在編譯中用屬性描述處理對象的些語義信息，在編譯中用屬性描述處理對象的語義特征。語義特征。n屬性代表與文法符號相關(guān)的語義信息屬性代表與文法符號相關(guān)的語義信息。n屬性的設(shè)置屬性的設(shè)置和語法結(jié)構(gòu)的語義以及翻譯程序的和語法結(jié)構(gòu)的語義以及翻譯程序的需要有關(guān)。需要有關(guān)。例如例如: :n文法符號文法符號X X的類型屬性的類型屬性: : X.type X.type n文法符號文法符號X X的值屬性的值屬性: : X.valX.valn文法符號文法符號X X的代碼序列的代碼序列

20、 : : X.codeX.coden文法符號文法符號X X的符號表入口指針的符號表入口指針: : X.entry X.entry 等等。等等。18屬性、語義規(guī)則屬性、語義規(guī)則n屬性和變量一樣屬性和變量一樣，可以在語法分析過程中進行，可以在語法分析過程中進行計算和傳遞。計算和傳遞。n語義規(guī)則語義規(guī)則：屬性的計算規(guī)則屬性的計算規(guī)則。屬性的加工和計。屬性的加工和計算的過程即是語義處理的過程，即語義動作、算的過程即是語義處理的過程，即語義動作、語義子程序。語義子程序。n屬性一般分為兩類：屬性一般分為兩類：綜合屬性綜合屬性和和繼承屬性。繼承屬性。n終結(jié)符只有綜合屬性終結(jié)符只有綜合屬性, 它它由詞法分析器

21、提供由詞法分析器提供 例如例如 “i.lexval” 表示單詞符號表示單詞符號“數(shù)數(shù)”的詞法值的詞法值 id.entry 表示單詞符號表示單詞符號“標識符標識符”的符號表入口的符號表入口n非終結(jié)符既可以有綜合屬性也可以有繼承屬性非終結(jié)符既可以有綜合屬性也可以有繼承屬性19兩種屬性：綜合屬性兩種屬性：綜合屬性n綜合屬性綜合屬性用于用于“自下而上自下而上”傳遞信息。傳遞信息。n綜合屬性綜合屬性：在語法樹中，一個結(jié)點的綜合屬性：在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性值確定。的值由其子結(jié)點的屬性值確定。n通常通常結(jié)合自下而上的語法分析在每一個結(jié)點處結(jié)合自下而上的語法分析在每一個結(jié)點處使用語

22、義規(guī)則計算綜合屬性的值使用語義規(guī)則計算綜合屬性的值 - - 由下層由下層子結(jié)點的屬性值計算上層父結(jié)點的綜合屬性值，子結(jié)點的屬性值計算上層父結(jié)點的綜合屬性值，隨著自下而上語法分析的進行，最終可計算出隨著自下而上語法分析的進行，最終可計算出開始符號的綜合屬性值。開始符號的綜合屬性值。A X1 X2 XnA.b X1. .c1 X2 .c.c2 Xn . ckA X1X2Xn 綜合屬性綜合屬性A.b:=f(c1,c2,ck) 帶注釋的帶注釋的語法樹語法樹20兩種屬性：繼承屬性兩種屬性：繼承屬性n繼承屬性繼承屬性用于用于“自上而下自上而下”傳遞信息。傳遞信息。n繼承屬性繼承屬性：在語法樹中，一個結(jié)點的

23、繼承屬：在語法樹中，一個結(jié)點的繼承屬性由此結(jié)點的父結(jié)點和性由此結(jié)點的父結(jié)點和( (或或) )兄結(jié)點的某些屬兄結(jié)點的某些屬性確定。性確定。n可以用繼承屬性來表示程序語言結(jié)構(gòu)中的上可以用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系。下文依賴關(guān)系。n繼承屬性的計算可以繼承屬性的計算可以結(jié)合自上而下的語法分結(jié)合自上而下的語法分析進行析進行。A X1 X XnA. ck X1. .c1 X.b Xn A X1X2XXn 繼承屬性繼承屬性 X.b:=f(c1,c2,ck) 214.2.2 4.2.2 屬性文法屬性文法n屬性文法的形式：屬性文法的形式： 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 . A b = f(c

24、1,c2,ck) n這里這里, f 是一個函數(shù)或過程是一個函數(shù)或過程, 表示屬性表示屬性 b 依賴于屬依賴于屬性性 c1,c2,ck。如果如果 f 沒有返回值，則認為沒有返回值，則認為 b 是是一個虛屬性。一個虛屬性。n語義規(guī)則所描述的工作語義規(guī)則所描述的工作可以是任何希望的翻可以是任何希望的翻譯工作，如譯工作，如: : 屬性計算、靜態(tài)語義檢查、符號屬性計算、靜態(tài)語義檢查、符號表操作、中間代碼生成、報告錯誤，表操作、中間代碼生成、報告錯誤， 等等。等等。舉例：只帶綜合屬性的屬性文法舉例：只帶綜合屬性的屬性文法( (P94.)n一個簡單算術(shù)表達式求值的屬性文法。輸入一個含一個簡單算術(shù)表達式求值的

25、屬性文法。輸入一個含+、*、(、)和數(shù)字的算術(shù)表達式和數(shù)字的算術(shù)表達式, 計算并打印其值計算并打印其值。 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則(1) SE Print(E.val)(2) EE(1)+T E.val:=E(1).val+T.val(3) ET E.val:=T.val(4) TT(1)*F T.val:=T(1).val*F.val(5) TF T.val:=F.val(6) F(E) F.val:=E.val(7) Fi F.val:=i.lexval1. 非終結(jié)符非終結(jié)符E, T, F有綜有綜合屬性合屬性val - 表達式值表達式值2. 終結(jié)符終結(jié)符 i 有綜合屬性有綜合屬性le

26、xval - 數(shù)的二進制值，數(shù)的二進制值，由詞法分析器提供由詞法分析器提供3. 注：注：同一個產(chǎn)生式的同一個產(chǎn)生式的相同非終結(jié)符加相同非終結(jié)符加上標上標，以區(qū)分這些非終結(jié)符的以區(qū)分這些非終結(jié)符的屬性值的引用屬性值的引用i lexval=3i lexval=5i lexval=4F val=3T val=3F val=5T val=15*E val=15F val=4T val=4+E val=19SPrint(E.val)自下而上語法制自下而上語法制導(dǎo)翻譯導(dǎo)翻譯 3 3* *5+45+4求表達式的值求表達式的值 (7) (5) (7) (4) (3) (7) (5) (2) (1)舉例：舉例：

27、帶有繼承屬性的屬性文法帶有繼承屬性的屬性文法( (P94.) 產(chǎn)生式產(chǎn)生式 語義規(guī)則語義規(guī)則 . (1) DTL L. in:= T. type (2) T int T. type := integer (3) T float T. type := real (4) L L(1), id L(1) . in := L. in； addtype(id. entry, L. in) (5) L id addtype(id. entry, L. in) T.type 是綜合屬是綜合屬性性 - 表示標識符表示標識符的類型信息的類型信息 L.in 為繼承屬為繼承屬性性 - 表示并傳遞表示并傳遞標識符的類

28、型信息標識符的類型信息addtype(id. entry, L. in)把標識符把標識符 id的類型信息填入符的類型信息填入符號表中號表中n一個簡單變量類型說明的屬性文法。一個簡單變量類型說明的屬性文法。翻譯：翻譯：輸入如輸入如下形式的說明語句下形式的說明語句 float x, y, z 或者或者 int x, y, z， 把把變量變量x、y、z的類型信息填入符號表中。的類型信息填入符號表中。P95.P95.圖圖4-3 4-3 說明語句：說明語句： float idfloat id1 1,id,id2 2,id,id3 3的帶有繼承屬性的語法樹的帶有繼承屬性的語法樹及其屬性信息傳遞情況。及其屬

29、性信息傳遞情況。繼承屬性繼承屬性 in的值自上的值自上而下計算、傳遞和流而下計算、傳遞和流動。動。三個三個L結(jié)點的結(jié)點的 L.in分分別給出標識符別給出標識符id1、id2和和id3的類型。的類型。過程過程addtype(id.entry,L.in)把把 id 的類型填入符號的類型填入符號表。表。id3T.type= realDL.in=realL.in= realfloatL.in= real,id1id2,L.in=T.typeL(1).in=L.inL(1).in=L.inaddtype(id.entry,L.in)26練習：寫屬性文法練習：寫屬性文法n基礎(chǔ)文法是基礎(chǔ)文法是P94.的算術(shù)

30、表達式文法的算術(shù)表達式文法, 定義一個定義一個屬性文法，屬性文法，計算表達式中算符的個數(shù)計算表達式中算符的個數(shù)，即輸，即輸入一個算術(shù)表達式，輸出其中算符的個數(shù)。入一個算術(shù)表達式，輸出其中算符的個數(shù)。 產(chǎn)生式產(chǎn)生式 SE EE(1) +T ET TT(1) *F TF F(E) Fin設(shè)置：設(shè)置：nE.c E.c 綜合屬性綜合屬性nT.c T.c 綜合屬性綜合屬性nF.c F.c 綜合屬性綜合屬性n幾個綜合屬性表幾個綜合屬性表示表達式示表達式E E、T T、F F 中算符的個數(shù)中算符的個數(shù) 語義規(guī)則語義規(guī)則 Print(E.c) E.c:=E(1).c+T.c+1 E.c:=T.c T.c:=T

31、(1).c+F.c+1 T.c:=F.c F.c:=E.c F.c:=027 4.3 4.3 幾種常見的中間語言幾種常見的中間語言 n要掌握幾種常見的中間語言的基本結(jié)構(gòu)：要掌握幾種常見的中間語言的基本結(jié)構(gòu)：n圖表示法：抽象語法樹圖表示法：抽象語法樹n逆波蘭表示法逆波蘭表示法( (也稱后綴式也稱后綴式) )n三地址代碼三地址代碼n四元式四元式n三元式、間接三元式三元式、間接三元式284.3.1 圖表示法：抽象語法樹圖表示法：抽象語法樹n語法制導(dǎo)翻譯以語法樹作基礎(chǔ)語法制導(dǎo)翻譯以語法樹作基礎(chǔ), 實際上實際上, 語法樹可以語法樹可以作為一種合適的中間語言形式。作為一種合適的中間語言形式。n現(xiàn)在對語法樹

32、進行改造，去掉那些對翻譯不必要的現(xiàn)在對語法樹進行改造，去掉那些對翻譯不必要的信息，將語法樹進行抽象信息，將語法樹進行抽象 - 抽象語法樹抽象語法樹。n在抽象語法樹中，每個葉結(jié)點都表示諸如常量或變在抽象語法樹中，每個葉結(jié)點都表示諸如常量或變量這樣的運算對象，而其它內(nèi)部結(jié)點則表示運算符。量這樣的運算對象，而其它內(nèi)部結(jié)點則表示運算符。n抽象語法樹不同于語法樹，它展示了一個操作過程抽象語法樹不同于語法樹，它展示了一個操作過程并同時描述了源程序的層次結(jié)構(gòu)。并同時描述了源程序的層次結(jié)構(gòu)。n語法制導(dǎo)翻譯既可以基于語法分析樹也可以基于抽語法制導(dǎo)翻譯既可以基于語法分析樹也可以基于抽象語法樹進行象語法樹進行，采用

33、的基本方法是一樣的。，采用的基本方法是一樣的。29抽象語法樹：簡例抽象語法樹：簡例( (參見參見P95.P95.圖圖4-4)4-4)n為下面文法的句子為下面文法的句子 x = a-4x = a-4* *c c 建立抽象語法樹：建立抽象語法樹： SV=E Vid E E+E | E-E | E*E | (E) | id | numn為每個運算量或運算符號都建立一個結(jié)點。為每個運算量或運算符號都建立一個結(jié)點。n可以可以根據(jù)表達式的運算順序自下而上的構(gòu)造根據(jù)表達式的運算順序自下而上的構(gòu)造 - 手工手工構(gòu)造。構(gòu)造。抽象語法樹抽象語法樹運算符作內(nèi)運算符作內(nèi)部結(jié)點部結(jié)點語法樹語法樹 比較：比較：抽象語法樹

34、的特點是結(jié)構(gòu)抽象語法樹的特點是結(jié)構(gòu)緊湊，容易構(gòu)造，結(jié)點較少。緊湊，容易構(gòu)造，結(jié)點較少。c*4a-xassign 表示賦值表示賦值id(c)E E * EE - Enum(4)id(a )S V = id(x )30n可以設(shè)計屬性文法構(gòu)造可以設(shè)計屬性文法構(gòu)造抽象語法樹。抽象語法樹。n下面舉例介紹手工構(gòu)造下面舉例介紹手工構(gòu)造抽象語法樹的方法。抽象語法樹的方法。n構(gòu)造賦值語句：構(gòu)造賦值語句： x=ab*(c-d)-e/f 的抽象語法樹的抽象語法樹，根據(jù)表根據(jù)表達式的運算順序自下而達式的運算順序自下而上的構(gòu)造。上的構(gòu)造。 手工構(gòu)造抽象語法樹：例手工構(gòu)造抽象語法樹：例 -a+xassign *b -cd

35、/ef31 4.3.2 4.3.2 逆波蘭表示法逆波蘭表示法( (參見參見P96.)P96.)n逆波蘭表示法逆波蘭表示法又稱又稱后綴式后綴式表示法。逆波蘭表表示法。逆波蘭表示法是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的一種示法是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的一種表示表達式的方法表示表達式的方法。這種方法是，把運算量。這種方法是，把運算量( (操作數(shù)操作數(shù)) )寫在運算符的前面，把運算符寫在寫在運算符的前面，把運算符寫在運算量的后面運算量的后面( (后綴后綴) )。n例：例：a+b ab+ a*(b+c) abc+* (a+b)*(c+d) ab+cd+*n逆波蘭表示法逆波蘭表示法也可以推廣到其他程序語句。也

36、可以推廣到其他程序語句。32 表達式的逆波蘭表示表達式的逆波蘭表示( (參見參見P96.)P96.)n一個一個表達式的后綴式表達式的后綴式可以如下遞歸定義：可以如下遞歸定義：1. 如果如果E是一個變量或常量，則是一個變量或常量，則E的后綴式是的后綴式是E自身。自身。2. 如果如果E是是 E1 op E2 形式的表達式，這里形式的表達式，這里op是是任何二元操作符，則任何二元操作符，則E的后綴式為的后綴式為 E1 E2 op,這里這里E1 和和E2分別為分別為E1和和E2的后綴式。的后綴式。3. 如果如果E是是(E1)形式的表達式，則形式的表達式，則E1的后綴式的后綴式就是就是E的后綴式。的后綴

37、式。n要求會正確寫出表達式的后綴式要求會正確寫出表達式的后綴式。33 后綴式遞歸定義的實質(zhì)后綴式遞歸定義的實質(zhì)( (參見參見P96.)P96.)n表達式的后綴式遞歸定義的實質(zhì)是：表達式的后綴式遞歸定義的實質(zhì)是：1. 后綴式中操作數(shù)出現(xiàn)的順序與原來一致。后綴式中操作數(shù)出現(xiàn)的順序與原來一致。2. 后綴式中運算符出現(xiàn)的次序即表達式的運算次序；后綴式中運算符出現(xiàn)的次序即表達式的運算次序；運算符按運算的先后順序放入相應(yīng)的操作數(shù)之后運算符按運算的先后順序放入相應(yīng)的操作數(shù)之后(即運算符先后的順序發(fā)生了變化即運算符先后的順序發(fā)生了變化)。3. 不再使用括號來規(guī)定運算的順序。不再使用括號來規(guī)定運算的順序。n例：

38、例：(a+b)*(c+d) ab+cd+*用用 uminus 表表示取負算符示取負算符-a+b*c a uminus bc*+A=5 CB = D A 5 = C B D = 34a 后綴式的計值后綴式的計值( (參見參見P96.)P96.)n后綴表示的計值用棧實現(xiàn)后綴表示的計值用棧實現(xiàn)很方便很方便n計值過程是自左至右掃描后綴式，遇運算量就把計值過程是自左至右掃描后綴式，遇運算量就把它推進棧，遇它推進棧，遇k目運算符就把它作用于棧頂?shù)哪窟\算符就把它作用于棧頂?shù)膋個個運算量，并用運算的結(jié)果運算量，并用運算的結(jié)果(即一個運算量即一個運算量)來取代棧來取代棧頂?shù)捻數(shù)膋個運算量，即出棧、進棧的操作。個

39、運算量，即出棧、進棧的操作。n例：例： -a+b*c 后綴式：后綴式：a uminus b c * + cb-ab*c -a+b*c35寫后綴式：練習寫后綴式：練習n寫出下列各式的逆波蘭表示寫出下列各式的逆波蘭表示: (1) -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C (D/E)/F (3) a/b*c-d*e (4) (A0B0)n解：解： (1) a uminus bc*cd-/b uminus a*+ - (2) A uminus BCDE/*F/+ (3) abc*/de* - (4) A0=B0 或或 A0=B0 and not36 程序語句的逆波蘭表示程序

40、語句的逆波蘭表示n賦值語句的逆波蘭表示：賦值語句的逆波蘭表示：參見參見P96.P96.n = =n例如例如賦值語句：賦值語句： x = a-b/(c+d) 逆波蘭表示為：逆波蘭表示為： x a b c d + / - = 或者或者 x a b c d + / - assign可用可用 assign 表示表示賦值算符賦值算符37 轉(zhuǎn)移語句的逆波蘭表示轉(zhuǎn)移語句的逆波蘭表示n為了用逆波蘭式表示一些控制語句，需要定義為了用逆波蘭式表示一些控制語句，需要定義轉(zhuǎn)移操作符號：轉(zhuǎn)移操作符號：參見參見P96.P96.n(1) BL：轉(zhuǎn)向某標號，單目算符轉(zhuǎn)向某標號，單目算符n(2) BT：條件為真時轉(zhuǎn)移，雙目算符

41、條件為真時轉(zhuǎn)移，雙目算符n(3) BF：條件為假時轉(zhuǎn)移，雙目算符條件為假時轉(zhuǎn)移，雙目算符n(4) BR：無條件轉(zhuǎn)移，單目算符無條件轉(zhuǎn)移，單目算符n算符算符BT、BF的意義：的意義：參見參見P97.P97. BT BFe為真時轉(zhuǎn)移為真時轉(zhuǎn)移到順序號到順序號e為假時轉(zhuǎn)移為假時轉(zhuǎn)移到順序號到順序號38 GOTOGOTO語句的逆波蘭表示語句的逆波蘭表示nGOTOGOTO語句的逆波蘭表示：語句的逆波蘭表示：參見參見P96.P96.nGOTO BL n例如例如GOTOGOTO語句：語句： GOTO L1 逆波蘭表示為：逆波蘭表示為： L1 BL39n條件語句條件語句 if (e) S1; else S2

42、的逆波蘭表示：的逆波蘭表示： BF /*e假轉(zhuǎn)假轉(zhuǎn)*/ /*e真時執(zhí)行真時執(zhí)行S1*/ BR /* S1執(zhí)行后無條件轉(zhuǎn)執(zhí)行后無條件轉(zhuǎn)*/ 條件語句的逆波蘭表示條件語句的逆波蘭表示( (P97.)P97.)順序號順序號2順序號順序號1 n布爾式布爾式e e的逆波蘭式和順序號是兩個特殊的運的逆波蘭式和順序號是兩個特殊的運算分量。算分量?！绊樞蛱栱樞蛱枴北硎灸娌ㄌm式中單詞符號表示逆波蘭式中單詞符號的順序號，即第幾個單詞的順序號，即第幾個單詞。條件語句的逆波蘭表示例條件語句的逆波蘭表示例( (參見參見P97.)P97.)n例：條件語句例：條件語句 if (mn) k=i+1; else k=i-1的逆

43、的逆波蘭表示為：波蘭表示為：(1) m n (4) 13 BF(6) k i 1 + =(11) 18 BR(13) k i 1 - =(18) if 語句的后繼語句語句的后繼語句順序號順序號1是是13順序號順序號2是是18n逆波蘭表示可以寫為幾行，也可以寫為一行：逆波蘭表示可以寫為幾行，也可以寫為一行： m n 13 BF k i 1 + = 18 BR k i 1 - =41循環(huán)語句的逆波蘭表示循環(huán)語句的逆波蘭表示( (參見參見P97.)P97.)n循環(huán)語句不能直接用逆波蘭表示，可以先將其循環(huán)語句不能直接用逆波蘭表示，可以先將其展開為等價的條件語句后再用逆波蘭表示。展開為等價的條件語句后再

44、用逆波蘭表示。n如如 forfor循環(huán)語句循環(huán)語句 for (i=m; i=n; i+) S; 展開展開為：為： i=mL0： if (i=n) S; i=i+1; goto L0 42 后綴式與抽象語法樹的關(guān)系后綴式與抽象語法樹的關(guān)系n后綴式是抽象語后綴式是抽象語法樹的線性表示法樹的線性表示形式形式。是樹的后。是樹的后序遍歷序遍歷(左，右，左，右，根根)的一個序列。的一個序列。n例如例如: a = b * - c+b * -c的抽象語法樹。的抽象語法樹。assigna+*bcuminus*uminuscb后綴式后綴式: : a b c uminus * b c uminus * + assi

45、gn43 4.3.3 三地址代碼三地址代碼(參見參見P97.)n三地址代碼是由下面一般形式的語句構(gòu)成的三地址代碼是由下面一般形式的語句構(gòu)成的序列序列: x = y op zn其中，其中，x、y、z為名字、常數(shù)或編譯時產(chǎn)生為名字、常數(shù)或編譯時產(chǎn)生的臨時變量；的臨時變量；op代表運算符號。代表運算符號。n每個三地址語句的右邊只能有一個運算符。每個三地址語句的右邊只能有一個運算符。n例例, 表達式表達式 x+y*z 翻譯為三地址代碼翻譯為三地址代碼: T1 = y*z T2 = x+T1nT1, T2是編譯時產(chǎn)生的臨時變量。是編譯時產(chǎn)生的臨時變量。44三地址代碼：說明三地址代碼：說明n1. 之所以稱

46、為三地址代碼，是因為三地址代碼之所以稱為三地址代碼，是因為三地址代碼語句類似與匯編指令語句類似與匯編指令, 涉及三個地址涉及三個地址 x、y和和z，其中其中y、z表示操作數(shù)，表示操作數(shù)，x存放結(jié)果。存放結(jié)果。地址常用地址常用屬性屬性place表示表示。n名字名字.place：指向符號表名字入口的指針指向符號表名字入口的指針n臨時變量臨時變量.place：臨時變量值存放的單元地址臨時變量值存放的單元地址n常數(shù)常數(shù).place：指向常數(shù)表中常數(shù)入口的指針指向常數(shù)表中常數(shù)入口的指針n2. 三地址語句可以帶符號標號三地址語句可以帶符號標號, 標號對應(yīng)存放標號對應(yīng)存放三地址代碼語句的數(shù)組的下標。三地址代

47、碼語句的數(shù)組的下標。n3. 三地址代碼是抽象語法樹的線性化表示三地址代碼是抽象語法樹的線性化表示 - 樹的每個內(nèi)部結(jié)點對應(yīng)一個三地址語句。樹的每個內(nèi)部結(jié)點對應(yīng)一個三地址語句。 45n例例，P95.P95.圖圖4-4 4-4 (a)(a)的賦值語句的賦值語句 x=a-bx=a-b* *c c 的抽的抽象語法樹象語法樹 ，按樹自下而上的順序?qū)懗雒總€內(nèi)按樹自下而上的順序?qū)懗雒總€內(nèi)部結(jié)點對應(yīng)的三地址代碼部結(jié)點對應(yīng)的三地址代碼： T1 b* c T2 a-T1 x T2 n注：注： 臨時變量的名字對應(yīng)抽象語法樹的內(nèi)部臨時變量的名字對應(yīng)抽象語法樹的內(nèi)部結(jié)點結(jié)點( (算符結(jié)點算符結(jié)點), ), 表達式中的每

48、個運算都要引表達式中的每個運算都要引入一個新的臨時變量存放計算結(jié)果入一個新的臨時變量存放計算結(jié)果, , 要多少引要多少引入多少。入多少。抽象語法樹與三地址代碼的關(guān)系抽象語法樹與三地址代碼的關(guān)系46n(1) 賦值語句賦值語句 x y op z ; op是二元算術(shù)或邏輯運算符是二元算術(shù)或邏輯運算符n(2) 賦值語句賦值語句 x op y ; op是一元算符，如取負運算符是一元算符，如取負運算符uminus、邏輯非運算邏輯非運算符符not、移位運算符及類型轉(zhuǎn)換運算符。移位運算符及類型轉(zhuǎn)換運算符。n(3) 復(fù)制語句復(fù)制語句 x y;n(4) 無條件轉(zhuǎn)移語句無條件轉(zhuǎn)移語句 goto L; L是語句標號。

49、是語句標號。 n(5) 條件轉(zhuǎn)移語句條件轉(zhuǎn)移語句 if x rop y goto L ; if a goto L ; rop 是關(guān)系運算符是關(guān)系運算符; a是布爾量是布爾量三地址語句的種類三地址語句的種類(參見參見P98.)47n(6) 過程調(diào)用語句過程調(diào)用語句 par x1; xi 是實參數(shù)是實參數(shù) par x2; par xn; call p, n ; p過程名過程名, n實參個數(shù)實參個數(shù) 過程返回語句過程返回語句 return y; y返回值返回值, 可有可無可有可無n(7) 變址賦值語句變址賦值語句 x = yi; = 變址取數(shù)變址取數(shù) xi = y ; = 變址存數(shù)變址存數(shù)n(8)

50、地址和指針賦值語句地址和指針賦值語句 x y; x * y; * x y;三地址語句的種類三地址語句的種類(續(xù)續(xù) P98.) 四元式四元式 ( op, arg1, arg2, result ) 用了四個域用了四個域 三元式三元式 ( op, arg1, arg2 ) 只用三個域只用三個域 間接三元式間接三元式 間接碼表間接碼表+三元式表，三元式表， 便于進行優(yōu)化便于進行優(yōu)化n四元式需要較多的臨時單元。四元式之間四元式需要較多的臨時單元。四元式之間 的聯(lián)系通的聯(lián)系通過臨時變量實現(xiàn)過臨時變量實現(xiàn), 三元式之間的聯(lián)系通過指針實現(xiàn)。三元式之間的聯(lián)系通過指針實現(xiàn)。n中間代碼優(yōu)化處理時，四元式比三元式方便

51、得多中間代碼優(yōu)化處理時，四元式比三元式方便得多, 間間接三元式與四元式同樣方便，四元式和三元式兩種接三元式與四元式同樣方便，四元式和三元式兩種實現(xiàn)方式需要的存儲空間大體相同。實現(xiàn)方式需要的存儲空間大體相同。三地址代碼的具體實現(xiàn)三地址代碼的具體實現(xiàn)(參見參見P98.)算符算符操作數(shù)操作數(shù)1(指針指針) 操作數(shù)操作數(shù)2(指針指針)結(jié)果結(jié)果(臨變臨變)n三地址代碼的具體實現(xiàn)三地址代碼的具體實現(xiàn): 用記錄結(jié)構(gòu)用記錄結(jié)構(gòu), 含四個域含四個域 三地址語句三地址語句 四元式表示四元式表示 參見參見P99. x = y op z ( op, y, z, x ) x = -y ( uminus, y, _ ,

52、x ) x = y ( =, y, _, x ) par x1 ( par, x1, _, _ ) call P (call, _, _, P ) goto L ( j, _, _, L ) 無條件轉(zhuǎn)移無條件轉(zhuǎn)移 if a goto L ( jnz, a, _, L ) 條件轉(zhuǎn)移條件轉(zhuǎn)移 a是邏輯量，是邏輯量，a非非0, 即即a為真時轉(zhuǎn)移為真時轉(zhuǎn)移 if x rop y goto L ( jrop, x, y, L ) 條件轉(zhuǎn)移條件轉(zhuǎn)移 rop是關(guān)系運算符是關(guān)系運算符, x和和y為算術(shù)量，為算術(shù)量，x rop y 為真時轉(zhuǎn)移為真時轉(zhuǎn)移常用的三地址語句對應(yīng)的四元式常用的三地址語句對應(yīng)的四元式50

53、n例：賦值語句例：賦值語句a=ba=b* *-c+b-c+b* *-c -c 的四元式：的四元式：見見P99.(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcbT2T5arg1T1T3T4arg2resultT1T2T3T4T5aop三地址代碼實現(xiàn)：四元式表示三地址代碼實現(xiàn)：四元式表示n注：注：四元式出現(xiàn)的順序與表達式計值的順序四元式出現(xiàn)的順序與表達式計值的順序一致；四元式之間一致；四元式之間 的聯(lián)系通過臨時變量實現(xiàn)。的聯(lián)系通過臨時變量實現(xiàn)。(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcb(1)aarg1(0)(2)(3

54、)(4)arg2opn例：賦值語句例：賦值語句a=ba=b* *-c+b-c+b* *-c -c 的三元式：的三元式： 見見P99.n注：注：三元式中使用了指向三元式語句的指針三元式中使用了指向三元式語句的指針( (序號序號) )，序號也表示該三元式計算的結(jié)果值；，序號也表示該三元式計算的結(jié)果值； 三元式之間三元式之間 的聯(lián)系通過指針實現(xiàn)。的聯(lián)系通過指針實現(xiàn)。三地址代碼實現(xiàn)：三元式表示三地址代碼實現(xiàn)：三元式表示n例：賦值語句例：賦值語句a=ba=b* *-c+b-c+b* *-c -c的的間接三元式間接三元式：P99.(0)(1)(2)(3)uminus*+assigncb(1)aarg1(0

55、)(1)(2)arg2op三元式表三元式表(0)(1)(0)(1)(2)(3)間接碼表間接碼表n間接碼表按運算的次序列出三元式序號，三元式表只間接碼表按運算的次序列出三元式序號，三元式表只列出不同的三元式。列出不同的三元式。 三元式表中沒有了重復(fù)的三元三元式表中沒有了重復(fù)的三元式，語句的移動僅改變左邊的間接碼表。式，語句的移動僅改變左邊的間接碼表。參見參見P99.三地址代碼實現(xiàn)：間接三元式三地址代碼實現(xiàn)：間接三元式53寫中間語言：練習寫中間語言：練習n寫出賦值語句：寫出賦值語句：A=B*(C-D)-E/FG 的逆波蘭表示、三元式表示、四元式表示。的逆波蘭表示、三元式表示、四元式表示。n解解:

56、四元式表示四元式表示：( - , C , D , T1 ) (* , B , T1, T2 ) ( , F , G , T3 ) ( / , E , T3, T4 ) ( - , T2, T4, T5 ) ( = , T5, _ , A )n解解: 三元式表示三元式表示：( - , C , D )(* , B , )( , F , G ) ( / , E , ) ( - , , ) ( = , , A )n解：解：逆波蘭表示逆波蘭表示： ABCD -*EFG/ - =544.4 表達式及賦值語句的翻譯表達式及賦值語句的翻譯n4.4.1 簡單算術(shù)表達式及賦值語句的翻譯簡單算術(shù)表達式及賦值語句的翻

57、譯 P100.P100. n簡單算術(shù)表達式是一種簡單算術(shù)表達式是一種僅含簡單變量僅含簡單變量的算術(shù)表達式。的算術(shù)表達式。n簡單變量是指普通變量和常數(shù)，簡單變量是指普通變量和常數(shù)，不含數(shù)組元素及結(jié)不含數(shù)組元素及結(jié)構(gòu)引用等復(fù)合型數(shù)據(jù)結(jié)構(gòu)構(gòu)引用等復(fù)合型數(shù)據(jù)結(jié)構(gòu)。n簡單算術(shù)表達式的簡單算術(shù)表達式的計值順序與四元式出現(xiàn)的順序相計值順序與四元式出現(xiàn)的順序相同同，因此很容易將其翻譯成四元式形式，這些翻譯，因此很容易將其翻譯成四元式形式，這些翻譯方法稍加修改也可用于產(chǎn)生三元式或間接三元式。方法稍加修改也可用于產(chǎn)生三元式或間接三元式。n4.4.2. 布爾表達式的翻譯布爾表達式的翻譯 P101.P101. n布爾

58、表達式是用布爾運算符布爾表達式是用布爾運算符 not 、 and 、 or 作用到布爾變量或關(guān)系表達式上而組成的。作用到布爾變量或關(guān)系表達式上而組成的。 4.4.1 簡單算術(shù)表達式及賦值語句的翻譯簡單算術(shù)表達式及賦值語句的翻譯n賦值語句及算術(shù)表達式的文法賦值語句及算術(shù)表達式的文法GAGA：見見P100.P100. n(1) Ai = E (4) E En(2) EE+E (5) E (E)n(3) E E*E (6) E i n為了實現(xiàn)由賦值語句和表達式到四元式的翻為了實現(xiàn)由賦值語句和表達式到四元式的翻譯，需要給文法加上語義子程序。譯，需要給文法加上語義子程序。n參見參見P100.101. P

59、100.101. 文法文法GAGA中每一個產(chǎn)生式的中每一個產(chǎn)生式的語義子程序。語義子程序。n語義子程序涉及的語義變量、語義過程及函語義子程序涉及的語義變量、語義過程及函數(shù)見下屏。數(shù)見下屏。 參見參見P100.P100. 簡單算術(shù)表達式及賦值語句的翻譯：說明簡單算術(shù)表達式及賦值語句的翻譯：說明n語義子程序涉及的語義變量、語義過程及函數(shù)：語義子程序涉及的語義變量、語義過程及函數(shù)：參見參見P100. P100. n語義變量語義變量E.place 表示存放表示存放E值的地方：變量名在值的地方：變量名在符號表中的入口地址；臨時變量名的整數(shù)碼。符號表中的入口地址；臨時變量名的整數(shù)碼。n語義函數(shù)語義函數(shù)ne

60、wtemp( ) 產(chǎn)生一個新的臨時變量產(chǎn)生一個新的臨時變量 T1，T2，等。等。n語義過程語義過程emit (op,arg1,arg2,result) 產(chǎn)生一個四元產(chǎn)生一個四元式并填入四元式表中。式并填入四元式表中。n語義過程語義過程lookup() 檢查檢查是否出現(xiàn)在符是否出現(xiàn)在符號表中，是則返回號表中，是則返回在符號表的入口指針，在符號表的入口指針，否則，否則返回否則，否則返回NULL。n應(yīng)用文法應(yīng)用文法GA的語義子程序，分析賦值語句：的語義子程序，分析賦值語句： X= -B*(C+D) 的語法制導(dǎo)翻譯過程。的語法制導(dǎo)翻譯過程。n解：自下而上語法制導(dǎo)翻譯