第8章語(yǔ)法制導(dǎo)翻譯和中間代碼生成經(jīng)過(guò)詞法分析、語(yǔ)法分析后，源程序在靜態(tài)結(jié)構(gòu)上的正確性得到了保證，編譯程序接著要對(duì)源程序進(jìn)行靜態(tài)語(yǔ)義檢查和翻譯。

語(yǔ)義檢查：類(lèi)型檢查、控制流檢查、一致性檢查等。翻譯：源程序→中間代碼1本章主要內(nèi)容1.屬性文法2.語(yǔ)法制導(dǎo)翻譯概念3.中間代碼的幾種形式4.幾個(gè)語(yǔ)句的翻譯：如賦值語(yǔ)句、條件語(yǔ)句等。2語(yǔ)法制導(dǎo)翻譯的引例E→E+T{print”1”}E→T{print”2”}T→T*F{print”3”}T→F{print”4”}F→(E)

{print”5”}F→i{print”6”}在文法的每個(gè)產(chǎn)生式后配了一個(gè)有{}括起來(lái)的語(yǔ)義子程序。3對(duì)(i+i)*i的翻譯

不難證明該符號(hào)串是文法的合法句子。按照這個(gè)句子向文法開(kāi)始符號(hào)E的歸約次序，且每當(dāng)歸約時(shí)調(diào)用該句柄的產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序，便可得到相應(yīng)的數(shù)字串：64264154632。這個(gè)例子表明：輸入源程序?yàn)?i+i)*i，輸出為數(shù)字串。這是一種變換，而變換的規(guī)則是每當(dāng)歸約時(shí)調(diào)用相應(yīng)的語(yǔ)義子程序。無(wú)疑這個(gè)例子是翻譯的一個(gè)十分簡(jiǎn)單的模型。4翻譯要解決的問(wèn)題1.翻譯成什么樣的代碼？2.什么時(shí)候?qū)崿F(xiàn)這種變換(翻譯)？3.如何實(shí)現(xiàn)這種翻譯？5翻譯成什么樣的代碼按照相應(yīng)語(yǔ)義規(guī)則產(chǎn)生一種介于源語(yǔ)言與目標(biāo)代碼之間的一種代碼(中間代碼)，它不依賴于機(jī)器但又便于產(chǎn)生依賴于機(jī)器的目標(biāo)代碼。中間代碼可用多種方式表示，常見(jiàn)的有：逆波蘭表示法、樹(shù)形表示法、三元式、四元式等。6什么時(shí)候?qū)崿F(xiàn)這種變換(翻譯)直觀來(lái)說(shuō)，就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序(語(yǔ)義子程序)，并且在語(yǔ)法分析的同時(shí)執(zhí)行這些子程序。具體來(lái)說(shuō)，就是一邊分析，一邊翻譯，語(yǔ)法分析完成，翻譯也就完成了。語(yǔ)法制導(dǎo)翻譯法對(duì)自上而下分析或自下而上分析都適用。語(yǔ)法制導(dǎo)翻譯方法是比較接近于形式化的翻譯方法。7如何實(shí)現(xiàn)這種翻譯至此不難明白，語(yǔ)法制導(dǎo)翻譯的關(guān)鍵是為每個(gè)產(chǎn)生式寫(xiě)相應(yīng)的語(yǔ)義子程序。例子中的print產(chǎn)生式序號(hào)這種語(yǔ)義子程序是為了輸出數(shù)字串而寫(xiě)的語(yǔ)義子程序。所以一個(gè)語(yǔ)義子程序描述了一個(gè)產(chǎn)生式對(duì)應(yīng)的翻譯工作。這些工作有：改變編譯程序某些變量的值、查填各種符號(hào)表、發(fā)現(xiàn)并報(bào)告源程序錯(cuò)誤、產(chǎn)生中間代碼。8語(yǔ)義子程序的一般形式語(yǔ)義子程序?qū)懺谠摦a(chǎn)生式后面的花括號(hào)內(nèi)：(1)X

