Antlr4实战：统一SQL路由多引擎

Original 后羿BigDataplus BigDataplus 2021-10-15

背景

安装

Antlr4概念讲解和简单语法

统一SQL多引擎实现方案

改写词法文件
翻译器的实现过程
函数适配：函数转换的困难

总结

背景

ANTLR是一款功能强大的语法分析器生成器，可用来读取、处理、执行和转换结构化文本或二进制文件。它被广泛应用于学术界和工业界构建各种语言、工具和框架。Antlr在Hadoop整个生态系统应用较为广泛，如Hive 词法文件是Antlr3写的；Presto词法文件也Antlr4实现的；SparkSQL词法文件是用Presto的词法文件改写的；还有HBase的访问客户端Phoenix也用Antlr工具进行SQL解析的等等。

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

一条数据库SQL执行或实现过程大致是这样的，实现词法文件.g4（如antlr写词法文件的话），生成词法分析器和语法分析器，生成抽象语法树，再遍历抽象语法树，生成语义树，访问统计信息，优化器生成逻辑执行计划，再生成物理执行计划去执行，这就是整个数据库实现过程。一般数据库架构图如下：

Antlr解析工具处理过程，包括写词法文件.g4，生成词法分析器和语法分析器，生成抽象语法树，再遍历抽象语法树。语义层以及之后步骤由不同的优化器部分实现的。Calcite是Apache开源的可用做SQL解析（标准SQL），查询优化Query optimization的动态数据管理框架。

目前, 使用Calcite作为SQL解析与Query optimization处理引擎有Hive、Kylin、Drill、Flink、Phoenix和Storm等等。后续文章会Apache Calcite单独讲解，这里主要讲解Antlr4解析工具的应用。

安装

直接在idea安装插件非常简单，点击安装即可，如图：

Antlr4概念讲解和简单语法

Antlr 4新特性与Antlr v3的区别：

学习成本低。antlr v4相对于v3，v4更注重于用更接近于自然语言的方式去解析语言。比如运算符优先级，排在最前面的规则优先级最高；
层次更清晰更易维护。引入访问者、监听器模式，使解析与应用代码分离；新増import功能，lexer、parser可以成为公共组件，増加可复用性；
新算法。改进LL()算法，使用新的Adative LL()算法，在运行时动态分析语法，而LL(*)需要静态分析语法，考虑各种语法的可能性。
新用法。引入了一些新用法，如rewrite the input stream、sending token in different channels、island grammars、associativity，可以更方便、灵活地在应用中处理解析对象。
性能。相对于v3，解析代码跟应用代码都是自动生成的，而v4分离了解析与应用代码的实现，应用代码的实现及性能则可以由开发人员自主地控制，但新算法据官方指引说会消耗一定的速度上的性能，因此提供了SLL()、LL()的开关，可通过api控制

通用术语

语言

一门语言是一个有效的语句的集合。语句由词组组成，词组由子词组组成，子词组又由更小的子词组组成，依次类推。

语法

语法定义来语言的语义规则。语法中的每条规则定义来一种词组结构。

词法符号Token

是一门语言的基本词汇符号，如标识符、运算符、关键字等等。

词法分析器

将输入的字符序列分解成一系列词法符号或词素序列。一个词法分析器负责分析词法。

语法分析器

通过检查语句的结构是否符合语法规则的定义来验证该语句在特定语言中是否合法。

抽象语法树

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

Antlr相关语法

ANTLR自动产生为递归下降的语法分析器，实际上为若干递归方法的集合，每个方法对应一条规则。下降的过程就是语法分析树的根节点开始，朝着叶节点（词法符号）进行解析的过程。首先，调用的规则，即语义符号的起始点，就会成为语法分析树的根节点。语法分析树是语法分析器分析得到的结果。写按照Antlr语法要求写词法和语法文件以.g4后缀。

词法和语法规则

语法规则：

