生成高速解析器，第二部分：Lemon

• 下载演示 - 5.7 KB

上一篇文章解释了如何使用re2c将文本分割成一系列标记。本文将解释Lemon生成的解析器如何使用这些标记来分析文本结构。为了演示Lemon的使用方法，本文的示例包括生成一个简化版C语言的解析器。

Lemon生成的解析器执行LALR(1)解析，其中LALR代表“向前看，从左到右”。这意味着它通过向前查看最多一个标记来匹配标记序列的规则。此解析器执行速度很快，SQLite项目依赖Lemon生成的解析器来分析SQL命令。

1. 前期准备

本文采用实践方法来解释如何用Lemon生成解析代码。要理解本文，您无需熟悉解析理论。但您应该对C语言有扎实的掌握。

本文提供的示例代码已用gcc编译。但是，它应该可以与任何C/C++构建系统一起使用。

还有一件事。许多计算机科学家非常严肃地对待解析主题。我不是那种人，所以如果您觉得本文内容缺乏专业出版物应有的学术严谨性，请不要生气或惊讶。

2. Lemon使用概述

与re2c一样，Lemon也是免费提供的。其主网站提供源代码（lemon.c和lempar.c）以及指向该工具文档的链接。要使用Lemon，需要将lemon.c编译成可执行文件，命令如下：

gcc -o lemon lemon.c

lemon可执行文件接受一个语法文件名，其后缀通常为*.y或*.yy。当可执行文件运行时，它会检查语法文件的内容并生成解析代码。例如，以下命令接受一个名为simple_c_grammar.y的语法文件：

lemon simple_c_grammar.y

只有当lempar.c在工作目录中时，此可执行文件才能正常工作。如果成功完成，Lemon将生成三个输出文件：

• simple_c_grammar.c - 解析器源代码
• simple_c_grammar.h - 定义标记值的头文件
• simple_c_grammar.out - 描述解析器操作的文本文件

*.c文件包含使解析器能够执行的函数。在我讨论这些函数之前，我想解释如何编写语法文件。

3. 编写语法文件

Lemon语法文件由两种类型的语句组成：

1. 规则 - 从其他符号构造语法模式（符号），并可选择执行C代码
2. 指令 - 配置Lemon的操作，每条指令都以%开头

这些语句可以按任何顺序出现。本节讨论这两种类型的语句，但在详细介绍之前，我想先讨论示例编程语言。

3.1 SimpleC编程语言

为了演示Lemon的使用方法，本文将介绍如何生成一个名为SimpleC的简化版C语言的解析器。它与我们熟悉和喜爱的C语言具有相同的语法，但排除了许多功能，包括自定义类型、if-then-else语句和预处理器指令。

以下陈述大致说明了SimpleC程序的结构：

1. 程序由函数和/或变量的声明/定义组成。
2. 变量声明由数据类型、一个或多个由逗号分隔的标识符、可选的初始化程序和分号组成。
3. 函数定义由可选类型、标识符、包围可选参数列表的括号以及花括号内的代码块组成。

这些规则并未涵盖SimpleC的所有内容，但每个程序的结构都可以归结为类似的规则。因此，每个SimpleC程序的结构都可以用一种称为抽象语法树（AST）的树形结构来表示。

例如，考虑以下SimpleC程序：

int x = 0;

main() {
  while(x < 5) {
    x = x+1;
  }
}

图1显示了该程序可能实现的AST。如图所示，AST不包含标点符号，如括号、花括号和分号。

图1：示例抽象语法树

在此树中，没有子节点的节点包含直接从程序文本形成的字符（标记）。这些深灰色节点称为*终结符*，因为它们出现在每个分支的末尾。

浅灰色节点是*非终结符*，它们是通过组合其子节点形成的。树的根节点代表整个程序。在这个简单的例子中，程序由一个变量声明和一个函数定义组成，因此最顶层的节点有两个子节点。

3.2 规则

前面，我介绍了描述SimpleC程序高层结构的语句。语法文件的目的是将这些语句表示成Lemon可以理解的形式。这些语句称为*规则*，每个规则由一个或多个符号构成一个非终结符。

