第五章 語法制導(dǎo)翻譯與中間代碼生成

第5章語法制導(dǎo)翻譯和中間代碼生成屬性文法：AttributedGrammar語法制導(dǎo)翻譯：Syntax-DirectedTranslation目前在實際應(yīng)用中比較流行的主要的語義描述和語義處理的方法。5.1概述屬性文法語法制導(dǎo)翻譯法的基本思想中間代碼形式各種常見語法結(jié)構(gòu)的LR語法制導(dǎo)翻譯簡單算術(shù)表達(dá)式的翻譯賦值語句的翻譯說明語句的翻譯控制語句的翻譯循環(huán)語句的翻譯含數(shù)組元素的賦值語句的翻譯綜合屬性的遞歸下降語法制導(dǎo)翻譯5.2屬性文法接近形式化的語義描述方法屬性文法(AttributedGrammar)的定義：在上下文無關(guān)文法的基礎(chǔ)上,為每個文法符號配備若干相關(guān)的“屬性”，對每個產(chǎn)生式都配備一組屬性的計算規(guī)則（語義規(guī)則）(斷言)。其中，語法與語義的關(guān)系語義信息作為終結(jié)符和非終結(jié)符的屬性；屬性計算和傳遞的過程即是語義處理的過程。如：文法符號E、T配屬性E.type,E.place,E.val,T.val等等產(chǎn)生式E→T,配屬性的計算規(guī)則E.val=T.val語義規(guī)則所描述的工作包括：屬性計算靜態(tài)語義檢查符號表操作代碼生成寫成程序段屬性分類：綜合屬性SynthesizedAttribute：自下而上傳遞信息；繼承屬性InheritedAttribute：自上而下傳遞信息。例類型檢查的屬性文法語義規(guī)則：在一個屬性文法A中，對應(yīng)每個產(chǎn)生式A都有一組語義規(guī)則(SemanticRules),每條語義規(guī)則的形式為:b=f(c1,c2,…,ck)其中，f是一個函數(shù),屬性b與ci之間,或者(1)b是A的一個綜合屬性且c1,c2,…,ck是產(chǎn)生式右邊文法符號的屬性;或者(2)b是產(chǎn)生式右邊某文法符號的繼承屬性且c1,c2,…,ck是A或產(chǎn)生式右邊任何符號的屬性。注意：(1)終結(jié)符a只有綜合屬性,由詞法分析器提供;(2)非終結(jié)符A既可有綜合屬性,也可有繼承屬性,文法開始符號S的所有繼承屬性作為屬性計算前的初始值。產(chǎn)生式左邊符號的繼承屬性和產(chǎn)生式右邊符號的綜合屬性，不由所給的產(chǎn)生式的屬性計算規(guī)則來計算，而是由其他產(chǎn)生式的語義規(guī)則來計算。例：產(chǎn)生式ABC語義規(guī)則:C.d(繼承屬性)=B.c(綜合屬性)+1A.b(綜合屬性)=A.a(繼承屬性)+B.c(綜合屬性)A.a(繼承屬性)和B.c(綜合屬性)在其他地方計算。例1:簡單計算器的設(shè)計編制算術(shù)表達(dá)式的文法引入屬性表示語義信息將值val作為表達(dá)式E、項T和因子F的綜合屬性用語義規(guī)則描述表達(dá)式的求值屬性文法（語法制導(dǎo)定義）產(chǎn)生式語義規(guī)則L→Eprint(E.val)E→E1+TE.val=E1.val+T.valE→TE.val=T.valT→T1*FT.val=T1.val*F.valT→FT.val=F.valF→(E)F.val=E.valF→digit

F.val=digit.attrattr是單詞

digit的綜合屬性,由詞法分析器提供綜合屬性：在語法樹中,結(jié)點的綜合屬性的值是從其子結(jié)點的屬性值計算出來的；如：E.val通常使用自底向上的方法,按照語義規(guī)則來計算各結(jié)點的綜合屬性值僅包括綜合屬性的屬性文法對于所有Ａ→Ｘ1

Ｘ2…Ｘn，Ａ的屬性計算僅用Ｘ1…Ｘn