语法规则总是以小写字母开头，首字母以后的字符，可是大小写字母、数字和下划线。最基本的形式是规则名称后面紧接着一个备选分支“|”，然后是一个分号。如下：

querySpecification : SELECT setQuantifier? selectItem (',' selectItem)* (FROM relation (',' relation)*)? (WHERE where=booleanExpression)? (GROUP BY groupBy)? (HAVING having=booleanExpression)? (ORDER BY sortItem (',' sortItem)*)? (clusterBy)? //PRESTO没有这种写法，添加clusterBy语法规则 (LIMIT limit=INTEGER_VALUE )? ; booleanExpression : predicated #booleanDefault | NOT booleanExpression #logicalNot | left=booleanExpression operator=AND right=booleanExpression #logicalBinary | left=booleanExpression operator=OR right=booleanExpression #logicalBinary ;

Antlr4会为每条规则自动生成一个方法，并生产一个相应规则Context上下文对象，若为规则的备用选项添加标签，就必须全部添加标签，会自动为每个标签自动生成一个方法，并生成一个相应规则Context上下文对象，标签相当于方法来用，其可更细粒度解析语法。

词法规则：

词法语法由词法规则组成，且可被分解成多个模式，词法规则不能包含参数，返回值或局部变量。词法规则名称必须以大写字母开头，与语法规则名称区别开来。如下：

PLUS: '+';MINUS: '-';ASTERISK: '*';SLASH: '/';PERCEN: '%';CONCAT: '||';

SIMPLE_COMMENT : '--' ~[\r\n]* '\r'? '\n'? -> channel(HIDDEN) ;BRACKETED_COMMENT : '/*' .*? '*/' -> channel(HIDDEN) ;WS : [ \r\n\t]+ -> channel(HIDDEN) ;

动作和属性

动作是以目标语言编写的，位于花括号中的文本块，识别器根据它们在语法中的位置，在不同的时机触发它。所有的词法符号都包含一组预定义的只读属性。这些属性包括一些有用的属性，如词法符号的类型以及匹配的文本等。如下：

predicated : valueExpression predicate[$valueExpression.ctx]? ;predicate[ParserRuleContext value] : comparisonOperator right=valueExpression #comparison | comparisonOperator '(' query ')' #quantifiedComparison | NOT? BETWEEN lower=valueExpression AND upper=valueExpression #between | NOT? IN '(' expression (',' expression)* ')' #inList | NOT? IN '(' query ')' #inSubquery | NOT? LIKE pattern=valueExpression #like | IS NOT? NULL #nullPredicate ;

遍历模式：监听者模式和访问者模式

监听器：对语法分析树遍历器在开始和结束对节点的访问，即构成的访问某条规则开始事件和结束事件触发作出响应。
访问器：没有使用遍历器来遍历访问语法分析树，而是访问器来访问语法分析树。

语法分析器ALL(*) 与 LR、LL等不同

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

统一SQL多引擎实现方案

统一SQL可屏蔽了多种引擎SQL差异，可基于SQL复杂度和成本估算、优先级和各引擎集群空闲程度，把用户提交的SQL路由到合适的执行引擎，如果Hive转换Presto、Spark或其他引擎执行失败，则使用Hive引擎来补救执行，最终都会返回结果。

目前，使用HQL语法作为统一SQL语法，根据SQL复杂度，解析SQL使用的表或Operator（如Join、Count、Distinct）访问HiveMeta来计算SQL成本等等信息进行路由不同引擎。到不同引擎执行，因各引擎语法各异，就需一个翻译器把统一HQL语法翻译成各引擎语法。

同样，统一SQL翻译器在语法进行翻译时，因引擎语法各异，则功能不同，函数完善程度不对等写UDF，使用方法或参数不同等内部映射转换等等都需要完善的。

因HQL语法作为统一SQL语法，但Hive词法文件是使用Anltr3实现的，含有大量Predicate断言，并分为多个不同的词法文件相对分散且不易理解。于是统一SQL引擎的HQL词法文件是笔者就使用Antlr4来实现的，是改写了Presto的词法文件（结构清晰且严谨完整的且一气呵成词法文件，SparkSQL也是改写的Presto词法文件作为自己的语法文件的）。

