SQLite之SQL解析-语法分析-7

SQLite语法分析背景

 SQLite语法分析器是由一个叫lemon的应用程序自动生成的，该语法分析器是由美国计算机专家Richard Hipp先生开发。相对于知名的YACC和BISON，Lemon语法分析器生成器有些名不见经传。但Lemon有自己特有的优势：块头更小，整个源代码只有四千多行，短小精悍；Lemon的可执行文件也很小，只有120多K，配合Lemon使用的lempar.c模板文件也只有700余行，非常精炼。
 Lemon的核心任务是一次次的读入一个个有意义的单元，然后寻求这些单元之间的关系。那么首先Lemon是如何工作的呢？

 首先，为了能够最终获得人们所要求的处理过程，Lemon要求一份已经被准确推敲、仔细考虑、再三审核的语法文件。这样的语法文件是由上下文无关的句法写成的，并且还附有当记号之间的关系符合某一句型时应该如何处置的代码。

 然后，调用Lemon程序，命令它读入该语法文件，并依之自动生成具体的计算机程序，即语法分析器（编译器）。

 最后，输入具体的程序代码，先用词法分析器分词获取每个词组的大记号（抽象出来的符号类型）、小记号（单元的具体内容）。顺序的送入语法分析器，语法分析器解析输入符号，生成可执行分析的中间机器代码。

Lemon专业名词解析

记号（Token）:如C语言里的变量名、常量、字符串、操作符、标点符号、分界符号等有意义的单元。
记号的类：终结符（terminal symbols）、大记号，它们是一些正整数，分别代表语句中一个个记号的类型，比如 1234是一个int型整数，可归类为INT终结符。
记号的值：标识符、小记号，由记号本身或记号本身所决定的某一种数据结构。比如 1234是一个int型整数，1234数字本身就是它的值。
项目：在每个产生式的右部添加一个圆点(或者其他符号)，表示我们在分析过程中已经看到了产生式的多大的部分。比如：A->XYZ共有四个项目，A->*XYZ,A->X*YZ,A->XY*Z,A->XYZ*。 A->X*YZ;表示已经读入了X，接下来期望读入Y。
规约项目：A->a*,结束符已经在产生式最右边，整个候选式已经分析识别了，可以规约了。
接受项目：拓广后的文法开始符号S’，它所对应的一个唯一的规约项目S’->a*称为接受项目，表示句子分析完毕。
移进项目：A->a*bc,(b属于Vt),即下面期待识别到终结符b，接下来遇到后直接将终结符b移进分析栈。
待约项目：A->a*Bc,(B属于Vn),即a已经识别，后面需要识别Bc,并且马上将要规约生成的是一个非终结符B，它将作为A的一部分。
所有的项目连接起来构成一个NFA，即项目作为状态，识别某个字符，*往后移动一位，转到另外一个项目

Lemon核心流程

初始化Lemon

 lemon中有一个非常核心的lemon结构，语法分析生成器所需要的所有状态变量都存放在这个结构中。其中一些非常重要的子结构，都需要初始化后挂到lemon结构之上，包括：

用于存放字符串的s_x1node结构；
用于存放语法符号（终结符和非终结符）以及归属它各种属性的symbol结构；
用于存放各条产生式的rule结构；
用于存放由产生式派生出来的项目config 结构；
用于存放进行语法分析时将如何动作的action结构;
用于存放相关项目和对应的动作集合的state结构；

词法扫描和语法要素构造

 首先说一下，这里的词法扫描是对语法文件.y的词法扫描，而不是词法分析器对某个具体语言的程序所做的词法扫描，但两者原理上相似。该过程核心任务是分析语法文件的语法，以它们在编译原理中的含义，变更、转换、形成计算机内部的表示。主要包括：

把语法文件一次性读入内存；
对语法文件中%ifdef-%endif等字样的代码块进行预处理和取舍；
把语法文件中的字符流，分割成各个词法符号；
把这些符号安家落户，形成语法文件在计算机内部的表示形式；
重现RePrint语法文件(-g选项下执行)；

lemon parse.y -g //控制台打印出扫描完语法分析文件后得到的“纯”语法文件

计算符号的First集合

 为了最终得到LALR(1)类型的语法分析器，需要知道某个句型（产生式）里面，能够跟在非终结符后面的终结符，而这些先行符组成组成了一个终结符的集合，这个集合称为Follow集。但为了能够得到这个集合，还需要先计算每一个符号的First集合。
 根据编译原理中的定义，一个串的First集合是指这个串能推出的任意串中，排在开头的终结符构成的集合。通过对有限的产生式进行反复扫描，连续使用First集合计算方法所描述的规则，直至每个First结合不再增大为止。就能得到准确的First集合。

