SQLite源码分析3 sqlite的语法分析#

这一次分析从sql字符串解出token以及sqlite语法分析的流程。


parse.y#

定义了sqlite的sql语法规则。另外包含一些配置代码。

%token_prefix TK_#

每个token加上前缀TK_
比如ecmd ::= SEMI.中SEMI这个token在生成的代码里会变成TK_SEMI。
tokenize.c里会给token赋值TK_SEMI喂给parser。
Token结构体定义在sqliteInt.h

include “sqliteInt.h”#

sqliteInt.h包含一系列重要的定义和接口。

%name sqlite3Parser#

定义生成的函数名为 sqlite3Parser。 即需要把token统一喂给这个函数。见tokenize.c。 不指定的话默认是”Parse”。

sql语句的整体定义#

    // Input is a single SQL command
    input ::= cmdlist.                 // input是一个cmd串
    cmdlist ::= cmdlist ecmd.          // cmd串可以是 cmd串 + ecmd
    cmdlist ::= ecmd.                  // cmd串可以是一个ecmd
    ecmd ::= SEMI.                     // ecmd可以是一个分号
    ecmd ::= cmdx SEMI.                // ecmd可以是一个命令+分号
    cmdx ::= cmd.           { sqlite3FinishCoding(pParse); }

定义了大体的语法,比如分号形成一条完整的sql,多条sql接起来也是一条sql,诸如此类。
cmd是具体的sql语言。按种类在后面分别定义。

一些例子#

;
ecmd
cmdlist
input

select * from xxx;
cmdx SEMI
ecmd
cmdlist
input

select * from xxx; select * from xxx;
cmdx SEMI cmdx SEMI
ecmd ecmd
cmdlist ecmd
cmdlist
input


SQL的匹配#

之后定义详细的各种sql,比如begin、create、drop、select等等。
我们看一下最常见的select。

以最简单的select * from GG为例;

    cmd ::= select(X).  {
      SelectDest dest = {SRT_Output, 0, 0, 0, 0, 0, 0};
      sqlite3Select(pParse, X, &dest);
      sqlite3SelectDelete(pParse->db, X);
    }

一旦识别到select语句,调用select.c里的sqlite3Select()来执行。

    select(A) ::= selectnowith(X). {
      Select *p = X;
      if( p ){
        parserDoubleLinkSelect(pParse, p);
      }
      A = p; /*A-overwrites-X*/
    }

select可以是一个selectnowith。

    selectnowith(A) ::= oneselect(A).

selectnowith可以是一个oneselect。

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

    distinct(A) ::= DISTINCT.   {A = SF_Distinct;}
    distinct(A) ::= ALL.        {A = SF_All;}
    distinct(A) ::= .           {A = 0;}

    // distinct可为空

    selcollist(A) ::= sclp(A) scanpt STAR. {
      Expr *p = sqlite3Expr(pParse->db, TK_ASTERISK, 0);
      A = sqlite3ExprListAppend(pParse, A, p);
    }

    // sclp(A)可为空。scanpt有些工程上的功能,为空,不深究。
    // 那么selcollist可为一个*号,即select所有。

    from(A) ::= FROM seltablist(X). {
      A = X;
      sqlite3SrcListShiftJoinType(A);
    }

    seltablist(A) ::= stl_prefix(A) nm(Y) dbnm(D) as(Z) indexed_opt(I)
                      on_opt(N) using_opt(U). {
      A = sqlite3SrcListAppendFromTerm(pParse,A,&Y,&D,&Z,0,N,U);
      sqlite3SrcListIndexedBy(pParse, A, &I);
    }

    stl_prefix(A) ::= .                           {A = 0;}

    // The name of a column or table can be any of the following:
    //
    %type nm {Token}
    nm(A) ::= id(A).
    nm(A) ::= STRING(A).
    nm(A) ::= JOIN_KW(A).

    dbnm(A) ::= .          {A.z=0; A.n=0;}

    as(X) ::= AS nm(Y).    {X = Y;}
    as(X) ::= ids(X).
    as(X) ::= .            {X.n = 0; X.z = 0;}

    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;}

    on_opt(N) ::= ON expr(E).  {N = E;}
    on_opt(N) ::= .     [OR]   {N = 0;}

    using_opt(U) ::= USING LP idlist(L) RP.  {U = L;}
    using_opt(U) ::= .                        {U = 0;}

