第六章(語義分析及中間代碼生成)

第六章

語義分析與中間代碼生成貴州大學計算機科學與技術學院本章內(nèi)容介紹幾種常用的中間表示：后綴表示、圖形表示和三地址代碼用語法制導定義和翻譯模式的方法來說明程序設計語言的典型語法結(jié)構怎樣被翻譯成中間形式重點：三地址碼，各種語句的目標代碼結(jié)構、語法制導定義與翻譯模式難點：布爾表達式的翻譯，對各種語句的目標代碼結(jié)構、語法制導定義與翻譯模式的理解本章內(nèi)容6.1中間代碼的形式6.2聲明語句的翻譯6.3賦值語句的翻譯6.4布爾表達式和控制流語句的翻譯6.1中間代碼的形式中間語言(復雜性界于源語言和目標語言之間)的好處：便于進行與機器無關的代碼優(yōu)化工作易于移植使編譯程序的結(jié)構在邏輯上更為簡單明確

源語言程序目標語言程序中間語言程序CompilerFrontEndCompilerBackEnd6.1中間代碼的形式常用的中間代碼：后綴式（逆波蘭表示）圖表示：DAG、語法樹三地址代碼三元式四元式間接三元式6.1.1后綴式中綴表達式的計算順序不是運算符出現(xiàn)的自然順序，而是根據(jù)運算符間的優(yōu)先關系來確定的，因此，從中綴表達式直接生成目標代碼一般比較麻煩。后綴式表示法：Lukasiewicz發(fā)明的一種表示表達式的方法，又稱逆波蘭表示法。一個表達式E的后綴形式可以如下定義：1.如果E是一個變量或常量，則E的后綴式是E自身。2.如果E是E1opE2形式的表達式，其中op是任何二元操作符，則E的后綴式為E1E2op，其中E1和E2分別為E1和E2的后綴式。3.如果E是(E1)形式的表達式，則E1的后綴式就是E的后綴式。后綴式表示法的優(yōu)點為：表達式的運算順序就是運算符出現(xiàn)的順序，它不需要使用括號來指示運算順序，只要知道每個算符的目數(shù)。(84)+2的后綴表示是842+8(4+2)的后綴表示是842+對于后綴式，不論從哪一端進行掃描，都能對它進行唯一分解。后綴式的計算用一個棧實現(xiàn)。一般的計算過程是：自左至右掃描后綴式，每碰到運算對象就把它推進棧。每碰到k目運算符就把它作用于棧頂?shù)膋個項，并用運算結(jié)果代替這k個項。6.1.1后綴式例6.1下面給出的是一些表達式的中綴、前綴和后綴表示。 中綴表示 前綴表示 后綴表示 a+b +ab ab+ a*(b+c) *a+bc abc+* (a+b)*(c+d) *+ab+cd ab+cd+* a:=a*b+c*d :=a+*ab*cd aab*cd*+:=6.1.2圖形表示圖表示法語法樹

DAG圖形表示有向無環(huán)圖(DirectedAcyclicGraph，簡稱DAG)對表達式中的每個子表達式，DAG中都有一個結(jié)點一個內(nèi)部結(jié)點代表一個操作符，它的孩子代表操作數(shù)在一個DAG中代表公共子表達式的結(jié)點具有多個父結(jié)點assigna++bcdcduminus(a)語法樹assigna++bcduminus(b)DAGa:=(b+cd)+cd的圖形表示構造賦值語句語法樹的語法制導定義產(chǎn)生式語義規(guī)則Sid:=E

E

E1+E2

E

E1E2E

E1E(E1)EidS.nptr:=mknode(‘a(chǎn)ssign’,mkleaf(id,id.entry),E.nptr)E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)E.nptr:=mknode(‘’,E1.nptr,E2.nptr)E.nptr:=mkunode(‘uminus’,E1.nptr)E.nptr:=E1.nptrE.nptr:=mkleaf(id,id.entry)6.1.3三地址代碼所謂三地址碼，是指這種代碼的每條指令最多只能包含三個地址，即兩個操作數(shù)地址和一個結(jié)果地址。一般形式：

x:=yopz表達式x+y

z翻譯成的三地址語句序列是t1:=y

z

t2:=x+t1

