Antlr4 如何自动解析得到 AST 而不是 ParseTree

为了开发具有自定义语法的领域特定语言(DSL)，一般我们会使用一个语法解析器生成工具来根据 EBNF 语法定义自动生成 Lexer 和 Parser，从而简化开发工作。

Antlr4 是目前使用最广泛的语法解析器生成工具，它推翻了 Antlr3 中的传统做法，首次强调 g4 语法定义文件应该成为完全独立的语法结构描述，同一份 g4 文件可以用于生成多种语言的实现代码。在 Antlr3 中，一般我们会在 g4 文件中增加大量与特定实现语言（例如 java）相关的 action 代码，导致该语法描述与某种特定的实现语言和某种使用目的绑定。而在 Antlr4 中提倡首先通过 g4 文件生成 ParseTree，然后再通过 Visitor 遍历 ParseTree 来实现其他特化的代码，这样同一份语法描述就可以用于生成多种实现语言的 Parser，并且可以用于编译器、代码格式化、代码重构工具、IDE 语法提示等多种使用目的。

这种做法非常灵活，但是目前从 ParseTree 转换为 ASTNode 的工作必须手工实现，对于比较复杂的 AST 语法树而言，工作量比较大。典型的实现方式可以参见 ShardingSphere 项目中的 SQL 语法树解析代码：MySQLStatementSQLVisitor.java

本文将介绍 Nop Platform 2.0 中所使用的一种技术方案，它基于 g4 描述文件，仅仅增加一些命名约定和元数据设置，即可自动解析得到 AST 语法树，从而极大降低了 AST 重构的成本。基于这一技术，Nop 平台实现了 XScript 语言（类似 TypeScript）和 EQL 语言（类似 Hibernate Query Language）的自动解析，具体配置方式可以参见文末的代码链接。

AST 映射约定

语法解析树(ParseTree)相比于抽象语法树(AST)而言，包含了更多的细节信息，因此理论上说，只要在 ParseTree 上增加一些标注，忽略我们不关心的部分，只保留我们需要的部分即可。具体来说，我们约定了如下的标注规则：

1. 一条解析规则映射为一种 AST 节点

最自然的情况是一条解析规则直接对应于一个抽象语法树节点，解析规则的名称直接对应于抽象语法树节点的类名。例如

sqlDelete    : DELETE FROM tableName=sqlTableName AS? alias=sqlAlias? where=sqlWhere?    ;
class SqlDelete extends SqlStatement {    SqlTableName tableName;    SqlAlias alias;    SqlWhere where;}

sqlDelete 规则直接对应于 SqlDelete 类。antlr 语法允许通过 altLabel 为某个语法元素指定明确的变量名，这一机制正好可以用于标记语法树节点的属性，例 tableName=sqlTableName 表示根据 sqlTableName 规则解析得到 tableName 属性。同时所有没有被 altLabel 标注的部分将被忽略，例如 DELETE 关键字。

2. 解析规则的每个分支映射为一种 AST 节点

一条解析规则也有可能对应多种语法树节点，每个分支都对应一种不同情况，解析得到的对象类型为所有分支对象的基类。例如：

sqlStatement    : sqlSelect    | sqlInsert    | sqlUpdate    | sqlDelete;
abstract class SqlStatement {}
abstract class SqlSelect extends SqlStatement {}
class SqlQuerySelect extends SqlSelect {   ...}
class SqlUpdate extends SqlStatement{   ...}    

sqlStatement 对应于所有分支结果的基类 SqlStatement，每个语法分支解析得到一种特定情况。

如果规则名以 ast_为前缀，则表示解析函数返回的类型为抽象语法树节点的公共基类。例如 XLangParser.g4 文件中，ast_topLevelStatement 规则的返回类型为 XLangASTNode。XLangASTNode 是 XLangAST 中定义的所有抽象语法树节点的公共基类。

3. 多个解析规则或者多个分支映射为同一种 AST 节点

不同的解析规则，或者一条解析规则的不同分支可能对应于同一种抽象语法树节点。例如：

expression_single    : left=expression_single operator=('*' | '/' | '%') right=expression_single    # BinaryExpression_multiplicative    | left=expression_single operator=('+' | '-') right=expression_single        # BinaryExpression_additive    ...;

antlr 依赖于解析规则的顺序来确定运算符优先级，因此同样的 BinaryExpression 会根据 operator 的不同拆分成多个语法分支。这种多条语法规则解析得到同一抽象语法树类型节点的情况很常见，我们可以通过增加后缀名的方式来区分不同的情况。在上面的例子中, BinaryExpression_multiplicative 和 BinaryExpression_additive 规则的解析结果都是 BinaryExpression 类型。同时整个 expression_single 规则本身解析得到的类型为 Expression 类型。

