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

Reggie: 一个非回溯流式正则表达式代码生成器

honey the codewitch
starIconstarIconstarIconstarIconstarIcon

5.00/5 (17投票s)

2021年10月24日

MIT

16分钟阅读

viewsIcon

28914

downloadIcon

183

嵌入快速流式 C# 代码，根据输入的正则表达式匹配文本

Reggie

引言

更新 3： 服务版本 - FastFA 解析中的一个错误修复，在某些情况下，范围（非[^]）未正确解析。清理了部分源代码树的冗余代码。

更新 2：几乎是重写。现在同时支持 T-SQL 和 C#。整个应用程序都是模板化的，包括使用界面。现在有主模板来决定状态机的整体结构，然后为每个支持的目标提供代码组件来渲染各个部分。这样，它就能通过测试，这花了几天时间。

更新：对文章和代码库进行了大规模更新。Reggie 增加了许多新功能，包括“块结束符”，允许您进行涉及起始和结束表达式的复杂匹配，生成带可选行/列跟踪的标记生成器，改进的表格式，以及更易于维护的代码生成。

我喜欢 .NET 的正则表达式引擎，直到我不再喜欢它。当您已将要搜索的内容加载到内存中时，它效果非常好。它在进行复杂的后向引用时也效果不错，但会牺牲原始吞吐量。

它有一些缺点，许多时候您可能不会在意。但有些时候您会，尤其是在搜索非常大的内容或来自远程端点的内容时，或者当您想对文本进行标记化而 .NET 引擎却没有提供此功能时。

另一件事是，.NET 的引擎生成的結果無法輕鬆地與 LINQ 表達式一起使用。由於此工具通過枚舉器公開搜索結果，因此它可以。

在这些场景中，Reggie 可以为您提供帮助，它是一个快速、无依赖、纯 C# 的解决方案，该方案基于您预先提供的一些正则表达式为您生成。将这些正则表达式放在一个规范文件中，然后运行此工具，就可以得到易于调用的方法，您可以使用这些方法根据文件中的表达式来验证、搜索或标记化文本。

注意：解决方案文件夹中有用于支持生成过程的二进制文件。它们是安全的 .NET 程序集，均可在 CodeProject 上作为单独的文章找到。

概念化这个混乱的局面

DFA 正则表达式，也称为非回溯正则表达式，是您熟悉的正则表达式的一个丰富子集。我之所以说丰富，是因为大多数时候，您可以使用非回溯引擎熟悉的正则表达式语法，但存在重要的限制。因此，您无法用它进行原子零宽度断言。好消息是，大多数时候，这种东西并不重要，除非您试图匹配 /* */ 对或其他类似的东西，而 Reggie 为这种情况提供了一个特殊的工具。

主要来说，您可以使用正则表达式做三件事：

  1. 您可以验证输入字符串是否与表达式匹配。
  2. 您可以搜索匹配表达式的文本出现。
  3. 您可以对文本进行标记化以便进行解析或最小化。

.NET 引擎允许您执行前两项，但不能执行第三项，并且其运行速度比 Reggie 的代码慢，灵活性也较低，尽管 .NET 的引擎支持后向引用而 Reggie 不支持。这是出于性能原因，同时也为了区分 Reggie 与 .NET 的产品。

使用这个烂摊子

使用此工具，您可以创建一系列命名的 DFA 正则表达式，并将它们放入一个 .rl 文件中。这些是 Rolex Lexer 规范文件，但它们在这里的工作方式相同。主要区别在于 blockEnd 属性可以是单引号括起来的正则表达式，也可以是双引号括起来的字面量。Rolex 只支持字面量作为块结束符（我们稍后会介绍）。否则，这些文件遵循 Rolex 格式。考虑以下 .rl 文件 Example.rl：

String='"([^"]|\\.)*"'
Keyword<ignoreCase>='as|base|case'
Whitespace<hidden>='[\t\r\n\v\f ]+'
Identifier='[_[:IsLetter:]][_[:IsLetterOrDigit:]]*'
CommentBlock<hidden,blockEnd="*/">="/*"

这是一个基于行的语法，其中每行包含 name='regex' 或 name<attributes...>='regex'，其中属性本身是键值对。如果未指定值，则解析为布尔值 true。正则表达式使用 \ 进行转义，并且 ' 必须转义。

