ANTLR 4进阶

ANTLR(Another Tool for Language Recognition)是一个开源的语法分析器生成工具。语法分析器生成工具可以根据特殊的领域语言生成语法分析器,解决了手写分析器复杂耗时的问题。

因为平时的开发工作中需要做语法分析的情况很少,所以知道ANTLR的人并不多。但我们今天用到的很多流行的应用和开源项目里边都有它的影子。Twitter使用ANTLR来解析其搜索服务的查询语句,每天处理超过20亿次查询。Java领域最流行的ORM框架Hibernate使用它将HQL翻译成SQL。Hadoop、Hive以及Pig都使用ANTLR来做语法分析。

ANTLR的作者是旧金山大学的教授Terence Parr,他从1989年还在上学的时候就开始做这个项目,一直到他自认满意的ANTLR 4发布,前后用了25年的时间。ANTLR 4可以生成ALL(*)语法分析器,ALL(*)比传统的LL(*)分析算法有多项重要的改进,有些时候,使用ANTLR生成的解析器要比官方的手写解析器速度更快。比如使用ANTLR解析大量的Java源文件,在不生成语法树的情况下,比手写的javac分析器更快。

我是从ANTLR 2开始使用的,当时做了一个小工具,可以分析Java的源代码,自动生成注释。Java语法描述文件在ANTLR的语法仓库可以下载到,只需要把业务代码插入语法描述文件的相应位置就可以了,花几个小时做的小工具节省了整个项目组大量的时间。最近做的项目用ANTLR 4来解析查询语句并调用Elastic Search的接口进行搜索,语法文件只有几十行,却可以支持模糊搜索,短语搜索,区间搜索,布尔表达式与括号分组。

这几天得闲重读了Terence Parr写的《The Definitive ANTLR 4 Reference》以及相关的论文,并与其他流行的语法分析器生成工具做了简单的对比,总结了我对ANTLR的ALL(*)语法解析器的理解以及一些解决常见语法分析问题的最佳实践。

语法分析器

语法分析器的工作可以分解为两个步骤:第一步是词法分析(lexical analysis),读取字符流,将字符聚集为单词或者符号(Token),并标记每一个符号的类别。比如一条赋值语句a = 20;,词法分析之后的结果为a=20;四个符号,并标记a为ID,20为INT数值等。第二步是语法分析(syntax analysis),语法分析通过解析词法分析生成的符号来识别语句结构,它一般不在乎符号的内容,只关心它们的类型。上边的语句经过语法分析后,就会得出这是赋值语句的结论。

语法分析器的工作就像是走迷宫,只有一个入口和一个出口,迷宫的地板上写着词法分析器分析而得的符号,不同路径上的符号序列组成不同的语句,而从入口到出口的符号序列组成的语句就是合法的输入。

ALL(*)语法分析器

LR(*)与LL(*)

现在主流的语法分析器分两大阵营,LR(*)与LL(*)。

LR是自低向上(bottom-up)的语法分析方法,其中的L表示分析器从左(Left)至右单向读取每行文本,R表示最右派生(Rightmost derivation),可以生成LR语法分析器的工具有YACC、Bison等,它们生成的是增强版的LR,叫做LALR

LL是自顶向下(top-down)的语法分析方法,其中的第一个L表示分析器从左(Left)至右单向读取每行文本,第二个L表示最左派生(Leftmost derivation),ANTLR生成的就是LL分析器。

两类分析器各有其优势,适用不同的场景,很难说谁要更好一些。普遍的说法是LR可以解析的语法形式更多,LL的语法定义更简单易懂。

ALL(*)原理

ANTLR从4.0开始生成的是ALL(*)解析器,其中A是自适应(Adaptive)的意思。ALL(*)解析器是由Terence Parr、Sam Harwell与Kathleen Fisher共同研发的,对传统的LL(*)解析器有很大的改进,ANTLR是目前唯一可以生成ALL(*)解析器的工具。

