编译原理第七章

编译原理电子教案第七章语义分析和中间代码产生谢强计算机科学与技术学ieqiang@2本章的主要内容中间代码的表示形式说明语句、赋值语句、控制语句的翻译3本章要求

知识点：中间语言，说明语句，赋值语句，布尔表达式，CASE语句，过程调用语句，控制流语句的翻译以及回填技术。深刻理解：语法树、有向非循环图、三地址代码、四元式、三元式、逆波兰式表示；适用于一遍扫描分析的回填技术。熟练掌握：（1）程序中说明的处理，重要的是在符号表中维持作用域信息；（2）数组元素，赋值语句，过程调用语句的翻译模式；（3）用回填技术实现布尔表达式和控制流语句的翻译。4静态语义审查（1）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。（2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。（3）一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。（4）上下文相关性检查。比如，变量名字必须先声明后引用；而有时，同一名字必须出现两次或多次。

(5)名字的作用域分析翻译为中间语言的好处（1）便于进行与机器无关的代码优化；（2）使编译程序改变目标机更容易；（3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。5本章教学线索1中间语言1.1后缀式1.2图表示法1.3三地址代码2说明语句3赋值语句的翻译4布尔表达式的翻译5控制语句的翻译6过程调用的处理61中间语言主要介绍三种类型的中间语言：后缀式、三地址代码、DAG图。71.1后缀式后缀式表示法（逆波兰式）是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法。这种表示法是：把运算量(操作数)写在前面，把算符写在后面（后缀）。例如：a+b写成ab+。一个表达式的后缀式可以如下定义：

1）如果E是一个变量或常量，则E的后缀式是E自身。

2）如果E是E1opE2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’op,这里E1’和E2’分别为E1和E2的后缀式。

