编译原理（十三）——中间代码生成（1）

编译原理（十三）——中间代码生成（1）

一、生成中间代码的目的

1. 便于优化
   让生成的目标代码效率更高
   优化不等同于对代码的精简和算法的优化
   （对于高级程序设计语言中可能不能继续进行优化，但是仍然可以在编译中进行优化）
   比方说多维下标变量地址计算过程，比方说a[i][j]和 a[i][k]，我们在计算他们的地址的时候都先要计算a[i]的地址然后再计算j k 的地址，实际上a[i]的计算过程实际上是重复计算了
2. 便于移植
   编译前端：与目标机无关
   编译后端：与目标机相关
   中间代码起到一个将一对一翻译转换成一对多对一的关系，通过编译前段可以不用改变，编译后端根据目标机相关需要变化，把编译前端的工作做的越多越好。比如java多平台开发，依赖java字节码

二、中间代码结构

2.1 三元式

1. 计算顺序确定，逐条执行即可，不用考虑后序顺序问题
2. 结果没有单独运算分量表示，使用指令的标号表示，在指令优化的时候比较麻烦，比如某些指令执行完之后vanish，标号消失就得重新命名

2.2 逆波兰式

2.3 抽象语法树

2.4 四元式（tag——本课程使用）

1. 基本结构解释：第一个式操作符，后面两个是操作数按照第一个操作符来进行运算，结果保留在第四个element（中间变量）中
2. t1相当于之前所说的中间变量保存中间的运行结果，和三元式不同的地方就在于有中间变量表示每条的运行结果
3. 算术、逻辑、关系运算符（可以在具体文法规则中插入下面的相关运算）

ADDI(整数加)、ADDF(浮点数加)、SUBI、SUBF、MULTI、MULTF、DIVI、DIVF、MOD
AND、OR、EQ、NE、GT、GE、LT、LE
READI,READF,FLOAT,

4. 在运行文法的时候遇到时随时解释

三、语法制导方法

如何创建四元式？语法制导技术在处理和规则相关联的任务中有着重要的应用

1. 语法制导就是在进行语法分析的同时要完成相应的语义动作（语法分析过程中插入自己所写的执行其他功能的函数），这些语义动作都是由一些程序组成的，要完成和用户的需求相关联的任务
2. 编译器对一个串进行语法检查的同时，可以按照语法分析的程序的结构对程序进行我们所需要的操作，从而解决我们想要解决的问题

INIT 添加到S开始头部——sum=0；
则有: S-> #Init# AB
A-> aA│ b #Add#
B-> b #Add# B│c #Out#
其中：
Init：m = 0;
Add : m++ ;
Out ：print(m);

起始符S首先进入符号栈，然后使用S的右侧代替S得到#init# AB，执行#init#使得m=0；执行完之后剩下AB#，不能与输入流中的字符消去；继续将A使用aA代替得到aAB，将输入流中的a和符号栈中的a匹配掉得到AB；没有匹配的，继续使用文法的右部进行替换，这次选择替换的指令是A->b# Add#，将b匹配上，然后剩下# Add# B,执Add，然后剩下B#，后面和前面的运行步骤相同，最后剩下#则证明成功实现。

匹配过程中仍然按照原来的规则选择语法压入符号栈，在进行匹配之前直接执行插入的相关操作，然后继续进行匹配

四、中间代码生成中的几个问题

四元式当前的表示形式是便于直接读写的方式，而实际上存储在x和y的不是x和y的符号，而是一个指向xy在符号表中位置的指针。
将语义信息（种类信息，类型信息，抽象地址）写在四元式中，但是如果全部写入会出现大量的冗余信息，所以最好的一种方式是指向对应存在语义信息的符号表中的指针，需要信息的时候直接通过指针在符号表中提取出所需信息。

五、表达式的中间代码生成

具体表达式的四元式生成的语义程序写法：

自底向上只能添加在末尾，在归约的时候才能执行添加操作。

Gen表示生成四元式的函数
将栈顶元素按照四元式进行计算之后将栈顶元素取出计算将结果压栈


首先画出其语法树，然后使用自底向上的方法看能否生成相应的四元式，过程如下：