三地址代碼是語法樹或DAG的一種線性表示:生成三地址代碼時，臨時變量的名字對應抽象語法樹的內(nèi)部結(jié)點

a:=(b+cd)+cd語法樹的代碼

t1:=b

t2:=c

d

t3

:=t1+t2

t4:=c

d

t5:=t3+t4a:=t5assigna++bcdcduminus

a:=(b+cd)+cd

DAG的代碼

t1

:=b

t2:=c

d

t3:=t1+t2

t4:=t3+t2

a:=t4

assigna++bcduminus常用的三地址語句賦值語句x:=yopz，x:=opy，x:=y無條件轉(zhuǎn)移gotoL條件轉(zhuǎn)移ifxrelop

ygotoL過程調(diào)用和返回使用如下的指令來實現(xiàn)： paramx用來指明參數(shù)； callp,n和y=callp,n用來表示過程調(diào)用和函數(shù)調(diào)用； returny表示過程返回；索引賦值x:=y[i]和x[i]:=y地址和指針賦值x:=&y，x:=y和x:=y四元式一個帶有四個域的記錄結(jié)構，這四個域分別稱為op,arg1,arg2及result op arg1 arg2 result(0) uminus c T1(1) * b T1 T2(2) uminus c T3(3) * b T3 T4(4) + T2 T4 T5(5) := T5 a

a:=b*(-c)+b*(-c)T1(T3):=-cT2(T4):=b*T1(T3)T5:=T2+T4a:=T5三地址代碼的具體實現(xiàn)三元式

三個域：op、arg1和arg2通過計算臨時變量值的語句的位置來引用這個臨時變量 op arg1 arg2(0) uminus c (1) * b (0)(2) uminus c (3) * b (2)(4) + (1) (3)(5) assign a (4)三地址代碼的具體實現(xiàn)a:=b*(-c)+b*(-c)T1(T3):=-cT2(T4):=b*T1(T3)T5:=T2+T4a:=T5三元式形如x[i]:=y和x:=y[i]的三元運算符需要用兩條三元式指令來表示y(0)assign1ix[]=0oparg1arg2(0)xassign1iy[]=0oparg1arg2間接三元式

為了便于優(yōu)化，用三元式表+間接碼表表示中間代碼間接碼表:一張指示器表，按運算的先后次序列出有關三元式在三元式表中的位置。優(yōu)點:方便優(yōu)化，節(jié)省空間三地址代碼的具體實現(xiàn)例如，語句X:=(A+B)*C;Y:=D↑(A+B)間接三元式表示如下:6.2聲明語句的翻譯分析過程或程序塊的聲明序列時：為局部名字建立符號表條目為它分配存儲單元符號表中包含了名字的類型和分配給它的存儲單元的相對地址等信息相對地址：對靜態(tài)數(shù)據(jù)區(qū)基址的偏移或?qū)顒佑涗浿芯植繑?shù)據(jù)區(qū)基址的偏移。6.2.1過程中的說明一個過程中的所有聲明語句可集中處理。用一個全程變量offset來記錄下一個可用的相對地址。計算聲明語句中名字的類型和相對地址的翻譯模式P {offset:=0} DSD

D;D

Did:T {enter(,T.type,offset); offset:=offset+T.width}Tinteger {T.type:=integer;T.width:=4}Treal{T.type:=real;T.width:=8}Tarray[num]ofT1 {T.type:=array(num.val,T1.type);

T.width:=num.val

T1.width}T

T1{T.type:=pointer(T1.type);T.width:=4}建立符號表條目programmainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integr)名字的作用域6.2.2作用域信息的保存1.問題的提出一般的語言中，標識符的作用在程序正文中有一個確定的范圍。因此，同一個標識符在不同的程序正文中可能標識不同的對象，具有不同的性質(zhì)，要求分配不同的存儲空間。于是提出下面的問題：如何組織符號表，使得同一個標識符在不同的作用域中得到正確的引用而不產(chǎn)生混亂。編譯程序分析聲明語句時建立符號表，編譯執(zhí)行語句時查找符號表。Lookup(id)返回正確的id.entry。2.程序結(jié)構一組嵌套過程，為每個過程說明的局部名字建立一張獨立的符號表，所有正在翻譯過程的符號表組成整個源程序的符號表。翻譯語句部分時查找符號表，查找過程的符號表的路線相當于當前被翻譯過程的訪問鏈。翻譯時，實際上，為每一個過程維持一張符號表。過程的符號表之間的關系反映過程在源程序中的關系。3.所討論語言的文法(允許過程嵌套) P