的屬性如：算術(shù)表達(dá)式求值的屬性文法Ｓ-屬性文法定義：例：3*5+4的語法樹與綜合屬性的計算例2：類型說明語句的文法設(shè)計方法編寫說明語句的文法將類型信息作為類型描述T的綜合屬性type和變量表L的繼承屬性in。目的分析說明語句D，為變量指定類型屬性文法定義(語法制導(dǎo)定義)語義規(guī)則L.in=T.typeT.type=‘integer’T.type=‘real’L1.in=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)entry單詞

id的屬性(符號表入口)addtype在符號表中為變量填入類型信息產(chǎn)生式D→TLT→intT→realL→L1,idL→id繼承屬性：在語法樹中,繼承屬性是從其兄弟結(jié)點和父結(jié)點的屬性值計算出來的如：L.in需要探討計算次序addtypeaddtypeaddtype例：realid1,id2,id3的分析樹和屬性計算5.3語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯法(SyntaxDirectedTranslation)：由源程序的語法結(jié)構(gòu)所驅(qū)動的分析方法。接近形式化的語義分析方法。在某些情況下，可以在語法分析的同時完成語義規(guī)則的計算，即一遍掃描，而無須明顯地構(gòu)造語法樹或構(gòu)造屬性之間的依賴關(guān)系。基本思想：每個產(chǎn)生式都附加一個語義動作或語義子程序，當(dāng)運(yùn)用該產(chǎn)生式推導(dǎo)或歸約時，執(zhí)行相應(yīng)的語義動作。自上而下語法制導(dǎo)翻譯、自下而上語法制導(dǎo)翻譯1、為文法的每個規(guī)則設(shè)計相應(yīng)的語義子程序。翻譯模式(Translationschemes)一種適合語法制導(dǎo)翻譯的描述形式;它給出了使用語義規(guī)則進(jìn)行計算的次序,可以把實現(xiàn)細(xì)節(jié)表示出來;其中的屬性和語義規(guī)則/動作,用{}括起來,插入到產(chǎn)生式右部的合適位置上。例簡單計算器的翻譯模式自下而上語法制導(dǎo)翻譯:翻譯模式(Translationschemes)把語義動作看成終結(jié)符號;翻譯模式就是在文法中加入動作符號,則可以應(yīng)用語法分析方法來處理,同時分析語法和語義。設(shè)計翻譯模式時，要注意保證動作引用的屬性在之前是有定義的。翻譯模式舉例建立翻譯模式一、只有綜合屬性時，情況最簡單。建立其翻譯模式的方法：為每一個語義規(guī)則建立一個包含賦值的動作，并且把這個動作放在相應(yīng)產(chǎn)生式右邊的末尾。例如：有產(chǎn)生式語義規(guī)則

T→T1*FT.val=T1.val*F.val

建立翻譯模式如T→T1*F{T.val=T1.val*F.val}二、既有綜合屬性又有繼承屬性此時要注意：(1)右邊符號的繼承屬性必須在這個符號以前的動作中計算出來;(2)一個動作不能引用該動作右邊的符號的綜合屬性;(3)左邊符號的綜合屬性的動作通?？梢苑旁诋a(chǎn)生式右邊的末尾。滿足這三個條件的翻譯模式可以在topdown或bottomup分析器中實現(xiàn)。1、為文法的每個規(guī)則設(shè)計相應(yīng)的語義子程序。2、為文法構(gòu)造LR分析表。例簡單計算器的自下而上語法制導(dǎo)翻譯

