ANTLR4 笔记

简介

ANTLR（ANother Tool for Language Recognition）是一个强大的语言识别工具，用于构建语法分析器、解析器和编译器。它能够根据语法规则生成解析器代码，并且能够处理从简单的配置文件到复杂的编程语言的各种语法。

ANTLR 提供了一个功能丰富的工具集，支持多种编程语言，包括 Java、C#、Python、 JavaScript、TypeScript 等，可以在这里查看支持的语言。ANTLR 使用 LL(*) 解析，可以自动构建解析树，并生成监听器（Listener）和访问者（Visitor），支持上下文无关文法（Context-Free Grammar，CFG）。

ANTLR 可以处理直接左递归文法，但是无法处理间接左递归文法，例如：S->A, A->S。

主要特点

  1. 语法规则定义：ANTLR 使用类似于 EBNF（扩展巴科斯范式）的语法规则来定义语言的语法结构。它的语法规则清晰易懂，支持嵌套规则、重复和可选元素等。

  2. 语法分析器生成：基于语法规则，ANTLR 可以生成解析器代码，可以是针对特定目标语言的解析器。生成的解析器可以将输入的文本解析为抽象语法树（Abstract Syntax Tree，AST）或其他形式的语法结构。

  3. 语法分析器动作：ANTLR 支持在语法规则中添加语义动作（semantic action），使用户能够在解析过程中执行自定义的代码逻辑。这样可以将解析和语义处理结合起来。

  4. 错误处理：ANTLR 提供灵活的错误处理机制，可以定义和处理语法错误、警告和诊断信息。它可以生成具有恢复能力的解析器，能够在遇到错误时继续解析输入，并收集错误信息。

  5. 监听器和访问者模式：ANTLR 支持两种处理解析树的模式，即监听器模式（Listener Pattern）和访问者模式（Visitor Pattern）。这些模式使用户能够以不同的方式遍历和处理解析树。

基本概念

基本概念

  1. 词法分析器（Lexer）
    词法分析器里，每个关键字是一个标记（Token），每个标识符是一个 Token，每个操作符是一个 Token，每个标点符号也都是一个 Token。除此之外，还会过滤掉源程序中的注释和空白字符（换行符、空格、制表符等）。

  2. 语法解析器（Parser）
    语法分析会将词法分析出来的 Token 根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程，并转化成有语法含义的抽象语法树结构。

  3. 抽象语法树（Abstract Syntax Tree，AST）
    抽象语法数是源代码语法结构的一种抽象表示，以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。

抽象语法树 AST

监听器和访问器

ANTLR 提供了两种树遍历机制的支持，其实现包含在其运行库中。ANTLR生成的语法分析树 Listener 接口是默认的实现，其中定义了回调方法，用于响应内置树遍历器触发的事件。

Listener 和 Visitor 都采用深度优先算法，并提供了一种简单且标准的方法来处理解析树。这种标准方法可以避免在文法文件中嵌入繁琐的动作，从而将解析与应用逻辑代码分离。这种方法不仅使文法的定义更加简洁清晰，还能够在不重新编译生成语法分析器的情况下复用相同的语法，并且可以采用不同的程序语言来实现这些动作。

Listener 和 Visitor 机制之间最大的区别在于，监听器会使用ANTLR提供的遍历器，通过节点监听，调用对应的 Listener 方法，而 Visitor 方法必须显式地调用 visit 方法来主动遍历其子节点。如果在节点的子节点上忘记调用 visit 方法，那么这些子树将无法被访问。

监听器

ANTLR 提供了 ParseTreeWalker 类，该类可以自动遍历树并生成事件，然后调用监听器。对于每个语法文件，ANTLR 会生成一个 ParseTreeListener 的子类，其中每个规则都有对应的 enter 方法和 exit 方法，这些方法也称为“事件方法”。这些方法的参数是 xxxContext，提供了该方法所需的所有信息。监听器的操作逻辑可以在这些 enter 和 exit 方法中添加。下图展示了 ParseTreeWalker 对监听器方法的完整调用顺序。

监听器

访问器

有时候我们希望手动控制遍历树的过程，并通过显式调用方法来访问子节点。通过在命令行中添加 -visitor 选项，可以指示 ANTLR 为语法生成访问器接口，其中每个规则对应于接口中的一个 visit 方法。ANTLR 提供了访问器接口和一个默认实现类，这样只需要覆盖接口中需要重写的方法即可。

访问器

ANTLR 案例

