語法制導(dǎo)翻譯市公開課獲獎?wù)n件省名師優(yōu)質(zhì)課賽課一等獎?wù)n件

語法制導(dǎo)翻譯靜態(tài)語義分析這一步才真正開始考慮程序設(shè)計語言實(shí)際意義靜態(tài)語義分析作用：檢驗出源程序中靜態(tài)語義錯誤而且將語義正確語句翻譯成中間代碼該過程中通常使用方法是語法制導(dǎo)翻譯1/251第四章語法制導(dǎo)翻譯生成中間代碼語法制導(dǎo)翻譯是處理語義基本方法，它以語法分析為基礎(chǔ)，在語法分析得到語言結(jié)構(gòu)結(jié)果時，對附著于此結(jié)構(gòu)語義進(jìn)行處理，如計算表示式值、生成中間代碼等。主要內(nèi)容包含：語法制導(dǎo)翻譯基本概念中間代碼介紹符號表介紹經(jīng)典申明語句與可執(zhí)行語句翻譯2/2524.1語法制導(dǎo)翻譯介紹語法與語義語法與語義關(guān)系語法是指語言結(jié)構(gòu)、即語言“樣子”；語義是指附著于語言結(jié)構(gòu)上實(shí)際含意，即語言“意義”。語義不能離開語法獨(dú)立存在；語義遠(yuǎn)比語法復(fù)雜；同一語言結(jié)構(gòu)可包含各種含意，不一樣語言結(jié)構(gòu)可表示相同含意；語法與語義之間沒有明確界限。[例1]貓吃老鼠與老鼠吃貓，曬被子與曬太陽(語法正確不一定語義正確)3/2534.1語法制導(dǎo)翻譯介紹語義分析兩個作用檢驗是否結(jié)構(gòu)正確句子所表示意思也正當(dāng)；執(zhí)行要求語義動作，如：表示式求值符號表填寫中間代碼生成等語義分析方法 語法制導(dǎo)翻譯基本思想：將語言結(jié)構(gòu)語義以屬性形式賦予代表此結(jié)構(gòu)文法符號，而屬性計算以語義規(guī)則形式賦予由文法符號組成產(chǎn)生式，在語法分析推導(dǎo)或者規(guī)約每一步驟中，經(jīng)過語義規(guī)則實(shí)現(xiàn)對屬性計算。4/2544.1語法制導(dǎo)翻譯介紹屬性與語義規(guī)則語法制導(dǎo)翻譯基本思想為每個產(chǎn)生式配上語義規(guī)則而且在適當(dāng)時候執(zhí)行這些規(guī)則詳細(xì)方法：將文法符號所代表語言結(jié)構(gòu)意思，用附著于該文法符號屬性表示；用語義規(guī)則要求產(chǎn)生式所代表語言結(jié)構(gòu)之間關(guān)系（即屬性之間關(guān)系），即用語義規(guī)則實(shí)現(xiàn)屬性計算。語義規(guī)則執(zhí)行：在語法分析適當(dāng)初刻（如推導(dǎo)或歸約）執(zhí)行附著在對應(yīng)產(chǎn)生式上語義規(guī)則，以實(shí)現(xiàn)對語言結(jié)構(gòu)語義處理，如計算、查填符號表、生成中間代碼、公布犯錯信息等。5/2554.1語法制導(dǎo)翻譯介紹屬性表示.attr如：E.val（值），E.type（類型），E.code（代碼序列），

E.place（存放空間）

屬性在程序設(shè)計中詳細(xì)表示能夠依據(jù)實(shí)際情況采取適當(dāng)

數(shù)據(jù)結(jié)構(gòu)或者程序代碼來實(shí)現(xiàn)語義規(guī)則定義 定義4.1

對于產(chǎn)生式A→α，其中α是由文法符號X1X2...Xn組成序列，它語義規(guī)則能夠表示為(4.1)所表示關(guān)于屬性函數(shù)：

b:=f(c1,c2,...,ck) (4.1)6/2564.1語法制導(dǎo)翻譯介紹A→α語義規(guī)則b:=f(c1,c2,...,ck) (4.1)語義規(guī)則中屬性存在下述性質(zhì)與關(guān)系。若b是A屬性，c1,c2,...,ck是α漢字法符號屬性，或者A其它屬性，則稱b是A綜合屬性。若b是α中某文法符號Xi屬性，c1,c2,...,ck是A屬性，或者是α中其它文法符號屬性，則稱b是Xi繼承屬性。稱(4.1)中屬性b依賴于屬性c1,c2,...,ck。若語義規(guī)則形式以下述(4.2)，則可將其想像為產(chǎn)生式左部文法符號A一個虛擬屬性。屬性之間依賴關(guān)系，在虛擬屬性上依然存在。

f(c1,c2,...,ck) (4.2)

