使用备选方案解析CFG

Question

我有一种相当简单的语言，表示为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足够小，不应该有什么问题，但我需要将其扩展到更大的语法(具有数千个终端)。

Answer 1

可以实现Earley algorithm (及其变体，比如GLR)来创建一个以立方时间工作的解析器。由于可能存在指数级数量的可能解析，因此复杂性仅在于构建“解析森林”，即包含所有可能解析的DAG。实际上，枚举解析所需的时间与可能性的数量成正比。

请注意，当我们在这里讨论时间复杂性时，我们讨论的是输入字符串的长度，而不是语法的大小。当然，语法有影响时的大小--通常是线性的，但这取决于测量大小的方式--但假设已经为特定的语法构建了一个解析器(这可能需要根据语法大小进行预处理)。

上面链接的维基百科文章有一个各种语言的实现列表，其中一些用于生产，另一些只是为了演示算法。请注意，bison生成的GLR解析器不是立方的；在病理情况下，它可以是指数级的。此外，它不会构建解析树(或森林)；这是留给用户的，并且不共享存储的朴素算法可能需要指数级的空间和时间。(尽管如此，它对于现实世界的语法还是非常有用的。)

Answer 2

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

两个这样的算法是Earley (正如@rici指出的那样)和CYK。它们被设计为根据您的需要返回所有可能的派生，并可用于创建SPPF (共享压缩解析森林)，这对于高度模棱两可的语法来说是一个非常有效的结构(无论您的语法是否符合这种描述，当然我不能说)。

如果你想尝试一下，你可以试试我的python解析库，它实现了Earley和CYK，可以为你的输入提供一个所有可能的派生的列表(但是，Lark支持还在开发中)。