parsing - 如何将令牌流转换为解析树

Question

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

Answer 1

我真的会推荐http://www.antlr.org/，当然还有经典的 Dragon Compilers 书。

对于像 JavaScript 这样的简单语言，手动滚动递归下降解析器并不难，但使用 yacc 或 antlr 这样的工具几乎总是更容易。

我想回到你问题的基础，你真的想研究 BNF 式的语法语法并为你的目标选择一种语法。如果你有这个，解析树应该会掉出来，成为该语法的“实例”表现。

另外，不要试图将解析树的创建变成最终解决方案（例如生成代码或其他什么）。它可能看起来可行且更有效；但总会有一段时间，你真的希望你有那个解析树'原样'。

Answer 2

您应该为您的平台研究解析器生成器工具。解析器生成器允许您为您的语言指定上下文无关语法。该语言由许多规则组成，这些规则将一系列符号“简化”为一个新符号。您通常还可以为不同的规则指定优先级和关联性，以消除语言中的歧义。例如，一个非常简单的计算器语言可能看起来像这样：

%left PLUS, MINUS           # low precedence, evaluated left-to-right
%left TIMES, DIV            # high precedence, left-to-right

expr ::= INT
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIV expr
| LEFT_PAREN expr RIGHT_PAREN

通常，您可以将一些代码与每个规则相关联，以从该规则中的其他符号构造一个新值（在本例中为表达式）。解析器生成器将接收语法并以您的语言生成代码，将令牌流转换为解析树。

大多数解析器生成器都是特定于语言的。ANTLR 是众所周知的，支持 C、C++、Objective C、Java 和 Python。不过听说很难用。我在 C/C++ 中使用过 bison，在 Java 中使用过 CUP，在 OCaml 中使用过 ocamlyacc，它们都非常好。如果您已经在使用词法分析器生成器，则应该寻找专门与之兼容的解析器生成器。

Answer 3

我相信一种常见的方法是使用Finite State Machine。例如，如果您读取一个操作数，您将进入下一个期望操作符的状态，并且您通常使用该操作符作为操作数的根节点，依此类推。

Answer 4

正如上面 Marcos Marin 所描述的，如果你想自己做的话，一个使用 BNF 中的语言规则来解析你的令牌列表的状态机可以解决问题。只是，正如 Paul Hollingsworth 在上面的评论中所说，更简单的方法是使用具有简单 FiFo 内存堆栈的下推自动机。在你的语法中，每一类令牌都有一个下一个预期的令牌，它也在你的状态机中表示。堆栈用于“记住”前一个标记类是什么，以减少所需的状态（可以在没有堆栈的情况下完成，但您需要为语法树中的每个类和子类拆分一个新状态）。接受状态将是（在自然语言和大多数编程语言中）起始状态，在特定情况下可能是其他一些状态。

如果您想使用工具（速度更快，范围更小），Antlr将是我的建议。祝你好运！