第8章语法制导翻译与中间代码生成

例8.2 描述说明语句中各种变量的类型信息的语义规则
产生式
DTL
语义规则
Lin:=T type
T int
T real
T type :=integer
T type :=real
L L1,id
L id
L1 in :=L in
addtype(id entry,L in) addtype(id entry,L in)
1） 2） 3） 4） 5） 6） 7） 8） 9） 10） 11） 12） 13） 14） 15）
r6 r4 r2 r6 r4
r6 r3 r1 接受
016975 01697(10) 169 01
—2—3— — —2—3—5 —2—(15) -17
#E+T*5 #E+T*F #E+T #E
2+3*5# +3*5# +3*5# +3*5# +3*5# 3*5# *5# *5# *5# 5# # # # #
自下而上的。在用某一产生式进行归约的同时就
执行相应的语义动作，在分析出一个句子时，这
个句子的“值”也就同时产生了，例如输入串是 3*5+4。
L
E.val=19 E.val=15
+
T.val=4 F.val=4 F.val=5 digit.lexval=4 digit.lexval=5
T.val=15
8.3 中间代码形式
所谓“中间代码”是一种结构简单、含义明 确的记号系统，这种记号系统可以设计为多种多 样的形式，重要的设计原则为两点：一是容易生 成；二是容易将它翻译成目标代码。编译程序所 使用的中间代码有多种形式。 常见的有逆波兰记号、三元式、四元式和树 形表示。

E.val=2 + E.val=4 n.lex=2 ( E.val=4 )
E.val=3 + E.val=1 n.lex=3 n.lex=1
例8.1 一个简单台式计算器的定义 综合属性val
产生 式
LE
E E1+T
ET T T1 * F TF
F (E) F digit
语 义 规 那么 Print(E.val)
r1 = [fp - 4] r2 = [r1 + 2] r3 = [fp - 8] r4 = r3 * 20 r5 = r4 + r2 r6 = 4 * r5 r7 = fp – 216 f1 = [r7 + r6]
8.3.1 逆波兰式
运算符跟在一切运算对象的后面的表 示法写出的式子称为后缀法或逆波兰 法。
#
.
a.
(b+c/d)#
* #
.
a.
b+c/d)#
( * #
.
ab.
+c/d)#
( * #
.
ab.
c/d)#
+ ( * #
.
abc.
/d)#
+ ( * #
.
abc.
d)#
/ + ( * / + ( * #
.
abcd/.
)#
+ ( * #
.
abcd/+.
)#
( * #
〔3〕一致性检查。在很多场所要求对象只能被 定义一次。例如Pascal言语规定同一标识符在一 个分程序中只能被阐明一次，同一case语句的标 号不能一样，枚举类型的元素不能反复出现等等。
〔4〕上下文相关性检查。比如，变量名字必 需先声明后援用；

图1 3*5+4的注释分析树
14
第8章
语法制导翻译和中间代码生成
D
继承属性
例2. 类型定义的语法制导定义（L.in为继承属性）。
产生式
(1)DTL (2)Tint
语义规则
L.in:=T.type T.type:=integer
Type
T L1 id1
L
(3)Treal T.type:=real
9
第8章 语法制导翻译和中间代码生成
3 语法制导定义
一个结点的综合属性值是从其子结点的综合属性值计算得来的，综 合属性用于自下而上传递信息；而继承属性则是由语法树中该结点 的父结点和位于其左边的兄弟结点的属性值计算出来的，继承属性 用于自上而下传递信息。 （1）非终结符既可有综合属性也可有继承属性，但文法开始符号 没有继承属性。 （2）终结符只有综合属性，它们由词法分析程序提供。 我们将每个结点都带有属性值的语法分析树称为注释分析树。计算 结点属性值的相关活动称为注释或装饰语法树。
21
8.2.1 翻译文法
如何构造翻译文法？ 翻译文法的构造方法可通过对输入文法修改得到。对输入文法 的产生式，在其右部的适当位置插入动作符号就形成翻译文法。因 此，翻译文法产生的动作序列实际上是受输入语言的文法控制的。 按语法制导翻译的方法来实现语言的翻译，就要根据输入语言 的文法，分析各条产生式的语义，即分析他们要求计算机所完成的 操作，分别编出完成这些操作的子程序或程序段(称为语义子程序 或语义动作)，并把这些子程序或程序段的名字作为动作符号插入 到输入文法各产生式右部的适当位置上，从而实现翻译文法。
10
第8章 语法制导翻译和中间代码生成
3 语法制导定义
定义1 语法制导定义

A ∨ B→if A then true else B A ∧B→if A then B else false ┐ A →if A then false else true
这种翻译法涉及到如何翻译if-thenelse的问题，将在下面具体讨论。
33
控制语ห้องสมุดไป่ตู้中布尔表达式的翻译
if E then S1 else S2,其中E为布尔式
第8章 语法制导翻译和中间代码生成
经过词法分析、语法分析后，源程序 在静态结构上的正确性得到了保证，编译 程序接着要对源程序进行静态语义检查和 翻译。 语义检查：类型检查、控制流检查、 一致性检查等。 翻译：源程序→中间代码
1
本章主要内容
1. 属性文法 2. 语法制导翻译概念 3. 中间代码的几种形式 4. 几个语句的翻译：如赋值语句、条件语 句等。
26
翻译 a:= -b+c*d
Ｓ
t1:=uminus b t2:=c*d t3:=t1+t2
a
:=
Ｅ1
Ｅ
＋ Ｅ2 Ｅ 21 c ＊
a:=t3
－
Ｅ 11 b
Ｅ 22 d
27
类型转换
如：X := Y + I * J，X,Y为实型，I,J为整型， 则相应的四元式序列应为： – (*i , I , J , T1 ) – ( itr , T1 , _ , T2 ) – ( +r , Y , T2 , T3 ) – ( := , T3 , _ , X )
23
四元式
1. 四元式对中间结果的引用必须通过 给定的名字，而三元式是通过产生中间结 果的三元式编号。四元式之间的联系是通 过临时变量实现的。 2. 四元式出现顺序与原表达式计算顺 序一致。(同三元式)