将 DFA 正则表达式编译为 .NET 程序集
4.78/5 (9投票s)
反射.Emit 的冒险！ 在这里，我展示了一个具有 Compile() 功能的正则表达式引擎。
引言
我发表这篇文章是为了分享我认为有趣的代码。虽然我在上一篇文章中已经介绍了 DFA 正则表达式引擎的理论，但在这里我们将深入探讨如何实际运行这些引擎，最重要的是，将它们编译成程序集。
必备组件
- 您需要一个较新版本的 Visual Studio。
- 要运行
FsmExplorer或SimpleDemo，您需要安装并配置好 Graphviz 的PATH环境变量。它们对于本文来说并非绝对必需，但能为您提供完整的体验。
Microsoft Regex "Lexer": [■■■■■■■■■■] 100% Done in 1556ms
Microsoft Regex Compiled "Lexer": [■■■■■■■■■■] 100% Done in 1186ms
Expanded NFA Lexer: [■■■■■■■■■■] 100% Done in 109ms
Compacted NFA Lexer: [■■■■■■■■■■] 100% Done in 100ms
Unoptimized DFA Lexer: [■■■■■■■■■■] 100% Done in 111ms
Optimized DFA Lexer: [■■■■■■■■■■] 100% Done in 6ms
Table based DFA Lexer: [■■■■■■■■■■] 100% Done in 4ms
Compiled DFA Lexer: [■■■■■■■■■■] 100% Done in 5ms
理解这个项目
注意：这是一个 DFA 正则表达式引擎。微软的正则表达式引擎是基于 NFA 的。在本文中，我们不使用 NFA 来指代像微软那样的回溯引擎。当本文使用 NFA 时，指的是具有 epsilon 转移的有限自动机，如上一篇文章中所述。
我们之前已经讨论过状态机的理论，所以这次我们来谈谈代码。
从 NFA 生成代码是相当复杂且低效的，所以我们不会这样做。相反，我们将处理已经成熟的 DFA 状态机。如果您对此感到困惑，请再次查阅上一篇文章，其中详细解释了其中的区别。
让我们先看看运行时如何遍历
// start at state q0
FA state = this;
while (true)
{
// try to move on the current codepoint
// under the cursor
FA next = state.Move(lc.Current);
// if no moves
if (null == next)
{
// match or no match...
if (state.IsAccepting)
{
// if we're at the end, this is a match
// otherwise it's not because there is
// more text
return lc.Current ==
LexContext.EndOfInput?state.AcceptSymbol:-1;
}
// state wasn't matched
return -1;
}
// move the cursor one place
lc.Advance();
// move to the next state
state = next;
// if we're at the end this is a match
if (lc.Current == LexContext.EndOfInput)
{
return state.IsAccepting?state.AcceptSymbol:-1;
}
}
这段代码将确定给定的字符串是否能被正则表达式匹配，如果它是词法分析器表达式，它将返回匹配的符号（接受符号）。
如果您安装了 GraphViz，您可以使用随附的 FSM Explorer 项目来可视化此过程。它可以让您逐步了解 Move() 的过程。
基本上，我们从第一个状态开始，持续移动，直到找不到有效的移动。然后，如果到达输入末尾，我们检查当前状态是否是接受状态。如果是，则返回其符号，否则返回 -1 表示不匹配。
目前，它是在运行时遍历状态机，但我们想要的是将其编译成固定的机器码，以尽可能高效地匹配特定表达式。
我们将为匹配以下词法分析器状态机中的表达式编写代码
在编写代码以生成代码（无论是 C# 还是机器码或其他）之前，编写一个具体示例来参考生成器通常很有帮助。我在这里的 CompileDemo/CompiledProto.cs 中已经这样做了。
与其一次性检查所有代码，不如我们来看看状态 q0 和 q1 的实现。
// q0:
if (codepoint == ' ')
{
codepoint = lc.Advance();
goto q1;
}
if (codepoint == '-')
{
codepoint = lc.Advance();
goto q2;
}
if (codepoint == '0')
{
codepoint = lc.Advance();
goto q4;
}
if (codepoint >= '1' && codepoint <= '9')
{
codepoint = lc.Advance();
goto q3;
}
if ((codepoint >= 'A' && codepoint <= 'Z') || (codepoint == '_') ||
(codepoint >= 'a' && codepoint <= 'z'))
{
codepoint = lc.Advance();
goto q5;
}
return -1;
q1:
if (codepoint == ' ')
{
codepoint = lc.Advance();
goto q1;
}
return (lc.Current == LexContext.EndOfInput ? 0 : -1);
在研究完这些内容并对照上图中的图表进行学习后，您应该会开始看到 goto 和状态之间的关联，以及 codepoint 转移。第一个状态（q0）不是接受状态。这意味着如果我们找不到匹配项，则返回 -1。q1 是接受状态，所以如果我们在输入结束时到达这里，就表示匹配成功。如果我们没有到达输入结束，则意味着字符串末尾还有未匹配的额外文本。现在，这还不算太难，对吧？很好，因为现在我们需要为此生成 IL。
让我们看看这两个状态的 IL。它相当长，请耐心等待。我使用了 JetBrains dotPeek 来获取上面代码的这个凌乱的结果。
// q0:
IL_000d: ldloc.0 // codepoint
IL_000e: ldc.i4.s 32 // 0x20
IL_0010: bne.un.s IL_001b
IL_0012: ldarg.1 // lc
IL_0013: callvirt instance int32 [LexContext]LC.LexContext::Advance()
IL_0018: stloc.0 // codepoint
IL_0019: br.s IL_006e
IL_001b: ldloc.0 // codepoint
IL_001c: ldc.i4.s 45 // 0x2d
IL_001e: bne.un.s IL_0029
IL_0020: ldarg.1 // lc
IL_0021: callvirt instance int32 [LexContext]LC.LexContext::Advance()
IL_0026: stloc.0 // codepoint
IL_0027: br.s IL_0080
IL_0029: ldloc.0 // codepoint
IL_002a: ldc.i4.s 48 // 0x30
IL_002c: bne.un.s IL_0037
IL_002e: ldarg.1 // lc
IL_002f: callvirt instance int32 [LexContext]LC.LexContext::Advance()
IL_0034: stloc.0 // codepoint
IL_0035: br.s IL_00b5
// [35 4 - 35 45]
IL_0037: ldloc.0 // codepoint
IL_0038: ldc.i4.s 49 // 0x31
IL_003a: blt.s IL_004a
IL_003c: ldloc.0 // codepoint
IL_003d: ldc.i4.s 57 // 0x39
IL_003f: bgt.s IL_004a
IL_0041: ldarg.1 // lc
IL_0042: callvirt instance int32 [LexContext]LC.LexContext::Advance()
IL_0047: stloc.0 // codepoint
IL_0048: br.s IL_0095
IL_004a: ldloc.0 // codepoint
IL_004b: ldc.i4.s 65 // 0x41
IL_004d: blt.s IL_0054
IL_004f: ldloc.0 // codepoint
IL_0050: ldc.i4.s 90 // 0x5a
IL_0052: ble.s IL_0063
IL_0054: ldloc.0 // codepoint
IL_0055: ldc.i4.s 95 // 0x5f
IL_0057: beq.s IL_0063
IL_0059: ldloc.0 // codepoint
IL_005a: ldc.i4.s 97 // 0x61
IL_005c: blt.s IL_006c
IL_005e: ldloc.0 // codepoint
IL_005f: ldc.i4.s 122 // 0x7a
IL_0061: bgt.s IL_006c
IL_0063: ldarg.1 // lc
IL_0064: callvirt instance int32 [LexContext]LC.LexContext::Advance()
IL_0069: stloc.0 // codepoint
IL_006a: br.s IL_00c2
IL_006c: ldc.i4.m1
IL_006d: ret
// q1:
IL_006e: ldloc.0 // codepoint
IL_006f: ldc.i4.s 32 // 0x20
IL_0071: beq.s IL_006e
IL_0073: ldarg.1 // lc
IL_0074: callvirt instance int32 [LexContext]LC.LexContext::get_Current()
IL_0079: ldc.i4.m1
IL_007a: beq.s IL_007e
IL_007c: ldc.i4.m1
IL_007d: ret
IL_007e: ldc.i4.0
IL_007f: ret
这段 IL 中最长且最令人困惑的部分是处理上面 if() 语句中 codepoint 的复合测试表达式的部分，因为 IL 没有 && 或 || 的概念，必须对复合测试表达式的每个组件使用条件分支。
我认为生成这个会很有挑战性。这确实花了一些功夫才弄对，但最终生成的代码却出奇地简单，而且比上面的 C# 代码效率更高，或者说比 C# 能实现的更高效。
由于我不太确定从何开始，我认为我们将从编译器最基本的部分开始——生成一个常量 int。这比听起来要麻烦得多。
private static void _EmitConst(ILGenerator il, int i)
{
switch (i)
{
case -1:
il.Emit(OpCodes.Ldc_I4_M1);
break;
case 0:
il.Emit(OpCodes.Ldc_I4_0);
break;
case 1:
il.Emit(OpCodes.Ldc_I4_1);
break;
case 2:
il.Emit(OpCodes.Ldc_I4_2);
break;
case 3:
il.Emit(OpCodes.Ldc_I4_3);
break;
case 4:
il.Emit(OpCodes.Ldc_I4_4);
break;
case 5:
il.Emit(OpCodes.Ldc_I4_5);
break;
case 6:
il.Emit(OpCodes.Ldc_I4_6);
break;
case 7:
il.Emit(OpCodes.Ldc_I4_7);
break;
case 8:
il.Emit(OpCodes.Ldc_I4_8);
break;
default:
if (i >= -128 && i < 128)
{
il.Emit(OpCodes.Ldc_I4_S, i);
} else
{
il.Emit(OpCodes.Ldc_I4, i);
}
break;
}
}
真是个混乱。基本上，某些数字（-1 到 8）有简写指令，还有针对 sbyte 范围值的指令，以及针对其他数字的通用指令，后者的占用空间更大。我们可以对所有数字都使用后者，但为了生成紧凑的程序集，我们选择这样做。
现在我们来看看如何为一组 codepoint 范围构建测试条件。
private static void _GenerateRangesExpression(ILGenerator il,
bool ismatch,
Label trueLabel,
Label falseLabel,
int[] ranges)
{
for (int i = 0; i < ranges.Length; i+=2)
{
int first = ranges[i];
int last = ranges[i+1];
var next = il.DefineLabel();
if (first != last)
{
il.Emit(ismatch?OpCodes.Ldloc_0: OpCodes.Ldloc_3);
_EmitConst(il, first);
il.Emit(OpCodes.Blt, falseLabel);
il.Emit(ismatch ? OpCodes.Ldloc_0 : OpCodes.Ldloc_3);
_EmitConst(il, last);
il.Emit(OpCodes.Ble, trueLabel);
} else
{
il.Emit(ismatch ? OpCodes.Ldloc_0 : OpCodes.Ldloc_3);
_EmitConst(il, first);
il.Emit(OpCodes.Beq, trueLabel);
}
il.MarkLabel(next);
}
il.Emit(OpCodes.Br, falseLabel);
}
好的，ismatch 仅表示我们正在生成匹配例程。局部变量 codepoint 在匹配例程中位于槽 0，在搜索例程中位于槽 3。标签分别是为真或为假时跳转的位置。ranges 数组是打包成整数的数组，每两个连续的整数构成一对。
当范围实际上是单个值时，我们有一个分叉——即范围的第一个和最后一个 codepoint 相同。在这种情况下，我们只需要生成一次比较。否则，我们会继续输出“next”标签，以防之前的“||”测试失败。请注意 Blt（小于时分支）操作码，这是我们对范围下限的测试。如果失败，它会短路剩余的条件。这就是我们相对于 C# 代码获得微小优势的地方，而无需评估每一个 ||。我们之所以能这样做，是因为我们知道范围是排序的。
我将编译过程合并为一个单一的例程，这其实并非理想，但我不想为获取两个例程都使用的 MethodInfo 和 PropertyInfo 对象而复制代码样板。此外，这样我就不必反射两次，也不必在函数之间传递大量数据。
值得注意的是，我们没有探索 Search 函数，尽管它可能比 Match 更重要。原因是它有更多的杂项内容，会干扰解释，而又没有增加太多内容。主要区别在于，搜索例程在无法移动时会从 q0 重新开始，并尝试匹配下一个输入，它还会将匹配的输入收集到一个缓冲区中，生成带有光标信息和捕获文本的 FAMatch 对象。
我们主要在下面探讨匹配生成。
if (fa == null)
throw new ArgumentNullException(nameof(fa));
fa = fa.ToDfa(progress);
var closure = fa.FillClosure();
var name = "FARunner" + fa.GetHashCode();
var asmName = new AssemblyName(name);
var asm = Thread.GetDomain()
.DefineDynamicAssembly(asmName,
AssemblyBuilderAccess.Run);
ModuleBuilder mod = asm.
DefineDynamicModule("M"+name);
TypeBuilder type =
mod.DefineType(name,
TypeAttributes.Public | TypeAttributes.Sealed,
typeof(FARunner));
这声明了我们的动态程序集和一个派生自 FARunner 的包含类。FARunner 提供了 Search() 和 Match() 功能，这些功能委托给几个内部实现之一，包括我们编译的那些。它有一个 abstract int MatchImpl(LexContext lc) 函数，我们将对其进行重写。LexContext 的解释在后面。目前，您只需将其视为一个跨越输入文本的光标。
我们需要从 LexContext 实例以及 StringBuilder 的 ToString() 和 FAMatch 的 Create() 函数中获取几个成员。为此，我们使用反射并存储结果以备后用。
PropertyInfo lcpos = typeof(LexContext).GetProperty("Position");
PropertyInfo lcline = typeof(LexContext).GetProperty("Line");
PropertyInfo lccol = typeof(LexContext).GetProperty("Column");
PropertyInfo lccur = typeof(LexContext).GetProperty("Current");
PropertyInfo lccapb = typeof(LexContext).GetProperty("CaptureBuffer");
MethodInfo lcadv = typeof(LexContext).GetMethod("Advance");
MethodInfo lccap = typeof(LexContext).GetMethod("Capture");
MethodInfo lccc = typeof(LexContext).GetMethod("ClearCapture");
MethodInfo sbts = typeof(StringBuilder).GetMethod("ToString",
BindingFlags.Public | BindingFlags.Instance,
null,
Type.EmptyTypes,
null);
MethodInfo createMatch = typeof(FAMatch).GetMethod("Create",
BindingFlags.Static | BindingFlags.Public);
Search 和 Match 都接受一个 LexContext 参数。
Type[] paramTypes = new Type[] { typeof(LexContext) };
我们将跳过 Search 生成代码，转向匹配代码。我们做的第一件事是告诉 Reflection.Emit 我们需要一个签名类似于 public override int MatchImpl(LexContext lc) 的函数。反射 Emit API 使用的访问修饰符和存储类说明符等术语与 C# 不同。我们还没有告诉它我们要重写哪个方法。与 C# 不同，您必须使用反射 Emit API 来做到这一点，但我们会在之后完成。目前，我们只是获取一个 ILGenerator，我们可以用它来开始在方法体中生成代码。
Type matchReturnType = typeof(int);
MethodBuilder match = type.DefineMethod("MatchImpl",
MethodAttributes.Public | MethodAttributes.ReuseSlot |
MethodAttributes.Virtual | MethodAttributes.HideBySig,
matchReturnType,
paramTypes);
il = match.GetILGenerator();
接下来，我们进行一些簿记工作——当前的 codepoint 值和一组新定义（但未标记）的标签，对应于机器中的每个状态。
il.DeclareLocal(typeof(int)); // current 0
states = _DeclareLabelsForStates(il, closure);
现在我们将检索 lc.Current 属性并将其存储在位置 0——即我们的当前 codepoint。在此之后，我们检查是否到达输入末尾（在这种情况下，codepoint 将为 -1），如果是，我们检查第一个状态是否接受。如果不是，我们返回 -1。否则，我们返回 q0 的接受符号。
l.Emit(OpCodes.Ldarg_1);
il.EmitCall(OpCodes.Call, lccur.GetGetMethod(), null);
il.Emit(OpCodes.Stloc_0);
il.Emit(OpCodes.Ldloc_0);
il.Emit(OpCodes.Ldc_I4_M1);
il.Emit(OpCodes.Ceq);
// not end of input
// jump to the start of the state of the state machine
il.Emit(OpCodes.Brfalse_S, states[0]);
// we use this later - checks if q0 accepting
// and returns accordingly
retEmpty = il.DefineLabel();
il.MarkLabel(retEmpty);
if(fa.IsAccepting)
{
_EmitConst(il, fa.AcceptSymbol);
il.Emit(OpCodes.Ret);
} else
{
_EmitConst(il, -1);
il.Emit(OpCodes.Ret);
}
现在事情变得有趣了。在这里，我们遍历每个状态，最终标记相应的 states[] 标签。之后，我们调用一个非常冗长的函数——FillInputTransitionRangesGroupedByState()。
它的作用是遍历该状态的所有转移，并返回一个由目标状态和对应的转移到该目标状态的范围组成的对列表，这些范围按排序顺序排列。哇！如果需要，请阅读两次。
// for each state
for (int q = 0; q < closure.Count; ++q)
{
// mark the current state
var fromState = closure[q];
il.MarkLabel(states[q]);
// get the transition ranges grouped
// by the state they transition to
var trnsgrp = fromState.FillInputTransitionRangesGroupedByState();
这部分存储在 trnsgrp 的一个字典中。我们即将枚举它。
因此，我们从 _GenerateRangesExpression() 调用中得到两种可能性——我们要么找到了匹配项，要么需要尝试下一个目标状态的范围。定义的标签分别对应于这两种可能性。在调用 _GenerateRangesExpression() 之前，我们还会存储目标状态（trnsTo）和相关的范围（trnsRngs）。如果匹配成功，则表示我们找到了一个有效的转移，需要前进输入并转到下一个状态。否则，我们将跳转过去尝试下一个状态的下一个范围集。
foreach (var trn in trnsgrp)
{
var foundMatch = il.DefineLabel();
var tryNextStateRanges = il.DefineLabel();
var trnsTo = trn.Key;
var trnsRngs = trn.Value;
_GenerateRangesExpression(il,
true,
foundMatch,
tryNextStateRanges,
trnsRngs);
// matched
il.MarkLabel(foundMatch);
var toIndex = closure.IndexOf(trnsTo);
il.Emit(OpCodes.Ldarg_1);
il.EmitCall(OpCodes.Callvirt, lcadv, null);
il.Emit(OpCodes.Stloc_0);
il.Emit(OpCodes.Br, states[toIndex]);
il.MarkLabel(tryNextStateRanges);
}
最后，我们需要处理在给定状态下根本找不到任何匹配转移的情况。这表示两种情况之一：要么我们已到达输入末尾，在这种情况下，如果当前状态是接受状态则匹配成功，要么输入无法匹配，在这种情况下我们通过返回 -1 来拒绝它。
// not matched
if (fromState.IsAccepting)
{
il.Emit(OpCodes.Ldloc_0);
_EmitConst(il,-1);
var no_eof = il.DefineLabel();
il.Emit(OpCodes.Bgt,no_eof);
_EmitConst(il, fromState.AcceptSymbol);
il.Emit(OpCodes.Ret);
il.MarkLabel(no_eof);
_EmitConst(il, -1);
il.Emit(OpCodes.Ret);
}
else
{
_EmitConst(il, -1);
il.Emit(OpCodes.Ret);
}
现在，在结束 for 循环后，我们完成了实际的 IL 代码，只需要将方法插入到适当的 vtbl 插槽中（或者用 C# 的说法是重写基类方法）。
MethodInfo matchBase = typeof(FARunner).GetMethod("MatchImpl",
BindingFlags.NonPublic | BindingFlags.Instance);
type.DefineMethodOverride(match, matchBase);
终于！现在我们可以创建类型，然后创建该类型的一个实例并返回它。
Type newType = type.CreateType();
return (FARunner)Activator.CreateInstance(newType);
调用它就像对表达式使用 Compile() 一样简单，它会生成一个 FARunner 实例。然后，您可以在该实例上调用 runner.Match(...) 或 foreach(FAMatch in runner.Search(...)) 来进行匹配和搜索。
关于 LexContext
LexContext 是我使用的一个库和类，它管理着文本源（例如 string、char 数组或 TextReader）上的光标。它执行多种功能，例如跟踪光标位置、行号和列号，以及将传入的字符转换为 UTF-32 codepoint。此外，它还“规范化”了 IEnumerator<char> 和 TextReader 在使用方式上的极性不匹配，同时提供了一种安全的方法来随时检索当前的 codepoint，而无需使用 TextReader 的 Peek()，后者在网络上是不安全的。
历史
- 2024 年 1 月 6 日 - 首次提交