选择解析器生成器

Question

选择解析器生成器

c++parsingbisonlexparser-generator

22

好的，我知道这个问题可能听起来很主观，但由于我有几个具体的选择标准，所以我认为它很适合SO。所以，这就是我在这里的原因...

我过去经常从事编译器/解释器构建（显然大多数是作为业余爱好），出于某种原因，我一直使用Lex/Yacc（或Flex/Bison，我对他们现在被称为什么感到非常困惑...哈哈）。

然而，由于我发现自己目前正在玩另一个业余解释器项目，我想尝试一些不同的东西，也许可以避免我不喜欢的Lex/Yacc。

所以，具体要求如下：

比较C++友好而不是C友好
有良好的文档（最好已经实现了一些现有的语法，并提供如何编译/使用它们的说明——听起来相当明显，是吧？）
可以是LALR、LL(*)、递归下降，我并不介意（注意：你可以告诉我你更喜欢哪种类型以及针对什么类型的实现；说实话，我从来没有真正理解它们的优缺点，尽管我知道他们指的是什么）
将Lexer部分和Parser语法组合在一个文件中并不坏；我从来没有真正明白为什么必须拆成两个部分。
最后但并非最不重要的：我总是遇到问题......就至少对于Lex/Yacc而言，解析错误消息更多地是晦涩难懂的（语法错误...呼呼！）而且很少有帮助诊断问题。（好吧，除非你是开发该解释器的人...哈哈）。因此，是否有比Lex/Yacc更好的选择？解析出错报告？

好的，希望这不会太啰嗦。我全副注意！:-)

- Dr.Kameleon

2

你应该在StackExchange的新网站Softwarerecommendations上提问。 - Ira Baxter

1

首先了解一下，请查看http://en.wikipedia.org/wiki/Compiler-compiler。 - Ira Baxter

2

供参考：解析表达式语法是另一种同时指定词法分析器和语法分析器的好方法。如果您无法使用类似ANTLR的东西，这很方便。 PEG允许上下文敏感的词法规则。至少一个值得注意的C ++ PEG实现是Dr. Hirsch的[PEGTL]（https://github.com/colinh/pegtl），这是一个MIT许可的无依赖头文件PEG词法/解析器实现，使用C ++ 11编写。词法分析器和语法分析器使用相同的语言描述，并且所有内容都使用纯C ++表达式编写，无需运行单独的工具。 - Kuba hasn't forgotten Monica

3个回答

10

我只回答最后一个问题，稍作修改：

就Lex/Yacc而言，解析错误消息往往比较晦涩（语法错误... Yuhuu！），很少能帮助诊断问题（除非你是开发解释器的人...lol）。那么，有没有更好的使用 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的一篇相对较新的文章：http://research.swtch.com/yyerror。

- rici

非常感谢您的建议！我一定会认真考虑的！;-) - Dr.Kameleon

3

有趣的问题 - 我不确定我是否有一个很好的答案来回答您实际的问题，但我的“评论”有点长了...

我正在编写一个Pascal编译器，已经基本上手写了1100行C++代码的Lexer、Tokenizer和Parser（包括生成AST以进入LLVM的代码生成器）。如果我可以这样说，它非常“不错”，对于生成良好的错误消息非常友好，这有助于。还有一些部分缺失，还有很多工作要做才能完成我的编译器，但我可以编译一些相当复杂的代码。

我承认，我从未在实际中使用过Lex/Yacc或Flex/Bison。我有时会看一下，但我发现难以使用这些工具，你要么用生成的代码并进行修改（自动生成的代码不是一个好主意），要么就是有糟糕的错误处理，加之难以调试的代码。但是我刚刚花了大约两个小时来查找由于“吞咽”分号太早而导致的错误，反过来又使解析器在令牌流中迷失了...

- Mats Petersson

旁注： 也许你已经从我的最后一条评论中猜到了，我主要对语言（+编译器）构建感兴趣（我的意思是：不是为现有语言创建编译器），因此能够相当“直观地”构建自己的EBNF语法，对提高生产力大有裨益。 - Dr.Kameleon

抱歉，我真的无法提供帮助。我曾经在谷歌上搜索过我的一位同事写的东西，但没有找到特别好的内容。他一直在研究使用ML编写的某些东西，几乎可以满足您的要求，包括内置文档以图形方式显示语言的语法。 - Mats Petersson

嗯，我必须说我喜欢你的观点。不幸的是，我现在谋生的工作远没有编译器那么复杂，也许我正在寻找一些更具挑战性的东西——作为爱好？是的，为什么不呢... :-) - Dr.Kameleon

不确定谁更“幸运”...无论如何，我选择了Pascal，因为它很容易解析。其他语言并不都那么容易... - Mats Petersson

2

但请注意，Pascal被精心设计为易于自上而下解析（和一般处理），这并不奇怪，手写解析器很容易。 - vonbrand

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

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

递归下降、YACC和JavaCC是你常听到的答案。

这些都是你爷爷辈的解析器生成器，存在于它们所接受的语法上的限制。不可避免地，（特别是在Stack Overflow上）会有一些可怜的灵魂问“我该如何解决这个移位/规约问题”（对于像YACC这样的LR解析器生成器），或者“我该如何消除左递归”（对于像JavaCC这样的递归下降或LL解析器生成器）。更糟糕的是，它们无法处理真正具有语法歧义的语法，就像大多数复杂语言中出现的那样。

GLR（和GLL）解析器允许您编写上下文无关语法......并解析它们，毫不费力。这是一个真正的生产力提升。代价是：您可能会得到歧义的解析，但有办法处理。（请参见讨论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，您仍然需要指定展望来解决歧义；我不知道它如何处理无限展望)。据我所知，没有人使用这两种技术构建过实际的C++解析器，因此它们并没有达到它们的声誉。

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