65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 RE/flex 构建快速词法分析器 - 为什么需要另一个扫描器生成器？

Robert van Engelen
starIconstarIconstarIconstarIconstarIcon

5.00/5 (34投票s)

2017年4月25日

BSD

25分钟阅读

viewsIcon

55906

downloadIcon

505

RE/flex for C++

引言

本文将介绍 **RE/flex 词法分析器生成器**。RE/flex 开源项目的动机是，可以基于一种完全不同的**分词**方法来构建生成器，这种方法允许生成的**扫描器**（又称**词法分析器**、**lexers**和**分词器**）使用正则表达式库。这种方法提供了额外的优势，例如灵活选择 **POSIX 模式**甚至 **Perl 模式**（！）正则表达式引擎，以及丰富的正则表达式语法，包括对 Unicode 的支持。另一个动机是挑战创造一种新算法，用于构建**确定性有限自动机**（DFA），以高效地进行**惰性量词**（又称**非贪婪重复**、**惰性重复**和**不情愿重复**）的模式匹配。这个算法也是新的。我的第三个目标是让 RE/flex 比 Flex 更快，至少在典型情况下是如此。我知道这是一个挑战，因为 Flex（**快速词法分析器**）已经存在很长时间，并且 Flex 的贡献者使其非常快。性能测试表明，RE/flex 比 Flex 更快，也比其他可用于扫描的正则表达式库更快。

为什么选择 RE/flex？

RE/flex 是一款新的快速灵活的基于正则表达式的 C++ 扫描器生成器。它与 Flex 和 Lex 有许多相似之处，但由于多种原因，其整体设计是根本不同的。首先，该设计旨在通过使用直接编码的 DFA 来使 RE/flex 比 Flex 更快，这种 DFA 通常通过现代 CPU 进行模拟效率更高。其次，该设计通过支持其他正则表达式库（包括 PCRE2 和 Boost.Regex，以及内置的 RE/flex 正则表达式引擎），提供了更具表达力的正则表达式语法，可用于词法分析器规范。将来可能会包含其他正则表达式库，以扩展匹配器引擎的选择。第三，该设计生成的扫描器是人类可读的源代码，其结构清晰地展示了用户在源代码形式中，完全按照用户**词法分析器规范**中指定的操作。

这种强大的新设计之所以成为可能，是因为任何正则表达式引擎原则上都可以用于对输入进行分词：给定一组 *n* 个模式 *pi*，*i*=1,...,*n*，形式为 "( *p*1 ) | ( *p*2 ) | ... | ( *pn* )" 的正则表达式可以用于匹配和分词输入。正则表达式匹配器返回的匹配模式 *pi* 的组捕获索引 *i* 标识了匹配的模式 *pi*。如果一个模式使用组 `(X)`，那么在我们的模式中使用它之前，必须将其转换为形式为 `(?:X)` 的非捕获组。然后，我们通过在扫描器中重复部分匹配来推进输入进行分词，通过执行与匹配模式相对应的特定**动作**。

int Lexer::lex()
{
  if (!has_matcher())
    matcher("(p1)|(p2)|...|(pn)"); // new matcher engine if not set up already
  while (true)
  {
    if (... EOF reached ...)
      return 0;
    switch (matcher().scan()) // scan and match next token, get capture index
    {
      case 1:   // pattern p1 matched
        ...     // Action for pattern 1 ...
        break;
      case 2:   // pattern p2 matched
        ...     // Action for pattern 2 ...
        break;
      ...       // etc ...
        ...
      default:
        ...     // no match: this is the "default rule" to echo input character ...
    }
  }
}

由 reflex 工具生成的扫描器源代码以此方式构建，因此与 Flex 生成的源代码大相径庭。改进后的源代码输出不仅人类可读，而且当使用 reflex 选项 `--fast` 生成扫描器时，其运行速度通常也比 Flex 代码快。该 reflex 选项以直接代码而非表格形式生成高效的 DFA。例如，以下 DFA 是由 reflex 选项 `--fast` 为模式 `"\w+"` 生成的，它能非常高效地匹配单词。

void reflex_code_FSM(reflex::Matcher& m)
{
  int c1 = 0;
  m.FSM_INIT(c1);
S0:
  c1 = m.FSM_CHAR();
  if (97 <= c1 && c1 <= 122) goto S5;
  if (c1 == 95) goto S5;
  if (65 <= c1 && c1 <= 90) goto S5;
  if (48 <= c1 && c1 <= 57) goto S5;
  return m.FSM_HALT(c1);
S5:
  m.FSM_TAKE(1);
  c1 = m.FSM_CHAR();
  if (97 <= c1 && c1 <= 122) goto S5;
  if (c1 == 95) goto S5;
  if (65 <= c1 && c1 <= 90) goto S5;
  if (48 <= c1 && c1 <= 57) goto S5;
  return m.FSM_HALT(c1);
}

RE/flex 的另一个优点是 PCRE2 和 Boost.Regex 以及 RE/flex 软件中包含的新 RE/flex 正则表达式库提供的丰富正则表达式模式语法。RE/flex 正则表达式库支持 Unicode、缩进/不缩进/反缩进锚点、惰性量词、单词边界等。