Reggie 中有三种代码生成“模式”：一种用于词法分析器/标记生成器，一种用于匹配器，一种用于检查器。

此外，还有两种主要类型的状态机。这样做的原因是，对于匹配和标记化使用同一个 .rl 文件是没有意义的，因为它们在每种情况下的使用方式非常不同。对于标记生成器，所有表达式都组合在一起；对于匹配器，每个表达式单独使用。如果您确实想这样做，可以为同一个输入文件和同一个类生成两者（通过每次运行 Reggie 两次并使用相同的类名 (/class)），但指定词法分析器 (/lexer) 选项在第二次运行时。

检查器代码

当使用 /checker 选项时会生成检查器代码。

每个命名表达式都会生成一个公共方法：

  • bool IsXXXX(IEnumerable<char> text) - 指示传入的流是否与正则表达式匹配。整个流必须与表达式匹配。可接受字符串和字符数组。

使用代码非常简单：

Console.WriteLine(Example.IsCommentBlock("/* baz */")); // prints True

匹配器代码

匹配器代码通过 /matcher 指定。

每个命名表达式将生成以下四种公共方法之一，其中 XXXX 是表达式的名称/符号，具体取决于是否指定了 /textreader 和/或 /lines：

  • IEnumerable<(long AbsolutePosition, int AbsoluteLength, long Position, int Length, string Value)> MatchXXXX(IEnumerable<char> text, long position = 0) - 搜索文本流，查找匹配项，并在每次迭代时返回它们。可接受字符串和字符数组。
  • IEnumerable<(long AbsolutePosition, int AbsoluteLength, long Position, int Length, string Value)> MatchXXXX(TextReader text, long position = 0) - 搜索文本流，查找匹配项，并在每次迭代时返回它们。可接受 TextReader 派生类。
  • IEnumerable<(long AbsolutePosition, int AbsoluteLength, long Position, int Length, string Value, int Line, int Column)> MatchXXXX(IEnumerable<char> text, long position = 0, int line = 1, int column = 1, int tabWidth = 4) - 搜索文本流，查找匹配项，并在每次迭代时返回它们。可接受字符串和字符数组。
  • IEnumerable<(long AbsolutePosition, int AbsoluteLength, long Position, int Length, string Value, int Line, int Column)> MatchXXXX(TextReader text, long position = 0, int line = 1, int column = 1, int tabWidth = 4) - 搜索文本流，查找匹配项，并在每次迭代时返回它们。可接受 TextReader 派生类。

一旦生成的输出包含在您的项目中，使用这些方法就很简单：

Console.WriteLine(Example.IsString("\"Hello\\tWorld!\"")); // prints True
Console.WriteLine(Example.IsWhitespace("foo bar")); // prints False

匹配过程同样简单，无论是通过 TextReader 还是其他源：

foreach(var match in Example.MatchWhitespace("The quick brown fox "+
    "jumped over the lazy dog"))
    Console.WriteLine("{0}/{1}: {2}", match.Position, match.Length, match.Value);

MatchXXXX() 函数几乎可以接受任何文本源，而 IsXXXX() 函数可以接受 IEnumerable<char> 实例，如字符串和字符数组。

词法分析器/标记生成器代码

当指定 /lexer 选项时，Reggie 将生成用于词法分析/标记化文本的代码，而不是匹配代码。词法分析将文本报告为一系列标记，这些标记包含位置、文本以及一个 id，该 id 指示匹配该文本的表达式。该 id 是 .rl 文件中符号的 id，该 id 是隐式创建的，或者是通过 id 属性显式指定的，或者是 ERROR/-1（当光标下的文本未匹配任何内容时）。如果您指定了 hidden 属性，则该特定符号不会由词法分析器报告。这对于跳过空格和注释等非常有用。

构建词法分析器/标记生成器时，会生成一个方法和几个常量字段。每个整数常量字段的名称与其在 .rl 文件中表示的符号相同，值将是 id 属性值，或者会自动为您编号。这些对应于 Token 类的 Id 字段。此外，还有一个值为 -1 的 ERROR 常量，表示一个错误标记。

生成两个 Tokenize() 方法，一个用于 IEnumerable<char>，一个用于 TextReader。您可以像在匹配器代码中使用 MatchXXXX() 方法一样，通过 foreach 遍历标记，只是这里返回的是 Token 实例：

