語法制導(dǎo)翻譯概述

編譯程序的功能和組織結(jié)構(gòu)表處理詞法分析源程序目標程序錯誤處理語法分析語義分析目標代碼生成前端后端中間代碼優(yōu)化中間代碼生成1第一頁，共二十九頁。第六章語法制導(dǎo)翻譯6.1中間代碼的形式6.2語法制導(dǎo)翻譯的概述6.3自底向上的制導(dǎo)翻譯2第二頁，共二十九頁。

何謂中間代碼：

（Intermediatecode/Intermediaterepresentation/Intermediatelanguage）

可以使編譯程序的結(jié)構(gòu)清晰、簡單、明確。源程序的一種內(nèi)部表示，不依賴目標機的結(jié)構(gòu)，易于機械生成目標代碼的中間表示。

為什么要此階段及使用原則主要優(yōu)點是可移植(與具體目標程序無關(guān))，且易于目標代碼優(yōu)化原則：１、形式比較簡單，容易翻譯成相應(yīng)的目標機器代碼。２、能充分反映源程序的特點。

中間代碼的幾種形式逆波蘭、四元式、三元式、樹型

6.1中間代碼(源程序的中間形式)3第三頁，共二十九頁。6.1.1逆波蘭記號（后綴式）將運算對象寫在前面，把運算符號寫在后面表達式逆波蘭式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=4第四頁，共二十九頁。后綴式的計算機處理后綴式的最大優(yōu)點是易于計算機處理處理過程： 從左到右掃描后綴式，每碰到運算對象就推進棧；碰到運算符就從棧頂彈出相應(yīng)目數(shù)的運算對象施加運算，并把結(jié)果推進棧。最后的結(jié)果留在棧頂。

bt1dct1t2t1t3t1=-bt2=c*dt3=t1+t2例：表達式－b＋c*d的后綴式b@cd*+的計值過程5第五頁，共二十九頁。逆波蘭表示法的擴充 逆波蘭表示法很容易擴充到表達式以外的范圍 例如：語句逆波蘭表示備注a:=b+cabc+:=:=看作二目運算符GOTOLLjmpjmp看成一目運算符，表示GOTOIfEthenS1elseS2ES1S2￥把￥看成三目運算符，表示if–then–else6第六頁，共二十九頁。逆波蘭示例例：把下述產(chǎn)生式定義的算術(shù)表達式映射到后綴波蘭表示：EE+TETTTFTFF(E)FaE=ET+E=TT=TFT=FF=EF=a產(chǎn)生式 翻譯成分7第七頁，共二十九頁。確定輸入a+aa的輸出：(E,E)(E+T,ET+)

(T+T,TT+)

(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)8第八頁，共二十九頁。6.1.2三元式和樹形表示格式：

(算符,第一運算對象,第二運算對象)如：

a=b*c+b*d

(1) (*,b,c)

(2) (*,b,d)

(3) (+,(1),(2))

(4) (=,(3),a)=a+**bcbd9第九頁，共二十九頁。6.1.3四元式由于三元式中的結(jié)果是用它的編號表示的，當在三元式進行優(yōu)化后，就要用一定的時間重新安排三元式的編號，很費時間。為了防止優(yōu)化后的重新編址，在三元式基礎(chǔ)上增加了一個存放結(jié)果的單元，這就形成了四元式子，是一種最常用的形式。格式：

(算符,第一運算對象,第二運算對象,結(jié)果)如：

a=b*c+b*d

(1) (*,b,c,t1)

(2) (*,b,d,t2)

(3) (+,t1,t2,t3)

(4) (=,t3,-,a)10第十頁，共二十九頁。四元式的特點類似于三地址指令四元式雖然比三元式多了一結(jié)果的引用，但有利于優(yōu)化和代碼生成為了便于書寫四元式也可以寫成如下形式：<結(jié)果>:=<運算對象1><運算符><運算對象2>則表達式a+(-b*c+d)*e的四元式為：(1)t1:=-b(2)t2:=t1*c(3)t3=t2+d(4)t4=t3*e(5)t5=a+t411第十一頁，共二十九頁。同樣要將算法語言翻譯成相應(yīng)的四元式，也要將四元式擴充到其他運算符，如(jmp,_,L)表示無條件轉(zhuǎn)向第L條四元式。12第十二頁，共二十九頁。6.1.4匯編代碼匯編語言是依賴于機器的低級程序設(shè)計語言，它是面向具體的計算機系統(tǒng)或相應(yīng)的計算機系列的，它和三元式相比有以下優(yōu)點：（1）能方便地翻譯成目標機器指令。（2）不必直接計算轉(zhuǎn)移地址。（3）可以使用各種數(shù)據(jù)表示法。13第十三頁，共二十九頁。6.2語法制導(dǎo)翻譯的概述(如何把源程序翻譯成相應(yīng)的中間代碼)基本思想： 在語法分析過程中，隨著分析的步步進展，每當使用一條產(chǎn)生式進行推導(dǎo)（對于自上而下分析）或歸約（對于自下而上分析），就執(zhí)行該產(chǎn)生式所對應(yīng)的語義動作，完成相應(yīng)的翻譯工作。

語法制導(dǎo)翻譯就是把語言的一些屬性附加到代表語言結(jié)構(gòu)的文法符號上，這些屬性值是由附加到文法產(chǎn)生式的“語義規(guī)則”中計算的，也就是為每個產(chǎn)生式配備翻譯子程序，即語義子程序。語法制導(dǎo)翻譯法不論對自上而下分析或自下而上分析都適用14第十四頁，共二十九頁。