RE/flex 的速度有多快？

在比较 Flex 和最佳性能选项时，RE/flex 比 Flex 更快。RE/flex 也比 `Boost.Spirit.Lex` 更快，并且比流行的正则表达式库（例如 `Boost.Regex`、C++11 `std::regex`、PCRE2 和 RE2）快得多。例如，将一个代表性的 C 源代码文件分词为 244 个标记仅需 8 微秒。

命令/函数 软件 时间 (μs)
reflex --fast --noindent RE/flex 1.6.7 8
reflex --fast RE/flex 1.6.7 9
flex -+ --full Flex 2.5.35 17
reflex --full RE/flex 1.6.7 18
boost::spirit::lex::lexertl::actor_lexer::iterator_type Boost.Spirit.Lex 1.66.0 40
pcre2_jit_match() PCRE2 (jit) 10.32 60
hs_compile_multi(), hs_scan() Hyperscan 5.1.0 209
reflex -m=boost-perl Boost.Regex 1.66.0 230
pcre2_match() PCRE2 (预编译) 10.30 318
RE2::Consume() RE2 (预编译) 2018-04-01 417
reflex -m=boost Boost.Regex POSIX 1.66.0 450
RE2::Consume() RE2 POSIX (预编译) 2018-04-01 1226
flex -+ Flex 2.5.35 3968
std::regex::cregex_iterator() C++11 std::regex 5979

该表显示了在 Mac OS X 10.12.6 clang 9.0.0 -O2、2.9 GHz Intel Core i7、16 GB 2133 MHz LPDDR3 配置下，100 次运行的 30 次测试中平均时间（微秒）的最佳结果。Hyperscan 因其“报告所有匹配项”的语义（在此测试中产生 1915 个匹配项）以及其事件处理程序要求而不适合作为潜在的扫描器。在此下载测试。下载内容包含一个 Dockerfile，其中包含在几乎任何系统上测试性能的说明。

RE/flex 跟踪行号、列号和行缩进，而 Flex 在此比较中不跟踪（通过选项 `%option noyylineno` 禁用），表格中的其他正则表达式匹配器也不跟踪，除了与 RE/flex 一起使用的 Boost.Regex。跟踪这些信息会产生一些开销。RE/flex 缩进跟踪通过 `--noindent` 禁用，以消除缩进跟踪的开销。

为了尽可能公平地生成此性能统计表，我使用了 RE/flex 选项 `--regexp-file` 来生成正则表达式字符串，并将其与每个正则表达式库一起使用，以对存储在内存中的 C 源代码字符串进行分词，从而避免了文件 IO 不可预测的开销。此正则表达式字符串具有 *n*=56 个形式为 "( *p*1 ) | ( *p*2 ) | ... | ( *pn* )" 的模式，其中每个 *pi* 是一个用于匹配 C/C++ 标记**词素**的模式。这些模式使用非捕获组 (?:...) 来替换括号，这允许捕获组索引标识匹配的标记。通过这种方式，我试图通过测量对存储在内存而非文件中的输入进行分词所需的时间，即测量没有 IO 开销的原始性能，来使性能比较尽可能公平。当然，性能取决于硬件和操作系统，因此您的结果可能有所不同。然而，对现代 CPU 和操作系统版本的测试仍然表明，在典型用例中，RE/flex 比 Flex 更快。

RE/flex 与 Flex 和 Bison/Yacc 的兼容性

在设计 RE/flex 时，我希望确保该项目与 Bison 和 Yacc 解析器完全兼容。这些工具很流行，通常预装在 Linux 和 Unix 发行版中。我还希望确保 RE/flex 接受标准 Flex 规范（使用 RE/flex 兼容性选项 `--flex`）。这意味着如果您已经熟悉 Flex 或 Lex，那么您会发现 RE/flex 易于使用。要生成一个与 Flex++ `yyFlexLexer` 类具有相同方法的 `yyFlexLexer` 类，只需使用 reflex 选项 `--flex`。

reflex --flex lexspec.l

这会在 *lex.yy.cpp* 中生成扫描器源代码。RE/flex 仅适用于 C++ 项目。使用 C++ 允许对词法分析器规范语言进行大量添加，并允许引入许多可在规则动作中使用的新方法，我将在下一节中进一步解释。然而，您仍然可以将 RE/flex 与 C 代码一起使用，例如期望全局 `yylex()` 函数的 Bison 生成的解析器。为此，请使用 `--flex` 和 `-bison` 命令行选项，或者只需使用 `--yy` 组合这些选项并强制 POSIX 兼容性。

reflex --yy lexspec.l

然而，RE/flex 也支持构建 Bison **可重入**解析器、**bison-bridge**、**bison-locations** 和 **bison-complete** 解析器的选项。这些高级解析器是线程安全的，并与词法分析器协作管理语法错误的位置。

