SQLite源码分析-词法分析和语法分析SQLite源码分析-词法分析和语法分析概述词法分析器语法分析器

SQLite源码分析-词法分析和语法分析

概述

一串字符串，经过词法分析器（tokenize) 程序分析后，得到一系列的记号 （Token），然后把这些记号送入语法分析器（Parse），形成相应的语法树。
Sqlite 的词法分析器是手写的，相对来说比较简单，其位于 src/tokenize.c 文件中。Sqlite 的语法分析器是通过 Lemon 语法生成器生成的，其语法文件位于 parse.y 文件中，语法分析器即编译器。

词法分析器

任务

输入 sql 语句，输出关键字的 Token。如输入 select ，输出 TK_SELECT，select 为用户输入的关键字，TK_SELECT 为系统中已定义的 Token。

简述

Sqlite 的词法分析器并没有使用有限状态自动机，而是使用了一个简的、自己实现的词法分析器。该实现位于：
src/tokenize.c 中。

tokenize.c

函数

static int sqliteKeywordCode(const char *z, int n) 关键字转换为关键码:

int sqliteGetToken(const char *z, int *tokenType) 根据传入的字符串获得关键码，如将 空格、t、n、f 转换为 TK_SPACE，将 <= 转换为 TK_LE， 具体的转换关系如下：

int sqliteRunParser(Parse *pParse, char *zSql, char **pzErrMsg) 该函数循环执行用户输入的sql语句，调用 sqliteGetToken 函数获得字符串对应的 token 和 token 长度，并交由下一步处理。

预定义的关键字

/*
** These are the keywords
*/
static Keyword aKeywordTable[] = {
  { "AND",               0, TK_AND,              0 },
  { "AS",                0, TK_AS,               0 },
  { "ASC",               0, TK_ASC,              0 },
  { "BY",                0, TK_BY,               0 },
  { "CHECK",             0, TK_CHECK,            0 },
  { "CONSTRAINT",        0, TK_CONSTRAINT,       0 },
  { "CREATE",            0, TK_CREATE,           0 },
  { "DEFAULT",           0, TK_DEFAULT,          0 },
  { "DELETE",            0, TK_DELETE,           0 },
  { "DESC",              0, TK_DESC,             0 },
  { "DROP",              0, TK_DROP,             0 },
  { "EXPLAIN",           0, TK_EXPLAIN,          0 },
  { "FROM",              0, TK_FROM,             0 },
  { "INDEX",             0, TK_INDEX,            0 },
  { "INSERT",            0, TK_INSERT,           0 },
  { "INTO",              0, TK_INTO,             0 },
  { "IS",                0, TK_IS,               0 },
  { "ISNULL",            0, TK_ISNULL,           0 },
  { "KEY",               0, TK_KEY,              0 },
  { "NOT",               0, TK_NOT,              0 },
  { "NOTNULL",           0, TK_NOTNULL,          0 },
  { "NULL",              0, TK_NULL,             0 },
  { "ON",                0, TK_ON,               0 },
  { "OR",                0, TK_OR,               0 },
  { "ORDER",             0, TK_ORDER,            0 },
  { "PRIMARY",           0, TK_PRIMARY,          0 },
  { "SELECT",            0, TK_SELECT,           0 },
  { "SET",               0, TK_SET,              0 },
  { "TABLE",             0, TK_TABLE,            0 },
  { "UNIQUE",            0, TK_UNIQUE,           0 },
  { "UPDATE",            0, TK_UPDATE,           0 },
  { "VALUES",            0, TK_VALUES,           0 },
  { "WHERE",             0, TK_WHERE,            0 },
};

关键字结构

/*
** All the keywords of the SQL language are stored as in a hash
** table composed of instances of the following structure.
*/
typedef struct Keyword Keyword;
struct Keyword {
  char *zName;             /* The keyword name */
  int len;                 /* Number of characters in the keyword */
  int tokenType;           /* The token value for this keyword */
  Keyword *pNext;          /* Next keyword with the same hash */
};

语法分析器

任务

根据语法定义，产生对应于语法的语法分析程序。

简述

SQLite 的语法分析器通过 Lemon 产生。因此，分析 SQLite 语法分析器，主要是分析语法定义文件，既 parser.y 文件。
Lemon 为 LALR(1) 分析器，既 Lookahead LR(1)， 该语法分析器是基于有限状态自动机构建的，最终产生的实质上是 LR(1)分析表，其包括 action 表和 goto 表，详细请参考编译原理 LR(1) 部分。

