• 欢迎大家分享资料!前往留言板评论即可!

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

合宙 模组资料网 7个月前 (05-15) 137次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

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

其中ParseAllocParseParseFree是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语法分析器
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址