自下而上語法制導(dǎo)翻譯3、擴(kuò)充原LR語法分析棧，以便存放語義值。4、擴(kuò)充原LR語法分析總控程序，以便在完成語法分析的同時也完成語義分析。例用LR分析器實現(xiàn)簡單計算器產(chǎn)生式語義動作代碼L→Eprint(val[top])E→E1+E2val[ntop]=val[top-2]+val[top]E→E1*E2val[ntop]=val[top-2]*val[top]E→(E1)val[ntop]=val[top-1]E→digitval[top]=digit.attr3+5*4的LR分析過程每次歸約前,先執(zhí)行語義規(guī)則的相應(yīng)代碼。5.4中間語言源程序的中間表示方法:后綴式三地址代碼(三元式、四元式、間接三元式)抽象語法樹DAG圖5.4.1后綴式(逆波蘭式)后綴式表示法(逆波蘭表示法)：一種表示表達(dá)式的方法表達(dá)式E的后綴形式定義如下：(1)若E是一個常量或變量,則E的后綴式為E自身;(2)若E形如E1opE2,則E的后綴式為E1’E2’op;(3)若E形如(E1),則E1的后綴式為E的后綴式。后綴表示法不用使用括號只要知道每個算符的目數(shù)，對于后綴式，不論從哪一端進(jìn)行掃描，都能對它正確進(jìn)行唯一分解。把表達(dá)式翻譯成后綴式的語義規(guī)則描述產(chǎn)生式EE1opE2E(E1)Eid語義規(guī)則E.code=E1.code||E2.code||opE.code=E1.codeE.code=例：表達(dá)式a+b*(c+d/e)

后綴式：abcde/+*+1、賦值語句的逆波蘭表示:賦值語句：<左部>=<表達(dá)式>逆波蘭式：

<左部><表達(dá)式的逆波蘭式>=2、GOTO語句的逆波蘭式：轉(zhuǎn)向語句：GOTO<語句標(biāo)號>

逆波蘭式：<語句標(biāo)號>BL3、條件語句的逆波蘭表示:條件語句：if(e)S1elseS2逆波蘭式：<e的逆波蘭式><序號1>BF<S1的逆波蘭式><序號2>BR<序號1>:<S2的逆波蘭式><序號2>:<序號1>BF表示條件e為假時，轉(zhuǎn)向序號1<序號2>BR表示無條件轉(zhuǎn)向序號2。4、循環(huán)語句的逆波蘭表示:循環(huán)語句：FOR(i=m;i<=n;i++)SFOR語句展開為等價形式：i=m;10:ifi<=n{S;i=i+1;goto10}逆波蘭式：

im=<序號1:>in<=<序號2>BFS的逆波蘭式ii1+=序號1BR<序號2:>5.4.2圖表示法圖表示法包括DAG與抽象語法樹DAG(directedacyclicgraph)無循環(huán)有向圖每個子表達(dá)式一個結(jié)點，一個內(nèi)部結(jié)點代表一個操作符，它的子結(jié)點代表操作數(shù)；公共子表達(dá)式的結(jié)點具有多個父結(jié)點。DAG描述源程序的自然層次結(jié)構(gòu)，比抽象語法樹更緊湊。a=b*-c+b*-c的圖表示法a=+*b-c*b-c抽象語法樹a=+*b-cDAG后綴式與抽象語法樹的關(guān)系:后綴式是抽象語法樹的線性表示形式;后綴式是樹的結(jié)點的一個序列,每個結(jié)點都是在它的所有子結(jié)點之后立即出現(xiàn)。抽象語法樹的邊沒有顯式地出現(xiàn)在后綴式中，可以根據(jù)結(jié)點出現(xiàn)的次序和算符的目數(shù)還原出來。如上例的后綴式為abc-*bc-*+=5.4.3三地址代碼三地址代碼是由如下的一般形式的語句構(gòu)成的序列:x=yopzNote：其中每個語句的右邊只能有一個運(yùn)算符。三地址代碼可以看成是抽象語法樹或DAG的一種線性表示。三地址代碼示例(a=b*-c+b*-c)T1=-cT2=b*T1T3=-cT4=b*T3T5=T2+T4a=T5(a)抽象語法樹的三地址代碼T1=-cT2=b*T1T5=T2+T2a=T5(b)DAG的三地址代碼三地址代碼特點:1.三地址代碼的語句類似于匯編語言代碼。2.語句可以帶有符號標(biāo)號,并且存在各種控制流語句。3.三地址代碼可以存放在一個數(shù)組中。三地址代碼語句的具體實現(xiàn)：(記錄)1.四元式