…{語(yǔ)義子程序1}(2)Y

…{語(yǔ)義子程序2}(3)A

XY{語(yǔ)義子程序3}9屬性文法與語(yǔ)法制導(dǎo)翻譯的關(guān)系對(duì)于某個(gè)壓縮了的文法，當(dāng)把每個(gè)文法符號(hào)和一組屬性相關(guān)聯(lián)，并把產(chǎn)生式附加以語(yǔ)義規(guī)則的時(shí)候，就得到屬性文法。語(yǔ)法制導(dǎo)的翻譯過(guò)程：由于屬性文法的規(guī)則和產(chǎn)生式是一一對(duì)應(yīng)的關(guān)系。所以，由屬性文法確定的語(yǔ)義分析可以在語(yǔ)法分析的過(guò)程中進(jìn)行。這個(gè)過(guò)程成為語(yǔ)法制導(dǎo)的翻譯。10屬性文法屬性文法是一個(gè)三元組:A=(G,V,F),其中G:是一個(gè)上下文無(wú)關(guān)文法。V:屬性的有窮集,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號(hào)相關(guān)信息，如它的類(lèi)型、值、代碼序列、符號(hào)表內(nèi)容等等.屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。11屬性文法F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱為語(yǔ)義規(guī)則)。斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。12

屬性文法的例子語(yǔ)義規(guī)則

LEE

E1+TETT

T1*FT

FF(E)F

digitPrint(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ǎn)單算術(shù)表達(dá)式求值的語(yǔ)義描述13設(shè)表達(dá)式為3＊5+4，則語(yǔ)義動(dòng)作打印數(shù)值19.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ù)14中間代碼的形式1.逆波蘭式2.三元式、間接三元式和樹(shù)形表示3.四元式15表達(dá)式的表示方法1.中綴表達(dá)式(一般表達(dá)式)：運(yùn)算符放在運(yùn)算量之間。A+BA*B2.前綴表達(dá)式(波蘭表達(dá)式)：運(yùn)算符放在運(yùn)算量前面。+AB*AB3.后綴表達(dá)式(逆波蘭表達(dá)式)：運(yùn)算符放在運(yùn)算量后面。AB+AB*16上述三種方法的比較

三種方法的共同點(diǎn)：1.運(yùn)算量個(gè)數(shù)不變，順序也不變。2.運(yùn)算符個(gè)數(shù)不變。逆波蘭式的優(yōu)點(diǎn)：1.是一個(gè)無(wú)括號(hào)表達(dá)式。2.逆波蘭式的運(yùn)算符出現(xiàn)的順序就是原表達(dá)式的運(yùn)算順序，因而計(jì)算方便。17舉例1.(a*b+c)*d+b*(a+d*c)

ab*c+d*badc*+*+

2.

賦值語(yǔ)句的后綴式

A：=B+C

ABC+：=

18三元式組成:算符OP，第一運(yùn)算量ARG1，第二運(yùn)算量ARG2

如：a:=b*c+b*d的三元式為：(1)(*,b,c)(2)(*,b,d)(3)(+,(1),(2))(4)(:=,a,(3))注意：三元式出現(xiàn)的順序與原表達(dá)式計(jì)算順序一致。19間接三元式

用一張間接碼表輔以三元式表的辦法來(lái)表示中間代碼。例：X:=(A+B)*CY:=D↑(A+B)

三元式表間接碼表(1)(+,A,B)(1)(2)(*,(1),C)(2)(3)(:=,X,(2))(3)(4)(↑,D,(1))(1)(5)(:=,Y,(4))(4)