为了帮助您开始使用 RE/flex，您可以在 GitHub 和 SourceForge 上的 RE/flex 仓库中找到几个示例。这些示例包括 Bison 解析器，从非常基础的到更高级的 bison-bridge、bison-location 和 bison-complete 解析器。

RE/flex 词法分析器规范的结构

词法分析器规范的结构与 Flex 相同，但有一些补充。词法分析器规范由三部分组成，用一个包含 `%%` 的行分隔开：**定义部分**、**规则部分**和**用户代码部分**。

  1. **定义部分**定义命名模式。也就是说，常用的正则表达式模式可以命名，并在其他模式中作为宏使用。此部分还可以包含用户代码：一个 ` %top{`...`}` 块，其代码一直复制到生成的扫描器源代码的顶部，以及通常的 `%{`...`%}` 代码块复制到扫描器的源代码中。一个 ` %class{`...`}` 块定义了词法分析器类的成员变量和函数。`%init{`...`}` 块定义了词法分析器类构造函数用于初始化的代码。我们还可以添加一个或多个 `%option` 来配置扫描器，并使用 `%s` 和 `%x` 定义**起始条件状态**。
  2. **规则部分**定义模式-动作对。动作是用 C++ 编写的，并在模式匹配时触发。
  3. **用户代码部分**在规范的末尾，可用于添加任何必要的 C++ 代码。对于独立扫描器，此处通常定义一个 `main()` 函数。

以下概述了 RE/flex 词法分析器规范的基本结构：

// DEFINITIONS go here

%top{
  #include <iostream>
  // ... other stuff to #include <...> all the way at the top
}

%{
  // ... other stuff to declare in C++
%}

// customize the generated Lexer class (optional):
%class{
 public:
  void a_public_function();
 private:
  std::string a_private_string;
}

// customize the generated Lexer class default constructor (optional):
%init{
  a_private_string = "initialized";
}

// enable Unicode matching:
%option unicode

// add a named pattern:
newline  \n

%%

// RULES go here, where a rule is a pattern and action

"foo"      { a_public_function(); }
"bar"      { a_private_string = text(); }
{newline}  // skip newline
.          { std::cerr << "unknown character at " << lineno() << ":" << columno(); }

%%

// USER CODE goes here

int main()
{
  Lexer lexer;
  while (lexer.lex() != 0)
    continue;
}

模式是扩展了常见 Lex/Flex 语法的正则表达式，这意味着命名模式 `{newline}` 扩展为 `(?:\n)`，带引号的文本 `"foo"` 是 `foo` 的字面匹配，而斜杠 `/`（示例中未显示）是先行模式（在 Lex 中传统上称为**尾随上下文**）。

此示例显示了规则操作中使用的三个内置函数：`text()` 返回匹配的以 0 结尾的字符文本，`lineno()` 和 `columno()`。前两个与 Flex 中的 `yytext` 和 `yylineno` 相同。Flex 兼容操作通过 reflex 选项 `--flex` 启用。

下表显示了可用于规则操作的 RE/flex 函数长列表中的一些操作：

RE/flex 动作 Lex/Flex 动作 结果
text() YYText(), yytext 以 0 结尾的文本匹配
str() 不适用 std::string 文本匹配
wstr() 不适用 std::wstring 文本匹配
size() YYLeng(), yyleng 匹配的字节大小
wsize() 不适用 匹配的宽字符数
lineno() yylineno 匹配的行号 (>=1)
columno() 不适用 匹配的列号 (>=0)
echo() ECHO 回显文本匹配
start(n) BEGIN n 将起始条件设置为 n

表中列出的经典 Lex/Flex 动作可以通过 reflex 选项 `--flex` 在 RE/flex 词法分析器规范中使用。由于匹配器库对象可通过 `matcher()` 在规则动作中访问，因此您可以在规则动作中使用它来增加功能。以下是一些有用的 `matcher()` 方法示例：

RE/flex 动作 Flex 动作 结果
matcher().input() yyinput() 从输入中获取下一个 8 位 `char`
matcher().winput() 不适用 从输入中获取宽字符
matcher().unput(c) unput(c) 放回 8 位 `char`
matcher().more() yymore() 将下一个匹配项连接到此匹配项
matcher().less(n) yyless(n) 将匹配长度缩小到 n
matcher().line() 不适用 将整行作为包含匹配项的字符串获取

这些只是几个例子。有关完整列表，请参阅 RE/flex 用户指南。

Unicode 模式匹配

一个无法处理 Unicode 的扫描器生成器，就如同用打字机在手机上发短信一样。大多数现代编程语言都有 Unicode 词法结构，需要支持 Unicode 的扫描器来构建解析器和编译器。至少应该原生支持广泛使用的 UTF-8 编码格式。扫描器生成器生成的词法分析器会扫描文件（除了 8 位字符串，可能还有宽字符串），这使得它们与正则表达式引擎不同，即大多数正则表达式库可以用于匹配宽字符串。要扫描包含 Unicode 的文件，必须从 UTF-8、UTF-16 或 UTF-32 (UCS-4) 格式解码这些文件。在 RE/flex 中，这种解码是**即时**自动高效完成的。