DS(1) DD;D(2)

|

id:T(3)

|

procid;D;S(4)問題：如何在處理產(chǎn)生式(1)和(4)的語言結(jié)構時正確地填寫符號表信息？修改文法，使得在定義D之前生成符號表P→MDS (1)D→D;D (2)|id:T (3)|procid;ND;S (4)M→ε (5)N→ε (6)4.翻譯方案中用到的全程量和函數(shù)全程量：有序?qū)＃╰blptr,offset）其中，tblptr保存指向符號表節(jié)點的指針，offset保存各嵌套過程的當前相對地址。函數(shù):mktable(previous)—創(chuàng)建新的符號表,并返回指向新表的指針。previous指向直接外圍過程的符號表(放在符號表首部)enter(table,name,type,offset)

addwidth(table,width)—在指針table指示的符號表表頭記錄下該表中所有名字占用的總域?qū)抏nterproc(table,name,newtable)—為過程名name建立新條目,newtable指向過程name本身的符號表tblptroffsettopprogramsort(input,output);vara:array[0..10]ofinteger;x:integer;procedurereadarray;vari:integer;begin…a…end；procedureexchange(i,j:integer);beginx:=a[i];a[i]:=a[j];a[j]:=x;end；procedurequicksort(m,n:integer);vark,v:integer;functionpartition(y,z:integer):integer; vari,j:integer; begin…a… …v……exchange(i,j)…end;begin…end；begin…end；例一個帶有嵌套的pascal程序(圖7.11)

sortreadarrayexchangequicksortpartitionP

MDS{addwidth(top(tblptr),top(offset));

pop(tblptr);pop(offset)}M

{t:=mktable(nil); push(t,tblprt);push(0,offset)}D

D1;D2Dprocid;ND1;S{t:=top(tblptr);addwidth(t,top(offset));

pop(tblptr);pop(offset); enterproc(top(tblptr),,t)}Did:T{enter(top(tblptr),,T.type,top(offset)); top(offset):=top(offset)+T.width}N

{t:=mktable(top(tblptr)); push(t,tblptr);push(0,offset)}處理嵌套過程中的聲明語句2/3/202331表頭空sortoffsettblptrtoptop02/3/202332表頭空sortoffsettblptrtoptop40aarray02/3/202333xinteger40aarray0表頭空sortoffsettblptrtoptop442/3/202334表頭空sortreadarrary表頭offsettblptrtoptop440aarray0xinteger402/3/202335表頭空sortreadarrary表頭offsettblptrtoptop444aarray0xinteger40iinteger02/3/202336表頭空sortreadarrary表頭4offsettblptrtoptop44aarray0xinteger40iinteger0readarray指向readarray2/3/202337表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭toptop02/3/202338表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange2/3/202339表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort02/3/202340表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort4kinteger02/3/202341表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger42/3/202342表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition02/3/202343表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition4iinteger02/3/202344表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭partition8iinteger0jinteger42/3/202345表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭quicksort8kinteger0vinteger4表頭8partitioniinteger0jinteger4partition2/3/202346表頭空sortreadarrary表頭4offsettblptr44aarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭8quicksortkinteger0vinteger4表頭8partitioniinteger0jinteger4partitionquicksort2/3/202347表頭44空sortreadarrary表頭4offsettblptraarray0xinteger40iinteger0readarray指向readarrayexchange表頭0toptopexchange指向exchange表頭8quicksortkinteger0vinteger4表頭8partitioniinteger0jinteger4partitionquicksort下述產(chǎn)生式中的非終結(jié)符T產(chǎn)生記錄類型TrecordDend例：c=recorda:integer;b:real;end編譯程序為記錄中的域名建立單獨的符號表6.2.3記錄的域名L6.2.3記錄的域名TrecordL

Dend {T.type:=record(top(tblptr)); T.width:=top(offset); pop(tblptr);pop(offset)}L

