ANTLR v4 学习笔记（一）－ANTLR 初体验

发表于 更新于 分类于 阅读次数：

新学期又迎来新课程《解释器构造实践》，通过综合应用来加深对编译原理技术的理解。该实验课最终要求设计并编制调试一个 CMM（C Minus Minus，C 语言的一个子集）程序结构的解释器，对输入的满足 CMM 语法的源程序文件进行解释执行。

课程推荐使用自动化生成工具 ANTLR，因此在这里持续记录我的解释器构造及 ANTLR 学习过程。当然也不排除之后可能会换用其他工具，或者全部自己实现。

ANTLR 目前更新到 v4.7，有一本详尽的使用说明《The Definitive ANTLR 4 Reference》。可惜到目前为止还没有找到中文译本，只有一些零零碎碎的翻译。所幸读完前两章，感觉我的英文水平还是能支持我不用查太多的词就能理解书中所著内容。因此这篇学习笔记也会整理一些书中重要的内容（当然会加以翻译）。

更新记录：

  • 17.09.06 《The Definitive ANTLR 4 Reference》Chapter 1、2 阅读完毕，笔记初版发布
  • 17.09.11 Chapter 3 阅读完毕，增加动手上路章节。
  • 17.09.20 对全文进行一定的润色，并修正了一些不太贴切的翻译

我对编译技术的认识

在正式进行 ANTLR 的学习前，先让我们聊一聊在经过上学期《编译技术及应用》的学习，以及查阅了有关资料后，我对编译技术和编译工具的一点认识。

说实话，如果单单是谈在《编译技术及应用》这门课上的认识的话，我可能只能像孔乙己一样，接连便是难懂的话，什么“上下文无关文法”，什么“LL(1)”，引得各位都哄笑起来，屏幕内外充满了快活的空气…

尽管经过了计算器和 JSONCompiler 两次实验，但我们可能对编译技术的应用还没有什么认识，觉得编译器的唯一用处就是写一个能把 xx 语言翻译成 xx 然后再运行成功…

基于写这篇博文的契机，我查了一下编译技术的各种应用，才发现其实“编译”这个概念应用还是很广泛的。

比如我的博客是用 hexo 这个博客框架搭建的，而你现在看到的这篇博文是 hexo 将我写的 markdown 文件解析成 html 生成的，这其中自然有编译模块的功劳。

再比如作为一个前端，有不少我使用过或日常接触的工具、框架其实都是编译相关知识的应用：Babel 作为 ES 6 的所有新特性还没有在主流浏览器全面推广的一个暂时的解决方法，将 ES 6 编译成 ES 5 等浏览器能够运行的 JavaScript 代码；在 Vue 中频繁出现的模版引擎、v-for="item in list"等也有编译的身影。如果真正对编译原理理解透彻，大概可以去摸摸 v8 ，帮助提高一下 Node.js 的运行效率。

编程，本质上是程序员通过语言来控制计算机按照人的意志去进行各种运算和操作。自 20 世纪 50 年代早期，第一个只能进行单目运算的编译程序诞生起，编译技术一直作为人与计算机之间的传声筒，支撑着计算机语言的发展，使其更加系统化、合理化。

在知乎上“编译原理学了有什么用？”这个提问下，有答主贴了一幅《C 编译器解剖》序的照片，其中有一段话：

操作系统和编译器就如武侠小说中的“九阴真经”，没看过“九阴真经”的侠客也可以行走江湖，但看过并练成九阴真经的人最终才更有机会登上华山之巅。

怀着对程序员之巅的心向往之，我也对编译原理更生敬畏。

当然，如何让这门古老的屠龙术落地，而不至于成为学生心中虚无缥缈的空中楼阁。我个人认为可以再开设一些相关的新课题，让学生能够充分了解编译技术的实用性，从而能够自主学习、实践。我也希望《解释器构造实践》能成为一个不错的起点。

初识 ANTLR

对应《The Definitive ANTLR 4 Reference》中 Chapter 1 Meet ANTLR。书里的这一章主要是介绍 ANTLR 的下载安装方法，并运行了一个简单的 demo。

安装 ANTLR

ANTLR 是用 Java 编写的，所以就算你想使用 C# 或者 C++ 来配合 ANTLR 生成解释器，安装 ANTLR 前也需要有 Java 环境。