(5)20間接三元式的優(yōu)點(diǎn)1.間接碼表是一張指示器表，它將按運(yùn)算的先后順序列出有關(guān)三元式在三元式表中的位置。所以，當(dāng)有相同三元式出現(xiàn)時(shí)，無(wú)需反復(fù)填進(jìn)三元式表中。2.當(dāng)調(diào)整運(yùn)算順序時(shí)，只需重新安排間接碼表即可。無(wú)需改動(dòng)三元式表。如Y:=D↑(A+B)X:=(A+B)*C間接碼表：(1)(4)(5)(1)(2)(3)21樹(shù)形表示表達(dá)式的樹(shù)形表示：1.簡(jiǎn)單變量或常數(shù)的樹(shù)就是該變量或常數(shù)自身。2.如果表達(dá)式e1和e2的樹(shù)分別為T(mén)1和T2，那么e1+e2，e1*e2，-e1的樹(shù)分別為：+*-T1T2T1T2T1樹(shù)形表示是三元式的翻版。22四元式組成:OP，ARG1，ARG2，RESULT如：a:=b*c+b*d的四元式為：

(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,_,a)更易理解的形式t1:=b*ct2:=b*dt3:=t1+t2a:=t323四元式

1.四元式對(duì)中間結(jié)果的引用必須通過(guò)給定的名字，而三元式是通過(guò)產(chǎn)生中間結(jié)果的三元式編號(hào)。四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的。2.四元式出現(xiàn)順序與原表達(dá)式計(jì)算順序一致。(同三元式)24簡(jiǎn)單賦值語(yǔ)句的翻譯文法：S→i:=E

E→E+E|E*E|-E|(E)|id四元式形式

:

result:=arg1op

arg2語(yǔ)義屬性：,E.place

函數(shù)：lookup();

過(guò)程：emit(t:=arg1oparg2);

newtemp;(op,arg1,arg2,result)或25(2)E

E1+E2

{E.place:=newtemp;

emit(E.place“:=”E1.place“+”E2.place)}(3)E

-E1

{E.place:=newtemp;

emit(E.place“:=”“uminus”E1.place)}(4)E

(E1)

{E.place:=E1.place}(5)E

id{E.place:=newtemp;

P:=lookup();

ifP

nilthenE.place:=P

elseerror}

(1)S

id:=E

{P:=lookup

()

;

ifP

nilthenemit(P“:=”E.place)

elseerror}26翻譯a:=-b+c*da:=－bＥ11Ｅ1＋cＥ21＊dＥ22Ｅ2ＥＳt1:=uminusbt2:=c*dt3:=t1+t2a:=t327類(lèi)型轉(zhuǎn)換如：X:=Y+I*J，X,Y為實(shí)型，I,J為整型，則相應(yīng)的四元式序列應(yīng)為：(*i,I,J,T1)(itr,T1,_,T2)(+r,Y,T2,T3)(:=,T3,_,X)28布爾表達(dá)式的翻譯布爾表達(dá)式在程序語(yǔ)言中有兩個(gè)基本作用。1.邏輯運(yùn)算，計(jì)算邏輯值。2.控制語(yǔ)句(如if-then或while-do語(yǔ)句)的條件式。29布爾表達(dá)式

布爾表達(dá)式是由布爾算符(and,or,not)施于布爾變量或關(guān)系表達(dá)式而成。其中關(guān)系表達(dá)式的形式為E1ropE2，E1和E2都是算術(shù)表達(dá)式，rop是關(guān)系符，如≤、＜、＝、≥、＞、≠等。布爾表達(dá)式的運(yùn)算順序：算術(shù)運(yùn)算→關(guān)系運(yùn)算→布爾運(yùn)算(┐、∧、∨；∧、∨服從左結(jié)合)布爾表達(dá)式文法：E→E∧E|E∨E|┒E|(E)|idropid|id30布爾表達(dá)式的邏輯計(jì)算1.按布爾式的運(yùn)算順序(用1代表true，用0代表false)，則1or(not0and0)or0的計(jì)算過(guò)程為：1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=131例子1.aorbandnotc(1)t1:=notc(2)t2:=bandt1(3)t3:=aort22.A∨B∧C=D?

