29

根据 Vala 文档：“在 0.3.1 之前，Vala 的解析器是经典的 flex 扫描器和 Bison LALR 解析器的组合。但从提交 eba85a 开始，解析器是手工制作的递归下降解析器。” 我的问题是：为什么？

这个问题可以针对任何不使用解析器生成器的编译器。从解析器生成器到手工解析器的这种转变的利弊是什么？为编译器使用解析器生成器（Bison、ANTLR）有什么缺点？

作为旁注：我特别对 Vala 感兴趣，因为我喜欢让语言具有现代特性和简洁语法但可编译成“本机”和“非托管”高级语言（在 Vala 的情况下为 C）的想法。到目前为止，我只找到了 Vala。我正在考虑通过使 Vala（或类似语言）可编译为 C++（由 Qt 库支持）来获得乐趣。但由于我不想发明全新的语言，我正在考虑采用一些现有的语法。显然，手工制作的解析器没有我可能重用的书面形式语法。欢迎您对这个想法发表评论（整个想法很愚蠢吗？）。

4

5 回答 5

28

在我的职业生涯中，我编写了六种手工制作的解析器（在大多数情况下是递归下降解析器，也称为自顶向下解析器），并且已经看到解析器生成器生成的解析器，我必须承认我对解析器生成器有偏见。

以下是每种方法的一些优点和缺点。

解析器生成器

优点：

  • 快速获得一个可以工作的解析器（至少如果你不知道如何手动编码）。

缺点：

  • 生成的代码很难理解和调试。
  • 难以实施正确的错误处理。生成器将为语法正确的代码创建正确的解析器，但会阻塞不正确的代码，并且在大多数情况下将无法提供正确的错误消息。
  • 解析器生成器中的错误可能会停止您的项目。您需要修复其他人代码中的错误（如果源代码可用），等待作者修复它或解决错误（如果可能的话）。

手工制作的递归下降解析器

优点：

  • 生成的代码很容易理解。递归解析器通常有一个对应于每种语言结构的函数，例如解析“while”语句的parseWhile，解析声明的parseDeclaration 等等。理解和调试解析器很容易。
  • 很容易提供有意义的错误消息，从错误中恢复并以在特定情况下最有意义的方式继续解析。

缺点：

  • 手动编写解析器代码需要一些时间，特别是如果您没有使用这些东西的经验。

  • 解析器可能有点慢。这适用于所有递归解析器，而不仅仅是手写的。具有对应于每种语言构造的一个函数来解析简单的数字文字，解析器可以进行十几个或更多嵌套调用，例如从 parseExpression 到 parseAddition、parseMultiplication 等。 parseLiteral。函数调用在像 C 这样的语言中相对便宜，但仍然需要很长时间。

加速递归解析器的一种解决方案是用通常更快的自下而上子解析器替换递归解析器的一部分。这种子解析器的自然候选者是具有几个优先级的几乎统一语法的表达式（即二元和一元表达式）。表达式的自下而上解析器通常也很容易编写代码，它通常只是一个循环，从词法分析器获取输入标记、一堆值和运算符标记的运算符优先级查找表。

于 2013-04-03T06:31:49.733 回答
16

LR(1) 和 LALR(1) 解析器非常非常烦人，原因有两个：

  1. 解析器生成器不太擅长生成有用的错误消息。
  2. 某些类型的歧义，例如 C 风格的 if-else 块，让编写语法变得非常痛苦。

另一方面，LL(1) 语法在这两方面都做得更好。LL(1) 文法的结构使得它们很容易编码为递归下降解析器，因此处理解析器生成器并不是真正的胜利。

此外，对于 Vala，解析器和编译器本身以库的形式呈现，因此您可以使用 Vala 编译器库为 Vala 编译器构建自定义后端，并免费获得所有解析和类型检查等。

于 2013-03-28T03:38:21.117 回答
2

我知道这不会是确定的，如果你的问题不是特别与 Vala 相关，我不会打扰，但因为它们是......

那时我并没有过多地参与这个项目，所以我对一些细节不是很清楚，但我记得 Vala 切换时的一个重要原因是dogfooding。我不确定这是主要动机，但我确实记得这是一个因素。

可维护性也是一个问题。该补丁用 Vala 中的一个较小的解析器替换了一个用 C/Bison/YACC 编写的更大的解析器（相对而言很少有人对后两者有丰富的经验）（几乎任何对 valac 感兴趣的人都可能知道并且很熟悉）。

