type
status
date
slug
summary
tags
category
icon
password
第四章 Spark SQL 编译器 Parser
如果不算存储过程等扩展功能，则 SQL 可以被看作是一种领域特定语言（Domain Specific Language），简称 DSL。DSL 的构建与通用编程语言的构建类似，主要的过程仍然是指定语法和语义，然后实现编译器或解释器。通常情况下，一个系统中 DSL 模块的实现需要涉及两方面的工作：
1）设计语法和语义，定义 DSL 中具体的元素；
2）实现词法分析器（Lexer）和语法分析器（Parser），完成对 DSL 的解析，最终转换为底层
逻辑来执行。
ANTLR4 是进行 Spark SQL 开发的基础。ANTLR (Another Tool for Language Recognition）是目前非常活跃的语法生成工具，用 Java 语言编写，基于 LL（＊）解析方式，使用自上而下的递归下降分析方法。ANTLR 可以用来产生词法分析器、语法分析器和树状分析器（Tree Parser）等各个模块，其文法定义使用类似 EBNF (Extended Backus-Naur Form）的方式，简洁直观。
ANTLR 的简单使用
以简单的四则运算为例，使用 ANTLR4 构建计算器。在 ANTLR4 中，词法和语法可以放在同 G4 文件中，词法单元以大写字母开头，语法单元以小写字母开头，以作区分。
基于 Calculator 文法文件，可以直接在命令行下或 MAVEN 中调用 ANTLR4 生成相应的
代码。
其中：
1）Calculator.tokens 和 CalculatorLexer.tokens 是内部的 Token 定义
2）CalculatorLexer 和 CalculatorParser 是生成的词法分析器和语法分析器
3）剩下的 Java 文件代表着两种访问语法树的方式。
CalculatoListener 和 CalculatoBaseListener 对应监听器模式，
CalculatorVisitor 和 CalculatoBaseVisitor 对应访问者模式
基于生成的代码，开发人员只要实现语法树遍历过程中的核心逻辑即可，可以在监听器模式和访问者模式中任意选择。
考虑到 Spark SQL 编译器中主要采用 Visitor 方式，这里在 CalculatorBaseVisitor 的基础上继承自己的类，重载其中的关键方法代码。
这里，addOrSubtract 标签对应于 visitAddOrSubstract 方法，在其中实现加减法的逻辑，而 visitFloat 方法和 float 标签一一对应，完成浮点数的解析。
实现了 Visitor 中的关键逻辑以后，就可以直接调用 ANTLR4 生成的各个模块了，驱动程序如下，根据输入的字符流相继构造词法分析器（Lexer）和语法分析器（Parser），然后 建相应 Visitor 来访问语法分析器解析得到的语法树，最后返回结果。
运行后输出 9.81，得到计算结果。
SparkSqlParser
回到 Spark SQL, Catalyst 中提供了直接面向用户的 ParseInterface 接口，该接口中包含了对 SQL 语句、 Expression 表达式和 Table Identifier 数据表标识符的解析方法。AbstractSqlParser 是实现了 ParseInterface 的虚类，其中定义了返回 AstBuilder 的函数。
当面临开发新的语法支持时，首先需要改动的是 ANTLR4 文件（在 Sq1Base.g4 中添加文法），重新生成词法分析器（SqlBaseLexer）、语法分析器（SqlBaseParser）和访问者类（SqlBaseVisitor 接口与 SqlBaseBaseVisitor 类），然后在 AstBuilder 等类中添加相应的访问逻辑，最后添加执行逻辑。
常见 SQL 生成的抽象语法树概览
对应的语法树如下：
从语法树可以看到，SingleStatementContext 是根节点，但是在访问该节点时一般什么都不做，只递归访问子节点。整个遍历访问操作中比较重要的是包含多个子节点的节点，例如
QuerqecificationContext 节点，一般将数据表和具体的查询表达式整合在一起。左边的一系列节点对应 select 表达式中选择的列，中间的 FromClauseContext 为根节点的系列节点对应数据
表，右边的一系列节点则对应 where 条件中的表达式。
上述语法树的结构比较通用，其他类型的 SQL 语句生成的语法树大同小异，这里假设在上述语句中加入排序的操作。
对应的语法树如下：
可以看到新的语法树在 queryOrganizationContext 节点下面加入了 SortItemContext 节点，代表数据查询之后所进行的排序操作。一般来讲，QueryOrganizationContext 为根节点所代表的子树中包含了各种对数据组织的操作，例如 Sort、Limit、Window 算子等。