Lemon

简述

要使用 Lemom ，首先，Lemon 需要一份已被准确推敲、仔细思考、再三审核的语法文件，即 parse.y 文件。该文件由上下文无关文法的句法写成，并且还附有当标记符号之间的关系符合某一句型时如何处理该代码。
然后，将 parse.y 文件传入 Lemon 程序，Lemon 即可生成具体的计算机程序，即语法分析器（编译器）。此后，人们才输入具体的程序代码。先用词法分析器将之区分为一个一个有意义的单元（Token），然后将之传入语法分析器（Parse)。语法分析器会按照语法文件中定义的约定，将句型作为”对号入座“的依据，进行正确的处理，从而得到人们需要的结果。

Lemon 工作时，需要两个文件: parse.y 和 lepar.c 文件，parse.y 为语法文件，lepar.c 为语法模板文件。当定义好这两个文件之后，即可调用 Lemon 程序生成语法分析器了，执行下面命令即可：

lemon parse.y

需要注意的是，Lemon 默认拥有 lepar.c 文件，我们可以使用默认的文件。关于 Lemon 的命令行选项，请参考 Lemon 文档。

函数

Lemon 中的几个重要函数如下：
ParseAlloc(): 向操作系统申请构造分析器所需的内存。
ParseFree(): 归还 ParseAlloc() 分配的内存。
Parse(): 接受 tokenzier 产生的 token 并做相应的动作。
ParseTrace(): 跟踪语法分析过程。

语法

• 终结符和非终结符：大写英文字母表示终结符，小写英文字母表示非终结符。
• 产生式：lemon 的产生式定义比较简单，如下：

expr(R) ::= expr(A) PLUS expr(B). {R=A+B}
expr ::= VALUE.

::= 表示可以推导出。
expr® 表示 expr 的别名是 R。
expr® ::= expr(A) PLUS expr(B). {R=A+B} 表示符合 expr(A) PLUS expr(B) 语法是执行 R=A+B 代码块。
expr ::= VAULE 表示 expr 为 VALUE 类型。

特殊声明符

• 优先级：%left 左结合性; %right 右结合性，如 %left PLUS MINUS 表示当遇到 PLUS（加） 和 MINUS（减）时，从左到右依次计算。
• %token_type: 定义 token 的类型.
• %code: 指定 c 或 c++ 代码块
• %destructor：定义析构函数
• %include: 包含外部文件
• %extra_argument：指定了进行语法分析时送进的第四个参数
• %name: 修改语法分析器中的函数的名字。
• %token_prefx: token 前缀
• %syntax_error: 语法错误报错定义处

Parser.y 分析

以下定以了 Token 的前缀为 TK_ ，Token 的类型为 Token，参数的类型为 Parser ，语法错误时调用 sqliteSetNString() 设置错误信息，同时记录错误的 Token。

以下为 SQL 语法定义的基本定义，该部分主要是SQL嵌套定义，explain定义。其中，小写的串为非终结符、大写的串为非终结符。
input 是输入的定义，他是文法的起始符号。他被定义为 cmdlist 和 END_OF_FILE ILLEGAL SPACE UNCLOSED_STRING COMMENT FUNCTION UMINUS FIELD，cmdlist 可以推导出 ecmd 或 cmdlist SEMI ecmd。ecmd 可以推到出 explain cmd 或 cmd 或空，其他的以此类推。语法分析中的这种推导很像数据中的公式展开。
当语法规约到 ecmd ::= explain cmd. 或 ecmd ::= cmd. 时，就执行 sqliteExec() 函数，既执行 VDBE 。

该定义可以简单的化为一下分析树。

以下为创建表的语句的定义

其可以简单的画为一下分析树。

以下为表删除的定义。定语法分析匹配到该行之后，就执行 SqliteDropTable（）函数。

以下为查询语句的语法定义。

以下为表达式的定义。

最后

以上就是感动小丸子为你收集整理的SQLite源码分析-词法分析和语法分析SQLite源码分析-词法分析和语法分析概述词法分析器语法分析器的全部内容，希望文章能够帮你解决SQLite源码分析-词法分析和语法分析SQLite源码分析-词法分析和语法分析概述词法分析器语法分析器所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。