问题标签 [parse-tree]

我构建了一个词法分析器，可以从输入中流出标记，但我不确定如何构建该过程的下一步 - 解析树。有没有人有任何好的资源或例子来说明如何做到这一点？

是否可以在使用递归下降解析器检查数据是否匹配语法的同时生成解析树？

如果是这样，当我递归下降时，我将使用什么方法来构建一棵树？

谢谢，博达赛多。

注意：我是解析新手。（已经问了几个关于 SO 的问题，我正在变得更好。）

有人知道俄语的语义解析器吗？我试图配置链接语法站点提供的链接解析器，但无济于事。

我希望有一个可以在 Mac 上运行并生成解析树的 prolog 或类似 lisp 的表示的系统（但 XML 输出也很好）。

我正在尝试使用简单的数学运算符（+、-、*、/ 和括号）为给定的字符串生成语法树。给定字符串“1 + 2 * 3”：

它应该返回一个像这样的数组：

我做了一个函数来转换 [1,"+",2,"*",3] 中的 "1 + 2 * 3"。

问题是：我不知道优先考虑某些操作。

我的代码是：

我一直在使用 Qi 和 Karma 对几种小语言进行一些处理。大多数语法都很小（20-40 条规则）。我几乎完全可以使用自动规则，所以我的解析树完全由变体、结构和 std::vectors 组成。

此设置非常适用于常见情况：
1) 解析某些东西 (Qi)，
2) 对解析树 (访问者) 进行少量操作，以及
3) 输出某些东西 (Karma)。

但是，我担心如果我想对语法树进行复杂的结构更改（例如移动大子树）会发生什么。考虑以下玩具示例：

使用自动规则的 s-expr 样式逻辑表达式的语法...

...这导致解析树表示看起来像这样...

假设我有一个看起来像这样的解析树：

（省略号的意思是“有更多类似形状的孩子pand。”）

现在，假设我想否定每个por节点，所以最终结果是：

对于每个por子树，直接的方法是：
- 创建pnot节点
（构造中的副本por）；- 在节点
中重新分配适当的向量槽 （复制节点及其子树）。 pand
pnotpor

或者，我可以构建一个单独的向量，然后pand批量替换（交换）向量，从而消除第二轮复制。

与基于指针的树表示相比，所有这些似乎都很麻烦，这将允许在pnot不复制现有节点的情况下插入节点。我的问题：

有没有办法使用符合自动规则的数据结构来避免复制繁重的树操作？我是否应该硬着头皮只使用非自动规则来构建基于指针的 AST（例如，http ://boost-spirit.com/home/2010/03/11/s-expressions-and-variants/ ）？

有没有人有一个很好的工具来绘制由上下文无关语法产生的解析树？有这个问题，但它专门处理有限自动机而不是解析树。我一直在使用graphviz，但是必须单独标记每个节点等有点烦人。

它们是由编译过程的不同阶段生成的吗？还是它们只是同一事物的不同名称？

可能重复：
解析树和 AST 有什么区别？

我需要知道抽象解析树和解析树有什么区别。

我在编译器设计书中找到了这两个术语，我想知道它们分别代表什么，以及它们有何不同。

我在互联网上搜索，发现解析树也称为具体语法树（CST）。

我无法弄清楚 antlr3 API，因此我可以在一些 javascript 代码中生成和使用解析树。当我使用 antlrWorks（他们的 IDE）打开语法文件时，解释器能够向我显示解析树，它甚至是正确的。

我在跟踪有关如何使用 antlr3 运行时在我的代码中获取此解析树的资源时遇到了很多困难。我一直在搞乱运行时和解析器文件中的各种功能，但无济于事：

由于 antlrWorks 可以在没有我自己的任何树语法的情况下显示解析树，并且由于我已经阅读了 antlr 自动从语法文件生成解析树，我假设我可以使用一些运行时函数访问这个基本的解析树。大概不知道。我的这种想法正确吗？