之后需要下载 antlr-4.x-complete.jar（越新越好，4.x 指最新版本的版本号）并把它放在你记得住的地方。这个 jar 包包含了运行 ANTLR 工具所需要的所有依赖，还包含两个支持库：一个树状排版库，以及 StringTemplate，一个用于生成代码以及其他结构化文本的模版引擎。

安装的具体步骤请直接看官网的 Quick Start，在此不作展示。

ANTLR 全貌

对应《The Definitive ANTLR 4 Reference》中 Chapter 2 The Big Picture，书中这一章介绍了从字符流到语法分析树的过程、ANTLR 运行流程中的一些重要术语，以及ANTLR 自带的 Listener、Visitor 这两种遍历树的机制。

想要实现一种语言，我们就需要构建读取句子的应用，并对输入的元素做出正确的反应。

如果一个应用可以计算或执行句子，我们就叫它解释器（interpreter）。包括计算器、配置文件读取器、Python 解释器都属于解释器。

而如果一个应用将句子转换成另一种语言，我们就叫它翻译器（translator）。例如 Java 到 C# 的翻译器和编译器都属于翻译器。

不管是解释器还是翻译器，想要正确运行，应用首先都要识别出所有有效的句子、词组、字词组等，识别语言的程序就叫解析器（parser）或语法分析器（syntax analyzer）。

完全 DIY 一个解析器非常麻烦，所以我们需要 ANTLR 的帮助。ANTLR 是一种能写出程序的程序，只需编写 ANTLR 的语法（grammars）文件，描述我们要解析的语言的语法，ANTLR 就能够自动生成用来解析这种语言的解析器。而用来声明我们语言的ANTLR语言的语法，就是元语言（meta-language）。

最基本的解析过程

为了简单起见，我们将解析分为两个阶段，第一阶段是词法分析（lexical analysis），对应的分析程序叫做词法分析器（lexer），负责将符号（token）分组成符号类（token class or token type）。而第二阶段就是真正的语法分析，默认 ANTLR 会构建出一棵语法分析树（parse tree / syntax tree）。下图展示了一个简单的赋值表达式的解析过程：

语法树的叶子是输入的 token，而上级结点是包含其孩子结点的词组名（phase），线性的句子其实是语法树的序列化。最终生成语法树的好处是：

  1. 树形结构易于遍历和处理，并且容易被程序员理解，方便了应用代码做进一步处理。
  2. 多种解释或翻译的应用代码都可以重用一个解析器。但 ANTLR 也支持像传统解析器生成器那样，将应用处理代码直接嵌入到语法中。
  3. 对于因为计算依赖而需要多趟处理的翻译器来说，比起多次调用解析器去解析，遍历语法树多次更加高效。

深入 ANTLR 的解析过程

ANTLR 生成的解析器叫做递归下降语法分析器（recursive-descent parser），属于自顶向下语法分析器（top-down parser）的一种。

顾名思义，递归下降指的就是解析过程是从语法树的根开始，向叶子（token）递归。还是以前面的赋值表达式解析为例，其递归下降语法分析器的代码大概是下面这个样子：

很酷的一点是stat()、assign()、expr()等方法调用所形成的调用栈能与语法分析树的内部节点一一对应。match()的调用对应树的叶子，而assign()方法直接顺序读取输入字符，而不用做任何选择。相比之下，stat()方法要复杂一些，因为在解析时，它需要向前看（lookahead）一些字符才能确认走哪个代码分支，有时甚至要读取完所有输入才能得出预测结果。

虽然 ANTLR 默默地为我们处理了这整个过程，但对这个选择过程有一个基本的了解会使得对生成的解析器进行 debug 变得更加容易。

用语法分析树构建语言应用

在内部，ANTLR 的数据结构会尽可能地共享数据来节约内存。如下图所示，语法分析树的叶子节点指向 token 流中的 token，而 token 中的起止字符索引指向字符流，并不拷贝子字符串。而像空格这种不与任何 token 相关的字符会直接被 Lexer 丢弃掉。

ANTLR 为每条规则都会生成一个 RuleNode，叫做上下文（Context）对象，它会记录根据规则识别词组时产生的所有上下文信息。每一个上下文对象都知道已经识别的短语的起始 token 和结束 token，并且提供了对这些短语的访问。例如，AssignContext提供ID()和expr()方法来访问标识符节点和表达式子树。

语法分析树的 Listener 和 Visitor 机制

