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 - |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
