编译原理7.1-中间语言.ppt

1、第七章 语义分析和中间代码生成,7.1 中间语言 7.2 说明语句 7.3 赋值语句的翻译 7.4 布尔表达式的翻译 7.5 控制语句的翻译 7.6 过程调用的处理 7.7 类型检查,7.1 中间语言,7.1.1 后缀式 7.1.2 图表示法 7.1.3 三地址代码,为什么引入中间语言?,许多编译程序采用了独立于机器的、复杂性介于源语言和机器语言之间的中间语言。 (1) 便于进行与机器无关的代码优化工作 (2) 使编译程序改变目标机更容易 (3) 使编译程序的结构在逻辑上更为简单明确, 编译前端和后端的接口更清晰,7.1.1 后缀式,后缀式表示法又称逆波兰表示法。 把运算量(操作数)写在前面，

2、把算符写在后面,a + b * -c ，其后缀式为 a b c * + a := b* -c + b * -c，其后缀式为 a b c * b c * + assign if ab then c := c + 1 ，其后缀式为 a b c c 1 + assign IF-THEN,表7.1 把表达式翻译成后缀式的语义规则描述,后缀式的连接,E的后缀式,参考输出后缀式的属性文法,后缀表示法的优点,方便具有堆栈体系的计算机的目标代码生成 适用于解释执行的程序设计语言的中间表示 24*5 的后缀式为 245*+,2,2,5 4 2,20 2,18,a） b） c） d） e）,7.1.2 图表示法,

3、DAG 无循环有向图 (Directed Acyclic Graph) 抽象语法树,DAG,在一个DAG中, 代表公共子表达式的结点具有多个父结点,图7.2 a + a * ( b c ) + ( b c ) * d 的DAG,公共子表达式,公共子表达式,图7.3 a:= b * c + b * c 的图表示法,图7.4 抽象语法树的两种表示法,(a) 链表,(b) 数组,10,9,8,3,0,2,1,6,5,7,4,7.1.3 三地址代码,三地址代码 是由下面一般形式的语句构成的序列： x := y op z x, y, z 为名字、常数或编译时产生的临时变量 op 代表运算符号 例: 表达

4、式 x + y * z 可以被翻译为如下语句序列： T1 := y * z T2 := x+T1 Tl，T2为编译时产生的临时变量,三地址代码可以看成抽象语法树或DAG的一种线性表示,T1 := - c T2 := b* T1 T3 := - c T4 := b* T3 T5 := T2+ T4 a := T5,对于抽象语法树的代码,b,uminus,*,b,uminus,a,+,assign,*,c,c,(a) 抽象语法树,T1,T2,T3,T4,T5,T5,T1 := - c T2 := b* T1 T5 := T2+ T2 a := T5,对于DAG的代码,T1,T2,T5,T5,教材中

5、所使用的三地址语句的种类,(1) 形如 x := y op z 的赋值语句, op 为二元算符算符 (2) 形如 x := op y 的赋值语句，op 为一元算符 (3) 形如 x := y 的赋值语句 (4) 形如 goto L 的无条件转移语句 (5) 形如 if x relop y goto L 或 if a goto L 的条件转移语句 (6) 过程调用的语句 param x 和 call p, n， 以及返回语句 return y (7) 形如 x:= yi 、 xi:=y 的索引赋值 (8) 形如 x:=&y、 x:=*y 、 *x:=y 的地址和指针赋值,产生三地址代码的属性文法

6、不作为考试要求,newtemp : 返回一个不同的临时变量的名字 E.place : 存放E值的名字, 存放E值的变量在符号表中的登录项。(指针) E.code : 对E求值的三地址语句序列 gen : 生成三地址语句,表7.3 对赋值语句产生三地址代码的属性文法,三地址语句可看成中间代码的一种抽象形式 在编译程序中, 三地址代码语句的具体实现可以用记录表示, 通常有三种表示形式: 四元式： （ op, arg1, arg2, result ） 三元式： （ op, arg1, arg2 ） 间接三元式,1. 四元式,(op, arg1, arg2, result),四元式可被看作一种虚拟三地

7、址机的通用汇编码，每条“指令”包含操作符和三个地址。,a:= b * c + b * c,T1 := - c T2 := b* T1 T3 := - c T4 := b* T3 T5 := T2+ T4 a := T5,四元式,三地址语句,四元式写成简单赋值形式,a := b*c + b*d 把上述四元式序列写成：（1）t1=b*c（2）t2=b*d（3）t3=t1+t2（4）a =t3,2. 三元式,(op, arg1, arg2),为了避免把临时变量填入到符号表，可以通过计算这个临时变量值的语句 的位置 来引用这个临时变量 arg1和 arg2，或者指向符号表中的指针，或者指向三元式表的指

8、针（临时变量）。,a:= b * c + b * c 的三元式,T1 := - c T2 := b* T1 T3 := - c T4 := b* T3 T5 := T2+ T4 a := T5,标号有存储空间,存放结果,参与后面运算,3. 间接三元式,(op, arg1, arg2),运算的先后顺序由一张间接码表列出,三元式 (1) (+ , A , B ) (2) (* , (1) , C ) (3) (+ , A , B ) (4) (* , (3) , D ) (5) (+ , (2) , (4) ) (6) (= , S , (5) ),S=(A+B)*C+(A+B)*D,间接三元式 (1) (+ , A , B ) (2) (* , (1) , C ) (3) (* , (1) , D ) (4) (+ , (2) , (3) ) (5) (= , S , (4) ),间接码表 (1) (2) (1) (3) (4) (5),例如，语句 X:= (AB)*C； Y:= D(AB) 的间接三元式表示如下表所示。,表7.6 间接三元式表示,间接码表 间接码表 三元式表 （ * , b , c ） （ / , d , f ） （ + , ,