Unicode 模式匹配通过 reflex 命令行选项 `--unicode` 或词法分析器规范中的 `%option unicode` 启用。

%option unicode

使用此选项，`.`（点）、`\w`、`\s`、`\l`、`\u`、`\u{XXXX}` 和 `\p{`...`}` 模式将匹配 Unicode。它们分别匹配任何 Unicode 字符（除了换行符 `\n`）、Unicode 单词字符、Unicode 空格、Unicode 小写字母、Unicode 大写字母、Unicode U+XXXX 和 Unicode 字符类。

\s+          // skip spacing
\w+          { std::cout << text() << "\n"; }
\p{Unicode}  { std::cout << "U+" << std::hex << wstr().at(0) << " \n"; }
.            { std::cerr << "invalid Unicode!\n"; }

这个词法分析器从文件中删除所有空格，并打印由 Unicode 字母、数字和连接标点（如下划线）组成的单词。匹配的文本以 UTF-8 格式打印到 `std::cout`，使用 `text()`（与 Flex 语法中的 `yytext` 相同）。任何其他 Unicode 字符都使用宽字符串 `wstr()` 匹配的第一个字符以 U+XXXX 代码打印。最后，`.`（点）模式用于捕获所有其他内容，包括超出有效 Unicode 范围 U+0000 到 U+D7FF 和 U+E000 到 U+10FFFF 的无效字符。当扫描 UTF-8 或 UTF-16 文件时，无效的 UTF 编码（如超长形式）也会被 `.`（点）匹配。

要匹配任何有效的 Unicode 字符，我建议使用 `\p{Unicode}`。我们只在需要时使用 `.`（点）作为**捕获所有其他**情况。其中一种情况是匹配无效内容，如上例所示，以防止扫描器在没有有效匹配时**卡住**其输入。因此，`.`（点）被设计为宽容的，既匹配有效的 Unicode，也匹配无效的 UTF-8 和 UTF-16 序列，以便捕获文件编码错误。我还使 `.`（点）能够自同步，这意味着在匹配无效字符后，它会前进到输入中的下一个字符。

缩进、不缩进和反缩进匹配

RE/flex 采用直接方法匹配文本中的 `indent`、`nodent` 和 `dedent` 位置，通过引入两个新的锚点，一个用于 `indent`，一个用于 `dedent`。当这些锚点与第三个 `undent` 锚点 `\k` 结合使用时，已被证明足以处理应用于作为扫描器输入文档的任何复杂缩进规则，例如 Python 和 YAML（RE/flex 中包含 Python 和 YAML 的分词器）。

这种方法相当直接。在新行上使用模式 `^[ \t]+\i` 匹配 `indent` 停止位置。请注意，`^[ \t]+` 匹配边距空间直到与 `\i` 匹配并设置的缩进，但仅当边距空间增加时才匹配。

同样，`dedent` 用 `^[ \t]*\j` 匹配。这会匹配一个先前的 `indent` 停止点并将其从内部堆栈中移除。

由于边距空间更大程度的减少可能导致多个停止位置一次性被移除，我们还应该添加一个带有单个 `\j` 锚点的模式来匹配每个额外的缩进停止点。这会一次匹配同一行上发生的任何额外 `dedent`，而不会消耗任何输入。

^[ \t]+    // nodent: text is aligned to the current indent margin
^[ \t]+\i  // indent: text is indented with new indent set and matched by \i
^[ \t]*\j  // dedent: text is dedented, matched by \j
\j         // dedent: text is dedented by an extra indent stop on the current line

一些网络文章建议 Lex/Flex 可以用于缩进匹配，但它们完全忽视了多重反缩进（即上述第四条规则）的问题，这在 Lex/Flex 中无法可靠地工作。

请注意，与当前停止位置对齐的 `nodent` 行的匹配是通过缺少 `\i` 和 `\j` 锚点的模式完成的。

让我们看看它是如何工作的。假设我们要扫描的输入如下：

def abs(n):
    if n < 0:
        n = -n
        return n
    else:
        return n
# EOF

然后我们定义的四个模式按此顺序匹配：`2, 2, 1, 3, 2, 3, 3`。请注意，第一行没有缩进边距，也没有缩进停止。

对仅使用空格进行缩进没有限制，例如 `[ \t]+`，它定义了边距间距。边距间距可以是任何东西，而不仅仅是空格和制表符，只要模式不包含换行符 `\n`。

当扫描跨越多行的文本时，由不应改变当前缩进停止位置的模式（如行延续、多行注释和需要“行连接”的表达式，如 Python 中）可能需要临时记住缩进停止点。这可以通过使用 `matcher().push_stops()` 保存当前缩进停止点，并使用 `matcher().pop_stops()` 再次检索它们来完成。

例如，为了扫描跨多行（缩进）的多行注释而不影响当前缩进停止点，我们应该保存当前停止点并转换为新的起始条件状态 `CONTINUE`。

"/*"          matcher().push_stops(); // save the indent margin/tab stops
              BEGIN CONTINUE;         // BEGIN state transition to CONTINUE w/o indent matching
