SQLite 浅析Lemon

- 日理万妓 2022-07-26 12:23 200阅读 0赞

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))

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

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

void  \* sqlite3ParserAlloc( void  \* ( \* mallocProc)(size\_t))\{  
yyParser  \* pParser;  
pParser  =  (yyParser \* )( \* mallocProc)( (size\_t) sizeof (yyParser) );  
 if ( pParser )\{  
pParser \-> yyidx  =  \- 1 ;  
\#ifdef YYTRACKMAXSTACKDEPTH  
pParser \-> yyidxMax  =  0 ;  
 \#endif   
 \#if  YYSTACKDEPTH<=0   
pParser \-> yystack  =  NULL;  
pParser \-> yystksz  =  0 ;  
yyGrowStack(pParser);  
 \#endif   
\}  
 return  pParser;  
\}

![复制代码][copycode.gif]

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

ParseFree(pParser, free);

SQLite对应的函数如下：

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

void  sqlite3ParserFree(  
 void  \* p,  /\*  The parser to be deleted  \*/   
 void  ( \* freeProc)( void \* )  /\*  Function used to reclaim memory  \*/   
)\{  
yyParser  \* pParser  =  (yyParser \* )p;  
 if ( pParser == 0  )  return ;  
 while ( pParser \-> yyidx >= 0  ) yy\_pop\_parser\_stack(pParser);  
 \#if  YYSTACKDEPTH<=0   
free(pParser \-> yystack);  
 \#endif   
( \* freeProc)(( void \* )pParser);  
\}

![复制代码][copycode.gif]

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

![ExpandedBlockStart.gif][]

void  sqlite3Parser(  
 void  \* yyp,  /\*  The parser  \*/   
 int  yymajor,  /\*  The major token code number  \*/   
sqlite3ParserTOKENTYPE yyminor  /\*  The value for the token  \*/   
sqlite3ParserARG\_PDECL  /\*  Optional %extra\_argument parameter  \*/   
)

该函数由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 :: =  expr PLUS expr.  
expr :: =  expr TIMES expr.  
expr :: =  LPAREN expr RPAREN.  
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支持如下一些特殊指示符：

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

% 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

![复制代码][copycode.gif]

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

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

3.1.2、select-core  
![lemon1-2.gif][]

相应的语法规则：

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

cmd :: =  select(X). \{  
SelectDest dest  =  \{SRT\_Output,  0 ,  0 ,  0 ,  0 \};  
sqlite3Select(pParse, X,  & dest);  
sqlite3SelectDelete(pParse \-> db, X);  
\}  
  
 % type select \{Select \* \}  // select语句对应的结构体   
 % destructor select \{sqlite3SelectDelete(pParse \-> db, $$);\}  
 % type oneselect \{Select \* \}  
 % destructor oneselect \{sqlite3SelectDelete(pParse \-> db, $$);\}  
  
select(A) :: =  oneselect(X). \{A  =  X;\}  
 // ...  
 // 简单SQL语句,可以分成以下几部分:输出列、from子句、where子句、group子句、having子句   
 oneselect(A) :: =  SELECT distinct(D) selcollist(W) from(X) where\_opt(Y)  
groupby\_opt(P) having\_opt(Q) orderby\_opt(Z) limit\_opt(L). \{  
A  =  sqlite3SelectNew(pParse,W,X,Y,P,Q,Z,D,L.pLimit,L.pOffset);  
\}

![复制代码][copycode.gif]



distinct

% type distinct \{  int \}  
distinct(A) :: =  DISTINCT. \{A  =  1 ;\}  
distinct(A) :: =  ALL. \{A  =  0 ;\}  
distinct(A) :: =  . \{A  =  0 ;\}

 selcollist(输出结果列)

![lemon1-3.gif][]

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

% type selcollist \{ExprList \* \}  // 输出列对应的结构体   
 % destructor selcollist \{sqlite3ExprListDelete(pParse \-> db, $$);\}  
 % type sclp \{ExprList \* \}  
 % destructor sclp \{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, P, X.pExpr);  
 if ( Y.n > 0  ) sqlite3ExprListSetName(pParse, A,  & Y,  1 );  
sqlite3ExprListSetSpan(pParse,A, & X);  
\}  
selcollist(A) :: =  sclp(P) STAR. \{  
Expr  \* p  =  sqlite3Expr(pParse \-> db, TK\_ALL,  0 );  
A  =  sqlite3ExprListAppend(pParse, P, p);  
\}  
selcollist(A) :: =  sclp(P) nm(X) DOT STAR(Y). \{  
Expr  \* pRight  =  sqlite3PExpr(pParse, TK\_ALL,  0 ,  0 ,  & Y);  
Expr  \* pLeft  =  sqlite3PExpr(pParse, TK\_ID,  0 ,  0 ,  & X);  
Expr  \* pDot  =  sqlite3PExpr(pParse, TK\_DOT, pLeft, pRight,  0 );  
A  =  sqlite3ExprListAppend(pParse,P, pDot);  
\}  
  
 //  An option "AS <id>" phrase that can follow one of the expressions that  
 //  define the result set, or one of the tables in the FROM clause.  
 //  AS语句   
 % type  as  \{Token\}  
 as (X) :: =  AS nm(Y). \{X  =  Y;\}  
 as (X) :: =  ids(Y). \{X  =  Y;\}  
 as (X) :: =  . \{X.n  =  0 ;\}

