第七章语义分析和中间代码产生本章概述上一章我们介绍了属性文法和语法制导翻译，本章我们将把上章所介绍的方法和技术应用于语义分析和中间代码产生中。

主要学习内容：中间语言的形式——后缀式、图表示法、三地址代码，说明语句的语义分析，赋值语句的翻译，布尔表达式的翻译，控制语句的翻译，过程调用的处理，类型检查。

学习目标：熟悉几种中间语言的描述，掌握各种语句的翻译方法，会给出各种语句的语义规则和语义子程序。

学习重点和难点：如何把属性文法和语法制导翻译的方法和技术应用于语义分析和中间代码产生中，特别是表达式和控制语句的翻译。

7.1 中间语言7.1.1 中间语言虽然源程序可以直接翻译为目标语言代码。

但是许多编译程序都采用了独立于机器的、复杂性介于源语言和机器语言之间的中间语言。

常见的中间语言形式包括：后缀式，三地址代码（包括三元式，四元式，间接三元式），DAG图表示和抽象语法树等。

1. 后缀式后缀式表示法是波兰逻辑学家卢卡西维奇（Lukasiewicz）发明的一种表示表达式的方法，因此又称逆波兰表示法。

这种表示法是，把运算量（操作数）写在前面，把算符写在后面（后缀）。

例如，把a+b写成ab+，把a*b写成ab*。

2. 抽象语法树在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。

这种经变换后的语法树称之为抽象语法树（Abstract Syntax Tree）。

3. DAG与抽象语法树一样，对表达式中的每个子表达式，DAG（Directed Acyclic Graph）中都有一个结点。

一个内部结点代表一个操作符，它的孩子代表操作数。

两者不同的是，在一个DAG 中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。

4. 三地址代码三地址代码是由下面一般形式的语句构成的序列：x:=y op z其中x,y,z为名字、常数或编译时产生的临时变量，op代表运算符号如定点运算符、浮点运算符、逻辑运算符等等。

每个语句的右边只能有一个运算符。

例如，源语言表达式x+y*z 可以被翻译为如下语句序列：T1:=y*zT2:=x+T1其中T1,T2为编译时产生的临时变量。

之所以称为三地址代码是因为每条语句通常包含三个地址，两个用来表示操作数，一个用来存放结果。

三地址语句类似于汇编语言代码。

语句可以带有符号标号，而且存在各种控制流语句。

符号标号代表存放中间代码的数组中三地址代码语句的下标。

下面是常用的三地址语句的种类：(1) 形如x:=y op z的赋值语句，其中op为二元算术算符或逻辑算符。

(2) 形如x:=op y的赋值语句，其中op为一元算符，如一元减uminus、逻辑非not、移位算符及转换算符（如将定点数转换成浮点数）。

(3) 形如x:=y的复制语句，它将y的值赋给x。

(4) 形如goto L的无条件转移语句，即下一条将被执行的语句是带标号L的三地址语句。

(5) 形如if x relop y goto L或if a goto L的条件转移语句。

第一种形式语句施用关系运算符号relop（如<, =, >, =等等）于x和y，若x与y满足关系relop，那么下面就执行带标号L的语句，否则下面就继续执行if语句之后的语句。

第二种形式的语句中，a为布尔变量或常量，若a为真，则执行带标号L的语句，否则执行后一条语句。

(6) 用于过程调用的语句param x和call p,n，以及返回语句return y。

源程序中的过程调用语句p(x1,x2,…,x n)通常产生如下的三地址代码：param x1param x2……param x ncall p,n其中n表示实参个数。

过程返回语句return y中y为过程返回的一个值。

(7) 形如x:=y[i]及x[i]:=y的索引赋值。

前者把相对于地址y的后面第i个单元里的值赋给x。

后者把y的值赋给相对于地址x后面的第i个单元。

(8) 形如x:=&y, x:=*y和*x:=y的地址和指针赋值。

其中第一个赋值语句把y的地址赋给x。

第二个赋值语句x:=*y执行的结果是把y所指示的地址单元里存放的内容赋给x。

第三个赋值语句*x:=y，将把x所指向的对象的右值赋为y的右值。

三地址语句可看成中间代码的一种抽象形式。

编译程序中，三地址代码语句的具体实现可以用记录表示，记录中包含表示运算符和操作数的域。

通常有三种表示方法：四元式、三元式、间接三元式。

1. 四元式一个四元式是一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result。

域op包含一个代表运算符的内部码。

三地址语句x:=y op z可表示为：将y置于arg1域，z 置于arg2域，x置于result域，:=为算符。

带有一元运算符的语句如x:=-y或者x:=y的表示中不用arg2。