ALL(*)改进了传统LL(*)的前瞻算法。其在碰到多个可选分支的时候,会为每一个分支运行一个子解析器,每一个子解析器都有自己的DFA(deterministic finite automata,确定性有限态机器),这些子解析器以伪并行(pseudo-parallel)的方式探索所有可能的路径,当某一个子解析器完成匹配之后,它走过的路径就会被选定,而其他的子解析器会被杀死,本次决策完成。也就是说,ALL(*)解析器会在运行时反复的扫描输入,这是一个牺牲计算资源换取更强解析能力的算法。在最坏的情况下,这个算法的复杂度为O(n4),它帮助ANTLR在解决歧义与分支决策的时候更加智能。

DFA缓存

ALL(*)解析器对这种反复扫描的工作方式进行了优化,引入了DFA缓存机制。DFA缓存记录了前瞻的输入与决策结果的映射,在未来进行决策时,可以先在缓存中尝试匹配相同的路径,而不需要重复进行复杂而耗时的分支遍历工作。在实际工作中,DFA缓存有很高的命中率,对性能有巨大提升。在对3.2M的Java文件进行解析的测试中,关闭DFA缓存的分析时间为42.5s,而打开DFA缓存的分析时间只有203ms。使用DFA缓存,可以让解析算法的复杂度降低到接近线性。

两阶段的ALL(*)分析

ALL(*)还包含了另一个分析策略,叫做SLLStrong LL)。它与ANTLR 3的策略相似,但是去掉了回溯,虽然名字里有Strong,但是功能不如LL(*)分析器强大,优点是速度很快。当SLL解析失败了,说明有可能是语法错误,也可能是SLL的能力有限,这个时候就会切换到全功能模式。自动两阶段分析功能需要调用parser.getInterpreter().setSLL(true)手动打开。打开SLL两阶段解析的ALL(*)解析器,在解析123M的Java文件测试中,速度快了8倍。

左递归

左递归是指在某个备选分支的最左侧以直接或间接的方式调用了自身

1
2
3
4
5
expr : expr '*' expr // 直接的左递归
| addExpr // 间接的左递归
;
addExpr : expr '+' expr ;

传统的LL语法分析器一般是无法处理左递归的。ANTLR 4通过透明的将左递归替换为一个判定循环(predicated loop)而允许在LL语法描述中使用左递归。它能够处理直接的左递归,但是不能处理间接的左递归。间接的左递归在一般的语法描述中非常少见。

ANTLR支持的直接左递归有四种:

  • 二元,如expr op exprexpr (op1 | op2 | ... | opN) expr
  • 三元,如expr '?' expr ':' expr
  • 一元前缀,即把任意元素的尾递归视做一元前缀,如'(' type ')' expr('+' | '-' | '++' | '--') expr
  • 一元后缀,如expr '.' identifier

允许左递归可以极大的简化语法文件,比如使用支持左递归的ANTLR 4重写的Java语法只有91行,而之前的版本则有172行。

性能

ALL(*)的论文中作者提供了一个ANTLR 4与其他一些语法分析器的性能对比。测试环境是6核3.33Ghz CPU,16GB内存,安装了OS X 10.7与Java 7的苹果电脑。测试数据是12,920个Java库的源文件,共123MB。下边是测试的结果:

performance_comparison_01.jpeg

图中标有号是指生成语法树。

下边是对单个3.2MB的大尺寸Java源文件的解析测试,算是比较极端的情况,很多分析器的表现非常不稳定:

Tool Time RAM (M)
Javac† 89 ms 7
ANTLR4 201 ms 8
JavaCC 206 ms 7
ANTLR4† 360 ms 8
ANTLR3 1048 ms 143
SableCC† 1,174 ms 201
Rats!† 1,365 ms 22
JSGLR† 15.4 ms 1,030
Rascal† 24.9 ms 2,622
(no DFA) ANTLR4 42.5 ms 27
elkhound 3.35 min 3
DParser† 10.5 hours 100+
elkhound† out of mem 5390

下表是ANTLR 4对不同语言的处理速度的测试:

Grammar KB/sec
XML 45,993
Java 24,972
JSON 17,696
DOT 16,152
Lua 5,698
C 4,238
Verilog2001 1,994
Erlang 751

语法的设计与实现

ANTLR生成的分析器是自顶向下(top-down)的,所以在对语法进行设计时也推荐使用自顶向下的方式,这种分析方式比自底向上的方式更贴近人类的思维和表达方式。