翻譯的任務(wù)：語法結(jié)構(gòu)的靜態(tài)語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標代碼。

使用的方法:稱作語法制導(dǎo)翻譯。

基本思想（簡言之）:根據(jù)翻譯的需要設(shè)置文法符號的屬性(這些屬性代表與文法符號相關(guān)的信息)，以描述語法結(jié)構(gòu)的語義。例如，一個變量的屬性有類型，層次，存儲地址等。表達式的屬性有類型，值等。屬性值的計算和產(chǎn)生式相聯(lián)系。隨著語法分析的進行，執(zhí)行屬性值的計算，完成語義分析和翻譯的任務(wù)。15第十五頁，共二十九頁。屬性一般分為兩類：綜合屬性和繼承屬性。簡單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。屬性加工加工的過程即是語義處理的過程，對于文法的每一個產(chǎn)生式都配備了一組屬性的計算規(guī)則，則稱為語義規(guī)則。16第十六頁，共二十九頁。一個屬性文法它包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語法規(guī)則附在文法的每個產(chǎn)生式上。在一個語法制導(dǎo)定義中，A→P都有與之相關(guān)聯(lián)的一套語義規(guī)則，規(guī)則形式為b：=f（c1，c2，…，ck），f是一個函數(shù)，而且

1．b是A的一個綜合屬性并且c1，c2，…，ck是中的符號的屬性，或者2．b是中的符號的一個繼承屬性并且c1，c2，…，ck是A或中的任何文法符號的屬性。

在兩種情況下，都說

屬性b依賴于屬性c1，c2，…，ck。語法制導(dǎo)定義的形式17第十七頁，共二十九頁。要特別強調(diào)的是：

（1）終結(jié)符只有綜合屬性，它由詞法分析器提供；

（2）非終結(jié)符既可以有綜合屬性也可以有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。

一般來講，對出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個計算規(guī)則，屬性計算規(guī)則中只能使用相應(yīng)產(chǎn)生式的文法符號的屬性，這有利于產(chǎn)生式范圍內(nèi)“封裝”屬性的依賴性。然而，出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生式的屬性計算規(guī)則進行計算，它們由其它產(chǎn)生式的屬性規(guī)則計算,由屬性計算器的參數(shù)提供。18第十八頁，共二十九頁。語義規(guī)則所描述的工作可以包括屬性計算、靜態(tài)語義檢查、符號表操作、代碼生成等。語義規(guī)則可能產(chǎn)生副作用（如產(chǎn)生代碼），也可能不是變元的嚴格函數(shù)（如某個規(guī)則給出可用的下一個數(shù)據(jù)單元的地址）。這樣的語義規(guī)則通常寫成過程調(diào)用，或過程段。

綜合屬性：在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性值確定。因此，通常使用自底向上的方法在每一個結(jié)點處使用語義規(guī)則計算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S—屬性文法。繼承屬性：在語法樹中，一個結(jié)點的繼承屬性由此結(jié)點的父結(jié)點和/或兄弟結(jié)點的某些屬性確定。用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。19第十九頁，共二十九頁。例6.1臺式計算器程序的語法制導(dǎo)定義（表6.1)產(chǎn)生式語義規(guī)則S’Eprint(Eval)EE1+TEval:=E1val+TvalETEval:=TvalTT1*FTval:=T1val*FvalTFTval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexval每個文法符號和一個屬性值val聯(lián)系，屬性值的設(shè)置和語法結(jié)構(gòu)的語義以及翻譯程序的需要有關(guān)。例如：把左例中的類型擴充到int和real。20第二十頁，共二十九頁。綜合屬性

S-屬性定義唯獨只使用綜合屬性的語法制導(dǎo)定義。結(jié)點屬性值的計算正好和自底向上分析建立分析樹結(jié)點同步進行。

例6.2輸入：3*5+4n21第二十一頁，共二十九頁。digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln例6.2輸入：3*5+4nLEnEE1+TETTT1*FTFF(E)Fdigit22第二十二頁，共二十九頁。

◆綜合屬性值的計算方法對于s-屬性定義通常使用自底向上的分析方法在建立每一個結(jié)點處綜合屬性值使用語義規(guī)則來計算即在用哪個產(chǎn)生式進行歸約后，就執(zhí)行那個產(chǎn)生式的s-屬性定義計算屬性的值，從葉結(jié)點到根結(jié)點進行計算。23第二十三頁，共二十九頁。繼承屬性繼承屬性值是由此結(jié)點的父結(jié)點和／或兄弟結(jié)點的某些屬性值來決定的。例變量說明的類型定義inta,b,c24第二十四頁，共二十九頁。表6.2帶有繼承屬性L.in的語法制導(dǎo)定義

產(chǎn)生式語義規(guī)則DTLLin:=TtypeTintTtype:=integerTrealTtype:=realLL1,idL1

in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)25第二十五頁，共二十九頁。TLLid3Lid2Did1real,,1entry2entry3entry4typein56in78in910圖6.526第二十六頁，共二十九頁。語法制導(dǎo)翻譯的實現(xiàn)途徑以自下而上（LR分析）的語法制導(dǎo)翻譯來說明將LR分析器能力擴大，增加在歸約后調(diào)用語義規(guī)則的功能增加語義棧，語義值放到與符號棧同步操作的語義棧中，多項語義值可設(shè)多個語義棧，棧結(jié)構(gòu)為：狀態(tài)棧符號棧語義棧SmXmXm.val………S1X1X1.valS0#-27第二十七頁，共二十九頁。例簡單算術(shù)表達式求值的屬性文法L→E {print(E.val)}E→E1+T {