从定义到 AST 及其遍历方式，一文带你搞懂 Antlr4
摘要：本文将首先介绍 Antlr4 grammer 的定义方式，如何通过 Antlr4 grammer 生成对应的 AST，以及 Antlr4 的两种 AST 遍历方式：Visitor 方式和 Listener 方式。
1. Antlr4 简单介绍
Antlr4（Another Tool for Language Recognition）是一款基于 Java 开发的开源的语法分析器生成工具，能够根据语法规则文件生成对应的语法分析器，广泛应用于 DSL 构建，语言词法语法解析等领域。现在在非常多的流行的框架中都用使用，例如，在构建特定语言的 AST 方面，CheckStyle 工具，就是基于 Antlr 来解析 Java 的语法结构的（当前 Java Parser 是基于 JavaCC 来解析 Java 文件的，据说有规划在下个版本改用 Antlr 来解析），还有就是广泛应用在 DSL 构建上，著名的 Eclipse Xtext 就有使用 Antlr。
Antlr 可以生成不同 target 的 AST（https://www.antlr.org/downloa...），包括 Java、C++、JS、Python、C#等，可以满足不同语言的开发需求。当前 Antlr 最新稳定版本为 4.9，Antlr4 官方 github 仓库中，已经有数十种语言的 grammer（https://github.com/antlr/grammars-v4，不过虽然这么多语言的规则文法定义都在一个仓库中，但是每种语言的 grammer 的 license 是不一样的，如果要使用，需要参考每种语言自己的语法结构的 license）。
本文将首先介绍 Antlr4 grammer 的定义方式（简单介绍语法结构，并介绍如何基于 IDEA Antlr4 插件进行调试），然后介绍如何通过 Antlr4 grammer 生成对应的 AST，最后介绍 Antlr4 的两种 AST 遍历方式：Visitor 方式和 Listener 方式。
2. Antlr4 规则文法
下面简单介绍一部分 Antlr4 的 g4（grammar）文件的写法（主要参考 Antlr4 官方 wiki：https://github.com/antlr/antl...）。最有效的学习 Antlr4 的规则文法的写法的方法，就是参考已有的规则文法，大家在学习中，可以参考已有语言的文法。而且 Antlr4 已经实现了数十种语言的文法，如果需要自己定义，可以参考和自己的语言最接近的文法来开发。
2.1 Antlr4 规则基本语法和关键字
首先，如果有一点儿 C 或者 Java 基础，对上手 Antlr4 g4 的文法非常快。主要有下面的一些文法结构：
注释：和 Java 的注释完全一致，也可参考 C 的注释，只是增加了 JavaDoc 类型的注释；
标志符：参考 Java 或者 C 的标志符命名规范，针对 Lexer 部分的 Token 名的定义，采用全大写字母的形式，对于 parser rule 命名，推荐首字母小写的驼峰命名；
不区分字符和字符串，都是用单引号引起来的，同时，虽然 Antlr g4 支持 Unicode 编码（即支持中文编码），但是建议大家尽量还有英文；
Action，行为，主要有 @header 和 @members，用来定义一些需要生成到目标代码中的行为，例如，可以通过 @header 设置生成的代码的 package 信息，@members 可以定义额外的一些变量到 Antlr4 语法文件中；
Antlr4 语法中，支持的关键字有：import, fragment, lexer, parser, grammar, returns, locals, throws, catch, finally, mode, options, tokens。
2.2 Antlr4 语法介绍
2.2.1 语法文件的整体结构及写法示例
Antlr4 整体结构如下：
一般如果语法非常复杂，会基于 Lexer 和 Parser 写到两个不同的文件中（例如 Java，可参考：https://github.com/antlr/gram...），如果语法比较简单，可以只写到一个文件中（例如 Lua，可参考：https://github.com/antlr/gram...）。
下面我们结合 Lua.g4 中的一部分语法结构，介绍使用方法。写 Antlr4 的文法，需要依据源码的结构来决定。定义时，依据源码文件的写法，从上到下开始构造语法结构。例如，下面是 Lua.g4 的一部分：
如上语法中，整个文件被表示成一个 chunk，chunk 表示为一个 block 和一个文件结束符（EOF）；block 又被表示为一系列的语句的集合，而每一种语句又有特定的语法结构，包含了特定的表达式、关键字、变量、常量等信息，然后递归表达式的文法组成，变量的写法等，最终全部都归结到 Lexer（Token）上，递归树结束。
上面其实已经可以看到 Antlr4 规则的写法，下面介绍一部分比较重要的规则的写法。
2.2.2 替代标签
首先，如 2.2.1 节的代码所示，stat 可以有非常多的类型，例如变量定义、函数定义、if、while 等，这些都没有进行区分，这样解析出来语法树时，会很不清晰，需要结合很多的标记完成具体语句的识别，这种情况下，我们可以结合替代标签完成区分，如下代码：
通过在语句后面，添加 #替代标签，可以将语句转换为这些替代标签，从而加以区分。
2.2.3 操作符优先级处理
默认情况下，ANTLR 从左到右结合运算符，然而某些像指数群这样的运算符则是从右到左。可以使用选项 assoc 手动指定运算符记号上的相关性。如下面的操作：
^ 表示指数运算，增加 assoc=right，表示该运算符是右结合。
实际上，Antlr4 已经对一些常用的操作符的优先级进行了处理，例如加减乘除等，这些就不需要再特殊处理。
2.2.4 隐藏通道
很多信息，例如注释、空格等，是结果信息生成不需要处理的，但是我们又不适合直接丢弃，安全地忽略掉注释和空格的方法是把这些发送给语法分析器的记号放到一个“隐藏通道”中，语法分析器仅需要调协到单个通道即可。我们可以把任何我们想要的东西传递到其它通道中。在 Lua.g4 中，这类信息的处理如下：
放到 channel(HIDDEN) 中的 Token，不会被语法解析阶段处理，但是可以通过 Token 遍历获取到。
2.2.5 常见词法结构
Antlr4 采用 BNF 范式，用’|’表示分支选项，’*’表示匹配前一个匹配项 0 次或者多次，’+’ 表示匹配前一个匹配项至少一次。下面介绍几种常见的词法举例（均来自 Lua.g4 文件）：
1) 注释信息
2) 数字
3) ID（命名）
3. 基于 IDEA 调试 Antlr4 语法规则（文法可视化）
如果要安装 Antlr4，选择 File -> Settings -> Plugins，然后在搜索框搜索 Antlr 安装即可，可以选择安装搜索出来的最新版本，下图是刚刚安装的 ANTLR v4，版本是 v1.15，支持最新的 Antlr 4.9 版本。
基于 IDEA 调试 Antlr4 语法一般步骤：
1) 创建一个调试工程，并创建一个 g4 文件
这里，我自己测试用 Java 开发，所以创建的是一个 Maven 工程，g4 文件放在了 src/main/resources 目录下，取名 Test.g4
2）写一个简单的语法结构
这里我们参考写一个加减乘除操作的表达式，然后在赋值操作对应的 Rule 上右键，可选择测试：
如上图，expr 表示的是一个乘法操作，所以我们如下测试：
但是，如果改成一个加法操作，则无法识别，只能识别到第一个数字。
这种情况下，就需要继续扩充 expr 的定义，丰富不同的语法，来继续支持其他的语法，如下：
还可以继续扩充其他类型的支持，这样一步步将整个语言的语法都支持完整。这里，我们形成的一个完整的格式如下（表示整形数字的加减乘除）：
4. Antlr4 生成并遍历 AST
4.1 生成源码文件
这一步介绍两种生成解析语法树的两种方法，供参考：
Maven Antlr4 插件自动生成（针对 Java 工程，也可以用于 Gradle）
pom.xml 设置 Antlr4 Maven 插件，可以通过执行 mvn generate-sources 自动生成需要的代码（参考链接： https://www.antlr.org/api/mav...，主要的意义在于，代码入库的时候，不需要再将生成的这些语法文件入库，减少库里面的代码冗余，只包含自己开发的代码，不会有自动生成的代码，也不需要做 clean code 整改），下面是一个示例：
按照上面设置后，只需要执行 mvn generate-sources 即可在 maven 工程中自动生成代码。
命令行方式
主要参考链接（https://www.antlr.org/downloa...），有每种语言的语法配置，我们这里考虑下载 Antlr4 完整 jar：
下载好后（antlr-4.9-complete.jar）,可以使用如下命令来生成需要的信息：
这样就可以生成 Python3 target 的源码，支持的源码可以从上面链接查看，如果不希望生成 Listener，可以添加参数 -no-listener
4.2 访问者模式遍历 Antlr4 语法树
Antlr4 在 AST 遍历时，支持两种设计模式：访问者设计模式 和 监听器模式。
对于 访问者设计模式，我们需要自己定义对 AST 的访问（https://xie.infoq.cn/article/...，这是一篇针对访问者设计模式的介绍，大家可以参考）。下面直接通过代码展示访问者模式在 Antlr4 中使用（基于第 3 章的例子）：
如上，main 方法中，解析出了表达式的 AST 结构，同时在源码中也定义了一个 Visitor：TestVisitor，访问 AddContext，并且打印该加表达式的前后两个表达式，上面例子的输出为：
4.3 监听器模式（观察者模式）
对于监听器模式，就是通过监听某对象，如果该对象上有特定的事件发生，则触发该监听行为执行。比如有个监控（监听器），监控的是大门（事件对象），如果发生了闯门的行为（事件源），则进行报警（触发操作行为）。
在 Antlr4 中，如果使用监听器模式，首先需要开发一个监听器，该监听器可以监听每个 AST 节点（例如表达式、语句等）的不同的行为（例如进入该节点、结束该节点）。在使用时，Antlr4 会对生成的 AST 进行遍历（ParseTreeWalker），如果遍历到某个具体的节点，并且执行了特定行为，就会触发监听器的事件。
监听器方法是没有返回值的（即返回类型是 void）。因此需要一种额外的数据结构（可以通过 Map 或者栈）来存储当次的计算结果，供下一次计算调用。
一般来说，面向程序静态分析时，都是使用访问者模式的，很少使用监听器模式（无法主动控制遍历 AST 的顺序，不方便在不同节点遍历之间传递数据），用法对咱们也不友好，所以本文不介绍监听器模式，如果有兴趣，可以自己搜索测试使用。
5. Antlr4 词法解析和语法解析
这部分实际上，算是 Antlr4 最基础的内容，但是放到最后一部分来讲，有特定的目的，就是探讨一下词法解析和语法解析的界限，以及 Antlr4 的结果的处理。
5.1 Antlr4 执行阶段
如前面的语法定义，分为 Lexer 和 Parser，实际上表示了两个不同的阶段：
词法分析阶段：对应于 Lexer 定义的词法规则，解析结果为一个一个的 Token；
解析阶段：根据词法，构造出来一棵解析树或者语法树。
如下图所示：
5.2 词法解析和语法解析的调和
首先，我们应该有个普遍的认知：语法解析相对于词法解析，会产生更多的开销，所以，应该尽量将某些可能的处理在词法解析阶段完成，减少语法解析阶段的开销，主要下面的这些例子：
合并语言不关心的标记，例如，某些语言（例如 js）不区分 int、double，只有 number，那么在词法解析阶段，就不需要将 int 和 double 区分开，统一合并为一个 number；
空格、注释等信息，对于语法解析并无大的帮助，可以在词法分析阶段剔除掉；
诸如标志符、关键字、字符串和数字这样的常用记号，均应该在词法解析时完成，而不要到语法解析阶段再进行。
但是，这样的操作在节省了语法分析的开销之外，其实对我们也产生了一些影响：
虽然语言不区分类型，例如只有 number，没有 int 和 double 等，但是面向静态代码分析，我们可能需要知道确切的类型来帮助分析特定的缺陷；
虽然注释对代码帮助不大，但是我们有时候也需要解析注释的内容来进行分析，如果无法在语法解析的时候获取，那么就需要遍历 Token，从而导致静态代码分析开销更大等；
…
这样的一些问题该如何处理呢？
5.3 解析树 vs 语法树
大部分的资料中，都把 Antlr4 生成的树状结构，称为解析树或者是语法树，但是，如果我们细究的话，可能说成是解析树更加准确，因为 Antlr4 的结果，只是简单的文法解析，不能称之为语法树（语法树应该是能够体现出来语法特性的信息），如上面的那些问题，就很难在 Antlr4 生成的解析树上获取到。
所以，现在很多工具，基于 Antlr4 进行封装，然后进行了更进一步地处理，从而获取到了更加丰富的语法树，例如 CheckStyle。因此，如果通过 Antlr4 解析语言简单使用，可以直接基于 Antlr4 的结果开发，但是如果要进行更加深入的处理，就需要对 Antlr4 的结果进行更进一步的处理，以更符合我们的使用习惯（例如，Java Parser 格式的 Java 的 AST，Clang 格式的 C/C++的 AST），然后才能更好地在上面进行开发。
本文分享自华为云社区《Antlr4 简明使用教程》，原文作者：maijun 。
版权声明: 本文为 InfoQ 作者【华为云开发者社区】的原创文章。
原文链接:【http://xie.infoq.cn/article/ad6d26e411c4a3f3e6319cc7d】。文章转载请联系作者。
提供全面深入的云计算技术干货 2020.07.14 加入
华为云开发者社区，提供全面深入的云计算前景分析、丰富的技术干货、程序样例，分享华为云前沿资讯动态，方便开发者快速成长与发展，欢迎提问、互动，多方位了解云计算！ 传送门：https://bbs.huaweicloud.com/
评论