生成高速解析器，第 1 部分：re2c

• 下载演示 - 2.5 KB

解析文本是一个繁琐且容易出错的过程，因此我宁愿使用生成解析器的工具，而不是从头开始编写解析器。有许多可用的选项，包括 ANTLR、bison 和 yacc。但是对于我当前的项目，我需要一个紧凑且执行速度快的 C/C++ 解析器。因此，我选择了两个工具：re2c 用于生成词法分析器，lemon 用于生成解析器。

理解它们之间的区别很重要。re2c 的工作是生成词法分析器，它分析输入文本并将其分解为称为“标记”的有意义的元素。lemon 的工作是生成解析器，它从词法分析器接收标记并构建文本的层次结构模型。

好消息是 re2c 和 lemon 都是免费提供的，并且都生成紧凑、高速的 C 代码。坏消息是它们都具有显著的学习曲线。在撰写这些文章时，我的目标是减轻学习 re2c 和 lemon 所带来的痛苦。

我对这两个工具都不是专家，我也不会假装这些文章提供了全面的处理。但是我已成功使用 re2c 和 lemon 生成了高质量的词法分析器/解析器，我希望这些文章能帮助您也做到这一点。第一篇文章重点介绍 re2c，第二篇文章讨论 lemon。

1. 前期要求

为了解释如何使用 re2c 生成词法分析器，本文采用了一种实践方法。我不期望您了解词法分析的理论，但我期望您能够使用 C 语言编程。

本文中提供的示例代码已使用 gcc 编译。但是，它应该适用于任何 C/C++ 构建系统。

2. 词法分析器概述

本文重点介绍如何使用 re2c 生成能够扫描 C 代码的词法分析器。这个词法分析器无法识别所有 C 语法，但它可以扫描以下代码

/* This is a simple test 
for the re2c-generated lexer */
int main() {
  printf("Hello World");
  return 0;
}

词法分析器读取每个字符并使用正则表达式匹配来返回一系列标记。例如，左括号对应于 LPAREN 标记，return 关键字对应于 RETURN 标记。tokens.h 文件将每个标记名称与一个数字相关联。

本文讨论的词法分析器将文本分成标记，然后打印每个标记的类型、行号和位置。对于上述代码，输出如下

INT_TYPE found on Line 3 at Position 0
NAME ('main') found on Line 3 at Position 4
LPAREN found on Line 3 at Position 8
RPAREN found on Line 3 at Position 9
LBRACE found on Line 3 at Position 11
NAME ('printf') found on Line 4 at Position 2
LPAREN found on Line 4 at Position 8
STRING_LITERAL ('"Hello World"') found on Line 4 at Position 9
RPAREN found on Line 4 at Position 22
SEMICOLON found on Line 4 at Position 23
RETURN_KW found on Line 5 at Position 2
INT_LITERAL ('0') found on Line 5 at Position 9
SEMICOLON found on Line 5 at Position 10
RBRACE found on Line 6 at Position 0

词法分析器不会为初始的多行注释创建标记，但它会为注释后面的行号添加偏移量。

3. 编写标记文件

re2c 的名称代表“正则表达式到 C”，这正是它所实现的目标。它生成检查文本与一系列正则表达式匹配的代码。当它找到匹配项时，它会执行与该表达式关联的 C 代码。例如，以下文本告诉 re2c 在代码中遇到 int 字符串时返回预定义的 INT_TYPE 标记

"int"       { return(INT_TYPE); }

文本和标记之间的关联在称为标记文件 (*.re) 的文件中定义。使用 re2c 的难点在于编写此文件，以便将其转换为词法分析器代码。对于本文讨论的词法分析器，标记文件是 simple_c.re。编写此文件的过程包括四个步骤

1. 定义 Scanner 结构
2. 提供执行扫描器的代码
3. 将正则表达式与代码关联
4. 为 re2c 特定的宏赋值

本节描述了如何为简单的词法分析器完成这些步骤。在可能的情况下，我将遵循 re2c 发行版中示例代码设定的约定。

3.1 定义扫描器

为方便起见，示例代码将 re2c 特定的数据存储在一个名为 Scanner 的结构中。它包含文本中的当前行号 (line) 和四个引用文本中内存位置的指针。以下代码显示了此结构的样子

typedef struct Scanner {
  char *top, *cur, *ptr, *pos;
  int line;
} Scanner;