ANTLR 在其运行库提供了 Listener 和 Visitor 两种语法分析树遍历机制。

Listener

Listener 的特点是全自动化，我们不必写一个语法分析树的遍历器，ANTLR 会生成一个 ParseTreeWalker 的子类来主导深度优先遍历过程，我们只需处理各种事件就可以了。例如当遍历器遍历到assign规则的节点时，会触发enterAssign()并向其传递AssignContext参数；而当遍历器遍历完assign节点的所有子节点时，触发exitAssign()。下图展示了 ParseTreeWalker 如何进行深度优先遍历：

而下图展示了 ParseTreeWalker 的完整监听器方法调用队列：

Visitor

而 Visitor 则提供了可控的遍历方式，我们可以自行决定是否将子结点作为参数调用visit()方法。

在使用 ANTLR 生成时加上参数-visitor，会生成带有默认实现的 Visitor 实现类。我们不必实现接口中的每一个方法，只需要覆盖我们感兴趣的方法。

动手上路

对应《The Definitive ANTLR 4 Reference》中 Chapter 3 A Starter ANTLR Project。

ANTLR 工具，运行时类库和生成代码

ANTLR 分为两个重要的部分：ANLTR 工具自身和 ANTLR 运行时（runtime） API。运行 ALTLR 工具会生成能够辨认语法所描述语言的句子的代码（词法分析程序和语法分析程序）；而运行时类库提供了生成代码所需的一系列类与方法，例如 Parser, Lexer 和 token。

我们先对一份语法运行 ANTLR，然后借助 jar 包中的运行时类库（runtime classes in the jar）对生成的代码进行编译。最后，编译得到的应用与运行库结合着运行。

《The Definitive ANTLR 4 Reference》（后文可能简写为《Reference》）给出了一份简单的示例，让我们可以快速了解 ANTLR 所需语法的格式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/** Grammers always start with a grammer header. This grammer */
/** is called ArrayInit and must match the filename: ArrayInit.g4 */
grammar ArrayInit;

/** A rule called init that that matches comma-separated values between {...} */
init : '{' value (',' value)* '}' ;  // must match at least one value

/** A value can be either a nested array/struct or a simple integer (INT) */
value : init
      | INT
      ;
      
// parser rules start with lowercase letters, lexer rules with uppercase
INT :  [0-9]+ ;              // Define Token INT as one or more digits
WS  :  [ \t\r\n]+ -> skip ;  // Define whitespace rule, toss it out

之后通过命令行运行antlr4 ArrayInit.g4，ANTLR 为我们生成很多一般需要我们自己手写的文件：

这些文件的功能如下：

  • ArrayInitParser.java：包含了专用于 ArrayInit 语法的解析器（parser）类的定义。
  • ArrayInitLexer.java：包含专用的词法分析程序（lexer）类的定义。
  • ArrayInit.Tokens：对于我们定义的每个 token，ANTLR 分配了一个 token 类型码（token type number）并将这些值保存在 ArrayInit.tokens。因为这个文件的存在，当我们将较大规模的语法分割为各种小型的语法表达时，ANTLR 能够使同种 token 的类型码保持一致。
  • ArrayInitListener.java, ArrayInitBaseListener.java：ANTLR 生成的解释器会默认根据输入构建一棵树。通过遍历这棵树，一个遍历器可以将事件（回调函数）传递给我们提供的监听者对象（listener object）。ArrayInitListener 是描述我们可以实现的回调函数的接口，而ArrayInitBaseListener 是默认空实现的集合，使我们可以方便的重写（override）那些我们感兴趣的回调函数。通过-visitor命令行参数，ANTLR 也可以为我们生成树的 visitors。

测试生成的解析器

之后，我们通过javac *.java来编译 ANTLR 生成的所有代码。UNIX 系统用户可以将以下代码写入.bash_profile或其他启动脚本，以免每次都要在命令行输入一遍：

1
2
3
export CLASSPATH=".:/usr/local/lib/antlr-4.7-complete.jar:$CLASSPATH"
alias antlr4='java -jar /usr/local/lib/antlr-4.7-complete.jar'
alias grun='java org.antlr.v4.gui.TestRig'

之后就可以通过grun命令来测试生成的解析器了。注意输入要以 EOF（Unix 系统 Ctrl + D，Windows 系统 Ctrl + Z）作为结束。加上-tokens命令行参数，输出的每一行会展示一个单独的 token 及其所有信息：