<CONTINUE>{
"*/"          matcher().pop_stops();  // restore the indent margin/tab stops
              BEGIN INITIAL;          // BEGIN state transition to INITIAL
.|\n          /* ignore */
}

我们通常在扫描由不同模式和规则匹配的文本时定义**起始条件状态**，例如本例中的 `CONTINUE`。`matcher().push_stops()` 方法会重置缩进停止位置。这些位置可以直接通过 `matcher().stops()` 访问，该方法返回一个对 `std::vector` 的引用，其中包含这些按低到高排序的位置。您可以更改该向量，只要保持低到高顺序即可。

当文本需要被扫描器忽略时，例如多行注释和行延续，有一种快速匹配多行文本的方法。为了实现在行尾放置 `\`（反斜杠）后的行延续，我们必须忽略下一个缩进。同样，使用模式 `"/*"(.|\n)*?"*/"`（使用惰性重复 `(.|\n)*?`）匹配的 C 风格多行注释应该被忽略，并且不影响当前缩进停止点。为此，我们使用 RE/flex `(?^X)` **负模式**，它会消耗文本而不执行任何操作，使输入的匹配部分实际上不可见。

(?^"/*".*?"*/")  // ignore multi-line comments
(?^\\\n[ \t]*)   // lines ending in \ will continue on the next line

负模式 `(?^X)` 是 RE/flex 特有的新增功能。它可以非常方便地用于跳过不需要的输入，例如注释，而不会影响缩进停止位置。但是，与负模式关联的任何操作都不会执行，因为负模式会跳过输入并且不会触发模式匹配。

最后，`undent` 锚点 `\k` 可用于模式中。当缩进深度在锚点 `\k` 在其模式中的位置处或之前发生变化时，`undent` 锚点匹配，即，当带有 `\i` 或 `\j` 的模式也会匹配时。锚点 `\k` 保持当前停止点不变，实质上撤销了缩进变化（即“取消缩进”）。例如，要忽略可能嵌套的多行注释，我们可以按如下方式使用锚点 `\k`：

%{
  int level;   // a variable to track the /*-comment nesting level
%}

%x COMMENT

%%
^[ \t]+        out() << "| ";    // nodent, text is aligned to current margin column
^[ \t]+\i      out() << "> ";    // indent
^[ \t]*\j      out() << "< ";    // dedent
\j             out() << "< ";    // dedent, triggered for each extra level dedented
[ \t]*"/*"\k?  level = 1;        // /*-comment after spacing, \k kills indent stop changes
               start(COMMENT);   // goto COMMENT
.|\n           echo();           // ECHO character

<COMMENT>{
"/*"           ++level;          // allow nested /*-comments 
"*/"           if (--level == 0)
                 start(INITIAL); // goto INITIAL (back to initial state)
.|\n                             // ignore all content in comments
}
%%

请注意，`[ \t]*"/*"\k?` 匹配带前导空格的 `/*`-注释的开头。当此空格位于左边距时，它也最初由第二条或第三条规则匹配到 `/*`，分别导致 `\i` 和 `\j` 锚点进行的缩进停止更改。即使规则 2 和 3 不匹配 `/*`，而只匹配前导 `/*` 的边距中的空格，`\i` 和 `\j` 锚点也会更改缩进停止。锚点 `\k` 恢复这些停止点，并在缩进停止点实际更改时匹配。规则 5 也适用于非边距 `/*`-注释，`/*`-注释可以放置在任何位置。由于这两个原因，我们将 `\k` 设为可选的 `\k?`。

有关缩进、不缩进、反缩进和撤销缩进模式的更多详细信息和示例，请参阅 RE/flex 用户指南。

惰性重复虽然好用，但也有其顽劣之处

在上一节中，我们看到了如何使用**惰性重复** `(.|\n)*?` 来匹配 C 风格的多行注释，例如 ` "/*"(.|\n)*?"*/" `。额外的 `?` 称为**惰性量词**，它将 `*` **贪婪重复**变为 `*?` 非贪婪**惰性重复**（也称为**不情愿重复**）。为什么这里需要惰性重复？请注意，模式 `(.|\n)` 匹配任何字符（`.`（点）匹配除换行符 `\n` 之外的任何字符）。问题在于，模式 ` "/*"(.|\n)*"*/" ` 中的贪婪重复 `(.|\n)*` 会吞噬**所有**匹配的文本，**包括** `*/`，直到输入文本中 EOF 之前的最后一个 `*/`。解决贪婪重复的常见方法是阻止重复模式匹配 `*/`，例如 ` "/*"([^*]|\*+[^/])*"*/" `。相比之下，惰性重复更简单、更优雅。

惰性量词 `?` 可用于使以下贪婪模式变为惰性：

X??Y      // matches zero or one X as needed to match Y next
X*?Y      // matches zero of more X as needed to match Y next
X+?Y      // matches at least one X or more as needed to match Y next
X{n,m}?Y  // matches at least n times and at most m times X to match Y next