First集合计算方法

这个过程主要工作：

计算各产生式的优先级
找出各非终结符的First集合·

计算LR(0)分析器

 为语法文件建立与之相对应的LR(0)分析器的各个状态，是一项复杂精细的工作。工作的过程大致如下：

1. 确定语法文件的开始符号。语法文件中各条产生式之间的关系，实质上是以开始符号为根节点的一棵语法树，所以明白无误的确认哪个符号就十分重要，并且还需要保证开始符号不能出现在任何产生式的右边。
   2.找到第一状态的基本项目。如果开始符号仅出现在首个产生式上，则第一状态的基本项目仅有一个；若开始符号出现在数个产生式上，则第一状态的基本项目也就是数个。今后计算LR(0)分析器中所有状态的出发点，就在这些基本项目上，代码也需要在每个基本项目上挂上它们的Follow集合。
   3.对第一状态的基本项目集进行闭包运算，求得此状态中包括基本项目和派生的非基本项目的全体集合，这个全体项目集合就是第一状态的完整形态。
   4.对第一状态的所有项目上的某个符号进行一次移进操作，这是模拟该符号的入栈操作。模拟该符号入栈后，就可以得到一系列的新项目，这时的这些新项目就是另外一个状态的基本项目。在新的基本项目上的bplp域上挂一个入栈前的原来项目，关联起来。新的项目再次移进后，有的会产生新的状态，有的会走到已有的状态上，摆动的记录依然挂到bplp域。
   5.重复上述步骤4
   基本项目集：./lemon parse.y -b
完全项目集：./lemon parse.y -c

计算符号的Follow集合

 项目传播链上记载了各个后继项目与它们前承项目的次序关系。如果把它们颠倒过来，则编程前承项目和后继项目的次序关系了。每一个项目传播链上都挂有一个Follow集，于是，前承项目的follow集合中的元素，可以从后继项目的先行符First集中获取。

颠倒项目传播链的次序，前承项目的fplp域挂上后继项目
找出符号的Follow集合

计算LALR(1)分析器

 在构造LR(0)分析器各状态的过程中，已经完成移进操作的分析和计算。这部分要解决的是规约操作的分析和计算、冲突的处理策略以及如何压缩表示动作的链表。

1. 遍历所有的状态中的项目集，取出可规约操作的项目，这些项目的分割符均已在产生式的最右侧。对照这些特定项目Follow集中的终结符，把这些规约项目与对应的先行符绑定，一起装配到动作表的规约区域去。
2. 找到整个语法分析器的终结态(即接受态);
3. 得到的动作表中，一个状态对应同一个先行符号，可能会有一种以上的动作，这样一来动作之间就产生了冲突。归类为：移进-规约冲突，规约-规约冲突；程序对两种冲突自动判断和消解，处理不了的报告出来。
4. 对于正确的动作表，为了减少存储空间，加快运行速度，程序对动作表进行了压缩。
   5.把动作表打印到.out文件中

生成LALR(1)语法分析器

 通过前面的步骤，已经拿到了语法文件的移进表（Goto表）和动作表（Action表），标志着编译原理中介绍的LALR(1)分析理论已经被实现完成。接下来就应该以Goto表和Action表为指导，生成一个真正的语法分析器了。但是光凭lemon程序是无法完成这个工作的。作者提供了一个名字叫lempar.c的模板文件，lemon通过结合lempar.c的使用才能正式生成一个语法分析器。大概过程：

1. 从模板文件和语法文件中提取并制作头文件包含部分。
2. 定义分析器中各种数据类型,将goto表和action表转换成数组并压缩，输出到语法分析器中。
3. 根据模板文件制作和输出移进、规约、接受的操作处理函数。
4. 生成出错和接受的处理函数。
5. 生成核心的语法分析器Parse函数。

总结

 SQLite的语法分析器代码Parse.c文件是由lemon根据语法文件parse.y和语法分析器模板lempar.c自动生成的，分析器核心函数是sqlite3Parser，它不断的接受词法分析器输入的分词结果，并根据输入值查询此时接受该单词后是移进还是规约，如果移进，内部保持相关状态，等待下一步的输入。如果规约，则调用规约的动作代码进行规约操作，动作代码在parse.y的产生式后。每一次规约的动作代码都会产生一些机器指令，记录在stmt结构中，等完整的输入一个SQL后，该SQL的执行指令全部被生成出来。此时调用虚拟机的核心函数即可以完成具体的动作。