SQLite源码分析2 Lemon语法分析器 | 模组资料网模组资料网

文章目录[隐藏]

# SQLite源码分析2 Lemon语法分析器
简介
原理
语法
核心规则
试验
总结
参考

# SQLite源码分析2 Lemon语法分析器

简介

如何解析sql语句？可以手写硬来，但非常困难。
对于一门语言，可以借助比较成熟的编译器相关工具来解析。
重点关注语法定义即可。
lemon语法分析器 (The Lemon LALR(1) Parser Generator )
https://sqlite.org/src/doc/trunk/doc/lemon.html
lemon是一个LALR(1)语法解析器。由Richard Hipp在1980年代写的。
2001年起作为sqlite的一部分来维护。
较安全和健壮，比YACC/BISON那一套有所改进。
sqlite使用lemon作为语法分析器。需要先学习lemon的用法。

原理

简单说就是用一系列算法把一串符合某语法的字符进行解析，匹配某一个语法分支，最后转换成C代码。

有两个输入:
1. 语法规则
2. parser模板文件

程序员一般只要编写语法规则即可，lemon有一个默认的通用模板lempar.c。
根据选项可生成三个文件:
1. 实现parser的C代码。
2. 包含每个token及其编号的头文件。
3. 描述parser自动机状态的文件。

lemon不会生成一个完整的可执行程序，而是生成一系列实现parser的函数。

语法

以一个简单的计算器语法为例，实现一个C++计算器。

calc1.y文件

%token_type {int}

%left PLUS MINUS.
%left DIVIDE TIMES.

%include {
#include <iostream>
#include "calc1.h"
}

%syntax_error {
  std::cout << "Syntax error!" << std::endl;
}

program ::= expr(A).   { std::cout << "Result=" << A << std::endl; }

expr(A) ::= expr(B) MINUS  expr(C).   { A = B - C; }
expr(A) ::= expr(B) PLUS  expr(C).   { A = B + C; }
expr(A) ::= expr(B) TIMES  expr(C).   { A = B * C; }
expr(A) ::= expr(B) DIVIDE expr(C).  {
 if(C != 0){
   A = B / C;
  }else{
   std::cout << "divide by zero" << std::endl;
   }
}  /* end of DIVIDE */

expr(A) ::= INTEGER(B). { A = B; }

%include
```
%include {
#include <iostream>
#include "xxx.h"
}
```
%include块可以添加自己的include代码，会放在生成代码的顶部。
错误处理
```
%syntax_error
%parse_failure
```
可以填入自定义的报错处理。比如打印错误信息。
比如运行时输入一条无法解析的句子，就会执行%syntax_error里的代码。
Terminal和Nonterminal(终结符和非终结符)

https://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols
终结符可以看成语法里的一个最小单位，不能再被分解。比如PLUS等加减乘除四个运算符。lemon里需要大写字母开头，一般做成全大写字母。
非终结符可以被转换成其他句子。expr是非终结符。
优先级

一般用%left(left-associative)来定义符号的优先级。越先定义的优先级越小。
比如：
```
%left PLUS MINUS.
%left DIVIDE TIMES.
```
这里加减优先级相同，最小。乘除优先级增加。
%destructor

析构。当一个非终结符(non-terminal)处于某个节点时(可以理解为无用了)，会走析构。
一般用来释放内存。

核心规则

program ::= expr(A).   { std::cout << "Result=" << A << std::endl; }
expr(A) ::= expr(B) MINUS  expr(C).   { A = B - C; }
expr(A) ::= expr(B) PLUS  expr(C).   { A = B + C; }
expr(A) ::= expr(B) TIMES  expr(C).   { A = B * C; }
expr(A) ::= expr(B) DIVIDE expr(C).  {
    if(C != 0){
        A = B / C;
    }else{
        std::cout << "divide by zero" << std::endl;
    }
}  /* end of DIVIDE */

expr(A) ::= INTEGER(B). { A = B; }

按最后一行的定义，expr可以为一个数字。大括号中可填实际的C/C++代码。
按2-5行的定义，expr也可以为加减乘除的组合。
第一行定义最终结果，结果是一个expr。
语法分析器就是按这些定义来对表达式进行分析，得出一个唯一的语义。

比如 2 + 3 * 6
数字匹配为一个expr，得到expr(2) PLUS expr(3) TIMES expr(6)。
按优先级先匹配乘法，按括号中的代码计算3×6，计算得到expr(2) PLUS expr(18)。
匹配加法得到expr(20)。
根据第一行定义，已经得到最终结果20。

试验

ubuntu下可apt install lemon安装lemon
输入lemon calc1.y
可得到calc1.c，calc1.h，calc1.out三个文件。

calc1.c里包含了大量生成的parser代码。不用关心生成的代码。
在calc1.c最后添加一个main。

int main()
{
  void* pParser = ParseAlloc (malloc);

  /* First input: 
      15 / 5
                                */
  Parse (pParser, INTEGER, 15);
  Parse (pParser, DIVIDE, 0);
  Parse (pParser, INTEGER, 5);
  Parse (pParser, 0, 0);

  /*  Second input:
        50 + 125
                               */
  Parse (pParser, INTEGER, 50);
  Parse (pParser, PLUS, 0);
  Parse (pParser, INTEGER, 125);
  Parse (pParser, 0, 0);


  /*  Third input:
        50 * 125 + 125
                               */
  Parse (pParser, INTEGER, 50);
  Parse (pParser, TIMES, 0);
  Parse (pParser, INTEGER, 125);
  Parse (pParser, PLUS, 0);
  Parse (pParser, INTEGER, 125);
  Parse (pParser, 0, 0);

  ParseFree(pParser, free );
}

其中ParseAlloc，Parse，ParseFree是lemon特定的接口，按文档使用即可。

g++ calc1.c -o calc1 编译可得calc1。运行可得到三组结果。
可以修改这个main试一下各种组合，包括不合法的语法。

总结一下

%token_type 指定为token为C的类型int。也可以指定为C结构体。
比如如果想支持小数，可改为double。
把token一个个喂给Parse()。第二个参数为规则里定义的token，生成的数值在calc.h里。
到此已经可以做一个可交互的程序了。用户输入表达式，我们依次找出每一个token，调用Parse即可。
.y里还可以用%code插入任意代码。比如main函数。这样lemon生成代码后直接编译即可。
这里并没有一个正规的tokenizer，是我们手动解出的token。
常用的tokenizer有flex等。
sqlite用的是自研的代码(tokenize.c)。

总结

学习/复习了语法解析相关知识。
学习了lemon语法解析器的使用。
为学习sqlite的sql解析打下基础。

参考

https://sqlite.org/src/doc/trunk/doc/lemon.html
http://souptonuts.sourceforge.net/readme_lemon_tutorial.html
https://en.wikipedia.org/wiki/LALR_parser

转载请注明原文链接：SQLite源码分析2 Lemon语法分析器