前言
SQL 编译与执行系列技术博客将按照以下顺序分别介绍整个 SQL 执行引擎。
图一 SQL 编译与执行研读流程
本文作为本系列第一篇文章，首先为大家介绍 parser 的核心设计，主要包括 SQL 词法以及语法的解析。
一、SQL 执行流程
图二所示为一条 SQL 语句的整体处理流程，总体来说，一条 SQL 语句需要经过下述步骤：parser—构建逻辑计划—构建优化计划—构建物理计划—构建执行计划。
图二 SQL 执行流程
parser 过程最主要的目的就是解析输入的 SQL 语句，通过词法解析器解析为 token，通过语法解析器生成抽象语法树，而后即可传入 SQL 执行引擎进行识别和处理。
接着进入下一步，首先要对输入的数据进行有效性验证，解析并转换 AST 树，构建逻辑计划。接下来就是对生成的计划进行优化以找到代价最小的执行方式，根据优化好的逻辑计划构建可执行的物理计划，最后下发到各个节点进行分布式执行。
二、Lex & Yacc
Lex 代表 Lexical Analyzar（词法分析器），Yacc 代表 Yet Another Compiler Compiler（编译器代码生成器）。它们分别是用来生成词法分析器和语法分析器的工具，Lex 和 Yacc 在 UNIX 下分别叫 Flex 和 Bison。
词法解析是编译的第一步，将语句拆分为 token，移除空格和注释，逐个读入源码中的 character，检查是否有效并传递给语法分析器。语法分析器以 token-stream 的形式从词法分析器获取输入；解析器根据规则文件生成的规则将 token 解析成一个抽象语法树的结构，如图三所示。
图三 Lex & Yacc 执行流程
从上图的执行流程可以看出，我们需要分别为 Lex 和 Yacc 提供对应的规则文件，Lex & Yacc 根据给定的规则，生成符合需求的词法分析器和语法分析器。一般这两种配置都是文本文件且结构相同：
... definitions ...%%... rules ...%%... subroutines …
复制代码
文件通过 %% 分成三部分，最上面定义了各种名称，例如各种表达式、token 等，中间则是重点的规则，首先看一下 Lex 的规则文件：
...%%/* 变量 */[a-z] { yylval = *yytext - 'a'; return VARIABLE; } /* 整数 */[0-9]+ { yylval = atoi(yytext); return INTEGER; }/* 操作符 */[-+()=/*\n] { return *yytext; }/* 跳过空格 */[ \t] ;/* 其他格式报错 */. yyerror("invalid character");%%…
复制代码
对于词法解析对应的规则，可以看出，左边是扫出来的字符内容，通过正则表达式进行匹配，如果匹配到即返回右边大括号中运行的结果。再看看 Yacc 对应的规则文件：
%token INTEGER VARIABLE%left '+' '-'%left '*' '/'...%%program: program statement '\n' | ;
statement: expr { printf("%d\n", $1); } | VARIABLE '=' expr { sym[$1] = $3; } ; expr: INTEGER | VARIABLE { $$ = sym[$1]; } | expr '+' expr { $$ = $1 + $3; } | expr '-' expr { $$ = $1 - $3; } | expr '*' expr { $$ = $1 * $3; } | expr '/' expr { $$ = $1 / $3; } | '(' expr ')' { $$ = $2; } ;%%…
复制代码
首先是定义了 token 以及一些运算符。%left 代表左结合，同一行的运算符优先级是一样的，不同行的越靠下优先级就越高。
语法规则使用了巴科斯范式（BNF）定义，它不仅能严格地表示语法规则，而且所描述的语法是与上下文无关的。它具有语法简单，表示明确，便于语法分析和编译的特点。每条规则的左部是一个非终结符，右部是由非终结符和终结符组成的一个符号串。具有相同左部的规则可以共用一个左部，各右部之间以直竖“|”隔开。
解析表达式是生成表达式的逆向操作，我们需要归宿表达式到一个非终结符。Yacc 生成的语法分析器使用自底向上的归约（shift-reduce）方式进行语法解析，同时使用堆栈保存中间状态。简单的以一条 select 为例：
// 有引号的代表终结符，没有的代表非终结符。SelectStmt: // 代表从哪些表里获取到哪些字段 SelectFiled FromTableSelectFiled: // FieldList 代表着一个字段列表 “Select” FieldList | “Select” “*”FromTable: // 从一个表列表中获取 “From” TableListFieldList: // FieldList 可以是某个字段，也可以是多个字段，利用递归可以扩展到无数字段 “Field” | FieldList “,” “Field”TableList: // TableList同理 “Table” | TableList “,” “Table”
复制代码
当语法分析器进行语法分析的时候，用 . 代表当前读取到的位置，以 SELECT * FROM test 为例：
SELECT . * FROM test// 匹配到终结符SELECT，继续执行→ SELECT * . FROM test// 此时堆栈里的内容匹配到 SelectFiled，将 SELECT *弹出，SelectFiled 压入到堆栈→ SelectFiled . FROM test→ SelectFiled FROM . test→ SelectFiled FROM test .→ SelectFiled FROM TableList .→ SelectFiled FromTable .→ SelectStmt
复制代码
通过一系列的转换，我们就获得了一个 SelectStmt，而整个过程就可以构造一棵树，用于 SQL 解析。上述所示仅为一个简单的例子，真实使用的结构则会复杂的多。
三、SQL parser
开务数据库使用了 Goyacc 生成语法分析器，而 Lex 则是手写出来的，实现了 Goyacc 中要求的接口，对应 sql/pkg/sql/parser/scan.go pkg/sql/parser/lexer.go，实现了词法分析的功能。
语法分析器所对应的功能在 sql.y 文件下。该文件仍符合上文所述 Yacc 规则文件格式，但没有第三部分 subroutines，第一部分主要就是对一些 token、表达式、优先级、结合性的定义，其中有一个 union 结构体。
%union { id int32 pos int32 str string union sqlSymUnion}
复制代码
该结构体会在 sql.go 生成文件里面生成一个对应的结构体，主要用来定义表达式和 token 的类型，存放解析过程中 token 的相关变量信息以及最后生成的 AST 信息。此外，还有一些对 token（终结符）和表达式（非终结符）的定义。
%token <str> IDENT SCONST BCONST BITCONST…%type <tree.Statement> stmt_block%type <tree.Statement> stmt…%left AND%right NOT%left AND_AND%nonassoc IS ISNULL NOTNULL %nonassoc '<' '>' '=' LESS_EQUALS GREATER_EQUALS NOT_EQUALS…%%
复制代码
下面是关于 rule 的定义，以 create table 为例：
create_table_stmt: CREATE opt_temp_create_table TABLE table_name '(' opt_table_elem_list ')' opt_interleave opt_partition_by opt_table_with opt_create_table_on_commit { name := $4.unresolvedObjectName().ToTableName() $$.val = &tree.CreateTable{ Table: name, IfNotExists: false, Interleave: $8.interleave(), Defs: $6.tblDefs(), AsSource: nil, PartitionBy: $9.partitionBy(), Temporary: $2.persistenceType(), StorageParams: $10.storageParams(), OnCommit: $11.createTableOnCommitSetting(), } }| CREATE opt_temp_create_table TABLE IF NOT EXISTS table_name '(' opt_table_elem_list ')' opt_interleave opt_partition_by opt_table_with opt_create_table_on_commit { name := $7.unresolvedObjectName().ToTableName() $$.val = &tree.CreateTable{ Table: name, IfNotExists: true, Interleave: $11.interleave(), Defs: $9.tblDefs(), AsSource: nil, PartitionBy: $12.partitionBy(), Temporary: $2.persistenceType(), StorageParams: $13.storageParams(), OnCommit: $14.createTableOnCommitSetting(), } }
复制代码
可以看出，除了上述所说的一些终结符和非终结符外，还有一个大括号，大括号里面的内容就是当匹配时进行的一些操作，主要就是构建出所需要的 AST。
其中 1对应的就是匹配到的第一个字符，4 就是 table_name 这一部分，最后产生的 CreateTable 这个结构体就对应着 tree 包下的结构体。
type CreateTable struct { IfNotExists bool Table TableName Interleave *InterleaveDef PartitionBy *PartitionBy Temporary bool StorageParams StorageParams OnCommit CreateTableOnCommitSetting Defs TableDefs AsSource *Select}
复制代码
通过生成的 sql.go 中的 parse 就可以将 token-stream 生成一个 AST 对应的结构。
总结
以上就是开务数据库的 SQL parser 词法解析和语法解析部分，主要是语法解析部分使用 Goyacc 工具将 sql.y 中的规则生成对应的语法分析器，将词法分析器生成的 token-stream 解析成制定好的树结构。具备这些基础后，我们就可以进行语法的添加以及修改，增加更多的解析规则，为后续操作做好准备。
END
评论