编译原理-第七章课件

编译原理

——第七章语义分析和中间代码产生王金伟计算机与信息工程学院天津师范大学7/23/20231TJNU-COCIE-WJW第七章语义分析和中间代码产生在词法分析和语法分析之后的阶段就是语义分析和中间代码生成本章把第六章介绍的有关语法制导翻译的相关方法和技术用在中间代码生成和语义分析上主要工作静态语义检查翻译7/23/20232TJNU-COCIE-WJW静态语义检查类型检查:如果操作符作用于不相容的操作数，编译程序必须报告出错信息。例如，在C语言中”.”因该作用与结构体变量，若作用于指针变量应用“->”控制流检查:控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括语句的最小while、for或switch语句。如果不存在包括它的这样的语句应该报错。7/23/20233TJNU-COCIE-WJW静态语义检查一致性检查:很多场合要求对象只能被定义一次例如，Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。相关名字检查:有时，同一名字必须出现两次或多次。例如，Ada语言程序中，循环或程序块可以有一个名字，它出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。其他:如名字的作用域分析等。7/23/20234TJNU-COCIE-WJW翻译（产生中间代码）采用独立于机器的中间代码的好处：便于进行与机器无关的代码优化工作使编译程序改变目标机更容易使编译程序的结构在逻辑上更为简单明确。以中间语言为界面，编译前端和后端的接口更清晰静态语义检查和中间代码生成器的位置语法分析器静

态检查器中间代码生成器中间代码符号流中间代码优化器7/23/20235TJNU-COCIE-WJW第七章语义分析和中间代码产生7.1中间语言7.2说明语句7.3赋值语句的翻译7.4分情况语句7.5回填技术7.6类型检查7/23/20236TJNU-COCIE-WJW7.1中间语言中间语言 源程序的中间表示方法中间语言的形式后缀式图表示法三地址代码7/23/20237TJNU-COCIE-WJW

把运算量(操作数)写在前面，把算符写在后面。

例如： 原式

后缀式

a+b， ab+ a*b， ab*

一、后缀式7/23/20238TJNU-COCIE-WJW1.表达式E的后缀表示递归定义如果E是变量和常数，则E的后缀表示是E本身如果E是形如E1opE2的表达式，其中op是任意的二元算符，则E的后缀表示是E1’E2’op，其中E1’和E2’分别是E1和E2的后缀表示如果E是形如opE1的表达式，其中op是一元算符，则E的后缀表示是E1’op，其中E1’是E1的后缀表示如果E是形如(E1)的表达式，则E1的后缀表示也是E的后缀表示注意：后缀式不需要括号7/23/20239TJNU-COCIE-WJW例：赋值语句a:=b*（-c）+b*（-34）的后缀式：

abc-*b34-*+:=7/23/202310TJNU-COCIE-WJW1.特点和形式描述了源程序的自然层次结构语法树(抽象语法树)有向无环图(DAG)二、图表示法7/23/202311TJNU-COCIE-WJW例：a:=b*-c+b*-c

后缀式是抽象语法树的线性表示 后根序遍历

abcuminus

*bcuminus

*+:=

assigna+*bcuminus(a)抽象语法树*uminuscb7/23/202312TJNU-COCIE-WJWassigna+*bcuminus(b)DAG例：a:=b*-c+b*-c 其中，b*-c是公共子表达式7/23/202313TJNU-COCIE-WJW2.产生赋值语句抽象语法树的属性文法产生式 语义规则S→id:=E S.nptr:=mknode(‘:=’,mkleaf(id,id.place),E.nptr)E→E1+E2

E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)E→E1*E2

E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)E→-E1

E.nptr:=mknode(‘uminus’,E1.nptr)E→(E1) E.nptr:=E1.nptrE→id E.nptr:=mkleaf(id,id.place)7/23/202314TJNU-COCIE-WJW例：赋值语句：a:=b*-c+b*-c抽象语法树的表示方法后缀式：abcuminus*bcuminus*+assignassign

+

*

uminus

id

aid

cid

b

*

uminus

id

cid

b

idb

idcunimus1

*

02

idb

idc

unimus5

*46

+37

ida

assign

98

...

