6 属性文法和语法制导翻译

实际上，编译中语义翻译的实现并不是按 上图的流程处理的；而是随语法分析的进展， 识别出一个语法结构，就对它的语义进行分析 和翻译。
1.依赖图
语义规则建立了属性之间的依赖关系，这些 关系可以用图来表示，这样的图称为依赖图。
2.树遍历的属性计算方法
假设语法树已经建立了，并且树中已 带有开始符号的继承属性和终结符的综合 属性。然后用深度优先，从左到右的遍历 方法遍历语法树，直至计算处所有属性。 如果需要，可进行多次遍历（遍）。
第六章属性文法和语法制导翻译
要对语法正确的源程序进行翻译：首先要进 行语义检查(详见龙书第六章及补充材料) ，若正 确，则翻译成中间代码或目标代码。 语义分析和中间代码生成使用的大多是语法 制导翻译方法。其思想是，根据翻译的需要为每 个文法符号设置属性，以表示文法符号的信息。 例如，一个变量的属性有类型、值、存储地址等; 表达式的属性有类型、值等。 属性值的计算和产生式相联系。随着语法分 析的进行，属性值也同时进行计算和传递，完成 语义分析和翻译的任务(语法制导)。
通常： 对出现在产生式右边的继承属性和出现在产 生式左边的综合属性都必须提供一个计算规则。 且属性计算规则中只能用相应产生式中的文法符 号的属性（利于封装）。 出现在产生式左边的继承属性和出现在产生 式右边的综合属性不由所给产生式的属性计算规 则进行计算，而由其它产生式的属性规则或由属 性计算器的参数提供。 例：ABC A.a (A继) A.b (A综) B.c (B综) C.d (C继) 可能有 C.d:=B.c+1 A.b:=A.a+B.c 而A.a和B.c在其它地方计算。
属性依赖图
A的继承属性
A.b
A的继承属性
A
X1.c1
X2.c2 …