目前，笔者只实现了Hive和Presto翻译两种引擎，以后会有更多的引擎加入，不断进行迭代优化。故以下内容实现和讲解都基于这两种引擎的。

改写词法文件

Hive、SparkSql和Presto语法都是基于SQL的，也都是标准SQL基础上因实现功能各异实现的不同语法，但90%语法相同，于是笔者也像SparkSQL一样对Presto词法文件语法进行改写使其满足HQL语法，做为统一SQL引擎的HQL词法文件。由于词法文件内容较多，没全部贴出，只讲解部分改写的内容。

1）删除(optionType=(INCLUDING | EXCLUDING) PROPERTIES)?

likeClause : LIKE qualifiedName

2）原Presto词法文件中无CLUSTER BY、DISTRIBUTE BY、SORT BY这添加了clusterBy语法规则来满足完整的HQL语法。

clusterBy语法规则：

clusterBy

    : ((CLUSTER BY expression (',' expression)*)| ((DISTRIBUTE BY expression (',' expression)*)? (SORT BY sortItem (',' sortItem)*)?) )?

;

3）删除了自然连接NATURAL joinType JOIN right=sampledRelation备选项和

删除关联时，关联条件两张表相同字段直接使用using写法，添加了lateral:LATERAL VIEW语法规则。

relation : left=relation ( CROSS JOIN right=sampledRelation | joinType JOIN rightRelation=relation joinCriteria? | lateral right=sampledRelation ) #joinRelation | sampledRelation #relationDefault ;lateral:LATERAL VIEW;joinType : INNER? | LEFT OUTER? | RIGHT OUTER? | FULL OUTER? ;joinCriteria : ON booleanExpression;

4）添加了Hive语法中TABLESAMPLE关键字取样的相关语法规则，如下：

sampledRelation : relationPrimary tableSampleFunc? (AS? identifier columnAliases?)? ;tableSampleFunc : TABLESAMPLE '(' percentage=samplevalue ')' ;samplevalue : percentType | bucketSample ;percentType : number PERCENT | INTEGER_VALUE ROWS | BLOCK_IDENTIFIER ;bucketSample :BUCKET INTEGER_VALUE OUT OF INTEGER_VALUE (ON primaryExpression)?

5）hive中没有all some any判断，故这里去掉comparisonQuantifier，删除IS NOT? DISTINCT FROM等等。

predicate[ParserRuleContext value]: comparisonOperator right=valueExpression #comparison

 | comparisonOperator '(' query ')' #quantifiedComparison //comparisonOperator comparisonQuantifier '(' query ')' hive中没有all some any判断，故这里去掉comparisonQuantifier

| NOT? BETWEEN lower=valueExpression AND upper=valueExpression #between | NOT? IN '(' expression (',' expression)* ')' #inList | NOT? IN '(' query ')' #inSubquery

 | NOT? LIKE pattern=valueExpression #like //NOT? LIKE pattern=valueExpression (ESCAPE escape=valueExpression)? 去掉(ESCAPE escape=valueExpression)? 部分

| IS NOT? NULL #nullPredicate //| IS NOT? DISTINCT FROM right=valueExpression #distinctFrom //删除IS NOT? DISTINCT FROM ;

上述只是列举一小部分改写的词法文件内容，还有很多细节这里就不再赘述，需要强调的是，写词法和语法规则时，不能产生歧义并严谨，否则语法产生非期望结果，因此需要初学者多次调试验证。

翻译器的实现过程

要实现统一SQL多引擎执行的支持，需根据不同引擎语法实现不同的监听器逻辑或访问器逻辑多种语法翻译功能，但是通用几个文件如下：

翻译器实现目录

改写完词法文件后的HQL的词法文件HiveSqlBase.g4,antlr4的词法文件以.g4作为文件后缀的。然后使用Antlr4工具命令或idea右键产生gen包下的8个文件，以下一一介绍功能。

