四、语义分析

在经过了词法和语法分析后，能够表明该源程序在书写上是没有语法错误的，因此可以开始进行翻译。采用的方法是语法制导翻译。

语法制导翻译

为每个产生式配上一个翻译子程序，如果使用过JavaCC就可以很清楚地理解这个意思了，在每个分析函数之后都会加上对应的处理代码。

属性文法

语义分析的一个工具，给文法符号附加一些属性，比如place、value、type等。用于描述变量的存储位置、类型、值。

逆波兰表达式（也叫后缀式）

表达式的逆波兰表示

常规计算一个算术表达时，由于运算符的优先级不同，在计算完一个子式后需要回过头去看前面的运算符，这对于计算机而言是不便于实现的。因此逆波兰表达式通过改写算术表达式的书写方式，使得计算机从左向右扫描一遍就能计算出结果，大大方便了实现过程。

逆波兰表示的递归定义：
（1）如果E是变量或常数，则E的后缀表示即E的本身
（2）如果E为 E₁ op E₂ 的形式则它的后缀表示为E₁’ E₂’ op，其中op为二元运算符，E₁’ E₂’ 又分别是E₁ E₂ 的后缀表示。如果op为一元运算符，则E₁ 和 E₁’ 为空
（3）如果E为(E₁)的形式，则E₁的后缀表示即E的后缀表示

逆波兰表示的计算方式：
从左向右扫描，遇到变量就将其入栈，遇到运算符就将栈顶的元素弹出进行计算，计算完后将结果压回。

由于网络上有很多逆波兰表达式的介绍，在这里就不进行赘述了。

下面列举几个例子：

• a+b 表示成 ab+
• a*(b+c)表示成 abc+*
• (a+b)*(a-c)-d 表示成 ab+ac-*d-

程序语句的逆波兰表示

• 赋值语句
  <左部> = <表达式> 的逆波兰表示为 <左部><表达式>=
  x = a + b * c 的逆波兰表示为 xabc*+=

• GOTO语句
  GOTO<语句标号> 的逆波兰表示为 <语句标号>BL
  GOTO 10 的逆波兰表示为 10BL

• 条件语句
  <布尔表达式e的逆波兰式><顺序号>BT/BF
  BT表示为真的时候跳转，BF表示为假的时候跳转
  if(m<n) k=i+1；else k=i−1 的逆波兰表示为：
  mn< 13 BFki1+= 18 BRki1−=
  这里的跳转数字表示逆波兰表达式里的字符编号

• 循环语句
  循环语句不能直接表示成逆波兰表达式，而是将其展开成等价的条件语句
  例如：for(i=m；i<n；i++)S
  展开后为：
  i=m;
  10: if(i<n)
  {
   S;
   i++;
   GOTO 10;
  }

三地址码

几种三地址码语句的形式为：
op为二元运算符：x = y op z
op为一元运算符：x = op y
赋值语句：x = y
跳转语句：goto L
条件语句：if x rop y goto L
过程调用：par X
过程调用：call P,n

四元式

四元式是定义操作的一种方式（中间代码），一共有四个域：
(op, arg1, arg2, result)
op为运算符，arg1, arg2, result为指针，指向变量的地址。

下面是一些常用的四元式：

如果操作符前面带 j 说明这是一条跳转语句，result是跳转的位置，例如：
j 表示无条件跳转
j< 表示 arg1 < arg2 就跳转 到 result 位置的四元式
jnz 表示arg1为真时跳转（jump if not zero）

如果是一元运算符，默认只使用arg1，不使用的位置填入 _

在本章中，主要介绍如何将输入源代码翻译成一连串的四元式。

表达式的翻译

算术表达式

在翻译算术表达式的时候，需要定义临时变量来存放中间运算结果，一般为T_i

以x=(a+b)*(a-c)-d 为例进行翻译
翻译成四元式就是（这里默认四元式的编号从100开始）：

x=(a+b)*(a-c)-d 的逆波兰表达式为：xab+ac-*d-=
可以看到四元式的翻译结果就是逆波兰表达式的计算过程。
因此借助逆波兰表达式能够非常方便地进行表达式的翻译。

布尔表达式

因为布尔表达式一般只在控制语句中出现，一旦确定了结果就会进行跳转。

比如下面这段代码，如果a不等于1，那么就会跳过后面的部分，直接进行跳转，因为这时候b是否等于1对结果已经没有影响了。

if(a==1 && b==1) c=1;
1

翻译成四元式就是：
100 (j≠,a,1,103)
101 (j≠,b,1,103)
102 (=,1,_,c)

当然，上面这段代码并不是一个布尔表达式，只是在翻译的时候采取和布尔表达式一样的策略。

对于布尔表达式，我们用∨表示或，用∧表示与。
对于表达式：a∨b∧c∨d
当我们可以确定这个表达式的值为真时，要跳转的位置称为真出口，反之则为假出口，但是在分析的时候我们是不能一下子确定这个位置是在哪里，因此要先留空，等确定后再进行回填。
如果有多个要回填的四元式，我们可以用一条链将相同跳转位置的四元式连接起来，最后一起填入，这就是所谓的拉链-回填。

三元式

控制语句的翻译

条件语句if-else

下面是一个练习：

if (x > y)
	if(a && b)
		m = m + 1;
	else
		m = m - 1;
else
	x = y;
1
2
3
4
5
6
7

可以画一个转移图来辅助翻译


实际上这个四元式可以进行优化，比如107的四元式跳转到109后又进行了跳转，那么就可以改写成107直接跳转到111。但这部分就属于代码优化的内容了，语义分析只要能够生成正确的中间代码即可。

循环语句while

就和逆波兰表达式里的做法一样，将while展开成条件语句后再进行翻译。

对于下面的代码：

while(a < b)
	if(c < d) 
		x = y + z;
1
2
3

我们可以改写为：

flag:if(a < b)
{
	if(c < d)
		x = y + z;
	goto flag;
}
1
2
3
4
5
6

然后进行翻译：

其实也可以直接进行翻译，无需进行改写，和条件语句相比只是在最后加了一条跳转语句而已。

比如将上面的while改成if

if(a < b)
	if(c < d) 
		x = y + z;
1
2
3

那么翻译的结果就是：

可以看到只是最后少了一条跳转语句，以及101语句的跳转地址减1了而已。

数组元素的翻译

在进行数组元素的翻译前我们先来了解一下数组是怎么存储的：
如果是一维数组，那么就是内存中一块连续的空间。
二维数组实际上还是一块连续的空间，只是有按行和按列存储两种方式，这里只讨论按行存储。
这是一个示意图，分别表示了按行存储和按列存储的方式：

书上的内容比较难理解，而且又多，这里仅用一个例子进行解释：

• 已知A是一个10x20的数组，按行存放(也就是一行20个元素)，每维的下界值为1（也就是下标从1开始），A同时也表示数组首个元素的地址
  翻译赋值语句的 X=A[i][j] 的四元式序列：
  首先计算出一维的地址：A+20*(i-1)+j-1=A+20i+j-21，然后就可以进行翻译了
  
  如果要对数组进行赋值，则使用[]=运算符

对于语句103，书上的例子都是用 T_i[T_j] 的形式表示数组中元素的地址，一般 T_i 为一维地址中的A+常数部分, T_j 为 ai + bj 的部分