【手写数据库核心揭秘系列】第6节 SQL词法分析器秘密

SQL词法分析器

一、概述

SQL解析的第一步就是对输入的SQL进行分词，也就是拆分成最小的语言组成单元。

词法分析之前需要定义一套分词规则，比如按语句中的空格先分隔成一系列的token，对于各种数据类型对应的值，当然不能对它们拆分，每个值都是一个整体，比如1.28就是一个浮点数，而I love the city是一个字符串，不能把字符串中的空格再拆分。

在这里插入图片描述

二、SQL分词器

现在我们就来使用flex实现一个创建表的SQL语句的分词器。

2.1 模版代码

根据flex的语法先创建一个代码框架，按格式分为三部分，第三部分程序部分只是调用主程序执行分flex分词主函数yylex，而每个模式对应的动作是将匹配到的token输出到标准输出。

%{
#include <stdio.h>
#include <string.h>

%}
%%

%%
int main(int argc, char *argv[])
{
yylex();
}

int yywrap()
{

}

这其实就是上一个demo的框架，内容全部删除了，保留了头文件的引用，因为后面要用到标准输出，其它都是必须要保留的内容。虽然这个代码非常简单，它也是可以运行的，不信你可以用上面的编译方法试一试。

2.2 创建表词法

创建表的语句长的模样是这样：

sql">CREATE TABLE table_name ( col_name1 typename, col_name2 typename, …);

语法说明：

固定格式中 CREATE TABLE是关键词，代表命令；
table_name 是被创建的表的名称，一般在64字符以内；
括号中的内容是表的字段定义，也叫做列的定义列表，由列名称和类型组成，中间用逗号分隔；类型名称是数据库内部支持的类型，名称在这里并不作过多校验；
这里的表名，列名都是用户定义的字段，也叫做标识符，与C语言中变量定义类似，需要遵守一定规则，这里就定为字母、数字组成，首字符必须是字母，这样与数字可以区分。
需要注意的是，标识符在有些数据库中大小写是敏感的，有些不敏感，这里也统一为大小写不敏感，内部按小写字母来处理。
在SQL语句中，空格的多少并不影响本身的含义，在解析时会将多余的空白符号忽略掉，除了空格，还有回车换号、TAB、注释都算作是空白字符。
每条SQL语句都以分号作为结尾符，这个符号需要被单独分词，同样的还有括号、逗号等。

分词模式按照关键字，用户标识，空白符号，标号四种类型来定义，其中关键字是SQL标准中定义的内容，数量有限，在这里直接原样匹配，类型名称按照用户标识进行分词即可，其实只需要定义用户标识、空白符号和标号三种。

2.3 空白字符模式定义

在flex使用正则表达式的方法，来定义空白字符。

在flex模式定义部分之前，还可以定义一些模式的标签，在其它模式中引用，下面就是先来定义对应的模式标签，比如space、nonewline等，这样会比较方便引用，同时整个模式定义部分比较简洁。

space       [ \t\n\r\f]
nonewline   [^\n\r]
comment     ("--"{nonewline}*)
whitespace		({space}+|{comment})

空白符号定义分为两种，一种是空白的分隔符，如空格，TAB为\t, 回车换行 \r\n，还有换页 \f。

正则表达式中，[]中的字符列表是或的关系，匹配其中一个即可满足。另一种是注释，SQL的注释是以--开头，直到一行的结束，也就是换行符为止。

nonewline定义了匹配一行中除换行符外的任意字符的模式，^在[]是非的意思；
comment的定义为以--开头，任意个字符组成的注释，( )中是一个表达式，这个表达式由三部分组成，开头为--，紧接着为非换行符以外的任意一个字符，然后*表示前面字符的数量可以是零个或任意多个。
whilespace 模式定义为至少一个空白分隔符或者为注释内容，+表示前面字符数量大于零，|表示或的意思，可以是两者之一。

2.4 用户标识符模式定义

