编译原理课件 第7章 语义分析和中间代码产生

本章在编译程序中的地位

表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理语义分析和中间代码的产生语义分析的概念:

源程序经过词法分析、语法分析后，表明该源程序书写正确、符合程序语言所规定的语法，但语法分析并未对程序内部的逻辑含义加以分析，因此编译程序接着进行语义分析，即审查每个语法成分的静态语义。如果静态语义正确，则生成与该语言成分等效的中间代码，或直接生成目标代码。

直接生成机器语言或汇编语言形式的目标代码的优点是编译时间短且无需中间代码到目标代码的翻译，而生成中间代码的优点是使编译结构在逻辑上更为简单明确，特别是使目标代码的优化较易实现。语义分析进行的语义检查有两类：动态语义检查和静态语义检查。动态语义检查需生成相应的目标代码，在运行时进行；静态语义检查在编译时进行。语义分析和中间代码的产生静态语义检查涉及以下几个方面：(1)类型检查，如运算操作数的类型应相容。(2)控制流检查，用以保证控制语句有合法的转向点。如C语言中不允许goto语句转入case语句流；break语句需寻找包含它的最小switch、while或for语句方可找到转向点。(3)一致性检查，如在相同作用域中标识符只能说明一次、case语句的标号不能相同等。语义分析和中间代码的产生语法分析器中间代码产生器静态检查器中间代码优化器

语义分析阶段只产生中间代码而不生成目标代码的方法使编译程序的开发变得较为容易，但由于语义是上下文有关的，因此语义的形式化描述非常困难，目前较常见的是用属性文法作为描述语义的工具，并采用语法制导翻译法完成对语法成分的翻译。语义分析和中间代码的产生语法制导翻译：在语法分析的基础上进行边分析边翻译。教学要求掌握：1.逆波兰式,DAG图,抽象语法树,三地址代码,三元式,四元式等中间代码表示;2.简单赋值语句的翻译,带数组元素引用的赋值句的翻译;3.布尔表达式的翻译,控制语句中布尔表达式的翻译;4.控制语句的翻译。了解理解：说明语句的翻译，过程调用和参数的处理。教学内容7.1中间语言

后缀式，DAG，三地址码(四元式，三元式，间接三元式)*7.2说明语句的翻译7.3赋值语句的翻译，数组元素引用的翻译7.4布尔表达式的翻译求布尔式值的翻译，作为控制条件的翻译7.5控制语句的翻译if，while，goto，case7.6过程调用的处理,参数传递的处理*7.7类型检查（不作要求，不讲）7.1中间语言要掌握几种中间语言的基本结构：逆波兰表示即后缀式抽象语法树DAG图三地址代码(四元式、三元式、间接三元式)7.1.1后缀式波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示法，又称逆波兰式表示法。后缀式这种方法是，把运算量(操作数)写在算符的前面，把算符写在运算量的后面(后缀)。后缀式的定义(P167.)一个表达式的后缀式可以如下定义：1.如果E是一个变量或常量，则E的后缀式是E自身。2.如果E是E1opE2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’op,这里E1’和E2’分别为E1和E2的后缀式。3.如果E是(E1)形式的表达式，则E1的后缀式就是E的后缀式。要求会正确写出表达式的后缀式。后缀式求值可以使用一个栈来求值求值过程：从左到右扫描后缀式，每碰到运算量就把它推进栈，每碰到k目运算符就把它作用于栈顶的k个项，弹出这k项，并用运算结果来代替这k个项后缀式：例写表达式的后缀式要点：1.后缀式中运算量的顺序与中缀式的相同；2.算符出现的次序即表达式的运算次序；3.不使用括号。例：a+bab+a*(b+c)abc+*(a+b)*(c+d)-a+b*cabc*+a/b*c-d*ex:=a-b/(c+d)用

表示取负算符(uminus):=表示赋值算符(assign)

ab+cd+*ab/c*de*-xabcd+/-:=7.1.2抽象语法树语法制导翻译以语法树作基础,实际上,语法树可以作为一种合适的中间语言形式。现在对语法树进行改造，去掉那些对翻译不必要的信息，将语法树进行抽象---抽象语法树。在表达式的抽象语法树中，运算符、关键字不作叶子结点而作为内部结点，叶子结点只是运算量。抽象语法树也可以属性化，给结点加上属性变成带附注的抽象语法树。语法制导翻译既可以基于语法分析树也可以基于抽象语法树进行，采用的基本方法是一样的。抽象语法树：简例例，为下面文法的句子a-4+c