{t:=mktable(nil); push(t,tblprt);push(0,offset)}為記錄中的域名建立符號表的翻譯方案Programsample(input,output);Varx:integer;y:real;Proceduresub;varx:integer;a=recorda:integer;b=recordb:integer;c:realendend;….空表首12xysub04sample表首20xa04sub空表首16ab04recordtype1空表首12bc04recordtype26.3賦值語句的翻譯賦值語句的語義是將賦值號右邊表達式的值保存到左邊的變量中表達式的類型可以是整型、實型，表達式中的運算對象可以是數(shù)組元素或者記錄域的引用怎樣從符號表中查找名字？怎樣訪問數(shù)組元素和記錄的域？6.3.1符號表的中名字在中間語言中出現(xiàn)的名字應該理解為指向符號表中相應該名字表項的指針實際處理源程序時，當在賦值語句中遇到名字的時候，需要在符號表中查找它的定義，獲得其屬性，然后在生成的三地址代碼中使用它在符號表中位置的指針。如何根據(jù)名字查找符號表的表項？過程lookup()檢查是否在符號表中存在相應此名字的表項。采用最近嵌套作用域規(guī)則查找非局部名字時，lookup過程先通過top(tblptr）指針在當前符號表中查找名字為name的表項。 若找到，返回有關信息。若未找到，lookup就利用當前符號表表頭的指針找到該符號表的外圍符號表，然后在那里查找名字為name的表項，直到所有外圍過程的符號表中均無此name表項，則lookup返回nil,表明查找失敗。文法:Sid:=EE

E1+E2E

E1*E2E

E1E(E1)Eid產(chǎn)生賦值語句三地址代碼的翻譯方案產(chǎn)生賦值語句三地址代碼的翻譯方案說明：E.place表示存放E值的變量的符號表條目地址newtemp用來產(chǎn)生一個新的臨時變量的名字，并返回其在符號表條目的地址emit將生成的三地址語句發(fā)送到輸出文件中Sid:=E {p:=lookup(); ifp

nilthen emit(p,‘:=’,E.place) elseerror}E

E1+E2 {E.place:=newtemp;

emit(E.place,‘:=’,E1.place,‘+’,E2.place)}E

E1*E2 {E.place:=newtemp;

emit(E.place,‘:=’,E1.place,‘*’,E2.place)}E

E1{E.place:=newtemp; emit(E.place,‘:=’,‘uminus’,E1.place)}E(E1){E.place:=E1.place}Eid{p:=lookup(); ifp

nilthen

E.place:=p

elseerror}6.3.2數(shù)組元素的地址計算一維數(shù)組A的第i個元素的地址計算VARA:ARRAY[low..high]OFT;

求A[i]的地址.

base+(i

low)

w=i

w+(base

low

w)常量部分：可在編譯時計算出來A[low]的地址每個數(shù)組元素的寬度二維數(shù)組按列存放(Fortran語言)按行存放(Pascal語言,C語言)若按行存放，

A:array[low1..high1,low2..high2]ofT則可用如下公式計算A[i1,i2]的地址：

base+((i1

low1)

n2+(i2

low2))

w=((i1

n2)+i2)w+(base((low1n2)+low2)

w)常量部分：可在編譯時計算n2=high2

low2+1可在編譯器分析數(shù)組聲明時計算，存于符號表的A條目中推廣到多維數(shù)組數(shù)組元素A[i1,i2,...,ik

]的地址表達式:((…((i1

n2+i2

)

n3

+i3)…)

nk

+ik)

w

+

base

((…((low1

n2+low2)

n3

+low3)…)

nk

+lowk)

w計算動態(tài)數(shù)組元素地址的公式與在固定長度數(shù)組情況下是同樣的，只是其上、下界在編譯時是未知的，地址計算全部在運行時完成。6.3.3數(shù)組元素地址計算的翻譯方案K維數(shù)組引用A[i1,i2,...,ik

]的三地址代碼主要是完成

((…((i1

n2+i2

)

n3

+i3)…)

nk

+ik)的計算，其計算可以由下列遞推公式完成e1=i1em=em-1nm+imnj=highj–lowj+1數(shù)組元素引用的文法

Lid[Elist]|id Elist

Elist,E|E

Elist+i1,i2,…,ik為了使數(shù)組各維的長度nj在將下標表達式合并到Elist時是可用的，需將產(chǎn)生式改寫為：

L

Elist

]|id Elist