根据 /textreader、/lines 和/或 /token 的存在，生成以下八种方法之一：

  • IEnumerable<(long AbsolutePosition, int AbsoluteLength, long Position, int Length, int SymbolId, string Value, int Line, int Column)> Tokenize(IEnumerable<char> text, long position = 0, int line = 1, int column = 1, int tabWidth = 4)
  • IEnumerable<(long AbsolutePosition, int AbsoluteLength, long Position, int Length, int SymbolId, string Value, int Line, int Column)> Tokenize(TextReader text, long position = 0, int line = 1, int column = 1, int tabWidth = 4)
  • IEnumerable<(long AbsolutePosition, int AbsoluteLength, long Position, int Length, int SymbolId, string Value)> Tokenize(IEnumerable<char> text, long position = 0)
  • IEnumerable<(long AbsolutePosition, int AbsoluteLength, long Position, int Length, int SymbolId, string Value)> Tokenize(TextReader text, long position = 0)
  • IEnumerable<{Token}> Tokenize(IEnumerable<char> text, long position = 0, int line = 1, int column = 1, int tabWidth = 4)
  • IEnumerable<{Token}> Tokenize(TextReader text, long position = 0, int line = 1, int column = 1, int tabWidth = 4)
  • IEnumerable<{Token}> Tokenize(IEnumerable<char> text, long position = 0)
  • IEnumerable<{Token}> Tokenize(TextReader text, long position = 0)

标记化与匹配一样简单，无论是通过 TextReader 还是其他源：

foreach(var token in Example.Tokenize("The quick brown fox "+
    "jumped over the lazy dog"))
    Console.WriteLine("{0}@{1}: {2}", token.Id, token.Position, token.Value);

如上所述，如果您指定 /lines，您的标记生成器将生成用于跟踪行和列位置的代码，但代价是代码量更大，性能略有下降（在大多数情况下可以忽略不计）。当指定 /lines 时，{Token} 类应包含 Line 和 Column 字段，并且 Tokenize() 可以接受可选的起始行和列以及可选的制表符宽度。

运行工具

从命令行或作为构建步骤执行实际的代码生成非常容易。我以后可能会添加 Visual Studio 集成，但说实话，我从不使用我制作的工具的这项功能。构建步骤更简洁。

Usage: Reggie.exe <input> [/output <output>] [/class <class>]
   [/namespace <namespace>] [/database <database>] 
   [/token <token>] [/textreader] [/tables] [/lexer] 
   [/target <target>] [/lines] [/ignorecase] [/dot] [/jpg] 
   [/ifstale]

Reggie 0.9.6.0 - A regular expression code generator

   <input>      The input specification file
   <output>     The output source file - defaults to STDOUT
   <class>      The name of the main class to generate
       - default derived from <output>
   <namespace>  The name of the namespace to use
       - defaults to nothing
   <database>   The name of the database to use (w/ SQL)
       - defaults to nothing
   <token>      The fully qualified name of an external token
        - defaults to a tuple
   <textreader> Generate TextReader instead of IEnumerable<char>
                - C#/cs target only
   <tables>     Generate DFA table code - defaults to compiled
   <lexer>      Generate a lexer instead of matcher functions
   <lines>      Generate line counting code
        - defaults to non-line counted, only used with /lexer
   <ignorecase> Generate case insensitive matches by default
        - defaults to case sensitive
   <target>     The output target to generate for
       - default derived from <output> or "cs"
       Supported targets: sql, rgg, cs
   <dot>        Generate .dot files for the state machine(s)
   <jpg>        Generate .jpg files for the state machine(s)
       - requires GraphViz
   <ifstale>    Skip unless <output> is newer than <input>

生成 Example.rl 到文件，只需运行以下命令行即可：

reggie Example.rl /output Example.cs

一旦 Example.cs 被包含在您的项目中，您就可以通过 Example 类访问前面提到的方法。

/tables 生成使用数组来保存状态机的 DFA 匹配代码，而不是使用 goto 表进行硬编码。其优点是生成的代码更紧凑，更重要的是，对于像复杂词法分析器/标记生成器这样的大型机器，基于表的方法可以比编译方法表现更好。

