第四章 语法制导的翻译

语义规则和产生式相联系的两种方式：语法制导的定义和语法执导的翻译方案（简称翻译方案）。语法制导定义是比较抽象的翻译规范，它隐蔽了一些实现细节；而翻译方案多陈述了一些实现细节，主要是指明各语义规则的计算时机。

4.1 语法制导的定义

4.1.1 语法制导定义的形式

• 基础文法
• 每个文法符号有一组属性
• 每个文法产生式A→α有一组形式为b := f(c₁, c₂, …, c_k )的语义规则，其中f 是函数，b和c₁, c₂, …, c_k 是该产生式文法符号的属性
  • 综合属性：如果b是A的属性，c₁, c₂, …, c_k 是产生式右部文法符号的属性或A的其它属性
  • 继承属性：如果b是产生式右部某个文法符号X的属性

    4.1.2 综合属性

    S属性定义：仅仅使用综合属性的语法制导定义

    4.1.3 继承属性

    4.1.4 属性依赖图

    4.1.5 属性计算次序

• 构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性
• 语义规则的计算方法
  • 分析树方法：前面介绍的方法
  • 基于规则的方法：静态确定语义规则的计算次序
  • 忽略规则的方法：事先确定属性的计算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制

    4.2 S属性定义的自下而上计算

    4.2.1 语法树

• 语法树是分析树的浓缩表示：算符和关键字是作为内部结点
• 语法制导翻译可以基于分析树，也可以基于语法树

  4.2.2 构造语法树的语法制导定义

  4.2.3 S属性的自下而上计算

  4.3 L属性定义的自上而下计算

  边分析边翻译的方式能否用于继承属性？
• 属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制
• 分析树的结点是自左向右生成
• 如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算

  4.3.1 L属性定义

• 如果每个产生式A →X₁ X₂ … X_n 的每条语义规则计算的属性是A的综合属性；或者是X_j 的继承属性，1 ≤ j ≤ n, 但它仅依赖：
  • 该产生式中X_j左边符号X₁ X₂ … X_n 的属性；
  • A的继承属性
• S属性定义属于L属性定义
• 变量类型声明的语法制导定义是一个L属性定义

  4.3.2 翻译方案

  4.3.3 预测翻译器的设计

  把预测分析器的构造方法推广到翻译方案的实现

  4.3.4 用综合属性代替继承属性

  4.4 L属性的自下而上计算

  在自下而上分析的框架中实现L属性定义的方法
• 它能实现任何基于LL(1)文法的L属性定义
• 也能实现许多（但不是所有的）基于LR(1) 的L属性定义

  4.4.1 删除翻译方案中嵌入的动作

  4.4.2 分析栈上的继承属性

  4.4.3 模拟继承属性的计算

  4.5 递 归 计 算

  语法制导定义的实现
• 分析树方法
• 边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）
• 先分析后计算的方法，不局限于L属性计算（基于规则的方法）
  • 为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分
  • 为非终结符的不同综合属性构造不同的函数

    4.5.1 自左向右遍历

    4.5.2 其它遍历方法

    按所需次序访问结点的子结点，可用于非L属性定义

    4.5.3 多次遍历