Elist,E|id[E把數(shù)組名字id與最左下標表達式E聯(lián)系，而不是在形成L時與Elist相聯(lián)系。其目的是使在整個下標表達式串Elist的翻譯過程中隨時都能知道符號表中相應于數(shù)組名字id的表項，從而隨時能夠了解登記在符號表中有關數(shù)組id的全部信息。給定文法：(1)S→L:=E(2)E→E+E(3)E→(E)(4)E→L(5)L→Elist](6)L→id(7)Elist→Elist,E(8)Elist→id[E引入下列語義變量或語義過程:Elist.ndim:記錄Elist中的下標表達式的個數(shù),即維數(shù);函數(shù)limit(array,j)：返回nj

，即由array所指示的數(shù)組的第j維大小;Elist.place：臨時變量，用來臨時存放由Elist中的下標表達式計算出來的值;Elist.array:記錄符號表中相應數(shù)組名字表項指針。L有兩個屬性,若L為簡單變量i,L.place指變量i的符號表入口，L.offset是null,否則,它們都是新的臨時變量,L.place對應地址計算中的常量部分,L.offset對應變量部分,即w×Elist.place的值(6)L→id {L.place:=id.place;L.offset:=null}(8)Elist→id[E

{Elist.place:=E.place;

Elist.ndim:=1; Elist.array:=id.place}A[i1,i2,…,ik]

((…((i1

n2+i2

)

n3

+i3)…)

nk

+ik)

w

+

base

((…((low1

n2+low2)

n3

+low3)…)

nk

+lowk)

w

(7)Elist→Elist1,E {t:=newtemp; m:=Elist1.ndim+1;

emit(t‘:=’

Elist1.place

‘*’

limit(Elist1.array,m)

);

emit(t‘:=’t‘+’

E.place);

Elist.array:=Elist1.array;

Elist.place:=t;

Elist.ndim:=m}A[i1,i2,…,ik]

(…((i1

n2+i2

)

n3

+i3)…)

nm

+im

em=em-1

nm

+im(5)L

Elist] {L.place:=newtemp;

emit(L.place,‘:=’,

base(Elist.array),‘’,

invariant(Elist.array));

L.offset:=newtemp;

emit(L.offset,‘:=’,

Elist.place,‘’,w)}A[i1,i2,…,ik]

((…((i1

n2+i2

)

n3

+i3)…)

nk

+ik)

w

+base

((…((low1

n2+low2)

n3

+low3)…)

nk

+lowk)

w

(4)E

L{ifL.offset=nullthen/

L是簡單變量/

E.place:=L.place

elsebeginE.place:=newtemp;

emit(E.place,‘:=’,

L.place,‘[’,

L.offset,‘]’)

end}

(2)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

+

base

((…((low1

n2+low2)

n3

+low3)…)

nk

+lowk)

w(3)E(E1){E.place:=E1.place}(1)S

L:=E

{ifL.offset=nullthen/

L是簡單變量/

emit(L.place,‘:=’,E.place) else

emit(L.place,‘[’,L.offset,‘]’,‘:=’,

E.place)}

例：設A為一個1020的數(shù)組，即n1=10,n2=20。并設w=4，數(shù)組第一個元素為A[1，1]。則有，((low1n2)＋low2)w=(120＋1)4=84。畫出賦值語句x:=A[y,z]的帶注釋的分析樹。請寫出語句x:=A[y,z]的最右推導？S

L:=EL:=LL:=Elist

]L:=Elist,E]L:=Elist,L]L:=Elist

,z]L:=A[E

,z]L:=A[L

,z]L:=A[y,z]x:=A[y,z](1)S→L:=E(2)E→E+E(3)E→(E)(4)E→L(5)L→Elist](6)L→id(7)Elist→Elist,E(8)Elist→id[Ex:=A[y,z]S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]yx:=A[y,z]的注釋分析樹S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]yx:=A[y,z]的注釋分析樹t1:=y20t1:=t1+zS:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]yx:=A[y,z]的注釋分析樹t1:=y20t1:=t1+zt2:=A84t3:=4t1

S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]yx:=A[y,z]的注釋分析樹t1:=y20t1:=t1+zt2:=A84t3:=4t1

