分析器的选择

Question

好的,我理解这个问题可能听起来很基于意见,但是由于我有几个特定的​​选择标准,我认为它会很适合SO.所以,我在这里......

我过去曾经使用编译器/解释器构建很多(显然主要是作为一种业余爱好)并且出于某种原因我坚持使用Lex/Yacc(或Flex/Bison,我对他们现在如何称呼它们感到困惑... 大声笑).

然而,由于我发现自己目前正在玩另一个业余爱好者翻译项目,我认为我应该尝试一些不同的东西,以避免我不喜欢Lex/Yacc.

所以,即:

• 更好的C++ - 友好(比C友好)
• 好的文档(最好已经实现了一些现有的语法+关于如何编译/使用它们的说明 - 听起来很明显,对吧？)
• 可能是LALR,LL(*),递归下降,我并不在乎(注意:关于你喜欢哪种类型以及哪种类型的实现会很棒的输入;我从来没有真正理解他们的专业和缺点,说实话,即使我知道他们所指的是什么)
• 将Lexer部分和Parser语法组合在一个文件中并不坏; 从来没有真正理解为什么它必须分成两部分.
• 最后但同样重要的是:我总是遇到......问题.我的意思是 - 至少就Lex/Yacc而言,解析错误信息或多或少是神秘的(Syntax Error...... Yuhuu!),很少有人帮助诊断问题.(好吧,除非你是开发翻译的人......哈哈).那么,有没有比Lex/Yacc更好的错误报告？

好的,我希望这不是太冗长.我全都耳朵!:-)

Answer 1

自1969年以来,我一直在构建解析器生成器和解析器.

递归下降,YACC和JavaCC是您听到的典型答案.

这些是你的爷爷的解析器生成器,并且受到他们将接受的语法的限制.总是(特别是Stack Overflow),一些可怜的灵魂问"如何解决这个转移/减少"问题(对于像YACC这样的LR解析器生成器)或"我如何消除左递归"(对于递归下降或LL解析器生成器,如JavaCC的).更糟糕的是,它们无法处理真正具有语法歧义的语法,就像在大多数复杂语言中一样.

GLR(和GLL)解析器允许您编写无上下文的语法...并解析它们,没有大惊小怪或muss.这是一个真正的生产力提升.有一个代价:你最终会得到模棱两可的解析,但有办法解决这个问题.(参见关于C++解析问题的讨论,YACC和JavaCC都不能自己处理).

Bison(广泛提供)有GLR选项 ; 用它!最近的多语言程序操作工具似乎都使用GLL或GLR.我们的DMS软件再造工具包使用GLR并解析C++(MS和GNU变体中的完整C++ 14!),Java,COBOL以及大量其他复杂语言; GLR是我职业生涯中最好的技术选择之一.Stratego使用GLR.我认为RascalMPL使用GLL.Scott McPeak的Elkhound GLR解析器生成器是基于C++的,并且很可靠地生成C++代码(OP要求基于C++的答案).

如今热门话题是PEG和ANTLR4.这些更好的LL或LR解析器,但仍然在试图塑造语法时给予一个悲伤.(使用PEG,您必须订购产品,假设您可以找到这样的订单,以处理具有优先级的模糊规则.使用ANTLR4,您仍然可以指定前瞻以解决歧义;不知道它如何处理无限前瞻).AFAIK,没有人使用这些技术中的任何一种构建实用的C++解析器,因此他们没有达到他们的声誉.

我认为GLR和GLL是更好,更好的答案.

Answer 2

我只想稍微编辑一下,回答最后一个问题:

至少就Lex/Yacc而言,解析错误消息或多或少是神秘的(语法错误...... Yuhuu!),很少有人帮助诊断问题.(好吧,除非你是开发翻译的人......哈哈).那么,有没有比 使用 Lex/Yacc 更好的方法更好地处理错误报告的方法呢？

好吧,首先使用现代版本的bison,它具有相当完整的在线手册(很可能与可执行文件一起安装,具体取决于你如何安装bison).特别是,从这些声明开始:

%define parse.error verbose
%define parse.lac full

这将至少用"预期"令牌类型列表替换神秘的"语法错误"错误.

然后确保您的令牌类型具有有意义的名称,因为它们将作为错误消息的一部分呈现给用户.如果您习惯使用IDENTIFIER终端,那么您可能没问题,但是"Expected TOK_YY_ID"消息有点令人讨厌.您可以在type声明中声明终端的可读性:

%type TOK_YY_ID "identifier"

那只会带你到目前为止.在许多情况下,了解"预期"的内容足以理解语法错误,但有时更明确一些是有用的.在这种情况下,实际定义error规则很有用.获得这些权利更像是一门艺术,而不是一门科学,但所有错误报告/恢复方法都是如此; 关键是尽可能具体地说明错误的语法是什么样的,而不是特定于必要的.

一种有趣的错误报告方法是使用当前解析器状态和前瞻标记(两者在错误报告时都可见)来查找自定义错误消息(如果存在).我认为这种方法很长一段时间以来一直是编译民间传说的一部分,我相信几十年来我已经看过几篇关于它的文章.这是Russ Cox最近的一篇文章.