(op、arg1、arg2、result)2.三元式(op、arg1、arg2)3.間接三元式三元式表+間接代碼表1.四元式T1=-cT2=b*T1T3=-cT4=b*T3T5=T2+T4a=T5a=b*-c+b*-c的三地址代碼：2.三元式aT5=(5)T5T4T2+(4)T4T3b*(3)T3c-(2)T2T1b*(1)T1c-(0)ResultArg2arg1Op(4)a=(5)(3)(1)+(4)(2)b*(3)c-(2)(0)b*(1)c-(0)Arg2arg1Op3.間接三元式T1=-cT2=b*T1T3=-cT4=b*T3T5=T2+T4a=T5a=b*-c+b*-c的三地址代碼實現(xiàn)：2.三元式(2)(3)(1)(0)(1)(0)1.四元式

(op、arg1、arg2、result)2.三元式(op、arg1、arg2)3.間接三元式三元式表+間接代碼表比較：2、3相對于1可以避免把臨時變量填入符號表，1、3更利于優(yōu)化。(1)x=yopz(2)x=opy(3)x=y(4)gotoL(5)ifEropEgotoL或ifEgotoL(6)paramx和callp,n以及returny(7)x=y[i]和x[i]=y常用的三地址代碼包括：5.5自下而上語法制導(dǎo)翻譯1、簡單算術(shù)表達(dá)式和賦值語句的翻譯2、布爾表達(dá)式的翻譯3、控制語句的翻譯4、循環(huán)語句的翻譯5、簡單說明語句的翻譯6、含數(shù)組元素的賦值語句的翻譯5.5.1簡單算術(shù)表達(dá)式和賦值語句的翻譯簡單算術(shù)表達(dá)式：僅含簡單變量，易于翻譯成四元式。分析文法特點、設(shè)置語義變量和語義函數(shù)。修改文法，構(gòu)造翻譯模式。實現(xiàn)LR分析。產(chǎn)生賦值語句三地址代碼的翻譯模式S→id=E E→E1+E2

E→E1*E2

E→－E1

E→(E1) E→id

{p=lookup(); if(p==null)error(); elseemit(p'='E.place);}{E.place=newtemp();emit(E.place'='E1.place'+'E2.place);}{E.place=newtemp();emit(E.place'='E1.place'*'E2.place);}{E.place=newtemp();emit(E.place′=′′uminus′E1.place;}{E.place=E1.place}{p=lookup();if(p!=null)E.place=p;elseerror();}產(chǎn)生賦值語句后綴式的翻譯模式？S→id=E E→E1+E2

E→E1*E2

E→－EE→(E1) E→id

5.5.2布爾表達(dá)式的翻譯◆布爾表達(dá)式:用布爾運(yùn)算符（and，or，not）作用到布爾變量或關(guān)系表達(dá)式上而組成。布爾運(yùn)算符、關(guān)系運(yùn)算符、算術(shù)運(yùn)算符◆考慮由如下文法生成的布爾表達(dá)式：

E→EorE|EandE|notE|(E)|idropid|id|true|false◆布爾表達(dá)式的作用：

1.用作計算邏輯值

2.用作控制流語句如if-then，if-then-else和 while-do等之中的條件表達(dá)式翻譯布爾表達(dá)式的方法：計算一個布爾表達(dá)式的值方法一：用數(shù)值表示真和假，從而對布爾表達(dá)式的求值可以象對算術(shù)表達(dá)式的求值那樣一步一步地來計算。方法二：通過程序的控制流，即用程序中控制轉(zhuǎn)移到達(dá)的位置來表示布爾表達(dá)式的值,可實施某種優(yōu)化措施。(例AorB)方法二用于翻譯控制流語句中的布爾表達(dá)式尤其方便。

數(shù)值表示法用1表示真，0表示假來實現(xiàn)布爾表達(dá)式的翻譯布爾表達(dá)式：aorbandnotc

翻譯成三地址代碼序列：

100：t1=notc101：t2=bandt1102：t3=aort1關(guān)系表達(dá)式：a<b等價于ifa<bthen1else0

翻譯成三地址代碼序列：a<b翻譯成三地址代碼序列：

100：ifa＜bgotol03101：t=0102：gotol04103:t=1104：關(guān)于布爾表達(dá)式的數(shù)值表示法的翻譯模式E→E1orE2 ｛E.place=newtemp();emit(E.place'='E1.place'or'E2.place)}E→E1andE2 ｛E.place=newtemp();emit(E.place'='E1.place'and'E2.place)}（接上頁）E→notE1 ｛E.place=newtemp();emit(E.place'=''not'E1.place)}E→id1ropid2{E.place=newtemp();emit('if'id1.placerop.opid2.place'goto'nextq+3);emit(E.place'=''0');emit('goto'nextq+2);emit(E.place'=''1')}E→id ｛E.place=id.place}E→true ｛E.place=newtemp();emit(E.place'=''1')}E→false ｛E.place=newtemp();emit(E.place'=''0')}例

