浅谈SQLite——浅析Lemon

概述1、概述 　　Lemon是一个LALR(1)文法分析器生成工具。虽然它是SQLite作者针对SQLite写的一个分析器生成工具，但是它与bison和yacc类似，是一个可以独立于SQLite使用的开源的分析器生成工具。而且它使用与yacc(bison)不同的语法规则，可以减少编程时出现错误的机会。Lemon比yacc和bison更精致、更快，而且是可重入的，也是线程安全的——这对于支持多线程的程序

1、概述
　　Lemon是一个LALR(1)文法分析器生成工具。虽然它是sqlite作者针对sqlite写的一个分析器生成工具，但是它与bison和yacc类似，是一个可以独立于sqlite使用的开源的分析器生成工具。而且它使用与yacc(bison)不同的语法规则，可以减少编程时出现错误的机会。Lemon比yacc和bison更精致、更快，而且是可重入的，也是线程安全的——这对于支持多线程的程序是非常重要的。
　　Lemon的主要功能就是根据上下文无关文法(CFG)，生成支持该文法的分析器。程序的输入文件有两个：
　　(1)语法规则文件；
　　(2)分析器模板文件。
　　一般来说，语法规则是由程序员定义的；Lemon有一个适用于大多数应用程序的默认分析器模板。根据命令行选项，Lemon会生成以下一些文件：
　　(1)分析器的C代码；
　　(2)一个为每个终结符定义一个整型ID的头文件；
　　(3)一个描述分析器状态的文件。
　　语法规范文件以”.y”为后缀，如果语法规范文件为”gram.y”，则可以使用如下命令生成分析器：
　　lemon gram.y

1.1、分析器接口
　　Lemon不会生成一个完整的、可以运行的程序。它仅仅生成一些实现分析器的子例程，然后由用户程序在适当的地方调用这些子例程，从而生成一个完整的分析器。
1.1.1、ParseAlloc
　　程序在使用Lemon生成的分析器之前，必须创建一个分析器。如下：

voID*pParser=ParseAlloc(malloc);

ParseAlloc为分析器分配空间，然后初始化它，返回一个指向分析器的指针。sqlite对应的函数为：

voID*sqlite3ParserAlloc(voID*(*mallocProc)(size_t))

函数的参数为一个函数指针，并在函数内调用该指针指向的函数。如：

代码 voID*(*mallocProc)(size_t)){
yyParser*pParser;
pParser=(yyParser*)(*mallocProc)((size_t)sizeof(yyParser));
if(pParser){
pParser->yyIDx=-1;
#ifdefYYTRACKMAXSTACKDEPTH
pParser->yyIDxMax=0;
#endif
#ifYYSTACKDEPTH<=0
pParser->yystack=NulL;
pParser->yystksz=0;
yyGrowStack(pParser);
#endif
}
returnpParser;
}

1.1.2、ParseFree
当程序不再使用分析器时，应该回收为其分配的内存。如下：

ParseFree(pParser,free);

sqlite对应的函数如下：

代码 voIDsqlite3ParserFree(
voID*p,/*Theparsertobedeleted*/
voID(*freeProc)(voID*)Functionusedtoreclaimmemory*/
){
yyParser*pParser=(yyParser*)p;
if(pParser==0)return;
while(pParser->yyIDx>=0)yy_pop_parser_stack(pParser);
#ifYYSTACKDEPTH<=0
free(pParser->yystack);
#endif
(*freeProc)((voID*)pParser);
}

1.1.3、Parse
Parse是Lemon生成的分析器的核心例程。在分析器调用ParseAlloc后，分词器就可以将切分的词传递给Parse，进行语法分析。sqlite对应的函数如下：

代 voIDsqlite3Parser(
voID*yyp,0)">Theparserintyymajor,0)">Themajortokencodenumber*/
sqlite3ParserTOKENTYPEyyminorThevalueforthetoken*/
sqlite3ParserARG_PDECLOptional%extra_argumentparameter*/
)