建立抽象语法树。EE+T|E－T|TT(E)Tid|num为每个运算量或运算符号都建立一个结点。可以根据表达式的运算顺序自下而上的构造---手工构造。a－+c4抽象语法树运算符作内部结点id(a)EE－TE+TTnum(4)id(c)语法树7.1.3DAG图表示法：无循环有向图（DAG)与语法树一样，对于表达式中的每个子表达式，DAG图中都有一个结点：一个内部结点代表一个操作符，它的孩子代表操作数；两者不同的是在DAG图中代表公共子表达式的结点具有多个父结点；在一棵抽象语法树中公共子表达式被表示为重复的子树；例如赋值语句的语法树与DAG图：a:=b*-c+b*-c抽象语法树公共子表达式重复出现assigna+*bcuminus*uminuscb图7.3抽象语法树例：

a:=b*-c+b*-c

(b)DAG公共子表达式只出现一次，一个结点可以有多个父结点图7.3DAG例：a:=b*-c+b*-c

assigna+bcuminus*

后缀式与抽象语法树(DAG)的关系后缀式是抽象语法树的线性表示形式。是树的后序遍历的一个序列。例如:抽象语法树assigna+*bcuminus*uminuscb后缀式:abcuminus*bcuminus*+assign后序遍历：

(1)遍历左子树；

(2)遍历右子树；

(3)访问根结点。

7.1.4三地址代码三地址代码是由下面一般形式的语句构成的序列:x:=yopz其中，x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号。每个三地址语句的右边只能有一个运算符。例,表达式x+y*z翻译为三地址代码:T1:=y*zT2:=x+T1T1,T2是编译时产生的临时变量。三地址代码：说明1.之所以称为三地址代码，是因为三地址代码语句类似与汇编指令,涉及三个地址x、y和z，其中y、z表示操作数，x存放结果。地址常用属性place表示。名字.place：指向符号表名字入口的指针临时变量.place：临时变量值存放的单元地址常数.place：指向常数表中常数入口的指针2.三地址语句可以带符号标号,标号代表存放中间代码的数组中三地址代码语句的下标。3.三地址代码是抽象语法树或DAG的线性化表示---每个内部结点对应一个三地址语句。例,P170.图7.5，是相应于P168.图7.3的抽象语法树和DAG的三地址代码：

(a)对应抽象语法树的代码(b)对应DAG的代码T1:＝-cT1:＝-cT2:＝b*T1T2:＝b*T1T3:＝-cT5:＝T2+T2T4:＝b*T3a:＝T5T5:＝T2+T4a:＝T5注：临时变量的名字对应抽象语法树的内部结点(算符结点),表达式中的每个运算都要引入一个新的临时变量存放计算结果,要多少引入多少。抽象语法树与三地址代码的关系(1)赋值语句x:＝yopz;

op是二元算术或逻辑运算符(2)赋值语句x:＝opy;op是一元算符，如取负、逻辑非、移位及类型转换(3)复制语句x:＝y;(4)无条件转移语句gotoL;

符号标号L代表存放中间代码的数组中三地址代码语句的下标(5)条件转移语句ifxrelopygotoL;

ifagotoL;

relop是关系运算符;a是布尔量*三地址代码语句的种类(P170.)(6)过程调用语句paramx;x是实参数

callp,n;p过程名,n实参个数

过程返回语句returny;y返回值,可有可无(7)索引赋值x:=y[i];=[]变址取数

x[i]:=y;[]=变址存数(8)地址和指针赋值x:＝＆y;

x:＝*y;

*x:＝y;注：选择适当的算符集合是中间代码设计的重要问题，应该不大不小，足以实现源语言的操作运算。*三地址代码语句的种类(续P170.)四元式用了四个域（op,arg1,arg2,result）四元式需要利用较多的临时单元，四元式之间的联系通过临时变量实现三地址语句：z:=xopy可表示为：(op，x，y，T1)(=，T1，，z)对于一元运算可只使用arg1四元式中的arg1,arg2,result其实都是指针，它指向相关符号表中的名字的入口,临时变量也要填入符号表。三地址代码的实现算符操作数1(指针)操作数2(指针)结果(临变)三地址代码的具体实现:用记录结构,含四个域赋值语句a:=b*-c+b*-c

