现在我们已经安装了ANTLR，并对如何构建和运行一个小例子有了一些了解，接下来我们将看看整体情况。在本章中，我们将学习与语言应用相关的重要过程、术语和数据结构。在学习过程中，我们将确定关键的ANTLR对象，并对ANTLR在幕后为我们做了什么有一些了解。

让我们进入元编程的世界吧！

要实现一门语言，我们需要构建一个应用程序，它能读取句子并对其发现的短语和输入符号做出适当的反应。（一门语言是一组有效的句子，句子由短语组成，而短语由子短语和词汇符号组成。）广义上说，如果一个应用程序计算或“执行”句子，我们称之为解释器。例如，计算器、配置文件阅读器和Python解释器都是解释器的例子。如果我们将句子从一种语言转换为另一种语言，我们称之为翻译器。例如，Java到C#的转换器和编译器就是翻译器的例子。

为了做出适当的反应，解释器或翻译器必须识别特定语言的所有有效句子、短语和子短语。识别一个短语意味着我们可以识别其中的各个组成部分，并将其与其他短语区分开来。例如，我们可以将输入sp = 100;识别为一个编程语言的赋值语句。这意味着我们知道sp是赋值的目标，而100是要存储的值。同样地，如果我们正在识别英语句子，我们会识别词性，如主语、谓语和宾语。识别赋值语句sp = 100;还意味着语言应用程序将其明确地与import语句等其他语句区分开来。在识别之后，应用程序将执行适当的操作，比如performAssignment("sp", 100)或translateAssignment("sp", 100)。

识别语言的程序称为解析器或语法分析器。语法指的是规定语言成员资格的规则，在本书中，我们将使用ANTLR语法来指定语言的语法。语法只是一组规则，每个规则都表达了一个短语的结构。ANTLR工具将语法转换为解析器，其外观与有经验的程序员手工构建的解析器非常相似。（ANTLR是一个编写其他程序的程序。）语法本身遵循针对指定其他语言进行优化的语言的语法：ANTLR的元语言。

如果将解析过程分解为两个相似但不同的任务或阶段，解析就会变得更容易。这些独立的阶段反映了我们大脑阅读英文文本的方式。我们不会逐个字符地阅读句子。相反，我们将句子视为一个单词流。人类大脑在识别语法结构之前，会下意识地将字符序列分组为单词，并在词典中查找它们。如果我们阅读莫尔斯码，这个过程更加明显，因为我们必须将点和划线转换为字符，然后再阅读消息。当阅读像Humuhumunukunukuapua'a这样的长单词时，这一过程也是明显的，它是夏威夷州的鱼类。

将字符分组为单词或符号（标记）的过程称为词法分析或仅仅是标记化。我们称将输入标记化的程序为词法分析器。词法分析器可以将相关的标记分组成标记类别或标记类型，例如INT（整数）、ID（标识符）、FLOAT（浮点数）等。当解析器只关心类型而不关心个别符号时，词法分析器将词汇符号分组为类型。标记至少包含两部分信息：标记类型（用于识别词法结构）和由词法分析器匹配的标记的文本。

第二个阶段是实际的解析器，它利用这些标记来识别句子结构，例如赋值语句。默认情况下，ANTLR生成的解析器会构建一种称为解析树或语法树的数据结构，记录解析器如何识别输入句子及其组成短语的结构。以下图示了语言识别器的基本数据流：

解析树的内部节点是将其子节点分组和标识的短语名称。根节点是最抽象的短语名称，在本例中是stat（表示“语句”的缩写）。解析树的叶子节点始终是输入标记。句子是符号的线性序列，实际上只是我们人类在硬件中本能地理解的解析树的序列化表示。为了向他人传达一个想法，我们必须使用一个词流在他们的头脑中召唤出同样的解析树。

通过生成解析树，解析器将一个方便的数据结构传递给应用程序的其他部分，其中包含有关解析器如何将符号分组为短语的完整信息。树在后续步骤中易于处理，并且程序员对其非常了解。更好的是，解析器可以自动生成解析树。

通过使用解析树进行操作，需要识别相同语言的多个应用程序可以重用一个解析器。另一种选择是直接将特定于应用程序的代码片段嵌入到语法中，这是传统的解析器生成器所做的。ANTLR v4仍然支持这种方式（请参见第10章，属性和动作），但解析树的设计更加整洁和解耦。

由于我们使用一组规则来指定短语结构，解析树的子树根节点对应于语法规则名称。作为即将到来的事物的预览，这是与图中assign子树的第一级对应的语法规则：