这样撸下来,把多数可空的表达式都做成空,是可以让select * from GG匹配成一个select表达式的。
然后到cmd再到cmdx最后到input结束。


匹配代码#

知道了大致的匹配方式。现在看一下具体代码。

从sqlite3RunParser()开始看,每一条sql会调这个来解析,sqlite3RunParser()会调sqlite3Parser()。
sqlite3Parser是parse.y里用%name指定的解析函数名。
调sqlite3Parser就会开始按语法定义来解析sql并调用指定的函数。
猜测一下parser的一种执行方式,大致是不断搜索可能的匹配,深度优先。
比如当前状态定义了三种匹配,那么先选一种往下走,一旦发现无法完成,说明选错了,就回退一步更换选择,如此递归。当然搜索过程肯定会有各种优化剪枝等。
粒度越小的匹配会越先执行。按这个顺序看代码。

1. 匹配from GG#

匹配到seltablist(A)。会走

    A = sqlite3SrcListAppendFromTerm(pParse,A,&Y,&D,&Z,0,N,U);
    sqlite3SrcListIndexedBy(pParse, A, &I);

代码在build.c。 结构体定义基本都在sqliteInt.h。

    SrcList *sqlite3SrcListAppendFromTerm(
      Parse *pParse,          /* Parsing context */
      SrcList *p,             /* The left part of the FROM clause already seen */
      Token *pTable,          /* Name of the table to add to the FROM clause */
      Token *pDatabase,       /* Name of the database containing pTable */
      Token *pAlias,          /* The right-hand side of the AS subexpression */
      Select *pSubquery,      /* A subquery used in place of a table name */
      Expr *pOn,              /* The ON clause of a join */
      IdList *pUsing          /* The USING clause of a join */
    )

用来往from后面添加项。对于from GG来说只传了pTable这个参数(GG)。

用sqlite3SrcListAppend把pTable添加到list。

list的定义

    struct SrcList {
      int nSrc;        /* Number of tables or subqueries in the FROM clause */
      u32 nAlloc;      /* Number of entries allocated in a[] below */
      SrcItem a[1];    /* One entry for each identifier on the list */
    };

SrcItem较复杂,为from后面每项的数据。包含数据库名字、表名字、join信息等等一系列数据。
SrcList相当于SrcItem的数组。
添加过程基本就是SrcList里新开一个SrcItem,再给SrcItem赋值,比如表名赋值为GG。
sqlite3SrcListIndexedBy在这个例子里不起作用。

2.匹配*号#

*号会匹配为一个selcollist(A)。那么会走

    Expr *p = sqlite3Expr(pParse->db, TK_ASTERISK, 0);
    A = sqlite3ExprListAppend(pParse, A, p);

Expr结构体,定义表达式。

    Expr *sqlite3Expr(
      sqlite3 *db,            /* Handle for sqlite3DbMallocZero() (may be null) */
      int op,                 /* Expression opcode */
      const char *zToken      /* Token argument.  Might be NULL */
    )

起一个表达式。op赋值为TK_ASTERISK。

    ExprList *sqlite3ExprListAppend(
      Parse *pParse,          /* Parsing context */
      ExprList *pList,        /* List to which to append. Might be NULL */
      Expr *pExpr             /* Expression to be appended. Might be NULL */
    )

添加进ExprList表达式列表。

3.匹配语法oneselect(A)#

*号和表名字都能匹配到了。又能成功匹配到oneselect(A)。走

    A = sqlite3SelectNew(pParse,W,X,Y,P,Q,Z,D,L);

组装一个select数据。

4.select(X)#

识别到了一个完整的select。执行

    SelectDest dest = {SRT_Output, 0, 0, 0, 0, 0, 0};
    sqlite3Select(pParse, X, &dest);
    sqlite3SelectDelete(pParse->db, X);

    sqlite3Select生成select语句的bytecode并执行.下次再分析.
    sqlite3SelectDelete进行释放

5.cmdx#

最后有个收尾动作sqlite3FinishCoding。


其他语法#

%destructor
析构。当一个非终结符(non-terminal)处于某个节点时(可以理解为无用了),会走析构。
可见代码里用了很多,一般是调用各种delete相关函数,来释放内存。


总结#

  • SQLite代码注释非常详细,很香。

  • 学习了sql的解析代码。了解了sql数据的拼装过程。