012345678910117/23/202315TJNU-COCIE-WJW1.一般形式 包含三个地址：两个操作数，一个结果x:=yopz一系列的上述形式

x,y,z是名字、常数和编译器产生的临时变量

op是算符，定点、浮点、逻辑，只能有一个例：x+y*z翻译成t1:=y*zt2:=x+t1三、三地址代码7/23/202316TJNU-COCIE-WJW1.一般形式（续）三地址代码是AST或DAG的线性化表示DAG图对应的三地址代码可能比相应的AST对应的三地址代码要优化，因为可以复用中间结果7/23/202317TJNU-COCIE-WJW例子：相应于a:=b*-c+b*-c的AST和DAG的三地址代码

t1：＝-ct2：＝b*t1t3：＝-ct4：＝b*t3t5：＝t2+t4a：＝t5

（a）对于AST的代码

t1：＝-ct2：＝b*t1t5：＝t2+t2a：=t5（b）对于DAG的代码

7/23/202318TJNU-COCIE-WJW2.三地址代码的种类(1)赋值语句：

x:=yopz，op是二元算术算符或逻辑算符(2)赋值语句：

x:=opz，op是一元算符，如：负号，逻辑非not等(3)复写语句：

x:=y7/23/202319TJNU-COCIE-WJW2.三地址代码的种类(续1)(4)无条件转移：

gotoL，L是下一步要执行的三地址语句的标号(5)条件转移语句：

ifxrelopygotoL

根据逻辑运算的结果决定是否执行转移

ifagotoL a为真跳到L执行，否则执行if后边的语句7/23/202320TJNU-COCIE-WJW2.三地址代码的种类(续2)(6)过程调用语句：

paramx和callp,n n表示实参个数例如：callp(x1,x2,…,xn)，表示成三地址语句：

paramx1

paramx2 ……

param