下面的案例将通过一个简单的例子，讲解如何使用访问器（Visitor）对输入的表达式进行加减乘除的运算，例子将使用 Java 的 Decimal 类对数字进行运算。

案例中源代码可以在 GitHub 上获得：antlr-demo

定义 DSL 语法

创建Expression.g4文件，其中定义了语法和 Token。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 定义了 grammar 的名字，名字需要与文件名对应
grammar Expression;
@header {
// 定义package
package org.example.parser;
}

/**
 * parser
 * calc 和 expr 就是定义的语法，会使用到下方定义的词法
 * 注意 # 后面的名字，是可以在后续访问和处理的时候使用的。
 * 一个语法有多种规则的时候可以使用 | 来进行配置。
 */

calc
  : expr EOF                                    # calculationBlock
  ;
// 四则运算分为了两个非常相似的语句，这样做的原因是为了实现优先级，乘除是优先级高于加减的。
expr
  : BR_OPEN expr BR_CLOSE                                    # expressionWithBr
  | sign=(PLUS|MINUS)? num=(NUMBER|PERCENT_NUMBER)           # expressionNumeric
  | expr op=(TIMES | DIVIDE) expr                            # expressionTimesOrDivide
  | expr op=(PLUS | MINUS) expr                              # expressionPlusOrMinus
  ;

/**
 * lexer
 */

BR_OPEN:   '(';
BR_CLOSE:  ')';
PLUS:      '+';
MINUS:     '-';
TIMES:     '*';
DIVIDE:    '/';
POW:       '^';
PERCENT:   '%';
POINT:     '.';

// 定义百分数
PERCENT_NUMBER
  : NUMBER ((' ')? PERCENT)
  ;

NUMBER
  : DIGIT+ ( POINT DIGIT+ )?
  ;

DIGIT
  : [0-9]+
  ;

// 定义了空白字符，后面的 skip 是一个特殊的标记，标记空白字符会被忽略
SPACE
  : ' ' -> skip
  ;

生成 Visitor 文件

执行下面的命令，让 ANTLR 生成 Visitor 接口及其默认实现，其中 -o 参数指明输出文件的位置，-vistor 表明需要生成 Visitor 接口，-no-listener 则是表明不需要默认生成的 Listener 相关的代码。

1
antlr4 -o src/main/java/org/example/parser -visitor -no-listener Expression.g4

实现计算逻辑

接下来我们需要重写 ANTLR 生成的方法，对输入的数字进行运算。首先新建一个类BigDecimalExpressionVisitor，需要继承 ANTLR 生成的ExpressionBaseVisitor。

下面的代码将简单展示对加法和减法进行重写，使其支持通过 Decimal 计算出结果。详细的代码和文件可以在GitHub 上获得。

1
2
3
4
5
6
7
8
9
10
11
12
13
@Override
public BigDecimal visitExpressionPlusOrMinus(ExpressionParser.ExpressionPlusOrMinusContext ctx) {
    BigDecimal left = visit(ctx.expr(0));
    BigDecimal right = visit(ctx.expr(1));
    switch (ctx.op.getType()) {
        case ExpressionLexer.PLUS:
        return left.add(right, MATH_CONTEXT);
        case ExpressionLexer.MINUS:
        return left.subtract(right, MATH_CONTEXT);
        default:
        throw new RuntimeException("unsupported operator type");
    }
}

调用代码

当我们写好计算逻辑后，就可以进行调用了，这里通过 Calculator 的 execute 方法进行调用。代码如下：

1
2
3
4
5
6
7
8
9
10
11
public class Calculator {
  public BigDecimal execute(String expression) {
    CharStream cs = CharStreams.fromString(expression);
    ExpressionLexer lexer = new ExpressionLexer(cs);
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    ExpressionParser parser = new ExpressionParser(tokens);
    ExpressionParser.CalcContext context = parser.calc();
    BigDecimalExpressionVisitor visitor = new BigDecimalExpressionVisitor();
    return visitor.visit(context);
  }
}

当我们输入 1+2 时，就可以得到 3 作为结果。

1
2
3
4
String expression = "1+2";
Calculator calculator = new Calculator();
System.out.println(calculator.execute(expression));
// output: 3

后记

ANTLR 还有很多高级用法，比如 Channel、内嵌代码等，这里就不做介绍了，各位有兴趣可以自行了解。

ANTLR4 笔记
https://slw.im/2023/09/antlr4-notes/
作者
Ryo Shen
发布于
2023年9月3日
许可协议