a>borcande的翻譯2作為條件控制的布爾式的翻譯

條件語句ifEthenS1elseS2中有布爾式EE.codeS1.codeE.true:S2.codeE.false:gotoS.next...S.next:toE.truetoE.falseif-then-else語句的代碼結(jié)構(gòu)如上作為轉(zhuǎn)移條件的布爾式,可以翻譯為一串跳轉(zhuǎn)指令布爾式的控制流翻譯法：基本思想：如果E是aropb,則E的三地址代碼為:ifaropbgotoE.truecodegotoE.falsecode其它：若E是E1orE2？E1andE2？

notE1

？id?true?false?實現(xiàn)的方法:一遍掃描：先產(chǎn)生暫時沒有填寫目標(biāo)標(biāo)號的轉(zhuǎn)移指令。對于每一條這樣的指令作適當(dāng)?shù)挠涗?，一旦目?biāo)標(biāo)號被確定下來，再將它“回填”到相應(yīng)的指令中。例如，E是a>b,則E的三地址代碼為:(1)ifa>bgoto----(2)goto----E.trueE.false使用“回填”翻譯布爾表達(dá)式：布爾表達(dá)式文法：（1）E→E1orE2

（2）|E1andE2

（3）|notE1

（4）|(E1)

（5）|id1ropid2

（6）|true

（7）|false

（8）|id翻譯模式用到如下公共變量和函數(shù)：1．nextq:下一條四元式的地址（或標(biāo)號）。2．E.bcode：非終結(jié)符E的第一個四元式標(biāo)號。3．merge(p1，p2)：連接由指針p1和p2指向的兩個表并且返回一個指向連接后的表的指針。4．backpatch（p，i）：把i作為目標(biāo)標(biāo)號回填到p所指向的表中的每一個轉(zhuǎn)移指令中去。此處的“表”都是為“回填”所建的“鏈”使用一遍掃描的布爾表達(dá)式的翻譯模式EE1ORE2

EE1ANDE2

{backpatch(E1.false,E2.bcode);E.bcode=E1.bcode；E.true=merge(E1.true,E2.true);E.false=E2.false；}

{backpatch(E1.true,E2.bcode);E.bcode=E1.bcode；

E.true=E2.true;E.false=merge(E1.false,E2.false);}EnotE1{E.true=E1.false;E.false=E1.true；E.bcode=E1.bcode；

}E(E1){E.true=E1.true；E.false=E1.false；

E.bcode=E1.bcode；}Eid1ropid2

{E.true=nextq;E.bcode=nextq；

E.false=nextq+1;emit(′if′id1.placerop.opid2.place′goto—′);emit(′goto—′);}Etrue

{E.true=nextq;emit(′goto—′);}Efalse{E.false=nextq;emit(′goto—′);}Eid{E.true=nextq;E.false=nextq+1;E.bcode=nextq;emit(`if`id.place`goto----`)emit(′goto—′);}E.trueE.falseE.bcode都是綜合屬性考慮表達(dá)式AorB<D

依次分析，得到如下三地址代碼：

100：ifAgoto--101：goto--102：ifB＜Dgoto--103：goto--104：經(jīng)過回填得到：

100：ifAgoto--101：gotol02102：ifB＜Dgoto--103：goto--104：當(dāng)知道了條件為真時和條件為假時分別應(yīng)做哪些動作時就可以進(jìn)行余下的回填5.5.3控制語句的翻譯

