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

错误处理

%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)。
按优先级先匹配乘法，按括号中的代码计算3x6，计算得到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