6. General Directional Top-Down Parsing

名词定义

下推自动机（pushdown automaton，PDA）：通过一个栈进行控制的自动机。
Greibach标准形式（Greibach Normal Form，GNF）：所有的产生式的形式如下，A -> a 或者 A -> aBCD...。

LL解析方法（LL parsing method）：从左到右处理输入，最终产生一个最左推导（leftmost derivation）。

左递归文法（left-recursive grammar）：包含左递归非终结符的文法。

递归下降（recursive descent）：将每一条产生式规则看成一个函数，自顶向下的解析（下降）。递归指的是这些函数可能会直接或间接的调用自己。

prefix-free非终结符（prefix-free non-terminal）：非终结符A产生的字符串，互相之间不为前缀。
prefix-free语法（prefix-free grammar）：所有非终结符都是prefix-free的。

通用递归下降解析（Generalized Recursive Descent Parsing (GRDP)）：对每个非终结符，跟踪它的所有匹配。

确定短语文法（Definite Clause Grammar）：Prolog支持的一种文法格式，Prolog会将这种文法转换成Prolog子句（Prolog clause）。

取消解析（cancellation parsing）：为了处理左递归，使用一个集合记录当前已经在处理的非终结符，如果当前已经在处理，则不重复处理。

内容总结

自顶向下（top-down）解析，总是尝试先把产生式右侧，最左边的非终结符替换成终结符，形成了一个最左推导（leftmost derivation）。
下推自动机工作原理：
（1）下推自动机，需要文法具有Greibach标准形式，产生式形如 A -> a 或者 A -> aBCD...。
（2）栈中弹出A，读取输入a，导致栈消耗掉一个元素。
（3）或者，栈中弹出A，读取输入a，导致BCD...压栈。
（4）直到栈为空，输入读完为止。

很多下推自动机是非确定性的，对某些上下文无关文法无法找到确定性的下推自动机。

深度优先搜索方法的缺点是，无法处理左递归文法。
我们可以进行文法转换，以消除左递归，仍可生成相同的语言。

广度优先搜索方法的缺点是，会占用大量的内存。

递归下降解析方法，也无法处理左递归文法。
prefix-free语法，在某个位置识别非终结符A的时候，只有一种办法。

通用递归下降解析适用于所有的非左递归上下文无关文法。

Prolog内置了一套搜索和回溯机制，用于回答问题。
Prolog使用深度优先搜索。

7. General Directional Bottom-Up Parsing

名词定义

Earley parser：一个采用自底向上识别方法的，自顶向下解析器。分为三个部分：Scanner，Completer，Predictor。

FIRST集（FIRST set）：非终结符A的FIRST集是由终结符组成的，指的是A的各种最终产生结果由哪些终结符开头。
FOLLOW集（FOLLOW set）：非终结符A的FIRST集是由终结符组成的，指的是A后面可以跟的终结符集。

解析表（Chart Parsing）：它不是一个算法，而是一个框架，用来开发解析器或者进行实验。

内容总结

自底向上解析，包括两个步骤：shift和reduce。
自底向上解析树的父节点，直到左右子节点都识别出来后，才会被识别。
自底向上解析，可以采用两种搜索方法：深度优先，广度优先，算法复杂度是指数级的。

广度优先的自底向上解析，可以处理左递归，经过特殊处理后，也可以处理空串规则（ε-rules）和循环（loops）。

Earley解析器的空间复杂度是平方级的，时间复杂度是立方级的。
与CYK解析器不同的是，CYK解析只对乔姆斯基标准形式的文法时间复杂度是立方级的，Earley解析器对任意文法都是立方级的。

前瞻（look-ahead）可提前排除错误的预测。

自底向上解析，可以在线性时间复杂度内处理左递归文法，但是处理右递归具有四次方复杂度。

Earley解析器处理很多文法的时间复杂度都是线性的，包括LR(k)文法以及LR正则文法。

参考

Parsing Techniques