第7章 語法制導(dǎo)的語義計(jì)算

第八章語法制導(dǎo)翻譯法指出：按照編譯程序的邏輯工作過程，語法分析后，接下來就要進(jìn)行語義分析了，語義分析后，再生成中間代碼。實(shí)際應(yīng)用中，往往在語法分析的同時(shí)，進(jìn)行語義分析并生成中間代碼，這就是語法制導(dǎo)翻譯法。語法制導(dǎo)翻譯過程中，需要借助于屬性文法進(jìn)行語義描述和語義處理。本章主要內(nèi)容屬性內(nèi)容語法制導(dǎo)翻譯的基本思想中間代碼的形式屬性文法對(duì)于某個(gè)壓縮了的文法，當(dāng)把每個(gè)文法符號(hào)和一組屬性相關(guān)聯(lián)，并把產(chǎn)生式附加以語義規(guī)則的時(shí)候，就得到屬性文法。語法制導(dǎo)的翻譯過程：由于屬性文法的規(guī)則和產(chǎn)生式是一一對(duì)應(yīng)的關(guān)系。所以，由屬性文法確定的語義分析可以在語法分析的過程中進(jìn)行。這個(gè)過程成為語法制導(dǎo)的翻譯。屬性文法屬性文法(attributegrammar):A=(G,V,F),其中G:一個(gè)CFG,屬性文法的基礎(chǔ)。V:有窮的屬性集每個(gè)屬性與一個(gè)文法符號(hào)相關(guān)聯(lián)這些屬性代表與文法符號(hào)相關(guān)的語義信息如類型、地址、值、代碼、符號(hào)表內(nèi)容等等屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞屬性加工的過程即是語義處理的過程屬性加工與語法分析同時(shí)進(jìn)行屬性的表示：標(biāo)始符（或數(shù)），寫在相應(yīng)文法的下邊點(diǎn)記法：E.Val,E.Place,E.Type…F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱為語義規(guī)則).

斷言或語義規(guī)則與一個(gè)產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性.繼承屬性和綜合屬性兩類屬性：綜合屬性(SynthesizedAttribute)：歸約型屬性用于“自下而上”傳遞信息繼承屬性(InheritedAttribute)：推導(dǎo)型屬性用于“自上而下”傳遞信息。屬性的計(jì)算：AX1X2…XnA的綜合屬性,計(jì)算S(A):=f(I(X1),…,I(Xn))Xj的繼承屬性,計(jì)算T(Xj):=f(I(A),...I(Xn))文法符號(hào)屬性的說明：非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號(hào)沒有繼承屬性.終結(jié)符只有綜合屬性.通常規(guī)定：文法符號(hào)的綜合屬性與繼承屬性無交。綜合屬性的例子非終結(jié)符E、T及F都有一個(gè)綜合屬性val,符號(hào)digit有一個(gè)綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式L→E對(duì)應(yīng)的語義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個(gè)過程，我們可認(rèn)為這條規(guī)則定義了L的一個(gè)虛屬性。某些非終結(jié)符加上標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)語義規(guī)則

L→EE→E1+TE→TT→T1*FT→FF→(E)F→digitPrint(E.val)

E.val:=E1.val+T.val

E.val:=T.val

T.val:=T1.valF.val

T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn)生式綜合屬性的自下而上定值.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è)表達(dá)式為3＊5+4，則語義動(dòng)作打印數(shù)值19繼承屬性的例子

繼承屬性L.in產(chǎn)生式語義規(guī)則DTL

Tint

Treal

LL1,idLidL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)繼承屬性的自上而下定值

DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.Realid1,id2,id3，，L－屬性文法適合于指導(dǎo)自上而下的分析。一個(gè)屬性文法稱為L(zhǎng)－屬性文法，如果對(duì)于每個(gè)產(chǎn)生式A→X1X2…Xn，滿足：（1）Xj（1≤j≤n）的繼承屬性僅依賴于下述屬性值中的一種：A的繼承屬性；產(chǎn)生式右部位于Xj左邊的符號(hào)X1，X2，…，Xj-1的屬性。（2）A的綜合屬性，僅依賴于下述屬性值中的一種：A的繼承屬性；產(chǎn)生式右部符號(hào)Xj

