关于java:从定义到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 。

点击关注，第一工夫理解华为云陈腐技术~