1.3 内容概要

由于解析最关键的就是句子和语法,而语法本身又非常的复杂,所以第2章我们将对语法进行详细的讲解。第3章探讨了解析背后的原理,并给出了解析方法的分类。总之,解析技术可以分为自顶向下(top-down)或自底向上(bottom-up)两种,或者是定向(directional)和非定向(non-directional)两种;定向法又可以细分为确定性(deterministic)和非确定性(non-deterministic)的。这就决定了和紧接着后面几章的内容的主体。

第4章我们讲解非定向法,包括Unger和CYK。第5章介绍有限状态自动机(finite-state automata),为后面需要的章节做一个过渡。第6到10章介绍定向法,如下。第6章涵盖了非确定性的自顶向下解析器(向下递归,Definite Clause Grammars),第7章涵盖了非确定性的自底向上解析器(Earley)。第8章和第9章介绍确定性方法(第8章介绍自顶向下法:各种形式的LL。第9章介绍自底向上法:LR)。第10章涵盖非规范(non-canonical)的解析器,以一种不太规范的自顶向下或自底向上的方法来确定解析树的节点的解析器(例如left-corner)。第11章则介绍了类似上一章中的算法的非确定性版本(比如GLR解析器)。

接下来的四章内容,不太符合上述的框架。第12章介绍了最新的用于解析某一语言中完整句子的子字符串技术,包括确定性和非确定性的。第13章介绍了一种正在发展中的技术,这种技术将解析视为贯穿有限状态机的上下文无关语法。第14章介绍了几个并行解析算法,而第15章则解释了几种关于非Chomsky文法系统的建议以及他们的解析器。而这些本身就完成了解析方法。

第16章介绍了一些错误处理方法,第17章介绍了在写作和使用中比较实用的解析器。