前言

SQL 编译与执行系列技术博客将依照以下程序别离介绍整个 SQL 执行引擎。

图一  SQL 编译与执行研读流程

  • parser 局部，包含词法解析和语法解析。
  • compile 局部，包含语义解析以及打算的构建。
  • optimize 局部，包含打算的优化。
  • exec 局部，包含执行打算的生成以及执行。

本文作为本系列第一篇文章，首先为大家介绍 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