SQLite是一款C语言实现的轻型数据库，相较于传统的MySQL等数据库，其具有灵活快速，高可靠性，功能齐全的特点。SQLite是世界上最常用的嵌入式数据库引擎，内置于世界上绝大多数手机和其他设备中。本篇将着重于编译器的实现，及其与虚拟机（Virtual Machine）的联系，旨在借此使读者对于SQL内核和编译器部分的运行形成一个初步的认识。
如图所示，SQLite 由三个主要模块组成：内核、编译器、后端，下面对三个模块八个部分进行简要介绍。
SQLite库大部分公共接口由main.c,legacy.c和vdbeapi.c源文件中的函数来实现，比较常用的函数有sqlite3_open(),sqlite3_close(),sqlite3_exec()等等，可以通过包含头文件"sqlite3.h"进行调用，之后会通过一个具体的例子进行说明。
编译器共包含三部分，词法分析器（Tokenizer）、语法分析器（Parser）、代码生成器（Code Generator）。SQLite对SQL语句采用解释执行的方式，每读入一条语句，Tokenizer和Parser对其进行语法检查，然后生成语法树方便VDBE代码生成器使用，然后把语法树传给VDBE代码生成器（Code Generator）处理。代码生成器根据语法树生成VDBE的类汇编语言操作码。 最后传入Virtual Machine进行执行。
当执行一个包含SQL语句的字符串时，接口程序要把这个字符串传递给tokenizer。Tokenizer的任务是把原有字符串分割成一个个标识符（token），并把这些标识符传递给解析器。Tokenizer是用手工编写的，在C文件tokenize.c中。
Parser的工作是在指定的上下文中赋予标识符具体的含义。SQLite的语法分析器使用Lemon LALR(1)分析程序生成器来产生，Lemon做的工作与YACC/BISON相同，但它使用不同的输入句法，这种句法更不易出错。驱动Lemon的源文件可在parse.y中找到。
语法分析器在把标识符组装成完整的SQL语句后，就调用代码生成器产生虚拟机代码，以执行SQL语句请求的工作。代码生成器包含许多文件：attach.c, auth.c, build.c, delete.c, expr.c, insert.c, pragma.c, select.c, trigger.c, update.c, vacuum.c, where.c。expr.c处理SQL中表达式的代码生成。where.c处理SELECT、UPDATE和DELETE语句中WHERE子句的代码生成。文件attach.c, delete.c, insert.c, select.c, trigger.c, update.cvacuum.c处理同名SQL语句的代码生成（这些文件在必要时都调用expr.c和where.c中的例程）。所有其他SQL语句的代码由build.c生成。文件auth.c实现sqlite3_set_authorizer()的功能。 同时在SQL语句的代码生成器中也会完成对其相应的语义检查，譬如delete.c中的sqlite3IsReadOnly()的作用就是检查以确保给定的表是可写的，反之会传出一条错误消息。
代码生成器生成的代码由SQLite中专门处理数据库虚拟机（VDBE）来执行。VDBE全称为Virtual Database Engine，是一个专为操作数据库文件而设计的抽象计算引擎。它有一个存储中间数据的存储栈，每条指令包含一个操作码和不超过三个额外的操作数。
一个SQLite数据库使用B-树的形式存储在磁盘上，B-树的实现位于源文件tree.c中。数据库中的每个表和索引使用一棵单独的B-树，所有的B-树存放在同一个磁盘文件中。文件格式的细节被记录在btree.c开头的备注里。B-树子系统的接口在头文件btree.h中定义。
B-树模块以固定大小的数据块形式从磁盘上读取/修改信息，默认的块大小是1024个字节，但是可以在512和65536个字节之间变化。页处理器负责读、写和缓存这些数据块，并且提供事物回滚、事物提交，管理数据文件的锁定等功能。B-树从页处理器中请求特定的页，当它想修改页面、想提交或回滚当前修改时，它也会通知页处理器。页处理器的实现代码在pager.c中。页处理器接口在头文件pager.h中定义。
为了保证SQLite在不同操作系统中的可移植性，如Unix，Windows等，SQLite在OS接口中对其支持的各种操作系统进行了抽象化的实现，如Unix使用os_unix.c,Windows使用os_win.c等。每个特定操作系统的实现通常都有自己的头文件，如os_unix.h, os_win.h。
| 文件名称 | 主要功能 | 文件名称 | 主要功能 |
|---|---|---|---|
main.c | SQLite Library的大部分接口 | vdbeapi.c | 虚拟机提供上层模块调用的API实现部分 |
legacy.c | sqlite3_exec() | vdbe.c | 虚拟机的主要实现部分 |
table.c | sqlite3_get_table(), sqlite3_free_table() | vdbe.h | 定义了VDBE的接口，和VDBE中的指令，即struct VdbeOP |
prepare.c | sqlite3_prepare() | vdbeaux.c | vdbe.h的实现 |
tokenize.c | 词法处理器的实现，sqlite3GetToken() | btree.h | 定义了B-Tree提供的操作接口 |
parser.c | 语法分析处理器的实现，由parser.y和Lemon自动产生，sqlite3Parser() | btree.h | B-Tree的主要实现 |
parser.h | 语法分析器内部定义的关键字，由parser.y和Lemon自动产生 | pager.h | 定义Pager提供的接口 |
update.c, delete.c, insert.c, trigger.c, attach.c, select.c, where.c, vacuum.c, pragma.c, analyze.c | 处理相应的同名SQL语句 | pager.c | Pager模块的主要实现 |
expr.c | 处理SQL语句中的表达式 | os.h | 定义了为OS Interface之前模块所以提供的操作函数 |
alter.c | 实现ALTER TABLE功能 | os_win.c, os_unix.c, os_os2 | 对应操作系统的OS接口 |
build.c | 处理以下语法：CREATE TABLE, DROP TABLE, CREATE INDEX, DROP INDEX, BEGIN TRANSACTION, COMMIT, ROLLBACK | sqlite3.h | SQLite的头文件，定义了提供给其他应用使用的接口和数据结构 |
func.c | 实现SQL语句的函数语句 | sqliteInt.h | 定义了SQLite内部使用的接口和数据结构 |
date.c | 与日期和时间转换有关的函数 |
该部分旨在通过对Lemon的简单介绍来帮助读者对生成的语法分析器中的API有一个初步的认识，并且了解Lemon的工作机理。
Lemon是一款用C语言编写的LALR(1)类型语法分析器的生成器，其功能和特性与YACC/BISON类似，但是它要求的.y语法文件采用与YACC/BISON不同的语法。同时Lemon也具有简便灵活的特性，它的源码仅仅只有lemon.c中简短的4000余行代码。
通常运行lemon生成器时，先通过编译指令gcc lemon.c生成lemon.exe，然后需要两个输入文件：语法文件(.y) 、语法模板文件(lepar.c)。但通常只需要给出语法文件，如grammar.y,而不需要给出模板文件，因为Lemon自带一个设计完备的模板文件(lepar.c)，不过理论上可以另行设计其他模板文件，以满足特殊要求。
在生成lemon.exe的文件目录下，放入语法文件，如grammar.y，在命令行中执行命令lemon grammar.y即可生成如下三个后缀分别为.c, .h的文件，.c文件即为语法分析器文件，.h文件是为每一个终结符分配一个整数的头文件。
需要注意的是Lemon生成的语法分析器，并不是一个完整的程序，仅仅生成可为其他过程调用的一些子函数。其中的主要函数有ParseAlloc(), Parse(), ParseFree()。下面给出进行语法分析时的核心部分的代码以辅助理解各函数的作用：
Parser() { *Parser pParser = ParseAlloc(malloc); while( GetTOken( pString, &Tokenid, &Token) ) {Parse(pParser, Tokenid, Token); } Parse(pParser, 0, Token); ParseFree(pParser, free);} 首先，使用ParseAlloc()创建一个指向分析器Parse（相当于LALR(1)文法分析中符号栈）的指针pParser。
然后，对于输入的每一条SQL语句，通过while()循环，不断通过GetNextToken()对输入的符号流进行分割处理获取属性字，需要注意的是，GetNextTOken()并不是自动生成，而是手动编写的，如在SQLite中手动编写了tokenize.c文件。每次GetNextToken()都把相应的属性字的类放到终结符栈TOkenid中，把属性字的值放入Token中。
随之，将pParser, Tokenid, Token送入Parse()函数，进行语法分析。在上述while循环中，一直进行着先取得符号类和符号值，后送进分析器pParser的操作，直至到达符号流pString的末尾。
接着，以Parser(pParser, 0, Token)的形式，最终调用一次Parser()函数，以便结束语法分析。这一过程必不可少，因为必须要让Tokenid为0作为结束符（相当于LALR(1)文法分析中符号栈中最后要放入结束符#）。
最后，调用ParseFree()函数，释放语法分析器和由它所占用的空间。
不过对于Lemon比较有意思的一点在于，通过命令行加-c选项处理后，可以得到描述语法分析器中各状态以及相应的移进规约动作的.out文件，下图是一个用lemon简单实现的计算器的状态表，其中shift代表移进动作，reduce代表规约动作，accept代表接受状态，shift、reduce后的数字代表跳转到的相应状态。个人认为这对于LALR(1)文法的学习是一个很有意思的工具。
SQLite对SQL语句采用解释执行的方式，并不像C语言编译器先生成AST再对AST进行语义检查、代码生成，相反，当SQLite识别出规约状态后即调用内部的yy_reduce()函数，完成规约动作，同时对识别出的相应关键词，调用相应的代码生成器函数，如输入SQL语句为CREATE TABLE EXAMPLE，则在yy_reduce()中会调用sqlite3StartTable()函数，并执行相应的语义检查。当然这一过程涉及到相当多的中间函数，在之后的部分会对其核心过程进行阐明，并以一个简单的例子辅助说明。
分析源码可以发现，传入相应的代码生成器函数的并非是传统的AST，而是在<sqliteInt.h>定义好的Parse结构体，其结构较为复杂，核心成分为一个指向当前数据库的指针db，指向出错信息表的指针zErrMsg，指向虚拟机VDBE的指针pVdbe，详细定义可在附件中的<sqliteInt.h>中搜索struct Parse进行查询。
下面通过调用<sqliteInt.h>中的API实现一个具体的例子，来帮助读者对于SQLite函数调用的过程有一个初步的认识。
#include <stdio.h>#include <stdlib.h>#include <string.h>#include "sqlite3.h"int main(){ sqlite3 *db = NULL; int result; result = sqlite3_open("test.db", &db); if (result == SQLITE_OK) printf("Open test.db success!! \n"); else { printf("Open test.db error! \n"); exit(1); } const char *sqlStr = "create table table1(id integer primary key not null,name string);"; result = sqlite3_exec(db, sqlStr, 0, 0, 0); if (result == SQLITE_OK) printf("Create test.db success!! \n"); else { printf("Create test.db error! \n"); exit(1); } sqlite3_close(db); return 0;} 由此可以看出SQLite分析SQL语句的基本流程为
而通过对sqlite3_exec()源码分析可以得到其函数调用的主要过程，由于其细节较为复杂，故以核心函数的调用为主
下面对代码的运行过程进行调试观察
通过在result = sqlite3_exec(db, sqlStr1, 0, 0, 0)设置断点，进入sqlite3_exec()函数体内部，通过下图可以看到(db, sqlStr1, 0, 0, 0)已经传入：
在sqlite3RunParser()函数中有sqliteGetToken()函数对SQL语句进行分析，然后通过sqlite3Parser()规约出CREATE语句时，在解析器里就会执行sqlite3StartTable()函数，下图是sqlite3StartTable()函数的参数信息：
从图中我们可以看到表名table1已经在pName1中，虚表、视图和临时表标识都为0，pParse中保存着被分析解释过的SQL语句。
分析sqlite3StartTable()函数的源码可以发现，其功能就是创建表，在函数体中通过调用sqlite3FindTable()函数在main数据库中查找到这个表，然后创建了一个VDBE实例v，把OP_ReadCookie、OP_If、OP_Integer、OP_SetCookie、OP_CreateTable、OP_OpenWrite、OP_NewRowid、OP_Null、OP_Insert、OP_Close等VDBE操作码传入v的aOp中。
到此为止VDBE代码准备阶段，释放占用内存，代码从sqlite3_prepare_v2()中跳出。
下面我们以delete.c为例，对代码生成器部分的文件进行简要分析。
delete.c中的主要函数为以下几个：
Table sqlite3SrcListLookup()int sqlite3IsReadOnly()void sqlite3MaterializeView()Expr sqlite3LimiWhere()void sqlite3DeleteFrom()void sqlite3GenerateRowDelete()void sqlite3GenerateRowIndexDelete()int sqlite3GenerateIndexKey()由于实现过于复杂，以前三个为例进行讲解
Table *sqlite3SrcListLookup(Parse *pParse, SrcList *pSrc){ struct SrcList_item *pItem = pSrc->a; Table *pTab; assert( pItem && pSrc->nSrc==1 ); pTab = sqlite3LocateTable(pParse, 0, pItem->zName, pItem->zDatabase); sqlite3DeleteTable(pParse->db, pItem->pTab); pItem->pTab = pTab; if( pTab ){ pTab->nRef++; } if( sqlite3IndexedByLookup(pParse, pItem) ){ pTab = 0; } return pTab;} 函数的作用查找所有名字为pItem->zname的表进行语义分析，通过依次调用sqlite3LocateTableItem(), sqlite3LocateTable()函数进行查找，如果没有找到任何表，就调用sqlite3ErrorMsg()添加一个错误消息pParse - > zErrMsg并返回NULL。如果所有的表都找到，返回一个指针，指向最后一个表。
int sqlite3IsReadOnly(Parse pParse, Table pTab, int viewOk){if( ( IsVirtual(pTab)&& sqlite3GetVTable(pParse->db, pTab)->pMod->pModule->xUpdate==0 )|| ( (pTab->tabFlags & TF_Readonly)!=0&& (pParse->db->flags & SQLITE_WriteSchema)==0&& pParse->nested==0 )){ sqlite3ErrorMsg(pParse, "table %s may not be modified", pTab->zName); return 1;} 函数的作用是检查以确保给定的表是可写的。如果它不是可写的，调用sqlite3ErrorMsg()函数生成一条错误消息，并返回1。如果它是可写的，返回0。
void sqlite3MaterializeView( Parse pParse, / Parsing context / Table pView, / View definition / Expr pWhere, / Optional WHERE clause to be added / int iCur / Cursor number for ephemerial table /){ SelectDest dest; Select pDup; sqlite3 db = pParse->db; pDup = sqlite3SelectDup(db, pView->pSelect, 0); if( pWhere ){ SrcList pFrom; pWhere = sqlite3ExprDup(db, pWhere, 0); pFrom = sqlite3SrcListAppend(db, 0, 0, 0); if( pFrom ){ assert( pFrom->nSrc==1 ); pFrom->a[0].zAlias = sqlite3DbStrDup(db, pView->zName); pFrom->a[0].pSelect = pDup; assert( pFrom->a[0].pOn==0 ); assert( pFrom->a[0].pUsing==0 ); }else{ sqlite3SelectDelete(db, pDup); } pDup = sqlite3SelectNew(pParse, 0, pFrom, pWhere, 0, 0, 0, 0, 0, 0); } sqlite3SelectDestInit(&dest, SRT_EphemTab, iCur); sqlite3Select(pParse, pDup, &dest); sqlite3SelectDelete(db, pDup);}函数的作用是把视图存放在一个临时的表空间中，之后用Expr *sqlite3LimitWhere()函数产生一个表达树来实现DELETE、UPDATE语句中的WHERE, ORDER BY, LIMIT/OFFSET 部分。
仍以之前SQLite编译器流程的简单例子为例，在命令行中输入以下指令，可以得到编译阶段产生的VDBE字节码
sqlite3 test_File //创建一个名为test_File的数据库文件.explain on //打开解释执行产生字节码的开关，默认是关闭EXPLAIN create table table1(id integer primary key not null, name string);//通过EXPLAIN命令要求输出产生字节码的过程 其输出结果如下
由此我们可以对编译器产生的VDBE字节码有一个初步的认识，在指令中可以看到Transaction指令表示开始一个事务 ，CreateBtree表示对这个表建立一棵B树，等等。
而结合之前对SQLite编译器运行流程的分析，在编译器对所有语句产生完字节码之后，程序从sqlite3_prepare_v2()中跳出，处理好的VDBE实例v被传入sqlite3_step()函数，其流程图如下
vdbe.c文件中存放着VDBE的执行方法（sqlite3VdbeExec()），这是VDBE的核心，也是SQLite的核心，SQL解析器生成一个程序然后由VDBE执行SQL语句的工作。VDBE程序在形式上类似于汇编语言。VDBC程序由一系列线性操作组成，每个操作都有1个操作码和5个操作数，操作数P1, P2, P3是整数，操作数P4是一个以null结尾的字符串，操作数P5是一个无符号字符。sqlite3VdbeExec()函数用于解析VDBE程序指令,但 是要建立一个程序指令还需要其它文件里的函数的帮助和支撑。下面是sqlite3VdbeExec()函数的简要介绍：
int sqlite3VdbeExec( Vdbe *p) { /* The VDBE */ int pc=0; /* 程序计数器 */ Op *aOp = p->aOp; /* p->aOp的复本 */ Op *pOp; /* 当前操作码 */ int rc = SQLITE_OK; /* 函数返回值 */ sqlite3 *db = p->db; /* 数据库 */ Mem *aMem = p->aMem; /* p->aMem的复本 */ Mem *pIn1 = 0; /* 第一次输入的参数 */ Mem *pIn2 = 0; /* 第二次输入的参数 */ Mem *pIn3 = 0; /* 第三次输入的参数 */ Mem *pOut = 0; /* 输出的参数*/ int iCompare = 0; /*存放操作码OP_Compare的操作结果*/ int *aPermute = 0; /*操作码OP_Compare使用的数组。*/ sqlite3VdbeEnter(p); /*初始化虚拟机程序p的环境*/ p->rc = SQLITE_OK; p->pResultSet = 0; db->busyHandler.nBusy = 0; CHECK_FOR_INTERRUPT; sqlite3VdbeIOTraceSql(p); for(pc=p->pc; rc==SQLITE_OK; pc++){ pOp = &aOp[pc]; if( pOp->opflags & OPFLG_OUT2_PRERELEASE ){ assert( pOp->p2>0 ); assert( pOp->p2<=p->nMem ); pOut = &aMem[pOp->p2]; memAboutToChange(p, pOut); VdbeMemRelease(pOut); pOut->flags = MEM_Int; } switch( pOp->opcode ){ //switch语句,每一个case都是在VDBE里执行一个单独的指令，一共155个。 …… } }《SQLite数据库文件全面分析》
《LEMON语法分析生成器源代码情景分析》
联系客服