4. 解析规则映射为 AST 节点的属性

有些解析规则不是对应于抽象语法树节点，而是对应于抽象语法树节点的某个属性。例如

assignmentExpression    :  left=leftHandSide operator=assignmentOperator_ right=expression_single eos__        ;
assignmentOperator_    : Assign    | MultiplyAssign    | DivideAssign    | ModulusAssign    | PlusAssign    | MinusAssign    | LeftShiftArithmeticAssign // '<<='    | RightShiftArithmeticAssign //'>>='    | RightShiftLogicalAssign // '>>>='    | BitAndAssign // '&='    | BitXorAssign // '^='    | BitOrAssign // '|='    ;
class AssignmentExpression extends Expression {    XLangOperator operator;    Expression left;    Expression right;}

assignmentOperator_规则解析得到 AssignmentExpression 对象的 operator 属性，类型为 XLangOperator。对于这种不对应于抽象语法树节点的解析规则，我们约定它的名称以_结尾。注意，这也等价于约定所有解析规则，如果后缀名不是_,则它的解析结果必须是抽象语法树节点类型。

5. 解析规则映射为 AST 节点列表

一条解析规则也有可能对应一个 AST 节点列表，例如函数的参数列表或者 SQL 语句中的字段列表等。例如

sqlInsert    : INSERT INTO tableName=sqlTableName LP_ {indent();} columns=columnNames_ { br();} RP_        ( values=sqlValues | select=sqlSelect)    ;
columnNames_    : e=sqlColumnName (COMMA_ e=sqlColumnName)*    ;    

我们约定每个列表都对应一条单独的解析规则，且在这个规则中通过属性 e 来标记列表元素对应的部分。例如 columnNames_规则解析得到 List 类型。

6. 忽略某些语法树节点

有些解析规则的结果可能不对应于抽象语法树的任何部分。例如 Statement 的结束符

eos__    : SemiColon    | EOF    | {this.lineTerminatorAhead()}?    | {this.closeBrace()}?    ;

我们约定以__结尾的规则不参与抽象语法树构建。

7. 简化终端符号的映射

对于终端符号直接对应的抽象语法树映射规则，如果针对每个终端符号都约定一条解析规则，则太过复杂，可以通过 astProp 属性标注来简化。

literaloptions{  astProp=value;}:  StringLiteral  | NumericLiteral;
literal_string:   value = StringLiteral;  

options 是 antlr 内置的一种元数据扩展机制，允许设置自定义的可扩展属性。

注意，在我们的约定中，终端节点不会直接对应于抽象语法树节点，它最多对应抽象语法树节点的一个属性。例如在 literal_string 规则中根据 StringLiteral 这个终端节点解析得到 Literal 节点的 value 属性。

对于多个终端符号都对应于同一种抽象语法树节点的情况，可以统一通过 astProp 选项来指明解析得到的属性名，从而避免针对每种分支情况单独进行指定。

在上面的例子中，literal 的所有分支都必须对应于单个终端符号，它们的解析结果都对应于 Literal 节点的 value 属性。

8. 辅助性规则

有时为了编写上的便利，我们会引入一些辅助性规则。例如

expression_initializer    : '=' expression_single    ;

目前只允许一种辅助规则，就是上例中所展示的，解析规则内部只有一个语法成分最终对应于抽象语法树节点。相当于是在已有抽象语法树规则的基础上增加一些最终没有进入抽象语法树的终端符号。辅助规则解析得到的结果类型与内部规则的解析结果类型相同。

9. 回避命名冲突

由于 antlr 实现层面的限制，它不允许 altLabel 与已经存在的规则名重复。当出现冲突时，可以通过为 altLabel 增加_后缀的方式来回避名称冲突。

arrayBinding    : '[' elements=arrayElementBindings_ (Comma restBinding_=restBinding |Comma)? CloseBracket # ArrayBinding_full    | OpenBracket restBinding_=restBinding Comma? CloseBracket # ArrayBinding_rest    ;

restBinding 本身是解析规则名，它也对应于抽象语法树节点的类名，因此在 arrayBinding 规则中不能使用 restBinding 作为 altLabel 属性名，需要把它替换为 restBinding_。

10. 设置固定的属性值

有时我们希望根据某条解析规则得到 AST 节点时，直接将 AST 节点的某个属性设置为固定值，而不是从 ParseTree 中映射得到属性值。例如

expression_single    :    ...    | <astAssign=computed> object=expression_single '[' property=expression_single CloseBracket     #   MemberExpression_index    | object=expression_single '.' property=identifier_ex               #  MemberExpression_dot    | <astAssign='optional:false'>expr=expression_single {this.notLineTerminator()}? optional='!' # ChainExpression     ...    ;