-tree会生成一个 Lisp 风格的简单语法分析树：

而-gui会生成一个展示语法分析树的 GUI 界面：

根据我们定义的语法规则，ANTLR 自动生成了这棵语法分析树。之后我们会利用 ANTLR 内置的遍历器触发enterInit()和enterValue()等各种回调函数。

将生成的解析器集成进 Java 程序

我们来写一个简单的 Java main()方法来集成生成的解析器，并打印出和使用-tree参数一样的语法分析树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// import ANTLR's runtime libraries

import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;

public class Test {
    public static void main(String[] args) throws Exception {
        // create a CharStream that reads from standard input
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        
        // create a lexer that feeds off of input CharStream
        ArrayInitLexer lexer = new ArrayInitLexer(input);
        
        // create a buffer of tokens pulled from the lexer
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        
        // create a parser that feeds off the tokens buffer
        ArrayInitParser parser = new ArrayInitParser(tokens);
        
        ParseTree tree = parser.init();  // begin parsing at init rule
        System.out.println(tree.toStringTree(parser));  // print LISP-style tree
    }
}

测试结果如下。语法错误也可以被报告：

构建语言应用

我们的目标不仅仅是识别，还想做一些翻译工作。最简单的方法是利用 ANTLR 内置的语法分析树遍历器，这样我们不需要自己去进行树遍历，大大减少了工作量。

我们给 ArrayInit 加一个新需求：将 short 数组{99, 3, 451}翻译为字符串\u0063\u0003\u01c3。实现这个需求，我们只需要继承ArrayInitBaseListener，来实现其中的一些监听器方法。

我们在 ShortToUnicodeString.java 中实现我们的监听器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/** Convert short array inits like {1, 2, 3} to "\u0001\u0002\u0003" */
public class ShortToUnicodeString extends ArrayInitBaseListener {
    @Override
    public void enterInit(ArrayInitParser.InitContext ctx) {
        System.out.print('"');
    }
    
    @Override
    public void exitInit(ArrayInitParser.InitContext ctx) {
        System.out.print('"');
    }
    
    @Override
    public void enterValue(ArrayInitParser.ValueContext ctx) {
        int value = Integer.valueOf(ctx.INT().getText());
        System.out.printf("\\u%04x", value);
    }
}

我们不需要覆盖每一个enter/exit方法，只需要实现我们需要的那些。代码里ctx.INT()代表上下文对象请求已经匹配的整数 INT 的值。记住我们之前提到的，上下文对象会记录根据规则识别词组时产生的所有信息。

接下来，我们要创建一个主程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// import ANTLR's runtime libraries

import org.antlr.v4.runtime.*;
import org.antlr.v4.runtime.tree.*;

public class Translate {
    public static void main(String[] args) throws Exception {
        // create a CharStream that reads from standard input
        ANTLRInputStream input = new ANTLRInputStream(System.in);
        
        // create a lexer that feeds off of input CharStream
        ArrayInitLexer lexer = new ArrayInitLexer(input);
        
        // create a buffer of tokens pulled from the lexer
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        
        // create a parser that feeds off the tokens buffer
        ArrayInitParser parser = new ArrayInitParser(tokens);
        
        ParseTree tree = parser.init();  // begin parsing at init rule
        
        // Create a generic parse tree walker that can trigger callbacks
        ParseTreeWalker walker = new ParseTreeWalker();
        
        // Walk the tree created during the parse, trigger callbacks
        walker.walk(new ShortToUnicodeString(), tree);
        System.out.println();
    }
}

比起上一节的主程序，我们多创建了一个树遍历器（ParseTreeWalker walker），并用它来遍历语法分析器返回的语法分析树，它会触发ShortToUnicodeString中的回调方法。

javac 进行编译后就可以使用了：

我们可以通过传入不同的监听器来产生完全不同的输出。监听器将语法和我们的语言应用很大程度上解耦了，使语法具有了更大的重用性。

结语

第一篇笔记到这里就结束了。我们聊了一下我对编译技术的一点看法，并阅读了《The Definitive ANTLR 4 Reference》的前三章。而书的 Part I: Introducing ANTLR and Computer Languages 还剩第四章 A Quick Tour，根据实验课的要求，这一章我会单独写一篇学习笔记，示例与内容也会和书上有一些区别。在这之后我会继续学习解释器构造，并继续写这本书的阅读笔记，敬请期待。

参考资料