表 1 列出了每个指针及其用途。

表 1：Scanner 结构的八个指针

指针	目的
顶部	指向当前标记的开头
cur	指向正在检查的字符
ptr	re2c 用于回溯
pos	指向行首

在示例代码中，每个指针都引用 char 的位置。这告诉词法分析器每个输入符号占用一个字节。根据字符集的大小，此数据类型也可以设置为 short、int 或无符号整数类型。

3.2 提供执行扫描器的代码

标记文件需要一个函数来启动扫描过程。如果程序的唯一目的是扫描文本，这将是 main 函数。无论名称如何，此函数都有三个职责

1. 创建 Scanner 结构
2. 为扫描器提供数据
3. 创建扫描循环来处理传入文本

前两个步骤很容易。以下代码将 test.dat 中的输入文本读入缓冲区。然后将 Scanner 的三个指针设置为指向缓冲区的开头。

// Access the text file
fp = fopen("test.dat", "r");
fread(buff, 1, size, fp); 

// Create and initialize the Scanner
Scanner scanner;
scanner.top = buff;
scanner.cur = buff;
scanner.pos = buff;  
scanner.line = 1;

第三步更复杂。扫描循环遍历缓冲区的内容，为找到的每个标记执行一次迭代。以下代码说明了其工作原理

int token = 0;
buff_end = (char*) (((char*)buff) + size);
while(token = scan(&scanner, buff_end)) {
  ... display output for the returned token ...
}

re2c 的实际工作是在 scan 函数中执行的，该函数返回一个唯一标识标记的整数。通常，scan 函数包含一些自定义代码和大量的 re2c 配置。

如果每个输入符号都是 char，scan 函数可能看起来像这样

int scan(Scanner* s, char *buff_end) {

regular:
  if (s->cur >= buff_end) {
    return END_TOKEN;
  }
  s->top = s->cur;

/*!re2c
  ... analyze regular code ...
*/

comment:
/*!re2c
  ... analyze comment ...
*/
}

scan 函数首先检查当前字符 (s->cur) 是否在文本缓冲区 (buff_end) 的末尾。如果是，则函数返回 END_TOKEN。否则，标记的开始 (s->top) 设置为当前字符 (s->cur)。

此代码有两个标签：regular 和 comment。它们是必需的，因为词法分析器代码中的 goto 语句会从这两个标签之一重复处理。像所有合格的程序员一样，我厌恶使用 goto 语句，但在词法分析中，它们是不可避免的。

