會計學1ch賦值語句與布爾表達式的翻譯張素琴實用28.4簡單賦值語句的翻譯為了實現(xiàn)賦值語句x=y語法制導的自動翻譯成四元式：

(=,y,,x)(1)需要定義賦值語句的屬性文法;(2)語法分析的同時執(zhí)行語義規(guī)則，由emit自動生成四元式。第1頁/共30頁3id=E

賦值語句的屬性文法：E=E1+E2

E=E1*E2

{

p:=lookup();

ifp<>nilthenemit(p':='E.place)

elseerror}{E.place=newtemp;emit(E.place':='E1.place'+'E2.place')}{E.place=newtemp;emit(E.place‘=’E1.place‘*'E2.place')}第2頁/共30頁4E=(E1) E=-E1

{E.place:=newtemp;

emit(E.place′:=′′uminus′E1.place}{E.place:=E1.place}語義過程emit將生成的四元式送到輸出文件上,如emit(+,E1.place，E2.place，E.place);過程lookup()負責在符號表中查找標示符符的名字;語義變量E.Place表示存放E的變量在符號表中的登錄項;語義過程newtemp表示生產(chǎn)一臨時變量。第3頁/共30頁5{E.place=newtemp;IfE1.type=int

andE2.type=intthen{emit(E.place,‘:=’,E1.place,‘*‘,E2.place)E.type:=int}elseifE1.type=real

andE2.type=realthen{emit(E.place,‘:=’,E1.place,‘*‘,E2.place)E.type:=real}elseifE1.type=int

andE2.type=realthen{t:=newtemp;emit(t,‘:=’,’itr’,E1.place);emit(E.place,‘:=’,t,‘*‘,E2.place);E.type:=real}else{t:=newtemp;emit(t,‘:=’,’itr’,E2.place);emit(E.place,‘:=’,E2.place,‘*‘,t);E.type:=real}}E→E1*E2

語義變量E.type是E的類型，一目算符itr將整數(shù)轉換成實數(shù)第4頁/共30頁6布爾表達式的文法：

布爾表達式的作用：

1.用作計算邏輯值

2.用作控制流語句如if-then，if-then-else和while-do等之中的條件表達式

布爾表達式:用布爾運算符號(and,or,not)作用到布爾變量或關系表達式上而組成E→EorE|EandE|notE|(E)|idrelopid|true|falseRelop關系運算符8.5布爾表達式的翻譯第5頁/共30頁7布爾表達式：aorbandnotc

手工翻譯成四元式代碼序列：

100：t1:=notc101：t2:=bandt1102：t3:=aort2用1表示真，0表示假實現(xiàn)布爾表達式的翻譯8.5.1布爾表達式的翻譯方法

第6頁/共30頁8關系表達式：a<b

100：ifa＜bgotol03101：t：=0102：gotol04

103:t:=1104：等價于ifa<bthen1else0手工翻譯成四元式代碼序列：100:(j<,a,b,103)101:(=,0,,t)

102:(j,,,104)103:(=,1,,t)

104:第7頁/共30頁9E→E1orE2{E.place:=newtemp;⑥emit(E.place=E1.placeorE2.place)}②E→notE1{E.place:=newtemp;emit(E.place=notE1.place)}E→E1andE2{E.place:=newtemp;①emit(E.place=E1.placeandE2.place)}④E→ture {E.place:=newtemp;emit(E.place=1)}⑤E→false {E.place:=newtemp;emit(E.place=0)}E→id1relopid2{E.place:=newtemp;③emit(ifid1.placerelopid2.placegotonextstart+3);emit(E.place=0);emit(gotonextstat+2);emit(E.place=1)}為自動翻譯需定義布爾表達式的屬性文法：第8頁/共30頁10emit含義：生成一個四元式輸送到文件中nextstat含義：給出下一個四元式在輸出序列中的序號,是即將生成的四元式代碼的序號。每執(zhí)行一次emit后，nextstat自動加1第9頁/共30頁11例：布爾表達式a<bandc<dande<f對應的語法樹a<bandc<dande<fEEEEE①③③③①語義動作執(zhí)行順序：③③①③①第10頁/共30頁12例：布爾表達式a<bandc<dande<f可以生成如下的中間代碼：100:ifa<bgoto103101:t1=0102:goto104103:t1=1③104:ifc<dgoto107105:t2=0106:goto108③107:t2=1{E.place=newtemp;emit(‘if’id1.placerelop.opid2.place‘goto’nextstart+3)emit(E.place‘=’‘0’)emit(‘goto’nextstart+2)emit(E.place‘=’‘1’)}{E.place=newtemp;emit(E.place‘=’E1.place‘a(chǎn)nd’E2.place)}108:t3=t1andt2①{E.place=newtemp;emit(‘if’id1.placerelop.opid2.place‘goto’nextstart+3)emit(E.place‘=’‘0’)emit(‘goto’nextstart+2)emit(E.place‘=’‘1’)}109:ife<fgoto112

110:t4=0111:goto113112:t4=1③{E.place=newtemp;emit(E.place‘=’E1.place‘a(chǎn)ndE2.place)}113:t5=t3andt4①第11頁/共30頁138.5.2控制語句中布爾表達式的翻譯對于出現(xiàn)在條件語句ifEthens1elses2中的布爾表達式E，其作用就是控制對S1和S2的選擇作為條件的布爾表達式，設計有兩個出口：E.true和E.false.對于IF語句，E.true指向S1，E.false指向S2；對于while語句E.true指向循環(huán)的開始，E.false指向while外

的下一條語句。第12頁/共30頁141、基本思想:假定E形如a＜d,則將生成如下E的代碼：四元式表示：E.true:(j<,a,b,E.true)(真出口)

E.false:(j,,,E.false)(假出口)第13頁/共30頁152、優(yōu)化的代碼結構：E→E1andE2E1的代碼E2的代碼E1.trueE2.trueE.trueE.falseE2.falseE1.falseE→E1orE2E1的代碼E2的代碼E1.falseE2.falseE.falseE1.trueE2.trueE.true第14頁/共30頁163、用四元式表示中間代碼用四元式實現(xiàn)中間代碼,真假出口表示為:真出口：(jnz,a,_,P)表示ifagotoP(jrop,x,y,P)表示ifxropygotoP假出口：(j,_,_,q)表示gotoq第15頁/共30頁17計算表達式：a>b四元式真假出口表示為：

(j>,a,b,p)p=nextstat+3(j,,,q)q=nextstat+2若將其作為條件表達式，例如：ifa>bthens1elses2(j>,a,b,p)p為s1的第一個代碼序號(j,,,q)q為s2的第一個代碼序號第16頁/共30頁18ifa<bgotoL1gotoLfalseL1:ifc<dgotoL2gotoLfalselL2:ife<fgotoLtruegotoLfalse(J<,a,b,102)(j,,,Lfalse)(J<,c,d,104)(j,,,Lfalse)(J<,e,f,Ltrue)(j,,,Lfalse)回填地址鏈Ifa<bandc<dande<fthens1elses2四元式第17頁/共30頁194、回填對于每一條這樣的四元式指令作適當?shù)挠涗洠坏┠繕藰颂柋淮_定下來，再將它“回填”到相應的指令中。先產(chǎn)生暫時沒有填寫目標標號的四元式轉移指令。第18頁/共30頁20要解決的問題：在一遍掃描中，生成跳轉語句時,不知道控制要轉向的語句標號解決方法：生成跳轉語句時，將其E.true和E.false鏈成一個鏈表，記錄在E.truelist和E.falselist中等到轉移目標確定以后，再將轉移出口填入E.truelist和E.falselist中回填第19頁/共30頁21(J<,a,b,102)(j,,,Lfalse)(J<,c,d,104)(j,,,Lfalse)(J<,e,f,Ltrue)(j,,,Lfalse)第二遍掃描第一遍掃描(J<,a,b,

)(j,,,)102(J<,c,d,)103(j,,,)回填E.true將E.flase合并成一個鏈102104104(J<,e,f,)105(j,,,)103101E.truelistE.falselist第20頁/共30頁225.控制語句中布爾表達式的語法制導定義(屬性文法)將用到兩個函數(shù)：merge(p1，p2)Backpatch(p,t)第21頁/共30頁23merge(p1，p2)：連接由指針p1和p2指向的兩個表并且返回一個指向連接后的表的指針。

merg(p1,p2)=代碼描述：

functionMERG(P1,P2):POITER{IFP2=0THENmerg=P1ELSE{P=P2while四元式P的第4分量不為0do{P=四元式P的第4分量內(nèi)容}

把P2填入四元式P的第4分量

MERG=P2}P1p2=0P2p2≠0第22頁/共30頁24(J<,a,b,102)(j,,,)102(J<,c,d,104)103(j,,,)P1P2P101第23頁/共30頁25Backpatch(p,t):把t作為目標標號回填到p所指向的表中的每一個轉移指令的第四個元素。此處的“表”都是為“反填”所拉的鏈.代碼如下：ProcedureBACKPATCH(P,t）{Q=PwhileQ≠0do{L=四元式Q的第4分量內(nèi)容;

把t填入四元式Q的第4分量；

Q=L;}}第24頁/共30頁26(J<,a,b,102)(j,,,)102(J<,c,d,104)103(j,,,101)104(J<,e,f,)105(j,,,103)PQLtttIfa<bandc<dande<fthens1elses2第25頁/共30頁(1)

E→E1orE2{backpatch(E1.false,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=merge(E1.true,E2.true)E.false:=E2.false}(2)

E→E1andE2{backpatch(E1.true,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge(E1.false,E2.false);}(3)E→notE1