该函数由sqlite3RunParser调用：
int sqlite3RunParser(Parse *pParse,const char *zsql,char **pzErrMsg)
　　sqlite3RunParser位于token.c文件中，它是进行SQL语句分析的入口，它调用sqlite3GetToken对SQL语句zsql进行分词，然后调用sqlite3Parser进行语法分析。而sqlite3Parser在语法规则发生规约时调用相应的opcode生成子例程，生成opcode。

1.2、与yacc和bison的不同之处
Lemon与yacc和bison有一些不同的地方：
(1)在yacc和bison中，是分析器调用分词器。在Lemon，分词器调用分析器；
(2)Lemon不会使用全局变量。而yacc与bison在分析器与分词器之间使用全局变量；
(3)Lemon允许多个分析器同时运行，因为它是可重入的。而yacc与bison却不行。

2、输入文件语法
　　Lemon的语法规则文件(grammar specification file)主要用于为分析器定义语法规则。此外，输入文件还包括其它一些有用的信息，使用的Lemon的大部分工作就是写语法文件。
2.1、终结符与非终结符(Terminals and Nonterminals)
　　终结符通常是大写的字符串(数字或字母)。非终结符是小写的字符串(数字或字母)。
2.2、语法规则(Grammar Rules)
　　每个语法规则由三部分构成：以非终结符开始，随后紧接着为“::=”，然后是终结符(或非终结)列表，规则以英文语句“.”结尾。如下：

expr::=exprPLUSexpr.
expr::=exprTIMESexpr.
expr::=LPARENexprRPAREN.
expr::=VALUE.

　　上例中，有一个非终结符“expr”，和5个终结符：“PLUS”、“TIMES”、“LPAREN”、“RPAREN”、和“VALUE”。
与yacc和bison一样，Lemon允许为规则添加C代码块，并由分析器进行规则规约时调用。如下：
expr ::= expr PLUS expr. { printf("Doing an addition...\n"); }
　　为了使规则有用，语法动作(grammar actions)必须与相应的语法规则联系起来。在yacc和bison中，动作(action)中的“$$”代表左值，而“$1”、“$2”等则代表“::=”右边的位置相应为1、2等的终结符或非终结符的值。这是非常有用的，但是，却非常容易出错。例如：
expr -> expr PLUS expr { $$ = $1 + $3; };

　　而Lemon通过为规则中的每个符号指定一个额外的符号名字(symbolic)达到相同的目的，然后在动作中使用这些符号名字。如下：
expr(A) ::= expr(B) PLUS expr(C). { A = B+C; }

2.3、优先级规则(Precedence Rules)
Lemon采用与yacc和bison相同的方法处理歧义性问题。移进—规约冲突，则选择移进；规约——规约冲突，则选择先出现的规则。
同样，Lemon也允许通过优先级规则来解决冲突。如下：
%left AND.
%left OR.
%nonassoc EQ NE GT GE LT LE.
%left PLUS MINUS.
%left TIMES divIDE MOD.
%right EXP NOT.

2.4、特殊指示符(Special Directives)
Lemon支持如下一些特殊指示符：

代码 %code
%default_destructor
%default_type
%destructor
%extra_argument
%include
%left
%name
%nonassoc
%parse_accept
%parse_failure
%right
%stack_overflow
%stack_size
%start_symbol
%Syntax_error
%token_destructor
%token_prefix
%token_type
%type

%code
%code表示将一段C/C++代码添加到输出文件的尾部。它主要用于包含一些动作例程(action routines)或者词法器的部分代码。

%default_type
如果没有在%type中为非终结符指定数据类型，则default_type指定非终结符的数据类型。
%destructor
为非终结符指定一个资源释放器(destructor)（%token_destructor为终结符指定资源释放器）。当非终结符从分析栈中d出时，释放器就会被调用，以释放其占用的资源。包括如下情况：
(1)一个规则发生规约，而非终结符的右边却没有C代码；
(2)在错误处理中，出栈 *** 作；
(3)ParseFree函数返回。
释放器可以做任何 *** 作，但是它主要用来释放非终结符占用的内存或其它资源。例：
%type nt {voID*}
%destructor nt { free($$); }
nt(A) ::= ID NUM. { A = malloc( 100 ); }
在例子中，“nt”的数据类型为“voID *”。当“nt”的规则发生规约时，为非终结符通过malloc分配空间。之后，当非终结符从栈中d出时，释放器会被调用，以释放malloc申请的内存。这可以避免内存泄漏。
注意，除非非终结符会在C动作代码中使用，否则，当非终结符从栈中d出时，就会调用释放器释放资源。如果C代码使用非终结符，则由C代码保证资源的释放。

