第五章: 语法制导的翻译

  • 翻译
    • CFG非终结符号代表了语言的某个构造
    • 程序设计语言的构造由更小的构造组合而成
    • 一个构造的语义可以由更小的构造的含义综合而来
    • 也可以从附近的构造继承而来
  • 语法制导定义: 将文法符号与某些属性相关联, 并用语义规则来描述如何计算属性的值
  • 语法制导翻译: 在产生式体中加入语义动作, 并在适当时候执行动作

    语法制导的定义SDD

    • 上下文无关文法和属性/规则的结合
    • 关联关系: 属性->符号, 规则->产生式
    • X.a: 文法符号X的属性a的值, 可进行计算
      • 属性计算规则
    • 综合属性和继承属性
      • 综合属性: N的子节点和N本身的属性值来定义, 来自产生式的语义规则
      • 继承属性: 依赖于父节点, 兄弟节点和本身的属性值来定义, 来自父节点所关联的语义规则
      • 继承属性不能依赖于子节点, 但综合属性可依赖于继承属性, 终结符号有综合属性, 无继承属性
    • S属性的SDD
      • 只包含综合属性
      • S属性的SDD可以和LR语法分析器一起实现
        • 栈中状态/符号可以附加属性值
        • 归约时, 按照语义规则计算规约得到的符号的属性值
        • 语义规则不应该有复杂的副作用: 不影响其他属性的求值
      • 语法分析树上的SDD求值: 注释分析树
        • 计算顺序: 先算被依赖的结点
        • S属性SDD: 自底向上的计算顺序可以求值
      • 自顶向下分析的SDD
        • 消除左递归后, 无法直接用val进行处理, 需要用继承属性完成计算
        • 属性值计算规律
          • 假设
            $$\begin{aligned}
            &A\to A_1Y &A.a=g(A_1.a, Y.y) \\
            &A\to X &A.a=f(X.x) \\
            \end{aligned}$$
          • 那么, 消除左递归后
            $$\begin{aligned}
            &A\to XR &R.i=f(X.x); A.a=R.s \\
            &R\to YR_i &R_1.i = g(R.i, Y.y);R.s=R_1.s \\
            &R\to \epsilon &R.s=R.i \\
            \end{aligned}$$
    • SDD的求值顺序
      • 求值过程中, 求算一个值, 必须先计算出其依赖的所有属性
      • 依赖关系是偏序, 构造依赖图, 有环则无法计算
      • 依赖图
        • 每个分析树结点N, 其每个属性a都对应一个依赖图结点N.a
        • 虚线边来自分析树, 箭头表示数据流向, 比如a依赖b, 则数据从b流向a
        • 计算时, 按照拓扑顺序进行计算
        • 特定类型的SDD一定不包含环, 且有固定的计算顺序: L属性SDD和S属性SDD
      • S属性SDD: 总是通过子节点计算父节点, 可以和自底向上或自顶向下的语法分析过程, 一同计算
        • 自底向上: 构造结点时, 计算相关属性, 因子节点已构造
        • 自顶向下: 递归时, 在结点过程的最后计算该结点属性, 此时其递归过程(子节点)已经计算完毕
      • L属性SDD: 每个属性可能是综合属性或继承属性
        • 继承属性: 每个$X_i$只能依赖产生式中, 其左边的那些文法符号的属性
        • 计算时
          • 综合属性从下到上, 继承属性从上到下, 或从左到右
        • 递归子程序法
          • 非终结符号A, 其对应过程的参数为继承属性, 返回值为综合属性
          • 处理规则$A\to X_1X_1\cdots X_n$
            • 调用$X_i()$之前, 计算其继承属性的值, 用作参数调用
            • 该产生式代码的最后, 计算$A$的综合属性
    • 受控副作用的语义规则
      • 属性文法没有副作用, 但增加了复杂度
      • 将标识符表作为全局变量, 用函数添加新的标识符
      • 受控: 不会对属性求值进行约束, 或者只进行简单约束
    • 抽象语法树
      • 结点代表语法结构, 相当于运算符
      • 节点的子节点代表子结构, 对应于运算分量
      • 可以忽略掉标点等非本质的东西
      • 表示方法
        • 每个节点用一个对象表示
        • 对象有多个域: 叶节点存词法值, 内部结点存op值和参数, 参数指向其他节点
      • 构建方法: 基于分析树, 似乎只有终结符, 其树边实箭头, 而分析树的中间结点用虚线箭头指向对应的抽象语法树结点

        语法制导的翻译SDT

  • 在产生式体中嵌入的语义动作(程序片段)
  • 实现方法
    • 建立语法分析树
    • 将语义动作看作虚拟结点
    • 从左到右, 深度优先遍历, 访问虚拟结点时执行相应动作
    • SDT实现SDD
      • LR文法, SDD是S属性
      • LL文法, SDD是L属性
  • 可在语法分析过程中实现的SDT
    • 可在分析过程中执行语义动作, 判断方法
      • 将每个语义动作替换为一个独有的非终结符以及产生式$M_i\to\epsilon$
      • 如果新的文法可以由某种方法分析, 则SDT可在这个分析过程中实现
    • 后缀SDT: 所有动作都发生在产生式的最右端
      • 文法是LR, 且其SDD是S属性, 必然可构造出后缀SDT
      • 后缀SDT和L属性对应的SDT, 可在分析时完成
    • 带有内部语义动作的SDT
      • 动作左边的符号处理完成后, 就立刻执行这个动作$B\to X \{a\} Y$
        • 自底向上: X出现在栈顶时, 执行其后的动作a
        • 自顶向下: 试图展开Y或在输入中检测到Y时, 执行其前的动作a
      • 一般的SDT, 都可先建立分析树, 之后前序遍历并执行动作
      • 不是所有的SDT都可在分析过程中实现
    • 消除左递归时SDT的转换
      • 动作不涉及属性值, 可以把动作当作终结符号处理, 消除左递归
      • 涉及属性值:
        • 原文法
        • $$\begin{cases}A\to A_1Y\{A.a=g(A_1.a, Y.y)\}\\A\to X\{A.a=f(X.x)\}\end{cases}$$
        • 消除后
        • $$\begin{cases}A\to X\{R.i = f(X.x)\}R\{A.a = R.s\}\\R\to Y\{R_1.i = g(R.i, Y.y)\}R_1\{R.s = R_1.s\}\\R\to \epsilon\{R.s = R.i\}\end{cases}$$
    • L属性的SDT
      • 如果文法是LL的, 就可以将L属性的SDD转换成一个SDT, 可在分析过程中实现
      • 将赋值语义动作放到相应产生式的适当位置
        • 计算$X_i$继承属性的动作放在其体部位置的左边
        • 计算产生式头部综合属性的动作在产生式的最右边
    • L属性的SDD实现
      • 每个非终结符号对应一个函数, 函数参数接受继承属性, 返回值包含综合属性
      • 函数体中
        • 首先选择适当的产生式
        • 局部变量保存属性
        • 对于产生式体中的终结符号, 读入符号并获取其综合属性(词法分析得到)
        • 对于非终结符号, 使用适当的方式调用相应函数, 并记录返回值
      • 边扫描边生成属性
        • 可以逐步生成属性的各个部分, 并增量式地添加到最终的属性值中
        • 三个条件
          • 存在一个主属性, 且是综合属性
          • 综合属性是由产生式体中的各非终结符号的主属性连接而得到, 同时还会连接一些其他元素
          • 主属性的连接顺序与产生式体顺序相同
        • 思想: 适当的时候”发出”元素, 拼接到适当的地方