现代编译器使用哪些解析器?

Which parsers do the modern compilers use?

我找不到关于某些现代编译器的解析器的任何信息,尤其是:

他们使用的是 LL(k)、LR(k)、混合物还是其他东西?是否有任何网站列出了关于 compilers/parsers 的多种语言的信息?由于这些编译器通常被认为是 "modern",我对它们的解析技术很感兴趣。

他们三个都使用特殊的 hand-built 解析器,松散地基于预测 (top-down) 解析,在 top-down 解析是non-deterministic.

如果您想这样做的话,我当然不会推荐将此作为构建解析器的模型。使用解析器生成器构建解析器要容易得多;生成的解析器将更短且更易于阅读,如果你做对了,它将是 self-documenting,因为用于生成解析器的语法正是你想要放入文档中的语法。

既然如此,您可能会想知道为什么只有这么少的 "modern" 语言使用解析器生成器。除了与编程心理学相关的解释外,我对此没有很好的答案。手工编写一个解析器需要大量的工作和巨大的痛苦,但这远不是编写编译器的最大任务——良好的优化是一个复杂得多的问题,而且没有简单的生成器工具可以解决这个问题——所以劳动可能不像人们想象的那样是一种抑制因素。 "only" 几千个 LoC 就可以解析大多数语言,这似乎比学习解析器生成器的来龙去脉更容易。

一个常见的解释是,使用 top-down 解析器显然更容易生成良好的编译器错误消息,并且良好的错误消息对于语言采用非常重要。 (例如,由于 C++ 模板中的小拼写错误导致的可悲的不可读错误消息显然是采用 C++ 的障碍。即使在今天,模板编译错误消息也难以阅读,但它们已经变得更好了。)这并不是说用 bottom-up 语法编写好的编译器错误消息处理程序是不可能的,但如何做到这一点并不总是很明显。

另一种解释是,大多数人似乎都想用自己的语言编写解析器(和编译器)。通常的策略是用其他一些令人反感的语言构建一个 quick-and-dirty 迷你编译器,然后用它来 bootstrap 一个正在开发的语言的华丽优雅的编译器。 (这种心态导致了一个奇怪的事实,即大多数语言首先针对编译器编写进行了优化,尽管每种语言很可能只会编写一个编译器。)

bootstrap 策略使得使用解析器生成器变得困难,因为解析器生成器本身必须首先重写才能生成新语言的代码。在一个完美的世界中,将一种新语言的代码生成改进到现有的解析器生成器中是很容易的,但现实情况却大不相同。 (如果你想接手这个项目,我强烈建议使用 Lemon 解析器作为基础,而不是任何 yacc 或 bison 的实现。这不是微不足道的,但至少你不需要学习如何在M4.)

this bug report, the major downside of handbuilt parsers is that there is no easy way to verify that they actually recognise the language documented by the published grammar. The Rust source tree now includes a Bison/Flex parser which produces an AST, although it is not used by the Rust compiler (which is written in Rust, see above). Despite its flaws, this grammar 中所述,它比生产解析器更接近已发布的语法。但它不会尝试生成任何类型的信息性语法错误消息(或者,实际上,生成代码)。