ANTLR改进 — 像使用Tree-sitter一样使用ANTLR

ANTLR（全名：ANother Tool for Language Recognition）是基于LL(*)算法实现的语法解析器生成器（parser generator），用Java语言编写，使用自上而下（top-down）的递归下降LL剖析器方法。

Tree-sitter 是一个解析器生成器工具和增量解析库。它可以为源文件构建具体的语法树，并在编辑源文件时高效地更新语法树。

本文将介绍一种方案在不改动ANTLR源码的基础上，使用ANTLR扩展性生成类似Tree-sitter的结构，像使用Tree-sitter一样使用ANTLR。

• AST生成方面：

• Tree-sitter 生成的AST简洁且合理，没有多余的节点；

• ANTLR 生成的AST较为臃肿，有较多不必要的节点。

• 规则表达能力方面：

• Tree-sitter 使用的LR(1)算法,表达能力较强；

• ANTLR使用LL(*) 算法，不支持间接左递归，表达能力较弱。

• 扩展性：

• Tree-sitter生成c代码用于解析文本AST，灵活性较差，不支持在规则中插入代码或者启用回调；

• ANTLR生成java代码用于解析文本生成AST，灵活性较好，支持在规则中插入代码或启用回调。

以下面Go代码为例，来比较Tree-sitter与ANTLR的AST生成：

Tree-sitter

Tree-sitter有在线平台，可以很方便地看到AST解析的结果。

ANTLR

这里使用IDEA的ANTLR v4插件，选择ANTLR官方维护的Go规则文件，选中词法解析文件，并输入测试代码：

即可得到AST树：

详细的算法原理见文档。

Tree-sitter

LR(1)算法是自底向上算法的一种,也被称作移进 - 规约算法。这种算法相较于LL算法，具有支持语法更多、不需要修改原来语法的左递归等优点。法有两个核心操作，shift和reduce，所谓reduce，就是根据语法规则把右边的式子归成左边的非终结符，shift则不规约，继续展开右边的式子。

例如有以下规则：

S -> E + T; E -> F + G; T -> X + W;

现在有一组token流：

F,G,X,W 

LR算法的第一步通过规则(reduce)：

E -> F + G;

则会新建一个E的节点，并且在token流中消费掉F,G，则token流则变成了：

E,X,W 

通过规则(shift)：

T -> X + W;

则会新建一个T的节点,并且消费X,W,现在token变成了：

E，T

然后通过规则(reduce)：

S -> E + T;

则会新建一个S的节点，并且消费掉E，T：

S

至此结束，得到的AST树为：

S(3)  E(1)    F    G  T(2)    X    W

ANTLR

LL(*) 算法是自顶向下的一种算法。还是有以下规则：

S -> E + T; E -> F + G; T -> X + W;

现在有一组token流

F,G,X,W 

由于是自顶向下的算法，所以我们需要指定顶层规则。如果我们指定S为顶层规则。

新建S节点，根据规则：

S -> E + T;

要解析S就需要先解析E规则。

新建E节点，根据规则：

E -> F + G;

发现F是token类型，不是规则，在token流中匹配F token并吃掉,吃掉后发现E规则，匹配完F token要匹配G token，在token流中匹配G token并吃掉。

现在E规则匹配完毕，返回S规则，发现S规则匹配完E之后，要匹配T规则：

S -> E + T;

新建T节点，根据规则：

T -> X + W;

发现X是token类型，不是规则，在token流中匹配X token并吃掉,吃掉后发现E规则，匹配完X token要匹配W token，在token流中匹配W token并吃掉。

现在T规则匹配完毕，返回S规则，S规则匹配完毕结束。

得到的AST树为：

现在考虑这样一种规则：

S -> E + T; E -> S + G; T -> X + W;

按照上边的逻辑，如果以S为顶层规则，就会发现死循环，这种就叫做左递归，间接左递归。

新建S节点，根据规则：

S -> E + T;

先要匹配E规则，新建E节点，要匹配E规则就要先要匹配S节点，新建S节点：

S -> S + T;

这种规则叫做直接左递归，注意：

S ->  T + S; T -> X + W;

这种不是左递归规则。

Tree-sitter

Tree-sitter生成的C完全基于状态机，并不会区分规则，也没有回调可以调用。

ANTLR

ANTLR可以生成cpp、java、python、csharp多种语言的代码。这里演示使用IDEA的ANTLR v4插件生成java的代码，右键parser的规则,配置ANTLR生成的配置：

可以设置目标语言、包名和输出的文件夹：

右击parser文件生成源码：

可以看到主要包括四个部分：

工作流程如下：

词法分析器

词法解析器的主要作用是将内容切割成token流，以上面的文本为例,大概会切成下面的数据流：

词法解析器的规则名称必须大写，形式如下：