的三地址代码实现(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcbT2T5arg1T1T3T4arg2resultT1T2T3T4T5aopP172.表7.4(a)三地址语句的四元式表示三地址代码实现：四元式表示四元式之间的联系通过临时变量实现三元式

(op,arg1,arg2）因为只有三个域，所以为三元式是为了避免把临时变量填入符号表；而是通过计算整个这个临时变量的值得语句的位置来引用该临时变量；三地址代码的实现(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcb(1)aarg1(0)(2)(3)(4)arg2opP172.表7.4(b)三地址语句的三元式表示三元式中使用了指向三元式语句的指针(序号)，序号也表示该三元式计算的结果值,三元式之间的联系通过指针实现。三地址代码实现：三元式a:=b*-c+b*-c三地址代码实现：(0)(1)(2)(3)uminus*+assigncb(1)aarg1(0)(1)(2)arg2op三元式表(0)(1)(0)(1)(2)(3)间接代码三元式表中没有了重复的三元式，语句的移动仅改变左边的间接码表。另外的例见P173.表7.6。间接三元式（三元式的指针表）不直接使用三元式表，而是另外设一张指示器表(间接码表)间接三元式a:=b*-c+b*-c写中间语言：练习写出表达式：A+B*(C-D)-E/(F-G)

的逆波兰表示、三元式表示、四元式表示。解:四元式表示：①(-,C,D,T1)②(*,B,T1,T2)③(+,A,T2,T3)④(-,F,G,T4)⑤(/,E,T4,T5)⑥(-,T3,T5,T6)解:三元式表示：①(-,C,D)②(*,B,①)③(+,A,②)④(-,F,G)⑤(/,E,④)⑥(-,③,⑤)解：逆波兰表示：ABCD-*+EFG-/-*7.2说明语句当考察一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。对每个局部名字，将在符号表中建立相应的表项，并填入相应的信息如类型、嵌套深度、相对地址等。说明语句的翻译目的就是建立符号表。…局部变量……地址增加相对地址基地址→相对地址是指相对数据区基地址的一个偏移量。如图所示：符号表的结构和组织(参见CH.8)符号表结构例,P235.FORTRAN语言的SD表结构。名字属性地址种属维数/形参个数类型数据区号相对地址

a局部变量整型120

b数组2实型2100

p过程1符号表的组织:指各表项的安排线性表:顺序填、查表二叉树：按序填表，对折查找杂凑技术：根据HASH()函数值填、查表sortnilheaderaxreadarrayexchangequicksortheaderexchangeheaderkvpartitionquicksortheaderijpartitioniheaderreadarraytoreadarraytoexchangeP176.

嵌套过程的程序例子P176.图7.7嵌套过程的符号表(5个过程,5张表,表之间的联系)P177.图7.8处理嵌套过程中的说明语句的翻译模式说明语句翻译的例子7.3赋值语句的翻译本节讨论的赋值语句，其表达式类型可以是整型、实型、数组和记录。赋值语句的翻译将讨论如何在符号表中查找名字及如何存取数组和记录的元素。本节只介绍7.3.1和7.3.2小节。7.3.1简单算术表达式及赋值语句的翻译图7.10的翻译模式；赋值语句翻译为三地址代码7.3.2数组元素引用的翻译一维、二维数组元素地址计算含有数组元素引用的赋值语句的翻译含简单变量的赋值语句，如id:=E，其中，id为普通变量，而E是简单的算术表达式。7.3.1简单算术表达式及赋值语句文法定义如下：S→id:=EE→E1+E2E→E1*E2E→-E1E→(E1)E→id需要的语义过程

1.E的属性定义：E.place:存放表达式E“值”2.newtemp：获取临时变量以存放中间结果3.emit－产生三地址码的过程；4.lookup(name)－检查name是否在符号表中有定义（条目）需要的语义变量E•PLACE：与非终结符E相联系的语义变量值为某变量的符号表入口地址或临时变量序号。它与文法的非终结符相联，分析过程需要就建立，不需要就消亡。例.翻译赋值语句x:=-a+b*c

为三地址代码自下而上语法制导翻译，结合图7.10理解赋值语句和算术表达式翻译：例三地址语句:

查表③①查表id(x):=E.placeSE.place+E.placeid(a)E.place*E.place－E.placeid(c)id(b)④查表②生成⑤生成⑥生成⑦查表,生成②T1:=uminusa

⑤T2:=b*c

⑥T3:=T1+T2

⑦x:=T3翻译赋值语句x:=-a+b*(-c+d)/e为三地址代码。掌握手工生成赋值句的三地址代码的方法：按运算顺序写出三地址语句。赋值语句和算术表达式翻译：练习三地址语句序列:T1:=uminusa

T2:=uminuscT3:=T2+dT4:=b*T3

T5:=T3/eT6:=T1+T2x:=T67.3.2数组元素的引用一．数组及其下标变量地址的计算1.数组分类：一维数组、二维数组、多维数组；2.多维数组的存放按行存放按列存放(FORTRAN)只要知道数组的首地址，及每个数组元素占多少内存单元，就可计算出任一数组元素的地址；7.3.2数组元素的引用数组元素引用的关键问题:数组元素地址的计算，由数组的存放方式决定翻译时要产生计算数组元素地址的中间代码。以后都假定：数组的元素存放在一片连续存储单元中，按行存放，数组的每个元素宽度为w。一维数组元素地址计算---牢记设一维数组：A[low

:high

]一维数组元素A[i]

的相对地址为：

base+(i–low)*w(7.4)

其中：low为数组下标的下界，high为数组下标的上界，base是数组的起始地址，即base为A的第一个元素A[low]的相对地址。(7.4)式可以整理为：i*w+(base–low*w)其中：i*w

是随数组下标变量i而变化的部分；base–low*w是在数组元素地址计算公式中不变化的常数,常记C=base–low*w。二维数组元素地址计算---牢记设二维数组：A[low1:high1][low2:high2]

每维

的长度(n1、n2)

ni=highi－lowi+1P180.

二维数组元素A[i1][i2]

的相对地址计算公式：

base＋((

i1－low1)*n2＋(i2－low2))*w

可整理为：base－(low1*n2＋low2)*w＋(i1*n2＋i2)*w

(7.5)

(7.5)分出地址不变部分和地址变化部分。常记C=(low1*n2＋low2)*wC值在处理数组说明时即可以计算出来,与数组元素的下标无关,是一个定数,C值可放在符号表数组A的表项中,或数组内情向量中。k维数组元素地址计算一般,对于一个k维数组P180.

A[low1:high1,…,lowk:highk]若按行存放，数组的每个元素的宽度为w

各维的长度ni=highi－lowi+1则数组元素A[i1,i2,…,ik]的相对地址计算：D=base–C+变化部分(7.6)

变化部分=((...((i1*n2+i2)*n3+i3)...)*nk+ik)*wC=((...((low1*n2+low2)*n3+low3)...)*nk+lowk)*w

(7.7)静态数组,动态数组静态数组：数组说明中各维的上下界是确定的C值在编译的时候就能计算出来动态数组：数组说明中各维的上下界有不确定的C值在编译的时候不能计算出来,运行时才能计算计算动态数组元素地址的公式与静态数组是同样的，只是上、下界在编译时是未知的。数组元素引用的文法:P181.

L→id[Elist]|id

L表示简单变量或数组元素

Elist→Elist,E|E

Elist表示下标列表Elist

+i1,i2,…,in数组元素地址变化部分:((i1*n2+i2)*n3+i3)*n4+……

nj

:=highj

–lowj

+1(7.8)

递归公式em

=em-1*nm+im

(7.9)为了从符号表获得有关数组各维长度nj

的信息，改写文法为：

L→Elist]

|id

Elist→Elist,E|id[E

让数组名与第一个下标联系设计数组元素引用的文法

P181.数组元素引用的文法:(1)S→L:＝ES赋值语句(2)E→E＋EE表达式,可含数组元素(3)E→(E)(4)E→L(5)L→Elist]L数组元素(6)L→idL简单变量(7)Elist→Elist,EElist

带数组名的下标表(8)Elist→id[E参见P181.~183.包含数组元素引用的赋值语句的翻译模式。数组元素引用的文法及翻译模式有关变量与函数的说明：Elist.ndim

综合属性：记录Elist中的下标表达式的个数，即维数;函数limit(array,j)：返回nj，即由array所指示的数组的第j维长度;Elist.place：临时变量，用来临时存放由Elist

中的下标表达式计算出来的值:

em=em-1*nmElist.Array综合属性：数组名的符号表地址;过程emit()

产生一条三地址语句;数组元素引用的翻译模式：说明(1)L.place,L.offset:描述L的左值的情况。若L为简单变量,则L.place为符号表指针,而L.offset为null;若L为数组,则L.place存放数组元素地址的不变部分的值,L.offset存放地址的变化部分的值,L表示的数组元素的地址为:L.place[L.offset]。

相应语义动作:若L是一个简单变量的名字，则生成一般的赋值;若L为数组元素引用，则生成对L所指示的数组元素地址的索引赋值。数组元素引用的翻译模式：说明(2)手工生成数组元素引用的代码1.先确定:数组维数k;宽度w;各维的下界Lowj,上界highj,计算各维长度nj;数组首地址(不同的数组用不同的符号,比如A数组用A表示);计算出常数C一维数组C=Low*w二维数组C=(low1*n2+low2)*w2.对一维数组元素A[i]产生2个地址计算的三地址语句:T1:=w*iT2:=A－C

地址表示T2[T1]3.对二维数组元素A[i,j]产生4个地址计算的三地址语句:T1:=i*n2T2:=A－C

T1:=T1+jT3:=w*T1

地址表示T2[T3]数组元素引用的代码结构例,

赋值语句x:=A[i1,i2]的三地址代码结构：

T1:=A[i1,i2]的地址变化部分的计算值

T2:=base-CA[i1,i2]地址的不变部分值T3:=T2[T1]x:=T3例,

赋值语句A[i1,i2]

:=E

的三地址代码结构：

T1:=A[i1,i2]的地址变化部分的计算值

T2:=base-CA[i1,i2]地址的不变部分值T3:=表达式E的值T2[T1]:=T3例7.1设A为一个10*20的二维数组P183.

即设A[1:10,1:20],

n1=10,n2=20;w＝4；

数组第一个元素为A[1,1]

则计算C值

=(low1*n2＋low2)*w=(1*20＋1)*4＝84使用P181~183.的翻译模式,对赋值语句

x:=A[y,z]

进行翻译，带注释的分析树如P183.图7.12所示。考虑结合自下而上分析的一遍扫描语法制导翻译。带数组元素引用的赋值语句的翻译例例7.1x:=A[y,z]的带注释的分析树L.place=xL.offset=nullL.place=T2L.offset=T3E.place=T4Elist.place=T1Elist.ndim=2Elist.array=AS:=x]⑨4⑩1①6⑧5⑦7图7.12结合翻译模式理解第7步产生2条,第8步产生2条,第9步产生1条,10步产生1条Elist.place=yElist.ndim=1Elist.array=A,L.place=zL.offset=nullE.place=zA[zyL.place=yL.offset=nullE.place=yElist(place=T1,ndim=2,array=A)⑦7⑥4⑤6④8③4②6(续上页）x:=A[y,z]在第7,8,9,10步归约时产生计算数组元素地址的代码数组元素的引用翻译:例7.1赋值语句x:=A[y,z]

在自下而上的分析中被翻译成如下三地址语句序列：P183.

T1:=y*20T1:=T1＋zT2:=A-84T3:=4*T1T4:=T2[T3]x:=T4

注意：20(第2维长度)、84(C值)、4(宽度)都是编译中引入的常量,用A代表数组的首地址。⑦7地址的变化部分计算:*,+⑧5地址的不变部分:base-C地址的变化部分(乘宽度w)⑨4从数组元素地址取数⑩1赋值手工生成数组元素引用的代码：例翻译A[i+2,j+1]:=M+B[k]

为三地址代码设A数组A[1:10,1:20];w=4;数组首地址A;

CA=(1*20+1)*4=84设B数组B[1:10];w=4;数组首地址B;CB=1*4=4三地址语句:

T1:=i+2

T5:=4*kT2:=j+1T6:=B－4T1:=T1*20T7:=T6[T5]变址取数T1:=T1+T2T7:=M+T7T3:=A－84T3[T4]:=T7变址存数

T4:=4*T1计算下标值一维B[k]二维A[i+2,j+1]数组元素引用翻译:练习1设二维数组A[1:10,1:20]，则n1=10,n2=20；设W=2(1)赋值语句X:=A[I,J]的三地址代码序列；(2)赋值语句A[I+2,J+1]:=M+N三地址代码。

(1)解：C=42

T1:=I*20T1:=T1+JT2:=A-42T3:=T1*2T4:=T2[T3]X:=T4(2)解：C=42

T1:=I+2T2:=J+1T3:=T1*20T3:=T2+T3T4:=A-42T5:=T3*2T6:=M+NT4[T5]:=T6数组元素引用翻译:练习2(3)赋值语句X:=A[I,J]的四元式序列；(4)赋值语句A[I+2,J+1]:=M+N四元式序列。(3)解：

C=42

(*，I,20,T1)(+,J,T1,T1)(-,A,42,T2)(*,T1,2,T3)(=[],T2[T3],_,T4)(:=,T4,_,X)(4)解：C=42(+,I,2,T1)(+,J,1,T2)(*,T1,20,T3)(+,T2,T3,T3)(-,A,42,T4)(*,T3,2,T5)(+,M,N,T6)([]=,T6,_,T4[T5])7.4布尔表达式的翻译布尔表达式是用布尔运算符号and、or、not

作用到布尔变量或关系表达式上而组成的。关系表达式形式如E1relopE2,其中E1和E2是算术表达式，relop为关系运算符:<,<=,>=,>,=,≠。程序设计语言中,布尔表达式有两个基本作用：一个是用作计算逻辑值(真1,假0)另一个是用作控制流语句如if-then、if-then-else和while-do等中的条件表达式布尔表达式的文法本节中考虑由下列文法产生的布尔表达式：

E→EorE|EandE|notE|(E)|idrelopid|id使用relop的属性relop.op来确定relop所指的6种关系运算中的哪一个。假定按惯例确定and,、or、not的优先级和结合性。注意:此id表示布尔量布尔表达式的语义布尔式的语义是指明计算一个逻辑值的规则,有两种计算规则:

1.用数值(1/0)表示真和假,同计算算术表达式一样,一步不差地按序计算出整个布尔式的值。例如:计算1or(not0and0)or0=12.优化(短路)方法，不一定一步不差的计算，可以由某个子布尔式的值确定整个布尔式的值。布尔表达式的计值规则规则2用于翻译控制流语句中的布尔表达式尤其方便①计算EE1

E2

or=真真真假假假②计算EE1

E2

and=真真真假假假解释为:ifE1thentrueelseE2解释为:ifE1thenE2elsefalse7.4.1数值表示法首先考虑用1表示真，用0表示假来实现布尔表达式的翻译。1.类似算术表达式求值方法计算布尔式值例:aorbandnotc翻译为:T1:=notc

T2:=bandT1T3:=aorT2注意:此布尔式中的a,b,c是逻辑量(值0/1)!数值表示法：第2种方法求布尔式值一个形如a<b的关系表达式可等价的写成:

ifa<bthen1else0并将它翻译成如下三地址语句序列：100ifa<bgoto103101T:=0102goto104103T:=1104逻辑量a也作同样翻译，只要将a<b换为a。P186.图7.13布尔式的数值表示法的翻译模式

P187.例7.2

翻译布尔式

a<borc<dande<f100ifa<b

goto103108ife<f

goto111101T1:=0109T3:=0102goto104110goto112103T1:=1111T3:=1104ifc<d

goto107112T4:=T2andT3105T2:=0113T5:=T1orT4106goto108114107T2:=1注意:这儿,三地址代码的序号作标号!布尔表达式的数值表示法翻译：图7.147.4.2作为条件控制的布尔式翻译出现在条件语句：作为控制语句中的布尔表达式E，其作用仅仅在控制选择语句S1和S2无须保留E的值，而是赋与予E两个出口“真出口”转向S1“假出口”转向S2语句(7.10)可翻译成如P187.图7.15所示的代码结构。ifEthenS1elseS2(7.10)假出口真出口无条件转移If_then_else语句的代码结构E.code:综合属性布尔式E的三地址代码S.code:综合属性语句S的三地址代码E.true:继承属性,E为‘真’时控制流转向的标号;E.false:继承属性,E为‘假’时控制流转向的标号；S.next:继承属性,标号,紧随S代码之后的地址。E.codeS1.codeGotoS.nextS2.code……E.ture:E.false:S.next:ToE.tureToE.false布尔表达式的翻译－短路计算对于布而表达式E:aorb如果a为true，则E为true

如果a为false，则E的值取决于b，要对b求值如果b为true，则E为true;如果b为false，则E为false对于布而表达式E:aandb如果a为false，则E为false如果a为true，则E的值取决于b，要对b求值如果b为true，则E为true;如果b为false，则E为false产生布尔式三地址跳转代码：例7.3例7.3应用P188.表7.7的属性文法语法制导翻译布尔表达式

E=a<borc<dande<f

为跳转三地址代码：P189.

ifa<bgoto

Ltrue---表达式的真出口

gotoL1

L1:ifc<dgotoL2

goto

Lfalse---表达式的假出口L2:ife<fgoto

Ltrue

goto

Lfalse设实现三地址代码时采用四元式形式,并且假定：

(jnz,a,_,p)

表示ifagotop

(jrop,x,y,p)

表示ifxropygotop

(j,_,_,p)

表示gotop例7.3布尔式a<borc<dande<f

翻译为跳转四元式序列:P189.

100(j<,a,b,Ltrue)104(j<,e,f,Lture)

101(j,_,_,102)105(j,_,_,

Lfalse)

102(j<,c,d,104)106

103(j,_,_,Lfalse)布尔式翻译为四元式注意:有向前转移!!7.5控制语句的翻译分三类进行讨论:7.5.1控制流语句

if–thenif–then–elsewhile-do*7.5.2标号与goto语句*7.5.3CASE语句的翻译7.5.1控制流语句控制流语句的文法：P192.

S→ifEthenS1S→ifEthenS1elseS2S→whileEdoS1

其中E是布尔表达式。与7.4节一样，先讨论对这些语句进行翻译的一般语义规则(P193.表7.8)。然后讨论如何通过一遍扫描产生上述语句的四元式代码，给出相应的翻译模式(P195.~196.)。控制流语句的代码结构及属性文法三条控制流语句的代码结构见P193.图7.17。P193.表7.8是这三条控制流语句的属性文法。用代码结构图去理解属性文法(表7.8)中给出的语义规则。该属性文法产生三地址指令。属性文法中:继承属性E.true、E.false、S.next综合属性E.code、S.code、S.begin||连接符号过程newlabel产生新的标号,标识即将产生的指令过程Gen()产生字面标号和转移指令图7.17(a)条件句的代码结构S→ifEthenS1E.true:继承属性,真出口,E为真时转移到的标号;E.false:继承属性,假出口,E为假时转移到的标号;E.code:综合属性,E的代码S1.code:综合属性,S1的代码S1.next:E.codeS1.code……E.ture:E.false:S.next:ToE.tureToE.false三个标号表示同一位置S.code..图7.17(b)条件句的代码结构S→ifEthenS1elseS2S.next:继承属性,是继S的代码之后的位置S1.next:继承属性,是继S1的代码之后的位置S2.next:继承属性,是继S2的代码之后的位置E.codeS1.codeGotoS.nextS2.code……E.ture:E.false:S.next:ToE.tureToE.falseS2.next:S1.next:三个标号表示同一位置..S.code图7.17(c)循环句的代码结构S→whileEdoS1

S.begin:综合属性,标识S代码的第1条指令,循环的开始位置E.codeS1.codeGotoS.begin……E.ture:E.false:S.next:ToE.tureToE.falseS.begin:S1.next:两个标号表示同一位置两个标号表示同一位置...S.code控制流语句翻译为三地址码：例7.5例7.5

P194.

考虑如下语句：

whilea＜bdoifc＜dthenx：=y＋zelsex：＝y-z根据表7.8的属性文法,和图7.10赋值语句的翻译模式，得到代码。

L1：ifa＜bgotoL2gotoLnextL2：ifc＜dgotoL3gotoL4L3：T1：=y＋zx：＝T1gotoL1L4：T2:=y－zx：＝T2gotoL1Lnext：控制流语句的文法：P194.

（1）S→ifEthenS（2）S→ifEthenSelseS条件句（3）S→whileEdoS循环句（4）S→beginLend复合句（5）S→A赋值句（6）L→L；S语句表(序列)（7）L→S其中E

为一个布尔表达式。使用回填技术翻译控制流语句1.用emit()过程产生不完全的转移四元式,如:(jnz,a,_,0);(j,_,_,0);(jrop,a,b,0)2.用makelist(i)函数创建一个仅包含i的新链表，i是四元式数组的一个索引(下标)，或说i是四元式代码序列的一个标号。3.一旦转移目标确定后,用backpatch(p,t)函数回填,将t填入链表p的所有四元式中。4.用merge(p1,p2)函数并链,将两条待填转移目标相同的链合并为一条。翻译考虑：使用过程和函数照这个方法,需要设置综合属性:E.truelist:真链表,E的代码中需回填真出口的四元式标号。E.falselist:假链表,E的代码中需回填假出口的四元式标号。S.nextlist:S的代码中需转移到S之后的代码处的四元式标号。L.nextlist:L的代码中需转移到L之后的代码处的四元式标号。变量nextquad

指向下一条将要产生但尚为形成的四元式标号,初值1,每执行一次emit()后值自动加1。翻译考虑：设置综合属性在文法产生式适当的地方引入标记非终结符M,以便在适当的时候执行一个语义动作,记下下一个将要产生的四元式标号,使用综合属性M.quad

来标记。SifEthenMS1

SifEthenM1S1

NelseM2S2

SwhileM1EdoM2S1引入标记非终结符N标记产生式

SifEthenS1elseS2的S1和S2之间的跳转四元式(开始也是不完全的)标号,使用综合属性N.nextlist

来标记。翻译考虑：引入标记非终结符翻译模式的说明(P195.)(1).SifEthenM1S1NelseM2S2用此产生式归约时：M1处回填E.truelistM2处回填E.falselist三链S1,S2

和N的nextlist合并,用S.nextlist标记,暂不回填E.codeS1.codeM1.quad:S2.codegotoS.next...toE.truetoE.falseM2.quad:N.nextlist:S.code翻译模式的说明(P195.)(4).SifEthenMS1

用此产生式归约时：M处回填E.truelist两条链S1.

nextlist,和E.falselist合并,用S.nextlist标记,暂不回填E.codeS1.codeM.quad:...toE.truetoE.falseS.code翻译模式的说明(P195.)(5).SwhileM1EdoM2S1

用此产生式归约时：M1处回填S1.nextlistM2处回填E.truelist传链

S.nextlist:=E.falselist产生无条件转移指令E.codeS1.codeM1.quad:gotoM1.quad...toE.truetoE.falseM2.quad:S.code(2).N{N.nextlist:=makelist(nextquad);emit(´j,_,_,0´)}产生不完全转移四元式,用N.nextlist标记(3).M{M.quad:=nextquad}用M.quad标记即将产生的下一条四元式标号控制流语句的翻译模式P195.控制流语句的翻译模式P196.(6).SbeginLend{S.nextlist:=L.nextlist}传链

(7).SA{S.nextlist:=makelist()}初始化S.nextlist为空链(8).LL1;MS{backpatch(L1.nextlist,M.quad);

L.nextlist:=S.nextlist}回填,传链(9).LS{L.nextlist:=S.nextlist}1.先记录要回填的转移指令地址(标号)，在适当的时候进行回填，以便赋值和布尔表达式的求值得到合适的连接，以完成程序的控制流程。2.上述规则中只有(2)和(5)产生新的转移四元式,(2)产生不完全的转移四元式,(5)产生完全的转移四元式,其他四元式将由赋值语句及算术表达式和布尔表达式产生。控制流语句的翻译模式:说明结合自下而上语法分析,翻译下面的句子生成四元式

while(a<b)do

if(c＜d)thenx:=y+zP196.例7.6控制流语句的翻译解:先根据控制语句的代码结构按序写出各部分的代码,适当地方加入无条件转移代码;然后分析句子的控制情况,决定转移目标,回填,拉链。四元式序列如下:100(j<,a,b,0)104(+,y,z,T)101

(j,_,_,0)105(:=,T,_,x)102

(j<,c,d,0)106(j,_,_,100)103(j,_,_,0)107102)107)104)100)结合自下而上语法分析,翻译以下句子生成四元式ifa>borc＜dande=fthenwhilex＜ydoz:=y*z

控制流语句的翻译:举例解:四元式序列如下:100(j>,a,b,0)106(j<,x,y,0)101

(j,_,_,102)107(j,_,_,0)102

(j<,c,d,0)108

(*,y,z,T)103(j,_,_,0)109(:=,T,_,z)104

(j=,e,f,0)

110(j,_,_,106)

105(j,_,_,0)111106)104)111)106)111)108)111)考虑如下语句的翻译：

whilea＜bdoifc＜dtheny:=a*belsez:=c/d

100(j<,a,b,0)101(j,_,_,0)102