assign : ID '=' expr ';' ; // match an assignment statement like "sp = 100;"

理解ANTLR如何将这些规则转换为可读的解析代码对于使用和调试语法非常重要，因此让我们深入了解解析的工作原理。

实现解析器

ANTLR工具根据我们刚刚看到的assign等语法规则生成递归下降解析器。递归下降解析器实际上只是一组递归方法，每个方法对应一个规则。下降（descent）一词指的是解析从解析树的根节点开始，并向叶子节点（标记）的方向进行。我们首先调用的规则，即起始符号，成为解析树的根节点。这意味着在前面的部分中，对于解析树，我们将调用stat()方法。对于这种类型的解析，更常见的术语是自顶向下（top-down）解析；递归下降解析器只是自顶向下解析器实现的一种。

为了了解递归下降解析器的样子，这里是ANTLR生成的assign规则的方法（稍作清理）：

// assign : ID '=' expr ';' ;
void assign() {    // method generated from rule assign
  match(ID);      // compare ID to current input symbol then consume
  match('=');  
  expr();         // match an expression by calling expr()
  match(';');
}

递归下降解析器的有趣之处在于调用方法stat()、assign()和expr()所形成的调用图与解析树的内部节点相一致。（请快速回顾一下解析树图。）match()的调用对应于解析树的叶子节点。在手动构建的解析器中，为了构建解析树，我们需要在每个规则方法的开头插入“添加新的子树根节点”操作，并在match()处插入“添加新的叶子节点”操作。

assign()方法仅仅检查确保所有必要的标记都存在且顺序正确。当解析器进入assign()方法时，它不必在多个备选项之间进行选择。备选项是规则定义右侧的选择之一。例如，调用assign的stat规则可能具有其他类型的语句的列表。

/** Match any kind of statement starting at the current input position */ 

stat: assign      // First alternative ('|' is alternative separator)
    | ifstat      // Second alternative
    | whilestat
   ...
    ;

stat的解析规则看起来像是一个switch语句。

void stat() {
  switch ( «current input token» ) {
    CASE ID    : assign(); break;
    CASE IF    : ifstat(); break;
    CASE WHILE : whilestat(); break;
    ...
    default    : «raise no viable alternative exception»
    } 
 }

方法stat()必须通过检查下一个输入标记来进行解析决策或预测。解析决策预测哪个备选项将成功。在这种情况下，看到WHILE关键字预测stat规则的第三个备选项。因此，规则方法stat()调用whilestat()。你可能之前听过前瞻标记（lookahead token）这个术语；它就是下一个输入标记。前瞻标记是解析器在匹配和消耗标记之前探查到的任何标记。

有时，解析器需要大量的前瞻标记来预测哪个备选项会成功。它甚至可能需要考虑从当前位置到文件结束的所有标记！ANTLR会在后台默默地处理所有这些情况，但了解决策过程基本原理对于调试生成的解析器很有帮助。

为了可视化解析决策，想象一个迷宫，它只有一个入口和一个出口，在地板上写有单词。从入口到出口的每个单词序列都代表一个句子。迷宫的结构类似于定义语言的语法规则。为了测试一个句子是否属于语言，我们将句子中的单词与沿着迷宫行走时遇到的单词进行比较。如果我们能够通过遵循句子中的单词到达出口，那么这个句子就是有效的。

为了在迷宫中导航，我们必须在每个岔路口选择一条有效的路径，就像在解析器中选择备选项一样。我们必须通过将句子中的下一个单词与从岔路口延伸出来的每条路径上可见的单词进行比较来决定选择哪条路径。从岔路口能看到的单词类似于前瞻标记。当每条路径以唯一的单词开始时，决策就相当简单了。在stat规则中，每个备选项都以唯一的标记开始，因此stat()可以通过查看第一个前瞻标记来区分备选项。

当从岔路口开始的路径的起始单词重叠时，解析器需要向前查找，扫描以区分备选项的单词。ANTLR会根据需要自动调整前瞻的数量。如果沿着到出口（文件结束）的多条路径的前瞻相同，那么当前输入短语就有多个解释。解决这种模糊性是我们接下来要讨论的主题。在此之后，我们将了解如何使用解析树构建语言应用程序。

你不能把太多水倒入核反应堆中

一个模棱两可的短语或句子是指具有多个解释的短语或句子。换句话说，这些词可以适应多种语法结构。章节标题“你不能把太多水倒入核反应堆中”是我多年前在《周六夜现场》（Saturday Night Live）的一个小品中看到的一个模棱两可的句子。角色们不确定是应该小心不要将太多水倒入反应堆中，还是应该将大量水倒入反应堆中。

