自己实现一个SQL解析引擎

功能：将用户输入的SQL语句序列转换为一个可执行的操作序列，并返回查询的结果集。
SQL的解析引擎包括查询编译与查询优化和查询的运行，主要包括3个步骤：
查询分析：
制定逻辑查询计划（优化相关）
制定物理查询计划（优化相关）
查询分析：将SQL语句表示成某种有用的语法树.
制定逻辑查询计划：把语法树转换成一个关系代数表达式或者类似的结构，这个结构通常称作逻辑计划。
制定物理查询计划：把逻辑计划转换成物理查询计划，要求指定操作执行的顺序，每一步使用的算法，操作之间的传递方式等。
查询分析各模块主要函数间的调用关系:

图1.SQL引擎间模块的调用关系

FLEX简介

flex是一个词法分析工具，其输入为后缀为.l的文件,输出为.c的文件. 示例是一个类似Unix的单词统计程序wc。

%option noyywrap
%{
    int chars = 0;
    int words = 0;
    int lines = 0;
%}

%%

[_a-zA-Z][_a-zA-Z0-9]+ { words++; chars += strlen(yytext); }
\n { chars++ ; lines++; }
.  { chars++; }

%%

int main()
{
       yylex();
       printf("%8d %8d %8d\n",lines,words,chars);
    return 0;
}

.l文件通常分为3部分：

%{
    definition
%}

%%
    rules
%%
    code

definition部分为定义部分，包括引入头文件，变量声明，函数声明，注释等，这部分会被原样拷贝到输出的.c文件中。

rules部分定义词法规则，使用正则表达式定义词法，后面大括号内则是扫描到对应词法时的动作代码。

code部分为C语言的代码。yylex为flex的函数，使用yylex开始扫描。

%option 指定flex扫描时的一些特性。yywrap通常在多文件扫描时定义使用。常用的一些选项有

noyywrap 不使用yywrap函数

yylineno 使用行号

case-insensitive 正则表达式规则大小写无关

flex文件的编译

    flex  –o wc.c wc.l
    cc wc.c –o wc

Bison简介

Bison作为一个语法分析器，输入为一个.y的文件,输出为一个.h文件和一个.c文件。通常Bison需要使用Flex作为协同的词法分析器来获取记号流。Flex识别正则表达式来获取记号，Bison则分析这些记号基于逻辑规则进行组合。

计算器的示例：calc.y

%{
#include 
%}

%token NUMBER
%token ADD SUB MUL DIV ABS
%token OP CP
%token EOL

%%

calclist:
    | calclist exp EOL {printf("=%d \n> ",$2);}
    | calclist EOL {printf("> ");}
    ;
exp: factor
    | exp ADD factor  {$$ = $1 + $3;}
    | exp SUB factor  {$$ = $1 - $3;}
    ;
factor:term
    | factor MUL term {$$ = $1 * $3;}
    | factor DIV term {$$ = $1 / $3;}
    ;
term:NUMBER
    | ABS term ABS { $$ = ($2 >= 0   $2 : -$2);}
    | OP exp CP    { $$ = $2;}
    ;
%%
int main(int argc,char *argv[])
{
    printf("> ");
    yyparse();

    return 0;
}
void yyerror(char *s)
{
    fprintf(stderr,"error:%s:\n",s);
}

Flex与Bison共享记号，值通过yylval在Flex与Bison间传递。对应的.l文件为

%option noyywrap
%{
#include "fb1-5.tab.h"
#include 
%}

%%
"+" { return ADD;}
"-" { return SUB;}
"*" { return MUL;}
"/" { return DIV;}
"|" { return ABS;}
"(" { return OP;}
")" { return CP;}
[0-9]+ { 
                 yylval = atoi(yytext);
                 return NUMBER;
           }

\n { return EOL; }
"//".*

[ \t] {}
"q" {exit(0);}
.   { yyerror("invalid char: %c\n;",*yytext); }
%%

Bision文件编译

    bison -d cacl.y
    flex cacl.l
    cc -o cacl cacl.tab.c lex.yy.c

通常，Bison默认是不可重入的，如果希望在yyparse结束后保留解析的语法树，可以采用两种方式，一种是增加一个全局变量，另一种则是设置一个额外参数，其中ParseResult可以是用户自己定义的结构体。

%parse-param {ParseResult *result}

在规则代码中可以引用该参数：

stmt_list: stmt ';'  { $$ = $1; result->result_tree = $$; }
| stmt_list stmt ';' { $$ = (($2 != NULL)  $2 : $1); result->result_tree = $$;}

调用yyparse时则为：

ParseResult p;

yyparse(&p);

SQL解析引擎中的数据结构

语法树结构

在实现的时候可以把语法树和逻辑计划都看成是树结构和列表结构，而物理计划更像像是链式结构。树结构要注意区分叶子节点（也叫终止符节点）和非叶子节点（非终止符节点）。同时叶子节点和非叶子节点都可能有多种类型。

语法树的节点：包含两个部分，节点的类型的枚举值kind，表示节点值的联合体u，联合体中包含了各个节点所需的字段。

typedef struct node{
   NODEKIND kind;

   union{
         //...
           /* query node */
         struct{
             int         distinct_opt;
              struct node *limit; 
              struct node *select_list;
              struct node *tbl_list;
              struct node *where_clause;
              struct node *group_clause;
              struct node *having_clause;
              struct node *order_clause;
         } SELECT;
         /* delete node */
        struct{
            struct node *limit;
            struct node *table;
            struct node *where_clause;
            struct node *group_clause;
         } DELETE;
/* relation node */
          struct{
                char

自己实现一个SQL解析引擎(一)

自己实现一个SQL解析引擎

FLEX简介

Bison简介

SQL解析引擎中的数据结构

语法树结构