t4:=t2[t3]S:=L.place:=xL.offset:=nullxE.place:=t4L.place:=t2L.offset:=t3Elist.place:=t1Elist.ndim:=2Elist.array:=A,Elist.place:=yElist.ndim:=1Elist.array:=AE.place:=zL.place:=zL.offset:=nullE.place:=yL.place:=yL.offset:=nullA[z]yx:=A[y,z]的注釋分析樹t1:=y20t1:=t1+zt2:=A84t3:=4t1

t4:=t2[t3]x:=t4

6.3.4訪問記錄中的域編譯器將記錄的域的類型和相對地址保存在相應域名的符號表表項之中，可以把用在符號表中查找名字的程序同樣用來查找域名。例如：表達式：p．info＋1

p是一個記錄類型的變量，info為其中一個算術型的域名。

p的類型是：record(tblptr)，域名info將可以在tblptr所指向的符號表中查找。6.3.5類型轉(zhuǎn)換用E.type表示非終結(jié)符E的類型屬性對應產(chǎn)生式EE1opE2的語義動作中關于E.type的語義規(guī)則可定義為： {ifE1.type=integerand E2.type=integer thenE.type:=integer elseE.type:=real}算符區(qū)分為整型算符intop和實型算符realop，X:=y＋i*j其中x、y為實型；i、j為整型。這個賦值句產(chǎn)生的三地址代碼為：

T1:=i

int*

j

T2:=inttoreal

T1

T3:=y

real+

T2

x:=T3

關于產(chǎn)生式E→E1＋E2

的語義動作E.place:=newtempifE1.type=integerandE2.type=integerthenbegin

emit(E.place,‘:=’,E1.place,‘int+’,E2.place);

E.type=integerendelseifE1.type=integerandE2.type=realthenbegin u:=newtemp; emit(u,‘:=’,‘inttoreal’,E1.place); emit(E.place,‘:=’,u,

‘real+’,E2.place); E.type:=realend...6.4布爾表達式和控制流語句的翻譯布爾表達式:用布爾運算符號（and，or，not）作用到布爾變量或關系表達式上而組成布爾表達式的作用： 1.用作計算邏輯值 2.用作控制流語句如if-then，if-then-else和while-do等之中的條件表達式本節(jié)考慮由如下文法生成的布爾表達式：

E→Eor

E|EandE|notE|(E)|idrelopid|true|false6.4.1布爾表達式的翻譯有兩種方法用來表示一個布爾表達式的值方法一：用數(shù)值表示真和假，對布爾表達式的求值象對算術表達式的求值那樣一步一步地計算1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=1

方法二：通過程序的控制流，即用程序中控制轉(zhuǎn)移到達的位置來表示布爾表達式的值

