自顶向下分析（top-down parsing）

概念

找到当前输入流最左推导的过程，对于任意输入流，根据当前的输入符号确定一项生产规则，使用生产规则右侧的符号代替相应的非终结符号向下推导。

举例

LL 文法使用自顶而下的分析方法，常见文法如下：

(1) S → S1
(2) S1 → aS1
(3) S1 → bS1
(4) S1 → ε

分析输入流 abb ，每次分析器会通过新加入的字符判断应该使用什么样的方式展开当前输入流。

(1) S （开始符号）
(2) S1 （规则一）
(3) aS1 （规则二）
(4) abS1 （规则三）
(5) abbS1（规则三）
(6) abb （规则四）

这种分析方法一定是从开始符号分析，通过下一个即将入栈的符号判断应该使用何种方式对当前栈上右侧的非终结符进行展开，直到整个字符串中不在存在任何非终结符，整个解析过程结束。

自底向上（down-top prasing）

概念

分析器从输入流开始，每次都尝试重写最右侧的多个符号，即分析器会从最简单的符号进行推导，在解析的最后合并成开始符号。

常见文法

LR(0) , SLR , LR(1) , LALR(1)

举例

LR(0) 文法：

(1) S → S1
(2) S1 → S1b
(3) S1 → a

使用上述等效文法处理相同的输入流 abb 会以完全不同的过程对输入流进行解析。

(1) a （入栈）
(2) S1 （规则三）
(3) S1b （入栈）
(4) S1 （规则二）
(5) S1b （入栈）
(6) S1 （规则二）
(7) S （规则一）

可见这种方式刚好是规则的逆用，自底向上的过程中会维护一个栈用于存储未被归约的符号，整个过程存在两种操作，一个是入栈（shift），也就是将下一个符号入栈，另一种叫归约（reduce），也就是对最右侧的字符串按照生产规则进行合并。

上述两种分析方式完全不同，这两种方式也代表了计算机科学中的两种思想——从抽象到具体，从具体到抽象。

lookahead

概念

当不同生产规则发生冲突时，当前分析器需要预读一些 Token 判断当前应该使用什么样的生产规则对输入流进行展开或归约，例如在 LALR(1) 中，需要预读一个 Token 保证出现冲突的生产规模能够被正常处理。

Go

分析器使用的是 LALR(1) 文法来解析词法分析过程中输出的 Token 序列，最右推导加向前查看构成了 Go 语言分析器的基本原理，这也是大多数编程语言的选择。

语法分析器实现原理

将编程语言所有的生产规则映射到对应的方法上，这些方法构成的树桩结构最终会产生一棵抽象语法树。