SQLite中文网
Lemon LALR(1) 解析器生成器
▼ 目录

一、概述

SQLite 的 SQL 语言解析器是使用名为“Lemon”的代码生成器程序生成的。Lemon 程序读取输入语言的语法并发出 C 代码以实现该语言的解析器。

1.1. 柠檬源文件和文档

Lemon 没有自己的源代码库。相反，Lemon 由 SQLite 源代码树中的几个文件组成：

  • lemon.html → Lemon 的原始详细使用文档和程序员参考。

  • lemon.c → 读取语法文件并生成相应解析器 C 代码的实用程序的源代码。

  • lempar.c → 生成的解析器 C 代码的模板。“柠檬”实用程序读取此模板并插入附加代码以生成解析器。

2、柠檬的好处

Lemon 生成一个 LALR(1) 解析器。它的操作类似于更熟悉的工具Yacc和 Bison，但 Lemon 增加了重要的改进，包括：

  • 语法语法不太容易出错——使用符号名称表示语义值，而不是 Yacc 的“$1”式位置符号。

  • 在 Lemon 中，分词器调用解析器。Yacc 以相反的方式运行，解析器调用分词器。Lemon 方法是可重入和线程安全的，而 Yacc 使用全局变量，因此两者都不是。可重入性对于 SQLite 尤其重要，因为一些 SQL 语句对解析器进行递归调用。例如，当解析 CREATE TABLE 语句时，SQLite 递归调用解析器生成 INSERT 语句以在sqlite_schema表中创建一个新条目。

  • Lemon 具有非终端析构函数的概念，可用于在出现语法错误或其他中止解析后回收内存或其他资源。

2.1. 在 SQLite 中使用 Lemon

SQLite 中有两个地方使用了 Lemon。

Lemon 的主要用途是创建 SQL 语言解析器。Lemon将语法文件 ( parse.y ) 编译成 parse.c 和 parse.h。parse.c 文件被合并到合并中，无需进一步修改。

Lemon 还用于为FTS5扩展中的查询模式表达式生成解析器。在这种情况下，输入语法文件是fts5parse.y。

2.2. 柠檬定制，特别是对于 SQLite

托管代码生成器工具作为项目的一部分的优势之一是可以优化这些工具以满足整个项目的特定需求。柠檬就受益于这种效果。多年来，Lemon 解析器生成器得到了扩展和增强，为 SQLite 提供了新功能和改进的性能。专为 SQLite 使用而设计的 Lemon 的一些特定增强包括：

  • Lemon 有一个“后备”令牌的概念。SQL 语言包含大量关键字，这些关键字有可能与标识符名称发生冲突。Lemon 能够将某些关键字指定为能够“回退”到标识符。如果关键字出现在上下文中的输入令牌流中，否则会出现语法错误，则在引发语法错误之前，令牌会自动转换为其回退。此功能允许解析器非常宽容用作标识符的保留字，这是 SQL 语言中经常出现的问题。

  • 为了支持 SQLite 的100% MC/DC 测试目标，Lemon 生成的解析器代码没有无法访问的分支，并且包含额外的（编译时选择的）工具，可用于测量测试覆盖率。

  • Lemon 支持语法文件规则的条件编译，因此可以根据编译时选项生成不同的解析器。

  • 作为性能优化，允许 Lemon 输入语法中的 reduce 动作包含“/*A-overwrites-Z*/”形式的注释，以指示规则右侧的语义值“A”是允许直接覆盖左侧的语义值“Z”。这种简单的优化减少了用于解析输入语法的下推自动机中堆栈操作的数量，从而提高了解析器的性能。它还使生成的代码更小一些。

SQL 语句的解析是任何 SQL 数据库引擎中 CPU 周期的重要消耗者。正在进行的优化 SQLite 的工作导致开发人员花费大量时间调整 Lemon 以生成更快的解析器。这些努力使 Lemon 解析器生成器的所有用户受益，而不仅仅是 SQLite。但是，如果 Lemon 是一个单独维护的工具，那么对 SQLite 和 Lemon 进行协调更改就会更加困难，结果就不会完成那么多的优化。因此，事实证明，解析器生成器工具包含在 SQLite 的源代码树中，这对工具本身和 SQLite 都是一个净收益。

3.柠檬的历史

Lemon 最初是由 D. Richard Hipp（也是 SQLite 的创建者）于 1987 年至 1992 年间在杜克大学读研究生时编写的。Lemon 的最初创建日期已经丢失，但可能是在 1990 年左右的某个时间。Lemon 生成一个LALR(1) 解析器。有一个名为“Lime”的配套 LL(1) 解析器生成器工具，但 Lime 的源代码已经丢失。

Lemon 源代码最初是作为单独的源文件编写的，后来才合并到一个“lemon.c”源文件中。

Lemon 和 SQLite 的作者 (Hipp) 报告说，通过研究 John Ousterhout 的 Tcl 原始源代码，他的 C 编程技能得到了极大的提高。Hipp在1993年发现并研究了Tcl，之前写了Lemon，之后写了SQLite。这两个产品的编码风格有明显的区别，SQLite 似乎更简洁、更易读且更易于维护。