代码中的两个注释都以 /*!re2c 开头。这告诉 re2c 可执行文件注释块包含与生成词法分析器代码相关的指令。以下讨论解释了其工作原理。

3.3 将正则表达式与代码关联

在 scan 函数中，提供给 re2c 的指令位于以 /*!re2c 开头的注释块内。这些指令可以采用多种形式，最常见的三种语句是

• name = regexp; - 将标识符与正则表达式关联（称为命名定义）
• regexp {code} - 将正则表达式与要执行的 C 代码关联（称为规则）
• re2c:name = value; - 配置 re2c 的 name 参数（称为就地配置）

命名定义阐明了正则表达式的使用。例如，与其在规则中使用 [a-zA-Z]，不如使用像“letter = [a-zA-Z]”这样的命名定义，允许在其中使用名称 letter。

re2c 识别各种正则表达式。表 2 列出了它们及其描述。

表 2：接受的正则表达式格式

表达式格式	描述
"foo"	字面字符串（区分大小写）
'foo'	字面字符串（不区分大小写）
[xyz]	字符类（匹配 'x'、'y' 或 'z'）
[^class]	字符类的反转
a-z	范围（从 'a' 到 'z' 的任何字符）
r \ s	匹配任何不是 s 的字符类 r
r*	零个或多个 r 表达式
r+	一个或多个 r 表达式
r?	零个或一个 r 表达式
名称	命名定义
(r)	覆盖 r 的优先级
r s	表达式 r 后跟 s
r|s	r 或 s
r/s	r 仅在后面跟着 s 时
r{n}	精确匹配 r n 次
r{n,}	匹配 r 至少 n 次
r{n, m}	匹配 r 至少 n 次， 但不超过 m 次
.	除换行符以外的任何字符

前两个表达式尤为重要。以下语句告诉 re2c 在词法分析器遇到 return 字符串时返回 RETURN 标记

"return"        { return RETURN; }

如果将双引号替换为单引号，则模式匹配将不区分大小写。也就是说，当词法分析器遇到 return 或 RETURN 时，将返回该标记。

为了使规则更易于阅读和编写，simple_c.re 使用以下命名定义

dig = [0-9];
let = [a-zA-Z_];

这些名称用于匹配标识符的模式。标识符可以包含数字，但第一个字符必须是字母或下划线。因此，标识符的规则如下

let (let|dig)*  { return NAME; }

空白由一个或多个空格、\t、\v 或 \f 字符组成。此定义如下

whitespace = [ \t\v\f]+;

当词法分析器在常规代码中遇到空白时，它应该忽略这些字符并从 regular 标签重新开始处理。这在以下规则中给出

whitespace      { goto regular; }

除了规则和命名定义之外，re2c 特定的语句还可以包含就地配置语句。这些语句将 re2c 属性与一个值关联起来。例如，re2c:yyfill:enable 属性标识词法分析器是否应该重新填充缓冲区。这在 simple_c.re 中不是必需的，因为缓冲区包含所有文本。因此，使用了以下配置语句

re2c:yyfill:enable = 0;

re2c 还有许多其他可以设置的属性。完整列表由 re2c 手册提供，位于此处。

3.4 为宏赋值

Scanner 结构为开发人员阐明了内存操作，但生成的词法分析器代码对此一无所知。它使用以 YY 开头的宏与应用程序交互。表 3 列出了三个重要的宏

表 3：重要的 re2c 宏

宏	描述	常用值
YYCTYPE	每个输入符号的数据类型	char、short、int， 或无符号类型
YYCURSOR	当前光标位置	一个 Scanner 指针 (s->cur)
YYMARKER	re2c 用于存储 回溯位置	一个 Scanner 指针 (s->ptr)

在 simple_c.re 中，以下代码为这些宏赋值

#define   YYCTYPE     char
#define   YYCURSOR    s->cur
#define   YYMARKER    s->ptr

当 re2c 为词法分析器生成代码时，它使用 YYCTYPE 和 YYCURSOR 等宏访问输入文本。有了这些 #define 语句，编译器会将 re2c 的宏与开发人员的 Scanner 结构关联起来。

4. 生成词法分析器

标记文件由 C 代码组成，但不打算直接编译。在编译之前，它应该使用 re2c 可执行文件进行处理，该文件可以在此处下载。这个命令行实用程序接受许多有用的标志，包括以下内容

• -d - 转储有关词法分析器当前位置和状态的信息
• -u - 支持完整的 Unicode 字符集
• -o - 设置包含词法分析器代码的文件名
• -D - 生成确定性有限自动机 (DFA) 结果的 Graphviz dot 视图

默认情况下，re2c 将其结果打印到标准输出。但是以下命令告诉 re2c 将 simple_c.re 转换为名为 simple_c.c 的词法分析器源文件

re2c -o simple_c.c simple_c.re

如果转换成功，simple_c.c 文件可以使用常规构建命令编译成词法分析器，例如以下命令

gcc -O3 -o simple_c simple_c.c

当 simple_c 执行时，它会将 test.dat 中的文本读入缓冲区，并在循环中调用 scan 函数。scan 的每次迭代都返回一个标记，在 simple_c 的情况下，每次迭代都会打印标记的类型以及它遇到的行和位置。

5. 使用代码

本文的代码生成一个简单的应用程序，用于读取简单的 C 代码。它以名为 re2c_demo.zip 的存档提供，其中包含四个文件

• simple_c.re - 词法分析器定义文件，re2c 可以使用它来生成词法分析器
• tokens.h - 将每个标记与一个整数值关联
• test.dat - 包含要扫描的 C 代码
• Makefile - 包含生成词法分析器和构建应用程序的说明

如果您有 GNU 的 make 和 gcc 实用程序，您可以执行 make 命令。这会读取 Makefile 指令并自动构建应用程序。

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

1. 使用 re2c 生成词法分析器代码 (re2c -o simple_c.c simple_c.re)
2. 将词法分析器代码编译成可执行文件 (gcc -o simple_c simple_c.c)

当应用程序运行时，它会从 test.dat 读取字符并打印它识别的每个标记的信息。

历史

2015/11/21 - 文章首次完成并发布