3）如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。注意以下三点：1）在后缀式中：标识符出现的顺序(从左到右)同原来的顺序相同；2）在后缀式中：运算符是按实际计算顺序（从左到右）出现的3）在后缀式中：运算符跟在运算对象的后面出现，且没有括号。例子：a＝3*（b+c）表示为：a3bc+*=a*（b+c/d）表示为：abcd/+*81.2图表示法包括：抽象语法树和DAG(DirectedAcyclicGraph无循环有向图）。DAG：对表达式中的每个子表达式，DAG中都有一个结点，一个内部结点代表一个操作符。它的孩子代表操作数。抽象语法树和DAG区别：在一个DAG中代表公共子表达式的结点具有多个父结点，而在一颗抽象语法树中公共子表达式被表示为重复的子树。++*-abc*da+a*(b-c)+(b-c)*d的DAG+a*-abc*d+-bca+a*(b-c)+(b-c)*d的抽象语法树后缀式：aabc-*+bc-d*+9=a+*buminusc*buminusc=a+*buminusca=b*-c+b*-c的抽象语法树a=b*-c+b*-c的DAG后缀式：abcuminus*bcuminus*+=结论：后缀式是抽象语法树的线性表示，对抽象语法树进行深度优先从左到右的扫描，就可以得到后缀式。101.3三地址代码1.3.1

概念

三地址代码的一般形式：x＝yopz三地址代码：每条语句通常包括三个地址，其中两个用来表示操作数，一个用来存放结果。如：源语言x+y*z可以翻译为：T1＝y*zT2=x+T1又如：a=b*-c+b*-c的抽象语法树对应的三地址代码：t1=-ct2=b*t1t3＝-ct4=b*t3t5＝t2+t4a=t5

a=b*-c+b*-c的DAG对应的三地址代码：t1=-ct2=b*t1t3＝t2+t2a=t3111.3.2三地址语句的种类（1）赋值语句x＝yopz，op为二目算术算符或逻辑算符；（2）赋值语句x＝opy，op为一目算符，如一目减uminus、逻辑非not、移位算符及转换算符；（3）复制语句x＝y；（4）无条件转移语句gotoL；（5）条件转移语句ifxrelopygotoL，关系运算符号relop（<，=，＞=等）；（6）过程调用语句paramx和callp，n，过程返回语句returny；（7）索引赋值x＝y[i]及x[i]＝y；（8）地址和指针赋值x

:＝＆y，x

:＝*y和*x

:＝y。在设计中间代码形式时，选择多少种算符需要权衡

.三地址语句序列是语法树的线性表示，用临时变量代替语法树中的结点。实际实现中，三地址语句序列往往被存放到一个输出文件中，而不是将三地址语句序列置入code属性之中。12产生赋值语句三地址代码的语法制导定义产生式语义规则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:=‘’131.3.3三地址代码的具体实现1）四元式op，arg1，arg2，result2）三元式op，arg1，arg23）间接三元式间接码表+三元式表四元式需要利用较多的临时单元，四元式之间的联系通过临时变量实现。中间代码优化处理时，四元式比三元式方便得多，间接三元式与四元式同样方便，两种实现方式需要的存储空间大体相同。例：对于语句a＝b*-c+b*-c的两种表示方法oparg1arg2resultoparg1arg2（0）uminuscT1（0）uminusc（1）*bT1T2（1）*b(0)（2）uminuscT3（2）uminusc（3）*bT3T4（3）*b(2)（4）+T2T4T5（4）+(1)(3)（5）=T5a（5）assigna(4)三元式四元式14（为什么要计算一次A+B即间接代码中要在一次调用（1），因为（1）已经被引用一次，存储临时变量的地址已经被释放。）例：X=(A+B)*CY=D↑（A+B）的三元式、间接三元式表示：间接代码(1)(2)(3)(1)(4)(5)oparg1arg2(1)+AB(2)*(1)C(3)=X(2)(4)↑D(1)(5)=Y(4)15本章教学线索1中间语言2说明语句2.1过程中的说明语句2.2保留作用域信息2.3记录中的域名3赋值语句的翻译4布尔表达式的翻译5控制语句的翻译6过程调用的处理162说明语句说明语句的翻译：对每个局部名字，在符号表中建立相应的表项，填写有关的信息如类型、嵌套深度、相对地址等。相对地址：相对静态数据区基址或活动记录中局部数据区基址的一个偏移值。172.1过程中的说明语句

一个过程中的所有说明语句作为一个类集来处理。用一个全程变量Offset来记录下一个数据在活动记录中的位置。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．4计算说明语句中名字的类型和相对地址182.2保留作用域信息

问题的提出一般的语言中，标识符的作用在程序正文中有一个确定的范围。因此，同一个标识符在不同的程序正文中可能标识不同的对象，具有不同的性质，要求分配不同的存储空间。于是提出下面的问题：如何组织符号表，使得同一个标识符在不同的作用域中得到正确的引用而不产生混乱。编译程序分析说明语句时建立符号表，编译执行语句时查找符号表。Lookup(id)返回正确的id.entry。程序结构一组嵌套过程，为每个过程说明的局部名字建立一个符号表，所有正在翻译过程的符号表组成整个源程序的符号表。翻译语句部分时查找符号表，查找过程的符号表的路线相当于当前被翻译过程的静态链。翻译时，实际上，为每一个过程维持一个符号表。这种符号表可用链表实现。当碰到过程说明D→procid；D1；S时，就创建一张新的符号表，并且把在D1中的所有说明项都填入此符号表内。新表有一个指针指向刚好包围该嵌入过程的外围过程的符号表，由id表示的过程名字作为该外围过程的局部名字。19处理嵌套过程中的说明语句P→MD {addwidth(top(tblptr)，top(offset))；

pop(tblptr)；pop(offset)}M→ε {t=mktable（nil）；

push（t，tblptr）；push（0，offset）｝D→D1；D2

D→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，tblptr）；push（0，offset)}

