一、术语
-
关键词（Lexis）
-
关键词是一组预定义的单词，为系统内置，区别于变量（Variable）。
-
语法（Syntax）
-
关键词、变量的摆放顺序
-
语义（Semantics）
-
由关键词和语法共同表达出的含义，即语言的含义。在编程语言中，通常不考虑修辞等语用信息。
-
词法分析
-
给定一段文本，建立文本中的单词和关键词/变量之间的映射的过程。产生符号表（Token List）
图 1.1 词法分析示意图
-
语法分析
-
将词法分析的产物与语法关联的过程。产生抽象语法树（Abstract Syntax Tree）
-
抽象语法树：一种基于多叉树的数据结构，定义了SQL语句中，关键词（Lexis）的摆放顺序，即：语法（Syntax）
图 1.2 语法分析示意图
-
终结符集合： 一个有限集合，其元素称为 终结符（terminal）； 编程语言中，将保留词定义为终结符。
-
非终结符集合：一个有限集合，与终结符集合无公共元素，其元素称为 非终结符（non-terminal）；
-
语义分析
-
基于抽象语法树和预定义的分析原则，也称为语言规范、产生式等，对语法树进行的遍历，通常产生与语法分析输入的文本不同类型的另一种语言。
-
上下文无关的分析：在实现上即基于 上下文无关的产生式 ，对抽象语法树进行遍历，根据产生式决定同时参考的节点数量，生成目标语言的过程。一段语义可能需要多个关键词和非关键词进行组合才可以表达，因此有时需要参考抽象语法树的子树才可以确定语义。
-
SQL语法是上下文无关文法
-
用常见的select子句的产生式为例：
-
querySpecificationNointo ⇒ SELECT selectSpec* selectElements fromClause? groupByClause? havingClause windowClause? orderByClause? limitClause?;
-
产生式的右侧为： querySpecificationNointo 是（ 非终结符 ），描述了一段语义；
-
表达式右侧不包含SQL关键字（ 终结符 ）；
-
图 1.3 语义分析示意图
-
执行方案（Execution Plan）
-
执行方案是执行引擎的运行时配置文件，程序读取执行方案，对执行方案进行解释--执行对应指令，产生目标数据。
-
在执行之前，可以利用各种策略，进行执行方案的优化。
二、SQL 执行过程
2.1 SQL执行步骤
-
SQL执行本质上是将SQL语句翻译成执行方案，再由执行引擎读取执行方案进行执行文件操作、计算的过程。
-
具体来讲，包含词法分析（Lexical Analysis）、语法分析（Syntax Analysis）、语义分析（Semantic Analysis）、执行方案生成（Execution Plan Generation）、执行方案优化（Execution Plan Optimization）等阶段。
2.2 关键阶段
-
其中，难度较大的步骤是 语义分析 与 执行方案优化 。
-
语义分析是整个流程中，第一次将输入的语言翻译为另外一种语言的过程。
-
由于语言之间的转译并不是一一对应的关系，在语言翻译时，需要综合考虑，调整单词的顺序、减少单词数量等。
-
举一个不恰当的例子，比如汉语“我 来自 中国。”翻译成英语“I come from China.”两句话表达了相同的语义，汉语用到了3个单词，英语用到了4个，因此在翻译时需要综合考虑。编程语言的转译过程与此类似，只不过编程语言没有修辞手法并且语法固定，比较适合用形式化的产生式进行描述，进而实现自动化翻译（即，编译)。
-
-
执行方案优化是按照各种场景构造优化策略加以解决的问题，并无通法。
-
比如常见的where子句优化：where a.id = 1 and 1 = 1 ⇔ where true；执行计划优化时，此where子句会被删去，因为它并没有对最终结果产生任何影响。
2.2 AST Visitor
-
AST Visitor是对SQL抽象语法树进行访问的工具，方便我们对抽象语法树进行遍历，在遍历语法树节点时作相应的动作，即副作用，是生成执行方案的基础。
参考资料
SQL解析工具库
-
druid.sql中的ast模块： https://github.com/alibaba/druid
-
druid中的抽象语法树和Visitor是预先构造好的。
-
antlr可以用于构造抽象语法树和Visitor： https://github.com/antlr/antlr4
-
构造抽象语法树和Visitor需要基于语法文件（关键词+语法规则产生式） https://github.com/antlr/grammars-v4
-
Apache calcite：用于构建数据库和数据管理系统的开源框架。它包括一个SQL解析器，基于关系代数构建表达式的API和查询计划引擎。
编译原理学习
