FA：Unicode 自动机和正则表达式引擎

• 下载源代码 - 1.1 MB

引言

这个代码库是我新的支持 Unicode 的有限自动机和正则表达式引擎。它填补了微软正则表达式产品中的一个空白，微软的产品只处理匹配而不是词法分析（我将解释两者的区别），依赖于一个效率较低但表达能力更强的正则表达式引擎，并且不支持流式处理。

这个引擎主要设计用于词法分析而不是匹配，并且它被设计成高效和支持流式处理。换句话说，它填补了微软在 .NET 中提供的产品中的不足。

必备组件

本文档假设读者对有限自动机和正则表达式有一定的了解。如果您需要一些背景知识，可以参考我的文章《如何用 C# 构建一个正则表达式引擎》。

强烈建议您安装 GraphViz 并将其添加到您的 PATH 环境变量中。这将允许您调用 RenderToStream() 和 RenderToFile() 方法来生成状态机图的图像，这对于调试非常有帮助。

我使用 deslang 和 csbrick 作为预构建步骤来构建 Rolex，这是一个包含的词法分析器生成器。因此，我已经将二进制文件包含在解决方案文件夹中。它们是无害的，并且对于项目构建是必需的。每个文件的源代码可以在上面的链接中找到。您可以随时删除它们，但您需要从 Rolex 中删除预构建步骤才能再次成功构建。

概念化这个混乱的局面

在正则表达式匹配和/或编译的任何阶段，有限自动机几乎总是被使用，无论实现如何。这部分归因于正则表达式和有限自动机的双重性质。一种可以精确地描述另一种，反之亦然。这使得有限自动机在图形化、分析或解释正则表达式方面非常有用，从其内部细节到外部，反过来又使正则表达式在描述有限自动机方面非常有用。它们是一对天生的组合，就像花生酱和果酱一样。因此，这个库包含了两者。

支持 Unicode 的主要难点之一是，输入转换不再适合基于单个字符值。这是因为 Unicode 范围有时非常大——21 位，或基数 0x110000——我们必须不惜一切代价避免将它们扩展为单个字符，否则处理起来会非常耗时。特别是 DFA 子集/幂集构造，它也必须处理这些范围，这更具挑战性。最后，我借鉴了 Fare 库中的一种技术，这为我节省了 50 美元（我原本需要买一本相关书籍）。很高兴找到它。

这个库是我之前提供的库的简化和重写版本，专门为 Unicode 输入设计。因此，内部所有的输入值都保留为 UTF-32，存储为 int 类型。

FA 类是该库的关键，负责处理从解析正则表达式到词法分析的所有操作。每个 FA 对象代表有限状态机中的一个单一状态。它们通过 InputTransitions 和 EpsilonTransitions 连接。需要始终注意的两点是机器的根状态以及通过计算闭包获得的机器的范围。一个状态的闭包简单地是所有可从该状态直接或间接到达的状态的集合，包括它本身。因此，x 的闭包代表了 FA x 的整个机器。敏锐的读者可能会注意到，这意味着机器可以嵌套在机器内部，这是正确的。没有一个 overarching machine 的概念，只有一个根状态，它可以确定其余的状态。如果进行图形化，根状态始终是“q0”。没有父节点，所以我们只能沿着图单向移动。图可以包含循环，因此可能是无限递归的。因此，在遍历图时，必须小心不要重复访问已见过的节点。这由 FillClosure() 和 FillEpsilonClosure() 方法处理。您实际上不必关心这些。

该库处理词法分析，而不是匹配——至少不是直接处理。词法分析是按词法单元或标记分解输入的过程，每个词法单元或标记都带有一个关联的符号。这通常会传递给解析器。常规的正则表达式匹配无法做到这一点。词法分析基本上是匹配一个复合正则表达式，其中每个子表达式都有一个特殊的标记——一个附加到它的“符号”。无法将符号附加到正则表达式匹配，这样做也没有意义。

您通常会想要构建一个词法分析器，所以，产生一个词法分析器的步骤如下：

1. 构建一个 FA 对象数组，通常使用 Parse() 从正则表达式解析而来。确保为每个您想区分的表达式设置唯一的接受符号值。
2. 调用 ToLexer() 并传入该数组，以获得一个可用于词法分析的 FSM。
   现在您有了一个可用的 NFA 词法分析器，但您可能希望将其转换为更有效率的东西。
3. 构建一个 int 数组来表示您的符号表。每个条目是该序数位置上 FA 的 ID。这是可选的，但推荐这样做，否则您将不知道您的 ID 是什么，因为它们将按照状态顺序自动生成。
4. 调用 ToDfaStateTable() 并传入您创建的符号表，以获得一个高效的 DFA 表，您可以使用它来进行词法分析。一旦您有了它，就可以调用 Lex() 方法来对您的输入进行词法分析，或者创建 Tokenizer 来使用 FA 进行词法分析。为了获得更高效的词法分析器，请使用 Rolex 工具来生成一个。

一旦您有了它，您可以通过调用其中一个 Lex() 方法来进行词法分析，或者创建一个 Tokenizer 来进行词法分析。Tokenizer，就像非静态 Lex() 方法一样，可以接受一个 FA，该 FA 可以是 DFA 或 NFA，但是接受 DFA 状态表的静态 Lex() 方法效率最高。

我们开始进入代码部分了，让我们进入下一节。

编写这个混乱的程序

首先要注意的是，我扩展了转换以接受范围。