(=,C,D,T1)(∧,B,T1,T2)(∨,A,T2,T3)322.采取優(yōu)化措施，只計(jì)算部分表達(dá)式。如AorB，如果A為1，B就無(wú)需計(jì)算；如AandB，如果A為0，則B就無(wú)需計(jì)算。

A∨B→ifAthentrueelseBA∧B→ifAthenBelsefalse

┐A→ifAthenfalseelsetrue

這種翻譯法涉及到如何翻譯if-then-else的問(wèn)題，將在下面具體討論。33

ifEthenS1elseS2,其中E為布爾式E的代碼序列S1的代碼序列S2的代碼序列真出口假出口控制語(yǔ)句中布爾表達(dá)式的翻譯34E.falseE的代碼

E.trueE.true:S1的代碼gotooutE.false:S2的代碼out:35作為條件轉(zhuǎn)移的E的翻譯僅把E翻譯成僅含條件真轉(zhuǎn)和無(wú)條件轉(zhuǎn)的四元式。

(jnz,A,_,p):

若A為真，轉(zhuǎn)向第p個(gè)四元式(jθ,A,B,p):

若AθB為真，轉(zhuǎn)向第p個(gè)四元式(j,_,_,p):

無(wú)條件轉(zhuǎn)向第p個(gè)四元式36

ifA∨B<DthenS1elseS2(1)(jnz,A,_,5)

真出口(2)(j,_,_,3)(3)(j<,B,D,5)(4)(j,_,_,p+1)

假出口(5)(關(guān)于S1的四元式序列)…………(p)(j,_,_,q)(p+1)(關(guān)于S2的四元式序列)…………(q)例子不是最優(yōu)翻譯37ifa<borc<dande>fthenS1elseS2(1)ifa<bgoto(7)

轉(zhuǎn)移至E.true，即S1的四元式(2)goto(3)(3)ifc<dgoto(5)(4)goto(p+1)

轉(zhuǎn)移至E.false，即S2的四元式(5)ife>fgoto(7)

轉(zhuǎn)移至E.true(6)goto(p+1)

轉(zhuǎn)移至E.false(7)(關(guān)于S1的四元式)E.true…………(p)goto(q)(p+1)(關(guān)于S2的四元式)E.false…………(q)38控制語(yǔ)句中的回填技術(shù)

上例中的一些轉(zhuǎn)移地址并不能不產(chǎn)生這些四元式的同時(shí)得知。也就是說(shuō)，一個(gè)布爾式的真假出口往往不能在產(chǎn)生四元式的同時(shí)就確定。因此，要回填這些地址。39拉鏈為了記錄需回填地址的四元式，采用“拉鏈”的方法。把需回填E.true的四元式拉成一鏈，把需回填E.false的四元式拉成一鏈，分別稱做“真”鏈和“假”鏈。40拉鏈的方式(10)…gotoE.true…(20)…gotoE.true…(30)…gotoE.true則鏈成(10)…goto(0)…(20)…goto(10)…(30)…goto(20)把地址(30)稱作“真”鏈鏈?zhǔn)祝?為鏈尾標(biāo)志，即地址(10)為“真”鏈鏈尾。41Z:=ifA＞Cthenx+yelsex-y+0.5100(j>,A,C,102)

真出口101(j,_,_,105)

假出口102(+,x,y,T1)103(:=,T1,_,Z)104(j,_,_,108)105(-,x,y,T2)106(+,T2,0.5,T3)107(:=,T3,_,Z)108這條四元式必須寫(xiě)42IF語(yǔ)句的翻譯過(guò)程翻譯過(guò)程大致如下：(1)翻譯E，獲得一組四元式；(2)掃描E的真出口，回填；假出口尚不知；(3)翻譯S(1)；(4)遇到else，S(1)結(jié)束，生成一條無(wú)條件轉(zhuǎn)移四元式，但出口不明；(5)翻譯S(2)，結(jié)束。43While語(yǔ)句翻譯成四元式