控制流語句ifEthenS1ifEthenS1elseS2whileEdoS1L→L;SL→SS→AS→ifEthenS1S→ifEthenS1elseS2

S→whileEdoS1

文法：E.codeS1.codeE.true:...E.false:(a)if-thentoE.truetoE.false控制流語句的代碼結(jié)構(gòu)：

E.codeS1.codeE.true:S2.codeE.false:gotoS.next...S.next:toE.truetoE.false(b)if-then-elseE.codeS1.codeE.true:E.false:gotoS.begin...S.begin:toE.falsetoE.true(c)while-do改寫含控制語句的文法：L→L;SL→SS→AS→CS1C→ifEthenS→TPS2

TP→CS1elseS→WdS1Wd→WEdoW→whileS→ifEthenS1S→ifEthenS1elseS2

S→whileEdoS1改寫后文法的翻譯模式：S→CS1C→ifEthenS→TPS2

TP→CS1else{S.CHAIN=merge(C.CHAIN,S1.CHAIN)}{backpatch(E.true,nextq);C.CHAIN=E.false;}{S.CHAIN=merge(TP.CHAIN,S2.CHAIN)}{q=nextq;emit(goto--);backpatch(C.CHAIN,nextq);TP.CHAIN=merge(S1.CHAIN,q);}改寫后文法的翻譯模式：S→WdS1Wd→WEdoW→while{W.bcode=nextq;}{backpatch(E.true,nextq);Wd.CHAIN=E.false;Wd.bcode=W.bcode}{backpatch(S1.CHAIN,Wd.bcode);emit(gotoWd.bcode);S.CHAIN=Wd.CHAIN;}考慮語句whileAorB<Ddoifx>6thenx=x-1elsey=x+1

依次分析，經(jīng)過回填得到如下三地址代碼：100：ifAgoto104

101：goto102

102：ifB＜Dgoto104

103：goto----104：ifx>6goto106

105:goto109106:t1=x-1107:x=t1108:goto100109:t2=x+1110:y=t2111:goto100112:改寫后文法的翻譯模式：S→WdS1Wd→WEdoW→while{W.bcode=nextq;}{backpatch(E.true,nextq);Wd.CHAIN=E.false;Wd.bcode=W.bcode}{backpatch(S1.CHAIN,Wd.bcode);emit(gotoWd.bcode);S.CHAIN=Wd.CHAIN;}5.5.4循環(huán)語句的翻譯

循環(huán)語句：fori=E1stepE2untilE3doS1

i=E1S.next:iE3S1.codeE3.true:E3.false:i=i+E2gotoS.begin...S.begin:toE3.falsetoE3.true

代碼結(jié)構(gòu)1：5.5.4循環(huán)語句的翻譯

循環(huán)語句：fori=E1stepE2untilE3doS1

代碼結(jié)構(gòu)2：i=E1；S.next:if(iE3)S1.codeOVER:E3.false:gotoAGAIN...AGAIN:gotoOVER；i=i+E2；E3.true:改寫文法為：S→F3doS1F3→F2untilE3F2→F1stepE2F1→fori=E1改寫后文法的翻譯模式：{emit(lookup()=E1.place);F1.place=lookup();F1.chain=nextq;emit(goto----);F1.bcode=nextq;}{F2.bcode=F1.bcode;F2.place=F1.place;emit(F1.place=F1.place+E2.place);backpatch(F1.CHAIN,nextq);}S→F3doS1F3→F2untilE3F2→F1stepE2F1→fori=E1i=E1；S.next:if(iE3)S1.codeOVER:E3.false:gotoAGAIN...AGAIN:gotoOVER；i=i+E2；E3.true:改寫后文法的翻譯模式：{F3.bcode=F2.bcode;q=nextq;emit(ifF2.placeE3.placegotoq+2);F3.CHAIN=nextq);emit(goto---);}S→F3doS1F3→F2untilE3F2→F1stepE2F1→fori=E1i=E1；S.next:if(iE3)S1.codeOVER:E3.false:gotoAGAIN...AGAIN:gotoOVER；i=i+E2；E3.true:{emit(gotoF3.bcode);backpatch(S1.CHAIN,F3.bcode);S.CHAIN=F3.CHAIN;}5.5.5簡單說明語句的翻譯