(4.1)中屬性之間依賴關(guān)系，實(shí)質(zhì)上反應(yīng)了屬性計算先后次序，即全部屬性ci被計算之后才能計算屬性b。7/2574.1語法制導(dǎo)翻譯介紹語義規(guī)則兩種形式語法制導(dǎo)定義 用抽象屬性和運(yùn)算符號表示語義規(guī)則翻譯方案 用詳細(xì)屬性和運(yùn)算表示語義規(guī)則

語義規(guī)則也被習(xí)慣上稱為語義動作。二者作用等價，語法制導(dǎo)定義適合用于設(shè)計階段，翻譯方案適用于實(shí)現(xiàn)階段。8/2584.1語法制導(dǎo)翻譯介紹[例4.1]將中綴形式算術(shù)表示式轉(zhuǎn)換為后綴表示。其語法制導(dǎo)定義和翻譯方案可分別表示以下。其中print(E.post)是L虛擬屬性，即L.p:=print(E.post)。翻譯方案中.lexval表示詞法分析返回記號num值。產(chǎn)生式語法制導(dǎo)定義翻譯方案L→Eprint(E.post)print_post(post);E→E1+E2E.post:=E1.post||E2.post||'+';post(k):='+';k:=k+1;E→numE.post:=num.lexval;post(k):=lexval;k:=k+1;9/2594.1語法制導(dǎo)翻譯介紹產(chǎn)生式語法制導(dǎo)定義翻譯方案L→Eprint(E.post)print_post(post);E→E1+E2E.post:=E1.post||E2.post||'+';post(k):='+';k:=k+1;E→numE.post:=num.lexval;post(k):=lexval;k:=k+1;語法制導(dǎo)定義只考慮“做什么”.post表示表示式后綴式||表示后綴式連接屬性和運(yùn)算詳細(xì)實(shí)現(xiàn)細(xì)節(jié)不在語法制導(dǎo)定義考慮范圍10/25104.1語法制導(dǎo)翻譯介紹產(chǎn)生式語法制導(dǎo)定義翻譯方案L→Eprint(E.post)print_post(post);E→E1+E2E.post:=E1.post||E2.post||'+';post(k):='+';k:=k+1;E→numE.post:=num.lexval;post(k):=lexval;k:=k+1;翻譯方案不但考慮做什么還要考慮怎樣做例子中用數(shù)組post存放表示式后綴形式由num歸約得到子表示式E后綴式就是它本身歸約由兩個子表示式和加號組成表示式時，兩個子表示式以分析過，已經(jīng)分別按從左到右次序放在post中，此時僅需將+添加到post中11/25114.1語法制導(dǎo)翻譯介紹從某種意義上來說，語法制導(dǎo)定義類似于算法，而翻譯方案類似于程序因為翻譯方案與詳細(xì)實(shí)現(xiàn)親密相關(guān)，所以不一樣實(shí)現(xiàn)方法能夠到達(dá)相同目標(biāo)（不唯一）產(chǎn)生式語法制導(dǎo)定義翻譯方案1翻譯方案2L→Eprint(E.post)print_post(post);E→E1+E2E.post:=E1.post||E2.post||'+';post(k):='+';k:=k+1;print(+);E→numE.post:=num.lexval;post(k):=lexval;k:=k+1;print(lexval);另一個翻譯方案：無需存放中間過程，直接在分析過程中輸出表示式后綴形式。原因：自下而上分析過程是對表示式分析樹一次后續(xù)遍歷，而遍歷次序與表示式后綴表示恰好一致。12/25124.1語法制導(dǎo)翻譯介紹翻譯方案中需要考慮問題：采取什么樣語法分析方法，不一樣分析方法對語義處理次序不一樣為屬性分配存放空間考慮計算次序翻譯方案1，自下而上計算，LR分析。以3+5+8為例，歸約時翻譯。產(chǎn)生式翻譯方案1L→Eprint_post(post);E→E1+E2post(k):='+';k:=k+1;E→numpost(k):=lexval;k:=k+1;post:(35+8+)13/25134.1語法制導(dǎo)翻譯介紹屬性作為分析樹注釋 將屬性附著在分析樹對應(yīng)文法符號上，形成注釋分析樹。[例4.2]3+5+8分析樹和注釋分析樹：產(chǎn)生式語法制導(dǎo)定義翻譯方案2L→Eprint(E.post)E→E1+E2E.post:=E1.post||E2.post||'+';print(+);E→numE.post:=num.lexval;print(lexval);.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+))14/25144.1語法制導(dǎo)翻譯介紹注釋分析樹上看繼承屬性與綜合屬性