（除自身外）的任意屬性。L－屬性文法的自上而下計(jì)算L－屬性文法的翻譯器通常可借助于LL分析器實(shí)現(xiàn)。在L－屬性文法的基礎(chǔ)上，LL分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。需要對(duì)LL分析器增加語義棧,以保存與棧中文法符號(hào)有關(guān)的繼承屬性值。每當(dāng)進(jìn)行推導(dǎo)時(shí)，新的屬性值就由棧中正在推導(dǎo)的產(chǎn)生式左邊符號(hào)的屬性值來計(jì)算。S－屬性文法適用于指導(dǎo)自下而上的分析一個(gè)屬性文法稱為S－屬性文法,當(dāng)且僅當(dāng)滿足如下條件：（1）所有非終結(jié)符的屬性是綜合屬性；（2）同一產(chǎn)生式中相同符號(hào)的各綜合屬性之間無相互依賴關(guān)系；（3）如果q是某個(gè)產(chǎn)生式中文法符號(hào)V的繼承屬性，則屬性q的值僅僅依賴于該產(chǎn)生式右部位于V左邊的符號(hào)的屬性。S－屬性文法的自下而上計(jì)算S－屬性文法的翻譯器通常可借助于LR分析器實(shí)現(xiàn)。在S－屬性文法的基礎(chǔ)上，LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。需要對(duì)LR分析器增加語義棧,以保存與棧中文法符號(hào)有關(guān)的綜合屬性值。每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值來計(jì)算。LR分析器改造為翻譯器LR分析器增加語義棧

產(chǎn)生式語義規(guī)則０）Ｌ→Ｅｐｒｉｎｔ（Ｅ.ｖａｌ）１）Ｅ→Ｅ1＋ＴＥ.ｖａｌ∶＝Ｅ1.ｖａｌ＋Ｔ.ｖａｌ２）Ｅ→ＴＥ.ｖａｌ∶＝Ｔ.ｖａl３）Ｔ→Ｔ1*ＦＴ.ｖａｌ∶＝Ｔ1.ｖａｌ×Ｆ.ｖａｌ４）Ｔ→FＴ.ｖａｌ∶＝F.ｖａｌ５）Ｆ→（Ｅ）Ｆ.ｖａｌ∶＝Ｅ.ｖａｌ６）Ｆ→ｄiｇiｔＦ.ｖａｌ:＝ｄｉｇｉｔ.ｌｅｘｖａｌLR分析器改造為翻譯器２＋３*５的分析和計(jì)值過程步驟動(dòng)作狀態(tài)棧語義棧(值棧)符號(hào)棧余留輸入串１）０－＃２＋3*５＃２）０５－－＃２＋3*５＃３）ｒ６０３－２＃Ｆ＋３*５＃４）ｒ４０２－２＃Ｔ＋３*５＃５）ｒ２０１－２＃Ｅ＋３*５＃６）０１６－２－＃Ｅ＋３*５＃７）０１６５－２－－＃Ｅ＋３*５＃８）ｒ６０１６３－２－３＃Ｅ＋Ｆ*５＃９）ｒ４０１６９－２－３＃Ｅ＋Ｔ*５＃１０）０１６９７－２－３－＃Ｅ＋Ｔ*５＃１１）０１６９７５－２－３－－＃Ｅ＋Ｔ*５＃１２）ｒ６０１６９７（１０）－２－３－５＃Ｅ＋Ｔ*Ｆ#１３）ｒ３０１６９－２－（１５）＃Ｅ＋Ｔ＃１４）ｒ１０１－（１７）＃Ｅ＃１５）接受語法制導(dǎo)翻譯的基本思想為每條產(chǎn)生式配上一個(gè)翻譯子程序（稱為語義動(dòng)作或語義子程序）；語義動(dòng)作的工作指明符號(hào)串的意義；按照這種意義規(guī)定了對(duì)應(yīng)的動(dòng)作：查添各種表格改變變量之值診察與報(bào)告源程序錯(cuò)誤產(chǎn)生中間代碼…在語法分析的同時(shí)，當(dāng)一個(gè)產(chǎn)生式獲得匹配（對(duì)于自上而下分析）或用于歸約（對(duì)于自下而上分析）時(shí)，就執(zhí)行相應(yīng)產(chǎn)生式的語義子程序。語法制導(dǎo)翻譯法的一般原理直觀地說，語法制導(dǎo)翻譯法（SDTS）組成如下：一個(gè)源語言；一個(gè)目標(biāo)語言；一組翻譯規(guī)則為文法中的產(chǎn)生式添加上語義動(dòng)作作用：將任何源語言符號(hào)串翻譯成對(duì)應(yīng)的目標(biāo)語言串。語法制導(dǎo)翻譯法的形式化定義SDTS是一個(gè)CFG,是一個(gè)五元組

