为什么有些编译器更喜欢手工制作的解析器而非解析器生成器？

Question

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

问题可以解决任何不使用解析器生成器的编译器.从解析器生成器到手工解析器的这种转变的优缺点是什么？将解析器生成器(Bison,ANTLR)用于编译器有什么缺点？

作为旁注:我对Vala特别感兴趣,因为我喜欢使用具有现代功能和清晰语法的语言,但可编译为"本机"和"非托管"高级语言(在Vala的情况下为C).到目前为止我只发现了Vala.我想通过使Vala(或类似语言)可编译为C++(由Qt libs支持)来获得乐趣.但是因为我不想发明全新的语言,所以我想考虑一些现有的语法.显然,手工制作的解析器没有我可能重用的书面形式语法.你对这个想法的评论是受欢迎的(整个想法是愚蠢的吗？).

Answer 1

在我的职业生涯中,我已经编写了六个手工制作的解析器(在大多数情况下是递归下降解析器AKA自上而下解析器),并且看过解析器生成器生成的解析器,我必须承认我对解析器生成器有偏见.

以下是每种方法的优缺点.

分析器发生器

优点:

• 快速获得一个有效的解析器(至少如果你不知道如何手动编码).

缺点:

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

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

优点:

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

缺点:

• 如果您没有这方面的经验,那么手动编写解析器代码需要一些时间.

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

加速递归解析器的一个解决方案是通过自下而上的子解析器替换部分递归解析器,这通常要快得多.这种子解析器的自然候选者是具有几个优先级的几乎统一的语法(即二进制和一元表达式)的表达式.表达式的自下而上解析器通常也很容易处理代码,它通常只是一个循环从词法分析器获取输入标记,一堆值和运算符标记的运算符优先级查找表.

Answer 2

LR(1)和LALR(1)解析器真的非常烦人,原因有两个:

1. 解析器生成器不是很擅长产生有用的错误消息.
2. 某些歧义,比如C风格的if-else块,使得编写语法非常痛苦.

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

此外,对于Vala,解析器和编译器本身作为库提供,因此您可以使用Vala编译器库为Vala编译器构建自定义后端,并免费获得所有解析和类型检查等.