Skip to content

语法制导的编译技术

语法制导

  • 将文法符号和某些属性相关联，并通过语义规则来描述如何计算属性的值
  • 语法制导翻译就是在产生式体中加入语义动作，在适当时候执行动作\(E\to E_{1}+T \ \ \{print'+'\}\)

  • 语义规则确定了节点上属性的取值和计算方式

  • 语法制导 SDD 是上下文无关文法和属性、规则的结合

    • 属性和文法符号关联，确定各个文法符号需要哪些属性，对于节点 X 的属性 a，表示为 X.a
    • 规则和产生式相关联

  • 综合属性

    • 节点 N 的属性值由 N 的产生式所关联的语义规则来定义
    • 即通过子节点或 N 本身的属性值来定义
    • 允许依赖于 N 本身的继承属性
  • 继承属性
    • 结点 N 的属性值由 N 的父结点所关联的语义规则来定义
    • 依赖于 N 的父结点、N 本身和 N 的兄弟结点上的属性值（不允许通过子节点来定义）
  • 终结符号只有综合属性，没有继承属性：终结符号的属性值是由词法分析器提供的词法值，SDD 中没有计算终结符号的属性值的语义规则
  • image.png|525

SDD

  • 语义规则不应该有复杂的副作用，要求副作用不影响其他属性求值。没有副作用的 SDD 称为属性文法
    • 每个语义规则仅仅通过它的输入属性（继承属性和综合属性）计算出其输出属性的值，而不依赖于外部状态，也不改变外部状态
  • 一个因为改变了全局变量造成了副作用的例子： 
    Expr -> Expr + Term  {Expr.val = Expr.val + Term.val; count++;}
Expr -> Term         {Expr.val = Term.val;}
Term -> 0            {Term.val = 0; count++;}
Term -> 1            {Term.val = 1; count++;}