繼承屬性是自上而下計算綜合屬性是自下而上計算提醒：除非尤其提醒，本章討論語法制導(dǎo)翻譯是綜合屬性。.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+))15/25154.1語法制導(dǎo)翻譯介紹LR分析翻譯方案設(shè)計LR分析中語法制導(dǎo)翻譯實(shí)質(zhì)上是對LR語法分析擴(kuò)充：擴(kuò)充LR分析器功效：當(dāng)執(zhí)行歸約產(chǎn)生式動作時，也執(zhí)行產(chǎn)生式對應(yīng)語義動作。因為是歸約時執(zhí)行語義動作，限制語義動作僅能放在產(chǎn)生式右部最右邊；擴(kuò)充分析棧：增加一個與分析棧并列語義棧，用于存放分析棧漢字法符號所對應(yīng)屬性值。比如：E→E1+E2val[top]:=val[top]+val[top-2];

對于表示式5+3

當(dāng)歸約為左部E時 同時也得到了值816/2516[例4.3]3+5*8語法制導(dǎo)翻譯。產(chǎn)生式L→EE→E1+E2E→E1*E2E→n分析棧 語義棧 輸入 語義動作# # 3+5*8# shift#n #3 +5*8# E→n,val[top]:=lexval#E #3 +5*8# shift#E+ #3? 5*8# shift#E+n #3?5 *8# E→n,val[top]:=lexval#E+E #3?5 *8# shift#E+E* #3?5? 8# shift#E+E*n#3?5?8 # E→n,val[top]:=lexval#E+E*E#3?5?8 # E→E1*E2,val[top]:=val[top]*val[top-2]#E+E #3?40 # E→E1+E2,val[top]:=val[top]+val[top-2]#E #43 # acc翻譯方案print(val[top]);val[top]:=val[top]+val[top-2];val[top]:=val[top]*val[top-2];val[top]:=lexval;語法制導(dǎo)定義print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val*E2.val;E.val:=n.lexval;17/25174.1語法制導(dǎo)翻譯介紹遞歸下降分析翻譯方案設(shè)計遞歸下降方法是用程序?qū)崿F(xiàn)對非終止符展開和對終止符匹配。翻譯方案設(shè)計需要處理兩個問題：怎樣在遞歸下降子程序中嵌入語義動作？ 產(chǎn)生式右部任何位置；怎樣為文法符號屬性設(shè)計存放空間？ 函數(shù)返回值、參數(shù)、變量等。18/25184.2

中間代碼介紹編譯器各階段完整輸出，均能夠被認(rèn)為是源程序某種中間表示。本章討論是中間代碼生成器輸出中間表示，稱之為中間代碼。中間代碼實(shí)際上應(yīng)起一個編譯器前端與后端分水嶺作用。要求中間代碼含有以下特征，方便于編譯器開發(fā)移植和代碼優(yōu)化：便于語法制導(dǎo)翻譯；既與機(jī)器指令結(jié)構(gòu)相近，又與詳細(xì)機(jī)器無關(guān)。中間代碼主要形式：樹、后綴式、三地址碼等。19/25194.2

中間代碼介紹后綴式操作數(shù)在前，操作符緊隨其后，無需用括號限制運(yùn)算優(yōu)先級和結(jié)合性。算法4.1后綴式計算采取下述過程進(jìn)行計算，最終止果留在棧中。

x:=first_token; whilenotend_of_exp

loop ifxinoperators then pushx; --操作數(shù)進(jìn)棧

else pop(operators); --算符，彈出操作數(shù)

push(evaluate); --計算，將結(jié)果進(jìn)棧

endif; next(x); endloop;20/25204.2

中間代碼介紹loop ifxinoperators then pushx; --操作數(shù)進(jìn)棧

else pop(operators); --算符，彈出操作數(shù)

push(evaluate); --計算，將結(jié)果進(jìn)棧

endif; next(x);endloop;算術(shù)表示式3+5+8后綴式為35+8+。# 35+8+# push(3)#3 5+8+# push(5)#35 +8+# pop(3和5)，push(3+5)#8 8+# push(8)#88 +# pop(8和8)，push(8+8)#16 #21/25214.2

中間代碼介紹后綴式并不局限于二元運(yùn)算表示式，能夠推廣到任何語句，恪守操作數(shù)在前，操作符緊跟其后標(biāo)準(zhǔn)即可。對語句： ifethenxelsey后綴式能夠?qū)憺椋?exyif-then-else (1)此時e、x和y均需計算。實(shí)際上，依據(jù)條件e取值，x和y不用都計算：

ep1jezxp2jumpp1:yp2: (2)其中：p1和p2分別是標(biāo)號；

p1jez表示e結(jié)果為0（假）則轉(zhuǎn)向p1；

p2jump表示無條件轉(zhuǎn)向p2。與(1)比較，(2)中if-then-else被分解，首先計算e，依據(jù)e結(jié)果是否為真，決定計算x還是計算y。22/25224.