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数据的拼装过程。