簡單說明語句：inta,b,cfloatx,yD→TLT→intT→floatL→L1,idL→idAttr[top]=‘int’Attr[top]=‘float’addtype(id.entry,attr[top-3])addtype(id.entry,attr[top-1])5.5.5簡單說明語句的翻譯

簡單說明語句：inta,b,cfloatx,yD→intLD→floatLL→L1,idL→id文法改寫為：D→D1,idD→intidD→floatid改寫后文法的翻譯模式為：D→D1,idD→intidD→floatid{addtype(id.entry,‘int’);D.ATTR=‘int’;}{addtype(id.entry,‘float’);D.ATTR=‘float’;}{addtype(id.entry,D1.ATTR);D.ATTR=D1.ATTR;}5.5.6含數(shù)組元素的賦值語句的翻譯

數(shù)組：a[low1:u1,low2:u2,…,lown:un]數(shù)組元素的三地址代碼是：x=y[i]和x[i]=y

如何生成數(shù)組元素的三地址代碼？數(shù)組元素地址的計算公式:一維數(shù)組a[low1:u1]的下標(biāo)為i的元素的開始地址：求

a[i]的地址：

b1＋（i－low1

）*w=b1-low1*w+i*w

常量部分（可在編譯時計算出來）+變量部分其中，b1

是數(shù)組元素a[low1]的地址?！魧τ谝粋€二維數(shù)組，可以按行或按列存放若按行存放，則可用如下公式計算A[i1,i2]

的相對地址：

b1＋（（i1

一low1）*n2＋i2

一low2）*w）=

b1－（（low1*n2）＋low2）*w

＋(（i1*n2）＋i2)*w

令c=

（（low1*n2）＋low2）*w

則常量部分=a[low1,low2]-c.

