概述

语法制导翻译的整体思路

首先，根据翻译目标来确定每个产生式的语义
其次，根据产生式的含义，分析每个符号的语义
再次，把这些语义以属性的形式附加到相应的文法符号上（即把语义和语言结构联系起来）
然后，根据产生式的语义给出符号属性的求值规则（即语义规则），从而形成语法制导定义

$E\to E_1+T$ 对应的求值规则： $E.val=E_1.val+T.val$

语法制导定义：产生式语义规则

翻译

根据语法分析过程中所使用的产生式，执行与之相应的语义规则，完成符号属性值的计算，从而完成翻译

翻译目标决定语义规则

翻译目标决定产生式的含义、决定文法符号应该具有的属性，也决定了产生式的语义规则

翻译结果依赖于语义规则

翻译目标

生成代码
- 可以为源程序产生中间代码
- 可以直接生成目标机指令
对输入符号串进行解释执行
向符号表中存放信息
给出错误信息

翻译的结果依赖于语义规则

使用语义规则进行计算所得到的结果就是对输入符号串进行翻译的结果

如： $E\to E+T$ 的翻译结果可以是：计算表达式的值、检查表达式的类型是否合法、为表达式创建语法树、生成代码等等

语法制导翻译的一般步骤

从文法建立输入符号串的分析树
为分析树构造依赖图
对依赖图进行拓扑排序
从排序序列得到语义规则的计算顺序
计算结果，得到对输入符号串的翻译

是多遍过程

语义规则的执行时机

可以用一个或多个子程序（称为语义动作）所要完成的功能描述产生式的语义
在语法分析过程中使用某个产生式时，在适当的时机执行相应的语义动作，完成所需要的翻译
把语义动作插入到产生式中适当的位置，从而形成翻译方案
语法制导定义是对翻译的高层次的说明，它隐蔽了一些实现细节，无须指明翻译时语义规则的计算次序
翻译方案指明了语义规则的计算次序，规定了语义动作的执行时机

语法制导定义及翻译方案

语法制导定义

在一个语法制导定义中，对应于每一个文法产生式 $A\to \alpha$ ，都有与之相联系的一组语义规则，其形式为： $b=f(c_1,c_2,...,c_k)$

这里， $f$ 是一个函数，而且
- 如果 $b$ 是A的一个综合属性，则 $c_1、c_2、...、c_k$ 是产生式右部文法符号的属性或者A的继承属性
- 如果 $b$ 是产生式右部某个文法符号的一个继承属性，则 $c_1、c_2、...、c_k$ 是A或产生式右部任何文法符号的属性
属性 $b$ 依赖于属性 $c_1、c_2、...、c_k$
语义规则函数都不具有副作用的语法制导定义称为属性文法
对上下文无关文法的推广
每个文法符号都可以有一个属性集，其中可以包括两类属性：综合属性和继承属性
- 左部符号的综合属性是从该产生式右部文法符号的属性值计算出来的；在分析树中，一个内部结点的综合属性是从其子结点的属性值计算出来的
- 出现在产生式右部的某文法符号的继承属性是从其所在产生式的左部非终结符号和/或右部文法符号的属性值计算出来的；在分析树中，一个结点的继承属性是从其兄弟结点和/或父结点的属性值计算出来的
- 分析树中某个结点的属性值是由与在这个结点上所用产生式相应的语义规则决定的
和产生式相联系的语义规则建立了属性之间的关系，这些关系可用有向图（即：依赖图）来表示

实线即为综合属性，虚线为继承属性

语义规则

综合属性

分析树中，如果一个结点的某一属性由其子结点的属性确定，则这种属性为该结点的综合属性

如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为S-属性定义

对于S-属性定义，通常采用自底向上的方法对其分析树加注释，即从树叶到树根，按照语义规则计算每个结点的属性值

简单计算器的语法制导定义是S-属性定义

这是一个一遍过程

注释分析树

一般的，继承属性（蓝色）写在左边，综合属性（红色）写在右边

依赖图

分析树中，结点的继承属性和综合属性之间的相互依赖关系可以由依赖图表示

为每个包含过程调用的语义规则引入一个虚拟综合属性b

把语义规则统一为b=f(c1,c2,…,ck)的形式

依赖图中：

为每个属性设置一个结点
如果属性b依赖于c，那么从属性c的结点有一条有向边连到属性b的结点

序号为了方便后面排序的使用而设置

计算顺序：拓扑排序

计算顺序是有向非循环图的拓扑排序

图中结点的一种排序m1,m2,…,mk
有向边只能从这个序列中前边的结点指向后面的结点
如果mi $\to$ mj是从mi指向mj的一条边，那么在序列中mi必须出现在mj之前

