我有一个相当简单的语言，表示为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 足够小，这无关紧要，但我需要将其扩展到更大的语法(有数千个终端(。
Earley算法(及其变体，如GLR(可以用来创建一个在立方时间内工作的解析器。由于可能存在指数级数量的可能分析，因此这种复杂性只是构建"分析林"，即包含所有可能分析的 DAG。实际上，枚举解析需要与可能性数量成正比的时间。
请注意，当我们在这里谈论时间复杂度时，我们谈论的是输入字符串的长度，而不是语法的大小。当然，语法有影响的大小 - 通常是线性的，但这取决于你如何测量大小 - 但假设已经为特定语法构建了一个解析器(这可能需要根据语法大小进行预处理(。
上面链接的维基百科文章列出了各种语言的实现，其中一些用于生产，而另一些仅用于演示算法。请注意，野牛产生的 GLR 解析器不是立方体的;在病理情况下，它可以是指数级的。此外，它不会构建解析树(或森林(;这留给用户，不共享存储的朴素算法可能需要指数级的空间和时间。(尽管如此，它对于现实世界的语法非常有用。
有几类上下文无关的语法。有确定性语法，可以使用shift-reduce解析器进行解析。存在非确定性语法，其解决方案通常是动态展望或回溯。还有一些模棱两可的语法，就像你描述的那种，最好通过专门设计有歧义的算法来解决。
两个这样的算法，是Earley(如@rici指出的(和CYK。它们旨在根据需要返回所有可能的派生，并可用于创建SPPF(共享打包解析林(，这是高度歧义语法的非常有效的结构(无论您是否符合此描述，我当然不能说(。
如果你想尝试一下，你可以试试我的python Lark解析库，它同时实现了Earley和CYK，并且可以为你输入提供所有可能的派生列表(但是，SPPF支持仍在进行中(。