以模式 `(a|b)*?bb` 为例。文本 `abaabb` 和 `bb` 匹配此模式，但 `bbb` 不匹配（实际上，存在部分匹配，因为 `bb` 匹配此模式，但第三个 `b` 仍留在输入中供扫描器进行下一次匹配）。

那没有连续模式 `Y` 的模式 `a*?` 呢？这不匹配任何东西。当模式 `Y` 允许空文本匹配或与 `X` 匹配相同的文本时，惰性会扼杀 `X`。为了让惰性重复表现良好，请确保它们后面跟着匹配非空文本的模式，或者确保它们正确锚定。例如，`a*?$ `匹配一系列 `a` 直到行尾。然而，在这种情况下，不需要惰性，贪婪模式 `a*$` 也能正常工作。

惰性重复在 POSIX 匹配器中不可用。这个概念是在 Perl 中引入的，它**基于正则表达式**，通过对正则表达式进行回溯（或者使用另一种形式的匹配引擎）。POSIX 匹配器是**基于文本**的，可以使用**确定性有限自动机** (DFA) 来显著加快匹配速度。基于 DFA 的匹配器缺乏惰性量词，因为无法动态评估这种**基于正则表达式**的信息适用的上下文。

RE/flex 使用一种新的 DFA 构造算法将其惰性量词添加到其 POSIX 匹配器中。惰性重复有效地**切断了 DFA 的边**，但也可以延长 DFA 以允许部分匹配，直到达到接受状态。考虑为正则表达式 `(a|b)*bb` 构造的以下 DFA。

并将其与为正则表达式 `(a|b)*?bb` 构造的 DFA 进行比较。

如您所见，第二个 DFA 匹配任何 `a` 和 `b`，直到匹配到 `bb`。

使用智能输入类扫描文件

我们经常需要扫描包含各种流行格式（如 UTF-8、UTF-16、UTF-32、ISO-8859-1，有时甚至是更旧的编码格式，如代码页 850、CP-1252 和 EBCDIC）编码的文本文件。为了支持多种输入文件格式，RE/flex 的 `reflex::Input` 类通过智能缓冲技术在扫描输入时动态转换输入格式。这种智能缓冲不需要先读取整个文件，从而允许实现流式词法分析器和正则表达式匹配器。流式转换器检测文件中的 UTF **字节顺序标记** (BOM)，通过将文本标准化为 UTF-8 进行匹配，从而实现自动 UTF-8/16/32 转换。事实上，当通过 `%option unicode` 启用 Unicode 匹配模式时，输入**应该**以这种方式进行 UTF 编码。

如果输入文件以 EBCDIC、ISO-8859-1 或扩展 Latin-1 编码，那么您应该在代码中确定这一点，并设置解码标志，以便将此文件与 RE/flex 词法分析器一起使用。例如，如下所示：

#include "lex.yy.h" // generated with reflex --flex --header-file

int main()
{
  FILE *fd = fopen("iso-8859-1-example-file.txt", "r");           // open a file
  if (fd != NULL)
  {
    reflex::Input input(fd, reflex::Input::file_encoding::latin); // construct ISO-8859-1 input
    yyFlexLexer lexer(input);                                     // construct lexer with input
    while (lexer.yylex() != 0)                                    // scan file until EOF
      continue;
    fclose(fd);                                                   // close the file
  }
}

RE/flex 内置支持 UTF 编码、ISO-8859-1 到 16、MACROMAN、EBCDIC、KOI8 和代码页 437、850、858、1250 到 1258。您还可以定义一个自定义代码页供智能输入类使用，该类将使用指定的代码页条目将 8 位字符自定义转换为 Unicode。

错误处理

扫描器和解析器的输入错误处理至关重要。一个编译器或解释器的好坏取决于其向用户报告错误的详细程度。输入中的语法错误和程序中的语义错误都应该详细报告。为此，Bison 解析器通常在语法错误时调用 `yyerror()` 函数。扫描器也可以使用相同的函数来报告错误的输入。

RE/flex 提供了几种方法来协助错误报告。首先也是最重要的是 `matcher().line()` 及其宽字符串变体 `matcher().wline()`。它们以（宽）字符串形式返回包含（错误）匹配的输入行。这使得在基于行的扫描器（如解释器）的输入中报告错误变得容易。

void yyerror(Lexer *lexer, const char *msg)
{
  std::string line = lexer->matcher().line();
  std::cerr << "Error: " << msg << " at " <<
    lexer->lineno() << "," << lexer->columno() << "\n" <<
    line << ":\n";
  for (size_t i = lexer->columno(); i > 0; --i)
    std::cerr << " ";
  std::cerr << "\\__ here" << std::endl;
}

这里，我们想将 `Lexer` 对象传递给 `yyerror()`。为此，我们使用 `%option bison-bridge`，它会生成将 `Lexer` 对象传递给词法分析器函数的代码，这在 Flex 和 RE/flex 中都有说明。bison-bridge 解析器会调用 `yyerror()`，我们可以在词法分析器规范中做同样的事情（RE/flex 中包含了一个使用此方法的 `calc.l` 和 `calc.y` 计算器示例）。

