语法分析——总结

语法分析方法可以分成三个大类：

1. 通用的分析方法，可以分析任意文法，主要包括CYK算法和Earley算法，也可以包括GLR算法。 这种分析方法对文法几乎没有限制，甚至可以用于自然语言处理之中。
2. 自顶向下的分析方法，主要用于LL(k)文法。
   1. 递归下降分析：简单易懂，适用于几乎所有文法，可以使用回溯，但对非LL文法可能陷入无限递归。 我们没有详细介绍这种方法，但它实际上是手工编写语法分析器的首选。
   2. 基于表的语法分析器：只能处理LL(1)文法，但不需要递归。
3. 自底向上的分析方法，主要用于LR(k)文法。 这种分析方法能处理的文法比基于表的语法分析器更多，但时间复杂度相近。 其一般非常复杂并用自动工具生成。 这种分析方法通常以“移入-规约语法分析器”的架构出现。
   1. LR(0)自动机：以类似自动机的方式处理LR(0)文法。 我们在此引入了CLOSURE和GOTO函数的概念。
   2. SLR语法分析器：基于LR(0)自动机的语法分析器，只能处理LR(1)文法的一个子集。 使用FOLLOW函数作为规约的向前看符号。
   3. 规范LR(1)语法分析器：处理所有LR(1)文法，但空间效率较低。 使用扩展项的概念以在其中包括向前看符号，这种符号只影响规约。 我们修改了CLOSURE以利用FIRST计算向前看符号。
   4. LALR语法分析器：处理LR(1)文法的一个子集，但分析力大于SLR，效率和SLR相当。 我们把核心（即LR(1)项的前半部分）相同的项集合并成一个项集来构造LALR分析器。 除此之外，也可以使用传播的方式不断地用LR(0)项集族生成LALR项集族。

值得注意的一点是，语言和文法是有区别的。 实际上，对于任何固定的k，LR(k)、LALR(k)和SLR(k)语言的集合是相同的。 而且，对任何大于等于1的k,LR(k)和LR(1)语言的集合也是相同的。 这意味着对任何属于LR(k)的文法，我们都可以构造可以用LALR和SLR分析器识别的文法，使这两个文法描述完全相同的语言。 但是，这样的文法，虽然能被很容易地识别，却并不一定能被很容易地翻译，因为这样的转化后的文法往往难以被人类理解，也很难以写出对应的语义动作。 虽然我们总是可以生成语法分析树，但这并不意味着生成目标语言的程序就非常简单。 因此，我们只关心一小部分常见的文法。