xn callp,n过程返回：returnyy表示返回值7/23/202321TJNU-COCIE-WJW2.三地址代码的种类(续3)(7)数组引用赋值x:=y[i]x[i]:=y(8)地址和指针的使用x:=&yx:=*y*x:=y7/23/202322TJNU-COCIE-WJW3.对赋值语句产生三地址代码的属性文法产生式语义规则S→id:=ES.code:=E.code║gen(id.place':='E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code║E2.code║gen(E.place':='E1.place'+'E2.place)E→E1*E2E.place:=newtemp;E.code:=E1.code║E2.code║gen(E.place':='E1.place'*'E2.place)E→-E1E.place:=newtemp;E.code:=E1.code‖gen(E.place´:=´´uminus´E1.place)E→(E1)E.place:=E1.place;E.code:=E1.codeE→idE.place:=id.place;E.code:=‘’7/23/202323TJNU-COCIE-WJW其中：(1)E.place表示存放E值的名字。(2)E.code表示对E求值的三地址语句序列。(3)newtemp是个函数，对它的调用将产生一个新的临时变量注意：

◆三地址语句序列是语法树的线性表示，用临时变量代替语法树中的结点◆实际实现中，三地址语句序列往往是被存放到一个输出文件中，而不是将三地址语句序列置入code属性之中7/23/202324TJNU-COCIE-WJW4.三地址代码的具体实现三地址代码是一种抽象形式，其具体实现可用结构体来表示，有以下几种表示方法： 四元式：op,arg1,arg2,result

三元式：op,arg1,arg2

间接三元式：间接码表+三元式表7/23/202325TJNU-COCIE-WJW

(1)四元式op,arg1,arg2,resultop：算符的内部编码arg1和arg2分别表示两个操作数result表示计算结果arg1、arg2和result的内容通常是符号表条目指针注意：一元运算不需要使用arg2的域param不使用arg2和result域条件和无条件转移把目标语句的标号放在result中7/23/202326TJNU-COCIE-WJW例子：语句a:=b*-c+b*-c的四元式表示arg1arg2resultop(0) uminus c t1(1) * b t1 t2(2) uminus c t3(3) * b t3 t4(4) + t2 t4 t5(5) Assign t5 a 7/23/202327TJNU-COCIE-WJW(2)三元式

op,arg1,arg2避免四元式引入临时变量，可以用三地址语句的序号表示临时变量有3个域的记录结构op：算符的内部编码arg1和arg2分别表示操作数语句的结果通过语句的序号引用arg1、arg2的内容通常是符号表条目指针或三地址语句的序号(对于临时变量)7/23/202328TJNU-COCIE-WJWarg1arg2op例子：语句a:=b*-c+b*-c的三元式表示(0) uminus c (1) * b (0)(2) uminus c (3) * b (2)(4) + (1)

(3)(5) Assign a (4) 7/23/202329TJNU-COCIE-WJW注意：有些三地址语句要多个三元式表示例子：

x[i]:=y

oparg1arg2 (0)[]=xi(1):=(0)y y:=x[i] oparg1arg2(0)=[]xi(1):=y(0)7/23/202330TJNU-COCIE-WJW(3)间接三元式在三元式基础上，增加一个间接码表.该表按运算的先后顺序列出有关三元式在三元表中的位置。7/23/202331TJNU-COCIE-WJWarg1arg2op间接代码例子：X:=(A+B)*C; Y:=D^(A+B)的间接三元式表示(1) + A B(2) * (1) C (3) assign

X (2)(4) ^ D (1)(5) assignY (4) (1)(2)(3)(1)(4)(5)7/23/202332TJNU-COCIE-WJW总结：3种三地址代码的表示形式的比较式子之间的联系所占空间优化四元式临时变量较大易于调整次序，便于优化的实施三元式三元式的序号较小不易于调整次序，牵一发而动全身间接三元式三元式的序号间接码表和四元式类似，但如果临时值引用不止一次，间接三元式的空间要节省一些通过重排间接代码来实现7/23/202333TJNU-COCIE-WJW7.2说明语句说明语句的翻译： 当翻译一个过程或分程序的一系列说明语句时，便可为该过程的中的每个局部名字(局部变量)分配存储空间，并在符号表中建立相应的表项，填写该名字的有关信息，如：类型、在存储器中的相对地址等相对地址： 相对静态数据区基址或活动记录中局部数据区基址的一个偏移值。7/23/202334TJNU-COCIE-WJWC，Java，Pascal和Fortran这些语言的语法允许一个过程中的所有声明集中在一起处理，把它们安排在一个数据区中在这种情况下，我们可用全局变量，例如offset，来记住下一个可用的相对地址。一、过程中的说明语句

7/23/202335TJNU-COCIE-WJW声明语句的翻译模式计算名字的类型和相对地址P→ {offset:=0} DD→D;DD→id:T {enter(,T.type,offset); offset:=offset+T.width}T→integer {T.type:=integer;

T.width:=4}T→real {T.type:=real;

T.width:=8}T→array[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}7/23/202336TJNU-COCIE-WJW综合属性type和width表示非终结符的类型和宽度初始化的工作由第一个产生式完成

P→{offset:=0}D改写上述产生式，使得所有动作出现在产生式的右部的末端

P→MD M→ε {offset:=0}7/23/202337TJNU-COCIE-WJW1.问题的提出一般的语言中，标识符的作用在程序正文中有一个确定的范围。因此，同一个标识符在不同的程序正文中可能标识不同的对象，具有不同的性质，要求分配不同的存储空间。于是提出下面的问题：如何组织符号表，使得同一个标识符在不同的作用域中得到正确的引用而不产生混乱。编译程序分析说明语句时建立符号表，编译执行语句时查找符号表。Lookup(id)返回正确的id.entry。二、作用域信息的保存7/23/202338TJNU-COCIE-WJW2.嵌套过程的声明当遇到一个嵌入的过程说明时，应当暂停包围此过程的外围过程说明语句处理，而转去处理嵌套过程，等被嵌套过程处理完后再继续。

可以采用以下的产生式描述嵌套过程

P→D D→D;D|id:T|procid;D1;S7/23/202339TJNU-COCIE-WJW

2.嵌套过程的声明（续）符号表的处理为每个过程建立一个独立的符号表，可用链表实现当遇到过程说明D→procid;D1;S时，就创建一张新符号表，把D1中的所有说明的局部名字都填入该符号表新表有一个指向其最近外围过程的符号表的指针id表示的过程名作为其外围过程的一个局部名字。7/23/202340TJNU-COCIE-WJWprogramsort(input,output)

vara:array[0..10]ofinteger;

x:integer; procedurereadarray;

var

i:integer; begin…a…end{readarray} procedureexchange(i,j:integer); begin x:=a[i];a[i]:=a[j];a[j]:=x end{exchange}; procedurequicksort(m,n:integer);

var

k,v:integer; functionpartition(y,z:integer):integer;

var

i,j:integer; begin…a… …v… …exchange(i,j);… end{partition}; begin…end{quicksort};begin…end{sort}.7/23/202341TJNU-COCIE-WJW例：P1767/23/202342TJNU-COCIE-WJW3.嵌套过程的翻译模式(1)定义一些操作mktable(previous)建立新的符号表，并返回新符号表的指针。参数previous指向直接外围过程的符号表。previous放在新建符号表的表头。enter(table,name,type,offset)在table指向的符号表中为变量名name建立新项，enter把类型type和相对地址offset置于该项的域中。7/23/202343TJNU-COCIE-WJW3.嵌套过程的翻译模式(1)定义一些操作(续)addwidth(table,width)把符号表table所有名字占用的总宽度记录在该符号表的表头。enterproc(table,name,newtable)在table指向的符号表中为过程名name建立新项。参数newtable指向过程name的符号表。

7/23/202344TJNU-COCIE-WJW(2)定义两个栈

tblptr栈： 用于保存各过程的符号表指针 栈顶的指针指向当过程的前符号表

offset栈： 用于存放各嵌套过程的当前相对地址 栈顶元素为当前被处理过程的下一个局部名字的相对地址 相应操作有：

push(栈名)：压栈

pop(值，栈名)：出栈

top(栈名)：返回栈顶7/23/202345TJNU-COCIE-WJWP→MD {addwidth(top(tblptr),top(offset)); pop(tblptr);pop(offset)}M→ε {t:=mktable(nil); push(t,tblprt);push(0,offset)}D→D1;D2D→procid;ND1;S{t:=top(tblptr);

addwidth(t,top(offset)); pop(tblptr);pop(offset);

enterproc(top(tblptr),,t)}D→id:T {enter(top(tblptr),, T.type,top(offset)); top(offset):=top(offset)+T.width}N→ε {t:=mktable(top(tblptr)); push(t,tblprt);push(0,offset)}7/23/202346TJNU-COCIE-WJW非终结符M的语义动作最先完成建立最外层作用域的符号表用最外层符号表初始栈tblptr用0初始化offset栈非终结符N的语义动作建立一个新的作用域的符号表在符号表栈中压入新的符号表指针用0作为offset栈顶7/23/202347TJNU-COCIE-WJW变量声明id:T不改变符号表栈建立新的符号条目累加符号的宽度过程的声明处理结束时addwidth记录该符号表的所有名字的宽度更改符号表栈和offset栈过程名进入外围符号表7/23/202348TJNU-COCIE-WJW4.记录声明的产生式T→recordDend为记录的域名建立符号表T→recordLDend {T.type:=record(top(tblptr));

T.width:=top(offset); pop(tblptr);pop(offset)}L→ε {t:=mktable(nil); push(t,tblprt);push(0,offset)}看见关键字record后，标记非终结符L为域名建立一个新的符号表D→id:T的语义动作将域名id的信息填入该纪录的符号表中纪录的域分析完后，offset栈顶保存纪录中所有数据对象的总宽度end后的动作将总宽度作为综合属性T.width返回。把构造器record作用于该记录的符号表指针，得到T.type，用于恢复记录中的域名的名字、类型和宽度7/23/202349TJNU-COCIE-WJW7.3赋值语句的翻译一、简单算术表达式及赋值语句1.符号表中的名字三地址代码中用标识符对应的符号表条目指针表示id的名字本身lookup()检查是否在符号表中存在相应该名字的入口如果找到，则返回该名字对应表项的指针如果找不到，则返回nil表示没有找到2.赋值语句的翻译方案 生成三地址代码7/23/202350TJNU-COCIE-WJW

S→id:=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}E→id {p:=lookup(); ifp<>nilthen

E.place:=p elseerror}移进规约过程A:=B+(-C)AA:=A:=BA:=EA:=E+A:=E+(A:=E+(-A:=E+(-CA:=E+(-EA:=E+(ET1=uminusCA:=E+(E)A:=E+EA:=ET2=B+T1SA=T27/23/202351TJNU-COCIE-WJW二、数组元素的翻译

数组元素的定址：对于一个数组，确定某个元素相对于数组首地址的偏移假设数组存储在连续的存储块中假设每个数组元素的宽度为w，数组的首地址为base1.一维数组元素的定址：A[i]假设数组下标的下界为low，此时：base=&A[low]A[i]的相对地址是：base+(i–low)*w优化的计算方式：i*w+(base–low*w)

后一部分可以在处理数组的说明语句时就计算出来，存到数组A对应的符号表项中去，然后在分析A[i]时只需计算出i*w的值7/23/202352TJNU-COCIE-WJW2.多维数组的定址存储方式有两种：数组元组的定址计算方式是不一样的行为主（一行接一行的存放）列为主（一列接一列的存放）7/23/202353TJNU-COCIE-WJW(1)行为主的二维数组元素的定址公式

A[i1，i2]的相对地址：

base+((i1–low1)*n2+(i2–low2))*wLow1和low2分别是两维的下界n2是数组第二维的维展，即i2可取值的个数，如果high2是i2值的上界，且这一维的步长为1，则n2=high2-low2+1地址计算的优化公式：

((i1*n2)+i2)*w+(base-((low1*n2)+low2)*w)(2)列为主的二维数组的元素定址类似于行为主的二维数组：

base+((i1–low1)+(i2–low2)*n1)*w7/23/202354TJNU-COCIE-WJW(3)多维数组的定址计算行为主的数组，最右边的下标变化最快

A[i1，i2，…，ik

]的相对地址：((…((i1*n2+i2)*n3+i3)…)*nk+ik

)*w+base–((…((low1*n2+low2)*n3+low3)…)*nk+lowk)*w由于在大多数情况下数组各维的维展是一个固定值，所以上述公式的第二行可以在编译时刻计算，并存放在符号表中A的条目中列为主的数组，最左边的下标变化最快，其地址计算公式可以参照上述公式7/23/202355TJNU-COCIE-WJW3.数组引用的描述(1)

产生式描述L→id[Elist]|idElist→Elist,E|E其中，Elist代表下标表达式的列表，表达式中间用‘，’号分隔。改写上述产生式，使数组名字id和最左下标表达式E相联系：L→Elist]|idElist→Elist,E|id[E目的是在对Elist进行翻译时，随时知道符号表中数组id的全部信息。为Elist配备一个综合属性array，用它来传递符号表中数组id项的指针。7/23/202356TJNU-COCIE-WJW(2)几个定义：属性Elist.ndim表示Elist中的下标表达式的个数函数Limit(array，j)返回数组(array指向的符号表项所记录的数组)第j维的元素个数(维展)函数Invariant(array)取得数组的地址计算的不变部分，即地址计算公式第二行中除base外的其它部分的值

((…((i1*n2+i2)*n3+i3)…)*nk+ik

)*w +base–((…((low1*n2+low2)*n3+low3)…)*nk+lowk)*w属性Elist.place存储临时变量在符号表中的表项地址

(3)采用递推计算方法实现Elist的计算(上式中的第一项)：

e1=i1

em=em-1*nm+im

当m=k时，ek

=((…((i1*n2+i2)*n3+i3)…)*nk+ik

)7/23/202357TJNU-COCIE-WJW4.数组定址的翻译模式(1)在赋值语句中引用数组的文法

(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[E7/23/202358TJNU-COCIE-WJW(2)各个产生式的三地址代码生成(1)S→L:=E {ifL.offset=nullthen /*L是简单名字*/ emit(L.place‘:=’E.place); else emit(L.place‘[’L.offset‘]’‘:=’E.place)}

如果L是简单名字，产生正常的赋值；否则产生对由L的两个属性确定的存储单元的索引赋值。(2)E→E1+E2 {E.place:=newtemp; emit(E.place‘:=’E1.place‘+’E2.place)}(3)E→(E) {E.place:=E1.place}7/23/202359TJNU-COCIE-WJW(4)E→L {ifL.offset=nullthen /*L是简单名字*/ E.place:=L.place; elsebegin E.place:=newtemp; emit(E.place‘:=’L.place‘[’L.offset‘]’) end}

如果E产生数组元素L，则需要L的右值，可用索引得到存储单元L.place[L.offset]的内容7/23/202360TJNU-COCIE-WJW(5)L→Elist] {L.place:=newtemp; emit(L.place‘:=’Elist.array‘-’invariant(Elist.array); L.offset:=newtemp; emit(L.offset‘:=’w‘*’Elist.place)}(6)L→id {L.place:=id.place; L.offset:=null}((…((i1

n2+i2

)

n3

+i3)…)

nk

+

ik)

w+base

((…((low1

n2+low2)

n3

+low3)…)

nk

+

lowk)

w

L.place和L.offset都是新的临时变量，L.place对应第二项；L.offset保存w乘以Elist.place的值，对应第一项

7/23/202361TJNU-COCIE-WJW(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}当看见下一个下标表达式时，使用递推公式e1=i1em=em-1*nm+imElist1.place对应em-1

，Elist.place对应em如果Elist1有m1个成分。那么产生式左边的Elist有m个成分7/23/202362TJNU-COCIE-WJW(8)Elist→id[E{Elist.place:=E.place;

Elist.ndim:=1;

Elist.array:=id.place}E.place保存表达式E的值 也是递推公式e1=i1em=em-1*nm+imm=1时的值7/23/202363TJNU-COCIE-WJW例：A是10*20的数组，即n1=10，n2=20，取w=4， 假设数组的第一个元素是A[1,1]

求赋值语句x:=A[y,z]的三地址代码。

(其中每个变量，用它们的名字来代替id.place)解：不变量：

Base-((low1*n2)+low2)*w=A-(1*20+1)*4=A-84可变量：(i1*n2+i2)*w=(y*20+z)*4 t1:=y*20 t1:=t1+z Elist→Elist1,E t2:=A–84 t3:=4*t1 L→Elist] t4:=t2[t3] E→L x:=t4 S→L:=E7/23/202364TJNU-COCIE-WJW7/23/202365TJNU-COCIE-WJW7.4布尔表达式的翻译一、概述1.布尔表达式的作用计算逻辑值在改变控制流的语句中作为条件表达式条件语句：if–then或if–then–else循环：while–do，for等2.布尔表达式的文法

E→EorE|EandE|notE|(E)|idrelopid|true|false用relop.op属性确定relop是<,>,<=,>=,==,!=中的哪个算符的结合性和优先性or和and都是左结合的or的优先级最低，其次是and，not的优先级最高7/23/202366TJNU-COCIE-WJW3.

表示布尔表达式的值的方法

(1)真假值数值化 使布尔表达式的计算类似于算术表达式的计算 通常用1表示真，0表示假 例如：1or(not0and0)or0的计算过程是：

1or(not0and0)or0 =1or(1and0)or0 =1or0or0 =1or0 =1

7/23/202367TJNU-COCIE-WJW(2)用控制流(采取优化措施)

例如：如果有E1orE2，当E1的值可以确定为真时，则可以确定整个表达式的值是真，不必计算E2同理，如果有E1andE2，当E1的值可以确定为假时，则可以确定整个表达式的值是假，不必计算E2简化了布尔表达式的计算也就是说，可以用if-then-else来解释or，and和not：把AorB解释成 ifAthentrueelseB把AandB解释成 ifAthenBelsefalse把notA解释成 ifAthenfalseelsetrue7/23/202368TJNU-COCIE-WJW二、数值表示法1.两个例子例1：aorbandnotc的三地址代码

t1:=notc t2:=bandt1 t3:=aort1例2：关系表达式a<b等价于条件语句ifa<bthen1else0，对应的三地址代码(假设从100行开始)：100：ifa<bgoto103 判断，跳到当前行号+3101：t:=0 产生一个新的临时变量t，令t=0102：goto104 跳到当前行号+2103：t:=1 另刚才产生的t=1104： 下面的语句7/23/202369TJNU-COCIE-WJW2.数值表示布尔值的翻译模式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→(E1) {E.place:=E1.place}E→id1

relopid2 {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→true {E.place:=newtemp; emit(E.place‘:=’‘1’)}E→false {E.place:=newtemp; emit(E.place‘:=’‘0’)}

其中，nextstat给出输出序列下一条三地址语句的地址，每产生一条三地址语句，emit把nextstat+17/23/202370TJNU-COCIE-WJWP187，假设nextstat初始值为100例：a<borc<dande<f产生的三地址代码如下

100：ifa<bgoto103 101：t1:=0 102：goto104 103：t1:=1 t1存放a<b的结果

104：ifc<dgoto107 105：t2:=0 106：goto108 107：t2:=1 t2存放c<d的结果

108：ife<fgoto111 109：t3:=0 110：goto112 111：t3:=1 t3存放e<f的结果

112：t4:=t2andt3 t4存放c<dande<f结果

113：t5:=t1ort4 t5存放整个式子的结果7/23/202371TJNU-COCIE-WJW三、布尔表达式的控制流翻译1.作为条件控制的布尔表达式 出现在条件语句 ifEthenS1elseS2

中的布尔表达式E仅用于控制选择执行S1还是S2，所以E的值不用保存在临时变量中。因此，作为转移条件的E，可以给它两个出口：一个“真”出口，到S1；一个“假”出口，到S2。7/23/202372TJNU-COCIE-WJW2.布尔表达式的控制流翻译的方法在翻译过程中，假定可以用符号标号来标识一条三地址语句，调用newlabel后都返回一个新的符号标号

对于一个布尔表达式E，引用两个标号E.true是E为“真”时控制转向的标号E.false是E为“假”时控制转向的标号翻译的基本思想

(1)假定E形如a<b

则将生成如下的E的代码：

ifa<bgoto

E.true

goto

E.false7/23/202373TJNU-COCIE-WJW

(2)若E形如E1orE2如果E1为真，则E为真，所以E1.true和E.true一样，不需要计算E2如果E1为假，则需要计算E2，此时可以让E1.false是E2代码的第一个语句的标号E2的真出口和假出口分别与E的真出口和假出口一样(3)若E形如E1andE2如果E1为假，则E为假，所以E1.false和E.false一样，不需要计算E2如果E1为真，则需要计算E2，此时可以让E1.true是E2代码的第一个语句的标号E2的真出口和假出口分别与E的真出口和假出口一样(4)若E形如notE1不必产生新的代码，只要把E1的真假出口作为E的假真出口即可，即E.true=E1.false，E.false=E1.true7/23/202374TJNU-COCIE-WJW为布尔表达式产生三地址代码的语法制导定义(根据基本思想)

产生式 语义规则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.codeE→E1andE2 E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code||gen(E1.true’:’)||E2.codeE→notE1 E1.true:=E.false; E1.false:=E.true; E.code:=E1.code其中，E.true和E.false均为继承属性，E.code为综合属性7/23/202375TJNU-COCIE-WJWE→(E1) E1.true:=E.true; E1.false:=E.false; E.code:=E1.codeE→id1

relopid2 E.code:=

gen(‘if’id1.placerelop.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)7/23/202376TJNU-COCIE-WJW

例：P189表达式a<borc<dande<f的翻译(两遍扫描)

假设整个表达式的真假出口已经分别置为Ltrue和Lfalse，则有：

ifa<bgoto

Ltrue

gotoL1 L1: ifc<dgotoL2

goto

Lfalse L2: ife<fgoto

Ltrue

goto

Lfalse

上述代码存在的问题：删掉第二个语句后，不改变代码的值，所以是冗余的T:L2F:LfT:LtF:LfT:LtF:L1T:LtF:LfT:LtF:Lf7/23/202377TJNU-COCIE-WJW7.5控制语句的翻译1.控制语句的文法考虑if-then，if-then-else和while-do语句，其文法：S→ifEthenS1 |ifEthenS1elseS2 |whileEdoS1符号标号的处理：符号标号的生成：函数newlabel每次调用时返回一个新的符号标号符号标号的引入：对每个布尔表达式E引入两个标号E.true：E为真时控制