FastFA: 用于代码生成器的 Unicode 启用正则表达式引擎

• 下载源代码 - 103.4 KB
• 从 Github 下载最新版本

引言

我先声明一下。本文内容属于小众兴趣。FastFA 已在 Reggie 和 Rolex 中使用。使用这些工具无需直接了解 FastFA，并且可以生成运行正则表达式的源代码，因此本文对那些想了解它是如何工作的，或者想用它来制作自己的源代码生成器的人更有兴趣。它也有助于更好地理解我提到的这两个项目。

话虽如此，FastFA 的这个版本比前面提到的项目中的版本要新，虽然兼容，但这个版本增加了一些功能。

它到底是什么？

简而言之，FastFA 是一个正则表达式引擎。与大多数正则表达式引擎不同，它不适合运行时使用。它可以在运行时使用，但更有效的方法是使用它生成源代码，然后由该源代码为您运行正则表达式。像 Reggie 这样的项目使用它来计算需要生成的代码。FastFA 本身不生成代码。相反，它会生成可用于协调其他应用程序进行代码生成的数据。

名字是怎么来的？

您可能想知道 FA 是什么，或者为什么它不称为“正则表达式引擎”之类的。事实上，按照构想，它们不一定匹配字符。您有可能可以用它来匹配其他流。匹配正则表达式的能力提供了一种——尽管是最常见的——用途。在这种情况下，FA 代表 有限自动机，它是用于匹配模式的特殊类状态机，通常（但不总是）在文本中。

为什么不直接使用 System.Text.RegularExpressions？

1. 该引擎更具表现力，但效率不高，因为它会回溯，而这个引擎不会。执行时间提高一倍以上的情况并不少见。
2. 该引擎是不透明的，意味着您对内部几乎没有控制，也无法控制实际的代码生成。此引擎是透明的，在所有必要的级别公开必要的信息，以便运行匹配或生成运行匹配的代码。
3. 该引擎不直接支持词法分析/标记化，这是一种使用正则表达式进行复合模式匹配的特殊方法。这个引擎支持。
4. 有时，拥有一个可以调整和拆解的东西就是很棒的。

致谢

FFA.cs 文件中的部分代码源自其他作者创建的代码，并根据 MIT 许可获得许可。

• Nikso Baxevanis 于 2013 年创作的 Fare，本身是从
• Anders Moeller 于 2001-2011 年创作的 dk.brics.automaton 移植而来。

您可以在 FFA.cs 中找到完整的版权声明。

理解这段乱码

哇。我们还有很多内容要讲。我会尽量将它分解。

究竟什么是正则表达式？

正则表达式是一种微型函数式语言（类似于 LISP 或 F#，但更简单），它拥有一系列相对较少的运算符，用于匹配文本中的模式。您无法使用非回溯正则表达式来匹配嵌套或创建层次结构的任何类型的文本。 这里有一个关于正则表达式的教程。正则表达式可以识别的“语言”类别被称为“正则表达式”或乔姆斯基 3 型语言。

这个特定的引擎是 POSIX(ish) 的。它不支持所有功能，但支持您最常使用的功能，除了锚点。我还没有实现锚点，因为它们有问题。

它是如何工作的？

如果您喜欢数学形式，可以阅读此处的内容。

非回溯正则表达式可以转换为可匹配文本的派生状态机。

最终状态机的状态非常简单。这种状态机的转移函数接受一个字符（技术上是 UTF-32 码点），并（如果找到）返回一个新状态并前进输入一个字符。每个状态都可以是接受状态或非接受状态。在某些情况下，状态还可以具有“接受符号 ID”，这是一个与接受状态关联的数值，但大多数时候我们不需要它。在转移函数找不到下一个状态的情况下，如果当前状态是接受状态，则表示匹配。

考虑以下有向图

这是一个匹配 C 标识符的简单状态机。它使用以下正则表达式生成：[A-Z_a-z][0-9A-Z_a-z]*

图中的每个圆圈代表一个状态。状态的名称或句柄，我们可以用它来引用它，显示在中间。图总是从q0开始。在本例中，我们有两个圆圈表示状态集{ q0, q1 }。您会注意到q1是双圆圈。这意味着它是一个接受状态。当处于该状态时，如果没有更多可用的移动，无论是由于到达输入末尾，还是由于没有合适的/匹配的输入，这都是一个匹配。

从状态引出的黑色箭头共同代表该状态的转移函数。基本上，它们指示移动方向。每个黑色箭头上方都有一个正则表达式片段，该片段是一个字符或字符范围，指示哪些输入可以沿着关联的箭头移动。请记住，当我们沿着箭头移动时，我们还将输入光标前进一个字符。