在自然语言中，歧义可能会很有趣，但对基于计算机的语言应用程序来说却会造成问题。为了解释或翻译一个短语，程序必须能够唯一地确定其含义。这意味着我们必须提供无歧义的语法，以便生成的解析器可以以唯一的方式匹配每个输入短语。

虽然我们还没有详细学习语法，但让我们在这里包含一些模棱两可的语法，以使歧义的概念更加具体化。如果在构建语法时遇到歧义，您可以参考本节内容。

有些模棱两可的语法是显而易见的。

stat: ID '=' expr ';'       // match an assignment; can match "f();"
    | ID '=' expr ';'       // oops! an exact duplicate of previous alternative 
    ;
expr: INT ;

然而，大多数情况下，歧义会更加微妙，就像以下的语法一样，它可以通过stat规则的两个备选项来匹配函数调用：

stat: expr ';'            // expression statement
    | ID '(' ')' ';'      // function call statement 
    ;
expr: ID '(' ')' 
    | INT
    ;

这是输入f();在stat规则中的两个解释：

左侧的解析树显示了f()匹配到expr规则的情况。右侧的树显示f()匹配到stat规则第二个备选项的开头。

由于大多数语言设计者都希望语法是无歧义的，所以一个歧义的语法类似于一个编程错误。我们需要重新组织语法，为每个输入短语向解析器提供单一的选择。如果解析器检测到一个歧义的短语，它必须选择一个可行的备选项。ANTLR通过选择涉及决策的第一个备选项来解决歧义。在这种情况下，解析器将选择与左侧解析树关联的f()的解释。

歧义不仅可能出现在解析器中，还可能出现在词法分析器中，但ANTLR会解决这些歧义，使规则行为自然。ANTLR通过将输入字符串与语法中首先指定的规则进行匹配来解决词法上的歧义。为了了解其工作原理，让我们看一个在大多数编程语言中常见的歧义情况：关键字和标识符规则之间的歧义。关键字begin（后面跟非字母字符）也可以作为标识符，至少在词法上是如此，因此词法分析器可以将b-e-g-i-n匹配到任一规则。

BEGIN : 'begin' ; // match b-e-g-i-n sequence; ambiguity resolves to BEGIN 
ID : [a-z]+ ; // match one or more of any lowercase letter

关于这种词法上的歧义，更多内容请参阅第74页的“匹配标识符”部分。 请注意，词法分析器会尝试匹配每个标记可能的最长字符串，这意味着输入beginner只会匹配到ID规则。词法分析器不会将beginner匹配为BEGIN后跟ID匹配输入ner。

有时，一个语言的语法本身就存在明显的歧义，无论如何重新组织语法都无法改变这个事实。例如，算术表达式的自然语法可以按照两种方式解释输入1+2*3，一种是从左到右执行操作（就像Smalltalk那样），另一种是按照大多数语言的优先级顺序。我们将在第5.4节“处理优先级、左递归和结合性”（第69页）中学习如何隐式指定表达式的运算符优先级顺序。

另一种类型的歧义可以通过使用上下文信息来解决，例如标识符的定义方式。考虑代码片段i*j;，从语法上看，它像是一个表达式，但它的含义或语义取决于i是类型名称还是变量。如果i是一个类型名称，那么这个代码片段不是一个表达式，而是将变量j声明为指向类型i的指针。我们将在第11章“使用语义谓词改变解析”（第189页）中看到如何解决这些歧义情况。

解析器本身仅用于检测输入句子是否符合语言规范并构建解析树。这是非常关键的内容，但现在是时候看看语言应用程序如何利用解析树来解释或翻译输入了。

利用解析树构建语言应用程序

要创建一个语言应用程序，我们需要对每个输入短语或子短语执行适当的代码。最简单的方法是对解析器自动生成的解析树进行操作。在解析树上操作的好处是我们回到了熟悉的Java领域。为了构建应用程序，无需学习更多关于ANTLR的语法。

让我们详细了解ANTLR在识别和解析树方面使用的数据结构和类名。对数据结构有一定了解将使未来的讨论更加具体化。

之前我们了解到词法分析器处理字符并将标记传递给解析器，解析器检查语法并创建解析树。对应的ANTLR类包括CharStream、Lexer、Token、Parser和ParseTree。连接词法分析器和解析器的“管道”被称为TokenStream。下面的图示展示了这些类型的对象在内存中的连接方式。