antlr 中允许通过<name=value>的形式为解析元素增加所谓的 ELEMENT_OPTIONS 元数据。astAssign 是我们增加的一个扩展选项，它的格式为 astAssign='name1:value1,name2:value2'。如果是 boolean 属性，则可以简写为属性名，例如 <astAssign=computed>表示解析得到 AST 节点后，自动设置 astNode.computed=true。

11. 格式化规则

为了实现语法树的格式化输出，可以在 g4 文件的 action 段中增加 indent 和 br 标注。

sqlDelete    : DELETE FROM tableName=sqlTableName AS? alias=sqlAlias?       (<br> where=sqlWhere)?    ;

上面的规则表示在输出 alias 之后，需要回车换行。

目前代码生成器读取 antlr 语法文件时只支持以上几种情况，因此对于第三方编写的 antlr 语法文件需要经过改写后才能与代码生成器集成在一起，直接生成抽象语法树解析器。

需要手工编写的代码

Nop 平台的代码生成器生成的 XXXBuildVisitor 类负责将 Antlr 的 ParseTree 转换为指定的抽象语法树对象，它会要求补充一些解析终端节点的帮助函数。

public class XLangASTBuildVisitor extends _XLangASTBuildVisitor {
    /**     * rules: assignmentExpression     */    public io.nop.xlang.ast.XLangOperator AssignmentExpression_operator(ParseTree node) {        return XLangParseHelper.operator(token(node));    }    ...}    

代码生成器会自动生成 BuildVisitor 框架代码，只需要填写少数几个映射函数即可。例如 assignmentExpression 规则中如何从 ParseTree 的 operator 映射得到 XLangOperator 枚举值。

此外，ASTNode 提供了 normalize 和 validate 函数，通过定制这两个函数，我们在 AST 节点初始化之后可以先根据解析情况规范抽象语法树节点结构（例如填充 AST 节点的缺省部分或者简化 AST 节点结构），然后再验证抽象 AST 节点满足规范定义要求，例如 Identifier 节点自动验证 name 属性不为空等。

自动生成 AST 节点类

使用 Antlr 解析器时，一般 AST 节点类是手工编写的，有一定的工作量。而且一般情况下一个 java 文件对应一个 AST 节点类型，很难让人对 AST 节点树的整体情况有个直观的认识。此外，AST 节点的复制、比较、遍历、转换等操作都是一些模式比较固定的模板代码，手工编写成本较高且容易出现错误。因此我们定义了一种抽象语法树的描述语法，根据这个语法定义直接生成各种 AST 节点类，以及 ASTVisitor/ASTOptimizer/ASTProcessor 等辅助处理类。

