编译原理10-semantics-ag

语义分析——属性文法

属性文法(Attribute Grammar): 为上下文无关文法赋予语义

属性文法

Offline 方式计算属性值

• 已有语法分析树 (calc)

按照从左到右的深度优先顺序遍历语法分析树

• 关键:

在合适的时机执行合适的动作，计算相应的属性值

语法分析过程中

在语法分析过程中实现属性文法

$B \rightarrow X \lbrace a \rbrace Y$

语义动作嵌入的位置决定了何时执行该动作

基本思想：

一个动作在它左边的所有文法符号都处理过之后立刻执行

时机

语义动作嵌入在什么地方? 这决定了何时执行语义动作。

SDD

Definition——语法制导定义 (Syntax-Directed Definition; SDD)

SDD 是一个上下文无关文法和属性及规则的结合。

• 每个文法符号都可以关联多个属性
• 每个产生式都可以关联一组规则
• SDD 唯一确定了语法分析树上每个非终结符节点的属性值
• SDD 没有规定以什么方式、什么顺序计算这些属性值

注释(annotated)语法分析树

显示了各个属性值的语法分析树

3 * 5 + 4

Definition——综合属性 (Synthesized Attribute)

节点 N 上的综合属性只能通过 N 的子节点或 N 本身的属性来定义。

Definition——S 属性定义 (S-Attributed Definition)

如果一个 SDD 的每个属性都是综合属性, 则它是 S 属性定义。

依赖图

用于确定一棵给定的语法分析树中各个属性实例之间的依赖关系

• S 属性定义的依赖图刻画了属性实例之间自底向上的信息流动

此类属性值的计算可以在自顶向下的 LL 语法分析过程中实现

在 LL 语法分析器中, 递归下降函数A返回时,计算相应节点A的综合属性值