T=(VT,VN,,R,S),其中(1)VT是有窮的輸入字母表（包含源語言中的符號(hào)）；(2)VN是有窮的非終結(jié)符集；(3)是有窮的輸出字母表（包含出現(xiàn)在輸出串中的符號(hào)）；(4)R是形如Aw,y的規(guī)則的有窮集合；R中規(guī)則形式：Aw,yA∈VN,,w∈(VT∪VN)*,y∈(VN

∪)*且y中那組非終結(jié)符是w中那組非終結(jié)符的置換。W：規(guī)則的源成分y：規(guī)則的翻譯成分(5)S∈VN，是文法的開始符號(hào)?；A(chǔ)源文法和基礎(chǔ)目標(biāo)文法SDTS的基礎(chǔ)源文法(輸入文法)一個(gè)CFG：(VT,VN,P,S),其中P={Aw|Aw,y屬于R)SDTS的基礎(chǔ)目標(biāo)文法(輸出文法)一個(gè)CFG：(VN,,P’,S),其中P’={Ay|Aw,y屬于R)一個(gè)例子EE+TETTTFTFF(E)FaE=ET+E=TT=TFT=FF=EF=a產(chǎn)生式

翻譯規(guī)則翻譯模式翻譯模式可遞歸定義為：①(S,S)是一個(gè)翻譯模式，且這兩個(gè)S是相關(guān)的②(aAb,a’Ab’)是一個(gè)翻譯模式，且兩個(gè)A是相關(guān)的；此外，若A->g,g’是R中的一條規(guī)則，則(agb,a‘g’b’)也是一個(gè)翻譯模式。規(guī)則中g(shù)和g’的非終結(jié)符之間的相關(guān)性也必須帶進(jìn)這種翻譯模式中。顯然，翻譯模式是一個(gè)形如(u,v)的串對(duì)，其中u是基礎(chǔ)源文法的一個(gè)句型,u∈(VT∪VN)*,v是與u對(duì)應(yīng)的翻譯，v∈(VN

∪)*翻譯模式的變換若(aAb,a’Ab’)是一個(gè)翻譯模式，A->g,g’是R中的一條規(guī)則，則(aAb,a’Ab’)=〉(agb,a‘g’b’)是一個(gè)翻譯模式到另一個(gè)翻譯模式的變換。與推導(dǎo)過程類似。SDTS定義的翻譯一個(gè)SDTS定義的翻譯是如下對(duì)偶集：{(x,y)|(S,S)=*>(x,y),x∈VT*,y∈Δ*}比較：CFG中語言的定義。翻譯的例子a+a*a的翻譯過程：

(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+)樹變換語法制導(dǎo)的翻譯過程可以看成是將輸入文法Gi中的推導(dǎo)樹變換成輸出文法G0中的推導(dǎo)樹。給了輸入句子x，可以按如下方式得到x的一個(gè)翻譯：先為推導(dǎo)x構(gòu)造一棵推導(dǎo)樹，再變換該樹到輸出文法中的一棵樹，然后取此輸出樹的邊緣作為x的一個(gè)翻譯。具體變換過程如下：從中剪去終結(jié)符號(hào)結(jié)點(diǎn)；根據(jù)適當(dāng)?shù)姆g規(guī)則，重排每個(gè)中間結(jié)點(diǎn)的孩子；添加對(duì)應(yīng)于輸出符號(hào)集Δ中的終結(jié)符結(jié)點(diǎn)。中間代碼中間代碼（Intermediatecode）：源程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，易于機(jī)械生成目標(biāo)代碼的中間表示。中間代碼的幾種形式逆波蘭四元式三元式間接三元式樹逆波蘭表示方法表達(dá)式的一種表示形式運(yùn)算符直接跟在運(yùn)算量后面又稱為后綴(postfix)表示法定義：設(shè)E是表達(dá)式，那么如果E是變量或者常量，E的逆波蘭表示為EE1OPE2==>E1’E2’OP，其中E1’,E2’

為E1,E2的逆波蘭表示。(E)==>E’,其中E’為E的逆波蘭表示。后綴表達(dá)式的計(jì)值自左向右掃描表達(dá)式，每遇到運(yùn)算量就把它推進(jìn)棧，每遇到k目算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并把運(yùn)算結(jié)果來代替這k個(gè)項(xiàng)逆波蘭表示的例子A+bab+A+b*cabc*+(a+b)*cab+c*A+B*(C-D)+E/(C-D)^NABCD-*+ECD–N^/+a+b*c/(d+e)abc*de+/+逆波蘭表示方法的擴(kuò)充賦值語句：V:=e V’e’:=例子：t=(a+b)*c/(d-e)tab+c*de-/=轉(zhuǎn)向語句：goto<Label><Label>jump條件語句：