%token_prefix
Lemon的生成文件会为每个终结符定义一个整数值。如下：
#define AND 1
#define MINUS 2
#define OR 3
#define PLUS 4
如果愿意，可以通过该指示符为#define的预处理符号加一个前缀。例如，可以在规则文件加上如下：
%token_prefix TOKEN_
则生成的文件的输出如下：
#define TOKEN_AND 1
#define TOKEN_MINUS 2
#define TOKEN_OR 3
#define TOKEN_PLUS 4

%include
由该指示符指定的C代码会包含到生成的分析的顶部。你可以包含任意代码，Lemon会完全拷贝过去。

%extra_argument
指示Parse函数中第四个参数。 Lemon本身不会做任何处理，但是相应的C代码可以使用该参数。

%parse_accept
分析器进行语法分析成功时，执行的C代码。如：
%parse_accept {
printf("parsing complete!\n");
}

%stack_overflow
当分析器执行发生内部栈溢出时，会执行相应的动作。通常，可以输出错误消息，分析器不能继续执行，而必须重置。例如：
%stack_overflow {
fprintf(stderr,"Giving up. Parser stack overflow\n");
}

%name
默认情况下，Lemon生成的函数都以“Parse”开始，可以通过该指示符修改。例如：
%name Abcde
这会导致Lemon生成的函数的名字如下：
AbcdeAlloc(),
AbcdeFree(),
AbcdeTrace(),and
Abcde().

%token_type与%type
这些指示符用于为分析器的栈中的终结符或非终结指定数据类型。所有终结符都必须是相同的类型，而与应该与Lemon生成的输出文件中的Parse()的第3个参数的类型一致。通常，可以将一个结构指针赋给终结符，如下：
%token_type {Token*}
如果终结符的数据类型没有指定，默认为“int”。

通常，每个非终结符都有各自的数据类型。例如，通常非终结符为指向的分析树的根结点的数据类型指针，该根结点包含非终结符的所有信息。例如：
%type expr {Expr*}

3、sqlite语法规则分析

　　下面以SELECT语句简要的概述一下sqlite的语法规则。
3.1、SELECT语法
　　SELECT语法是SQL语句中最复杂的部分之一。而其它SQL语句，比如CREATE（DROP） table、CREATE（DROP）INDEX、INSERT、DELETE、UPDATE相对来说比较简单。
3.1.1、select-stmt
select的语法全图：

3.1.2、select-core

相应的语法规则：

代码 cmd::=select(X).{
SelectDestdest={SRT_Output,0,128)">0};
sqlite3Select(pParse,X,&dest);
sqlite3SelectDelete(pParse->db,X);
}

%typeselect{Select*}//select语句对应的结构体
%destructorselect{sqlite3SelectDelete(pParse->db,$$);}
%typeoneselect{Select*}
%destructoroneselect{sqlite3SelectDelete(pParse->db,$$);}

select(A)::=oneselect(X).{A=X;}
...
简单SQL语句,可以分成以下几部分:输出列、from子句、where子句、group子句、having子句
oneselect(A)::=SELECtdistinct(D)selcolList(W)from(X)where_opt(Y)
groupby_opt(P)having_opt(Q)orderby_opt(Z)limit_opt(L).{
A=sqlite3SelectNew(pParse,W,Y,P,Q,Z,D,L.plimit,L.pOffset);
}



　　distinct

%typedistinct{int}
distinct(A)::=disTINCT.{A=1;}
distinct(A)::=ALL.{A=0;}
distinct(A)::=.{A=0;}

selcolList(输出结果列)