partial class FA 
{
    public readonly Dictionary<KeyValuePair<int,int>,FA> InputTransitions = 
                                          new Dictionary<KeyValuePair<int,int>,FA>();
    public readonly HashSet<FA> EpsilonTransitions = new HashSet<FA>();
    public int AcceptSymbol = -1;
    public bool IsAccepting = false;
...

如您所见，我们只是使用了简单的字段。KeyValuePair<int,int> 是一个由两个 UTF-32 Unicode 值组成的范围，表示范围中的第一个和最后一个字符。每个都像往常一样映射到它的下一个状态。其余的 FA 与非 Unicode 版本保持不变。

除此之外，如前所述，FA 类包含处理 FSM 各方面的方法，包括从正则表达式解析。同样，每个 FA 代表自动机中的一个单一状态。FA 实例不知道它们的根，所以每个操作都好像您正在操作的 FA 实例是 FSM 的根，或者状态 q0。FSM 由根状态和从该状态可达的所有状态——闭包——组成。如果您使用 fa.FillClosure() 计算 FSM 的闭包，返回集合中的第一个状态始终是 fa。

有几个 static 方法用于组合 Thompson 构建，例如 Literal()、Set()、Optional()、Or() 和 Repeat()，还有一个 Parse() 方法用于从正则表达式解析。

基本上，您可以使用这些方法的组合来构建您的表达式或词法分析器。一旦您使用这些方法构建了 FSM，您就可以使用它来进行词法分析或匹配。建议您使用微软的正则表达式引擎进行后者，除非您需要流式处理输入。

FA 的设计并非用于匹配，但您可以使用内置的词法分析器来即兴创建一个匹配器，并报告任何 SymbolId 不为负的项。

请记住，FA 接受的所有输入值都期望是 UTF-32，这意味着它们必须从 UTF-16 字符值转换为 UTF-32 整数值。您可以使用 UnicodeUtility.ToUtf32 来处理字符串和字符数组。对于单个字符，您可以使用 char.ConvertToUtf32()。

至于其余部分，就让演示代码来说话吧。

var kws = "abstract|as|ascending|async|await|base|bool|break|byte|case|catch|char|checked|
           class|const|continue|decimal|default|delegate|descending|do|double|dynamic|else|
           enum|equals|explicit|extern|event|false|finally|fixed| float |for|foreach| get | 
           global |goto|if|implicit|int|interface|internal|is|lock|long|namespace|new|null|
           object|operator|out|override|params|partial|private|protected|public|readonly|
           ref|return|sbyte|sealed|set|short|sizeof|stackalloc|static|string|struct|switch|
           this|throw|true|try|typeof|uint|ulong|unchecked|unsafe|ushort|using|var|virtual|
           void|volatile|while|yield";
// shorten this so our state graphs aren't so big:
kws = "as|base|case";
var lexa = new FA[]
{
    FA.Parse(kws,0), // keyword
    FA.Parse("[A-Z_a-z][0-9A-Z_a-z]*", 1), // id
    FA.Parse(@"""([^""]|\\[^n])*""", 2),   // string
    FA.Parse("[\r\n\t\v\f ]+", 3)          // whitespace
};

// build our lexer
var nfa = FA.ToLexer(lexa);
nfa.TrimNeutrals();
Console.WriteLine("NFA has " + nfa.FillClosure().Count + " states");

// minimize
var dfa = nfa.ToDfa();
dfa.TrimDuplicates();
Console.WriteLine("DFA has " + dfa.FillClosure().Count + " states");

var baseFn = @"..\..\lex_";
var fn = baseFn + "nfa.jpg";
Console.WriteLine("Rendering...");
Console.WriteLine(fn);

// graphviz might not be installed:
try
{
    nfa.RenderToFile(fn);
}
catch
{
    Console.WriteLine("Rendering aborted - GraphViz is not installed. 
                       Visit GraphViz.org to download.");
}
            
fn = baseFn + "dfa.jpg";
Console.WriteLine(fn);
try
{
    dfa.RenderToFile(fn);
}
catch { }
var text = "\"\\\"foo\\tbar\\\"\"";
text = "\"base foo \\\"bar\\\" foobar  bar 123 baz -345 fubar 1foo *#( 0\"";
Console.Write("Lex NFA " + text + ": ");
var sb = new StringBuilder();
// lex NFA
Console.WriteLine(nfa.Lex(UnicodeUtility.ToUtf32(text).GetEnumerator(), sb));
                       
// build a simple symbol table so our ids match our NFA
var symids = new int[lexa.Length];
for (var i = 0; i < symids.Length; i++)
    symids[i] = i;

// create DFA state table
var dfaTable = dfa.ToDfaStateTable(symids);

// Use built in lexing method
Console.Write("Lex DFA " + text + ": ");
Console.WriteLine(FA.Lex(dfaTable,UnicodeUtility.ToUtf32(text).GetEnumerator(), sb));

// use tokenizer
var tokenizer = new Tokenizer(dfa, text);
foreach (var token in tokenizer)
    Console.WriteLine("{0}: {1}", token.SymbolId, token.Value);

这只是使用这个库的一种方式。另一种方式是使用它进行代码生成，以生成词法分析器。

就是这样！

限制

FA 引擎匹配速度相当快，但最小化速度可以更快。目前也没有锚点支持。

历史

• 2020 年 2 月 1 日 - 初次提交
• 2020 年 2 月 4 日 - 修复了 FA.Parse() 中的一个错误