c++ - 抽象树与解析器树

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center提供指导。




已关闭8年。




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

我想解析一种语言，例如C(只是C的一个子集，进行一些更改以使其更加面向伪代码)，但不是为了将其翻译为其他输出语言/文件，而是为了执行其语句以动画化其执行过程(我使用Qt绘制)。 C子集的一个功能是启用嵌套作用域。我对我在ST和AST之间进行选择的怀疑来自符号表。总体思路是(使用Boost.spirit):

通过自定义Boost.spirit解析器解析源代码文件。

语义操作会生成一个语法树，它只是源代码语法树的副本(或者也是Boost.spirit内部语法树的副本，但具有我自己的类和结构)。因此，没有AST。

手持此ST，程序从上至下读取该语法树，如下所示:

执行第一句话。

使用新值(句子的结果)上载符号表。

将符号表的实际状态保存在程序状态堆栈中。

到3.1，直到ST被完全处理。

对算法进行动画处理，以读取和绘制程序状态堆栈。

两个理由:

如果我使用AST，则在解析后会丢失有关变量声明，其类型等的信息。因此，我必须通过解析器的语义 Action 来使用符号表，这会使解析器的编写和理解变得复杂。而且，我必须一直使用带有所有变量的符号表，而不管实际范围是什么(如果我在范围i中，则只需要范围i，i-1，....，1；不需要整个算法的所有范围)。这会花费内存。

在程序状态堆栈中，我只需要实际作用域和先前作用域的变量，以免通过动画使算法的可理解性复杂化。如果使用ST，则必须先删除所有不需要的符号，然后再将其保存到堆栈中。这会花费时间。

具有动态范围的静态符号表比动态符号表更难以设计和使用。静态符号表必须为每个范围具有一个标识符(例如)，并将树的每个节点与每个标识符相关联。动态符号表更容易工作，因为如果我在范围i中，则只需要两个“ vector ”(也许是双队列和堆栈):

一个带有符号及其相关信息的容器(双队列？):容器中的最后一个变量是最近的声明变量。

整数的容器(堆栈)，显示每个作用域的开始(双队列的索引)。

例如，对于范围i:

容器1:[x y z x a b z f a z]

容器2:[0 3 6 8]

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

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

两个问题:

哪个更好？

存在任何形式来提取Spirit内部树或对其进行自定义以不进行复制吗？

最佳答案

我认为您正在寻找的是代表程序语义(相对于语法)的抽象语义图(ASG)。您可以做的是:

将源解析为AST，然后解析为

将AST转换为ASG，最后

走ASG来执行实际代码。

另外，我想说您 可以确实构建一个不太抽象的AST。例如，我当前正在构建自己的脚本语言解释器，而AST将包含变量名(这对于调试解析器/解释器和解析程序本身很有用)。

关于c++ - 抽象树与解析器树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13442147/

上一篇：c++ - 有人可以解释这个 OpenGL 代码吗？

下一篇：c++ - 光线追踪三角形网格对象

相关文章：

c++ - 两次连续的套接字读取，第二次读取不起作用

c++ - 双三次图像降尺度

c++ - Qsort()比较struct int之和

c++ - 分配给不同的基类时，我可以多次使用 std::move 吗？

java - 解释对多个 XML 文档应用多个 xpath 查询的规则

c++ - 如何将现有的回调接口(interface)转换为使用 boost 信号和插槽

c++ - 通过容器的 protected 继承来 boost foreach

c++ - 在 C++ 中解析逗号分隔的整数/整数范围

c++ - 解析字符串会产生重复值

c++ - 引用c++临时字符串的内容

Answer 1

我认为您正在寻找的是代表程序语义(相对于语法)的抽象语义图(ASG)。您可以做的是:

将源解析为AST，然后解析为

将AST转换为ASG，最后

走ASG来执行实际代码。

另外，我想说您 可以确实构建一个不太抽象的AST。例如，我当前正在构建自己的脚本语言解释器，而AST将包含变量名(这对于调试解析器/解释器和解析程序本身很有用)。