代码 %typeselcolList{ExprList*}输出列对应的结构体
%destructorselcolList{sqlite3ExprListDelete(pParse->db,$$);}
%typesclp{ExprList*}
%destructorsclp{sqlite3ExprListDelete(pParse->db,$$);}
sclp(A)::=selcolList(X)COMMA.{A=X;}
sclp(A)::=.{A=0;}
selcolList(A)::=sclp(P)expr(X)as(Y).{
A=sqlite3ExprListAppend(pParse,X.pExpr);
if(Y.n>0)sqlite3ExprListSetname(pParse,A,&Y,128)">1);
sqlite3ExprListSetSpan(pParse,&X);
}
selcolList(A)::=sclp(P)STAR.{
Expr*p=sqlite3Expr(pParse->db,TK_ALL,128)">0);
A=sqlite3ExprListAppend(pParse,p);
}
selcolList(A)::=sclp(P)nm(X)DOTSTAR(Y).{
Expr*pRight=sqlite3PExpr(pParse,&Y);
Expr*pleft=sqlite3PExpr(pParse,TK_ID,&X);
Expr*pDot=sqlite3PExpr(pParse,TK_DOT,pleft,pRight,pDot);
}

Anoption"AS<ID>"phrasethatcanfollowoneoftheExpressionsthat
definetheresultset,oroneofthetablesintheFROMclause.
AS语句
%typeas{Token}
as(X)::=ASnm(Y).{X=Y;}
as(X)::=IDs(Y).{X=Y;}
as(X)::=.{X.n=0;}

from

from子句分以下几部分：
join-source：

single-source：

join-op：

join-constraint：

语法规则：

代码 %typeseltabList{SrcList*}from子语对应的数据结构
%destructorseltabList{sqlite3SrcListDelete(pParse->db,$$);}
%typestl_prefix{SrcList*}
%destructorstl_prefix{sqlite3SrcListDelete(pParse->db,$$);}
%typefrom{SrcList*}
%destructorfrom{sqlite3SrcListDelete(pParse->db,$$);}