更好的错误报告也是一个目标，IIRC。

我不知道这是否是一个因素，但手写解析器是递归下降解析器。我知道 ANTLR 会生成这些，ANTLR 是用 Java 编写的，这是一个非常重的依赖项（是的，我知道它不是运行时依赖项，但仍然如此）。

作为旁注：我特别对 Vala 感兴趣，因为我喜欢让语言具有现代特性和简洁语法但可编译成“本机”和“非托管”高级语言（在 Vala 的情况下为 C）的想法。到目前为止，我只找到了 Vala。我正在考虑通过使 Vala（或类似语言）可编译为 C++（由 Qt 库支持）来获得乐趣。但由于我不想发明全新的语言，我正在考虑采用一些现有的语法。显然，手工制作的解析器没有我可能重用的书面形式语法。欢迎您对这个想法发表评论（整个想法很愚蠢吗？）。

很多 Vala 确实反映了 GObject 做出的决定，在 C++/Qt 中事情可能会或可能不会以相同的方式工作。如果您的目标是用 Qt/C++ 替换 valac 中的 GObject/C，那么您的工作可能比您预期的要多。但是，如果您只想让 Vala 可以访问 C++ 和 Qt 库，那当然是可能的。事实上，Luca Bruno 大约一年前就开始研究这个了（参见wip/cpp分支）。由于时间不足，而不是技术问题，它已经有一段时间没有看到活动了。

于 2013-03-29T01:27:28.747 回答
0

根据 Vala 文档：“在 0.3.1 之前，Vala 的解析器是经典的 flex 扫描器和 Bison LALR 解析器的组合。但从 Commit eba85a 开始，解析器是手工制作的递归下降解析器。” 我的问题是：为什么？

在这里，我专门询问 Vala，尽管这个问题可以针对任何不使用解析器生成器的编译器。从解析器生成器到手工解析器的这种转变的利弊是什么？为编译器使用解析器生成器（Bison、ANTLR）有什么缺点？

也许程序员发现了解析器生成器没有发现的一些优化途径，而这些优化途径需要完全不同的解析算法。或者，也许解析器生成器在 C89 中生成代码，而程序员决定为 C99 或 C11 重构会提高易读性。

作为旁注：我特别对 Vala 感兴趣，因为我喜欢让语言具有现代特性和简洁语法但可编译成“本机”和“非托管”高级语言（在 Vala 的情况下为 C）的想法。

只是一个简短的说明： C 不是native。它源于可移植性，因为它旨在抽象出那些在移植时导致程序员如此痛苦的硬件/操作系统特定细节。例如，想想为每个操作系统和/或文件系统使用完全不同的fopen的痛苦；我的意思不仅是功能上的不同，还包括输入和输出期望的不同，例如。不同的参数，不同的返回值。同样，C11 引入了可移植线程；使用线程的代码将能够使用相同的符合 C11 的代码来针对所有实现线程的操作系统。

到目前为止，我已经找到了 Vala。我正在考虑通过使 Vala（或类似语言）可编译为 C++（由 Qt 库支持）来获得乐趣。但由于我不想发明全新的语言，我正在考虑采用一些现有的语法。显然，手工制作的解析器没有我可能重用的书面形式语法。欢迎您对这个想法发表评论（整个想法很愚蠢吗？）。

使用手工制作的解析器轻松生成 C++ 代码可能是可行的，所以我不会这么快就放弃这个选项；旧的 flex/bison 解析器生成器可能更有用，也可能不更有用。但是，这不是您唯一的选择。无论如何，我很想广泛研究规范。

于 2013-03-28T02:59:36.473 回答
0

奇怪的是，这些作者从野牛变成了 RD。大多数人会朝相反的方向走。

我能看到做 Vala 作者所做的唯一真正原因是更好的错误恢复，或者他们的语法可能不是很干净。

我想你会发现大多数新语言都是从手写解析器开始的，因为作者对他们自己的新语言有一种感觉，并确切地知道他们想要做什么。在某些情况下，作者学习如何编写编译器。C 是一个典型的例子，C++ 也是。在进化的后期，可能会替换生成的解析器。另一方面，现有标准语言的编译器可以通过解析器生成器更快地开发，甚至可能通过现有语法：上市时间是这些项目的关键业务参数。

于 2013-03-29T00:04:11.373 回答