举个例子,假如有人问你什么是CSV文件,你大概会做如下解释:CSV是一种文件(file)格式,一个CSV文件包含了很多行(row),每一行又包含了多个由逗号分割的字段(field),每个段可以是字符串也可以是数字,字符串需要用双引号包裹起来。

可以把上边的描述用伪代码表示如下:

1
2
3
file : <<sequence of rows that are terminated by newlines>> ;
row : <<sequence of fields separated by commas>> ;
field : <<number or string>> ;

接下来,只需要将描述替换成ANTLR的领域语言即可:

1
2
3
4
5
6
7
8
9
10
11
file : (row '\n')* ;
row : field (',' field)* ;
field : NUMBER
| STRING
;
NUMBER : '0' .. '9'+ ;
STRING : '"' .*? '"' ;

解决歧义

优先级

最常见的歧义应该就是优先级带来的歧义问题。

形如5 + 8 * 2这样的输入有两种匹配:5 + 8之后再乘2,或是8 * 2之后再加5,从数理上说后者是正确的解析方式。大多数的语法工具如Bison,使用额外的标记来指定运算符优先级。而ANTLR会优先选择位置更靠前的备选分支来隐式的解决这类歧义:

1
2
3
expr : expr '*' expr // 乘法运算写在前边,会被优先匹配
| expr '+' expr
;

右结合

如指数运算2 ^ 5 ^ 7是右结合的,需要先计算5 ^ 7,可以使用assoc选项来指定结合性:

1
2
3
expr : expr '^'<assoc=right> expr // 指定右结合
| INT
;

非保留关键字

很多编程语言中,关键字是被保留的,不能用来命名变量。但是也有一些语言允许使用关键字来命名变量,比如Fortran。这种情况会给词法分析带来歧义,但是语法分析可以通过关联前后的符号进行正确的决策,因此使用语法定义代替词法定义就可以解决这个问题。下边以一种只有一个关键字var,并允许使用关键字来命名变量的语言为例:

1
2
3
assign : 'var' id ;
id : 'var' | ID ; // 使用一个语法定义显式指明可以用作命名的关键字
ID : [a-z]+ ;

使用语义判定根据上下文剪枝

有一些歧义是上下文相关的,比如在Ruby语言中方法调用的括号是可以省略的,所以当我们看到a = b这样的语句时,如果不结合上下文,你并不知道,b是变量还是方法。解决这个歧义其实已经不是上下文无关的语法分析器的工作了,因为它缺少解决这个歧义所需要的信息。处理这一类的歧义,需要将这部分信息的处理逻辑硬编码到ANTLR的语义文件中并配合语义判定来实现。下边使用一个简化的语法为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 这部分内容会被插入到生成的GrammarParser文件的头部
@parser::header {
import java.util.Set;
import java.util.HashSet;
}
// 这部分内容会被插入到生成的GrammarParser文件的类定义中
@parser::members {
Set<String> funcs = new HashSet<String>();
void addFunction(String name) { funcs.add(name); };
boolean isFunction(String name) { return funcs.contains(name); };
}
funcDef : 'def' id=ID { addFunction($id.text); } // 当出现方法定义时,将方法名保存下来
;
assign : {!isFunction($id.text)}? ID '=' id=ID // 是方法定义时,此分枝会被忽略
| {isFunction($funcCall.text)}? ID '=' funcCall // 不是方法定义时,此分枝会被忽略
;
funcCall : ID
| ID '(' ')'
;

最佳实践

非贪婪匹配与转义符

很多开发语言都支持多行注释,比如Java或C指定在/**/之间的任意字符都是注释的内容。ANTLR默认使用贪婪匹配的原则,如果一个文件内有多块注释,那么从第一个/*一直到最后一个*/之间的所有内容都会被匹配为注释内容。所以对于这类的语法定义需要使用非贪婪匹配:

1
comment : '/*' .*? '*/'; // *?表示非贪婪匹配

但对于有转义符的情况,要慎用非贪婪匹配。比如在CSV文件中,一个值可以是被双引号包裹的字符串,同时双引号又做为转义符,两个连续的双引号表示值内的双引号,如果使用非贪婪匹配,ANTLR在读到连续双引号的第一个时就会判定当前词法符号结束,所以需要使用子规则枚举每一种可能情况:

1
2
field : '"' ('""' | ~'"')* '"'; // 这里('""' | ~'"')*是一个子规则,表示可以包含两个连续的双引号或者除双引号以外的任意字符

将词法符号送入不同通道

ANTLR支持在词法分析阶段将词法符号放到不同的通道,除了默认通道,其他自定义的通道都是隐藏的,对语法分析不可见。比如,分析并运行Java文件的应用并不关心文件里的空白字符和注释,这些不关心的内容可以放入丢弃通道,接下来的语法分析会忽略这部分内容,加快分析的速度。把某种语言翻译成另一种语言的应用,如果两种语言有一部分相同的语法,可以把这部分内容送入单独的通道,略过语法分析,在最后的翻译应用中再取出复制。下边是对内置丢弃通道skip通道与自定义通道的使用示例:

1
2
3
4
5
6
7
@lexer::members {
public static final int COMMENTS = 1; // 非ANTLR内置的通道需要定义
}
COMMENT : '\\' .*? '\n' -> channel(COMMENTS) ; // 将注释放入COMMENTS通道
WS : [ \t\n\r]+ -> skip ; // 将空白字符放入skip通道,skip通道是ANTLR内置的通道,传入的符号将被丢弃

处理同一文件中的不同格式

有一些语言,其结构化的区域被随机文本所包围,被称为孤岛语言(island language)。比如XML或HTML,<>之内包裹的部分是结构化的标签,而外部则是大片我们不关心的文本。处理这一类语言就需要用到语法模式。下边以一个简化的XML语法为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
file : (tag | TEXT)* ;
tag : '<' ID '>'
| '<' '/' ID '>'
;
OPEN : '<' -> mode(TAG) ; // 切换到TAG模式
TEXT : ~'<'+ ;
mode TAG; // 从此处向下的部分为TAG模式的词法
CLOSE : '>' -> mode(DEFAULT_MODE) ; // 返回默认模式
SLASH : '/' ;
ID : [a-zA-Z]+ ;

处理不同的语法版本

在开发语言升级时有时会引入一些新的特性,比如Java 5之后加入了枚举类型enum。有时一个语言可能会派生出多种方言,比如每个关系数据库都会有一些自己的SQL方言。如果对于差别不大的不同语言版本或者方言都创建单独的语法定义文件,违反了DRY的原则,会给以后的维护工作带来不便。这时可以使用语义判定来实现运行时选择性的打开一些分枝,下边以Java的枚举类型为例:

1
2
3
4
5
6
7
8
9
10
@parser::members {
public static boolean java5 = false;
}
// 运行时会根据静态变量java5的值而选择打开或关闭分枝
enumDecl : {java5}? 'enum' id '{' id (',' id)* '}' ;
id : ID
| {!java5}? 'enum' // 对变量命名中enum的合法性做相反的语义判定,在java5之前使用enum为变量命名是合法的
;

运行时API

ANTLR是一个语法分析器生成工具,最终的目的还是要生成目标开发语言的语法分析器。目前ANTLR支持的目标语言有:Java、JavaScript、CPP、C#、Python、Go、Swift。也可以继承org.antlr.v4.codegen.target.Target类,添加对新目标语言的支持。

同时,生成的语法分析器还需要依赖ANTLR运行时库才可以工作,比如Java依赖antlr4-runtime库,JavaScript依赖antlr4库。不同语言的运行时库的用法大同小异,下边以Java为例。

监听器(Listener)与访问者(Visitor)

在ANTLR 4以前,有两种开发方式:一是将目标语言的代码直接硬编码到语法定义文件中,在生成分析器时会插入这些代码到生成文件中,这也是大多数语法分析器生成工具的做法。在上边的语法判定与通道的例子中,就有将Java代码硬编码到语法定义的情况。将目标代码和语法定义耦合在了一起,当需要生成不同目标语言的分析器时,就需要维护多份语法定义文件,增加了维护成本,同时在编写复杂逻辑时,由于IDE没有对目标语言的支持,开发和测试都很幸苦。另一种方式是让ANTLR生成语法分析树,然后写程序遍历语法树,对语法树的遍历是一个很复杂的工作。

