Calcite系列(六)：执行流程-语法解析
原创Calcite系列(六)：执行流程-语法解析
原创
解析流程
语法解析是SQL处理的第一步，主要由词法分析和语法分析两个步骤组成：
- 词法分析：分词操作，基于生成工具(正则文法+有限状态自动机DFA)将SQL分词为Token(词法记号)，并识别Token为关键字、标识符、标识符、字面量等
- 语法分析：识别出AST的树状语法结构，可基于递归下降算法(自顶向下)构造，其中根节点(RootNode)可代表整个语法树
目前广泛使用的语法解析框架主要包括ANTLR、JavaCC和Yacc等。在大数据领域中，很多计算引擎都是基于ANTLR进行语法解析，例如 Hive、Spark和Presto等都基于ANTLR进行处理。然而，Calcite使用JavaCC编译器进行语法解析。
在Calcite中，Parser.jj是最核心的词法&语法分析文件。为了便于语法扩展，支持基于FMPP（Apache FreeMarker）模板动态生成Parser.jj，主要涉及以下三个文件：
- config.fmpp：FreeMarker配置文件，描述可扩展的解析配置，包括：解析包名/类名、类引用、keywords(关键字)、nonReservedKeywords(非保留关键字)等常见定义
- xxx.ftl：FreeMarker模板文件，描述Java生成类的结构和内容，包括：类定义、方法定义、变量定义等
- Parser.jj：JavaCC模板文件，可结合FreeMarker模板替换生成，最终通过JavaCC编译生成对应的解析器源码
解析流程如下图所示：基于FreeMarker作为模板，整合config.fmpp、xxxx.ftl、Parser.jj文件，生成JavaCC可识别的词法语法文件，JavaCC编译该文件生成对应的SQL解析器源码。
解析框架
JavaCC描述文件格式（Parser.jj模板文件）的定义格式如下：
options {
JavaCC的选项
}
PARSER_BEGIN(解析器类名) # 即是SqlAbstractParserImpl实现
package 包名;
import 库名;
public class 解析器类名 {
任意的Java代码，解析类方法
}
PARSER_END(解析器类名)
词法分析器
语法分析器Calcite中定义的核心解析类方法：
- parseSqlStmtEof：解析单个SQL Statement，获取Root AST Node (SqlNode)
- parseSqlStmtList： 解析SQL Statement列表
词法分析器
词法分析器：定义Token解析器，基于正则文法匹配对应类型，分为四类：
- SKIP：词法解析忽略处理
- MORE：需继续读取下一个文本符
- TOKEN：匹配TOKEN
- SPECIAL_TOKEN：提前定义的字符，不参与解析操作，如结束符
示例如下所示：
SKIP : { " " }
SKIP : { "\n" | "\r" | "\r\n" }
TOKEN : { < PLUS : "+" > }
TOKEN : { < NUMBER : (["0"-"9"])+ > } #正则匹配数字语法分析器
语法分析器：由BNF范式构成，定义TOKEN序列解析规则(推导规则)，类似于Java方法，定义格式示例如下：
SqlNodeList ParenthesizedKeyValueOptionCommaList() :
{
# 定义方法常量
final Span s;
final List<SqlNode> list = new ArrayList<SqlNode>();
}
{
# 方法调用
{ s = span(); }
# TOKEN正则匹配
<LPAREN>
KeyValueOption(list)
(
<COMMA>
KeyValueOption(list)
)* # 循环匹配处理
<RPAREN>
# 返回处理结果
{return new SqlNodeList(list, s.end(this));}
}编译生成的Java代码如下：
final public SqlNodeList ParenthesizedKeyValueOptionCommaList() throws ParseException {
final Span s;
final List<SqlNode> list = new ArrayList<SqlNode>();
s = span();
jj_consume_token(LPAREN);
KeyValueOption(list);
label_21:
while (true) {
switch ((jj_ntk==-1)?jj_ntk():jj_ntk) { # 预读下一个Token
case COMMA:
break;
default:
jj_la1[182] = jj_gen;
break label_21;
}
jj_consume_token(COMMA);
KeyValueOption(list);
}
jj_consume_token(RPAREN);
{if (true) return new SqlNodeList(list, s.end(this));}
throw new Error("Missing return statement in function");
}方法说明：
- jj_consume_token：真读Token，从Token流读取并移除该Token
- jj_ntk：预读Token，进行回溯匹配
语法正则映射关系：
- <token值> ： Token匹配读取，对应 jj_consume_token(token值);
- | ：对应 if 或者 switch的判断条件，或判断
- (...)* ：对应while循环语句，支持0次或多次匹配，直到满足break标识；
- (...)+ ：对应while循环语句，支持1次或多次匹配，直到满足break标识；
- (...) ：对应处理逻辑，1次匹配，支持final字段的初始赋值；如果没有指定<token值>，则默认匹配所有TOKEN；如果多个 | (或判断)没有匹配，switchdefault 抛出异常；
- (...)?：对应判断操作匹配0-1次，如果多个 | (或判断)没有匹配，switch default 不抛出异常；
- [...] ：对应判断匹配0-1次，与(...)?类似
抽象语法树
在Calcite中，基于SqlNode表示AST抽象语法树，一个SqlNode可对应语法树中的一个节点，即对应SQL语句中的一个元素。SqlNode是一个抽象类，拥有许多子类，每个子类代表SQL语法中一类元素，主要包括：
- SqlCall：代表SQL运算符(operator)调用，有很多关系运算相关的扩展子类，如 SqlJoin、SqlFilter；也可以用于描述语法结构，如 SELECT(SqlSelect)、INSERT(SqlInsert)
- SqlIdentifier：代表 SQL标识符，例如表名、列名等
- SqlLiteral：代表 SQL字面量，例如字符串、数字、日期等
- SqlDataTypeSpec：代表数据类型规范，描述数据类型的各种属性，包括基本类型、精度、字符集等
在Calcite中，SqlOperator代表SQL语句中的运算符，可通过SqlCall调用执行，其子类包括：数学运算符、比较运算符、逻辑运算符、自定义SQL函数(SqlFunction)。
如图所示：一条SQL语句基于SqlParser解析后，转换为SqlNode语法树结构：
总结
语法解析是SQL处理的前提和基础，目前由于不同的计算引擎SQL方言不同，因此SQL解析处理模式也大相径庭。从整体上看，SQL解析将SQL转为AST抽象语法树，该语法树是朴素的，无元数据绑定的，也无法直接进行查询优化。但基于语法树遍历，也可以挖掘丰富的SQL执行信息，如目标库表、数据血缘、防御SQL注入攻击、热度分析等。除此之外，基于语法树也可以进行SQL改写处理，识别特定节点并变更后，再将语法树转为改写后的SQL执行。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。