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，主要涉及以下三个文件：

1. config.fmpp：FreeMarker配置文件，描述可扩展的解析配置，包括：解析包名/类名、类引用、keywords(关键字)、nonReservedKeywords(非保留关键字)等常见定义
2. xxx.ftl：FreeMarker模板文件，描述Java生成类的结构和内容，包括：类定义、方法定义、变量定义等
3. 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解析器，基于正则文法匹配对应类型，分为四类：

1. SKIP：词法解析忽略处理
2. MORE：需继续读取下一个文本符
3. TOKEN：匹配TOKEN
4. 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语法中一类元素，主要包括：

1. SqlCall：代表SQL运算符(operator)调用，有很多关系运算相关的扩展子类，如 SqlJoin、SqlFilter；也可以用于描述语法结构，如 SELECT(SqlSelect)、INSERT(SqlInsert)
2. SqlIdentifier：代表 SQL标识符，例如表名、列名等
3. SqlLiteral：代表 SQL字面量，例如字符串、数字、日期等
4. SqlDataTypeSpec：代表数据类型规范，描述数据类型的各种属性，包括基本类型、精度、字符集等

在Calcite中，SqlOperator代表SQL语句中的运算符，可通过SqlCall调用执行，其子类包括：数学运算符、比较运算符、逻辑运算符、自定义SQL函数(SqlFunction)。

如图所示：一条SQL语句基于SqlParser解析后，转换为SqlNode语法树结构：

总结

语法解析是SQL处理的前提和基础，目前由于不同的计算引擎SQL方言不同，因此SQL解析处理模式也大相径庭。从整体上看，SQL解析将SQL转为AST抽象语法树，该语法树是朴素的，无元数据绑定的，也无法直接进行查询优化。但基于语法树遍历，也可以挖掘丰富的SQL执行信息，如目标库表、数据血缘、防御SQL注入攻击、热度分析等。除此之外，基于语法树也可以进行SQL改写处理，识别特定节点并变更后，再将语法树转为改写后的SQL执行。

我正在参与2024腾讯技术创作特训营最新征文，快来和我瓜分大奖！