[Theory] Parsing Techniques 读书笔记
（接上文）
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正则文法。
8. Deterministic Top-Down Parsing
名词定义
确定性解析器（deterministic parser）：不需要搜索的解析器，每一步都有唯一的选择，它只产生一棵解析树。
简单LL(1)文法（simple LL(1) grammar，SLL(1)）：每条产生式右边，都以不同的终结符开头。
解析表（parser table）：表示每个非终结符，对于特定字符，选择哪个推导。
LL(1)文法（LL(1) grammar）：不包含空串规则（ε-rules）的文法，任何两个非终结符的FIRST集不相交，即，在前瞻一个字符的情况下，每个产生式都有确定的推导。
内容总结
确定性解析器，只适用于无歧义文法（non-ambiguous grammars）。
自定向下确定性解析器，采用了前瞻方法，往前看一个或多个符号，从而决定怎样推导。
只考虑那些产生式右边开头的终结符，与当前处理的下一个字符相同的产生式规则。
很多文法都是LL(1)的，或者可以转换成LL(1)。
（接后文）