注释语法分析树

  • 注释语法分析树：包含了各个节点各属性值的语法分析树
    • 对于任意的输入串，首先构造出相应的分析树
    • 给各个结点 (根据其文法符号) 加上相应的属性
    • 按照语义规则计算这些属性的值
  • S 属性的 SDD（只含综合属性） 一定可以通过自底向上的方式求值

  • image.png|475

  • SDD 无法计算循环定义的语法 \(A\to B \ \ \ A.s=B.i \ \ \ B.i=A.s+1\)

  • 适用于自顶向下分析的 SSD

    • 对于自顶向下分析需要先去除左递归，但是这又可能破坏结构
    • 对于消除左递归后的式子 \(T\to FT' \ \ \ T'\to*FT'|\varepsilon\) (\(T\to T*F|F\))
    • image.png|475
    • T 对应的项中，第一个因子对应 F，而运算符却在 T' 中需要用继承属性来完成这样的计算
    • image.png|500
    • 即 image.png|475 [[作业p5]]

SDD 的求值顺序

  • 需要先求出 N 的属性所依赖的节点的属性，才能计算得到 N 的属性

  • 使用依赖图来表示计算顺序：计算顺序组成偏序关系, 存在环则说明无解

  • 依赖图描述了分析书上各个属性之间的信息流（计算顺序）

    • \(a\to b\) 表示计算 \(b\) 需要 \(a\) 的值
    • 对于分析树结点 N，与 N 关联的每个属性 a 都对应依赖图的一个结点N.a
    • image.png|500
  • 各个属性值需要按照依赖图的拓扑排序的顺序进行计算
    • 给定一个 SDD，很难判定是否存在一棵分析树，其对应的依赖图包含环
    • SL 属性的 SDD 一定无环，并且有固定的计算顺序
S 属性的 SDD
  • 每个属性都是综合属性，都是根据子构造的属性来计算父构造的属性
  • 可以与自底向上或自顶向下的语法分析过程一起计算
    • 自底向上：构造分析树节点同时计算相关的属性（此时子节点的属性已经计算完毕）
    • 自顶向下：后序思想，最后计算 A 的属性（此时其他过程已经完成）
      • image.png|475
L 属性的 SDD

  • 每个属性是综合属性或继承属性（\(A\to X_{a}\dots X_{n}\) 中 \(X_{i}.a\) 的计算只用 A 的继承属性或 \(X_{j}(j<i)\) 的继承属性或综合属性）

    • 即在一个产生式体所关联的各个属性之间总是从左到右，而不能是从右到左；总是使用来自上/左边的属性信息
    • 对于非终结符号 \(A\)，参数为继承属性，返回值为综合属性
    • image.png|450

  • image.png|375

具有受控副作用的语义规则

  • 属性文法虽然没有副作用，但是增加了描述的复杂度
    • 比如标识符表就需要作为属性传递
    • 但是如果把标识符表作为全局变量，就可以简化这个过程

  • 受控的副作用

    • 不会对属性求值产生约束，仍然可以按照任何拓扑顺序求值而不影响结果
    • 也可能对求值的过程添加简单的约束

  • 使用全局标识符表，通过 addType 将类型信息加入到标识符表

    • image.png|350
  • \(L → E n \{ print(E.val); \}\)
    • 通过副作用打印出 E 的值（输出操作通常会改变程序的状态，因此认为是有副作用的）
    • 但是因为总在最后执行，不影响其它属性的求值

SDD 的应用

抽象语法树的构造
  • 抽象语法树不包含源代码中可能出现的不影响程序语义的元素，比如括号、特定的关键字等（删除了不影响程序意义的如括号分号等信息，忽略掉非本质的东西）
    • 每个节点代表一个语法结构，对应于运算符
    • 节点的子节点表示其子结构，对应于运算分量

  • 每个节点用一个对象表示

    • 叶子节点中只存放词法值
    • 内部节点中存放了 op 值和参数

  • image.png|500

  • image.png|500
    • 对于生产式 3、4 没有产生任何新节点

  • 使用后序遍历进行求值

  • 一个自顶向下处理的 L 属性 SDD 的例子

    • image.png|500
    • image.png|500
类型结构
  • 生成类型表达式的 SDD
    • image.png
    • 类型包括两个部分：基本类型 B 及分量 C
    • 数组构造算符 array：array (2, array (3, int))表示抽象的 2 x 3 的二维数组
  • image.png|500

语法制导的翻译方案 SDT

  • 在产生式体中嵌入语义动作 (程序片断) 的上下文无关文法
  • SDT 是SDD 的一种实现方式，它通过嵌入动作（如代码片段）到语法分析树的构造过程中，以实现对属性的计算和其他翻译动作
  • 基本实现
    • 建立语法分析树
    • 将语义动作看作是虚拟结点
    • 从左到右、深度优先地遍历分析树，在访问虚拟结点时执行相应的语义动作
    • |475

  • 用 SDT 实现两类重要的 SDD (无需建分析树)

    • 基本文法是 LR 的，且 SDD 是 S 属性的
    • 基本文法是 LL 的，且 SDD 是 L 属性的

  • 在语法分析过程中实现 SDT：

    • 在语法分析时即时进行，不实现构造完整的语法分析树，这样编译效率更高
  • 可以在分析过程中实现的条件
    • 即使基础文法可以应用某种分析技术，仍可能因为动作的缘故导致此技术不可应用（即引入语义动作之后可能导致 LL、LR 等技术不再适用）
    • 将每个语义动作替换为独有的非终结符号 Mi，其中每个 Mi 的产生式为 Mi → ε（ε代表空串）。这一步是将原本直接嵌入在文法中的语义动作抽象为特定的非终结符号，以便于分析。
    • 分析新的文法：通过上一步的替换，我们得到了一个只含有非终结符号表示语义动作的新文法。接下来，分析这个新文法是否可以被某种语法分析方法（如 LL、LR 分析方法）处理。如果可以，那么原始的 SDT 就可以在这种分析方法的框架下实现。
    • 可行性：如果替换语义动作后的新文法可以被成功分析，说明原始的 SDT 可以在语法分析过程中实现，即可以在解析的同时执行语义动作，而不需要构建完整的语法分析树。
    • image.png|500

后缀翻译

  • 后缀 SDT：所有动作都在产生式最右端的 SDT
    • 文法可以自底向上分析 (即 LR 的) 且其 SDD 是 S 属性的，必然可以构造出后缀 SDT
    • 将每个语义规则看作是一个赋值语义动作
    • 将所有的语义动作放在规则的最右端
    • image.png|400

  • 反例 (1 的动作会提前执行，不会等到规则全部识别) 

    1. A → { print("A1") } B C
2. B → b { print("B") }
3. C → c

  • 后缀分析的栈实现

    • 可以在 LR 语法分析的过程中实现（LR 分析器是一种自底向上的分析方法，它通过不断地将输入符号移入栈中，并在识别到某个产生式的右部时进行归约，将其替换为产生式的左部符号）
    • 当 LR 分析器识别到一个产生式的右部，并准备进行归约时，会执行与该产生式相关联的语义动作。这时，产生式右部的各个文法符号的属性信息都可以在栈中找到
      • image.png|375
    • 如果不同的文法符号有不同的属性集合，我们可以使用 union 来保存这些属性值
  • image.png|500

产生式内部带有语义动作的 SDT

  • 不是所有动作都在产生式最右端的 SDT（与后缀翻译相对应）
  • 动作左边的所有符号 (以及动作) 处理完成后，就立刻执行这个动作：B → X { a } Y
    • 自底向上分析时，在 X 出现在栈顶时执行动作 a
    • 自顶向下分析时，在试图展开 Y 或者在输入中检测到 Y 的时刻执行 a

  • 对一般的 SDT，都可以先建立分析树再遍历执行动作；不是所有的 SDT 都可以在分析过程中实现，后缀 SDT 以及 L 属性对应的 SDT 可以在分析时完成

  • 消除左递归的 SDT 的转换

L 属性的 SDT

  • 若基础文法是 LL 的，则可以将 L 属性 SDD 转换成一个 SDT，该 SDT 可以在自顶向下的分析过程中实现
  • 从 L 属性的 SDD 到 SDT 的转换
    • 将赋值语义动作放到相应产生式 A → \(X 1 X 2 … Xn\) 的适当位置
    • 计算 Xi 继承属性的动作插入到产生式体中 Xi 的左边
    • 计算产生式头 A 综合属性的动作在产生式的最右边
  • S → while (C) S1
    • 首先对 C 求值，若为真，则控制转向 S 1 的开始处
    • 若为假，则转向 while 语句的后续语句开始处
    • S 1 结束时，要能够跳转到 while 语句的代码开始处
    • image.png|500
    • L1 = new(); 和 L2 = new();： 这两行为循环的两个关键点生成新的标签（Label）。L1 用于循环条件的开始部分，而 L2 用于循环体的开始部分。
    • S1.next = L1;： 这一行设置了循环体（记为 S1）结束后应该跳转到的下一标签，这里是跳回到循环条件的检查部分，实现循环的效果。
    • C.false = S.next;： 设置条件 C 为假时（即循环条件不满足时）的跳转位置。这里用 S.next 表示循环结束后代码继续执行的位置，也就是整个 while 结构的下一个语句。
    • C.true = L2;： 设置条件 C 为真时（即循环条件满足时）的跳转位置，这里是跳到循环体的开始。
    • S.code = label || L1 || C.code || label || L2 || S1.code： 这是生成最终的中间代码的步骤。它是通过拼接以下几部分构成的：
      • label || L1：放置一个标签，用于循环条件部分的开始。
      • C.code：条件 C 的中间代码，这部分代码会计算循环条件并跳转到 L2 或 S.next。
      • label || L2：放置一个标签，用于循环体的开始。
      • S1.code：循环体 S1 的中间代码。
    • 除了S.code 外均为继承属性，转化为 SDT 如下
    • image.png|500
L 属性 SDD 的实现（递归下降语法分析）
  • 使用递归下降的语法分析器
    • 每个非终结符号对应一个函数
    • 函数的参数接受继承属性，返回值包含了综合属性
  • 在函数体中
    • 首先选择适当的产生式
    • 使用局部变量来保存属性
    • 对于产生式体中的终结符号，读入符号并获取其 (经词法分析得到的) 综合属性
    • 对于非终结符号，使用适当的方式调用相应函数，并记录返回值

  • image.png|500

  • 边扫描边生成属性

    • 有些属性可能非常大（code 属性就可能是很长的字符串），对这样的大属性进行运算的效率很低
    • 可逐步生成属性的各个部分，并增量式地添加到最终的属性值中 (如数组或输出文件中)；增量式地添加属性则意味着我们将这些小部分逐一加入到最终的属性值中。这种方法类似于流式处理，可以是向一个数组中添加元素，或者直接写入到输出文件中。
  • 条件
    • 存在一个主属性，且其为综合属性
    • 在产生式中，主属性是通过产生式体中各非终结符号的主属性连接而得到：在处理一个产生式时，我们可以逐个处理产生式体中的每个非终结符号，生成它们的主属性，然后将这些主属性拼接起来。
    • 各个非终结符号的主属性的连接顺序与它们在产生式体中的顺序相同：这保证了生成的属性与程序的实际执行顺序相匹配。
  • 对于语句 S → while (C) S1，假设它的中间代码生成规则是 { S.code = label || L1 || C.code || label || L2 || S1.code }。通常我们需要生成并保存整个字符串 S.code。但如果我们改为边扫描语法结构边输出代码，就可以先输出 label L1，然后调用处理条件 C 的函数（输出 C 的代码），接着输出 label L2，最后调用处理语句 S1 的函数（输出 S1 的代码）。这样，我们不需要在内存中维护整个 S.code 字符串。而是直接按照执行顺序输出每个部分
  • image.png|500
  • image.png