/ignorecase 使您的正则表达式默认情况下不区分大小写。您可以通过使用 ignoreCase 属性逐个/逐条规则地覆盖该设置。

/class 和 /codenamespace 指示包含类的命名空间和名称。默认情况下，这取决于输出文件名，或者在未指定 /output 时取决于输入文件名。

最后，/ifstale 指示 Reggie 仅当 output 比 input 旧时才运行生成过程。这在将 Reggie 作为预构建步骤运行时非常有用，特别是当词法分析器或匹配器复杂且生成耗时时。通常，DFA 正则表达式很难转换为代码，因此它们的编译时间比 .NET 的长，但它们的性能明显更好，所以这是一个权衡。此选项有助于缓解一些耗时问题。

目标

Reggie 可以生成到多个输出目标/类型。目前可用的三种是 C#、SQL 和 RGG（Reggie 二进制格式）。当指定 /output 时，这些是从输出文件的扩展名派生的，除非指定了 /target。如果未指定输出文件或目标，则目标默认为 C#。

  • CS - 生成 C# 代码，如上所述。
  • SQL - 生成 T-SQL 代码，其中包含存储过程，这些存储过程提供了与上述几乎相同的 API，只是使用结果集来返回标记和匹配项。
  • Rgg - 生成一个 Reggie 二进制文件，其中包含所有预先计算的状态机信息。然后，该文件可以作为输入文件而不是 .rl 文件使用。这样做可以避免重新计算状态表，对于复杂的机器来说，这可以节省大量时间，尤其是在从单个 .rl 文件渲染输出时。只需在您的预构建步骤中添加另一个 reggie.exe 调用，然后再执行其他所有调用，即可生成一个 .rgg 文件。然后，将此 .rgg 文件用作所有后续 reggie.exe 调用的输入。

如果您安装了 GraphViz，您可以渲染状态图的 jpg 图像，这对于调试您的表达式很有用。您可以使用 /jpg 开关进行渲染。即使没有 GraphViz，您也可以使用 /dot 渲染状态图的 .dot 文件。

高级 Reggie

网络流

匹配网络流比匹配本地源几乎一样容易，也比从文件读取复杂不了多少。请记住，由于它是流式的，如果您提前中止，您不必下载所有内容 - 这正是它在 .NET 产品之上真正的闪光点，.NET 产品需要您在第一次匹配之前获取整个页面。

这是抓取 google.com 上带引号字符串的一些代码：

var wr = WebRequest.Create("https://www.google.com");
using (var wrs = wr.GetResponse())
    foreach(var match in Example.MatchString(new StreamReader(wrs.GetResponseStream())))
        Console.WriteLine("{0}/{1}: {2}", match.Key, match.Value.Length, match.Value);    
return 0;

当我在这台机器上运行它时（已截断），会产生以下输出：

31/2: ""
43/27: "http://schema.org/WebPage"
76/4: "en"
101/161: "Search the world's information, including webpages, images, videos and more. 
Google has many special features to help you find exactly what you're looking for."
268/13: "description"
296/7: "noodp"
309/8: "robots"
332/26: "text/html; charset=UTF-8"
370/14: "Content-Type"
399/62: "/images/branding/googleg/1x/googleg_standard_color_128dp.png"
471/7: "image"
514/26: "7iBgPwxaZu1vJQzy3lozqg=="
2320/5: "eid"
2426/6: "leid"
2490/2: ""
2510/6: "&ei="
2522/6: "&ei="
2548/7: "&lei="
2572/7: "&lei="
2586/2: ""
2617/9: "&cshid="
2629/5: "slh"
2643/9: "&cshid="
2668/3: "/"
2676/9: "gen_204"
2687/13: "?atyp=i&ct="

为了在接近真实的应用中完全理解此功能，我创建了 ImgScraper 演示，该程序可以从网站下载图片。它的工作方式与上述抓取类似，使用一个匹配图像文件的正则表达式。

使用块结束符

块结束符是 Reggie 的一项独特功能，它允许您绕过 DFA 正则表达式的一些限制。它们允许您指定一个用于终止初始表达式的表达式。当初始表达式匹配后，匹配器或标记生成器会继续进行，捕获字符直到达到块结束符。然后返回整个匹配项。这对于块注释等功能非常有用。

