编译原理：L属性、S属性语法制导

1 基本概念

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

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

• Definition (语法制导的翻译方案 (Syntax-Directed Translation Scheme; SDT))

  SDT 是在其产生式体中嵌入语义动作的上下文无关文法。

2 S属性

• Definition (综合属性 (Synthesized Attribute))

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

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

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

S 属性定义的依赖图描述了属性实例之间自底向上的信息流

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

2.1 例子

3 L属性

• Definition (继承属性 (Inherited Attribute))

  节点 N 上的继承属性只能通过N 的父节点、N 本身和 N 的兄弟节 点上的属性来定义。

• Definition (L 属性定义 (L-Attributed Definition))

  如果一个 SDD 的每个属性

  1. 要么是综合属性,

  2. 要么是继承属性, 但是它的规则满足如下限制: 对于产生式 A → X1X2 . . . Xn 及其对应规则定义的继承属性 Xi .a, 则这个规则只能使用

     (a) 和产生式头 A关联的继承属性;

     (b) 位于Xi 左边的文法符号实例 X1、X2、. . . 、Xi−1 相关的继承属性或综合属性;

     (c) 和这个 Xi 的实例本身相关的继承属性或综合属性, 但是在由这个 Xi 的全部属性组成的依赖图中不存在环。

  则它是 L 属性定义。

3.1 例子

4 转换

5 SDT

Definition (语法制导的翻译方案 (Syntax-Directed Translation Scheme; SDT))

SDT 是在其产生式体中嵌入语义动作的上下文无关文法。

语义动作可以嵌入在产生式体中的任何位置