在下面的语义规则中用到如下操作。(1)mktable(previous)创建一张新符号表，并返回指向新表的一个指针。参数previous指向一张先前创建的符号表，譬如刚好包围嵌入过程的外围过程符号表。指针previous之值放在新符号表表头，表头中还可存放一些其它信息如过程嵌套深度等等。我们也可以按过程被说明的顺序对过程编号，并把这一编号填入表头。(2)enter(table，name，type,offset）在指针table指示的符号表中为名字name建立一个新项，并把类型type、相对地址offset填入到该项中。(3)addwidth(table,width)在指针table指示的符号表表头中记录下该表中所有名字占用的总宽度。(4)enterproc(table，name，newtable）在指针table指示的符号表中为名字为name的过程建立一个新项。参数newtable指向过程name的符号表。20programsortvara,xprocedurereadarryvaribegin…end//readarryprocedureexchangebeginx=a…end//exchangeprocedurequiksortvark,vfunctionpartitionvari,jbegin…a….;….v…exchange(i,j)endpartitionbegin….end//sort嵌套过程的符号表nilheaderaxreadarryexchangequicksortheaderireadarryheaderpartitionheaderkvpartitionheaderijexchangequicksortexchangereadarrysort212.3记录中的域名T→recordLDend {T.type=record（top（tblptr））；

T.width=top(offset)；

pop（tblptr)；pop(offset)}L→ε{t=mktable(nil)；

push(t，tblptr)；push(0，offset))}

图7.7为－个记录中的域名建立一张符号表p178该翻译模式强调了作为一个语言结构的记录的设计与活动记录之间的相似处。22关于符号表的一些讨论：1.符号表的数椐结构（a）线性表；（b）散列表；

（c）树结构。2.符号表上的运算：（a）插入（insert）；（b）查找（lookup）；（c）删除(delete)；（d）更新（update）。3.符号表必须维持源程序中的作用域信息，源程序中的作用域规则因语言而异，对一种语言，根椐符号表采用的数据结构，维持源程序中的作用域信息方法不同。４.符号表中名字的属性信息由两方面组成：（a）名字在源程序中的属性信息，例如，名字在源程序中的表示，种类，类型等；（b）经分析加工得到的有用信息，例如，对于变量来说，嵌套深度，在活动记录中的偏移量等。23本章教学线索1中间语言2说明语句3赋值语句的翻译3.1符号表中的名字3.2数组元素地址分配3.3访问数组元素的翻译模式3.4访问记录中的域4布尔表达式的翻译5控制语句的翻译6过程调用的处理243赋值语句的翻译赋值语句的翻译表达式的类型可以是整型、实型、数组和记录253.1符号表中的名字名字可以理解为指向符号表中相应该名字表项的指针，如何根据名字查找符号表的表项？过程lookup()检查是否在符号表中存在相应此名字的表项。采用最近嵌套作用域规则查找非局部名字时，lookup过程先通过top(tblptr）指针在当前符号表中查找名字为name的表项。 若找到，返回有关信息。若未找到，lookup就利用当前符号表表头的指针（指向正好包围该过程的外围过程）找到该符号表的外围符号表，然后在那里查找名字为name的表项，直到所有外围过程的符号表中均无此name表项，则lookup返回nil，表明查找失败。26产生赋值语句三地址代码的翻译模式p179：S→id：=E{p：=lookup()；

ifp≠nilthenemit（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≠nilthenE.place：=pelseerror}lookup()=id.entry/nil（查询符号表，如果查到则返回id在符号表中的入口，否则返回空）emit：它将生成的三地址代码送到输出文件。

语义动作还应包括类型分析，文法符号应有类型属性，在类型分析的基础上，进行相容和赋值相容检查，生成类型转换的三地址代码。

273.2数组元素地址分配

数组元素的三地址代码是什么？如何生成数组元素的三地址代码。28数组元素地址的计算公式一维数组A的下标为i的元素的开始地址

VARa：ARRAY[low…high]OFreal；求a[i]的地址。base＋（i-low）*w=i*w+(base-low*w)

其中，base是数组元素a[low]的地址。对于C＝(base-low*w)是一个常量，可以在处理数组说明的时候确定。对于一个二维数组，可以按行或按列存放若按行存放，则可用如下公式计算A[i1,i2]的相对地址：

base+（（i1-low1）*n2+i2-low2）*w=base-（low1*n2+low2）*w

+（i1*n2+i2)*w

