2021SC@SDUSC

简介

       SQLite的SQL语言解析器是使用一个名为“Lemon”的代码生成器程序生成的。Lemon程序读取输入语言的语法，并发出C代码来实现该语言的解析器。
       Lemon是一个LALR(1)文法分析器生成工具，它的操作类似于更熟悉的工具。yacc和bison，但是Lemon增加了重要的改进，包括：

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

       2.在Lemon中，令牌程序调用解析器。Yacc的操作方式正好相反，解析器调用令牌程序。Lemon方法是可重入和ThreadSafe，而Yacc使用全局变量，因此两者都不是。可重入性对于SQLite尤其重要，因为一些SQL语句对解析器进行递归调用。例如，在解析CREATETABLE语句时，SQLite递归地调用解析器以生成INSERT语句，以便在SQLITE模式桌子。

       3.柠檬具有非终端析构函数的概念，可用于在语法错误或其他中止的解析之后回收内存或其他资源。

解析器接口

       柠檬不能产生一个完整的工作程序。它只生成几个实现解析器的子程序。本节描述这些子例程的接口。这取决于程序员以适当的方式调用这些子例程，以便生成一个完整的系统。

       在程序开始使用柠檬生成的解析器之前，程序必须首先创建解析器.新的解析器创建如下：

   void *pParser = ParseAlloc( malloc );

       Parsealloc()例程分配并初始化一个新的解析器，并返回指向它的指针。用于表示解析器的实际数据结构是不透明的–其内部结构在调用例程中不可见或不可用。因此，Parsealloc()例程返回指向void的指针，而不是指向特定结构的指针。Parsealloc()例程的唯一参数是指向用于分配内存的子例程的指针。通常这意味着malloc()。

       程序使用解析器完成后，它可以通过调用

   ParseFree(pParser, free);

       第一个参数是Parsealloc()返回的同一个指针。第二个参数是指向用于将大容量内存释放回系统的函数的指针。

       在使用Parsealloc()分配解析器之后，程序员必须向解析器提供一系列要解析的标记(终端符号)。这是通过对每个令牌调用一次以下函数来实现的：

	Parse(pParser, hTokenID, sTokenData, pArg);

       Parse()例程的第一个参数是Parsealloc()返回的指针。第二个参数是一个小的正整数，它告诉解析器数据流中下一个令牌的类型。语法中的每个终端符号都有一个标记类型。由Lemon生成的gra.h文件包含#Defined语句，这些语句将符号终端符号名映射到适当的整数值中。第二个参数的值为0是解析器的一个特殊标志，用于指示已到达输入结束。第三个参数是给定令牌的值。默认情况下，第三个参数的类型是“void*”，但是语法通常会将这种类型重新定义为某种结构。通常，第二个参数将是一个广泛的标记类别，如“标识符”或“数字”，第三个参数将是标识符的名称或数字的值。

       Parse()函数可能有三个或四个参数，这取决于语法。如果语法规范文件请求它(通过%额外论证指令)，Parse()函数将具有第四个参数，该参数可以是程序员选择的任何类型的参数。解析器除了把它传递给动作例程之外，不会对这个参数做任何事情。这是一种方便的机制，可以将状态信息向下传递到动作例程，而不必使用全局变量。

       Lemon解析器的典型使用可能如下所示：

	1 ParseTree *ParseFile(const char *zFilename){2    Tokenizer *pTokenizer;3    void *pParser;4    Token sToken;5    int hTokenId;6    ParserState sState;78    pTokenizer = TokenizerCreate(zFilename);9    pParser = ParseAlloc( malloc );10    InitParserState(&sState);11    while( GetNextToken(pTokenizer, &hTokenId, &sToken) ){12       Parse(pParser, hTokenId, sToken, &sState);13    }14    Parse(pParser, 0, sToken, &sState);15    ParseFree(pParser, free );16    TokenizerFree(pTokenizer);17    return sState.treeRoot;18 }

它解析一个文本文件并返回一个指向解析树的指针。(为了保持简单，本例中省略了所有错误处理代码。)我们假设存在某种令牌，它在第8行使用TokenizerCreate()创建，在第16行被TokenizerFree()删除，第11行的GetNextToken()函数从输入文件中检索下一个令牌，并将其类型放入整数变量hTokenId中。Stoken变量被假定为某种结构，其中包含关于每个令牌的详细信息，例如它的完整文本、发生在哪一行，等等。

       此示例还假定存在一个ParserState类型的结构，该结构包含有关特定解析的状态信息。这种结构的一个实例在第6行上创建，在第10行上初始化。指向该结构的指针作为可选的第4个参数传递到Parse()例程中。语法为解析器指定的操作例程可以使用ParserState结构来保存任何有用和适当的信息。在示例中，我们注意到ParserState结构的treeroot字段指向解析树的根。

       本示例与Lemon相关的核心如下：

   ParseFile(){pParser = ParseAlloc( malloc );while( GetNextToken(pTokenizer,&hTokenId, &sToken) ){Parse(pParser, hTokenId, sToken);}Parse(pParser, 0, sToken);ParseFree(pParser, free );}

       基本上，程序使用柠檬生成的解析器需要做的是首先创建解析器，然后通过标记输入源来发送大量令牌。当到达输入结束时，应该最后一次调用Parse()例程，标记类型为0。这一步骤是必要的，以通知解析器输入的结束已经到达。最后，我们通过调用ParseFree()来回收解析器使用的内存。

       在继续之前，还应该提到另一个接口例程。ParseTrace()函数可用于从解析器生成调试输出。此例程的原型如下：

	ParseTrace(FILE *stream, char *zPrefix);

       调用此例程后，每次解析器更改状态或调用操作例程时，都会向指定的输出流写入一条短消息(一行)。每个这样的消息都使用zPrefix提供的文本作为前缀。通过再次使用第一个参数NULL(0)调用ParseTrace()，可以关闭此调试输出。

附源代码

lemon.c