数据库实现中会涉及到很多关键技术，SQL引擎、存储引擎、事务等，在SQL引擎中，第一件事就是识别用户的SQL。而识别用户SQL的第一步就是词法分析。
SQL解析器
我们知道数据库用户通过SQL来操作数据库，那么数据库怎么识别出SQL呢？ 比如select * from t。编译原理好像告诉了我们答案。SQL语句在数据库管理系统中的编译过程符合编译器实现的常规过程，需要进行词法分析、语法分析和语义分析。
- 词法分析：从查询语句中识别出系统支持的关键字、标识符、操作符、终结符等，确定每个词自己固有的词性。词法分析是解析SQL语句的第一步，常用工具如flex。
- 语法分析：根据SQL语言的标准定义语法规则，使用词法分析中产生的词去匹配语法规则，如果一个SQL语句能够匹配一个语法规则，则生成对应的抽象语法树（abstract synatax tree，AST）。常用工具如Bison。
- 语义分析：对抽象语法树进行有效性检查，检查语法树中对应的表、列、函数、表达式是否有对应的元数据，将抽象语法树转换为查询树。
我们看一下非常流行的开源数据库PostgreSQL的实现，在PostgreSQL数据库的实现中，具体的词法分析是用flex实现的，所以我们需要学习一下flex。
flex
flex，词法分析工具，通常与bison一起协同工作。不止PG，其他很多数据库的SQL Parser中的词法语法分析部分就是用的flex和bison实现的。而数据库SQL解析器的开发有两种方案，自动生成和自己手工编写，各有利弊，PostgreSQL选择用flex和bison实现。
- 自动生成： 利用flex，bison等工具生成C、C++目标语言的词法、语法代码。
- 手工编写： 不用自动生成工具，自己编写这一部分的代码，好处是性能更好，针对SQL有更多的代码优化空间，不足是开发工作量大，需要长时间、大规模的测试才能趋于稳定，对开发人员要求很高。
源码在flex git source，整个代码量在1万行左右。核心原理是自动机，可以看一下源码，会对编写flex的.l文件帮助很大。
Lex解决冲突的两个规则：当输入的多个前缀与一个或多个模式匹配时，Lex用如下规则选择正确的词素：
- 总是选择最长的前缀
- 如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中先被列出的模式
正则表达式
在应用flex前中需要理解正则表达式。那么正则表达式是干什么的呢？为什么会有正则表达式出现呢？正则表达式就是一种描述字符串结构模式的形式化表达方法。我们看几个例子：
. 匹配除换行符（“\n”）以外的任何单个字符
* 匹配前面表达式的零个或多个拷贝
[] 匹配括号中的任意字符的字符类
[a-zA-Z]+ // 匹配单词
{} 当括号中包含一个或2个数字时，指示前面的模式被允许匹配多少次，例如`A{1,3}`，表示匹配字母A一次到3次。
+ 匹配前面的正则表达式的一次或多次出现。
？
正则表达式还有很多内容，比如匹配规则：
^: 表示该模式只匹配那些以^开头的字符串,例如^once表示该模式只匹配那些以once开头的字符串$: 用来匹配那些以给定模式结尾的字符串，例如bucket$。
更多的我们不再叙述，接下来我们看几个flex的例子，具体的可以参考gnu flex manual。
flex例子
先看一下最简单的例子，
/* 最简单的flex程序，echo */
%{
#include<stdio.h>
%}
%%
. | \n ECHO // 匹配任意字符，特殊动作ECHO输出匹配的模式
%%
void main() {
yylex();
}
功能类似于输入什么就输出什么，下面我们看一个有实际意义的例子。其实就是写正则表达式，匹配后需要做什么工作等。
/* simple flex example 字数统计例子 fbcount.l*/
// 声明部分, 会将 %{ %} 之间的内容直接拷贝到生成的C文件
%{
#include<stdio.h>
int chars = 0;
int words = 0;
int lines = 0;
%}
// 规则部分
%%
[a-zA~Z]+ { words++; chars += strlen(yytext); } // 变量yytext总是被设为指向本次匹配的输入文本
\n { chars++; lines++; } // 匹配换行符
. { chars++; } // 匹配任意字符
%%
void main() {
printf("%8d%8d%8d\n", lines, words, chars); // 输出统计信息
}
通过flex count.l生成lex.yy.cC程序，再编译c程序，gcc lex.yy.c -lfl，运行echo "asdf asd" | ./a.out即可查看运行结果。
再看一个例子，用flex识别单词。
%{
/* 单词识别程序 */
#include<stdio.h>
%}
%%
[\t ]+ ; // 忽略空白
red |
blue |
green |
yellow { printf("%s: is a color. \n", yytext); } // 匹配颜色
[a-zA-Z]+ { printf("%s: is not a color. \n", yytext); } // 匹配其他单词
. |
\n { ECHO;}
%%
void main() {
yylex();
}
看懂了上面几个例子后就可以分析一下PG源码scan.l了。
后记
词法分析部分，基本很少变化，PG中的词法分析部分源码解析可以参考一下这篇文章PostgreSQL中表名，列名的长度限制。我们后面还会再讲一下语法分析，学过编译原理的理解起来应该很快。这部分只需要理解怎么识别SQL的就好，不需要太深入。
参考文档：