而象param这样的运算符仅使用arg1域。

条件和无条件转移语句将目标标号置于result域中。

2. 三元式为了避免把临时变量填入到符号表，我们可以通过计算这个临时变量值的语句的位置来引用这个临时变量。

这样表示三地址代码的记录只需三个域：op、arg1和arg2。

因为用了三个域，所以称之为三元式。

3. 间接三元式为了便于代码优化处理，有时不直接使用三元式表，而是另设一张指示器（称为间接码表），它将按运算的先后顺序列出有关三元式在三元表中的位置。

换句话说就是，我们用一张间接码表辅以三元式表的办法来表示中间代码。

这种表示法称为间接三元式。

7.2说明语句7.2.1 说明语句当考查一个过程或分程序的一系列说明语句时，便可为局部于该过程的名字分配存储空间。

对每个局部名字，我们都将在符号表中建立相应的表项，并填入有关的信息如类型、在存储器中的相对地址等。

相对地址是指对静态数据区基址或活动记录中局部数据区基址的一个偏移量。

当产生中间代码地址时，对目标机一些情况做到心中有数是有好处的。

例如，假定在一个以字节编址的目标机上，整数必须存放在4的倍数的地址单元，那么，计算地址时就应以4的倍数增加。

在C、Pascal及FORTRAN等语言的语法中，允许在一个过程中的所有说明语句作为一个组来处理，把它们安排在一所数据区中。

从而我们需要一个全程变量如offset来跟踪下一个可用的相对地址的位置。

允许嵌套过程的语言，对于每一个过程，其中局部名字的相对地址计算与前述一样。

而当遇到一个嵌入的过程说明时，则应当暂停包围此过程的外围过程说明语句的处理。

对于记录中的域名同样可以类似地给它建立一张符号表。

7.3 赋值语句的翻译7.3.1 赋值语句的翻译对于简单算术表达式及赋值语句,把它们翻译为三地址代码的翻译模式是比较好理解的,如下所示。

S→id:=E {p:=lookup();if p nil thenemit(p ‘:=’ E.place)else error}E→E1+E2{E.place:=newtemp;emit(E.place ‘:=’ E1.place ‘+’ E2.place)}E→E1*E2 {E.place:=newtemp;emit(E.place ‘:=’ E 1.place ‘*’ E 2.place)}E→E1{E.place:=newtemp;emit(E.place‘:=’ ‘uminus’E 1.place)}E→(E1) {E.place:=E1.place}E→id {p:=lookup();if p nil thenE.place:=pelse error }产生简单算术表达式及赋值语句三地址代码的翻译模式如果表达式和赋值句中包含数组元素的引用，则编译程序要根据数组元素的地址计算公式产生相应的代码。

为了便于翻译，我们把包含数组元素引用的表达式和赋值句的产生式改写成如下形式：(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{if L.offset=null then /*L是简单变量*/emit(L.place ‘:=’ E.place)else emit(L.place ‘ [’ L.offset‘]’ ‘:=’ E.place)}E→E1 +E2{E.place:=newtemp;emit(E.place ‘:=’ E 1.place ‘+’ E 2.place)}E→(E1){E.place:=E1.place}E→L{if L.offset=null thenE.place:=L.placeelse beginE.place:=newtemp;emit(E.place ‘:=’ L.place ‘[’ L.offset ‘]’)end }L→Elist ]{L.place:=newtemp;emit(L.place ‘:=’ Elist.array ‘－’ C);{C的定义见（7.7）} L.offset:=newtemp;emit(L.offset ‘:=’ w ‘*’ Elist.place)}L→id{ L.place:=id.place; L.offset:=null }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}Elist→id [ E{Elist.place:=E.place;Elist.ndim:=1;Elist.array:=id.place}含数组元素引用的表达式和赋值句的翻译模式7.4 布尔表达式的翻译7.4.1 布尔表达式的翻译在程序设计语言中，布尔表达式有两个基本的作用：一个是用作计算逻辑值；另一个，也是更多地是用作控制流语句如if-then、if-then-else和while-do等之中的条件表达式。

作为逻辑求值的布尔表达式的翻译与简单算术表达式的翻译类似，较易理解。

重点是作为条件控制的布尔表达式的翻译。

出现在条件语句if E then S1 else S2中的布尔表达式E，它的作用仅在于控制对S1和S2的选择。

只要能够完成这一使命，E的值就无须最终保留在某个临时单元之中。

因此，作为转移条件的布尔式E，我们可以赋予它两种“出口”。

一是“真”出口，出向S1；一是“假”出口，出向S2。

对于作为转移条件的布尔式，我们可以把它翻译为一串跳转指令。