本节书摘来自华章社区《ANTLR 4权威指南》一书中的第2章，第2.4节使用语法分析树来构建语言类应用程序，作者［美］　特恩斯·帕尔（Terence Parr），更多章节内容可以访问云栖社区“华章社区”公众号查看

2.4　使用语法分析树来构建语言类应用程序
为了编写一个语言类应用程序，我们必须对每个输入的词组或者子词组执行一些适当的操作。进行这项工作最简单的方式是操作语法分析器自动生成的语法分析树。这种方式的优点在于，我们能够重回我们所熟悉的Java领域。这样，在语言类应用程序进一步的构建过程中，我们就不需要再学习复杂的ANTLR语法了。
首先，我们来认识一下ANTLR在识别和建立语法分析树的过程中使用的数据结构和类名。熟悉这些数据结构将为我们未来的讨论奠定基础。
前已述及，词法分析器处理字符序列并将生成的词法符号提供给语法分析器，语法分析器随即根据这些信息来检查语法的正确性并建造出一棵语法分析树。这个过程对应的ANTLR类是CharStream、Lexer、Token、Parser，以及ParseTree。连接词法分析器和语法分析器的“管道”就是TokenStream。图2-2展示了这些类型的对象在内存中的交互方式。
ANTLR尽可能多地使用共享数据结构来节约内存。如图2-2所示，语法分析树中的叶子节点（词法符号）仅仅是盛放词法符号流中的词法符号的容器。每个词法符号都记录了自己在字符序列中的开始位置和结束位置，而非保存子字符串的拷贝。其中，不存在空白字符对应的词法符号（索引为2和4的字符）的原因是，我们假定我们的词法分析器会丢弃空白字符。
图2-2中也显示出，ParseTree的子类RuleNode和TerminalNode，二者分别是子树的根节点和叶子节点。RuleNode有一些令人熟悉的方法，例如getChild()和getParent()，但是，对于一个特定的语法，RuleNode并不是确定不变的。为了更好地支持对特定节点的元素的访问，ANTLR会为每条规则生成一个RuleNode的子类。如图2-3所示，在我们的赋值语句的例子中，子树根节点的类型实际上是StatContext、AssignContext以及ExprContext。

因为这些根节点包含了使用规则识别词组过程中的全部信息，它们被称为上下文（context）对象。每个上下文对象都知道自己识别出的词组中，开始和结束位置处的词法符号，同时提供访问该词组全部元素的途径。例如，AssignContext类提供了方法ID()和方法expr()来访问标识符节点和代表表达式的子树。
给定这些类型的具体实现，我们可以手工写出对语法分析树进行深度优先遍历的代码。这样，在访问其中的节点时，我们可以进行一切所需的操作。这个过程中的典型操作是诸如计算结果、更新数据结构或者产生输出一类的事情。实际上，我们可以利用ANTLR自动生成并遍历树的机制，而不需要每次都重复编写遍历树的代码。

2.5　语法分析树监听器和访问器
ANTLR的运行库提供了两种遍历树的机制。默认情况下，ANTLR使用内建的遍历器访问生成的语法分析树，并为每个遍历时可能触发的事件生成一个语法分析树监听器接口（parse-tree listener interface）。监听器非常类似于XML解析器生成的SAX文档对象。SAX监听器接收类似startDocument()和endDocument()的事件通知。一个监听器的方法实际上就是回调函数，正如我们在图形界面程序中响应复选框点击事件一样。除了监听器的方式，我们还将介绍另外一种遍历语法分析树的方式：访问者模式（vistor pattern）。
1.语法分析树监听器
为了将遍历树时触发的事件转化为监听器的调用，ANTLR运行库提供了ParseTree-
Walker类。我们可以自行实现ParseTreeListener接口，在其中填充自己的逻辑代码（通常是调用程序的其他部分），从而构建出我们自己的语言类应用程序。
ANTLR为每个语法文件生成一个ParseTreeListener的子类，在该类中，语法中的每条规则都有对应的enter方法和exit方法。例如，当遍历器访问到assign规则对应的节点时，它就会调用enterAssign()方法，然后将对应的语法分析树节点——AssignContext的实例——当作参数传递给它。在遍历器访问了assign节点的全部子节点之后，它会调用exitAssign()。图2-4用粗虚线标识了ParseTreeWalker对语法分析树进行深度优先遍历的过程。

其中，粗虚线显示了对语法分析树进行深度优先遍历的过程。细虚线标示出访问器方法的调用顺序。我们可以在自己的程序代码中实现这个访问器接口，然后调用visit()方法来开始对语法分析树的一次遍历。

ANTLR内部为访问者模式提供的支持代码会在根节点处调用visitStat()方法。接下来，visitStat()方法的实现将会调用visit()方法，并将所有子节点当作参数传递给它，从而继续遍历的过程。或者，visitMethod()方法可以显式调用visitAssign()方法等。
ANTLR会提供访问器接口和一个默认实现类，免去我们一切都要自行实现的麻烦。这样，我们就可以专注于那些我们感兴趣的方法，而无须覆盖接口中的方法。我们将在第7章中深入介绍访问器和监听器。
与语法分析相关的术语
本章介绍了很多重要的与语言识别相关的术语。
语言　一门语言是一个有效语句的集合。语句由词组组成，词组由子词组组成，子词组又由更小的子词组组成，依此类推。
语法　语法定义了语言的语义规则。语法中的每条规则定义了一种词组结构。
语义树或语法分析树　代表了语句的结构，其中的每个子树的根节点都使用一个抽象的名字给其包含的元素命名。即子树的根节点对应了语法规则的名字。树的叶子节点是语句中的符号或者词法符号。
词法符号　词法符号就是一门语言的基本词汇符号，它们可以代表像是“标识符”这样的一类符号，也可以代表一个单一的运算符，或者代表一个关键字。
词法分析器或者词法符号生成器　将输入的字符序列分解成一系列词法符号。一个词法分析器负责分析词法。
语法分析器　语法分析器通过检查语句的结构是否符合语法规则的定义来验证该语句在特定语言中是否合法。语法分析的过程好比是走迷宫，通过比较语句中和地板上的单词来从入口走到出口。ANTLR能够生成被称为ALL()的自顶向下的语法分析器，ALL()是指它可以利用剩余的所有输入文本来进行决策。自顶向下的语法分析器以结果为导向，首先匹配最粗粒度的规则，这样的规则通常命名为program或者inputFile。
递归下降的语法分析器　这是自顶向下的语法分析器的一种实现，每条规则都对应语法分析器中的一个函数。
前向预测　语法分析器使用前向预测来进行决策，具体方法是：将输入的符号与每个备选分支的起始符号进行比较。
迄今为止，我们已经大体上了解了ANTLR的工作原理。在本章中，我们认识了从字符序列到语法分析树的整个流程，学习了ANTLR运行库的一些关键类。此外，我们还简单了解了监听器和访问器机制，它们是连接语法分析器和特定程序代码的桥梁。在下一章中，我们将通过一个实际的例子来使大家加深对上述概念的理解。