import io.nop.api.core.annotations.meta.PropMeta;
public class XLangAST {    enum PropertyKind {        init,        get,        set    }
    abstract class XLangASTNode {
    }
    abstract class Expression {    }
    interface IdentifierOrPattern {
    }
    class Program extends Expression {        String sourceType; //: "script" | "module";
        @PropMeta(mandatory = true)        List<XLangASTNode> body; //: [ Statement | ModuleDeclaration ];    }
    class Identifier extends Expression implements IdentifierOrPattern {        @PropMeta(mandatory = true)        String name;    }    ...}    

我们通过所谓的 xjava 语法来定义 AST 语法树结构。有趣的是，xjava 语法就是普通的 java 语法，我们通过 @PropMeta 注解等可以为它引入额外的描述信息。Nop 平台利用 Janino 库解析 xjava 文件，并将它转换为 ObjMeta 定义，然后再根据 ObjMeta 生成对应的 Java 类。

ObjMeta 是 Nop 平台中定义的一种类似 json schema 的对象元数据规范，它本身存在一种 xml 定义语法。也就是说既可以通过 xml 格式来定义 ObjMeta，也可以使用 xjava 格式来定义 ObjMeta，而且 XML 格式和 xjava 格式可以互相转换。这种同一结构存在多种定义格式的情况，正是可逆计算理论中所强调的多重表象（Representation）的概念。在不同的使用场景中我们可以根据需要选择合适的表象。例如，可视化编辑的时候我们可以选择 XML 格式或者 JSON 格式（Nop 平台中定义了 XML 和 json 的可逆转换规则），而在需要人工查看或者利用 IDE 重构的时候使用 xjava 格式。

如果和 grpc 中使用的 proto 格式做个比较，我们会发现，xjava 也可以用于描述 proto buffer 结构，只要允许通过注解类引入额外的元数据信息即可！

根据可逆计算理论，元数据和数据之间形成一种互补关系。元数据+数据才构成对结构信息的完整描述，而且在一定情况下元数据和数据之间不存在本质性的区别，它们之间可以互相转换。

Structure = 数据1 + 元数据1 = 数据2 + 元数据2

在不同的表象中，如果我们只关注聚光灯下的数据部分，则可能发现它们是不等价的，信息转换存在失真和扭曲的情况。

只有把元数据看作是信息表达的一个必要的、不可或缺的部分，总是将元数据和数据配对作为一个整体来表达，我们才能达到可逆计算理论所要求的可逆性。

按照可逆计算理论的分析，信息在不同的系统之间传递时，也可以被看作是一个表象转换问题。因此，跨系统传递的消息对象一定是 data + header 结构， 我们需要以一种可扩展的方式来保存结构未定的元数据！

在本文所介绍的技术方案中，正是利用了 antlr 内置的可扩展元数据定义，我们才可以实现出乎原作者意图之外的功能。

深层语法 vs. 浅层语法

现代语言理论的祖师爷乔姆斯基在上世纪 50 年代提出了转换-生成语法理论，在语言学领域掀起了所谓的"乔姆斯基革命"。

所谓正则文法、上下文无关文法、上下文相关文法等概念都来自于大名鼎鼎的乔姆斯基层级

乔姆斯基认为，每个句子都有两个结构层次―深层和表层。深层结构“指短语或句子成分之间的内在的语法关系,但这种语法关系不能直接从他们的线形序列上看出来。在生成语法里,指句子的抽象句法表达，它规定所有支配句子应如何解释的因素”，决定句子的意思。表层结构是”指句子的句法表达的最后阶段,是由深层结构转换得来的，是对实际上形成的句子各成分间的关系进行线形排列的结果"，是用于交际中的句子的形式。通过转换-生成语法理论,可以把表面形式不同而意思相同的句子联系起来。例如“Mary cleaned the room”和“The room was cleaned by Mary”，表层结构不同，但深层结构却相同。

简单的说，深层语法决定语义，深层结构通过转换规则转化为浅层结构，浅层语法决定了句子最终的表现形式。同一深层语法可以对应于多种不同的浅层语法。对照这一理论，抽象语法树可以看作是语言的深层结构，而 antlr 语法文件所指定的实际上是一种浅层语法。

如果沿着上述理论进一步思考，既然真正重要的是稳定的领域结构（也就是抽象语法树），那么为什么不规定一个通用的、稳定的抽象语法树表达形式，而彻底放弃不稳定的、格式多样化的浅层语法表达形式呢？这不就是 Lisp 语言吗？

Nop 平台的整体技术战略可以说正是围绕着 AST 节点树结构制定的，只是它选择了 XML 和 JSON 这种更加编辑友好的结构化格式，而不是传统的 Lisp 语法格式。

Nop 平台的设计目标是成为一个通用的领域语言工作台(Domain Specific Language Workbench)，也就是说，它为创建新的领域语言提供了一系列的技术支持，力争将开发新的领域语言的成本降到最低。领域特定语言最重要的部分是它的语义结构（存在哪些领域特有的原子概念，以及这些概念之间如何相互作用），而表观的语法形式其实是一个次要问题。

在 Nop 平台中开发新的领域语言，最基本的要求只有一条：提供一个抽象语法树定义文件。Nop 平台会根据 xdef/xjava/xmeta 等多种形式的抽象语法树定义文件来生成 AST 节点类。这些定义的抽象语法树都自带 XML 表示和 JSON 表示形式，无需编写任何代码即可从 XML/JSON 解析得到 AST，并可以反向将 AST 序列化为 XML/JSON。如果需要一个类似传统程序语言的语法形式，则可以补充定义一个 antlr 语法描述文件。

可逆计算理论并不是一个简单的针对某个特定低代码产品的设计模式，而是一种具有广泛适用性的下一代软件构造理论。在可逆计算的理论框架下，一系列分散的设计实践可以获得统一的理论解释，并很自然的推导出一系列具有内在一致性的可扩展性设计方案。

可逆计算理论的应用范围也绝不限于是单个系统内部，实际上只有当上下游所有软件都遵循可逆计算原理时，我们才可以实现前所未有的粗粒度软件复用。下一篇文章中我将介绍一下可逆计算与 office word 结合实现模板导出的一个技术方案，它通过几百行代码即可提供类似poi-tl的功能，并且免费提供了超越其他技术方案的可扩展性。

参考

关于本文中介绍的 Antlr 自动解析 AST 技术，具体的配置实例可以参见XLangAST.javaXLangParser.g4

EqlAST.javaDMLStatement.g4

基于可逆计算理论设计的低代码平台 NopPlatform 已开源：

• gitee: canonical-entropy/nop-entropy
  

• github: entropy-cloud/nop-entropy
  

• 开发示例：docs/tutorial/tutorial.md
  

• 可逆计算原理和Nop平台介绍及答疑_哔哩哔哩_bilibili