篇首语：本文由编程笔记#小编为大家整理，主要介绍了SQLite虚拟机相关的知识，希望对你有一定的参考价值。
1 前言
本文主要介绍SQLite虚拟机VDBE，为了更好地了解SQLite虚拟机，文中也加入了一些Lua虚拟机内容来对比学习，更好地了解不同虚拟机之间的异同。
1.1 预备知识
虚拟机设计需要编译原理相关理论基础，这里先简单温习下编译原理中的一些知识。
1.1.1 文法
(1) LR文法
1965年，D.knuth 首先提出了LR(K)文法及LR(K)分析技术。括号中的K 表示向右查看输入串符号的个数。对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR 分析器进行识别，而且这种方法还具有分析速度快，能准确、及时地指出出错位置。
(2) LR(0)，SLR(1)，LR(1)，LALR(1)
LR(0)：分析器是在分析过程中不需向右查看输入符号，因而它对文法的限制较大，不适用绝大多数高级语言的语法分析器，但它是构造其它LR 类分析器的基础。
SLR(1)：简单LR(1)分析法
SLR(1)方法简单地把非终极符的后继符集做为可归约的依据，较容易产生文法冲突。
LR(1)：针对不同产生式上的非终极符，分别定义其后继符集，减少了移入/归约冲突。
LALR(1):Look-AheadLR(1)：
是LR(1)的优化版,LR(1)文法产生的项目较多，带来的实际问题是系统资源消耗大。由于许多LR(1)产生式具有同心状态，合并这些同心状态后没有冲突的文法即符合LALR文法。
LALR分析法因减少了系统内存消耗而得到广泛的使用
(3)YACC
目前对于真正实用的编译程序，所采用的LR分析器基本都是借助于美国贝尔实验室1974年推出的"一个编译器的编译器-YACC"来实现的。它能接受一个用BNF(巴科斯范式)描述的LALR(1)文法并构造LALR(1)语法分析器。简单来说就是YACC这个工具可以编译一个符合LALR（1）文法的语法文件，输出一个该文法文件对应的语法解析文件，这个输出文件一般是C或C++文件。
SQLite中的文法文件是parse.y
(4)Lemon
SQLite中的文法文件并不是使用YACC编译的，而是用Lemon编译。Lemon是SQLite作者维护的一个开源项目。Lemon的源文件在SQLite包里tool目录下，只包含两个C文件：lemon.c和lempar.c，其中lempar.c是模板文件，在编译parse.y时使用。Lemon.c则用于生成lemon可执行程序。
Lemon与YACC没有本质上的不同，都是LALR(1)文法编译器。但lemon有一些改进，主要有：
(1)语法更易读和理解，变量不易弄错。
YACC语法示例： expr -> expr PLUS expr { $$ = $1 + $3; };
Lemon语法示例： expr(A) ::= expr(B) PLUS expr(C). { A = B+C; }
(2)Lemon不使用全局变量，YACC在分析器与分词器间使用全局变量。
(3)Lemon是可重入的，允许多个分析器同时运行。YACC不支持重入。
Lemon简介:
http://www.hwaci.com/sw/lemon/
用Lemon编译parse.y文件后生成的文件是parse.c文件，它包含在SQLite源文件包里。这个文件是解释SQL语句生成可执行指令的编译程序，其入口是函数sqlite3Parser。
Lua在3.1版本以前使用LALR(1)文法文件，并使用YACC生成该文法文件生成编译引擎。但从3.1版本开始为了实现更高的编译效率，使用手写的自顶向下的编译器。
2 虚拟机的组成要素
1．语言和文法
SQLite虚拟机的语言是SQL语句，类似insert into … 这种SQL语句。Lua的语言就是我们在lua脚本中写程序用的语句。
文法是解释语言用的规则，许多虚拟机会采用文法文件，SQLite中是parse.y文件，Lua早期版本是lua.stx文件。
2．文法编译器
编译文法文件的工具。SQLite用的Lemon，Lua早期版本用Yacc。编译器编译文法文件，生成语法分析程序。SQLite中生成的文件是parse.c。Lua1.1版本生成的是y.tab.c。
3．指令和程序
虚拟机中执行的程序体，程序由指令串构成。指令常会变化比较大，以适应各种不同的需求或性能改进等。SQLite和Lua的指令都经历过比较大变化。
4．执行器和运行期环境
在SQLite中入口是sqlite3VdbeExec，Lua执行入口是lua_execute。运行期需要维护的主要是程序运行栈、程序计数器PC、寄存器等。
3 SQLite虚拟机
3.1 SQLite架构
图一
上图取自SQLite官网，在《SQLite文件分析》中，主要介绍了B-Tree这部分内容（图中左下角框图）。本文则主要介绍上面两个框图部分。
3.2 SQL语句执行流程图
本文中的SQL语句Demo采用下面的例子:
create table examp(one text, two int);
insert into examp values ('hello', 98);
流程图如下：
图二
3.3 SQL语句编译
编译的目的是将SQL语句生成能够在SQLite虚拟机VDBE(Virtual Database Engine)中可以执行的指令序列（可以理解为VDBE的执行程序）。SQLite的SQL语句编译引擎在parse.c文件中，由工具Lemon编译文法文件parse.y而来，引擎的入口函数是sqlite3Parser。所有的SQL语句都将通过sqlite3Parser编译成指令才会在虚拟机VDBE中执行
我们用下面SQL语句作为Demo来演示SQL语句的编译。
insert into examp values ('hello1', 98 );
//Insert Demo 1
insert into examp( one,tow ) values('hello', 98 );
//Insert Demo 2，与1等价
Parse.y中对应的inert文法有两条
////// The INSERTcommand //////////
cmd ::= insert_cmd(R) INTO fullname(X)inscollist_opt(F)
VALUES LP itemlist(Y) RP.
{sqlite3Insert(pParse,X, Y, 0, F, R);}
//前面两个insert例子会匹配上面的文法项。其中参数F是可选的，demo1的F为空，demo2的F为表列的List。
cmd ::= insert_cmd(R) INTO fullname(X)inscollist_opt(F) select(S).
{sqlite3Insert(pParse, X, 0, S, F, R);}
//对于形如下面的insert语句会匹配第二条insert文法项
INSERT INTO first_table_name [(column1,column2, ... columnN)]
SELECT column1,column2, ...columnN
FROMsecond_table_name [WHERE condition];
上面例子中的Insert语句会调用sqlite3Insert函数生成insert语句相关的指令序列。
3.4 SQLite的VDBE指令
VDBE每条指令都包括一个操作码和三个操作数，P1，P2，P3(注：VDBE指令随版本不同会有较大变化，但大体指令的模式仍是想通的，SQLite近期的版本采用5个操作数)。P1是一个任意整数，P2是一个非负整数，P3是一个结构体指针（可能为空）或者非空的字符串。很少的指令使用全部三个操作数。大多数指令仅仅使用一个或者两个操作数。也有一些指令没有操作数，而是操作在执行栈上的数据。
仍然用前面的insert语句来看看生成的指令序列，如下图所示：
图三
解释一下上图中每条指令的意义，下面表格中代表运行时执行指令后VDBE栈的变化
0|Goto|0|11| 跳转到第11条指令
1|Integer|0|0| 将要操作的数据库ID入栈，数据库ID这里是0
2|OpenWrite|0|5| OpenWrite指令打开一个可写游标。P1=0 table id， P2=5 table所在的根页号，P3没有被使用
3|SetNumColumns|0|2| 设置列数目
4|NewRowid|0|0| 为新插入的纪录分配rowid，同时rowid入栈
5|String8|0|0|hello 将字符串”hello”入栈
(string) "hello1" |
(integer) new rowid |
6|Integer|98|0| 将整数98入栈
(integer) 98 |
(string) "hello1" |
(integer) new rowid |
7|MakeRecord|2|0|ti 将栈中P1=2个元素弹出，转换成二进制（用于写入db），压入栈
Ti代表操作数类型，其意义如下：
** 'n' =NUMERIC.
** 'i' =INTEGER.
** 't' =TEXT.
** 'o' =NONE.
(record) "hello1", 98 |
(integer) new rowid |
8|Insert|0|3| 执行插入记录到数据库，栈清空
9|Close|0|0| 关闭游标
10|Halt|0|0| 同步脏Page到文件，结束
11|Transaction|0|1| 事务开始。事务开始会获得一个写锁，当这个事务在执行时其他程序不能读或者写这个文件。开始事务会创建一个回滚日志，在对数据库改变前必须启动一个事务。
12|VerifyCOOKIE|0|4| 检查COOKIE 0（数据库schema版本）以确保它等于P2（数据库schema最后读出的值）。P1是数据库号（0代表主数据库）。这是确保数据库schema没有被其他线程改写而导致它必须被重新读入
13|Goto|0|1| 跳转到第1条指令
14|Noop|0|0|
3.4.1 栈和寄存器
根据指令获取操作数方式的不同，可以把虚拟机的实现分为基于栈和基于寄存器两类，两种实现方法同样会导致指令有比较大差异。
基于栈的虚拟机
对于大多数的虚拟机，比如JVM，Python，都采用传统基于栈的。VDBE同样基于栈。
基于栈的虚拟机指令一般都是在当前栈中获取和保存操作数。比如一个简单的加法赋值运算:a=b+c，一般会被转化成如下的指令:
1.push b; // 将变量b的值压入stack
2.push c; // 将变量c的值压入stack
3.add; // 将stack顶部的两个值弹出后相加，将结果压入stack
4.mov a; // 将stack顶部结果放到a中
由于基于栈的指令是通过当前栈来查找操作数的，这意味着所有操作数的存储位置是在运行期才决定。因为不需要在编译阶段决定在哪里存储操作数，所以基于栈的编译器实现起来相对比较容易。
基于栈的缺点在于：对于一个简单的运算，也需要使用较多的指令组合才能完成，这样增加了整体指令集的长度。虚拟机也需要同样多的迭代次数来执行这些指令，这对于效率来说会有比较大的影响。并且，由于操作数都要放到栈上，使得移动这些操作数的内存复制增加，这也会影响效率。
基于寄存器的虚拟机
基于寄存器的指令都是在已经分配好的寄存器中存取操作数。对于上面的运算，一般会使用如下的指令:
add a b c; //将b与c对应的寄存器的值相加，将结果保存在a对应的寄存器中
Lua 在5.0版本以前采用栈方式，5.0以后采用寄存器方式。
3.4.2 对比Lua的指令
让我们看看Lua早期版本的指令和5.0后的指令对比。用一个简单的算术运算来查看指令。
Demo： a=11;b=2;c=a+b;
lua1.1版本指令
图四
1.1版本是基于栈的，ADDOP前进行了操作数压栈。
lua5.2版本指令
Lua5.2的指令使用32bit的unsigned integer表示。所有指令的定义都在lopcodes.h文件中，总共有40种指令(id从0到39)。根据指令参数的不同，可以将所有指令分为4类:
图五
从上图可以看到lua5.2的指令高度精炼，lua可以把脚本编译成lua可执行文件随宿主程序一起发布，其指令的精炼可以使生成的可执行文件很小，执行起来速度也更快。
图六
5.2版本基于寄存器，ADD指令包含了操作数寄存器，寄存器id从0开始。
对比Lua早前版本和现在的版本，可以看到Lua在性能优化方面做了很多努力。
3.5 VDBE(Virtual Database Engine)
SQL语句编译成指令序列后，接下里会在虚拟机中执行这些指令。VDBE引擎的入口是sqlite3VdbeExec，很好理解这个函数一定包含一个循环和所有指令的Case分支，引擎执行编译好的指令序列。每条指令对应一个case OP_xxxx。下面是截取sqlite3VdbeExec的一个片段。
/*从这里开始执行指令
**pc为程序计数器(int)
*/
for(pc=p->pc; rc==SQLITE_OK; pc++){
//取得操作码
pOp = &p->aOp[pc];
switch( pOp->opcode ){
case OP_Goto:{ /*jump */
CHECK_FOR_INTERRUPT;
pc =pOp->p2 - 1;
break;
}
… …
}
}
VDBE主要工作如下：
1.保存编译好的SQL语句对应指令集，即程序体。
2.执行指令相应的动作
3.维护运行时栈的状态。VDBE的栈是局部的，Lua1.1版时还比较简陋，使用的是全局栈，3.1版本后引入了闭包（closure）
4.维护指令计数器PC
4 参考文献
2.《lex与yacc》 JobnR.Levine等。
3. SQLite源码，主要用的3.2.8版本
4. Lua各版本源码
5 附录
这部分附件下载自网络，作者不详。
5.1 LR(0),SLR(1),LR(1),LYLR(1)文法介绍
京公网安备 11010802041100号