WhileEdoS1,E為布爾式。首先檢查E的值，如果為真，則執(zhí)行S語(yǔ)句(可以是一個(gè)單獨(dú)的語(yǔ)句或一復(fù)合語(yǔ)句)。當(dāng)一開(kāi)始E就為假時(shí)，S語(yǔ)句根本不執(zhí)行。每次執(zhí)行S語(yǔ)句后，再次檢查布爾表達(dá)式E，如果仍為真，繼續(xù)執(zhí)行S語(yǔ)句，否則循環(huán)結(jié)束，執(zhí)行while語(yǔ)句后的下一語(yǔ)句。

E的代碼序列S1的代碼序列44例子

WhileA<BdoifC<DthenX:=Y+Z100(j<,A,B,102)

真出口101(j,_,_,107)

假出口102(j<,C,D,104)103(j,_,_,100)104(+,Y,Z,T)105(:=,T,_,X)106(j,_,_,100)10745WHILE語(yǔ)句的翻譯過(guò)程翻譯過(guò)程大致如下：(1)翻譯E，待填E的真鏈、假鏈；(2)掃描do后，回填E的真鏈；(3)翻譯S(1)語(yǔ)句稱代碼段；(4)無(wú)條件轉(zhuǎn)移到E代碼段的第一條四元式，若S(1)有語(yǔ)句鏈，也應(yīng)轉(zhuǎn)到E代碼段的第一條四元式。46Whilea＞0∨b＜0do

Begin

X：＝X＋1；

ifa≥0thena：＝a－1elseb：＝b＋1

End；

(1)(j＞，a，0，5)

(11)(j，－，－，1)(2)(j，－，－，3)(12)(＋，b，1,T3)(3)(j＜，b，0，5)

(13)(:＝，T3，－，b)(4)(j，－，－，15)(14)(j，－，－，1)(5)(＋，X，1，T1)(15)(6)(：＝，T1,－,X)(7)(j≥，a，0，9)(8)(j，－，－，12)(9)(－，a，1，T2)(10)(:＝,T2,－,a)47WhileA<C∧B<Ddo

ifA≥0thenC:=C-1else

whileB≤1doB:=B+1100(j<,A,C,102)108(j,_,_,100)101(j,_,_,115)109(j≤,B,1,111)102(j<,B,D,104)110(j,_,_,100)103(j,_,_,101)111(+,B,1,T2)104(j≥,A,0,106)112(:=,T2,_,B)105(j,_,_,109)113(j,_,_,109)106(-,C,1,T1)114(j,_,_,100)107(:=,T1,_,C)11548數(shù)組的翻譯在簡(jiǎn)單賦值語(yǔ)句的翻譯中，只涉及到了對(duì)簡(jiǎn)單變量的引用和賦值。下面討論數(shù)組元素在簡(jiǎn)單賦值語(yǔ)句的翻譯。49數(shù)組元素地址分配A:array[1:2,1:3]

(1)按行存放(2)按列存放A[1.1]A[1,2]A[1,3]A[2,1]A[2,2]A[2,3]A[1.1]A[2,1]A[1,2]A[2,2]A[1,3]A[2,3](1)(2)50二維數(shù)組元素地址的計(jì)算

數(shù)組元素的地址計(jì)算和數(shù)組的存儲(chǔ)方式密切相關(guān)。以按行存放為例，討論如何計(jì)算數(shù)組元素的地址。設(shè)A是一個(gè)10×20的二維數(shù)組，各維的下限為1，每個(gè)元素占用1個(gè)單元，a為數(shù)組的首地址，則數(shù)組元素A[i，j]的地址為：

a+(i–1)×20+(