彩票走势图

我们已经到了最后！如果您是第一次遇到这个系列，请查看上面的其他帖子。

解析算法

我们最后的重点是自下而上的算法。

自下而上算法

自下而上策略的主要成功是许多不同LR解析器的家族。虽然LR解析器比传统的LL（1）语法更强大，但它们相对不受欢迎的原因是，历史上它们难以建立。因此，除了对CYK解析器的简要描述之外，我们主要关注它们。

这意味着我们避免谈论更通用的shift-reduce分析器类，它也包含LR分析器。

Shift-Reduce算法分两步工作：

1. Shift：从输入中读取一个token，这将成为一个新的（暂时孤立的）节点。
2. Reduce：一旦适当的规则匹配，加入结果树与先行的现有子树。

基本上，Shift步骤读取输入直到完成，而Reduce步骤连接子树，直到构建最终的分析树。

CYK解析器

Cocke-Younger-Kasami（CYK）算法由三位作者独立制定。它的显着性是由于最糟糕的表现（O（n3））造成的，尽管它在大多数常见的情况下受到相对较差的表现的阻碍。

然而，该算法的真正缺点是它需要以表示。

这是因为该算法依赖于这种特殊形式的属性，能够将输入分成两半来尝试匹配所有的可能性。从理论上讲，任何上下文无关的语法都可以转化为相应的CNF，但这种手段很少实用。想象一下，你不能使用左递归规则，然后被要求学习一种特殊的形式这一事实令人烦恼。

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

出于所有实际的目的，如果您需要解析所有上下文无关的语法，并且性能很差，那么您需要使用Earley解析器。

LR分析器

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

传统上，他们已经被比较，并与LL解析器竞争。有一个类似的分析需要解析一个语言的前瞻tokens的数量。一个LR（k）解析器可以解析需要解析前向k个tokens的语法。然而，LR语法的限制性较小，因此比相应的LL语法更强大。例如，不需要排除左递归规则。

从技术上讲，LR语法是LL语法的超集。这样做的一个结果是你只需要LR（1）语法，所以通常，（k）被省略。

它们也是基于表格的，就像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和bisonwork。

与LR语法相反，LALR和SLR语法不是LL语法的超集。他们不容易比较；一些语法可以被一个类而不是另一个所覆盖，反之亦然。

广义LR解析器

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

在其表上找不到GLR解析器的威力，这相当于传统LR解析器的表。相反，它可以移动到不同的状态。在实践中，如果存在歧义，则会派生一个新的解析器（或解析器）来处理特定的情况。这些解析器可能会在稍后阶段失败并被丢弃。

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

总结

通过这个大系列，我们希望解决大部分关于解析术语和算法的疑问，比如术语的含义以及为什么选择某种算法。我们不仅解释了它们，而且还解释了解析编程语言的一些常见问题。

由于时间和精力的原因，我们无法提供所有解析算法的详细解释。所以，我们还提供了一些链接，让您更深入地了解这些算法，背后的理论以及它们是如何工作的。

如果您只是对解析感兴趣，您可能需要阅读“解析技术”（）这本书。它明显比我们的理解深入得多，并且它也涵盖了一些较少使用的解析算法。

推荐阅读：

展望2018年：基于AI人工智能的移动应用程序开发将如何发展

开发一个聊天机器人（Chatbot）应用程序需要花费多少钱？

PS: 更多、相关视频、培训、公开课，请关注！

关于人工智能技术的最新资讯和相关开发工具推荐，请<>！