用于C或C++的GLL分析器组合器或生成器

Question

是否有任何现有的GLL算法实现,无论是以解析器组合器(首选)的形式,还是作为C或C++的解析器生成器？

我的要求是输出是一个共享打包解析林(SPPF),我以后可以使用语义和/或上下文规则消除歧义.还有其他解析算法,如GLR,它们能够处理一般的无上下文语法,但是,我可以找到的所有GLR解析器生成器要么返回第一个成功的解析树,要么在最后仍有任何歧义时失败.

Answer 1

如果您尝试GLL 组合器会怎么样？尽管它使用 Scala，但您可以通过JNI为其编写“薄”包装器。

GLL Combinators是一个旨在 以功能方式实现GLL 解析算法（Scott 和 Johnstone，LDTA 2009）的框架。更具体地说，该框架利用原子解析器组合器来组成语法，然后使用 GLL 算法对其进行评估。该框架为此任务提供了一种语法，该语法与 Scala 中内置的解析器组合器框架的语法几乎相同。例如，我们可以使用 GLL 组合器呈现经典的“括号语法”：

惰性 val expr: 解析器[Any] = (
    “(”~表达式~”)”
  | ””
）

正如类型注释所暗示的，expr将引用类型的实例 Parser[Any]。也就是说，一个原子解析器消耗一些输入并返回类型的值Any。我们可以String通过以下方式针对输入调用此解析器：

表达式(“((()))”)

这将返回一个类型的值Stream[Result[Any]]。ADTResult[A]定义为以下之一（对于某些类型A）：

• Success[A]-- 表示解析成功并包含结果值。
• Failure-- 表示解析失败并包含相关错误消息以及解析流的其余部分（未消耗的字符）。

如果任何结果成功（即 的实例Success[A]），则不会返回任何失败。因此，Stream返回的结果将是完全同质的，包含或 Success，Failure但不能同时包含两者。返回AStream而不是单个值，以允许语法中的歧义（见下文）。

值得一提的是，GLL 是递归下降解析的一种形式。它具有传统递归下降的所有优点，包括直观的控制流、语义动作的任意定位和卓越的错误消息。事实上，GLL 是递归下降的，这使得它可以使用原子组合器来实现。其他与 GLL 具有相同功能的算法（例如 GLR、Earley Parsing 等）由于其控制流程非常不直观，因此从根本上与组合器模型不兼容。在 GLL 解析中，控制流遵循语法的控制流，就像在传统解析器组合器或任何其他形式的递归下降中一样。