Lemon语法文件中的规则的一般形式如下：

nonterminal_symbol ::= expression. { code }

这里，expression是零个或多个符号的组合。{ code }是在创建非终结符时可选择执行的代码块。

默认情况下，Lemon期望第一个规则的非终结符对应于语法树的根。例如，当program符号由declarations符号创建时，以下规则会将文本打印到控制台：

program ::= declarations. { printf("Constructed the root symbol!\n"); }

Lemon支持递归，因此一个非终结符可以在规则的双方出现。Lemon的文档推荐使用左递归，以下规则声明declarations符号可以包含一个或多个声明符号：

declarations ::= declarations declaration.
declarations ::= declaration.

一个语法文件可以包含同一个非终结符的多个规则。发生这种情况时，Lemon会检查所有规则，并在任何规则适用时形成该符号。换句话说，Lemon不支持使用“|”来表示“或”的表达式，因此有必要为每个备选项编写一个新规则。

到目前为止，所有非终结符都以小写字母书写。这不仅仅是约定。Lemon通过检查首字母的大小写来区分非终结符和终结符：小写表示非终结符，大写表示终结符。一般来说，终结符全部大写。

例如，以下规则表示代表enum语句的非终结符可以由ENUM终结符、NAME终结符、LBRACE终结符、enumerator_list非终结符和RBRACE终结符构成。

enum_specifier ::= ENUM NAME LBRACE enumerator_list RBRACE.

ENUM、NAME、LBRACE和RBRACE终结符对应re2c生成的词法分析器提供的ENUM、NAME、LBRACE和RBRACE标记。稍后，我将解释如何将re2c生成的词法分析器的输出连接到Lemon生成的解析器的输入。

3.3 指令

如前所述，Lemon假定语法文件中第一条规则创建的非终结符是语法树的最顶层节点。但如果program符号应该是最顶层节点，则应添加以下语句：

%start_symbol program

%start_symbol是一个配置Lemon生成的解析器如何工作的指令。表1列出了此指令及其他指令。

表1：Lemon语法文件的特殊指令

指令	描述
%start_symbol	作为语法树顶部的符号
%token_prefix	为头文件中的名称添加前缀
%name	更改生成函数的名称
%token_type	每个标记的数据类型
%token_destructor	终结符的析构代码
%type	非终结符的数据类型
%destructor	非终结符的析构代码
%include	插入到解析器顶部的代码
%left	分配左结合优先级值
%right	分配右结合优先级值
%nonassoc	分配非结合优先级
%parse_accept	成功解析后执行的代码
%parse_failure	解析失败后执行的代码
%syntax_error	语法错误后执行的代码
%stack_size	设置解析器的堆栈大小
%stack_overflow	堆栈溢出时执行的代码
%extra_argument	允许使用第四个参数调用Parse

当Lemon生成解析器时，它还会生成一个头文件，将每个终结符与一个数字关联起来（类似于re2c示例中的tokens.h）。默认情况下，Lemon将使用规则中给出的名称（LPAREN在头文件中将是LPAREN，INT将是INT，依此类推）。但是，如果%token_prefix与文本关联，该文本将添加到头文件中的每个宏前面。

例如，以下指令告诉Lemon在生成的头文件中将TK_添加到每个标记名称的前面。

%token_prefix TK_

%name指令类似，但它不更改标记名称，而是更改解析器接口函数的名称。稍后我将解释，访问解析器的所有函数默认都以Parse开头。但是，如果%name与字符串关联，则函数将以该字符串开头。

%token_type指令与%token_name有很大不同。如前所述，当解析器从词法分析器接收标记时，它还可以接收包含数据的结构。例如，如果解析器需要使用单字节值读取标识符名称，则标记的值可以设置为char*，如下所示：

%token_type { char* }

如果需要在销毁标记数据结构时执行特殊代码，可以将代码块与%token_destructor指令关联。%type和%destructor指令类似于%token_type和%token_destructor，但它们关系到非终结符而不是终结符。