要为规则启用块结束符，您可以指定一个 blockEnd 属性。其值必须是单引号或双引号括起来的，分别表示正则表达式或字面字符串。以下示例匹配 C 风格的注释：

CommentBlock<blockEnd="*/">= "*/"
CommentLine<blockEnd='\n'>= "//"

这将导致 Reggie 匹配 // ... <newline> 和 /* ... */ 序列。

性能

ReggiePerf 比较了编译、表驱动和 .NET 正则表达式的性能。这是在我机器上对一个简单标记生成器的输出：

Pass 1

Table - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 157ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 94ms
.NET Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 337ms

Pass 2

Table - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 161ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 99ms
.NET Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 321ms

Pass 3

Table - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 150ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 93ms
.NET Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 315ms

Pass 1

Table - Tokenizing test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 1126ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 942ms
Table - Tokenizing test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 1066ms
Compiled - Matching whitespace in test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 969ms

Pass 2

Table - Tokenizing test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 1106ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 937ms
Table - Tokenizing test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 1071ms
Compiled - Matching whitespace in test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 963ms

Pass 3

Table - Tokenizing test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 1108ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 962ms
Table - Tokenizing test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 1091ms
Compiled - Matching whitespace in test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 960ms

这是对一个明显更复杂的标记生成器的性能结果。您会注意到，在这种情况下，标记生成器的表版本比编译版本性能更好：

Pass 1

Table - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 168ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 101ms
.NET Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 332ms

Pass 2

Table - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 161ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 90ms
.NET Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 316ms

Pass 3

Table - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 154ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 91ms
.NET Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% matched all 100 times in 321ms

Pass 1

Table - Tokenizing test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 1897ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 3821ms
Table - Tokenizing test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 1827ms
Compiled - Matching whitespace in test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 3853ms

Pass 2

Table - Tokenizing test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 1825ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 2454ms
Table - Tokenizing test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 1823ms
Compiled - Matching whitespace in test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 2522ms

Pass 3

Table - Tokenizing test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 1820ms
Compiled - Matching whitespace in test.txt
[■■■■■■■■■■] 100% tokenized all 100 times in 2488ms
Table - Tokenizing test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 1822ms
Compiled - Matching whitespace in test.txt with line counting
[■■■■■■■■■■] 100% tokenized all 100 times in 2524ms

这些都是发布模式，在这种模式下，生成代码的性能明显更好。您可以看到，这个 DFA 正则表达式引擎在性能上远远超过了 Microsoft 的正则表达式引擎，在某些情况下快 2 到 3 倍。由于 Microsoft 的引擎无法在不进行大量黑客式修改并以奇怪的方式使用它们的情况下进行标记化，因此无法与 Microsoft 的引擎进行比较，而且这样做的性能损失使得测试不公平。

工作原理

总体结构

Reggie 使用我的 FastFA 正则表达式/有限自动机引擎从正则表达式生成状态机。然后，这些状态机会被查询以生成匹配代码。

匹配代码本身是使用存储在 Export 文件夹下的类 ASP 风格的模板生成的，并使用 csppg 生成。生成的模板发射器类的名称为 Export.XXXX，其中 XXXX 是每个类的名称。这些类接受一个包含参数的字典和一个要写入的 TextWriter，以生成代码。

所有模板都继承自 TemplateCore，它提供了处理状态机生成的辅助函数。

状态机结构

状态机可以表示为由连接的 F.FFA 实例组成的有向图，每个 F.FFA 的 Transitions 列表将它们链接在一起。该列表包含一个字符范围（以 UTF32 代码点表示，状态机仅使用 UTF32），以及一个目标状态，当范围匹配输入字符时跳转到该状态。

在生成过程中，状态机从 .rl 文件中解析为正则表达式，然后使用分区子集构造方案（我从 Fare 复制而来，Fare 本身是 Java 版本 dk.brics.automaton 的端口）从 NFA 转换为 DFA 并进行压缩。当 .rl 文件特别大或表达式复杂时，这部分是处理时间花费最多的地方。

Fare 版权归 © 2013 Nikos Baxevanis 所有。我使用的相关代码位于 FastFA 项目中，位于 FFA.cs 下，涵盖了 DFA 创建和最小化代码。

大多数时候，DFA 状态机被传递为 int[] 数组。数组是顺序布局的，一个状态紧随下一个状态。每个状态的结构如下：

