无扫描分析器生成器

另外两个:

• 布莱恩·福特的解析表达式语法(PEG)不需要扫描器。高效、懒惰的“packrat解析器”是可选的。我对Lua只有很好的经验 LPEG 版本,它编译成一个有效的字节码机器。挺实用的。

• YAKKER 看起来很有趣,尽管它仍然明显处于预发布状态。他们正在使用声称是Earley解析算法的有效变体。

我实际上是无扫描解析器的忠实粉丝;它们极大地简化了配置。而一般的扫描器发生器,委婉地说,使用起来并不有趣。从Lex的主页:

The asteroid to kill this dinosaur is still in orbit.

最后,我对埃尔霍蒙德没有个人经验,但我听到的二手报告令人印象深刻。我想说没有问题,但是 一些 无扫描分析器生成器非常实用。

解析器生成器不 需要 扫描仪。但如果你不使用的话,你就疯了。

由解析器生成器构建的解析器不关心您向它们提供什么,只要您称它们为令牌。

要构建使用不带扫描器的解析器生成器,只需将语法定义为字符级别,并将单个字符作为标记提供给解析器。

这很疯狂的原因是解析比词法分析更复杂。您可以将lexer构建为有限状态机,将其转换为机器代码,就像“比较并跳转到下一个状态”。对于速度来说,这真的很难打败。解析器生成器构造执行递归下降预测解析(对于大多数ll生成器,如antlr)或通过散列、二进制或线性搜索等进行表查找的解析器,因此解析器在令牌上花费的精力比lexer在字符上花费的精力要多得多。

如果您将字符作为令牌提供给解析器,那么它将相应地比等效的lexer在字符上花费更多的精力。如果您处理大量的输入文本,这最终会很重要,无论您是为数不清的小输入流还是为几个真正大的输入流执行此操作。

所谓的无扫描GLR解析器,相对于设计用来使用令牌的GLR解析器而言,存在这个性能问题。

我的公司制造了一个工具, the DMS Software Reengineering Toolkit 它使用了一个GLR解析器(并且成功地解析了所有你知道的普通语言和很多你不知道的奇怪语言,因为它有一个GLR解析器)。我们知道无扫描解析器,但由于速度差异,选择不实现它们;我们有一个经典风格(但功能极其强大)的lex类子系统,用于定义词汇标记。在DMS与基于XT(一种无扫描GLR解析器的工具)的工具处理相同输入的情况下,DMS的速度似乎是XT包的10倍。公平地说,实验是临时的,没有重复,但由于它符合我的怀疑,我没有理由重复。YMMV。 当然,如果我们想实现无扫描,那么,用字符终端编写一个语法很容易,正如我已经指出的那样。

无扫描分析器 做 拥有另一个对大多数人来说都不重要的非常好的财产。对于无扫描的解析器,您可以采用两个独立的语法,并逐字连接它们,仍然可以得到一个解析器(通常有很多模棱两可的地方)。当您构建一种嵌入到另一种语言中的语言时,这非常重要。如果这不是你所做的,这只是学术上的好奇心。

而且,阿法克,Elkhound不是无扫描的。(在这方面我可能是错的)。 (编辑:2/10:看起来我错了。不会是我生命中的第一次。)

boost::spirit::qi 虽然你可以用,但不需要雷克萨斯 boost::spirit::lex 作为前端。从介绍 助推器::Spirit::Lex :

事实上,精神。气允许你写作 不使用lexer的解析器,解析 直接输入字符流, 在大多数情况下,这就是 自从它被用于 发明。

boost::spirit (原来的那个)确实按你想要的方式工作,但它已经被移到 boost::spirit::classic . spirit::qi , spirit::lex 是新设计的精神,所以我把古典版忘了:)

Waxeye :无扫描分析器基于 parsing expression grammars (钉)。

不好意思做了尸检。您可以尝试一下这一点,.NET的可嵌入peg/packrat实现:

http://www.meta-alternative.net/pfdoc.pdf

http://www.meta-alternative.net/mbase.html