如果代码块与%include关联，Lemon会将代码插入到生成的解析器代码的顶部。因此，此代码块通常包含#include语句和自定义数据结构的声明。这由以下指令显示：

%include {
#include <assert.h>
}

4. 将解析器与re2c集成

如果simple_c_grammar.y是一个合适的语法文件，则以下命令将在名为simple_c_grammar.c的文件中生成解析代码：

lemon simple_c_grammar.y

simple_c_grammar.c中的代码包含四个函数，使应用程序能够访问解析器。表2列出了这些函数并提供了每个函数的描述：

表2：Lemon解析器的接口函数

函数	描述
ParseAlloc(malloc_func)	使用例程分配解析器结构 并返回指向解析器的指针
Parse(void* parser, int token_id,    CustomType tokenData)	将标记发送到解析器
ParseFree(void* parser, free_func)	使用给定的例程取消分配解析器
ParseTrace(FILE* fp, char* trace)	通过提供流来启用解析器跟踪

这些函数易于使用和理解。ParseAlloc接受一个应用于分配内存的函数（通常是malloc），并返回指向解析器的指针。解析器的数据类型不重要，因此应用程序通常将返回的指针视为void指针，如下面的代码所示：

void* parser = ParseAlloc(malloc);

在Parse函数中，第一个参数是解析器，第二个参数标识标记ID（LPAREN、WHILE、FOR等），它应该是一个整数。第三个参数是与标记对应的结构。其数据类型使用前面介绍的%token_type指令设置。

re2c示例代码在一个循环中调用scan函数。循环的每次迭代都对应于输入文本的一个标记。以下代码在循环中调用Parse，以便在接收到每个标记后将其发送到解析器。没有数据随标记一起发送，因此第三个参数设置为NULL。

while(token = scan(&scanner, buff_end)) {
  Parse(parser, token, NULL);
}

在词法分析器发送最后一个标记到解析器之后，它需要再次调用Parse。在这种情况下，标记ID应设置为零，标记值应设置为NULL。我不确定为什么这是必需的，但解析器如果没有它将无法成功完成。以下代码显示了如何实现：

Parse(parser, 0, NULL);

当不再需要解析器时，可以使用ParseFree方法销毁它。它接受ParseAlloc返回的void指针和用于取消分配的例程名称（通常是free）。

4.1 发送/接收标记数据

词法分析器通常会随标记ID一起发送数据。例如，词法分析器可能会传递对应于标识符标记（NAME）的字符串。这意味着将%token_type设置为字符的数据类型（如char*），并将Parser函数的第三个参数设置为字符串。以下代码显示了一种实现方法：

int token, name_length;
char* name_str;

if(token == NAME) {

  // Get the length of the identifier
  name_length = scanner.cur - scanner.top;

  // Allocate memory and copy the identifier from the scanner
  name_str = (char*)malloc(name_length * sizeof(char));
  strncpy(name_str, scanner.top, name_length);
  name_str[name_length + 1] = '\0';

  // Send the token and the string to the parser
  Parse(parser, token, name_str);

  // Free the allocated memory
  free(name_str);
}
else {
  Parse(parser, token, "");
}

解析器可以通过在终结符后面加上括号中的变量名来访问此值。在以下规则中，代码打印与NAME符号关联的str变量的值：

direct_declarator ::= NAME(str). { printf("The identifier is %s\n", str); }

非终结符也可以具有关联值。以下代码将direct_declarator符号与NAME标记的值关联起来：

direct_declarator(strB) ::= NAME(strA). { strB = strA; }

可以使用类似的 D 代码在规则之间传递数据。另一种方法是使用额外的参数调用Parse函数。这是以下讨论的主题。

4.2 额外参数

Lemon不允许在语法文件中设置全局变量。这有助于确保线程安全，但使得不同规则难以访问相同的数据。为了实现全局数据访问，Lemon允许词法分析器向Parse函数添加一个可选的第四个参数。

