第六章(语义分析及中间代码生成)

第六章

语义分析与中间代码生成贵州大学计算机科学与技术学院本章内容介绍几种常用的中间表示：后缀表示、图形表示和三地址代码用语法制导定义和翻译模式的方法来说明程序设计语言的典型语法结构怎样被翻译成中间形式重点：三地址码，各种语句的目标代码结构、语法制导定义与翻译模式难点：布尔表达式的翻译，对各种语句的目标代码结构、语法制导定义与翻译模式的理解本章内容6.1中间代码的形式6.2声明语句的翻译6.3赋值语句的翻译6.4布尔表达式和控制流语句的翻译6.1中间代码的形式中间语言(复杂性界于源语言和目标语言之间)的好处：便于进行与机器无关的代码优化工作易于移植使编译程序的结构在逻辑上更为简单明确

源语言程序目标语言程序中间语言程序CompilerFrontEndCompilerBackEnd6.1中间代码的形式常用的中间代码：后缀式（逆波兰表示）图表示：DAG、语法树三地址代码三元式四元式间接三元式6.1.1后缀式中缀表达式的计算顺序不是运算符出现的自然顺序，而是根据运算符间的优先关系来确定的，因此，从中缀表达式直接生成目标代码一般比较麻烦。后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。一个表达式E的后缀形式可以如下定义：1.如果E是一个变量或常量，则E的后缀式是E自身。2.如果E是E1opE2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1E2op，其中E1和E2分别为E1和E2的后缀式。3.如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。后缀式表示法的优点为：表达式的运算顺序就是运算符出现的顺序，它不需要使用括号来指示运算顺序，只要知道每个算符的目数。(84)+2的后缀表示是842+8(4+2)的后缀表示是842+对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算对象就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这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图形表示有向无环图(DirectedAcyclicGraph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点assigna++bcdcduminus(a)语法树assigna++bcduminus(b)DAGa:=(b+cd)+cd的图形表示构造赋值语句语法树的语法制导定义产生式语义规则Sid:=E

E

E1+E2

E

E1E2E

E1E(E1)EidS.nptr:=mknode(‘assign’,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三地址代码所谓三地址码，是指这种代码的每条指令最多只能包含三个地址，即两个操作数地址和一个结果地址。一般形式：

x:=yopz表达式x+y

z翻译成的三地址语句序列是t1:=y

z

t2:=x+t1

三地址代码是语法树或DAG的一种线性表示:生成三地址代码时，临时变量的名字对应抽象语法树的内部结点

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无条件转移gotoL条件转移ifxrelop

ygotoL过程调用和返回使用如下的指令来实现： paramx用来指明参数； callp,n和y=callp,n用来表示过程调用和函数调用； returny表示过程返回；索引赋值x:=y[i]和x[i]:=y地址和指针赋值x:=&y，x:=y和x:=y四元式一个带有四个域的记录结构，这四个域分别称为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三地址代码的具体实现三元式

三个域：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)三地址代码的具体实现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间接三元式

为了便于优化，用三元式表+间接码表表示中间代码间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。优点:方便优化，节省空间三地址代码的具体实现例如，语句X:=(A+B)*C;Y:=D↑(A+B)间接三元式表示如下:6.2声明语句的翻译分析过程或程序块的声明序列时：为局部名字建立符号表条目为它分配存储单元符号表中包含了名字的类型和分配给它的存储单元的相对地址等信息相对地址：对静态数据区基址的偏移或对活动记录中局部数据区基址的偏移。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.问题的提出一般的语言中，标识符的作用在程序正文中有一个确定的范围。因此，同一个标识符在不同的程序正文中可能标识不同的对象，具有不同的性质，要求分配不同的存储空间。于是提出下面的问题：如何组织符号表，使得同一个标识符在不同的作用域中得到正确的引用而不产生混乱。编译程序分析声明语句时建立符号表，编译执行语句时查找符号表。Lookup(id)返回正确的id.entry。2.程序结构一组嵌套过程，为每个过程说明的局部名字建立一张独立的符号表，所有正在翻译过程的符号表组成整个源程序的符号表。翻译语句部分时查找符号表，查找过程的符号表的路线相当于当前被翻译过程的访问链。翻译时，实际上，为每一个过程维持一张符号表。过程的符号表之间的关系反映过程在源程序中的关系。3.所讨论语言的文法(允许过程嵌套) P

DS(1) DD;D(2)

|

id:T(3)

|

procid;D;S(4)问题：如何在处理产生式(1)和(4)的语言结构时正确地填写符号表信息？修改文法，使得在定义D之前生成符号表P→MDS (1)D→D;D (2)|id:T (3)|procid;ND;S (4)M→ε (5)N→ε (6)4.翻译方案中用到的全程量和函数全程量：有序对栈（tblptr,offset）其中，tblptr保存指向符号表节点的指针，offset保存各嵌套过程的当前相对地址。函数:mktable(previous)—创建新的符号表,并返回指向新表的指针。previous指向直接外围过程的符号表(放在符号表首部)enter(table,name,type,offset)

addwidth(table,width)—在指针table指示的符号表表头记录下该表中所有名字占用的总域宽enterproc(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下述产生式中的非终结符T产生记录类型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赋值语句的翻译赋值语句的语义是将赋值号右边表达式的值保存到左边的变量中表达式的类型可以是整型、实型，表达式中的运算对象可以是数组元素或者记录域的引用怎样从符号表中查找名字？怎样访问数组元素和记录的域？6.3.1符号表的中名字在中间语言中出现的名字应该理解为指向符号表中相应该名字表项的指针实际处理源程序时，当在赋值语句中遇到名字的时候，需要在符号表中查找它的定义，获得其属性，然后在生成的三地址代码中使用它在符号表中位置的指针。如何根据名字查找符号表的表项？过程lookup()检查是否在符号表中存在相应此名字的表项。采用最近嵌套作用域规则查找非局部名字时，lookup过程先通过top(tblptr）指针在当前符号表中查找名字为name的表项。 若找到，返回有关信息。若未找到，lookup就利用当前符号表表头的指针找到该符号表的外围符号表，然后在那里查找名字为name的表项，直到所有外围过程的符号表中均无此name表项，则lookup返回nil,表明查找失败。文法:Sid:=EE

E1+E2E

E1*E2E

E1E(E1)Eid产生赋值语句三地址代码的翻译方案产生赋值语句三地址代码的翻译方案说明：E.place表示存放E值的变量的符号表条目地址newtemp用来产生一个新的临时变量的名字，并返回其在符号表条目的地址emit将生成的三地址语句发送到输出文件中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数组元素的地址计算一维数组A的第i个元素的地址计算VARA:ARRAY[low..high]OFT;

求A[i]的地址.

base+(i

low)

w=i

w+(base

low

w)常量部分：可在编译时计算出来A[low]的地址每个数组元素的宽度二维数组按列存放(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可在编译器分析数组声明时计算，存于符号表的A条目中推广到多维数组数组元素A[i1,i2,...,ik

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

n2+i2

)

n3

+i3)…)

nk

+ik)

w

+

base

((…((low1

n2+low2)

n3

+low3)…)

nk

+lowk)

w计算动态数组元素地址的公式与在固定长度数组情况下是同样的，只是其上、下界在编译时是未知的，地址计算全部在运行时完成。6.3.3数组元素地址计算的翻译方案K维数组引用A[i1,i2,...,ik

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

((…((i1

n2+i2

)

n3

+i3)…)

nk

+ik)的计算，其计算可以由下列递推公式完成e1=i1em=em-1nm+imnj=highj–lowj+1数组元素引用的文法

Lid[Elist]|id Elist

Elist,E|E

Elist+i1,i2,…,ik为了使数组各维的长度nj在将下标表达式合并到Elist时是可用的，需将产生式改写为：

L

Elist

]|id Elist

Elist,E|id[E把数组名字id与最左下标表达式E联系，而不是在形成L时与Elist相联系。其目的是使在整个下标表达式串Elist的翻译过程中随时都能知道符号表中相应于数组名字id的表项，从而随时能够了解登记在符号表中有关数组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中的下标表达式的个数,即维数;函数limit(array,j)：返回nj

，即由array所指示的数组的第j维大小;Elist.place：临时变量，用来临时存放由Elist中的下标表达式计算出来的值;Elist.array:记录符号表中相应数组名字表项指针。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的数组，即n1=10,n2=20。并设w=4，数组第一个元素为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类型转换用E.type表示非终结符E的类型属性对应产生式EE1opE2的语义动作中关于E.type的语义规则可定义为： {ifE1.type=integerand E2.type=integer thenE.type:=integer elseE.type:=real}算符区分为整型算符intop和实型算符realop，X:=y＋i*j其中x、y为实型；i、j为整型。这个赋值句产生的三地址代码为：

T1:=i

int*

j

T2:=inttoreal

T1

T3:=y

real+

T2

x:=T3

关于产生式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等之中的条件表达式本节考虑由如下文法生成的布尔表达式：

E→Eor

E|EandE|notE|(E)|idrelopid|true|false6.4.1布尔表达式的翻译有两种方法用来表示一个布尔表达式的值方法一：用数值表示真和假，对布尔表达式的求值象对算术表达式的求值那样一步一步地计算1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=1

方法二：通过程序的控制流，即用程序中控制转移到达的位置来表示布尔表达式的值

把AorB解释成ifAthentrueelseB把AandB解释成ifAthenBelsefalse把notA解释成 ifAthenfalseelsetrue数值表示法用1表示真，0表示假来实现布尔表达式的翻译布尔表达式：aorbandnotc翻译成三地址代码序列：100：t1:=notc101：t2:=bandt1102：t3:=aort2关系表达式：a<b等价于ifa<bthen1else0翻译成三地址代码序列：100：ifa＜bgotol03101：t：=0102：gotol04。103:t:=1104：关于布尔表达式的数值表示法的翻译方案过程emit将三地址代码送到输出文件中nextstat给出输出序列中下一条三地址语句的地址索引每产生一条三地址语句后，过程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}关于布尔表达式的数值表示法的翻译方案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的翻译结果

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‘and’E2.place)}6.4.2控制流语句的翻译考虑下列产生式所定义的语句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语句的语法制导定义

产生式 语义规则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:返回一个新标号把形成的代码串作为函数值串的连接算符if-then-else语句 S→ifEthenS1elseS2E.codeS1.codeS2.codeToE.trueToE.falsegotoS.nextS.next……E.true:E.false:if-then-else语句的语法制导定义

产生式 语义规则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语句的语法制导定义

产生式 语义规则 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布尔表达式的语法制导定义

产生式 语义规则

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布尔表达式的语法制导定义

产生式 语义规则 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布尔表达式的语法制导定义

产生式 语义规则 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布尔表达式的语法制导定义

产生式 语义规则

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