◆計算元素A[i1,i2,...,ik]相對地址的推廣公式((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+b1-((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w

含有數(shù)組元素的賦值語句的文法：S→V=EV→i[elist]|ielist→elist,E|EE→E+E|(E)|V為方便地址計算，可將文法改寫為：S→V=EV→elist]|ielist→elist1,E|i[EE→E+E|(E)|V文法：（1）S→V＝E（2）V→i（3）V→Elist]（4）Elist→i[E（5）Elist→Elist，E（6）E→E＋E（7）E→（E）（8）E→V

訪問數(shù)組元素的翻譯模式◆計算元素A[i1,i2,...,ik]相對地址的推廣公式((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+b1-((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w

1．S→V＝E

｛ifV.off＝nullthenemit(V.place'＝'E.place)elseemit（V.place[V.off]=E.Place）}2．V→i{V.place=i.place;V.off=null;}◆相應(yīng)語義動作

若V是一個簡單的名字，將生成一般的賦值；若V為數(shù)組元素引用，則生成對V所指示地址的索引賦值。◆計算元素A[i1,i2,...,ik]相對地址的推廣公式((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+b1-((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w

3．V→Elist]

｛V.place=newtemp();emit（V.place'='Elist.array'－'c)(（…(low1*n2＋low2)*n3＋low3)…lowk-1)*nk

＋lowk

V.off=Elist.place;}

4．Elist→i[E

｛Elist.place=E.place;Elist.dim=1;Elist.array＝i.place}

◆計算元素A[i1,i2,...,ik]相對地址的推廣公式((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+b1-((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w

3．V→Elist]

｛V.place=newtemp();emit（V.place'='Elist.array'－'c)(（…(low1*n2＋low2)*n3＋low3)…lowk-1)*nk

＋lowk)*w

V.off=newtemp();emit(V.off'='Elist.place*w;}應(yīng)用遞歸公式掃描下一個下標(biāo)表達(dá)式

5．Elist→Elist1,E{t＝newtemp();m＝Elist1．dim＋1；

dm=limit(Elist1.array,m);emit(t=Elist1.place*dm)；

emit（t=t＋E.place）；

Elist.array＝Elist1．a(chǎn)rray;Elist.place=t;Elist.dim＝m｝◆計算元素A[i1,i2,...,ik]相對地址的推廣公式((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+b1-((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w

7．E→（E1）{E.place＝E1.place}使用索引來獲得地址V.place[V.off]的內(nèi)容：

8．E→V

｛ifV.off＝=nullthenE.place＝V.placeelse{E.place=newtemp();emit(E.place=V.place[V.off]);}}6．E→E1＋E2

｛E.place＝newtemp();emit（E.place'＝'E1.place'＋'E2.place）｝◆計算元素A[i1,i2,...,ik]相對地址的推廣公式((...((i1*n2+i2)*n3+i3)...)*nk+ik)*w+b1-((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w

例：有數(shù)組a[10,15]，每個元素的存儲寬度為4，數(shù)組第一個元素為a[0,0]，則a[y,z]=a[y,z]+1可翻譯成：三地址代碼序列：100：t1=y*16101：t1=t1＋z102：t2=t1*4◆計算元素a[i1,i2]相對地址的公式b1－（（low1*n2）＋low2）*w＋(（i1*n2）＋i2)*w103：t3=y*16104：t3=t3＋z105：t4=t3*4106：t5=b1[t4]107：t6=t5+1108：b1[t2]=t6例：有數(shù)組a[10,15]，每個元素的存儲寬度為1，數(shù)組第一個元素為a[1,1]，則x=a[y,z]可翻譯成：三地址代碼序列：100：t1=y*15101：t1=t1＋z102：t2=b-16103：t3=t2[t1]104：x=t3

注意：15、16都是編譯中引入的常量?！粲嬎阍豠[i1,i2]相對地址的公式b1－（（low1*n2）＋low2）*w＋(（i1*n2）＋i2)*wV.place=x；V.off=nullV.place=t2；V.off=t1；102:t2=A-CE.place=t3；103:t3=t2[t1]Elist.place=t1；Elist.dim=2；Elist.array=A100:t1=y*15；101:t1=t1+zS{104:x=t3}=x]例：x=a[y,z]的帶注釋的分析樹：Elist.place=y；Elist.dim=1Elist.array=A,V.place=z；V.off=nullE.place=za[zyV.place=y；V.off=nullE.place=y5.5.7過程和函數(shù)調(diào)用語句的翻譯returny過程和函數(shù)調(diào)用要傳遞參數(shù)、轉(zhuǎn)子程序：paramxcallp,n子程序的末尾要能正確返回：5.6遞歸下降語法制導(dǎo)翻譯將語義子程序嵌入到每個遞歸過程中，通過局部量和參數(shù)傳遞語義信息。方法:擴(kuò)充消除左遞歸的算法，在消除基本文法的左遞歸時同時考慮屬性。此法適合于帶綜合屬性的翻譯模式。如算術(shù)表達(dá)式的翻譯模式。算術(shù)表達(dá)式的左遞歸文法的翻譯模式E→E1+T{E.val=E1.val+T.val}E→T{E.val=T.val}T→T1*F{T.val=T1.val*F.val}T→F{T.val=F.val}F→(E){F.val=E.val}F→num{F.val=num.val}左邊符號的綜合屬性的動作符號放在產(chǎn)生式的最右邊。消除左遞歸的算術(shù)表達(dá)式的翻譯模式E→T{R.i=T.val}R{E.val=R.s}R→+T{R1.i=R.i+T.val}R1{R.s=R1.s}R→{R.s=R.i}T→F{Q.i=F.val}Q{T.val=Q.s}Q→*F{Q1.i=Q.i*F.val}Q1{Q.s=Q1.s}Q→{Q.s=Q.i}F→(E){F.val=E.val}F→num{F.val=num.val}左邊符號的綜合屬性的動作符號放在產(chǎn)生式的最右邊。對于topdown分析,假定動作是在處于相同位置上的符號被展開時執(zhí)行的。Topdown分析樹按深度優(yōu)先、從左向右的順序來生成，動作的執(zhí)行是在它前面的符號展開成終結(jié)符號之后，這樣就滿足計算次序的要求。消除左遞歸的算術(shù)表達(dá)式的遞歸下降翻譯:E→T{+T}T→F{*F}F→(E)|idE(){E1.place=T();while(sym==`+`)do{scaner