这些ANTLR数据结构尽可能共享数据，以减少内存需求。图中显示，解析树中的叶子节点（标记节点）是指向标记流中的标记的容器。这些标记记录了它们在CharStream中的起始和结束字符索引，而不是复制子字符串。由于我们可以假设词法分析器会忽略空白字符，因此与空白字符（索引为2和4）无关联的标记不会存在。

图中还显示了ParseTree的子类RuleNode和TerminalNode，它们对应于子树根节点和叶子节点。RuleNode具有熟悉的方法，如getChild()和getParent()，但RuleNode不针对特定的语法。为了更好地支持对特定节点内部元素的访问，ANTLR为每个规则生成一个RuleNode子类。下图显示了我们的赋值语句示例中子树根节点的具体类，它们是StatContext、AssignContext和ExprContext：

这些被称为上下文对象，因为它们记录了我们对规则识别的短语的所有了解。每个上下文对象都知道被识别短语的起始和结束标记，并提供访问该短语的所有元素的方法。例如，AssignContext提供了ID()和expr()等方法来访问标识符节点和表达式子树。

根据这些具体类型的描述，我们可以手动编写代码来对树进行深度优先遍历。在发现和完成节点时，我们可以执行任何我们想要的操作。常见的操作包括计算结果、更新数据结构或生成输出。然而，为了避免为每个应用程序重复编写相同的树遍历样板代码，我们可以使用ANTLR自动生成的树遍历机制。

解析树监听器和访问者模式

ANTLR在其运行时库中提供对两种树遍历机制的支持。默认情况下，ANTLR生成一个解析树监听器接口，用于响应内置树遍历器触发的事件。这些监听器本质上类似于用于XML解析器的SAX文档处理程序对象。SAX监听器会接收诸如startDocument()和endDocument()之类的事件通知。监听器中的方法只是回调函数，类似于我们在GUI应用程序中响应复选框点击的方式。一旦我们了解了监听器，我们将看到ANTLR还可以生成遵循访问者设计模式的树遍历器。

解析树监听器

为了遍历树并触发对监听器的调用，ANTLR的运行时库提供了ParseTreeWalker类。为了构建一个语言应用程序，我们需要构建一个实现ParseTreeListener接口的监听器，其中包含应用程序特定的代码，通常会调用更大的周围应用程序。

ANTLR会为每个语法生成一个特定的ParseTreeListener子类，为每个规则生成enter和exit方法。例如，当遍历到assign规则的节点时，它会触发enterAssign()方法，并将AssignContext解析树节点作为参数传递。在遍历完assign节点的所有子节点之后，它会触发exitAssign()方法。下面显示的树图展示了ParseTreeWalker执行深度优先遍历的过程，用粗虚线表示。

它还标识了ParseTreeWalker在遍历过程中调用assign规则的enter和exit方法的位置（其他监听器的调用未显示）。

图1中的图表，"ParseTreeWalker调用序列"（见第19页），展示了ParseTreeWalker对我们语句树的监听器进行的完整调用序列。

监听器机制的美妙之处在于它是自动完成的。我们不需要编写解析树遍历器，我们的监听器方法也不需要显式地访问它们的子节点。

解析树访问者

然而，有些情况下，我们希望控制遍历过程本身，显式地调用方法来访问子节点。使用选项-visitor，ANTLR可以从语法中生成一个访问者接口，每个规则对应一个visit方法。下面是在我们的解析树上运行的熟悉的访问者模式：

粗虚线表示对解析树的深度优先遍历。细虚线表示访问者方法之间的方法调用顺序。为了开始对树的遍历，我们的应用程序特定的代码将创建一个访问者实现并调用visit()方法。

ParseTree tree = ... ; // tree is result of parsing MyVisitor 
v = new MyVisitor();
v.visit(tree);

在看到根节点时，ANTLR的访问者支持代码将调用visitStat()。然后，visitStat()的实现将使用子节点作为参数调用visit()以继续遍历。或者，visitMethod()可以显式地调用visitAssign()，以此类推。

通过生成访问者接口并提供具有默认实现的访问者方法的类，ANTLR为我们提供了比自己编写所有代码更好的起点。这样，我们避免了必须覆盖接口中的每个方法，让我们只专注于感兴趣的方法。我们将在第7章，解耦语法和应用程序特定代码（第109页）中全面了解访问者和监听器的使用。

现在，我们已经了解了整个过程。我们查看了从字符流到解析树的整体数据流，并确定了ANTLR运行时中的关键类名。我们刚刚看到了将解析器与应用程序特定代码连接起来使用的监听器和访问者机制的摘要。让我们通过在下一章中深入研究一个真实的示例来使这一切更加具体化。