HiveSqlBase.tokens

由词法文件生成的词法符号

HiveSqlBaseListener

此接口为HiveSqlBaseParser生成的分析树定义一个完整的监听器

HiveSqlBaseBaseListener

实现了HiveSqlBaseListener监听器接口的空类

HiveSqlBaseVisitor

此接口为HiveSqlBaseParser生成的分析树定义一个完整的访问器

HiveSqlBaseBaseVisitor

实现了HiveSqlBaseVisitor访问器接口的空类

HiveSqlBaseLexer

由词法和语法文件HiveSqlBase.g4，生成的词法分析器

HiveSqlBaseLexer.tokens

词法分析器产生的词法符号列表

HiveSqlBaseParser

由词法和语法文件HiveSqlBase.g4，生成的语法分析器

注：file.tokens 和 lexer.tokens 两者之间的区别？Antlr为每种文法(词法和语法)创建tokens文件，当它把混合文法(词法规则和语法规则写在一起)拆分为词法和语法时，你将要看到两个tokens文件。这些files.tokens是antlr自动生成词法语法分析等等过程中生成的临时文件，也不会分布式到最终的程序，大小可忽略不计。在生成过程中也没必要消除它们。两者唯一区别：有时，语法分析器引入的tokens在词法分析器中没有发现，通常这是一个bug

实现访问器模式

继承HiveSqlBaseBaseVisitor<String>返回类型为String类型，深度优先遍历。

大致实现步骤如下：

1）泛型T作为所有visitXXX()方法的返回值，这里String类型返回值

2）生成visitXXX()默认实现：调用visitChildren(ctx)并返回也就是访问子树根节点存储的内容。对于存在多个子节点，直接使用父类继承的visitXXX()方法有问题的，visitChildren(RuleNode node)默认实现只会返回最后一个子节点的内容，使用的话需要重写做遍历子节点并整合子节点信息。

3）visit(ParseTree tree):遍历一颗语法分析树，调用visitXXX(ParserRuleContext ctx)规则方法并获取返回值(自顶向下递归调用后的返回值)，visit()需要开发者自顶向下手写遍历代码visitXXX()，保证这些visitXXX()是根据语法分析树能递归下降调用的，才能完全遍历访问一颗语法分析树（监听器不需要开发者手写遍历代码，一切是自动遍历）。visitXXX(ParserRuleContext ctx)和语法分析树之间是通过传递代表当前节点ParserRuleContext上下文参数来访问语法分析树。

如：

a) ctx.getChild(i).getText()：获取语法分析树本身子树节点上存储的内容

b) visit(ctx.getChild(i))：获取的是从语法分析树visitXXX开始访问手写遍历代码visitXXX()自顶向下递归调用visitXXX方法后的返回值。

如果ctx.getChild(i)为叶子节点时visit(ctx.getChild(i))返回值为null，因为叶子节点没有相关visitXXX()方法。这也是涉及到叶子节点的方法实现使用ctx.getChild(0).getText()来访问语法分析树叶子节点上存储的内容。

4）实现访问器遍历原HSQL生成转换目标语法如Presto逻辑，作为翻译器的返回结果。

这些实现过程因为函数的转换，不同语句转换，调换，裁剪，增加等等逻辑都是在访问器模式遍历语法树的过程中实现的。

语法树片段，如图：

在使用Visitor访问器模式，对语法树进行遍历时，把HQL语法转换为目标引擎的语法如Presto语法。部分具体逻辑如下：

单引号或双引号统一单引号转换
对字符串处理逻辑：

1）最外围双引号去掉,234步骤内部字符串处理。

2） hive中使用反斜杠进行转义，翻译时需将Hive中反斜杠转义符删掉

3）当多个反斜杠转义反斜杠的情况，反斜杠为偶数，两个反斜杠替换为一个反斜杠