X1.c1
X2.c2 Xk.b …
综合属性A.b的计算
继承属性Xk.b的计算
特别强调：
（1）终结符只有综合属性，它们由词法分 析器提供。 （2）非终结符既可以有综合属性，也可以 有继承属性，文法开始符号的所有继承属 性作为属性计算前的初始值。
T.type :=real
L L1,id
L id
L1.in :=L.in
addtype(id.entry, L .in) addtype(id.entry, L .in)
D
T real 4 type in 5 L , 6
in 7 in 9 L 10
L ,
8
id3 3 entry
id2 2 entry 每个L结点都带有继承属性
产生式s→if B then S1 else S2的抽象语法树 if-then-else ／ | ＼ B S1 S2
赋值语句的抽象语法树 assignment / \ variable expression 在抽象语法树中，运算符号和关键字都不 在叶结点，而是在内部结点中出现。
例:建立表达式的抽象语法树 (类似后缀形式)
3 继承属性
继承属性值是由此结点的父结点和／或兄 弟结点的某些属性值来决定的。 例6.2 利用继承属性解决变量说明中的类 性定义： int a,b,c
表6.2 带有继承属性L.in的语法制导定义 产生式
DTL
语义规则
L.in:=T.type
T int
T real
T.type :=integer
关于语法和语义： 语法是指语言的结构；语义是指附着于语言结构上 的实际含意 ，即语言的“意义”。 •语义不能离开语法独立存在； •语义远比语法复杂； •同一语言结构可包含多种含意，不同语言结构表示相 同含意； •语法与语义之间没有明确的界线。 语义分析的两个作用： 检查是否结构正确的句子所表示的意思也合法； 执行规定的语义动作，如：表达式求值 符号表填写 中间代码生成等 语义分析的方法： 语法制导翻译
每个非终结符都有一个综合属性val，表示它 的整数值。产生式左边的属性值由右边计算。
属性依赖图:
3＋4×5
E. val = 23
E. val = 3
+
E. val = 4
E. val = 20
number. lex_val = 3
×
E. val = 5
number. lex_val = 4
number. lex_val = 5
AXYZ A.a:=f(X .x, Y .y,Z .z) A .a X .x Y .y Z .z
top
ntop
state ... X Y Z
val ... X.x Y.y Z.z
top
state ... A
val ... A .a
定义式 A .a:=f(X.x, Y.y, Z.z)（抽象）变成 val[ntop]:=f(val[top-2],val[top-1],val[top])（具 体可执行代码）。 在执行代码段之前执行：
建立结点使用的函数： 1. mknode(op,left,right) 建立一个运算符号结点， 标号是op,两个域left和right指向运算分量结点 的指针。 2．mkleaf(id,entry) 建立一个标识符结点,由标号 id标识，一个域entry指向标识符符号表中相应 的项。 3. mkleaf(num,val) 建立一个数结点，标号为num， 域val用于存放数的值。 函数返回新建立结点的指针。
L E.val:=19 E.val:=15 T.val:=15 + n T.val:=4
F.val:=4
F.val:=5
T.val:=3
F.val:=3
*
digit.lexval:=4
digit.lexval:=5
digit.lexval:=3
综合属性值的计算方法：
对于S-属性定义，通常使用自底向上的分 析方法，在建立每一个结点处使用语义规则来 计算综合属性值，即在 用哪个产生式进行归约 后，就执行那个产生式的S-属性定义计算属性 的值，从叶结点到根结点进行计算。
ntop:=top-r+1
r是句柄的长度
执行代码段后执行： top:=ntop;
表6.5用LR分析器实现台式计算器(对比slide 10)
产生式 代码段
LEn
E E+T
printf(val[ntop])
val[ntop]:=val[top-2]+val[top] val[ntop]:=val[top-2]*val[top] val[ntop]:=val[top-1]
语法制导翻译的具体方法：
1. 将文法符号所代表的语言结构的意思，用 附着于该文法符号的属性表示； 2. 用语义规则规定产生式所代表的语言结构 之间的关系（即属性之间的关系），即用 语义规则实现属性计算。 3. 语义规则的执行：在语法分析的适当时刻 （如推导或归约）执行附着在对应产生式 上的语义规则，以实现 对语言结构语义的 处理，如计算、查填符号表、生成中间代 码、发布出错信息等。
id1 1 entry
6.2 基于属性文法的处理方法
输
入
符 号 串
分 析 树
依 赖
图
语 义 规 则 的 计 算
析，构造语 法分析树，然后根 据需要遍历语法树 并在语法树的各结 点处按语义规则进 行计算。 这种由源程序 的语法结构所驱动 的处理方法就是语 法制导翻译。
下图为一个带有综合属性值域的分析栈： state val ... ... X X.x Y Y.y top Z Z.z ... ...
若有产生式A
b:=f(c1,c2,…,ck)
b是A的综合属性，ci(1 ik)是中符号的属 性。综合属性的值在自底向上的分析过程中， 每步归约时，计算相应的属性值。
3. 一次扫描的处理方法
在语法分析的同时计算属性值，而不是在 语法分析构造语法树之后进行属性计算。无需 构造语法树。 一遍扫描的处理方法与语法分析器交互工 作，它与所采用的语法分析方法和属性的计算 次序密切相关。
L属性文法可用于一遍扫描的自上而下分析， 而S属性文法适用于一遍扫描的自下而上的分析。
表6.1 简单台式计算器的属性文法
产生式 LEn E E1+T E T T T1*F T F F (E) F digit 语义规则 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.lexval
自底向上地构造a-4+c 的抽象语法树
(1)p1:=mkleaf(id,entrya) (2)p2:=mkleaf(num,4) (3)p3:=mknode(‘-’,p1,p2)
+
(4)p4:=mkleaf(id,entrye) (5)p5:=mknode(‘+’,p3,p4)
– id num 4
属性值的设置与语法结构的语义以及翻译程 序的需要有关。
例如，把表6.1中的类型扩充到 int和real,就 出现了表6.2(Slide 11)中的类型属性 。
2 综合属性
S-属性文法：只使用综合属性的文法。 结点属性值的计算正好和自底向上分析建立 分析树结点同步进行。 例6 .1 用表6.1中的属性文法对表达式进行计 算。 设输入的表达式为：3*5+4n n是换行符。
4.抽象语法树
抽象语法树（Abstract syntax tree）： 去掉了在语法分析树中对语义无关紧要的成分， 是分析树的抽象形式。 抽象语法树是常用的一种中间表示形式。 语法分析过程中完成翻译有许多优点，但也有一 些不足： 1.适于语法分析的文法可能不完全反映语言成分 的自然层次结构； 2. 语法分析方法限制，对分析树结点的访问序和 翻译需要的访问序不一致。