【编译原理复习专题5】中间代码生成
文章目录
中间代码生成就是把经过语法分析和语义分析的源程序中间表示翻译为中间代码展示,中间表示可能有多个种类,如语法树、DAG、后缀式、三地址代码等。
如果中间代码独立于机器的话,那么各便于编译系统的建立和移植,并且便于进行独立于机器的代码优化工作。
三地址代码
三地址代码包含一个运算和三个地址,两个地址用于存放运算对象,一个用于存放运算结果。
具体实现:四元式、三元式、间接三元式。
四元式
op、arg1、arg2、result
三元式
op、arg1、arg2 使用运算x op y 的位置来表示计算的结果
间接三元式
类型和声明
类型表达式是用于表示类型的结构的,如基本类型int、char、float,
类型表达式名也是类型表达式。
类型构造算子:作用于类型表达式可以构造新的类型表达式。
数组构造符array
类型 | 类型表达式 |
---|---|
int[3] | array(3,int) |
int[2][3] | array(2,array(3,int)) |
指针构造符pointer
笛卡尔乘积构造符x
函数构造符->
记录构造符record
类型检查 type checking
保证参与的运算分量和运算符预期的类型相匹配。
如果两个类型表达式相等,那么返回某种类型,否则出错
类型等价
两种类型之间结构等价当且仅当下面某个条件为真:
1.是相同的类型
2.是相同的类型构造算子应用于结构等价的类型而构造得到的。
3.一个类型是另一个类型表达式的名字
类型检查有两种形式:类型综合和类型推导。
类型综合是根据子表达式的类型构造出表达式的类型,要求名字先声明再使用。表达式$E1+E2$的类型是根据$E1$和$E2$的类型定义的。
类型推导是根据一个语言结构的使用来确定结构的类型,就类似如果使用了某个类型才能用的函数的话,那么可以指出使用该函数的变量就是对应的类型。
类型转换
浮点数和整型相加,编译器内部需要进行转换。
不同的语言有不同的类型转换,主要转换有两种:拓宽转换(保持信息)、窄化转换(丢失信息)。
类型翻译
类型的声明
语义分析在遇到声明语句时,主要做两件事情:1.收集标识符的类型等属性信息;2.为每一个名字分配一个相对地址。
声明的SDT
表达式和赋值语句的翻译
为赋值语句生成三地址码的SDD
gen 一个函数,生成括号内代表信息的三地址码
Production | Semantic Rules |
---|---|
$S\rightarrow id=E$ | $S.code=E.code |
$E\rightarrow E_1+E_2$ | $E.addr=new Temp()$, $E.code=E1.code |
$E\rightarrow -E_1$ | $E.addr=new Temp()$ ,$E.code=E_1.code |
$E\rightarrow (E_1)$ | $E.addr=E1.addr$,$E.code=E_1.code$ |
$E\rightarrow id$ | $E.addr=top.get(id.lexeme)$, $E.code=’’$ |
将$a=b+-c;$ 编译成三地址码:
$S\Rightarrow id=E_0;$
$\Rightarrow id=E_1+E_2;$
$\Rightarrow id=E_1+-E_3;$
$\Rightarrow id=E_1+-id;$
$\Rightarrow id=id+-id;$
产生式 | 属性变化 |
---|---|
$E_1\rightarrow id$ | $E_1.addr=addr(b)$, $E_1.code=’’$ |
$E3\rightarrow id$ | $E_3.addr=addr(c)$, $E_3.code=’’$ |
$E_2\rightarrow -E_3$ | $E_2.addr=t1$ ,$E_2.code=E_3.code |
$E_0\rightarrow E_1+E_2$ | $E_0.addr=t2$,$E_0.code=E_1.code |
$S\rightarrow id=E_0$ | $S.code=E_0.code |
刚好三行就是赋值语句的三地址码。
布尔表达式的翻译
短路代码
跳转代码中&& || !都被翻译成跳转指令。
语句:
1 | if(x<100||x>200 && x!=y) |
三地址代码:
1 | if x<100 goto L2 |
其实运算符并不在代码中,布尔表达式的值是通过代码序列中的位置来表示的。
控制流语句
控制流语句:(S表示语句,B表示布尔表达式)
1.$P\rightarrow S$
2.$S\rightarrow assign$
3.$S\rightarrow if(B) S1$
4.$S\rightarrow if(B) \quad S1 \quad else \quad S2$
5.$S\rightarrow while(B)\quad S1$
6.$S\rightarrow S1 \quad S2$
SDD
$P\rightarrow S$ | $S.next=newlable()$ |
$S\rightarrow assign$ | $S.code=assign.code$ |
$S\rightarrow if(B) S1$ | $B.true=newlabel()$,$B.false=S_1.next=S.next$, $S.code=B.code |
$S\rightarrow if(B) \quad S1 \quad else \quad S2$ | $B.true=newlabel()$,$B.false=newlabel()$,$S_1.next=S_2.next=S.next$,$S.code=B.code |
$S\rightarrow while(B)\quad S1$ |
(1) $B\rightarrow E1 \quad rel \quad R2$ (假设形如$a<b$)
$B.true: if \quad a<b\quad goto \quad B.true$ (j<,a,b,B.true)
$B.FALSE: goto B.false$ (j,,,B.false)
(2) B是常量, 就直接翻译为跳转指令。
(3) 不需要为$B\rightarrow!B$产生新的代码,只需要将真假出口交换就可以了。(继承属性)。
(4) 对$B\rightarrow B1||B2$,
如果B1为真则B为真,B1.true从B.true继承而来,如果B1为假,则对B2求值,B1.false就可以设置为B2的代码的第一条指令的标号。B2的真假出口标号可直接从B继承获得。
原文作者: Ruoting Wu
原文链接: https://codingclaire.github.io/2020/05/23/%E4%B8%AD%E9%97%B4%E4%BB%A3%E7%A0%81%E7%94%9F%E6%88%90/
许可协议: 知识共享署名-非商业性使用 4.0 国际许可协议