If<e>then<x>else<y><e><L1>jumpf<x><L2>jump<y>數(shù)組說明：arrayA[l1..u1,….,ln..un]L1u1…lnunAADEC下標(biāo)變量：A[<e1>…<en>]<e1>…<en>ASUBSeL1jumpfxL2jumpyL1L2四元式一般形式：<op><ARG1><ARG2><RESULT>例子：a+b*c* b c t1+ a t1 t2單目運(yùn)算符的處理：<ARG2>為空。一般來講，四元式的運(yùn)算符都有對(duì)應(yīng)的機(jī)器指令，或者對(duì)應(yīng)的子程序，因此從四元式生成指令代碼是容易的。四元式之間的聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的，便于進(jìn)行代碼優(yōu)化。四元式表示的例子A+B*(C-D)+E/(C-D)^N（1）(-CDT1)（2）(*BT1T2)（3）(+AT2T3)（4）(-CDT4)（5）(^T4NT5)（6）(/ET5T6)（7）(+T3T6T7)三元式如果我們不明顯給出四元式的結(jié)果部分，而是用四元式的編號(hào)來表示結(jié)果，那么我們可以得到三元式。形式如下：<op><ARG1><ARG12> 例子：a+b*c=>①*bc②+a①三元式的出現(xiàn)順序與表達(dá)式的計(jì)值順序一致。和四元式的比較：無須臨時(shí)變量；占用存儲(chǔ)空間少；相互引用太多，使得難以進(jìn)行代碼優(yōu)化。 三元式表示的例子A+B*(C-D)+E/(C-D)^N(1)(-CD)(2)(*B(1))(3)(+A(2))(4)(-CD)(5)(^(4)N)(6)(/E(5))(7)(+(3)(6))間接三元式間接三元式：為了便于代碼優(yōu)化處理，用一張間接碼表輔以三元式表的辦法來表示中間代碼。間接碼表是一張指示器表，它將按運(yùn)算的先后順序列出有關(guān)三元式在三元式表中的位置。當(dāng)在代碼優(yōu)化過程中需要調(diào)整運(yùn)算順序時(shí)，只需重新安排間接碼表即可。例子：X:=(A+B)*CY:=D↑(A+B)間接三元式表示的例子A+B*(C-D)+E/(C-D)^N間接三元式序列間接碼表(-CD)(1)(*B(1))(2)(+A(2))(3)(4)(^(1)N)(1)(/E(4))(4)(6)(+(3)(5))(5)(6)樹形表示（抽象語法樹AST）采用樹形表示作為一種中間代碼形式，有助于代碼的產(chǎn)生和優(yōu)化。樹形表示的定義：簡(jiǎn)單變量或常數(shù)的樹就是該變量或常數(shù)自身；如果表示e1和e2的樹為T1和T2，那么，e1+e2,e1*e2,-e1的樹分別是：

顯然，樹形表示是三元式表示的翻版。抽象語法樹（AbstractSyntaxTree）在語法樹中去掉那些對(duì)翻譯不必要的信息，獲得更有效的源程序中間表示AST可以拓廣，用來表示數(shù)組元素、過程調(diào)用、控制結(jié)構(gòu)、說明等。+e1e2-e1*e1e2簡(jiǎn)單算術(shù)表達(dá)式和賦值句的翻譯文法：A→i:=EE→E+E|E*E|-E|(E)|I引入的語義屬性：E.PLACE與非終結(jié)符E相聯(lián)系，表示存放E值的變量名在符號(hào)表的入口或整數(shù)碼（對(duì)臨時(shí)變量）語義過程：NEWTEMP:函數(shù)過程。每次調(diào)用，回送一個(gè)代表新臨時(shí)變量名的整數(shù)碼作為函數(shù)值。ENTRY(i):函數(shù)過程。對(duì)i所代表標(biāo)識(shí)符查找符號(hào)表以獲知它在符號(hào)表中位置（入口）。GEN(OP,ARG1,ARG2,RESULT):語義過程。把四元式(OP,ARG1,ARG2,RESULT)填入四元式表中。產(chǎn)生式的語義描述(1)A→i:=E{GEN(:=,E.PLACE,_,ENTRY(i))}(2)E→E1+E2{E.PLACE:=NEWTEMP;GEN(+,E1.PLACE,E2.PLACE,E.PLACE)}(3)E→E1*E2{E.PLACE:=NEWTEMP;GEN(*,E1.PLACE,E2.PLACE,E.PLACE)}(4)E→-E1{E.PLACE:=NEWTEMP;GEN(@,E1.PLACE,_,E.PLACE)}(5)E→(E1)

{E.PLACE:=NEWTEMP}(6)E→i

{E.PLACE:=ENTRY(i)}布爾表達(dá)式的翻譯布爾表達(dá)式基本作用：用作計(jì)算邏輯值；用作控制條件。布爾表達(dá)式文法：

E→E∧E|E∨E|┒E|(E)|idropid|id結(jié)合性和優(yōu)先級(jí)：rop┒∧∨；∧∨左結(jié)合。布爾表達(dá)式的翻譯計(jì)算布爾表達(dá)式的值：逐步計(jì)算；利用布爾表達(dá)式的性質(zhì)采取優(yōu)化措