26

序言：虽然解析器（上下文无关文法）识别的语言集严格大于扫描器（常规文法），但大多数解析器生成器都需要扫描器。

（请不要试图解释背后的原因，我很了解）。

我见过解析器，不需要像

不使用扫描仪有一定的优势：

  • 只有一个概念（上下文无关语法）而不是两个
  • 在一个文件中解析多种语言（如 HTML/Javascript）
  • 解析没有保留关键字的语言（如PL/1）

通常，使用“变通方法”，例如根据解析器的请求切换扫描仪。

问题：你知道任何其他无扫描解析器生成器（任何语言）吗？这些在使用中是否实用（或纯粹是学术性的）？除了富田/GLR 还有其他方法吗？

答案：

4

6 回答 6

11

另外两个：

  • Bryan Ford 的 Parsing Expression Grammars (PEG) 不需要扫描仪。高效、懒惰的“packrat 解析器”是可选的。我对 Lua LPEG版本只有很好的经验，它可以编译成高效的字节码机器。很实用。

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

我实际上是无扫描解析器的忠实粉丝。它们极大地简化了配置。委婉地说，典型的扫描仪生成器使用起来并没有多大乐趣。从 Lex 的手册页：

杀死这只恐龙的小行星仍在轨道上。

最后，我对 Elkhound 没有亲身经历，但我听到的二手报告令人印象深刻。我会说毫无疑问，但一些无扫描仪解析器生成器非常实用。

于 2010-02-13T21:11:36.600 回答
9

解析器生成器不需要扫描仪。但是，如果您不使用它，您将非常疯狂。

解析器生成器构建的解析器并不关心你给它们提供什么，只要你称它们为令牌。

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

这很疯狂的原因是解析是比词法分析更复杂的活动。您可以将词法分析器构建为有限状态机，它几乎可以将机器代码转换为“比较并跳转到下一个状态”。对于速度，这真的很难被击败。解析器生成器构建的解析器执行递归下降预测解析（对于大多数 LL 生成器，例如 ANTLR）或通过散列、二进制或线性搜索等进行表查找。因此，解析器在令牌上花费的能量比词法分析器在特点。

如果您将字符作为标记提供给解析器，那么它将在字符上花费比同等词法分析器更多的能量。如果您处理大量输入文本，这最终会很重要，无论您是为数以万计的小输入流还是一些非常大的输入流进行处理。

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

我的公司构建了一个工具， DMS Software Reengineering Toolkit它使用 GLR 解析器（并成功解析了所有你知道的常见语言和许多你不知道的奇怪语言，因为它有一个 GLR 解析器）。我们知道无扫描解析器，但由于速度差异而选择不实现它们；我们有一个经典风格（但非常强大）的类 LEX 子系统，用于定义词法标记。在 DMS 与基于 XT（具有无扫描仪 GLR 解析器的工具）处理相同输入的工具正面交锋的一种情况下，DMS 的速度似乎是 XT 包的 10 倍。公平地说，所做的实验是临时性的，没有重复，但由于它符合我的怀疑，我认为没有理由重复它。YMMV。当然，如果我们想不用扫描仪，那么用字符终端编写语法非常容易，正如我已经指出的那样。

GLR Scannerless 解析器确实有另一个对大多数人来说并不重要的非常好的属性。您可以为无扫描仪解析器采用两个单独的语法，并将它们连接起来，仍然得到一个解析器（通常有很多歧义）。当您将一种语言嵌入到另一种语言中时，这很重要。如果那不是您正在做的事情，那只是学术上的好奇心。

而且，AFAIK，Elkhound 不是没有扫描仪的。（我可能错了）。（编辑：2/10：看起来我错了。不会是我生命中的第一次 :)

于 2010-02-10T15:47:44.213 回答
3

Waxeye：基于解析表达式语法（PEG）的无扫描解析器。

于 2011-09-24T21:54:33.443 回答
3

boost::spirit::qiboost::spirit::lex尽管您可以将其用作前端，但不需要词法分析器。从介绍boost::spirit::lex：

事实上，Spirit.Qi 允许您在不使用词法分析器的情况下编写解析器，直接解析输入字符流，而且大部分情况下，这就是 Spirit 自发明以来一直使用的方式。

boost::spirit（原来的）实际上完全按照您的要求工作，但它已被移至boost::spirit::classic. spirit::qi,spirit::lex是精神的新设计，所以我把经典版本排除在外 :)

于 2010-02-08T20:05:16.783 回答
1

对不起，一个死灵贴。你可以试试这个 - 一个 .NET 的可嵌入 PEG/Packrat 实现：

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

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

于 2010-03-18T09:30:03.237 回答
0

我写了一个“按需扫描”解析器。它是带有扫描仪的解析器和无扫描仪解析器之间的一种折衷。

它允许“无保留关键字”，并使一种语言能够嵌入/嵌套在另一种语言中。

这种嵌套的一个很好的例子是来自 graphviz https://graphviz.gitlab.io/的点语法，其中 XML/HTML 可以嵌入到外部图形语言中。

您可以在https://info.itemis.com/demo/agl/editor看到我的解析器和点语法的演示

可以在此处找到有关解析器的更多详细信息https://medium.com/@dr.david.h.akehurst/a-kotlin-multi-platform-parser-usable-from-a-jvm-or-javascript-59e870832a79

于 2020-04-09T13:45:36.287 回答