一、背景
自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時，我們想實現四則運算該怎么處理呢？有一種思路是基于棧實現。例如，在不考慮異常處理的情況下，自行實現簡單的四則運算代碼如下：
package org.example.calc;
import java.util.*;
public class CalcByHand {
// 定義操作符并區分優先級，*/ 優先級較高
public static Set<String> opSet1 = new HashSet<>();
public static Set<String> opSet2 = new HashSet<>();
static{
opSet1.add("+");
opSet1.add("-");
opSet2.add("*");
opSet2.add("/");
}
public static void main(String[] args) {
String exp="1+3*4";
//將表達式拆分成token
String[] tokens = exp.split("((?<=[\\+|\\-|\\*|\\/])|(?=[\\+|\\-|\\*|\\/]))");
Stack<String> opStack = new Stack<>();
Stack<String> numStack = new Stack<>();
int proi=1;
// 基于類型放到不同的棧中
for(String token: tokens){
token = token.trim();
if(opSet1.contains(token)){
opStack.push(token);
proi=1;
}else if(opSet2.contains(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 -package org.example.calc -no-listener -visitor .\LabeledExpr.g4
命令執行完成后，生成的文件如下：
$ tree .
├── LabeledExpr.g4
├── LabeledExpr.tokens
├── LabeledExprBaseVisitor.java
├── LabeledExprLexer.java
├── LabeledExprLexer.tokens
├── 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 = visit(ctx.expr(0)); // get value of left subexpression
int right = visit(ctx.expr(1)); // get value of right subexpression
if ( ctx.op.getType() == 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 -package org.example.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 (ctx.op.getType() == LabeledExprParser.ADD) {
result = left + right;
} else {
result = left - right;
}
numStack.push(result);
}
直接從棧中取出操作數，進行運算即可。
3.2.3 小結
關于Listener模式和Visitor模式的區別，《The Definitive ANTLR 4 Reference》一書中有清晰的解釋：
Listener模式：
Visitor模式
- Listener模式通過walker對象自行遍歷，不用考慮其語法樹上下級關系。Vistor需要自行控制訪問的子節點，如果遺漏了某個子節點，那么整個子節點都訪問不到了。
- Listener模式的方法沒有返回值，Vistor模式可以設定任意返回值。
- Listener模式的訪問棧清晰明確，Vistor模式是方法調用棧，如果實現出錯有可能導致StackOverFlow。
通過這個簡單的例子，我們驅動Antlr4實現了一個簡單的計算器。學習了ANTLR4的應用流程。了解了g4語法文件的定義方式、Visitor模式和Listener模式。通過ANTLR4，我們生成了ParseTree,并基于Visitor模式和Listener模式訪問了這個ParseTree，實現了四則運算。
綜合上述的例子可以發現，如果沒有ANTLR4，我們自行編寫算法也能實現同樣的功能。但是使用ANTLR不用關心表達式串的解析流程，只關注具體的業務實現即可，非常省心和省事。
更重要的是，ANTLR4相比自行實現提供了更具想象空間的抽象邏輯，上升到了方法論的高度，因為它已經不局限于解決某個問題，而是解決一類問題?？梢哉fANTLR相比于自行硬編碼解決問題的思路有如數學領域普通的面積公式和微積分的差距。
四、參考Presto源碼開發SQL解析器
前面介紹了使用ANTLR4實現四則運算，其目的在于理解ANTLR4的應用方式。接下來圖窮匕首見，展示出我們的真正目的：研究ANTLR4在Presto中如何實現SQL語句的解析。
支持完整的SQL語法是一個龐大的工程。在presto中有完整的SqlBase.g4文件，定義了presto支持的所有SQL語法，涵蓋了DDL語法和DML語法。該文件體系較為龐大，并不適合學習探究某個具體的細節點。
為了探究SQL解析的過程，理解SQL執行背后的邏輯，在簡單地閱讀相關資料文檔的基礎上，我選擇自己動手編碼實驗。為此，定義一個小目標：實現一個SQL解析器。用該解析器實現select field from table語法，從本地的csv數據源中查詢指定的字段。
4.1 裁剪SelectBase.g4文件
基于同實現四則運算器同樣的流程，首先定義SelectBase.g4文件。由于有了Presto源碼作為參照系，我們的SelectBase.g4并不需要自己開發，只需要基于Presto的g4文件裁剪即可。裁剪后的內容如下：
grammar SqlBase;
tokens {
DELIMITER
}
singleStatement
: statement EOF
;
statement
: query #statementDefault
;
query
: queryNoWith
;
queryNoWith:
queryTerm
;
queryTerm
: queryPrimary #queryTermDefault
;
queryPrimary
: querySpecification #queryPrimaryDefault
;
querySpecification
: SELECT selectItem (',' selectItem)*
(FROM relation (',' relation)*)?
;
selectItem
: expression #selectSingle
;
relation
: sampledRelation #relationDefault
;
expression
: booleanExpression
;
booleanExpression
: valueExpression #predicated
;
valueExpression
: primaryExpression #valueExpressionDefault
;
primaryExpression
: identifier #columnReference
;
sampledRelation
: aliasedRelation
;
aliasedRelation
: relationPrimary
;
relationPrimary
: qualifiedName #tableName
;
qualifiedName
: identifier ('.' identifier)*
;
identifier
: IDENTIFIER #unquotedIdentifier
;
SELECT: 'SELECT';
FROM: 'FROM';
fragment DIGIT
: [0-9]
;
fragment LETTER
: [A-Z]
;
IDENTIFIER
: (LETTER | '_') (LETTER | DIGIT | '_' | '@' | ':')*
;
WS
: [ \r\n\t]+ -> channel(HIDDEN)
;
// Catch-all for anything we can't recognize.
// We use this to be able to ignore and recover all the text
// when splitting statements with DelimiterLexer
UNRECOGNIZED
: .
;
相比presto源碼中700多行的規則，我們裁剪到了其1/10的大小。該文件的核心規則為: SELECT selectItem (',' selectItem)* (FROM relation (',' relation)*)?
通過理解g4文件，也可以更清楚地理解我們查詢語句的構成。例如通常我們最常見的查詢數據源是數據表。但是在SQL語法中，我們查詢數據表被抽象成了relation。
這個relation有可能來自于具體的數據表，或者是子查詢，或者是JOIN，或者是數據的抽樣，或者是表達式的unnest。在大數據領域，這樣的擴展會極大方便數據的處理。
例如，使用unnest語法解析復雜類型的數據，SQL如下：
盡管SQL較為復雜，但是通過理解g4文件，也能清晰理解其結構劃分?；氐絊electBase.g4文件，同樣我們使用Antlr4命令處理g4文件，生成代碼：
antlr4 -package org.example.antlr -no-listener -visitor .\SqlBase.g4
這樣就生成了基礎的框架代碼。接下來就是自行處理業務邏輯的工作了。
4.2 遍歷語法樹封裝SQL結構信息
接下來基于SQL語法定義語法樹的節點類型，如下圖所示。
通過這個類圖，可以清晰明了看清楚SQL語法中的各個基本元素。
然后基于visitor模式實現自己的解析類AstBuilder (這里為了簡化問題，依然從presto源碼中進行裁剪)。以處理querySpecification規則代碼為例：
@Override
public Node visitQuerySpecification(SqlBaseParser.QuerySpecificationContext context)
{
Optional<Relation> from = Optional.empty();
List<SelectItem> selectItems = visit(context.selectItem(), SelectItem.class);
List<Relation> relations = visit(context.relation(), Relation.class);
if (!relations.isEmpty()) {
// synthesize implicit join nodes
Iterator<Relation> iterator = relations.iterator();
Relation relation = iterator.next();
from = Optional.of(relation);
}
return new QuerySpecification(
getLocation(context),
new Select(getLocation(context.SELECT()), false, selectItems),
from);
}
通過代碼，我們已經解析出了查詢的數據源和具體的字段，封裝到了QuerySpecification對象中。
4.3 應用Statement對象實現數據查詢
通過前面實現四則運算器的例子，我們知道ANTLR把用戶輸入的語句解析成ParseTree。業務開發人員自行實現相關接口解析ParseTree。Presto通過對輸入sql語句的解析，生成ParseTree, 對ParseTree進行遍歷，最終生成了Statement對象。核心代碼如下：
SqlParser sqlParser = new SqlParser();
Statement statement = sqlParser.createStatement(sql);
有了Statement對象我們如何使用呢？結合前面的類圖，我們可以發現：
- Query類型的Statement有QueryBody屬性。
- QuerySpecification類型的QueryBody有select屬性和from屬性。
通過這個結構，我們可以清晰地獲取到實現select查詢的必備元素：
- 從from屬性中獲取待查詢的目標表Table。這里約定表名和csv文件名一致。
- 從select屬性中獲取待查詢的目標字段SelectItem。這里約定csv首行為title行。
整個業務流程就清晰了，在解析sql語句生成statement對象后，按如下的步驟：
s1: 獲取查詢的數據表以及字段。
s2: 通過數據表名稱定為到數據文件，并讀取數據文件數據。
s3: 格式化輸出字段名稱到命令行。
s4: 格式化輸出字段內容到命令行。
為了簡化邏輯，代碼只處理主線，不做異常處理。
/**
* 獲取待查詢的表名和字段名稱
*/
QuerySpecification specification = (QuerySpecification) query.getQueryBody();
Table table= (Table) specification.getFrom().get();
List<SelectItem> selectItems = specification.getSelect().getSelectItems();
List<String> fieldNames = Lists.newArrayList();
for(SelectItem item:selectItems){
SingleColumn column = (SingleColumn) item;
fieldNames.add(((Identifier)column.getExpression()).getValue());
}
/**
* 基于表名確定查詢的數據源文件
*/
String fileLoc = String.format("./data/%s.csv",table.getName());
/**
* 從csv文件中讀取指定的字段
*/
Reader in = new FileReader(fileLoc);
Iterable<CSVRecord> records = CSVFormat.RFC4180.withFirstRecordAsHeader().parse(in);
List<Row> rowList = Lists.newArrayList();
for(CSVRecord record:records){
Row row = new Row();
for(String field:fieldNames){
row.addColumn(record.get(field));
}
rowList.add(row);
}
/**
* 格式化輸出到控制臺
*/
int width=30;
String format = fieldNames.stream().map(s-> "%-"+width+"s").collect(Collectors.joining("|"));
System.out.println( "|"+String.format(format, fieldNames.toArray())+"|");
int flagCnt = width*fieldNames.size()+fieldNames.size();
String rowDelimiter = String.join("", Collections.nCopies(flagCnt, "-"));
System.out.println(rowDelimiter);
for(Row row:rowList){
System.out.println( "|"+String.format(format, row.getColumnList().toArray())+"|");
}
代碼僅供演示功能，暫不考慮異常邏輯，比如查詢字段不存在、csv文件定義字段名稱不符合要求等問題。
4.4 實現效果展示
在我們項目data目錄，存儲如下的csv文件：
cities.csv文件樣例數據如下：
"LatD","LatM","LatS","NS","LonD","LonM","LonS","EW","City","State"
41, 5, 59, "N", 80, 39, 0, "W", "Youngstown", OH
42, 52, 48, "N", 97, 23, 23, "W", "Yankton", SD
46, 35, 59, "N", 120, 30, 36, "W", "Yakima", WA
42, 16, 12, "N", 71, 48, 0, "W", "Worcester", MA
運行代碼查詢數據。使用SQL語句指定字段從csv文件中查詢。最終實現類似SQL查詢的效果如下：
SQL樣例1：select City, City from cities
SQL樣例2：select name, age from employee
本節講述了如何基于Presto源碼，裁剪g4規則文件，然后基于Antlr4實現用sql語句從csv文件查詢數據。依托于對Presto源碼的裁剪進行編碼實驗，對于研究SQL引擎實現，理解Presto源碼能起到一定的作用。
五、總結
本文基于四則運算器和使用SQL查詢csv數據兩個案例闡述了ANTLR4在項目開發中的應用思路和過程，相關的代碼可以在github上看到。理解ANTLR4的用法能夠幫助理解SQL的定義規則及執行過程，輔助業務開發中編寫出高效的SQL語句。同時對于理解編譯原理，定義自己的DSL，抽象業務邏輯也大有裨益。紙上得來終覺淺，絕知此事要躬行。通過本文描述的方式研究源碼實現，也不失為一種樂趣。