.  yyerror(this, "mystery character");

如果输入不是基于行的，解析器可能会报告一个它在检测到错误后很久就已经跳过的行的语法错误。这意味着必须从文件中检索并报告违规输入。假设我们有一个启用了 bison-locations 的 bison-complete 解析器 `yy::parser`，以下用户定义的 `error()` 方法会报告错误，无论位置如何以及输入文件中要报告多少行违规行。

void yy::parser::error(const location& loc, const std::string& msg)
{
  std::cerr << loc << ": " << msg << std::endl;
  if (loc.begin.line == loc.end.line && loc.begin.line == lexer.lineno())
  {
    std::cerr << lexer.matcher().line() << std::endl;
    for (size_t i = 0; i < loc.begin.column; ++i)
      std::cerr << " ";
    for (size_t i = loc.begin.column; i <= loc.end.column; ++i)
      std::cerr << "~";
    std::cerr << std::endl;
  }
  else
  {
    FILE *file = lexer.in().file(); // the current file being scanned
    if (file != NULL)
    {
      yy::scanner::Matcher *m = lexer.new_matcher(file); // new matcher
      lexer.push_matcher(m);      // save the current matcher
      off_t pos = ftell(file);    // save current position in the file
      fseek(file, 0, SEEK_SET);   // go to the start of the file
      for (size_t i = 1; i < loc.begin.line; ++i)
        m->skip('\n');            // skip to the next line
      for (size_t i = loc.begin.line; i <= loc.end.line; ++i)
      {
        std::cerr << m->line() << std::endl; // display offending line
        m->skip('\n');            // next line
      }
      fseek(file, pos, SEEK_SET); // restore position in the file to continue scanning
      lexer.pop_matcher();        // restore matcher
    }
  }
}

此示例使用了 `matcher().line()` 以及 else 分支中的临时匹配器，以通过 `matcher().skip('\n')` 在输入文件中寻找要前进到的位置，这需要可查找文件作为输入。有关更多详细信息，特别是使此功能起作用的各种 RE/flex 和 Bison 选项，请参阅 RE/flex 用户指南。

性能调优

有几个 reflex 命令行选项可用于调试词法分析器并分析其在给定输入文本下的性能。命令行选项 `-d` 生成一个打印匹配文本的扫描器。选项 `-p` 生成一个打印性能报告的扫描器。该报告显示了为词法分析器规范中定义的每个规则获得的性能统计数据。这些统计数据是在扫描器在给定输入上运行时收集的。

通过 `-p` 选项，您可以专注于计算开销较大的模式和规则，从而微调扫描器的性能。这最好通过一个示例来说明。RE/flex 下载包的 `examples` 目录中的 JSON 解析器 *json.l* 使用 reflex 选项 `-p` 构建，然后针对某些 JSON 输入运行以分析其性能。

reflex 0.9.22 json.l performance report:
  INITIAL rules matched:
    rule at line 51 accepted 58 times matching 255 bytes total in 0.009 ms
    rule at line 52 accepted 58 times matching 58 bytes total in 0.824 ms
    rule at line 53 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 54 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 55 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 56 accepted 5 times matching 23 bytes total in 0.007 ms
    rule at line 57 accepted 38 times matching 38 bytes total in 0.006 ms
    rule at line 72 accepted 0 times matching 0 bytes total in 0 ms
    default rule accepted 0 times
  STRING rules matched:
    rule at line 60 accepted 38 times matching 38 bytes total in 0.021 ms
    rule at line 61 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 62 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 63 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 64 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 65 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 66 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 67 accepted 0 times matching 0 bytes total in 0 ms
    rule at line 68 accepted 314 times matching 314 bytes total in 0.04 ms
    rule at line 69 accepted 8 times matching 25 bytes total in 0.006 ms
    rule at line 72 accepted 0 times matching 0 bytes total in 0 ms
    default rule accepted 0 times
  WARNING: execution times are relative:
    1) includes caller's execution time between matches when yylex() returns
    2) perf-report instrumentation adds overhead and increases execution times

显示的时间包括模式匹配的时间和规则执行代码的时间。如果规则返回给调用者，则调用者花费的时间也包含在此计时中。在本例中，我们有两个起始条件状态，即 `INITIAL` 和 `STRING`。第 52 行的规则是：

[][}{,:]        { return yytext[0]; }

这会向解析器返回一个 `[` 或 `]` 方括号，一个 `{` 或 `}` 大括号，一个逗号或一个冒号。由于模式和规则非常简单，我们不期望它们对该规则所花费的 0.824 毫秒时间贡献太多。扫描器返回时执行的解析器代码可能开销很大。根据返回的字符，解析器会构造一个 JSON 数组（方括号）或一个 JSON 对象（大括号），并在每次匹配到逗号时用一个项填充数组和对象。但哪个最昂贵呢？为了单独获取这些事件的计时，我们可以将规则拆分为三个类似的规则。

