语义分析和语法制导翻译-编译原理-06-(二)

E.p
是语法结构树指针 是名字的表项入口 是数值
id.entry num.val
树构造函数
mknode 建中间结点 mkleaf 建叶结点
生成语法树的属性文法
产生式 S→id:=E 语义规则 S.p:= mknode(':=', mkleaf(id, id.entry), E.p)
E→E1+E2 E.p:= mknode('+', E1.p, E2.p) E→E1*E2 E.p:= mknode('*', E1.p, E2.p) E→ -E1 E→ (E1) E→ id E→ num E.p:= mknode('-', 0, E1.p) E.p:= E1.p E.p:= mkleaf(id, id.entry) E.p:=mkleaf(num,num.val)
翻译模式的设计
D → T { L.in := T.type } L T → int { T.type := integer } T → real { T.type := real } L → { L1.in := L.in } L1 , id { addtype(id.entry, L.in) } L → id { addtype(id.entry, L.in) }
从其兄弟结点和父结点的属性值计算出来的 如：L.in
固有属性（单词属性）
属性的计算
构造语法分析树，填加响应的语义规则 综合属性
自底向上按照语义规则来计算各结点的综
合属性值
继承属性
需要探讨计算次序
例6-3：3*5+4 的
语法树与属性计算
E.val=15 T.val=15 T.val=3 F.val=3 digit.attr=3 ＊
b c 0 0 b 34 0 4 3 a 9
1 2 5 6 7 8
三地址代码
一般形式 x := y op z
其中
x, y, z 为变量名、常数或编译 产生的临时变量 x, y, z）
双目运算 单目运算 赋值 条件转移
四元式（op,
种类：x := y op z x := op y x := y if x relop y goto l
entry addtype
语义规则 L.in := T.type T.type := ‘integer’ T.type := ‘real’ L1.in := L.in addtype( id.entry, L.in ) addtype( id.entry, L.in ) 单词 id 的属性(符号表入口) 在符号表中为变量填加类型信息
包括：控制结构、数据结构、单词 充分了解它们的实现方法
目标语言的语义
了解中间代码的语义 了解运行环境
实现赋值语句的翻译
语义过程
产生一条中间代码 产生新的临时变量
gen(code) newtemp
属性设置
中间代码序列 存储位置
code
place
赋值语句的四元式翻译
S → id := E S.code := E.code || gen( id.place':='E.place ) E → E1 + E2 E.place := newtemp; E.code := E1.code || E2.code || gen(E.place':='E1.place'+'E2.place) E → E1 * E2 E.place := newtemp; E.code := E1.code || E2.code || gen(E.place':='E1.place'*'E2.place)
attr print(
语义规则 print( E.val ) E.val := E1.val + T.val E.val := T.val T.val := T1.val * F.val T.val := F.val F.val := E.val F.val := digit.attr
是单词 digit 的属性 val ) 是输出函数
习题
1. 下列文法是一个二进制数的文法。试根据 该文法，编写一个语法制导定义，描述由 S 生成的二进制数的数值计算。 S -> L . L L -> L B | B B -> 0 | 1 2. 参照下列表达式文法编写语法制导定义， 描述表达式的类型计算。要求在不同精度的 数的计算中，结果取精度高的类型。 E -> E + T | T T -> n.n | n

语义规则 L.in := T.type T.type := ‘integer’ T.type := ‘real’ L1.in := L.in addtype( id.entry, L.in ) addtype( id.entry, L.in )
将语义动作中的计算向前移，使继承属性的计 算出现在其文法符号之前
E → - E1 E → ( E1 ) E → id E → num
E.place := newtemp; E.code := E1.code || gen(E.place':=0-'E1.place) E.place:= E1.place; E.code:= E1.code E.place:= id.place; E.code:= ' ' E.place:= num.val；E.code:= ' '
例6-6：a := b * (- c) + b *
root
(- 34) 的语法结构树
:= id a + * id b * id b - 0 id c - 0 num 34
地址 算符 操作数 操作数 0 1 2
语法结构树的 三元式表示
3 4 5 6 7 8 9 10
id id * id num * + id :=
需求：算术表达式的求值 设计：
编制算术表达式的文法 引入属性表示语义信息
将值
val 作为表达式 E、项 T 和因子 F 的属性
用语义规则描述表达式的求值
属性文法（语法制导定义）
产生式 L → E E → E1 + T E → T T → T1 * F T → F F → ( E ) F → digit
6.2 中间语言
用于编译程序
源程序经过语义分析被译成中间代码
序列
（中间语言的语句）
用中间语言过渡的好处：
便于编译系统的实现、移植、代码优
化
常用的中间语言

三地址代码（四式） 语法结构树（三元式）
后缀式 特点 形式简单、语义明确、便于翻译 独立于目标语言
语法制导编译
例6-4：real id1,id2,id3 的
分析树和属性计算
Ｓ-属性定义：
仅包括综合属性
对于所有Ａ
→ Ｘ1 Ｘ2 …Ｘn， 的属性
Ａ的属性计算仅用Ｘ1…Ｘn
如：算术表达式求值的属性文法
Ｌ-属性定义：
其属性可用深度优先的顺序从左至
右计算
对于所有 Ｘi
Ａ→Ｘ1 Ｘ2 … Ｘn
属性计算仅使用Ａ Ｘ1 Ｘ2 … Ｘi-1 的属性
Ｌ Print(19) E.val=19 ＋ T.val=4 F.val=4 F.val=5 digit.attr=5 digit.attr=4
D T.type=real real L.in=real id1
addtype
L.in=real L.in=real , , id2
addtype
id3
addtype
其他三地址代码
goto l param x call p, n (n是参数个数) return x x := y[i] x[i] := y x := &y x := *y *x = y 无条件转移 实在参数 过程调用 过程返回 数组运算 指针运算
6.3 赋值语句的翻译
翻译的需求
充分了解各种语言现象的语义
组成语句的翻译结果（中间代码序列）

中间代码的生成过程
S.code => E.code || gen( ‘a:=‘E.place ) /* ‘a’ => id.place */ => E1.code || E2.code || gen( ‘t1:=‘E1.place’+’E2.place ) || gen( ‘a:=t1’ ) /* newtemp => t1 => E.place */ => E11.code || gen( ‘t2:= 0 -’ E11.place ) /* newtemp => t2 => E1.place */
|| E21.code || E22.code || gen( ‘t3:=’ E21.place’*’E22.place ) /* newtemp => t3 => E2.place */ || gen( ‘t1:=t2+t3’ ) || gen( ‘a:=t1’ ) => gen( ‘t2:= 0 - c’ ) || gen( ‘t3:=b*34’ ) /* ‘c’ => E11.place */ /* ‘b’ => E21.place */ /* ‘34’ => E22.place */ || gen( ‘t1:=t2+t3’ ) || gen( ‘a:=t1’ ) /* ‘ ’ => E21.code => E22.code */
例6-2：说明语句的类型信息统计

说明语句的作用
支持语义分析，提供语义检查的依据

设计
编写说明语句的文法 将类型信息作为类型描述