－ E的语法树（根结点指针）
(, , )－建立一个表达式语法树结点，它的运 算符为，左、右运算对象是和所指的语法树。 如果建成，则需要检查是否已存在相应内部 结点，其左右运算对象分别是和。若没有则 新建一个。
(‘’)－
(‘’)－
建立表达式语法树的叶结点。建也需检查是 否已有相应结点。
28.02.2021
. 语法树 －语法树与分析树
语法树可看作分析树的浓缩。也称抽象语法 树。而分析树可看成具体语法树。
28.02.2021
《编译原理与技术》讲义
12
语法树 . 分析树
S S1 S2
语法树
分析树
S
S1 S2
S1
S2
28.02.2021
《编译原理与技术》讲义
13
语法树 . 分析树
a b* + b *
语法树
9
语义规则的计算方法
分析树方法 － 为输入串建立分析树 － 由语义规则建立属性依赖图（没有属性循环
依赖的） － 对依赖图进行拓扑排序，得到属性计算次序 － 依次计算属性，得到“翻译”结果 基于规则的方法 － 构造编译器时，事先对产生式的语义规则进
行分析，得到属性计算次序 忽略规则的方法 － 28.02.2021 属性计算次序《编仅译原由理与分技术析》讲方义 法限定。如属性定 10
《编译原理与技术》讲义
17
.4 构造表达式*-4的属性结构树
+
a
ID a
28.02.2021
+
*
*
@
b
ID b
@
4
NUM 4
《编译原理与技术》讲义
-
18
.4 构造表达式*-4的语法树（）
+
ID a
*
ID b
@NUM 4
28.02.2021
《编译原理与技术》讲义
19
属性定义
－如果产生式A X1X2… 的语义规则只计算 1）A的综合属性，或者 2）的继承属性，且该属性仅依赖于产生式右部的 左边符号（j<i）的（综合）属性或A的继承属性；
常量的“值”、变量的类型和存储位置等。
. 二义性表达式文法G，非终结符E有属性 （表达式的值）
E E ‘+’ E | E ‘*’ E | ‘(‘ E ‘)’ | 属性计算规则（语义规则）
与产生式相关联的反映文法符号属性之间关
系的“规则”
28.02.2021
《编译原理与技术》讲义
3
属性文法 语法制导定义（文法＋属性＋语义规则） 语义规则仅表明属性间“抽象”关系，不
涉及具体翻译实现细节，如计算次序等。
翻译方案（文法＋属性＋语义动作）
语义规则－即语义动作，可体现若干实现的 细节。
28.02.2021
《编译原理与技术》讲义
4
.1算术表达式的计算器
产生式 E E1 ‘+’ E2 E E1 ‘*’ E2 E ’(‘ E1 ‘)’ E
语法制导定义 E1 + E2 E1 * E2 E1
28.02.2021
《编译原理与技术》讲义
5
.1算术表达式的计算器
产生式
翻译方案
E E1 ‘+’ E2 { E1 + E2 }
E E1 ‘*’ E2 { E1 * E2 }
E ’(‘ E1 ‘)’ { E1 }
E {}
28.02.2021
《编译原理与技术》讲义
6
属性文法
属性的分类
若产生式A X1X2…，与之相关的属性计算 规则
21
.5 非属性定义的语法制导定义
产生式 A
A
语义规则 l()
m() f() r() q() f()
28.02.2021
《编译原理与技术》讲义
22
翻译方案中的动作
－语义动作可放在产生式右端任何位置；这也就显式 地给出了动作的执行时刻。（可认为是在深度优先 遍历中的执行时刻）
编译原理与技术
语法制导翻译
28.02.2021
《编译原理与技术》讲义
1
语法制导翻译
属性文法 属性定义 属性定义 语法制导定义与翻译方案 自底向上翻译 属性定义自底向上计算 自底向上计算继承属性 自顶向下翻译
28.02.2021
《编译原理与技术》讲义
2
属性文法
属性文法（ ）
上下文无关文法+属性+属性计算规则 属性－用来描述文法符号的语义特征，如
义可以在自下而上分析时，在归约前计算。如中的
. 3 属性计算次序: 3＋4×5
1
. =3
2
E. = 3
8
E. = 23
+
4
E. = 4
7
E. = 20
6
×
E. = 5
3
. =4
5
. =5
28.02.2021
《编译原理与技术》讲义
11
属性定义
－语义规则仅包含综合属性计算（可以有固有 属性出现）。
－适合自底向上计算
产生式
语义规则
E E1 + E2 (‘+’1, E2)
E E1 - E2 (‘-’1, E2)
E E1 * E2 (‘*’1, E2)
E E1 / E2 (‘/’1, E2)
E ( E1 ) E - E1
E1 (‘@’1, －)
E (‘’)
E
(‘’)
28.02.2021
《编译原理与技术》讲义
16
.4 构造表达式的语法树（）
分析树
赋值语句
算符 E
a
+
a
*
*
b@
b@
c
c
EE+ຫໍສະໝຸດ EE*E E*Eb @E b @E
c
c
28.02.2021
《编译原理与技术》讲义
14
语法树 .
（去除了公共子表达式的无环有向图） a b* + b *
a
+
*
*
b@
b@
a
+
* b@
c
c
c
语法树
28.02.2021
《编译原理与技术》讲义
15
.4 构造表达式的语法树（）
b f ( c1, c2, … )
－如果属性b是产生式左部符号A的属性则称 其为A的综合属性；
－如果属性b是产生式右部符号的属性则称其 为的继承属性；
－c1, c2, … 一般是产生式右部其它符号的 (综合)属性或A的继承属性；
28.0－2.2021固有属性：终《结编译符原理与仅技术有》讲的义 属性。如。通常 7
－属性定义均为属性定义 －可按深度优先次序计算
－ 一种自然的属性计算次序 － 在分析期间完成翻译。属性计算与结点建立有联 系；适合于自顶向下和自底向上分析方法。
28.02.2021
《编译原理与技术》讲义
20
深度优先次序
(n: )
m n, m;
(m); ;
n;
28.02.2021
《编译原理与技术》讲义
A的继承属性
属性依赖图
A的继承属性 A
X11 X22 … 综合属性的计算
X11 X22
…
继承属性的计算
28.02.2021
《编译原理与技术》讲义
8
. 2 属性依赖图:
3＋4×5
E. = 23
E. = 3 . =3
+
E. = 20
E. = 4
×
E. = 5
. =4
. =5
28.02.2021
《编译原理与技术》讲义