获取理解和实现特定分析器算法（特别是自顶向下算法）所需的主要信息摘要。
在阅读之前，一定要查看第1-6部分！
让我们继续我们的解析算法的概述。
解析算法
概述
解析算法表
我们在下面提供一个表格，提供理解和实现特定分析器算法所需的主要信息摘要。您可以通过阅读我们提供用于Java、C＃、Python和JavaScript的解析工具和库的文章来找到更多的实现（需要这些方面文章资源的同学可以联系Elyn获取哦）。
该表格列出：
- 一个形式化的描述，来解释算法背后的理论
- 更实际的解释
- 一个或两个实现，通常一个更容易，另一个是专业解析器。有时候，没有简单的版本或专业版本。
| 算法 | 形式描述 | 说明 | 示例实现 |
|---|---|---|---|
| CYK | An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages (PDF) | CKY and Earley Algorithms (PDF) | CYK Algorithm in Golang/Chart-parsers |
| Earley | An Efficient Context-Free Parsing Algorithm (PDF) | Earley Parsing Explained | Nearley |
| LL | LL(*): The Foundation of the ANTLR Parser Generator (PDF) | LL Parser on Wikipedia/LL-parser.js | ll(1) parser/ANTLR |
| LR | On the Translation of Languages from Left to Right (PDF) | Compiler Course | Jison/Bison |
| Packrat (PEG) | Packrat Parsing: A Practical Linear-Time Algorithm with Backtracking (PDF) | Packrat Parsing: Simple, Powerful, Lazy, Linear TimePackrat Parsing in Scala (PDF) | Companion Code of the Thesis/Canopy |
| Parser Combinator | Constructing Natural Language Interpreters in a Lazy Functional Language (PDF) | Parser Combinators Explained | Understanding Parser Combinators/Sprache |
| Pratt | Top Down Operator Precedence | Simple Top-Down Parsing in Python | A Pratt Parser in Python/JSLint |
要理解解析算法的工作原理，还可以查看语法分析工具包。这是一个解析器生成器教程，它描述了生成的解析器完成其目标的步骤。它实现了一个LL和一个LR算法。
第二个表格显示了不同解析算法的主要特征以及它们通常使用的内容的总结。
自顶向下算法
自上而下的策略是两种策略中最普遍的策略，并且有几种成功的算法在应用它。
LL解析器
LL（从左到右读取输入，最左边的派生）解析器是基于表格的解析器，没有回溯，但具有前瞻性。基于表格意味着他们依靠分析表来决定应用哪个规则。解析表分别用作行和列的非终结符和终端。
要找到适用的正确规则：
- 首先，解析器查看当前token和适量的先行tokens。
- 然后，它试图应用不同的规则，直到找到正确的匹配。
LL解析器的概念并不是指特定的算法，而更多的是指一类解析器。它们是根据语法来定义的。也就是说，LL解析器是一个可以解析LL语法的解析器。反过来，LL语法是根据解析它们所需的先行标记的数量来定义的。这个数字在LL旁边的括 中表示，所以形式为LL（k）。
LL（k）解析器使用k个令牌的lookahead，因此它最多可以解析需要解析k个令牌的lookahead的语法。实际上，LL（k）语法的概念比相应的语法分析器更广泛地使用——这意味着当比较不同的算法时，LL（k）语法被用作meter。例如，你会看到PEG解析器可以处理LL（*）语法。
LL语法的价值
LL语法的这种使用是由于LL语法分析器被广泛使用并且有点限制的缘故。实际上，LL语法不支持左递归规则。你可以用等价的非递归形式来转换任何左递归语法，但是这个限制的重要性有两个：生产力和能力。
生产力的损失取决于你必须以特殊的方式写出语法的需求，这需要花费时间。能力是有限的，因为当用左递归规则编写时，可能需要一个前瞻标记的语法在以非递归方式写入时可能需要两个或三个向前的标记。所以，这个限制不仅仅是烦人的，它限制了算法的能力，即它可以用于的语法。
生产力的损失可以通过一种算法来减轻，该算法自动转换非递归语法中的左递归语法。ANTLR是一个可以做到这一点的工具，但是当然，如果你正在构建你自己的解析器，你必须自己去做。
有两种特殊的LL（k）语法：LL（1）和LL（*）。过去，第一种是唯一被认为是实用的，因为为他们构建高效的解析器是很容易的。直到许多计算机语言被有目的地设计为由LL（1）语法描述的时候。LL（*），也称为LL-regular，解析器可以使用无限量的超前tokens来处理语言。
在StackOverflow上，您可以阅读LL解析器和递归下降解析器之间的简单比较，或LL解析器和LR解析器之间的比较。
Earley解析器
Earley解析器是一个以其发明者Jay Earley命名的图表解析器。该算法通常与CYK（另一个图表解析器）进行比较，该算法更简单，但通常在性能和内存方面更差。Earley算法的突出特点是，除了存储部分结果之外，还实现了一个预测步骤，以决定哪个规则将要尝试匹配下一个。
Earley解析器从根本上按照分段划分规则来工作，如下例所示。
// an example grammarHELLO : "hello"NAME : [a-zA-Z]+greeting : HELLO NAME// Earley parser would break up greeting like this// . HELLO NAME// HELLO . NAME// HELLO NAME .
然后，在可以连接点（.）的这个段上工作，试图达到完成状态; 也就是说。末尾的内容在最后有一个点。
Earley解析器的吸引力在于能够解析所有上下文无关的语言，而其他着名的算法（即LL、LR）只能解析其中的一个子集。例如，左递归语法没有问题。更一般地说，Earley解析器也可以处理非确定性和模糊的语法。
在最糟糕的情况下，它可能会导致性能下降（O（n3））。但是，对于正常语法，它具有线性时间表现。问题在于用更传统的算法解析的语言集合是我们通常感兴趣的。
它也有一个缺点的副作用：通过强迫开发人员以某种方式编写语法，解析可以更有效率，也就是说，构建一个LL（1）语法对于开发人员来说可能比较困难，但是解析器可以非常有效地应用它。Earley，你做的工作少，所以解析器做的更多。
简而言之，Earley允许您使用更容易编写的语法，但在性能方面可能不是最理想的。
Earley使用案例
所以，Earley解析器很容易使用，但在平均情况下，性能方面的优势可能是不存在的。这使得该算法对于教育环境或生产力比速度更重要的地方是很好的。
例如，第一种情况很有用，因为大多数情况下，用户编写的语法工作得很好。问题是解析器会抛出模糊和看似随机的错误。当然，这些错误实际上并不是随机的，但是这是由于用户不知道或不明白的算法的局限性。所以，你迫使用户理解你的解析器的内部工作来使用它，这是不必要的。
请继续关注第8部分！
推荐阅读：
展望2018年：基于AI人工智能的移动应用程序开发将如何发展
开发一个聊天机器人（Chatbot）应用程序需要花费多少钱/h5>
PS: 更多人工智能、大数据相关视频、培训、公开课，请关注【学院】！
关于人工智能技术的最新资讯和相关开发工具推荐，请<咨询在线客服>！
标签：算法人工智能解析器语法解析NLP自然语言处理AI
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！