17

Is there any existing implementation of the GLL algorithm, either in the form of parser combinators (preferred) or as a parser generator for C or C++?

My requirements are that the output is a shared packed parse forest (SPPF) which I can later disambiguate using semantic and/or contextual rules. There are other parsing algorithms such as GLR which are able to cope with general context-free grammars, however, all GLR parser generators I could find either return the first successful parse tree or fail if any ambiguity remains at the end.

4

1 回答 1

0

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

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

惰性 val expr: Parser[Any] = (
    "(" ~ expr ~ ")"
  | “”
)

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

expr("((()))")

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

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

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

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

于 2015-09-21T10:03:23.243 回答