图灵汇官网

解析算法

我们此次讨论的重点是自下而上的算法。

自下而上算法

自下而上的策略主要体现在许多不同LR解析器的家族中。尽管LR解析器比传统的LL（1）语法更强大，但它们并不如预期的那样受欢迎，因为历史上建立它们较为困难。因此，我们主要关注CYK解析器的简要介绍，而不再深入探讨更通用的shift-reduce分析器类，它也包括LR解析器。

Shift-Reduce算法分为两个步骤： 1. Shift：从输入中读取一个token，这将成为一个新的（暂时孤立的）节点。 2. Reduce：一旦适当的规则匹配，将结果树与先前的子树合并。

Shift步骤读取输入直至结束，而Reduce步骤则负责连接子树，直到构建出最终的分析树。

CYK解析器

Cocke-Younger-Kasami（CYK）算法由三位作者独立提出。其显著性在于最糟糕情况下的表现（O（n3）），尽管在大多数常见情况下，其性能相对较差。

然而，该算法的主要缺陷在于它需要以乔姆斯基（Chomsky）范式语法表示。这是因为算法依赖于这种特殊形式的特性，能够将输入分成两半来尝试匹配所有的可能性。理论上，任何上下文无关的语法都可以转化为相应的CNF，但在实践中却很少这样做。想象一下，你不能使用左递归规则，然后被要求学习一种特殊的形式，这确实令人沮丧。

CYK算法主要用于特定问题，例如成员问题：确定一个字符串是否与某个语法兼容。它也可用于自然语言处理，以找到多种选项中最可能的解析。

如果需要解析所有上下文无关的语法，并且对性能要求不高，那么Earley解析器可能是更好的选择。

LR分析器

LR（从左到右读取输入；最右边的派生）分析器是自下而上的分析器，可以在线性时间内处理确定性的上下文无关语言，且无需回溯。LR解析器的发明者是著名的Donald Knuth。

传统上，LR解析器与LL解析器进行了比较和竞争。LR解析器需要解析前向k个tokens的语法，而LR语法的限制性较小，因此比相应的LL语法更强大。例如，LR语法不需要排除左递归规则。

从技术上讲，LR语法是LL语法的超集。因此，通常只需要LR（1）语法，因此（k）常被省略。

LR语法分析器基于表格，就像LL解析器一样，但它们需要两个复杂的表格。简而言之： 1. 一个表告诉解析器根据当前的token、状态以及可能跟随当前token（token集）做什么。 2. 另一个表告诉解析器接下来的状态。

LR语法分析器功能强大，性能良好，但由于需要手工编写复杂的表格，对于普通计算机语言来说可能变得非常庞大。因此，通常通过语法生成器来使用它们。如果您需要手动构建解析器，可能会更倾向于自顶向下的解析器。

简单LR和前瞻LR

解析器生成器解决了创建复杂表格的问题，但无法解决生成和浏览这些大表格的成本问题。Knuth描述的规范LR（1）解析器提供了更简单的选择。这些替代方案包括简单LR解析器（SLR）和前瞻LR解析器（LALR）。按照能力的顺序，我们有： 1. LR(1) 2. LALR(1) 3. SLR(1) 4. LR(0)

Frank DeRemer发明的两个解析器的名字有些误导：一个并非特别简单，另一个也不是唯一使用前瞻的解析器。总的来说，它们使用的表格不同，这又对语法分析提出了不同的限制。换句话说，它们使用不同的算法从语法中派生语法分析表。

SLR解析器在实际应用中有相当的限制，并不常用。LALR解析器则适用于大多数实际语法，并被广泛使用。事实上，使用LALR解析器表的工具yacc和bison非常流行。

与LR语法相反，LALR和SLR语法并不是LL语法的超集。它们之间难以比较；某些语法可以被一个类覆盖，而不是另一个。

广义LR解析器

广义LR解析器（GLR）是LR解析器的更强大变种。它们在1974年由Bernard Land描述，1984年由Tomita首次实现。GLR解析器存在的原因是为了解析非确定性和模糊的语法。

GLR解析器在表上的表现并不优于传统LR解析器，而是能够在不同状态下移动。在实践中，如果存在歧义，GLR解析器会派生一个新的解析器（或解析器）来处理特定的情况。这些解析器可能会在稍后阶段失败并被丢弃。

GLR解析器在最坏情况下的复杂度与Earley（O（n3））相同，尽管在确定性语法的最好情况下，性能可能会更好。一个GLR解析器的构建比Earley解析器更为复杂。

总结

通过本系列，我们希望能够解答大部分关于解析术语和算法的疑问，如术语的含义及为何选择某种算法。我们不仅解释了它们，还探讨了解析编程语言的一些常见问题。

由于时间和精力的限制，我们无法提供所有解析算法的详细解释。因此，我们提供了一些链接，以便您能进一步深入了解这些算法及其背后的理论和工作原理。

如果您对解析感兴趣，建议阅读《解析技术》（Parsing Techniques）这本书。它比我们的理解更为深入，并涵盖了更多较少使用的解析算法。

原文作者：Gabriele Tomassetti

翻译：Elyn