3

我需要您的意见，以便在生成解析器树 (ST) 或生成抽象语法树 (AST) 之间选择最佳选择。这是上下文：

我想解析像 C 这样的语言（只是 C 的一个子集，进行了一些更改以使其更加面向伪代码），但不是为了将它翻译成其他输出语言/文件，而是为了执行它的句子以动画其执行过程（我用Qt来画）。这个 C 子集的一个特性是它支持嵌套范围。我对我在 ST 和 AST 之间的选择的怀疑来自符号表。总体思路是（使用 Boost.spirit）：

  1. 通过自定义 Boost.spirit 解析器解析源代码文件。
  2. 语义操作产生一个语法树，只是源代码语法树的副本（或者也是 Boost.spirit 内部语法树的副本，但具有我自己的类和结构）。因此，没有 AST。
  3. 有了这个 ST，程序按照自上而下的方向读取这个语法树，如下所示：
    1. 执行第一句话。
    2. 使用新的（句子的结果）值上传符号表。
    3. 将符号表的实际状态保存在程序状态堆栈中。
    4. 到 3.1 直到 ST 完全处理完毕。
    5. 动画算法读取和绘制程序状态堆栈。

两个理由：

  1. 如果我使用 AST，我会在解析后丢失有关变量声明、其类型等的信息。因此，我必须通过解析器的语义动作来处理符号表，使解析器的编写和理解变得复杂。此外，无论实际范围如何，我都必须一直使用包含所有变量的符号表（如果我在范围 i 中，只需要范围 i、i-1、....、1；不是整个算法的所有范围）。这会消耗内存。
  2. 在我的程序状态堆栈中，我只需要实际和先前范围的变量，以免通过动画使算法的可理解性复杂化。如果我使用 ST，我必须先删除所有不需要的符号，然后再将其保存到堆栈中。这会花费时间。

  3. 具有控制范围的静态符号表比动态符号表更难设计和使用。静态符号表必须为每个作用域提供一个标识符（例如），并将树的每个节点与每个标识符相关联。动态符号表更容易工作，因为如果我在 i 范围内，只需要两个“向量”（可能是双队列和堆栈）：

    • 带有符号及其相关信息的容器（双队列？）：容器中的最后一个变量是最近的声明变量。
    • 整数的容器（堆栈），显示每个范围的开始（双队列的索引）。

    例如，对于范围 i：

    • 容器 1：[xyzxabzfaz]
    • 容器 2：[0 3 6 8]

    如果我离开范围 i，我只需要擦除最后一个整数和从位置 8 到末尾的符号。树保持不变。

  4. 由于我必须在执行时间内执行每个句子，因此 ST 有助于我的执行。

两个问题：

  1. 那哪个更好呢？
  2. 是否存在任何形式来提取Spirit的内部树或定制它以便不复制它？
4

1 回答 1

1

我认为您正在寻找的是一个抽象语义图 (ASG)，它表示程序的语义（与语法相反）。你可以做的是：

  1. 将源解析为 AST，然后
  2. 将 AST 转换为 ASG，最后
  3. 走 ASG 以执行实际代码。

另外，我想说你确实可以构建一个不太抽象的 AST；例如，我目前正在构建自己的脚本语言解释器，AST 将包含变量名称（这对于调试解析器/解释器以及解析的程序本身也很有用）。

于 2012-11-18T20:58:17.543 回答