用户标识符，包括表名，属性列的名称等，由用户定义。

identify    [a-zA-Z][a-zA-Z0-9_]*

按照用户标识符的规则，开头必须为字母，第一部分为大写或者小写字母中的一个；
第二部分可以是大小写字母，也可以是数字，或者是_下划线，其中0-9表示从0到9之间连续的数字；
第三部分为前一部分字符的数量可以是任意数量。

类型名称没有单独定义模式进行匹配，它也符合标识符的模式，类型名称的正确性校验，延迟到语义解析步骤。

2.5 标号模式定义

在一个完整的SQL语句中，含有一些标识符号，比如多个属性列之间用逗号分隔，属性列用括号包围等，它们也是一个最小的组成单元，要能单独成token。

flagself	[,().;\+\-\*\/\%\<\>\=]

标号除了前面提到的逗号、括号外，还有运算符号如加号、减号、乘号、除号、取模，还有比较运算符如小于、大于和等于号，这里的\表示转义；
在正则表达式中有特殊含义的符号经过转义后表示它本身，比如*在正则表达式中表示数量为任意个，经过转义后表示星号这个符号。

2.6 分词动作定义

当提到了一个最小的语言单元，也就是token之后，需要做什么？这就是每个模式可以定义对应的执行动作的代码，它是由C语言编写的。

%% 
CREATE          {printf("%s\n", yytext); }
TABLE	        {printf("%s\n", yytext); }
{identify}      {printf("%s\n", yytext);}
{flagself}      {printf("%s\n", yytext); }
{whitespace}    {; /* ignore */}
%%

四种模式对应的动作，在这里目前无需处理，为了调试方便，每个模式都将输出对应模式匹配到的token，所以只需要printf输出即可。在模式匹配到分词之后，flex会将它存储在yytext这个全局变量当中，在对应动作中可以使用它来获得分词结果。

这里的CREATE、TABLE就是字符串本身，可以在flex程序的声明部分增加大小写不敏感的参数设置，这样大写和小写都可以匹配得上。
标识符模式，也就是表名，属性列名，当然这里类型名也包括在内；
标号模式；
空白字符；对于这样的token，直接忽略即可，在后面不对它们进行处理。

2.7 参数设置

在声明部分增加两个参数，第一个是大小写不敏感设置；第二个是没有yywrap这个接口的设置，这样在程序部分简化掉yywrap这个空函数了，代码更加简洁。

%option case-insensitive
%option noyywrap

最终的代码如exam_02/sqlscanner.l文件中所示。

值得注意的是，flex程序中的参数设置和标签定义部分都在前面介绍的程序结构的三部分之外，当然必须在使用前定义。

删除表的词法分析也是类似的处理，只需要添加关键词部分即可，其它并没有新增的模式规则；至于其它的SQL语句的词法分析，我们在用到它时再进行添加。

三、开发模式说明

整个数据库内核开发的过程，采用一种增量开发的模式，并不会盯住一个模块将它做到最终的样子，那样需要考虑的东西太多，整个都需要详细分析清楚才能完成。而恰恰相反，增量开发模式只需要将当前能够分析清楚的部分先完成，达到当前的目标即可，而后可以再进一步的做其它事情，如果需要再添加或修改，那么再继续，到那候又可以看到很多不一样的东西。

这种开发模式的好处是，可以很快开发出来原型，有原型之后就非常直观的感受差异，原型与目标之间还缺少什么，或者产生了偏离，能够很清晰的进行定义和描述，开发也会变得很高效。

四、测试SQL

先使用flex编译生成C语言代码，然后使用gcc编译生成可执行程序。

[senllang@hatch exam_02]$ flex sqlscanner.l 
[senllang@hatch exam_02]$ gcc lex.yy.c -o sqlscanner[senllang@hatch exam_02]$ ./sqlscanner 
please intput SQL.
create table student(id int, name varchar,address varchar);
create
table
student
(
id
int
,
name
varchar
,
address
varchar
)
;