TokenName表示规则名，alternative1表示匹配内容，支持正则，字符串等匹配方式。

例如：

词法分析器以下几种机制

• channel 通道。可以通过规则把token放置在不同通道，默认在在默认通道里面，例如下面的规则：

表示把COMMENT类型的token放到HIDDEN通道中。其作用是后续的词法分析器可以通过通道过滤。例如下面的代码，就是只解析DEFAULT_CHANNEL中的token流。

• fragment 即为内联token，例如下面的规则：

在token流中只有一个token类型即为HEX_FLOAT_LIT。

• mode 模式。规则默认在DEFAULT_MODE模式，使用mode关键字，表示匹配完当前规则，下一个token的规则必须在指定的mode下：

语法分析器

词法分析器的主要作用是将token流构建成AST。词法分析器的规则必须以小写开头。例如：

其中packageClause为规则名， PACKAGE packageName = IDENTIFIER为规则内容，生成内容如下：

可以看到一共生成了两部分：

• 一部分是PackageClauseContext是packageClause规则的节点；

• packageClause函数既是解析packageClause规则的函数。其中enterRule()和exitRule()函数主要是使用/恢复上下文和调用ParserListener的回调。

ParserListener

ParserListener在AST解析过程中调用回调函数，使用方式如下所示：

每一个规则都两个接口函数可以实现。

ParserVisitor

ParserVisitor既是在AST生成好之后调用。

在Tree-sitter中，例如有如下规则：

在代码中可以使用如下代码：

而在ANTLR中,你需要定义下面的等价规则：

生成的代码如下：

可以看到如果你要访问FunctionDeclContext的name，只能使用：

这种方式是不如上面灵活的 解决方法有两种：

• 一种是直接改代码生成的模板，即修改ANTLR的源代码；

• 另外一种是直接利用ANTLR的机制，重载各种类、方法。

我们选择的是第二种方法。对于第一种方法需要了解ANTLR生成代码的原理。

ANTLR生成java代码使用的这个库。

和Django基于模板生成html原理差不多。java代码的生成的模板文件在ANTLR4仓库的toolresourcesorgANTLRv4tooltemplatescodegenJavaJava.stg路径下。实际上每个规则都会映射toolsrcorgANTLRv4codegenmodelRuleFunction.java的一个实例，再通过模板生成对应的代码：

详细原理可以阅读toolsrcorgANTLRv4codegenOutputModelController.java 的buildParserOutputModel函数的相关代码实现。

我们的方法是在规则中指定 contextSuperClass 关键字：

这个关键字的作用是指定上下文的的基类，以上述规则为例，生成后的代码为：

在AST.Node中实现相关方法：

然后创建Symbol类：

那么怎么触发添加field字段呢，首先可以在规则中插入代码来实现field赋值：

生成的代码如下：

现在问题是init函数和FUNCTION_DECL这些变量没有定义该如何定义呢 我们方法是在规则中指定superClass字段，该字段的意思是指定Parser的基类。没有该字段时，GoParser类默认继承ParserBase。

然后在GoParserBase实现变量定义和相关函数：

改进生成的代码：

在之前的比较中，ANTLR生成的AST的较为冗余。我们方法是利用ParserListener在每条规则结束后进行处理，基本的原则是如果这条规则只有一个子节点，则将子节点加到父节点上：

假设有以下规则：

S = E + T; E = F|G; F = H + I; G = M + N; T = X + W;

假设我们指定S为顶层规则，我们有以下token流：

H,I,X,W

按照之前方法生成的AST树为：

可以看到会有E节点冗余。加上我们修改后，在E规则结束，要返回S规则时，会发现E规则只有一个子节点F，此时会将F节点作为S的子节点。生成的AST树为：

这样生成的AST树与Tree-sitter一致。

按道理说LL算法是不支持左递归的这种语法的，在但是ANTLR在代码生成的时候做了改进，支持了直接左递归规则语法，不支持的间接的左递归语法，推测其原因可能是ANTLR的代码生成原理是基于模板的，每个规则都会生成一个函数，而函数与函数之间都是独立的，所以较难支持间接左递归。

我们的方法是将间接左递归规则转换左递归规则：

左递归规则和非左递归规则有不同的模板：

生成的函数也比较复杂：

修改后生成的AST如下：

Tree-sitter AST

本文共有两个部分。第一部分是从三个方面（AST生成、规则表达能力、扩展性）比较Tree-sitter和ANTLR之间的差异。第二部分是对于ANTLR的三个问题（节点访问方式不灵活、AST冗余、以及不支持间接左递归的规则）提出了我们的解决方案，最终实现像使用Tree-sitter一样使用ANTLR的效果。

1. 语法分析的那些算法

2. 掌握StringTemplate的动态文本模版引擎：Java基础应用指南

本作品著作权归pwnht所有

未经作者同意，不得转载