antlr介绍

本文结合案例介绍antlr的名词和原理

前言

antlr4(Another Tool for Language Recognition),是一款语法解析工具,可以通过语法模板的方式将字符串解析成语法树。并且提供自动生成的代码来自定义分析。Hive和Sprk的sql解析都使用了antlr4方案。

antlr 术语

首先整个antlr的语法树由两部分组成,RuleTerminalRule可以被作为一级节点被访问到,而Terminal只能通过Rule来访问。

  • lexer
    词法解析,把字符串按类分组,构建出token集合。

  • parser
    语法解析,将token流以树形结构展现出来,方便使用者自定义分析。

  • token
    可以理解为被词法解析后,分组后的单词符号。在语法树中是Terminal实体的存在。

  • rule
    规则节点,在g4文件中以小写字母表示,并且声明了一系列语法结构。

  • terminal
    终止节点,在g4文件中以大写字母表示,是树的叶子节点。

  • ATN
    Augmented Transition Network

Listener & Visitors

antlr提供了两种遍历语法树的方式,监听者模式和访问者模式。

  • Listener
    监听者模式相对简单,antlr会先序遍历整颗树,然后将对应的节点和事件回调监听器。你无法改变他的遍历顺序,只能被动接受。如果你想自定义遍历语法树的顺序,那么可以用访问者模式。

  • Visitor
    访问者模式,可以让用户可以选择性的主动遍历树,从而控制遍历的顺序。

解析流程

  1. 词法解析,将字符串解析出token集合
  2. 语法解析,将token集合转换成语法树
  3. 使用监听者或者访问者模式来遍历语法树

g4文件结构

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
// 文件头,必须和文件名保持一致
grammar xxx;

// 生成的文件头,antlr会直接把这些字符串写在生成的文件的上方
@header {
// class header
package com.xxx;

import java.util.xxx;
}

// members, 类内代码,antlr会直接把这些字符串写入生成的类里面
@members {
int i = 0;
public int get() {
return i;
}
}

// rules 各种规则
expr
: expr * expr
| INT
;

// 叶子节点
INT: [0-9]+ ;

## fragment
// 片段,是其他token的组成部分,不会成为独立的token,方便在g4文件中做抽象
fragment xxx;

// skip & channel(HIDDEN)
// 这两个关键字都可以跳过解析的功能
COMMENT: '--' ~[\r\n]* '\r'? '\n' -> channel(HIDDEN)
COMMENT: '--' ~[\r\n]* '\r'? '\n' -> skip

案例

计算器案例

下面通过一个基于访问者模式的计算器案例来说明antlr4的工作流程。

  1. 定义一个xxx.g4文件
  2. 通过g4文件生成代码;如果是maven可以通过antlr的插件antlr4-maven-plugin,再执行命令mvn antlr4:antlr4
  3. 自定义visitor来遍历语法树
  4. main启动代码

Expr.g4

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
grammar Expr;

// @header 内的字符串会直接输出到生成的文件,因此我们可以在这里指定包名
@header {
package ulysses.demo.antlr.expr;
}

prog
: expr* NEWLINE*
;

// # 不是注释,而是打标签,可以使生成的类中增加对该表达式的访问
// antlr默认,定义在前面的规则优先匹配,因此乘和除的优先级大于加和减
expr: expr (MUL|DIV) expr # mulDiv
| expr (ADD|SUB) expr # addSub
| INT # lit
;


NEWLINE : [\r\n]+ ;
INT : [0-9]+ ;

MUL:
'*'
;
DIV:
'/'
;

ADD:
'+'
;
SUB:
'-'
;

CustomVisitor.java

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
public class CustomVisitor extends ExprBaseVisitor<Double> {

@Override
public Double visitLit(ExprParser.LitContext ctx) {
// 这里只会访问到数字,将数字转换为double类型
return Double.parseDouble(ctx.INT().getText());
}

@Override
public Double visitAddSub(ExprParser.AddSubContext ctx) {
// 递归访问子表达式计算出left和right
double left = visit(ctx.expr(0));
double right = visit(ctx.expr(1));

// 判断token类型 进行计算
if (ctx.ADD() != null) {
return left + right;
} else {
return left - right;
}
}

@Override
public Double visitMulDiv(ExprParser.MulDivContext ctx) {
double left = visit(ctx.expr(0));
double right = visit(ctx.expr(1));

if (ctx.MUL() != null) {
return left * right;
} else {
return left / right;
}
}
}

Main.java

1
2
3
4
5
6
7
8
9
10
11
12
13
String expr = "1*2+3-4/5";
// 将字符串喂给词法解析器
ExprLexer lexer = new ExprLexer(CharStreams.fromString(expr));
// 通过词法解析器生成token
CommonTokenStream tokens = new CommonTokenStream(lexer);
// 把token构建成语法树
ExprParser parser = new ExprParser(tokens);
ParseTree tree = parser.prog();
// 自定义访问者 修改遍历树的逻辑 模拟出计算器的效果
CustomVisitor eval = new CustomVisitor();
double res = eval.visit(tree);
// 输出结果4.2
System.out.println(res);

json解析案例

Json.g4文件

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
grammar Json;

@header {
package ulysses.demo.antlr.expr;
}


json
: object
| array
;

object
: '{' pair (',' pair)* '}'
| '{' '}' // empty json object
;

array
: '[' ']'
| '[' value (',' value)* ']'
;


pair
: STRING ':' value
;

value
: STRING
| NUMBER
| 'true' | 'false'
| 'null'
| object
| array
;

STRING: '"' ~["\\]* '"' ;

NUMBER: [1-9]+ [0-9]* ;

WS: [ \t\n\r]+ -> skip ;

1
2
// 测试数据
{"key1":"value1", "key2":{"subkey2":"subvalue2"}}

语法树效果图如下
语法树效果图

参考资料

《The Definitive ANTLR 4 Reference.pdf》

ulysses wechat
订阅+