AcompleteFROMclause.FROM子句
//
from(A)::=.{A=sqlite3DbMallocZero(pParse->db,255)">sizeof(*A));}
from(A)::=FROMseltabList(X).{
A=X;
sqlite3SrcListShiftJoinType(A);
}

"seltabList"isa"SelecttableList"-thecontentoftheFROMclause
inaSELECTstatement."stl_prefix"isaprefixofthisList.
//
stl_prefix(A)::=seltabList(X)joinop(Y).{
A=X;
if(ALWAYS(A&&A->nSrc>0))A->a[A->nSrc-1].jointype=(u8)Y;
}
stl_prefix(A)::=.{A=0;}

from后面的语句
seltabList(A)::=stl_prefix(X)nm(Y)dbnm(D)as(Z)indexed_opt(I)on_opt(N)using_opt(U).{
A=sqlite3SrcListAppendFromTerm(pParse,&D,&Z,N,U);
sqlite3SrcListIndexedBy(pParse,&I);
}

数据库名
%typedbnm{Token}
dbnm(A)::=.{A.z=0;A.n=0;}
dbnm(A)::=DOTnm(X).{A=X;}

全名
%typefullname{SrcList*}
%destructorfullname{sqlite3SrcListDelete(pParse->db,$$);}
fullname(A)::=nm(X)dbnm(Y).{A=sqlite3SrcListAppend(pParse->db,&X,&Y);}

join语句
%typejoinop{int}
%typejoinop2{int}
joinop(X)::=COMMA|JOIN.{X=JT_INNER;}
joinop(X)::=JOIN_KW(A)JOIN.{X=sqlite3JoinType(pParse,&A,128)">0);}
joinop(X)::=JOIN_KW(A)nm(B)JOIN.{X=sqlite3JoinType(pParse,&B,128)">0);}
joinop(X)::=JOIN_KW(A)nm(B)nm(C)JOIN.
{X=sqlite3JoinType(pParse,&C);}
on语句
%typeon_opt{Expr*}
%destructoron_opt{sqlite3ExprDelete(pParse->db,$$);}
on_opt(N)::=ONexpr(E).{N=E.pExpr;}
on_opt(N)::=.{N=Notethatthisblockabusesthetokentypejustalittle.Ifthereis
no"INDEXEDBY"clause,thereturnedtokenisempty(z==0&&n==0).If
thereisanINDEXEDBYclause,thenthetokenispopulatedaspernormal,
withzpointingtothetokendataandncontainingthenumberofbytes
inthetoken.

Ifthereisa"notinDEXED"clause,then(z==0&&n==1),whichis
normallyillegal.Thesqlite3SrcListIndexedBy()function
recognizesandinterpretsthisasaspecialcase.
indexby语句(似乎不属于sql92标准)
%typeindexed_opt{Token}
indexed_opt(A)::=.{A.z=0;}
indexed_opt(A)::=INDEXEDBYnm(X).{A=X;}
indexed_opt(A)::=notinDEXED.{A.z=1;}

using语句
%typeusing_opt{IDList*}
%destructorusing_opt{sqlite3IDListDelete(pParse->db,$$);}
using_opt(U)::=USINGLPinscolList(L)RP.{U=L;}
using_opt(U)::=.{U=order by

代码 %typeorderby_opt{ExprList*}
%destructororderby_opt{sqlite3ExprListDelete(pParse->db,$$);}
%typesortList{ExprList*}
%destructorsortList{sqlite3ExprListDelete(pParse->db,$$);}
%typesortitem{Expr*}
%destructorsortitem{sqlite3ExprDelete(pParse->db,0)">orderby语句
orderby_opt(A)::=.{A=0;}
orderby_opt(A)::=ORDERBYsortList(X).{A=X;}
sortList(A)::=sortList(X)COMMAsortitem(Y)sortorder(Z).{
A=sqlite3ExprListAppend(pParse,Y);
if(A)A->a[A->nExpr-1].sortOrder=(u8)Z;
}
sortList(A)::=sortitem(Y)sortorder(Z).{
A=sqlite3ExprListAppend(pParse,255)">if(A&&ALWAYS(A->a))A->a[0].sortOrder=(u8)Z;
}
sortitem(A)::=expr(X).{A=X.pExpr;}

顺序
%typesortorder{int}

sortorder(A)::=ASC.{A=sqlITE_SO_ASC;}
sortorder(A)::=DESC.{A=sqlITE_SO_DESC;}
sortorder(A)::=.{A=sqlITE_SO_ASC;}

group by

代码 %typegroupby_opt{ExprList*}
%destructorgroupby_opt{sqlite3ExprListDelete(pParse->db,$$);}
groupby_opt(A)::=.{A=0;}
groupby_opt(A)::=GROUPBYnexprList(X).{A=X;}

　　

　　having

%typehaving_opt{Expr*}
%destructorhaving_opt{sqlite3ExprDelete(pParse->db,$$);}
having_opt(A)::=.{A=0;}
having_opt(A)::=HAVINGexpr(X).{A=X.pExpr;}

　　limit

代码 %typelimit_opt{structlimitVal}

Thedestructorforlimit_optwillneverfireinthecurrentgrammar.
Thelimit_optnon-terminalonlyoccursattheendofasingleproduction
ruleforSELECTstatements.Assoonastherulethatcreatethe
limit_optnon-terminalreduces,theSELECTstatementrulewillalso
reduce.sothereisneveralimit_optnon-terminalonthestack
exceptasatransIEnt.sothereisneveranythingtodestroy.
%destructorlimit_opt{
sqlite3ExprDelete(pParse->db,$$.plimit);
}
limit_opt(A)::=.{A.plimit=0;A.pOffset=0;}
limit_opt(A)::=liMITexpr(X).{A.plimit=X.pExpr;A.pOffset=0;}
limit_opt(A)::=liMITexpr(X)OFFSETexpr(Y).
{A.plimit=X.pExpr;A.pOffset=Y.pExpr;}
limit_opt(A)::=liMITexpr(X)COMMAexpr(Y).
{A.pOffset=X.pExpr;A.plimit=Y.pExpr;}

主要参考：

http://www.sqlite.org/src/doc/trunk/doc/lemon.html

总结

以上是内存溢出为你收集整理的浅谈SQLite——浅析Lemon全部内容，希望文章能够帮你解决浅谈SQLite——浅析Lemon所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。