![复制代码][copycode.gif]

 from

from子句分以下几部分：  
join-source：  
![lemon1-4.gif][]

single-source：

![lemon1-5.gif][]

join-op：

![lemon1-6.gif][]

join-constraint：

![lemon1-7.gif][]

语法规则：

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

% type seltablist \{SrcList \* \}  // from子语对应的数据结构   
 % destructor seltablist \{sqlite3SrcListDelete(pParse \-> db, $$);\}  
 % type stl\_prefix \{SrcList \* \}  
 % destructor stl\_prefix \{sqlite3SrcListDelete(pParse \-> db, $$);\}  
 % type from \{SrcList \* \}  
 % destructor from \{sqlite3SrcListDelete(pParse \-> db, $$);\}  
  
 //  A complete FROM clause. FROM子句  
 //  
 from(A) :: =  . \{A  =  sqlite3DbMallocZero(pParse \-> db,  sizeof ( \* A));\}  
from(A) :: =  FROM seltablist(X). \{  
A  =  X;  
sqlite3SrcListShiftJoinType(A);  
\}  
  
 //  "seltablist" is a "Select Table List" - the content of the FROM clause  
 //  in a SELECT statement. "stl\_prefix" is a prefix of this list.  
 //  
 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,X, & Y, & D, & Z, 0 ,N,U);  
sqlite3SrcListIndexedBy(pParse, A,  & I);  
\}  
  
 // 数据库名   
 % type dbnm \{Token\}  
dbnm(A) :: =  . \{A.z = 0 ; A.n = 0 ;\}  
dbnm(A) :: =  DOT nm(X). \{A  =  X;\}  
  
 // 全名   
 % type fullname \{SrcList \* \}  
 % destructor fullname \{sqlite3SrcListDelete(pParse \-> db, $$);\}  
fullname(A) :: =  nm(X) dbnm(Y). \{A  =  sqlite3SrcListAppend(pParse \-> db, 0 , & X, & Y);\}  
  
 // join语句   
 % type joinop \{  int \}  
 % type joinop2 \{  int \}  
joinop(X) :: =  COMMA | JOIN. \{ X  =  JT\_INNER; \}  
joinop(X) :: =  JOIN\_KW(A) JOIN. \{ X  =  sqlite3JoinType(pParse, & A, 0 , 0 ); \}  
joinop(X) :: =  JOIN\_KW(A) nm(B) JOIN. \{ X  =  sqlite3JoinType(pParse, & A, & B, 0 ); \}  
joinop(X) :: =  JOIN\_KW(A) nm(B) nm(C) JOIN.  
\{ X  =  sqlite3JoinType(pParse, & A, & B, & C); \}  
 // on语句   
 % type on\_opt \{Expr \* \}  
 % destructor on\_opt \{sqlite3ExprDelete(pParse \-> db, $$);\}  
on\_opt(N) :: =  ON expr(E). \{N  =  E.pExpr;\}  
on\_opt(N) :: =  . \{N  =  0 ;\}  
  
 //  Note that this block abuses the Token type just a little. If there is  
 //  no "INDEXED BY" clause, the returned token is empty (z==0 && n==0). If  
 //  there is an INDEXED BY clause, then the token is populated as per normal,  
 //  with z pointing to the token data and n containing the number of bytes  
 //  in the token.  
 //   
 //  If there is a "NOT INDEXED" clause, then (z==0 && n==1), which is  
 //  normally illegal. The sqlite3SrcListIndexedBy() function  
 //  recognizes and interprets this as a special case.  
 // index by语句(似乎不属于SQL92标准)   
 % type indexed\_opt \{Token\}  
indexed\_opt(A) :: =  . \{A.z = 0 ; A.n = 0 ;\}  
indexed\_opt(A) :: =  INDEXED BY nm(X). \{A  =  X;\}  
indexed\_opt(A) :: =  NOT INDEXED. \{A.z = 0 ; A.n = 1 ;\}  
  
 // using语句   
 % type using\_opt \{IdList \* \}  
 % destructor using\_opt \{sqlite3IdListDelete(pParse \-> db, $$);\}  
using\_opt(U) :: =  USING LP inscollist(L) RP. \{U  =  L;\}  
using\_opt(U) :: =  . \{U  =  0 ;\}