当您没有更多可用移动或输入用完时，检查当前状态是否为双圆圈。如果是双圆圈，则表示接受状态，因此匹配。否则，则不匹配。

以上用于匹配文本。标记器是这些相同的状态机，只是稍有不同。每个双圆圈/接受状态都有一个相关的整数符号 ID，它精确地指示了匹配的内容。每当发生匹配时，都会报告该相关 ID。

但是如何从表达式得到那个图呢？

首先，一个状态的闭包是指从该状态直接或间接通过任何箭头可达的所有状态，包括它本身。状态的闭包代表一个完整状态机。因此，闭包中每个状态的闭包也代表一个状态机，依此类推。这几乎就像俄罗斯套娃，但这是一个有向图，而不是树。在上方的 C 标识符图中，有一个以q0开始的状态机，以及技术上以q1开始的一个，它处理整个匹配的后半部分。

以上很重要，因为它突显了这些状态机的可组合性。您可以构建小机器来运行匹配的一部分，然后创建一个引用这些机器的大机器。如果我们这样做，我们可以将任何正则表达式分解为几个基本构建块，然后像乐高积木一样将它们组合起来，构成完整的机器。

事实上，这种将状态机组合成少量基础机器的方法被称为汤普森构造。这发生在解析过程中，或者通过使用 API 公开的汤普森构造方法来完成。

使用这个烂摊子

主 API

核心类型是 FastFA.dll 中的 F.FFA。它代表状态机中的单个状态。但是，它也通过其接口公开了整个 API。记住我提到了闭包，即通过遵循箭头直接或间接从该状态可达的所有状态的集合。您可以从任何给定状态计算闭包，以获取其整个机器中所有状态的集合。因此，您可以将 FFA 的实例视为单个状态，或者将其视为状态机的根状态，具体取决于您当前的需求。它们的工作方式相同。您对状态执行的许多操作都将该状态视为状态机的根状态。例如，在一个实例上调用 IsMatch() 会使用该实例作为状态机的根来匹配输入字符串。

通常，您将使用 FFA.Parse() 将正则表达式解析到 FFA 实例中，然后您可以分析其 Transitions，或者更典型地，使用 FillInputTransitionRangesGroupedByState() 按目标状态分析其转换范围，这对于代码生成器很有用。您还可以使用 ToDfaTable() 将机器打包为 int[] 数组。如果您想将状态机转换回正则表达式，可以调用 ToString()。如果您想获取其图，请确保已安装 GraphViz 并将其添加到您的路径中，然后使用 RenderToFile() 或 RenderToStream()。

除了解析之外，您还可以直接使用静态汤普森构造方法（如 Literal()、Set()、Repeat()、Concat() 和 Or()）从 UTF32 码点构建状态图。

这里有一个使用它的例子

// our expression
var exp = "foo|(bar)+|baz";
Console.WriteLine(exp);
            
// parse it
var fa = FFA.Parse(exp);
// write it back as an equivalent regular expression
Console.WriteLine(fa);
// run IsMatch
Console.WriteLine("IsMatch(\"foo\") = {0}", fa.IsMatch("foo"));
// run IsMatch (DFA table)
Console.WriteLine("IsMatch(dfa, \"barbar\") = {0}", FFA.IsMatch(fa.ToDfaTable(), "barbar"));
            
// run searches
var srch = "abcde foo fghij barbar klmnop baz";
var lc = LexContext.Create(srch);
Console.WriteLine("Search(\"{0}\")", srch);
var pos = 0L;
// run Search
while (-1 < (pos = fa.Search(lc))) {
    Console.WriteLine("\t{0} @ {1}", lc.GetCapture(), pos);
}
lc = LexContext.Create(srch);
Console.WriteLine("Search(dfa, \"{0}\")", srch);
pos = 0L;
// run Search (DFA table)
while (-1 < (pos = FFA.Search(fa.ToDfaTable(), lc))) {
    Console.WriteLine("\t{0} @ {1}", lc.GetCapture(), pos);
}
// C identifier:
var ident = FFA.Parse("[A-Z_a-z][A-Z_a-z0-9]*");
var opts = new FFA.DotGraphOptions();
// don't need to see accept symbol ids
opts.HideAcceptSymbolIds = true;
// render it to a jpg in the project directory
// this is used in the article!
ident.RenderToFile(@"..\..\..\ident.jpg",opts);

DFA 表布局

当打包为整数数组时，DFA 表的构建方式使其可以高效导航。其存储方式如下：

您有一个状态列表，每个状态由一个接受 ID（-1 表示不接受）、一个转换计数，然后是每个转换组成。

每个转换又以目标状态索引开头。这是指向 dfa 表数组中下一个状态开始位置的绝对索引。它不是状态编号，如 qN。之后是一个打包范围的计数，然后是打包范围本身。

