NLP|自然语言处理-语法解析指南：算法和技术（第8部分）

在这篇文章中，我们继续深入分析自顶向下的分析算法，包括Packrat（PEG），递归下降分析器，Pratt分析器和分析器组合器。

一定要先看看第7部分！如果您第一次遇到这个系列，您可以在本文顶部找到其余的帖子。

解析算法

自顶向下算法

Packrat（PEG）

Packrat经常与正式语法PEG相关，因为它们是由同一个人Bryan Ford发明的。Packrat在他的论文中首先被描述了：Packrat Parsing：具有回溯的实用线性时间算法。标题说几乎所有我们关心的事情：它有一个线性的执行时间，不使用回溯。

其效率的另一个原因是记忆：在解析过程中存储部分结果。缺点是，直到最近才使用该技术的原因是存储所有中间结果所需的内存数量。如果所需的内存超过了可用的内存，算法将失去执行的线性时间。

Packrat也不支持左递归规则，因为PEG需要总是选择第一个选项。实际上，一些变体可以支持直接的左递归规则，但是以牺牲线性复杂性为代价。

如果需要的话，Packrat解析器可以执行无限量的lookahead。这会影响执行时间，在最坏的情况下可能是指数级的。

递归下降解析器（Recursive Descent Parser）

递归下降解析器是一个解析器，它与一组（相互）递归过程一起工作，对于语法的每个规则通常是一个过程。因此，解析器的结构反映了语法的结构。

termpredictive解析器以几种不同的方式使用：有些人把它作为自顶向下解析器的同义词，有些人认为它是从不回溯的递归下降解析器。

第二个含义的反义词是一个递归下降解析器，它会回溯。也就是说，通过依次尝试每一个规则，然后每次失败就返回，找到与输入相匹配的规则。

通常，递归下降解析器在解析左递归规则时会遇到问题，因为算法会一次又一次地调用同一个函数。这个问题的一个可能的解决方案是使用尾递归。使用此方法的解析器称为尾递归解析器。

尾递归本身只是在函数结束时发生的递归。然而，尾部递归与语法规则的转换一起使用。转换语法规则和在过程结束时进行递归的组合允许处理左递归规则。

Pratt解析器

Pratt解析器是一个广泛未使用的，但非常值得赞赏的（由少数人知道的），由Vaughan Pratt在一篇名为“Top Down Operator Precedence”的论文中定义的解析算法。本文首先从BNF语法的论战开始，笔者认为错误的是解析研究的唯一问题。这是缺乏成功的原因之一。实际上，该算法不依赖于语法，而是直接对tokens进行操作，这使解析专家变得不同寻常。

第二个原因是，如果你有一个有意义的前缀来帮助区分不同的规则，那么传统的自顶向下的解析器就能很好地工作。例如，如果您得到token FOR，您正在查看for语句。由于这基本上适用于所有的编程语言及其语句，所以很容易理解为什么Pratt解析器没有改变解析世界。

Pratt算法的亮点在于表达式。事实上，优先的概念使得不可能仅仅通过查看tokens的顺序来理解输入的结构。

基本上，该算法要求您为每个运算符token分配一个优先值，并根据token的左侧和右侧确定要执行的操作。然后，它使用这些值和函数在遍历输入的同时将操作绑定在一起。

虽然Pratt算法没有公开地成功，但它用于解析表达式。JSLint也为Douglas Crockford（JSON成名）所采用。

解析器组合器

解析器组合器是一个高阶函数，接受解析器函数作为输入，并返回一个新的解析器函数作为输出。解析器函数通常意味着接受一个字符串并输出解析树的函数。

解析器组合器是模块化的并且易于构建，但是它们也比较慢（在最坏的情况下它们具有O（n4）复杂性）并且不太高端。它们通常被用于更简单的解析任务或原型设计。从某种意义上说，解析器组合器的用户部分手动构建解析器，但依赖于创建解析器组合器的人所做的艰苦工作。

通常，它们不支持左递归规则，但是有更高级的实现可以做到这一点。例如，参见用于模糊左递归语法的解析器组合器，其也设法描述具有执行多项式时间的算法。

许多当代实现被称为monadic解析器组合器，因为它们依赖于称为monad的函数式编程的结构。Monad是一个相当复杂的概念，我们不能在这里解释。但是，monad基本上可以将依赖于数据类型的功能和操作组合起来。关键的特点是数据类型指定如何组合不同的值。

最基本的例子是Maybe monad。这是一个正常类型的包装器，比如整数，在值有效的时候（567）返回值本身，当它不是时（即未定义或被零除），则返回一个特殊的值Nothing。因此，你可以避免使用空值，并毫不客气地崩溃程序。相反，Nothing值是正常管理的，就像管理任何其他值一样。

请继续关注第9部分！

本文原作者：Gabriele Tomassetti翻译：Elyn

推荐阅读：

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

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

PS: 更多人工智能、大数据相关视频、培训、公开课，请关注【学院】！

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

来源：慧都