令c=（low1*n2+low2）*w则常量部分=a[low1，low2]-c=base-c29计算元素A[i1，i2，...，ik]相对地址的推广公式：((...((i1*n2+i2)*n3+i3...)*nk+ik)*w+base-((...((low1*n2+low2)*n3+low3...)*nk+lowk)*wc=((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w变量部分=((...((i1*n2+i2)*n3+i3...)*nk+ik)*wa[i1，i2，…，in]的地址=base-c+变量部分

x：=a[i1，i2

，…，ik]三地址代码结构：

t1：=变量部分t2：=base-ct3：=t2[t1]x：=t3计算动态数组元素地址的公式与在固定长度数组情况下是同样的，只是上、下界在编译时是未知的。30数组的类型信息：VARa：ARRAY[1..10，1..20]OFreal；符号表中的信息可组织如下：（w=4）a嵌套深度偏移量类型名字表C=84low1=1high1=10n1=10low2=1high2=20n2=20基类型Real标准类型4内情向量31数组元素引用的文法L→id[Elist]|id//*****数组名在形成L时与Elist联系Elist→Elist，E|E为了在分析下标表达式中始终知道有关数组名的信息，改写为：

L→Elist]|idElist→Elist，E|id[E//****数组名与数组最左下标表达式联系Elist可以产生k维数组引用的前m维下标，并生成：（…（（i1n2+i2）n3+i3）…）nm+im则有递归公式：e1=i1

，em=em-1*nm+im对于m=k时，ek*w即为计算数组元素相对地址的变量部分。有关变量与函数的说明Elist.ndim：记录Elist中的下标表达式的个数，即维数；limit（array，j）：返回nj，即由array所指示的数组的第j维长度；Elist.place：用来临时存放由Elist中的下标表达式计算出来的值；em=em-1*nm+imElist引进综合属性array，指向符号表中相应数组名字表项的指针。323.3访问数组元素的翻译模式给定文法：（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相应语义动作S→L：＝E

｛ifL.offset＝nullthenemit(L.place'：＝'E.place)elseemit（L.place'['L.offset']'：='E.Place）}//如果L为简单变量，则生成一般赋值语句，否则若L为数组元素引用，则生成对L所指示地址的索引赋值。332．E→E1＋E2

｛E.place：＝newtemp；

emit（E.place'：＝'E1.place'＋'E2.place）｝3．E→（E1）

{E.place：＝E1.place}当一个数组引用L归约到E时，我们需要L的右值，因此使用索引来获得地址L.place[L.offset]的内容：4.E→L

｛ifL.offset＝nullthenE.place:＝L.place／*Lisasimpleid*/elsebeginE.place：=newtemp；

emit（E.place'：='L.place'['L.offset']')end}（L.place：常量部分，L.offset：变量部分）345.L→Elist]

｛L.place：=newtemp；

emit（L.place‘：=’Elist.array‘－’c）//-----Elist.array：base

L.offset：=newtemp；

emit（L.offset‘：=’w‘*’Elist.place）}

//------Elist.place：下标表达式计算出来的值em

//------L.offset：数组元素相对地址的变量部分一个空的offset表示一个简单的名字：6.L→id{L.place：=id.place；L.offset：=null}35应用递归公式扫描下一个下标表达式：7.Elist→Elist1，E//**（Elist1.place：em-1）{t：＝newtemp；

//**（limit（Elist1.array，m）：nm；E.place：im）

m：＝Elist1.ndim＋1；

emit（t'：='Elist1.place'*'limit（Elist1.array，m））；

emit（t'：='t'+'E.place）；

Elist.array：＝Elist1.array；（em=em-1*nm+im）Elist.place：=t；

Elist.ndim：＝m｝第一维情况，最先扫描到：8.Elist→id[E

｛Elist.place：=E.place；（E.place：i1）

Elist.ndim：=1；

Elist.array：＝id.place}36例设A为一个10*20的数组，即n1=10，n2=20。并设w＝4，数组第一个元素为A[1，1]。则有：((low1*n2)＋low2)*w=(1*20＋1)*4＝84。赋值语句x:=A[y,z]在由底向上的分析中被翻译成如下三地址语句序列：t1：=y*20t1：=t1＋zt2：=A-84t3：=4*t1t4：=t2[t3]x：=t4SL.place=xL.offset=nullx:=E.place=T4L.place=T2L.offset=T3Elist.place=T1Elist.ndim=2Elist.array=A]Elist.place=yElist.ndim=1Elist.array=AA[E.place=yL.place=yL.offset=null,E.place=zL.place=zL.offset=nullzy373.4访问记录中的域

编译器将记录的域的类型和相对地址保存在相应域名的符号表表项之中，可以把用在符号表中查找名字的程序同样用来查找域名。例如：表达式：p↑．info＋1变量P是一个指向某个记录类型的指针，info为其中一个算术型类型的域名。编译程序内部把p表示为：pointer（record（t）），域名info将可以在t所指向的符号表中查找。PinfonextTYPElink=↑node；

node=RECORDinfo：integer；

next：linkEND；VARp：link；38本章教学线索1中间语言2说明语句3赋值语句的翻译4布尔表达式的翻译4.1翻译布尔表达式的方法4.2数值表示法4.3用作控制流语句的布尔表达式的翻译5控制语句的翻译6过程调用的处理394布尔表达式的翻译布尔表达式：用布尔运算符号（and，or，not）作用到布尔变量或关系表达式上而组成；布尔表达式的作用：1）用作计算逻辑值；

2）用作控制流语句如if-then，if-then-else和while-do等之中的条件表达式。本节考虑由如下文法生成的布尔表达式：

E→EorE|EandE|notE|（E）|idrelopid|true|false404.1翻译布尔表达式的方法表示一个布尔表达式的值：方法一：用数值1、0表示真、假，从而对布尔表达式的求值可以象对算术表达式的求值那样一步一步地来计算；方法二：通过程序的控制流，即用程序中控制转移到达的位置来表示布尔表达式的值。方法二用于翻译控制流语句中的布尔表达式尤其方便。414.2数值表示法用1表示真，0表示假来实现布尔表达式的翻译布尔表达式：aorbandnotc

翻译成三地址代码序列：

100：t1：=notc 101：t2：=bandt1 102：t3：=aort1关系表达式：a<b等价于ifa<bthen1else0翻译成三地址代码序列：

100：ifa＜bgotol03 101：t：=0 102：gotol04103：t：=1 104：（注意：运算优先级：not、and、or）42关于布尔表达式的数值表示法的翻译模式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→id1relopid2{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')}43例：根据上面的翻译模式，将布尔表达式:

a<borc<dande<f翻译成三地址代码100：ifa<bgoto103107：T2:=1101：T1:=0108：ife<fgoto111102：goto104109：T3:=0103：T1:=1110：goto112104：ifc<dgoto107111：T3:=1105：T2:=0112：T4:=T2andT3106：goto108113：T5:=T1orT4444.3用作控制流语句的布尔表达式的翻译布尔表达式在控制流语句中的作用：用于对语句的选择，其中间值无须保留。如：ifEthenS1elseS2：如果E为真，转向S1，否则转向S2。因此需要给出E的“真”出口和“假”出口。E.codeS1.codegotoS.nextS2.code…toE.truetoE.falseE.true:E.false:S.next:作为转移条件布尔表达式可以翻译成一串跳转语句如：ifa>corb<dthenS1elseS2代码：ifa>cgotoL2gotoL1L1：ifb<dgotoL2gotoL3L2：S1.codegotoL.nextL3：S2.codeL.next：45产生布尔表达式三地址代码的语义规则产生式语义规则E→E1orE2E1.true=E.trueE1.false=newlabelE2.true=E.trueE2.false=E.falseE.Code=E1.code||gen(E1.false’:’)||E2.codeE→E1andE2E1.true=newlabelE1.false=E.falseE2.true=E.trueE2.false=E.falseE.Code=E1.code||gen(E.true’:’)||E2.codeE→notE1E1.true=E.falseE1.false=E.trueE.code=E1.code46产生布尔表达式三地址代码的语义规则(续)产生式语义规则E→（E1）E1.true=E.trueE1.false=E.falseE.code=E1.codeE→id1relopid2E.code=gen（’if’id1.placerelop.opid2.place‘goto’E.true)||gen(‘goto’E.false)E→trueE.code=gen(‘goto’E.true）E→falseE.code=gen(‘goto’E.false）47例：a<borc<dande<f翻译为：ifa<bgotoLtruegotoL1L1:ifc<dgotoL2gotoLfalseL2:ife<fgotoLtruegotoLfalseEEEorEEandab<cd<ef<48使用翻译模式，实现一遍扫描完成布尔表达式作为条件转移的翻译基本思路：由于在生成某些跳转语句时，语句标号可能还是未知，因此需要采用回填技术来解决这个问题。在生成跳转指令时，对于未知的目标，可以先建立一个链表，将这些具有相同的跳转目标的语句串起来，然后在确定了目标后，再进行回填。跳转指令的三地址代码：(jnz，a，-，p）：ifagotop(jrop，x，y，p）：ifxropygotoprop:>、=、<、<>…(j，-，-，p)：gotop49布尔表达式的文法：（1）E→E1orME2（2）|E1andME2（3）|notE1（4）|(E1)（5）|id1relopid2（6）|id（7）M→ε//M用来产生下一条语句的标号翻译模式用到如下三个函数：

1．makelist(i)：创建一个仅包含i的新表，i是四元式数组的一个下标（标号）。

2．merge(p1，p2)：将由指针p1和p2指向的两个表合并，且返回一个指向连接后的表的指针。

3．backpatch（p，i）：把i作为目标标号回填到p所指向的表中的每一个转移指令中的第四区段。此处的“表”都是为“反填”所拉的链50使用一遍扫描的布尔表达式的翻译模式EE1orME2

{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist}EE1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist);}EnotE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}E(E1){E.truelist:=E1.truelist;E.falselist:=E1.falselist}51Eid1relopid2{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(´j´relop.op‘，’id1.place‘，’id2.place´，´´0´);emit(´j，-，-，0´);}Eid{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘jnz’‘，’id.place‘，’‘-’‘，’‘0’）

emit(‘j,-,-,0’)}M{M.quad:=nextquad}52E.t={100,104}E.f={103,105}E.t={100}E.f={101}E.t={104}E.f={103,105}orM.q=102a<bE.t={102}E.f={103}E.t={104}E.f={105}andM.q=104c<edf<例:表达式a＜borc＜dande＜f一棵作了注释的分析树a<b归约为E产生：100（j<，a，b，0）101（j，-，-，0）c<b归约为E产生：102（j<，c，d，0）103（j，-，-，0）e<f归约为E产生：104（j<，e，f，0）105（j，-，-，0）E1andME2归约为E，对102回填104：102（j<，c，d，104）E1orME2归约为E，对101回填102：101（j，-，-，102）53本章教学线索1中间语言2说明语句3赋值语句的翻译4布尔表达式的翻译5控制语句的翻译5.1

控制流语句5.2

控制流语句的属性文法5.3使用回填技术实现控制流语句的翻译5.4标号与GOTO语句5.5CASE语句的翻译6过程调用的处理545.1控制流语句控制流语句的种类：S→ifEthenS1|ifEthenS1elseS2|whileEdoS1下图为代码结构：E.codeS1.codeGotoS.begin…E.codes1.code…E.true:E.falseE.trueE.false:E.codes1.codegotoS.nextS2.code…E.true:E.falseE.trueE.false:S.next:E.true:E.falseE.trueE.false:S.begin:（a）建立新的标号，E.true，代表S1的代码的第一条指令，如果布尔表达式E的值为真则执行S1的代码，否则直接执行S1之后的代码；代码：

IFETHENGOTOE.trueGOTOE.falseE.true：S1.codeE.false：……55（b）建立新的标号E.true和E.false，因为布尔表达式E的值为真则执行S1的代码，否则执行S2的代码，E.true为S1的代码的第一条指令，E.false为S2的代码的第一条指令，在S1的代码执行后，应该有一条无条件跳转指令跳转到S2的代码之后：代码结构：IFEGOTOE.trueGOTOE.falseE.true：S1的代码

GOTOS.nextE.false：S2的代码

S.next：（c）建立新的标号E.true和E.false，根据while的含义，E为真则执行S1的代码，执行完后跳转到E的代码的开始位置，继续检查E的值，所以在S1的代码后有一条语句GOTOS.begin，如果E的值为假则执行E.false开始的代码，即：代码结构：S.begin：IFETHENGOTOE.trueGOTOE.falseE.true：S1的代码

GOTOS.beginE.false：565.2控制流语句的属性文法产生式语义规则S→ifEthenS1E.True=newlabelE.false=S.nextS1.next=S.nextS.code=E.code||gen(E.true’:’)||S1.codeS→ifEthenS1elseS2E.True=newlabelE.false=newlabelS1.next=S.nextS2.next=S.nextS.code=E.code||gen(E.true’:’)||S1.code||

gen(‘goto’S.next)||gen(E.false’:’)||S2.codeS→whileEdoS1S.begin=newlabelE.true=newlabelE.false=S.nextS1.next=S.beginS.code=gen(S.begin’:’)||E.code||gen(E.true’:’)||S1.code||gen(‘goto’S.begin)57例：whilea<bdoifc<dthenx=y+zelsex=y-z根据属性文法生成的代码：L1：ifa<bgotoL2gotoLnextL2：ifc<dgotoL3gotoL4L3：T1=y+zx=T1gotoL1L4：T2=y-zx=T2gotoL1Lnext：585.3使用回填技术实现控制流语句的翻译考虑的文法：S→ifEthenS|ifEthenSelseS|whileEdoS|beginLend|AL→L；S翻译模式：S→ifEthenM1S1NelseM2S2{backpatch(E.truelist，M1.quad)；

backpatch(E.falselist,M2.quad)；

S.nextlist=merge(S1.nextlist，N.nextlist，S2.nextlist)}N→ε{N.nextlist=makelist(nextquad)emit(‘j，-，-，-’)}M→ε{M.quad=nextquad}59S→ifEthenMS1{backpatch(E.truelist，M.quad)S.nextlist=merge(E.faselist，S1.nextlist)}S→whileM1EdoM2S1{backpatch(S1.nextlist，M1.quad)；

backpatch(E.truelist，M2.quad)S.nextlist=E.falselistemit(‘j，-，-，M1.quad’)}S→beginLend{S.nextlist=L.nextlist}S→A{S.nextlist=makelist()}L→L1；MS{backpatch(L1.nextlist，M.quad)；L.nextlist=S.nextlist}L→S{L.nextlist=S.nextlist}60L1.nextlist=S.nextlist={101}例：将下列语句翻译成四元式：while(a<b)doif(c<d)thenx=y+z;LL1;MSS.nextlist=E.falselist={101}whileM1doM2S1.nextlist={103,-}Ea<bifEc<dthenM3S2Ax=EE1+E2y