此额外参数可以是任何类型，并且可以通过将%extra_argument设置为包含参数类型和变量名的块来启用。在SimpleC示例语法中，Parse的第四个参数允许应用程序计算声明和函数定义的数量。此参数是指向ParserCount结构的指针，该结构定义如下：

typedef struct ParserCount {
  int numFunctionDefinitions;
  int numVariableDeclarations;
} ParserCount;

词法分析器创建ParserCount，初始化其字段，并使用以下代码将其发送到解析器：

Parse(parser, token, "", &pCount);

在语法文件中，ParserCount结构在%include指令中定义，以便将其插入到生成代码的顶部。以下指令允许在整个解析器中访问pCount变量：

%extra_argument { ParserCount *pCount }

以下规则访问pCount以增加函数定义和变量声明的数量：

external_declaration ::= function_definition. { pCount->numFunctionDefinitions++; }
external_declaration ::= declaration. { pCount->numVariableDeclarations++; }

额外参数可以设置为顶层非终结符的值。该值是指向对应于输入文本的语法树的指针。

5. 错误处理

如果解析器无错误地完成其分析，Lemon将执行与%parse_accept指令关联的代码块。如果发生错误，Lemon将执行与%syntax_error关联的代码。之后，它会回溯，直到达到一个可以移入名为error的非终结符的状态。然后它会尝试正常继续解析。

如果解析器一直回溯到开头，并且无法移入error符号，它将执行与%parse_failed指令关联的代码。然后它会将自身重置到其起始状态。

根据我的经验，检测错误的最有用的工具是表2中的ParseTrace函数。它向流打印消息，描述解析器的当前状态。例如，以下代码告诉Lemon将状态消息打印到名为traceFile的文件指针，并在每条消息前加上“parser >>”。

ParseTrace(traceFile, "parser >>");

解析器运行时，它会打印如下消息：

parser >> Input 'LPAREN'
parser >> Reduce [direct_declarator ::= NAME], go to state 92.
parser >> Shift 'direct_declarator', go to state 135
parser >> Shift 'LPAREN', go to state 58
parser >> Return. Stack=[external_declaration_list declaration_specifiers direct_declarator LPAREN]

如果解析器遇到语法错误，它会提供警报消息。

parser >> Shift 'logical_or_expression', go to state 141
parser >> Reduce [conditional_expression ::= logical_or_expression], go to state 41.
parser >> Shift 'conditional_expression'
parser >> Reduce [constant_expression ::= conditional_expression], go to state 41.
parser >> Shift 'constant_expression', go to state 179
parser >> Syntax Error!

通过检查这些消息，应用程序可以大致了解错误发生的位置。在发生语法错误时，最好将%syntax_error与Parse的额外参数一起使用，以通知词法分析器。

6. 使用代码

本文的代码生成了一个SimpleC的解析应用程序。它包含在一个名为lemon_demo.zip的存档中，该存档包含四个文件：

• simple_c.re - 词法分析器定义文件，re2c可以使用它生成一个词法分析器
• simple_c_grammar.y - SimpleC语法文件，Lemon可以使用它生成解析代码
• test.dat - 包含可以成功解析的C代码
• Makefile - 包含生成词法分析器和解析器以及构建应用程序的说明

如果您安装了GNU的make和gcc工具，可以执行make命令。这将读取Makefile的说明并自动构建应用程序。

如果您想手动构建应用程序，需要执行三个步骤：

1. 使用Lemon从语法生成解析代码（lemon simple_c_grammar.y）
2. 使用re2c生成词法分析器代码（re2c -o simple_c.c simple_c.re）
3. 编译词法分析器和解析器代码（gcc -o simple_c simple_c.c simple_c_grammar.c）

该应用程序解析test.dat中的代码。除了向标准输出打印消息外，它还使用ParseTrace将状态消息打印到trace.out。

历史

2015年11月21日 - 文章完成并首次发布

2015年11月22日 - 修正了图片链接和拼写错误（感谢Garth！）

2015年11月22日 - 添加了对re2c上一篇文章的链接