依赖图的任何拓扑排序

给出了分析树中结点的语义规则计算的有效顺序
在拓扑排序中，一个结点上语义规则b=f(c1,c2,…,ck)中的属性c1,c2,…,ck在计算b时都是可用的

Eg.对上图的拓扑排序（有两种）

1、2、3、4、5、6、7、8、9、10

4、5、3、6、7、2、8、9、1、10

S属性与L属性

S属性定义：仅涉及综合属性的语法制导定义

L属性定义：一个语法制导定义是L属性定义，如果与每个产生式 $A\to X_1X_2...X_n$ 相应的每条语义规则计算的属性都是

A的综合属性，或是
$X_j（1\le j\le n）$ $X_{j} （ 1 \leq j \leq n ）$ 的继承属性，而该继承属性仅依赖于
- A的继承属性
- 产生式中 $X_j$ 左边的符号 $X_1、X_2、...、X_{j-1}$ 的属性

注意：这里的继承属性与上文有所变化，只能从父亲节点和当前节点的左边兄弟节点（哥哥节点）继承，不能从右边节点（弟弟节点）继承！

每一个S属性定义都是L属性定义

属性的计算顺序可以由深度优先遍历分析树实现

以分析树的根结点作为实参，L属性定义的属性都可以用深度优先的顺序计算。

进入结点前，计算它的继承属性；从结点返回时，计算它的综合属性

翻译方案

上下文无关文法的一种便于翻译的书写形式
属性与文法符号相对应
语义动作括在花括号中，并插入到产生式右部某个合适的位置上
给出了使用语义规则进行属性计算的顺序
分析过程中翻译的注释

对S属性的方案设计

为每一个语义规则建立一个包含赋值的动作

把这个动作放在相应的产生式右边末尾

Eg.产生式语义规则

$T\to T1*F$ $T.val=T1.val*F.val$

如下安排产生式和语义动作：

$T\to T1*F \{T.val=T1.val*F.val\}$

对L属性的方案设计

一个动作不能引用这个动作右边的文法符号的综合属性

左部符号的综合属性只有在它所引用的所有属性都计算出来之后才能计算

这种属性的计算动作放在产生式右端末尾
把动作类属性视为虚拟综合属性

右部符号的继承属性必须在这个符号以前的动作中计算出来

计算该继承属性的动作必须出现在相应文法符号之前

S-属性定义的自底向上分析

为表达式构造语法树的语法制导定义

抽象语法

把语法规则中对语义无关紧要的具体规定去掉，剩下来的本质性的东西称为抽象语法

eg.

赋值语句：x=y、x:=y、或 $y\to x$

抽象形式：assignment(variable,expression)

语法树

分析树的抽象（或压缩）形式,也称为语法结构树或结构树

内部结点表示运算符号，其子结点表示它的运算分量

区分语法树和分析树

构造表达式的语法树

表达式的语法树的形式

每一个运算符号或运算分量都对应树中的一个结点
运算符号结点的子结点分别是与该运算符的各个运算分量相应的子树的根
每一个结点可包含若干个域：标识域、指针域、属性值域等

在运算符结点中

一个域标识运算符号
其它各域包含指向与各运算分量相应的结点的指针
称运算符号为该结点的标号

有先分析再翻译和边分析边翻译两种方法

表达式的有向非循环图(dag)

dag与语法树相同的地方

表达式的每一个子表达式都有一个结点
一个内部结点表示一个运算符号，且它的子结点表示它的运算分量。

dag与语法树不同的地方

dag中，对应一个公共子表达式的结点具有多个父结点
语法树中，公共子表达式被表示为重复的子树

为表达式创建dag的函数makenode和makeleaf

建立新结点之前先检查是否已经存在一个相同的结点
- 若已存在，返回一个指向先前已构造好的结点的指针
- 否则，创建一个新结点，返回指向新结点的指针

S-属性定义的自底向上实现

LR分析方法中，分析程序使用栈来存放已经分析过的子树的信息，分析树中某结点的综合属性由其子结点的属性值计算得到。也就是说，LR分析程序在分析输入符号串的同时可以计算综合属性。

修改分析栈

目的：使之能够保存综合属性

做法：在分析栈中增加一个域，存放综合属性值

Eg. 带有综合属性域的分析栈

栈：一对数组state和val

state元素：指向LR(1)分析表中状态行的指针（或索引）

如果state[i]保存对应符号A的状态，则val[i]中就存放A的属性值

假设综合属性刚好在每次归约前计算， $A\to XYZ$ 对应的语义规则是 $A.a=\to(X.x,Y.y,Z.z)$