algorithm - 使用备选方案解析 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 解析器不是立方体的；在病理情况下，它可以是指数级的。此外，它不构建解析树(或森林)；这是留给用户的，不共享存储的朴素算法可能需要指数级的空间和时间。 (尽管如此，它对于现实世界的语法非常有用。)