把AorB解釋成ifAthentrueelseB把AandB解釋成ifAthenBelsefalse把notA解釋成 ifAthenfalseelsetrue數(shù)值表示法用1表示真，0表示假來實現(xiàn)布爾表達式的翻譯布爾表達式：aorbandnotc翻譯成三地址代碼序列：100：t1:=notc101：t2:=bandt1102：t3:=aort2關系表達式：a<b等價于ifa<bthen1else0翻譯成三地址代碼序列：100：ifa＜bgotol03101：t：=0102：gotol04。103:t:=1104：關于布爾表達式的數(shù)值表示法的翻譯方案過程emit將三地址代碼送到輸出文件中nextstat給出輸出序列中下一條三地址語句的地址索引每產(chǎn)生一條三地址語句后，過程emit便把nextstat加1E→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→(E1)｛E.place:=E1.place}關于布爾表達式的數(shù)值表示法的翻譯方案E→id1relopid2{E.place:=newtemp;

emit('if‘,id1.place,relop.op,id2.place,'goto‘,nextstat+3);

emit(E.place,':=‘,'0');

emit('goto‘,nextstat+2);

emit(E.place,':=‘,'1')}

E→ture｛E.place:=newtemp;emit(E.place,':=‘,'1')}E→false｛E.place:=newtemp;emit(E.place,':=‘,'0')}a<b翻譯成100: ifa<bgoto103101: T:=0102: goto104103: T:=1104:

布爾表達式a<b

or

c<d

and

e<f的翻譯結(jié)果

100: ifa<bgoto103101: T1:=0 102: goto104103: T1:=1104: ifc<dgoto107105: T2:=0 106: goto108107: T2:=1108:ife<fgoto111109:T3:=0110:goto112111:T3:=1112:T4:=T2andT3113:T5:=T1orT4Eid1relopid2

{E.place:=newtemp; emit(‘if’id1.placerelop.opid2.place ‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2); emit(E.place‘:=’‘1’)}E→E1orE2

{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp;emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}6.4.2控制流語句的翻譯考慮下列產(chǎn)生式所定義的語句SifEthenS1 |ifEthenS1

elseS2 |whileEdoS1|S1;S2

其中E為布爾表達式if-then語句 S→ifEthenS1E.codeS1.codeToE.trueToE.false……E.true:E.false:E.Code和S.code分別表示E和S的三地址代碼E.True，E.false，S.begin和S.next都是三地址語句的標號if-then語句的語法制導定義

產(chǎn)生式 語義規(guī)則S→ifEthenS1

E.true:=newlabel; E.flase:=S.next; S1.next:=S.next

S.code:=E.code

||

gen(E.true‘:’)

||

S1.codeE.codeS1.codeToE.trueToE.false……E.true:E.false:返回一個新標號把形成的代碼串作為函數(shù)值串的連接算符if-then-else語句 S→ifEthenS1elseS2E.codeS1.codeS2.codeToE.trueToE.falsegotoS.nextS.next……E.true:E.false:if-then-else語句的語法制導定義

產(chǎn)生式 語義規(guī)則S→ifEthenS1elseS2

E.true:=newlabel; E.false:=newlabel; S1.next:=S.next S2.next:=S.next;

S.code:=E.code

||

gen(E.true‘:’)

||

S1.code||

gen(‘goto’S.next)||

gen(E.false‘:’)

||

S2.codeE.codeS1.codeS2.codeToE.trueToE.falsegotoS.nextS.next……E.true:E.false:while-do語句 S→whileEdoS1

E.codeS1.codeToE.trueToE.falsegotoS.beginS.begin:……E.true:E.false:while-do語句的語法制導定義

產(chǎn)生式 語義規(guī)則 S→whileEdoS1 S.begin:=newlabel; E.true:=newlabel; E.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin‘:’)||

E.code

||

gen(E.true‘:’)

||

S1.code

||

gen(‘goto’S.begin)E.codeS1.codeToE.trueToE.falsegotoS.beginS.begin:……E.true:E.false:S1.codeS2.codeS1.next:...(d)S1;S2SS1;S2

S

S1;S2{S1.next:=newlabel;S2.next:=S.next;

S.code:=S1.code||gen(S1.next,‘:’)||S2.code}6.4.3控制流語句中布爾表達式的翻譯基本思想:假定E形如a＜b,則將生成如下的E的代碼：ifa＜bgotoE.truegotoE.false布爾表達式的語法制導定義

產(chǎn)生式 語義規(guī)則

E→E1orE2

E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code|| gen(E1.false‘:’)||E2.code

E1.codeToE.trueToE1.falseE2.codeToE.trueToE.false布爾表達式的語法制導定義

產(chǎn)生式 語義規(guī)則 E→E1andE2

E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code|| gen(E1.true‘:’)||E2.codeE1.codeToE.

falseToE1.trueE2.codeToE.trueToE.false布爾表達式的語法制導定義

產(chǎn)生式 語義規(guī)則 E→notE1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.codeE→(E1) E1.true:=E.true; E1.false:=E.false; E.code:=E1.code布爾表達式的語法制導定義

產(chǎn)生式 語義規(guī)則

E→id1relopid2E.code:=gen(‘if’id1.place relop.opid2.place‘goto’E.true)|| gen(‘goto’E.false)E→true E.code:=gen(‘goto’E.true)E→false E.code:=gen(‘goto’E.false)考慮如下表達式：

a<borc<dande<f

假定整個表達式的真假出口已分別置為Ltrue和Lfalse，則按定義將生成如下的代碼： ifa<bgotoLtrue gotoL1 L1: ifc<dgotoL2 gotoLfalse L2: ife<fgotoLtrue gotoLfalse考慮如下語句:

whilea<bdo

ifc<dthenx:=y+z

elsex:=y-z生成下列代碼：

L1: ifa<bgotoL2 g