[][]        { return yytext[0]; }
[}{]        { return yytext[0]; }
[,:]        { return yytext[0]; }

然后，我们使用 reflex 选项 `-p`，重新编译扫描器 *lex.yy.cpp*，并重新运行我们的实验以查看这些更改。

    rule at line 52 accepted 2 times matching 2 bytes total in 0.001 ms
    rule at line 53 accepted 14 times matching 14 bytes total in 0.798 ms
    rule at line 54 accepted 42 times matching 42 bytes total in 0.011 ms

因此，事实证明，当输入中遇到 `{` 和 `}` 时，解析器构建 JSON 对象是我们的应用程序中相对而言最昂贵的部分。如果我们想提高 JSON 解析器的整体速度，我们应该将优化工作重点放在那里。

本文提供此示例中使用的 JSON 词法分析器和解析器源代码供下载。

使用 Readline 进行交互式输入

Shell、解释器和其他交互式命令行工具允许用户输入由应用程序解释和执行的命令。GNU readline 库通过提供历史机制和基于行的编辑极大地增强了交互体验。相比之下，通过读取标准输入进行的简单交互式输入会给用户带来笨拙的体验。

将 readline 与 RE/flex 结合使用是说明我们如何利用类 Flex 的 `wrap()` 函数的绝佳例子。当达到 EOF 时，`wrap()` 函数被调用，以允许分配新的输入源以继续扫描。在这个例子中，`readline()` 返回一行输入，我们将其作为 `string` 进行扫描。当扫描器到达此 `string` 的末尾时，它会触发 `wrap()` 函数，该函数被设置为返回 `readline()` 返回的下一行，依此类推。

我们在此处给出的词法分析器规范首先在 `%top` 块中包含所需的 C 头文件，然后将词法分析器类 `wrap()` 函数定义在 `%class` 块中，并将词法分析器类构造定义在 `%init` 块中。

%top{
  #include <stdlib.h>
  #include <stdio.h>
  #include <readline/readline.h>
  #include <readline/history.h>
}

%class{
  const char *prompt;
  // we use wrap() to read the next line
  virtual bool wrap() {
    if (line)
    {
      free((void*)line);
      line = readline(prompt);
      if (line != NULL)
      {
        if (*line)
          add_history(line);
        linen.assign(line).push_back('\n');
        in(linen);
      }
    }
    // wrap() == true means OK: wrapped after EOF
    // be careful when using Flex --flex: yywrap() == 0 means OK !!
    return line == NULL ? false : true;
  }
  // the line returned by readline() without \n
  char *line;
  // the line with \n appended
  std::string linen;
}

%init{
  prompt = NULL; // we can set a prompt here
  line = readline(prompt);
  if (line != NULL)
  {
    if (*line)
      add_history(line);
    linen.assign(line).push_back('\n');
  }
  in(linen);
}

本文提供了与此示例类似但使用 Flex 动作的基于 readline 的词法分析器示例供下载。

结论

RE/flex 不仅仅是 Flex 的 C++ 版本。它增加了 Flex 缺乏的许多有用的新功能，包括关键的 Unicode 模式匹配、改进的错误报告功能、智能输入处理以接受 UTF-8/16/32（带或不带 UTF BOM“字节顺序标记”）、ASCII、ISO-8859-1 到 16、EBCDIC、各种代码页编码的输入、POSIX 模式下的惰性重复，以及以高效 C++ 源代码形式生成直接编码的 DFA。

RE/flex 还为四种常见的模式匹配方法提供统一的正则表达式 API：`find`、`scan`（连续查找）、`split` 和 `matches`。这个统一的 API 不仅仅是 PCRE2、Boost.Regex、RE/flex regex 和 C++11 std::regex 的包装器。这个 API 提供了一个统一的接口来选择合适的正则表达式模式匹配器类来执行 `find`、`scan`、`split` 和 `matches` 操作。这个易于使用的 API 可以用于任何 C++ 应用程序，以匹配来自字符串、流和文件描述符的输入，这些文件以 UTF 或其他格式编码。这个 API 被有效地用于 ugrep，一个用 C++11 编写的超快速交互式 grep 工具。

延伸阅读

要了解更多关于 RE/flex 的信息，我建议您阅读《使用 RE/flex 构建快速词法分析器》和《RE/flex 用户指南》。

下载和许可

RE/flex 可从 SourceForge 和 GitHub 下载。RE/flex 是根据 BSD-3 许可授权的免费开源软件。

历史

  • 2017年4月25日：本文首个版本
  • 2017年4月30日：进行了一些外观更新
  • 2017年5月16日：少量更新以澄清
  • 2017年6月25日：添加了下载图标并解释了代码页的使用
  • 2019年7月31日：扩充了缩进/不缩进/反缩进部分，增加了 `\k` 锚点
  • 2019年8月8日：更新了性能比较以包含 RE/flex 1.3.5 版本
  • 2020年2月5日：新增错误处理章节；更新了性能比较
  • 2020年4月30日：添加 PCRE2 作为正则表达式引擎选项；更新了示例和性能比较
© . All rights reserved.