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

第2章

纵 观 全 局

在上一章中，我们安装了ANTLR，了解了如何构建和运行一个简单的示例语法。在本章中，我们将纵观全局，学习语言类应用程序相关的重要过程、术语和数据结构。随着学习的深入，我们将认识一些关键的ANTLR对象，并简单了解ANTLR在背后帮助我们完成的工作。

2.1　从ANTLR元语言开始

为了实现一门编程语言，我们需要构建一个程序，读取输入的语句，对其中的词组和输入符号进行正确的处理。语言（language）由一系列有意义的语句组成，语句（sentence）由词组组成，词组（phrase）是由更小的子词组（subphrase）和词汇符号（vocabulary symbol）组成。一般来说，如果一个程序能够分析计算或者“执行”语句，我们就称之为解释器（interpreter）。这样的例子包括计算器、读取配置文件的程序和Python解释器。如果一个程序能够将一门语言的语句转换为另外一门语言的语句，我们称之为翻译器（translator）。这样的例子包括Java到C#的转换器和普通的编译器。

为了达到预期的目的，解释器或者翻译器需要识别出一门特定语言的所有的有意义的语句、词组和子词组。识别一个词组意味着我们可以将它从众多的组成部分中辨认和区分出来。例如，我们能够将输入的“sp = 100;”识别为一个赋值语句，这意味着我们需要知道sp是被赋值的目标，100是要被赋予的值。与之类似，如果我们要识别英文语句，就需要辨认出一段对话的不同部分，例如主语、谓语和宾语。识别语句“sp = 100;”还意味着语言类应用程序能够将它和import表达式之类的语句区分开。在成功识别后，程序就能执行适当的操作，诸如performAssignment ("sp", 100)或者translateAssignment ("sp", 100)。

识别语言的程序称为语法分析器（parser）或者句法分析器（syntax analyzer）。句法（syntax）是指约束语言中的各个组成部分之间关系的规则，在本书中，我们会通过ANTLR语法来指定语言的句法。语法（grammar）是一系列规则的集合，每条规则表述出一种词汇结构。ANTLR工具能够将其转换为如同经验丰富的开发者手工构建一般的语法分析器（ANTLR是一个能够生成其他程序的程序）。ANTLR语法本身又遵循了一种专门用来描述其他语言的语法，我们称之为ANTLR元语言（ANTLR抯 meta-language）。

如果我们将语法分析的过程分解为两个相似但独立的任务或者说阶段时，实现起来就容易多了。这两个阶段与我们的大脑阅读英文文本的过程相类似。我们并不是一个字符一个字符地阅读一个句子，而是将句子看作一列单词。在识别整个句子的语法结构之前，人类的大脑首先通过潜意识将字符聚集为单词，然后获取每个单词的意义。这个过程在阅读摩斯电码的时候更加明显，因为我们需要首先将点和划转换为字符才能获取消息本身。同样的事情也发生在阅读长单词时，比如说阅读这个单词Humuhumunukunukuapua抋——它是夏威夷的州鱼。

将字符聚集为单词或者符号（词法符号，token）的过程称为词法分析（lexical analysis）或者词法符号化（tokenizing)。我们把可以将输入文本转换为词法符号的程序称为词法分析器（lexer）。词法分析器可以将相关的词法符号归类，例如INT（整数）、ID（标识符）、FLOAT（浮点数）等。当语法分析器不关心单个符号，而仅关心符号的类型时，词法分析器就需要将词汇符号归类。词法符号包含至少两部分信息：词法符号的类型（从而能够通过类型来识别词法结构）和该词法符号对应的文本。

第二个阶段是实际的语法分析过程，在这个过程中，输入的词法符号被“消费”以识别语句结构，在上例中即为赋值语句。默认情况下，ANTLR生成的语法分析器会建造一种名为语法分析树（parse tree）或者句法树（syntax tree）的数据结构，该数据结构记录了语法分析器识别出输入语句结构的过程，以及该结构的各组成部分。图2-1展示了数据在一个语言类应用程序中的基本流动过程。

语法分析树的内部节点是词组名，这些名字用于识别它们的子节点，并将子节点归类。

根节点是最抽象的一个名字，在本例中即stat（statement的简写）。语法分析树的叶子节点永远是输入的词法符号。句子，也即符号的线性组合，本质上是语法分析树在人脑中的串行化。为了能与其他人沟通，我们需要使用一串单词，使得他们能在脑海中构建出一棵相同的语法分析树。

通过语法分析树这种方便的数据结构，语法分析器就能将诸如“符号是如何构成词组的”这样的完整信息传达给程序的其余部分。树结构不仅在后续的步骤中易于处理，而且也是一种为开发者所熟知的数据结构。幸运的是，语法分析器能够自动生成语法分析树。

通过操纵语法分析树，识别同一种语言的不同程序就能复用同一个语法分析器。另外一种解决方案，也是传统的生成语法分析器的方案，是直接在语法文件中嵌入与这种程序相关的代码。ANTLR 4仍然允许这种传统的方案（详见第10章），不过，使用语法分析树可以使程序更整洁、解耦性更强。

在语言的翻译过程中，一个阶段依赖于前一个阶段的计算结果和信息，因此需要多次进行树的遍历（tree walk），这种情况下语法分析树也是非常有用的。在其他情况下，将一个复杂的程序分解为多个阶段会大大简化编码和测试工作，与其每个阶段都重新解析一下输入的字符流，不如首先生成语法分析树，然后多次访问其中的节点，这样更有效率。

由于我们使用一系列的规则指定语句的词汇结构，语法分析树的子树的根节点就对应语法规则的名字。在下文的长篇大论之前，我们先看一个例子。下面这条语法规则对应图2-1中的赋值语句子树的第一级：

使用和调试ANTLR语法的一个基本要求是，理解ANTLR是如何将这样的规则转换为人类可阅读的语法分析程序的，因此接下来我们将深入研究语法分析的过程。