接受    
转换计数    
  转换目标  
  打包范围计数  
    打包范围最小值
    打包范围最大值

在这里，每个状态都有一个接受符号 id（-1 表示状态不接受），后跟一个转换计数。对于每个转换，都有一个指向状态机的目标索引（从目标状态的索引开始），后跟一个打包范围的计数。对于每个打包范围，都有两个值，表示每个范围的最小值和最大值。

状态机代码

请注意，此代码已过时，但其结构与当前生成的代码相同。在此保留，因为此代码更简单。

这是用于匹配 DFA 表中文本的一些代码，以便您可以看到数组的遍历。在此，entries 代表 DFA 状态机，而 _FetchNextInput(cursor) 只是从枚举器中获取下一个 UTF32 代码点，如果没有更多输入则返回 -1：

var cursor = text.GetEnumerator();
var ch = _FetchNextInput(cursor);
if (ch == -1) return -1!=entries[0];
var state = 0;
var acc = -1;
while (ch != -1)
{
    // state starts with accept symbol
    acc = entries[state++];
    // next is the num of transitions
    var tlen = entries[state++];
    var matched = false;
    for (var i = 0; i < tlen; ++i)
    {
        // each transition starts with the destination index
        var tto = entries[state++];
        // next with a packed range length
        var prlen = entries[state++];
        for (var j = 0; j < prlen; ++j)
        {
            // next each packed range
            var tmin = entries[state++];
            var tmax = entries[state++];
            if (ch >= tmin && ch <= tmax)
            {
                matched = true;
                ch = _FetchNextInput(cursor);
                state = tto;
                i = tlen;
                break;
            }
        }
    }
    if (!matched)
    {
        if (acc != -1)
            break;
        return false;
    }
}
return -1 != acc;

您可以看到遍历它相当直接。生成器代码通常将状态机用作 int[] 数组。

当不使用上面的表时，此代码默认生成修改过的状态机以使用 goto 表进行匹配。这是一个示例，在此情况下匹配简单的空格：

var sb = new System.Text.StringBuilder();
var position = 0L;
var cursor = text.GetEnumerator();
var cursorPos = 0L;
var ch = _FetchNextInput(cursor);
while (ch != -1) {
    sb.Clear();
    position = cursorPos;
// q0
    if((ch >= '\t' && ch <= '\r') || ch == ' ') {
        sb.Append((char)ch);
        ch = _FetchNextInput(cursor);
        ++cursorPos;
        goto q1;
    }
    goto next;
q1:
    if((ch >= '\t' && ch <= '\r') || ch == ' ') {
        sb.Append((char)ch);
        ch = _FetchNextInput(cursor);
        ++cursorPos;
        goto q1;
    }
    if (sb.Length > 0) yield return new 
        System.Collections.Generic.KeyValuePair<long,string>(position, sb.ToString());
next:
    ch = _FetchNextInput(cursor);
    ++cursorPos;
}

这个状态机嵌套在 C# 迭代器中（其本身由 C# 编译器使用状态机实现）。它由两个状态 q0 和 q1 组成，如下图所示：

Whitespace

您可以在 q0 下方的代码中看到第一个转换是如何由 if((ch >= '\t'... 代码片段实现的。

在 q1 下方，有一个类似的片段，代表其转换。q1 有一个双圈，因为它接受输入，这意味着它 yield 返回结果。您会看到 yield 周围的 if ... 条件，它阻止了零长度表达式的匹配。

尽情享用！

历史

  • 2021 年 10 月 24 日 - 初始提交
  • 2021 年 10 月 24 日 - 添加了 /dot 和 /jpg 功能，简化了匹配，并添加了演示项目
  • 2021 年 10 月 24 日 - 使演示更健壮。进行了一般性清理。
  • 2021 年 10 月 25 日 - 进行了性能测试。添加了表生成。进行了小的错误修复。
  • 2021 年 10 月 29 日 - 大规模更新，包括更多功能，如带可选行计数的词法分析器/标记生成器，以及“块结束符”支持，允许表达式继续匹配直到达到结束条件/表达式。
  • 2021 年 11 月 7 日 - 几乎是重写。现在支持多个目标，以及将状态机缓存到 .rgg 文件以提高构建时间性能。
  • 2021 年 11 月 10 日 - 服务版本。FastFA 的错误修复。
© . All rights reserved.