ANTLR 4开始会生成监听器(Listener)与访问者(Visitor),将语法定义与目标代码完全的解耦。监听器可以被动的接受语法分析树遍历的事件,对于每一个语法节点,都会生成进入enterSomeNodeName与退出exitSomeNodeName两个方法。访问者机制生成对语法节点的访问方法visitSomeNodeName,在访问方法中需要手动调用visit方法来对子节点进行遍历,使用访问者模式可以控制语法树的遍历,略过某些的分枝。ANTLR默认只生成监听器,生成访问者类需要在生成时添加-visitor选项。

标注备选分枝

ANTLR对于多个备选分支只会生成同一个处理方法,这样就需要在目标代码中自行做判断,增加了代码的复杂度。对于这种情况,可以使用标注功能让ANTLR为每一个分支单独生成处理方法:

1
2
3
4
expr : expr '*' expr # Mult // 生成enterMult与exitMult方法
| expr '+' expr # Add // 生成enterAdd与exitAdd方法
| INT # Int // 生成enterInt与exitInt方法
;

在上边的例子中,如果不做标注,则ANTLR只会生成enterExprexitExpr方法,需要在方法内手动判断分支。

重写输入流

有些应用的目的是在代码的某个位置插入内容,或是修改某个词法符号,比如在Java源代码类成员的最上边插入serialVersionUID。这时可以使用TokenStreamRewriter对输入的词法符号流进行重写。下边是插入serialVersionUID的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class InsertSerialIDListener extends JavaBaseListener {
private final TokenStreamRewriter rewriter;
public InsertSerialIDListener(TokenStream tokens) {
rewriter = new TokenStreamRewriter(tokens);
}
@Override
public void enterClassBody(JavaParser.ClassBodyContext ctx) {
String field = "\n\tpublic static final long serialVersionUID = 1L;";
// 进入对象体定义,在还没有访问子符号前,插入serialVersionUID定义
rewriter.insertAfter(ctx.start, field);
}
}

从隐藏通道中取出词法符号

之前提到了可以将语法符号送入不同的通道绕过语法分析,加快分析的速度。这些被送入隐藏通道的符号仍然可以从符号流中被获取到。下边以获取注释通道的语法符号为例:

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
public class CommentShifter extends CymbolBaseListener {
private final BufferedTokenStream tokens;
private final TokenStreamRewriter rewriter;
public CommentShifter(BufferedTokenStream tokens) {
this.tokens = tokens;
this.rewriter = new TokenStreamRewriter(tokens);
}
@Override
public void exitVarDecl(CymbolParser.VarDeclContext ctx) {
Token semi = ctx.getStop();
int i = semi.getTokenIndex();
// 每一个符号在被送入不同通道前都会被编号
// 这里获取注释通道在当前符号后边的符号(编号比当前符号编号大),一直获取到下一个在默认通道中出现的符号之前
// 如果第二个参数传入-1,则表示所有隐藏通道
List<Token> cmtChannel = tokens.getHiddenTokensToRight(i, CymbolLexer.COMMENTS);
if ( cmtChannel != null ) {
Token cmt = cmtChannel.get(0);
String txt = cmt.getText().substring(2);
// 改写注释格式
String newCmt = "/* " + txt.trim() + " */\n";
// 将改写的注释插入重写流
rewriter.insertBefore(ctx.start, newCmt);
// 将原注释替换成换行符(删除原注释)
rewriter.replace(cmt, "\n");
}
}
}

使用语法错误异常做补全

当输入内容出现问题时,如输入的不完整或错误,ANTLR会抛出RecognitionException异常,RecognitionExceptiongetExpectedTokens方法会返回所有期望的符号,利用这个机制,可以实现语法自动补全与提示的功能。捕获RecognitionException异常需要继承BaseErrorListener,并在parser中注册异常监听器parser.addErrorListener(...)

ANTLR语法库

在GitHub上有一个ANTLR 4语法库:https://github.com/antlr/grammars-v4,里边有几乎所有常见语言的语法文件。就算是要设计一个新的语言,也应该首先到这里借鉴一下,对于一些基本的符号定义,比如字符串,整形数字等完全可以照搬过来。

参考