每个打包范围都包含一个最小输入值和一个最大输入值——通常是构成范围的 UTF32 码点，至少在将状态机用于匹配正则表达式时是这样（尽管请记住，您实际上可以用它来匹配文本以外的内容）。

总之，为了说明我的意思，这里是关于使用 LexContext 处理输入并检查其内容是否能被我们的 DFA 状态表匹配的代码：

public static bool IsMatch(int[] dfa, LexContext lc) {
    lc.EnsureStarted();
    int si = 0;
    while (true) {
        // retrieve the accept id
        var acc = dfa[si++];
        if (lc.Current == LexContext.EndOfInput) {
            return acc != -1;
        }
        // get the transitions count
        var trns = dfa[si++];
        var matched = false;
        for (var i = 0; i < trns; ++i) {
            // get the destination state
            var tto = dfa[si++];
            // get the packed range count
            var prlen = dfa[si++];
            for (var j = 0; j < prlen; ++j) {
                // get the min cp
                var min = dfa[si++];
                // get the max cp
                var max = dfa[si++];
                if (min > lc.Current) {
                    // we need to break.
                    // first advance si
                    // past the remaining
                    // packed ranges
                    si += (prlen - (j+1)) * 2;
                    break;
                }
                if (max >= lc.Current) {
                    // the new state
                    si = tto;
                    matched = true;
                    // break out of both loops
                    goto next_state;
                }
            }
        }
    next_state:
        if (!matched) {
            // is the state accepting?
            if (acc != -1) {
                return lc.Current == 
                    LexContext.EndOfInput;
            }
            return false;
        }
        lc.Advance();
        if (lc.Current == LexContext.EndOfInput) {
            // is the current state accepting?
            return dfa[si] != -1;
        }
    }
}

一开始，所有的 dfa[si++] 符号看起来有点吓人，但它所做的并不复杂。它只是从数组中读取下一个值，si 是 dfa 的当前数组索引。我在上面注释了它从 DFA 表中提取相关数据的所有位置。这是读取状态表关键，无论您是为了匹配还是为了生成代码。在许多情况下，您可以使用该数组而不是整个 FastFA 库，从而消除了对依赖性的需求，并提高了整体效率。

Search() 和 IsMatch()

这些方法允许您执行正则表达式的三个主要功能中的两个。具体来说，它们允许您在更大的流中查找匹配的文本，并允许您检查文本是否与状态机表示的表达式匹配。

IsMatch() 应该很明显。Search() 也很简单，只是它可以对同一个流多次调用，直到返回负数。您必须向它提供一个 LC.LexContext，来自 LexContext.dll。您可以调用 LexContext.Create() 并将一些文本提供给该方法来创建一个。

其中，静态 DFA 表方法效率最高，而其他方法主要为了方便，而且坦白说，这使我更容易调试，我也没有理由移除它们。

标记/词法分析在哪里？

它不允许您做的唯一一件事就是标记文本。我决定不提供它，原因并非完全是出于工作量和维护原因，而是因为首先，我已经提供了两个使用 FastFA 的标记生成器，并且 Reggie 发布得相当新，所以我建议使用它。它将为您生成 C# 源代码，该源代码可以根据您提供的正则表达式进行搜索、验证或标记。此外，要进行标记，需要引入更多类型，或至少是元组，并需要额外的支持来支持 Rolex 和 Reggie 的“块结束”功能，这些功能在现实世界中几乎是必需的。最终，您将谈论引入大量的 API 表面积，并且在依赖性方面，它会增加负担。Reggie 通过为您生成源代码来规避其中大部分问题，因此运行时引擎无需在标记领域进行操作，而生成的代码也不需要运行时。一切都很顺利。请注意，虽然我推荐使用 Reggie 来实现这一点，但 FastFA 的这个迭代版本稍新一些，并且具有额外的功能（包括 Search()! 和 Match()!）。Reggie 使用这个引擎（尽管是它的最后一个版本）来施展魔法，所以您不妨直接使用它。Reggie 生成的代码不依赖于 FastFA.dll 或 LexContext.dll。

关注点

我包含的新功能之一是能够在一个 FFA 实例上调用 ToString() 并获取正则表达式。这使用了 DFA 状态移除法，或者至少是我多年来一直没能弄对之后尽力而为的尝试。它已经能够处理我遇到的所有内容，但尚未在实际中使用，所以请谨慎使用。有时，它生成的内容可能不那么美观，但它应该能匹配它接收到的相同内容。这是如何工作的，非常有趣。如果您想查看它，可以深入 FFA.cs 的迷宫中寻找 ToString()。虽然内容很多，请小心。

历史

• 2021 年 12 月 25 日 - 首次提交