摘要：本文将首先介绍 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。
点击关注，第一工夫理解华为云陈腐技术~