基于ANTLR⾃⼰实现⼀个SQL解析器
作者
vivo互联⽹开发团队-Shuai Guangying
⼀、背景
⾃2014年⼤数据⾸次写⼊政府⼯作报告，⼤数据已经发展7年。⼤数据的类型也从交易数据延伸到交互数据与传感数据。数据规模也到达了PB级别。
⼤数据的规模⼤到对数据的获取、存储、管理、分析超出了传统数据库软件⼯具能⼒范围。在这个背景下，各种⼤数据相关⼯具相继出现，⽤于应对各种业务场景需求。从Hadoop⽣态的Hive, Spark, Presto, Kylin, Druid到⾮Hadoop⽣态的ClickHouse, Elasticsearch，不⼀⽽⾜...
这些⼤数据处理⼯具特性不同，应⽤场景不同，但是对外提供的接⼝或者说操作语⾔都是相似的，即各个组件都是⽀持SQL语⾔。只是基于不同的应⽤场景和特性，实现了各⾃的SQL⽅⾔。这就要求相关开源项⽬⾃⾏实现SQL解析。在这个背景下，诞⽣于1989年的语法解析器⽣成器ANTLR迎来了黄⾦时代。
⼆、简介
ANTLR是开源的语法解析器⽣成器，距今已有30多年的历史。是⼀个经历了时间考验的开源项⽬。⼀个程序从源代码到机器可执⾏，基本需要3个阶段：编写、编译、执⾏。
在编译阶段，需要进⾏词法和语法的分析。ANTLR聚焦的问题就是把源码进⾏词法和句法分析，产⽣⼀个树状的分析器。ANTLR⼏乎⽀持对所有主流编程语⾔的解析。从antlr/grammars-v4可以看到，ANTLR⽀持Java,C, Python, SQL等数⼗种编程语⾔。通常我们没有扩展编程语⾔的需求，所以⼤部分情况下这些语⾔编译⽀持更多是供学习研究使⽤，或者⽤在各种开发⼯具(NetBeans、Intellij)中⽤于校验语法正确性、和格式化代码。
对于SQL语⾔，ANTLR的应⽤⼴度和深度会更⼤，这是由于Hive, Presto, SparkSQL等由于需要对SQL的执⾏进⾏定制化开发，⽐如实现分布式查询引擎、实现各种⼤数据场景下独有的特性等。
三、基于ANTLR4实现四则运算
当前我们主要使⽤的是ANTLR4。在《The Definitive ANTLR4 Reference》⼀书中，介绍了基于ANTLR4的各种有趣的应⽤场景。⽐如：实现⼀个⽀持四则运算的计算器；实现JSON等格式化⽂本的解析和提取；
将JSON转换成XML；从Java源码中提取接⼝等。本节以实现四则运算计算器为例，介绍Antlr4的简单应
⽤，为后⾯实现基于ANTLR4解析SQL铺平道路。实际上，⽀持数字运算也是各个编程语⾔必须具备的基本能⼒。
3.1 ⾃⾏编码实现
在没有ANTLR4时，我们想实现四则运算该怎么处理呢？有⼀种思路是基于栈实现。例如，在不考虑异常处理的情况下，⾃⾏实现简单的四则运算代码如下：
ample.calc;
import java.util.*;
public class CalcByHand {
// 定义操作符并区分优先级，*/ 优先级较⾼
public static Set<String> opSet1 = new HashSet<>();
public static Set<String> opSet2 = new HashSet<>();
static{
hive trim函数opSet1.add("+");
opSet1.add("-");
opSet2.add("*");
opSet2.add("/");
}
public static void main(String[] args) {
String exp="1+3*4";
//将表达式拆分成token
String[] tokens = exp.split("((?<=[\\+|\\-|\\*|\\/])|(?=[\\+|\\-|\\*|\\/]))");
String[] tokens = exp.split("((?<=[\\+|\\-|\\*|\\/])|(?=[\\+|\\-|\\*|\\/]))");
Stack<String> opStack = new Stack<>();
Stack<String> numStack = new Stack<>();
int proi=1;
// 基于类型放到不同的栈中
for(String token: tokens){
token = im();
ains(token)){
opStack.push(token);
proi=1;
}else ains(token)){
proi=2;
opStack.push(token);
}else{
numStack.push(token);
// 如果操作数前⾯的运算符是⾼优先级运算符，计算后结果⼊栈
if(proi==2){
calcExp(opStack,numStack);
}
}
}
while (!opStack.isEmpty()){
calcExp(opStack,numStack);
}
String finalVal = numStack.pop();
System.out.println(finalVal);
}
private static void calcExp(Stack<String> opStack, Stack<String> numStack) {
double right=Double.valueOf(numStack.pop());
double left = Double.valueOf(numStack.pop());
String op = opStack.pop();
String val;
switch (op){
case "+":
val =String.valueOf(left+right);
break;
case "-":
val =String.valueOf(left-right);
break;
case "*":
val =String.valueOf(left*right);
break;
case "/":
val =String.valueOf(left/right);
break;
default:
throw new UnsupportedOperationException("unsupported");
}
numStack.push(val);
}
}
代码量不⼤，⽤到了数据结构-栈的特性，需要⾃⾏控制运算符优先级，特性上没有⽀持括号表达式，也没有⽀持表达式赋值。接下来看看使⽤ANTLR4实现。
3.2 基于ANTLR4实现
使⽤ANTLR4编程的基本流程是固定的，通常分为如下三步：
基于需求按照ANTLR4的规则编写⾃定义语法的语义规则, 保存成以g4为后缀的⽂件。
使⽤ANTLR4⼯具处理g4⽂件，⽣成词法分析器、句法分析器代码、词典⽂件。
编写代码继承Visitor类或实现Listener接⼝，开发⾃⼰的业务逻辑代码。
基于上⾯的流程，我们借助现有案例剖析⼀下细节。
第⼀步：基于ANTLR4的规则定义语法⽂件，⽂件名以g4为后缀。例如实现计算器的语法规则⽂件命名为LabeledExpr.g4。其内容如下：grammar LabeledExpr; // rename to distinguish from Expr.g4
prog: stat+ ;
stat: expr NEWLINE # printExpr
| ID '=' expr NEWLINE # assign
| NEWLINE # blank
;
expr: expr op=('*'|'/') expr # MulDiv
| expr op=('+'|'-') expr # AddSub
| INT # int
| ID # id
| '(' expr ')' # parens
;
MUL : '*' ; // assigns token name to '*' used above in grammar
DIV : '/' ;
ADD : '+' ;
SUB : '-' ;
ID : [a-zA-Z]+ ; // match identifiers
INT : [0-9]+ ; // match integers
NEWLINE:'\r'? '\n' ; // return newlines to parser (is end-statement signal)
WS : [ \t]+ -> skip ; // toss out whitespace
(注：此⽂件案例来源于《The Definitive ANTLR4 Reference》)
简单解读⼀下LabeledExpr.g4⽂件。ANTLR4规则是基于正则表达式定义定义。规则的理解是⾃顶向下的，每个分号结束的语句表⽰⼀个规则 。例如第⼀⾏：grammar LabeledExpr; 表⽰我们的语法名称是LabeledExpr, 这个名字需要跟⽂件名需要保持⼀致。Java编码也有相似的规则：类名跟类⽂件⼀致。
规则prog 表⽰prog是⼀个或多个stat。
规则stat 适配三种⼦规则：空⾏、表达式expr、赋值表达式 ID’=’expr。
表达式expr适配五种⼦规则：乘除法、加减法、整型、ID、括号表达式。很显然，这是⼀个递归的定义。
最后定义的是组成复合规则的基础元素，⽐如：
规则ID: [a-zA-Z]+表⽰ID限于⼤⼩写英⽂字符串；
INT: [0-9]+; 表⽰INT这个规则是0-9之间的⼀个或多个数字，当然这个定义其实并不严格。再严格⼀点，应该限制其长度。
在理解正则表达式的基础上，ANTLR4的g4语法规则还是⽐较好理解的。
定义ANTLR4规则需要注意⼀种情况，即可能出现⼀个字符串同时⽀持多种规则，如以下的两个规则：
ID: [a-zA-Z]+;
FROM: ‘from’;
很明显，字符串” from”同时满⾜上述两个规则，ANTLR4处理的⽅式是按照定义的顺序决定。这⾥ID定义在FROM前⾯，所以字符串from会优先匹配到ID这个规则上。
其实在定义好与法规中，编写完成g4⽂件后，ANTLR4已经为我们完成了50%的⼯作：帮我们实现了整个架构及接⼝了，剩下的开发⼯作就是基于接⼝或抽象类进⾏具体的实现。实现上有两种⽅式来处理⽣成的语法树，其⼀Visitor模式，另⼀种⽅式是Listener(模式)。
3.2.1 使⽤Visitor模式
第⼆步：使⽤ANTLR4⼯具解析g4⽂件，⽣成代码。即ANTLR⼯具解析g4⽂件，为我们⾃动⽣成基础代码。流程图⽰如下：
命令⾏如下：
antlr4 -ample.calc -no-listener -visitor .\LabeledExpr.g4
命令执⾏完成后，⽣成的⽂件如下：
$ tree .
.
├── LabeledExpr.g4
├── kens
├── LabeledExprBaseVisitor.java
├── LabeledExprLexer.java
├── kens
├── LabeledExprParser.java
└── LabeledExprVisitor.java
⾸先开发⼊⼝类Calc.java。Calc类是整个程序的⼊⼝，调⽤ANTLR4的lexer和parser类核⼼代码如下：
ANTLRInputStream input = new ANTLRInputStream(is);
LabeledExprLexer lexer = new LabeledExprLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
LabeledExprParser parser = new LabeledExprParser(tokens);
ParseTree tree = parser.prog(); // parse
EvalVisitor eval = new EvalVisitor();
eval.visit(tree);
接下来定义类继承LabeledExprBaseVisitor类，覆写的⽅法如下：
从图中可以看出，⽣成的代码和规则定义是对应起来的。例如visitAddSub对应AddSub规则，visitId对应id规则。以此类推…实现加减法的代码如下：
/** expr op=('+'|'-') expr */
@Override
public Integer visitAddSub(LabeledExprParser.AddSubContext ctx) {
int left = pr(0)); // get value of left subexpression
int right = pr(1)); // get value of right subexpression
if ( Type() == LabeledExprParser.ADD ) return left + right;
return left - right; // must be SUB
}
相当直观。代码编写完成后，就是运⾏Calc。运⾏Calc的main函数，在交互命令⾏输⼊相应的运算表达式，换⾏Ctrl+D即可看到运算结果。例如1+3*4=13。
3.2.2 使⽤Listener模式
类似的，我们也可以使⽤Listener模式实现四则运算。命令⾏如下：
antlr4 -ample.calc -listener .\LabeledExpr.g4
该命令的执⾏同样会为我们⽣产框架代码。在框架代码的基础上，我们开发⼊⼝类和接⼝实现类即可。⾸先开发⼊⼝类Calc.java。Calc类是整个程序的⼊⼝，调⽤ANTLR4的lexer和parser类代码如下：
ANTLRInputStream input = new ANTLRInputStream(is);
LabeledExprLexer lexer = new LabeledExprLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
LabeledExprParser parser = new LabeledExprParser(tokens);
ParseTree tree = parser.prog(); // parse
ParseTreeWalker walker = new ParseTreeWalker();
walker.walk(new EvalListener(), tree);
可以看出⽣成ParseTree的调⽤逻辑⼀模⼀样。实现Listener的代码略微复杂⼀些，也需要⽤到栈这种数据结构，但是只需要⼀个操作数栈就可以了，也⽆需⾃⾏控制优先级。以AddSub为例：
@Override
public void exitAddSub(LabeledExprParser.AddSubContext ctx) {
Double left = numStack.pop();
Double right= numStack.pop();
Double result;
if (Type() == LabeledExprParser.ADD) {
result = left + right;
} else {
result = left - right;
}
numStack.push(result);
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论