本节书摘来自华章计算机《ANTLR 4权威指南》一书中的第2章，第2.2节，作者［美］ 特恩斯·帕尔（Terence Parr），张博 译，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.2　实现一个语法分析器

ANTLR工具依据类似于我们之前看到的assign的语法规则，产生一个递归下降的语法分析器（recursive-descent parser）。递归下降的语法分析器实际上是若干递归方法的集合，每个方法对应一条规则。下降的过程就是从语法分析树的根节点开始，朝着叶节点（词法符号）进行解析的过程。首先调用的规则，即语义符号的起始点，就会成为语法分析树的根节点。在前一节的例子中，就是调用stat()方法作为起始点的。这种解析过程的更广为人知的名字是“自上而下的解析”，递归下降的语法分析器仅仅是自上而下的语法分析器的一种实现。

下面是一个ANTLR根据assign规则生成的方法（稍微经过格式整理），用于展示递归下降的语法分析器的实现细节：

递归下降的语法分析器最神奇的地方在于，通过方法stat()、assign()和expr()的调用描绘出的调用路线图映射到了语法分析树的节点上（请迅速回顾一下图2-1）。调用match()对应了语法分析树的叶子节点。在手工构造的语法分析器中，我们需要在每条规则对应的方法的开始位置插入“增加一个新的子树根节点”这样的操作，在match()方法中插入“增加一个新的叶子节点”这样的操作。

assign()方法仅仅验证所有的词汇符号都存在且顺序正确。当语法分析器进入assign()方法的内部时，仅有一个备选分支（alternative），无须做出选择。一个备选分支指的是规则的右侧定义的多个方案之一。例如，除了assign之外，下面的stat规则还可能对应其他多种语句。

对stat语法规则的解析像是一个switch语句：

stat()方法必须通过检查下一个词法符号来做出语法分析决策（parsing decision）或者预测（prediction）。做出决策的过程实际上就是判断哪一个备选分支是正确的。在上面的例子中，一个WHILE关键字意味着它选择stat规则的第三个备选分支。因此，stat()方法将调用whilestat()方法。你可能听说过前瞻词法符号（lookahead token）这个术语，它其实就是下一个输入的词法符号。一个前瞻词法符号是指任何一个在被匹配和消费之前就由语法分析器嗅探出的词法符号。有些时候，语法分析器需要很多个前瞻词法符号来判断语义规则的哪个方案是正确的，甚至可能要从当前的词法符号的位置开始，一直分析到文件末尾才能做出判断！ANTLR默默地帮你完成了所有的这些工作，不过，对其决策过程的基本理解将会有助于调试ANTLR自动生成的语法分析器。

为了让语法分析的决策过程可视化，想象一个迷宫，它只有一个入口和一个出口，迷宫的地板上写着单词。每个从入口到出口的路径上的单词序列代表一个语句。这个迷宫的结构就好比是一种语言所定义的全部语法规则。为了测试一个语句是不是合法，我们将这个语句中的单词和迷宫的地板上的单词比较，然后沿着这个语句的单词所描述的路径在迷宫中前进。如果我们能够通过这个语句中的单词序列指定的路径到达出口，那么这个语句就是合法的。

为了到达迷宫的出口，我们必须在每个分岔路口选择一条正确的路径，就好像一个语法分析器要在多个备选分支中做出选择一样。我们必须将语句中接下来的若干个单词与站在路口所看到的不同岔路地板上的单词相比较，从而决定走哪条岔路。我们站在路口所看到的地板上的单词就好像是前瞻词法符号。显然，若每条岔路都以一个独一无二的单词开始，做出选择就会容易许多。在上例中的stat规则中，每个备选分支都是以一个独一无二的词法符号开始的，因此stat()方法可以通过检查第一个前瞻词法符号来区分不同的备选分支。

当每条岔路的起始单词有重复的时候，语法分析器就需要更多地进行前瞻，即通过扫描更多的单词来区分不同的备选分支。在每次语法分析决策中，ANTLR能够根据情况自动调整前瞻的数量。如果通过前瞻，我们能够经多条路径抵达迷宫出口（文件末尾），那就意味着能够用多种语义去解释当前的输入文本。解决这种歧义是我们下一节的任务，之后，我们将会学习如何使用语法分析树来构建语言类应用程序。