4） Hive中出现单引号时，一个单引号替换为两个单引号，因presto只有单引号需转义，使用单引号对单引号进行转义。

5）上述处理后，最外围使用单引号包围。

关键字反引号转换处理
反斜杠语义不同的处理

如：剔除中文的regexp_replace(cmp_nam,'[^\u4e00-\u9fa50-9]',''))函数处理

Presto使用字符串中使用'单引号做字符转义,Hive使用\反斜杠做转义，同一个正则表达式'[^\\u4e00-\\u9fa50-9]'，在Hive中，就写成'[^\\u4e00-\\u9fa50-9]'，在Presto 中，写成'[^\u4e00-\u9fa50-9]'，这里不需要对反斜杠进行转义。否则两边结果一致。

函数不同的处理
Cast转换Presto使用VARCHAR而不是STRING
要对两个整数执行浮点除法转换Cast

.....

数组下标，行列转换，group集合等等涉及太多细节这里不再一一讲解了，实现这样的翻译器需补全完善功能，要做的事情很多很多，这样才能让统一SQL多引擎执行结果保持一致。

函数适配：函数转换的困难

Hive与其他引擎的函数功能、参数个数、参数数据类型、参数顺序及返回精度及隐式转换支持与否都各不完全一致等等这难点，都需统一SQL引擎实现时要解决的。

函数适配的问题如下：

内置函数不对等
内置函数名称不同
内置函数参数个数不同
内置函数参数顺序不同
内置函数参数数据类型不同
内置函数返回结果数据类型不同

实现思路：

关于内置函数不对等，来实现相关UDF使其两边对等，还有函数参数顺序、数据类型和个数问题，都预写一个映射模版，调换参数顺序，转换参数的数据类型，填充默认的参数，转换返回的数据类型来满足精度等问题，如Hive的日期函数date_add，date_sub、add_months日期向前推和向后推，但是Presto函数对应的只有一个date_add，其是根据第一个参数类型来判断天、月等，就可以默认填写，并调换p2和p4的参数顺序(这是通过遍历语法树解析出来的)。

//presto函数翻译配置multiFunc.put("date_add",Arrays.asList( "date_add('day',p4,cast(p2 as date))"));multiFunc.put("date_sub",Arrays.asList( "date_add('day',-p4,cast(p2 as date))"));multiFunc.put("add_months",Arrays.asList( "date_add('month',p4,cast(p2 as date))"));

两边实现转换的有几十个内置函数，包括整体代码实现逻辑，这里不再赘述。

总结

统一SQL路由多引擎实现了统一HQL语法和统一入口，屏蔽了多种引擎SQL方言切换，根据各引擎集群空闲负载情况，SQL复杂度及开销成本等路由到合适的引擎执行。但因Hive天生支持隐式转换，再加上没有标准化建模的数据仓库（没有指定数据标准，同一个通用字段，在不同表中有不同的数据类型等）会给其增加路由其他引擎执行的难度，这里实现部分简单的隐式转换功能，以后会再添加一层语义层（通过去年Hive 优化器源码研究，熟悉HiveMeta元数据每张表的功能，这不是问题）增加数据类型判断，隐式转换及SQL重写优化功能等等。

Antlr4解析工具用途蛮多的，如在做数据治理的元数据管理时，做动态字段级血缘关系的数据地图，SQL重写优化，DSL实现等等。

由于笔者知识及水平有限,因此文中错漏之处在所难免,恳请各位老师、专家不吝赐教。

往期文章分享

Flink系列

Flink优化器与源码解析系列--让Flink飞奔起来这篇文章就够啦(一)

数据治理系列

数据治理系列：一个数据质量监控系统的自我修养

优化规则系列

Hive优化器原理与源码解析系列--优化规则SortRemoveRule(一)

Hive优化器原理与源码解析系列--优化规则SortJoinReduceRule(二)

Hive优化器原理与源码解析系列--优化规则SortProjectTransposeRule(三)

Hive优化器原理与源码解析系列--优化规则SortUnionReduceRule(四)