![复制代码][copycode.gif]

 order by

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

% type orderby\_opt \{ExprList \* \}  
 % destructor orderby\_opt \{sqlite3ExprListDelete(pParse \-> db, $$);\}  
 % type sortlist \{ExprList \* \}  
 % destructor sortlist \{sqlite3ExprListDelete(pParse \-> db, $$);\}  
 % type sortitem \{Expr \* \}  
 % destructor sortitem \{sqlite3ExprDelete(pParse \-> db, $$);\}  
  
 // order by语句   
 orderby\_opt(A) :: =  . \{A  =  0 ;\}  
orderby\_opt(A) :: =  ORDER BY sortlist(X). \{A  =  X;\}  
sortlist(A) :: =  sortlist(X) COMMA sortitem(Y) sortorder(Z). \{  
A  =  sqlite3ExprListAppend(pParse,X,Y);  
 if ( A ) A \-> a\[A \-> nExpr \- 1 \].sortOrder  =  (u8)Z;  
\}  
sortlist(A) :: =  sortitem(Y) sortorder(Z). \{  
A  =  sqlite3ExprListAppend(pParse, 0 ,Y);  
 if ( A  &&  ALWAYS(A \-> a) ) A \-> a\[ 0 \].sortOrder  =  (u8)Z;  
\}  
sortitem(A) :: =  expr(X). \{A  =  X.pExpr;\}  
  
 // 顺序   
 % type sortorder \{  int \}  
  
sortorder(A) :: =  ASC. \{A  =  SQLITE\_SO\_ASC;\}  
sortorder(A) :: =  DESC. \{A  =  SQLITE\_SO\_DESC;\}  
sortorder(A) :: =  . \{A  =  SQLITE\_SO\_ASC;\}

![复制代码][copycode.gif]

 group by

![ExpandedBlockStart.gif][]

% type groupby\_opt \{ExprList \* \}  
 % destructor groupby\_opt \{sqlite3ExprListDelete(pParse \-> db, $$);\}  
groupby\_opt(A) :: =  . \{A  =  0 ;\}  
groupby\_opt(A) :: =  GROUP BY nexprlist(X). \{A  =  X;\}

having

% type having\_opt \{Expr \* \}  
 % destructor having\_opt \{sqlite3ExprDelete(pParse \-> db, $$);\}  
having\_opt(A) :: =  . \{A  =  0 ;\}  
having\_opt(A) :: =  HAVING expr(X). \{A  =  X.pExpr;\}

limit

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

% type limit\_opt \{  struct  LimitVal\}  
  
 //  The destructor for limit\_opt will never fire in the current grammar.  
 //  The limit\_opt non-terminal only occurs at the end of a single production  
 //  rule for SELECT statements. As soon as the rule that create the  
 //  limit\_opt non-terminal reduces, the SELECT statement rule will also  
 //  reduce. So there is never a limit\_opt non-terminal on the stack  
 //  except as a transient. So there is never anything to destroy.  
 //   
 // %destructor limit\_opt \{  
 //  sqlite3ExprDelete(pParse->db, $$.pLimit);  
 //  sqlite3ExprDelete(pParse->db, $$.pOffset);  
 // \}   
 limit\_opt(A) :: =  . \{A.pLimit  =  0 ; A.pOffset  =  0 ;\}  
limit\_opt(A) :: =  LIMIT expr(X). \{A.pLimit  =  X.pExpr; A.pOffset  =  0 ;\}  
limit\_opt(A) :: =  LIMIT expr(X) OFFSET expr(Y).  
\{A.pLimit  =  X.pExpr; A.pOffset  =  Y.pExpr;\}  
limit\_opt(A) :: =  LIMIT expr(X) COMMA expr(Y).  
\{A.pOffset  =  X.pExpr; A.pLimit  =  Y.pExpr;\}

![复制代码][copycode.gif]

[ExpandedBlockStart.gif]: /images/20220724/23c314cdec8d4933a6a699705eb6913a.png
[copycode.gif]: /images/20220724/094ee331738e48adba44a9aa902821a6.png
[lemon1-1.gif]: /images/20220724/93239b672abf45ef8b9e42bb4cb004f7.png
[lemon1-2.gif]: /images/20220724/c41841a9a8a64b108b6028fb1c745405.png
[lemon1-3.gif]: /images/20220724/bb88a894295347708ae856902af5bdfc.png
[lemon1-4.gif]: /images/20220724/3306186faf5540d8b45523a0562952e3.png
[lemon1-5.gif]: /images/20220724/50904ad0a6614a19b6358a1e26875d19.png
[lemon1-6.gif]: /images/20220724/6c83b9adad8143ac8d5dcf8f65bc33a7.png
[lemon1-7.gif]: /images/20220724/13c78c943c034f3e8517bdb665856d09.png