0

我有一个相当简单的语言表示为 CFG。

S → A z
A → A y A
  | A x A
  | A w
  | v

由于存在左递归，递归下降解析器不会削减它。但是，我还需要找到所有可能的解释：给定v x v y v z，我需要我的解析器同时找到(v x (v y v)) z和((v x v) y v) z。

我有什么选择？添加回溯以查找所有可能性的 Shift-reduce 似乎很好，但我听说向 shift-reduce 解析器添加回溯可以使其时间复杂度呈指数级增长。这个 CFG 足够小，应该没关系，但我需要将它扩展到更大的语法（有数千个终端）。

4

2 回答 2

2

可以实现Earley 算法（及其变体，例如 GLR）来创建一个在立方时间内工作的解析器。由于可能的解析可能呈指数级，因此复杂性只是构建一个“解析森林”，它是一个包含所有可能解析的 DAG。实际上，枚举解析所花费的时间与可能性的数量成正比。

请注意，当我们在这里谈论时间复杂度时，我们指的是输入字符串的长度，而不是语法的大小。当然，如果语法有影响，则大小 - 通常是线性的，但这取决于您如何测量大小 - 但假设是已经为特定语法构建了解析器（这可能需要依赖于语法的预处理尺寸。）

上面链接的 Wikipedia 文章列出了各种语言的实现，其中一些用于生产，另一些仅用于演示算法。注意，bison 产生的 GLR 解析器不是立方的；在病理情况下，它可能是指数级的。此外，它不构建解析树（或森林）；这留给用户，不共享存储的简单算法可能需要指数空间和时间。（尽管如此，它对于现实世界的语法非常有用。）

于 2018-05-24T01:55:05.290 回答
1

有几类上下文无关文法。有确定性语法，可以用 shift-reduce 解析器来解析。存在非确定性语法，其解决方案通常是动态前瞻或回溯。还有一些模棱两可的语法，就像你描述的那样，最好通过特别设计考虑歧义的算法来解决。

两种这样的算法是 Earley（正如@rici 指出的那样）和 CYK。它们旨在根据您的需要返回所有可能的派生，并可用于创建 SPPF（共享打包解析森林），这是一种非常有效的结构，适用于高度模糊的语法（无论您的语法是否符合此描述，我当然不能说）。

如果你想尝试一下，你可以试试我的 python Lark解析库，它同时实现了 Earley 和 CYK，并且可以为你的输入提供所有可能的派生列表（但是，SPPF 支持仍在工作中-进步）。

于 2018-05-24T07:45:38.630 回答