彩票走势图

在阅读之前，请务必首先查看第1部分、第2部分、第3部分、第4部分和第5部分！

解析算法

从理论上讲，解析是一个已解决的问题，但是这种问题还是会一再地被解决。也就是说，有很多不同的算法，每个算法都有强大的优点和缺点，而且学者们还在不断进步。

在本节中，我们不会教导如何实现每一个解析算法，但是我们将解释它们的特征。目标是您可以选择更多的知道哪些分析工具使用或哪些算法更好地学习和实现您的自定义分析器。

概述

我们先从全局概述所有解析器的功能和策略。

两种策略

有两种解析策略：自顶向下解析（top-down parsing）和自底向上解析（bottom-up parsing）。这两个术语都是根据解析器生成的分析树来定义的。简单的解释：

• 自顶向下的解析器首先尝试识别解析树的根，然后向下移动子树直到找到树的叶子。
• 自下而上的解析器是从树的最低部分（树叶）开始，然后上升直到确定树的根部。

让我们看一个例子，从一个分析树开始。

示例解析树（）

同样的树会由一个自顶向下和一个自底向上的解析器以不同的顺序生成。在下面的图片中，数字表示创建节点的顺序。

自上而下的树的生成顺序（）

自下而上的生成树的顺序（）

传统上，自顶向下的解析器更容易构建，但自下而上的解析器更强大。现在，情况更加平衡，主要是因为自上而下的解析策略的进步。

推导的概念与策略密切相关。派生指出了规则中的非终结符元素出现在右侧的顺序，用于获取左侧的非终结符号。使用BNF术语，它指示如何使用__expression__中出现的元素来获得< symbol >。这两种可能性是最左边的推导和最右边的推导。第一个表示规则从左到右应用，而第二个表示相反。

一个简单的例子：想象一下，你正在试图解析符号结果，在语法中定义了这样的结果。

expr_one = .. // stuff
expr_two = .. // stuff
result   = expr_one 'operator' expr_two

您可以先将符号规则应用于符号expr_one，然后执行expr_two，反之亦然。在最左边的派生的情况下，你选择第一个选项，而为了最右边的派生，你选择第二个。

理解推导是深度优先还是递归应用是很重要的。也就是说，它被应用到开始表达式，然后再被应用到所获得的中间结果。因此，在这个例子中，如果在应用expr_one对应的规则之后，有一个新的非终结符；那个先变了 非终结符expr_two仅在它成为第一个非终结符并且不遵循原始规则中的顺序时才应用。

派生与两种策略相关联，因为对于自下而上的解析，您可以应用最右边的派生，而对于自顶向下的解析，您可以选择最左派生。请注意，这对最终的解析树没有影响；它只是影响中间元素和使用的算法。

共同的元素

用自上而下和自下而上的策略构建的解析器有一些我们应该谈论的内容。

前瞻性和回溯性

术语“前瞻”和“回溯”在解析方面的含义与其在大型计算机科学领域中的含义不同。Lookahead表示在当前的元素之后的元素的数量，这些元素被考虑来决定采取哪个当前的行动。

一个简单的例子：解析器可能会检查下一个标记以决定现在应用哪个规则。当适当的规则匹配时，当前token被消耗，但下一个仍然在队列中。

回溯是一种算法的技术。它包括通过尝试部分解决方案找到复杂问题的解决方案，然后不断检查最有前途的解决方案。如果当前正在测试的那个失败，则解析器回溯（即，它回到最后被成功解析的位置）并且尝试另一个。

它们与LL、LR和LALR分析算法特别相关，因为只需要一个预读标记的语言的解析器更容易构建并且更快地运行。在算法名称之后的括号（即LL（1），LR（k））之间指示由这些算法使用的前瞻tokens。符号（*）表示该算法可以检查无限的超前tokens，尽管这可能会影响算法的性能。

图表解析器

图表解析器是可以自下而上（即CYK）或自上而下（即Earley）的一系列解析器。图表解析器基本上试图通过使用动态编程来避免回溯，这可能是昂贵的。或动态优化是在较小的子问题中解决较大问题的一般方法。

图表解析器使用的常见动态编程算法是（Viterbi algorithm）。该算法的目标是在给定已知事件序列的情况下找到最有可能的隐藏状态。基本上，考虑到我们所知道的tokens，我们试图找出最可能的规则。

名称图表解析器来自这样一个事实，即部分结果存储在名为图表的结构中（通常，图表是表格）。存储部分结果的特定技术称为memoization。其他算法也使用Memoization，与图表解析器无关，如packrat。

自动机

在讨论解析算法之前，我们想谈谈在解析算法中使用自动机。是一个抽象机器族群，其中有著名的图灵机（Turing machine）。

当谈到解析器时，您可能会听到（确定性）下推自动机（PDA）这个术语，当您阅读词法分析器时，您会听到术语（确定性）有限自动机（DFA）。PDA比DFA更强大，更复杂（虽然比图灵机简单）。

由于它们定义了抽象机器，通常它们与实际算法没有直接关系。相反，他们正式描述算法必须能够处理的复杂程度。如果有人说解决问题X需要一个DFA，他意味着你需要一个和DFA一样强大的算法。

但是，由于DFA是状态机，在词法分析器的情况下，区分通常是没有意义的。这是因为状态机实现相对简单（即有现成的库），所以大多数情况下，DFA是通过状态机实现的。这就是为什么我们要简要地谈论DFA以及为什么他们经常用于词法分析器。

用确定性有限自动机（Deterministic Finite Automaton）进行词法分析

DFA是一个（有限的）状态机，这个概念我们假设你很熟悉。基本上，状态机有许多可能的状态和每个状态的转换函数。这些转换功能控制机器如何从一个状态移动到另一个状态以响应事件。当用于练习时，机器每次输入一个输入字符，直到达到接受状态（即它可以建立一个标记）。

他们用于几个原因：

• 事实证明，他们确实认可了一套正规语言；也就是说，它们和普通语言一样强大。
• 有一些数学方法来操作和检查它们的属性（即它们是否可以解析所有字符串或任何字符串）。
• 他们可以使用高效的在线算法（见下文）。

在线算法是一个不需要整个输入工作的算法。在词法分析器的情况下，这意味着只要算法看到其中的字符，就可以识别它。另一种选择是它需要整个输入来识别每个token。

除了这些属性之外，将一组正则表达式转换为DFA相当容易，这使得可以以许多开发人员熟悉的简单方式输入规则。然后，您可以自动将其转换为可以高效处理的状态机。

请继续关注第7部分！

推荐阅读：

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

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

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

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