Regex 作为一台微型“线程化”虚拟机
4.29/5 (8投票s)
一个 Pike VM，用于在 C# 中运行非回溯 NFA 正则表达式
引言
免责声明：我将在此文中使用大量术语，并尽我所能解释它们，但顺序可能不尽如人意，如果您不太理解某事，请先记下来，继续阅读。我已经尽力避免这种情况，但我无法预测所有问题。
因此，之前，我使用了确定性有限自动机在我的分词器中实现了非回溯正则表达式。该算法很老，但非常高效。唯一的缺点是生成状态表所需的时间，尤其是在处理 Unicode 引入的大字符范围时。这是一个算法限制，几乎没有什么办法，最终我发现了。
我需要的是一种使用非确定性有限自动机的方法，并完全放弃转换为确定性模型。这解决了一部分问题，但仍然不支持像单词边界这样更复杂的正则表达式。
然后，Rob Pike、Ken Thompson 和 Russ Cox 等几位朋友给了我一个绝妙的主意，以一种非常有趣的方式高效地解决了这些问题，即使用一个具有专用指令集的微型虚拟机来运行正则表达式匹配。我在“进一步阅读”部分包含了关于此的几篇文章。对我来说，这种方法很吸引人，因为我就是喜欢这种位运算。它还有可能被编译成本机“真实”目标机器的指令集。我还没有在这里实现所有这些（现在！），但这已经是一个基础的运行时引擎。我应该强调，我的代码借鉴了他们引入的概念，如果没有看到链接中的代码，我可能不会这样做——功劳应归于他们。
概念化这个混乱的局面
首先，我应该解释确定性有限自动机和非确定性有限自动机。
有限状态机由状态图组成。每个状态都可以通过“输入转移”或“epsilon 转移”引用另一个状态。输入转移会消耗指定的输入，然后移动到目标状态。epsilon 转移会在不消耗或检查任何输入的情况下移动到目标状态。具有一个或多个 epsilon 转移的机器被认为是“非确定性”（NFA），并且在任何给定时间可能处于多个状态。非确定性状态机更复杂且效率较低，但对于任何非确定性状态机都存在一个确定性状态机（DFA），并且存在一种称为幂集构造的技术可以将 NFA 转换为 DFA。我一直使用这种幂集构造方法来创建 DFA，但对于 Unicode 范围来说，它耗时太长。
状态的闭包是状态本身以及从该状态可达的所有状态的唯一集合，无论是通过 epsilon 转移还是输入转移。闭包代表根状态所指示的状态机。这些图可以是递归的——这意味着状态可以指向自身。
匹配“foo”的状态机的图如下所示
但这并不实用。对于更接近“现实世界”的场景，这是一个简单的 DFA 分词器，可以匹配“id”（标识符）、整数或空格。
DFA 的好处是它一次只处于一个状态，所以状态之间的移动就像玩“蛇梯棋”一样简单。对于 NFA，它可能同时处于多个状态，因为下面的虚线一旦遇到就会自动移动，所以它们之间的移动会变得更加复杂。有效地做到这一点需要一定的技巧。为了说明这一点，这里有一个与上面等效的分词器机器，表示为 NFA。
您可能会问，为什么有人会构造 NFA，因为它更复杂、效率较低，而且每个 NFA 都有一个 DFA。嗯，有几个原因。第一个是，以编程方式从表达式构造 NFA 作为 NFA 更容易。以 DFA 的形式这样做需要极其复杂的冲突解决代码，以应对一个状态在相同字符上可以分支到多个状态的情况。它必须分割状态并创建更多状态来补偿。第二个是，从 NFA 到 DFA 的转换过程可能非常耗时，比匹配本身花费的时间还要长，所以如果您只使用一次正则表达式然后丢弃它，这是不切实际的。这对于分词器来说通常不是问题，因为分词器从不这样做，但对于纯正则表达式来说可能是一个问题。在这种情况下，运行一个效率稍低的运行时算法比提前优化它要好，因为优化可能比低效的匹配花费的时间更长。有时，例如在使用 Unicode 时，即使我们预先生成这些 DFA，它们的生成也可能需要很长时间，以至于预生成过程本身就有不切实际的等待时间。
还有另一个部分原因，那就是既然我们已经花费了开销，那么在不进行额外开销的情况下，只要我们使用 NFA，我们不妨添加更多功能。我将解释一下。
DFA 状态本质上有一个关联函数。该函数接受一个输入字符，并返回一个目标状态。我们现在称之为 Transition()（不是实际名称）。每次我们在输入流中遇到一个字符时，我们都会运行 Transition() 函数，从当前状态移动到其目标状态，或在前进光标时报告错误。为了使 NFA 工作，该函数将接受一个输入字符并返回多个目标状态！这意味着我们必须“同时”遍历多个路径才能匹配。或者至少这是一种看待方式。另一种看待方式是，机器必须“猜测”在给定多个选择时应该走哪条路径，而且它必须总是完美地猜测。前者实际上是我们做事的方式，而且比听起来容易，但后者在实践中结果完全相同。我保证这里没有魔术——只是它经常以后者的方式解释，但理论之下实践是相同的。
总之，我们想要比简单地根据单个字符进行转移更多的功能。为了启用 NFA，我们需要一个函数来无条件地跳转到某个状态而不消耗输入，还需要一个函数——请注意——在不消耗输入的情况下“同时”跳转到多个状态。这样，我们就可以沿着所有虚线前进。我暂时不深入解释我们如何跳转到多个目的地，只说我们将使用“协程”（fibers），它们有点像线程，来完成它。总之，既然我们添加了这些函数，我们就可以添加更复杂的功能，例如根据一系列范围进行分支，以提高匹配效率。
我们还有另一个问题需要解决，那就是在给定正则表达式的情况下，如何首先调用这些函数。我们将把正则表达式转换成一个微型“程序”，使用一些字节码，其中每个函数都由一个指令表示，然后我们解释这个程序来匹配。这个解释器就是运行我们正则表达式的东西。很酷，对吧？
将表达式转换为抽象语法树
在我们能够将正则表达式编译成字节码之前，我们必须首先将正则表达式解析成一种易于遍历的、规范的中间表示。我们将其表示为一个简单的二叉树。它不是最高效的搜索结构，但我们并不是在搜索它。无论如何，我们都会在发出字节码时遍历整个树。这个类有点难看，但它仅在编译过程中使用。它不向任何消费者（除了编译器）公开，因此它只需要“足够好”供编译器使用。
sealed class Ast
{
#region Kinds
public const int None = 0;
public const int Lit = 1;
public const int Set = 2;
public const int NSet = 3;
public const int Cls = 4;
public const int Cat = 5;
public const int Opt = 6;
public const int Alt = 7;
public const int Star = 8;
public const int Plus = 9;
public const int Rep = 10;
public const int UCode = 11;
public const int NUCode = 12;
#endregion Kinds
public int Kind = None;
public bool IsLazy = false;
public Ast Left = null;
public Ast Right = null;
public int Value = '\0';
public int[] Ranges;
public int Min = 0;
public int Max = 0;
...
这是一个如此一次性的类，我甚至没有为不同类型的节点创建 enum。这没关系，正如我们稍后将看到的。Kind 表示我们可以对正则表达式执行的操作类型，包括选择、连接、集合、“非”集合、可选、星号、加号等。由于它主要用于词法分析，我们不处理捕获组或锚点，但如果我们处理了，我们就会在这里添加相应的类型。对于一元表达式，仅使用 Left。对于二元表达式，则同时使用 Left 和 Right。对于字面量和 Unicode 类别，使用 Value，对于集合和非集合，使用 Ranges。IsLazy 用于量化匹配，表示匹配是非贪婪的还是贪婪的。这些信息足以将我们的正则表达式编译。我们通过静态 Parse() 例程生成这些结构，该例程是递归下降的，并且有点复杂。字符存储为 int，以便将来扩展。我希望最终支持 32 位 Unicode 值。
请注意代码中的 CharCls.cs 文件。这是一个生成的文件，我专门使用 LexTableGen 工具来生成它。该工具的作用是为各种命名字符类和 Unicode 类别创建许多打包范围。这样，我们可以通过避免在程序集加载时生成这些内容来节省一些启动时间。这些范围由解析器用于在使用命名字符集时用相应的数据填充 AST。我还没有填写所有字符类，因为此版本是初步的，因此像 \d 或 [[:digit:]] 之类的内容目前不起作用。我很快就会添加支持，但这对于演示来说并不重要。[[:IsDigit:]] 是 Unicode 等效项，并且可以使用。
定义虚拟机指令集
现在进入有趣的部分。这涵盖在 Russ Cox 的文章中，其中他介绍了 Rob Pike 的理论虚拟机，但我对理论虚拟机进行了相当多的增强，并包含了可以接受操作数数组的更复杂的指令。使用像 .NET 这样的垃圾回收系统的一个好处是，促进这些的嵌套数组很容易，不像在 C 中那样。
当我们生成分词器代码时，我们不希望该代码依赖于任何库。因此，我们不为指令创建类。相反，每条指令都编码为 int[] 类型的数组，其中索引 0 是操作码，其余索引包含操作数。这些数组本身存储在一个 int[][] 类型的程序数组中。这个程序数组代表正则表达式的程序。您可以运行此程序来匹配文本，或者将其转储为字符串以查看生成的代码。
让我们看一些代码。这是上面分词器部分的代码。一个“id”（标识符），形式为 [A-Z_a-z][0-9A-Z_a-z]*
L0000: set "A".."Z", "_", "a".."z"
L0001: split L0002, L0004
L0002: set "0".."9", "A".."Z", "_", "a".."z"
L0003: jmp L0001
L0004: match 0
您看到循环了吗？注意在 **L0003** 处，我们 jmp 回到 **L0001**。这是我们放在正则表达式末尾的 * 的一部分。
循环的另一部分是进入条件，由 split 指令指定。在这里，我们告诉机器跟随两个路径——**L0002** 和 **L0004**。由于 **L0002** 在 split 指令中排在第一位，因此它具有优先权。这表明它以贪婪匹配的配置方式。如果我们想使其成为非贪婪匹配，我们只需交换 split 中的两个操作数。
这是机器当前支持的指令列表
match <symbol>- 指示机器匹配并报告指定的符号jmp <addr>- 指示机器跳转到指定的地址split <addr1>, <addr2>, ... <addrN>- 指示机器跳转到每个指定地址并同时执行它们。char <ch>- 指示机器匹配单个字符并前进或失败any- 匹配任何字符并前进。在输入结束时失败。set <packedRange1>, <packedRange2>, ... <packedRangeN>- 指示机器匹配范围之一并前进或失败nset <packedRange1>, <packedRange2>, ... <packedRangeN>- 指示机器如果匹配范围之一则失败，否则前进ucode <cat>- 指示机器匹配特定的 Unicode 类别并前进或失败nucode <cat>- 指示机器如果匹配特定的 Unicode 类别则失败，否则前进save <slot>- 将字符位置保存在给定槽中。槽是任何整数值，并表示要存储该位置的寄存器编号。
请注意，还有其他操作码目前未使用。这些将在未来的版本中实现。
发出指令集
编译涉及遍历 AST 并根据节点类型发出指令。在 Compiler 中，我们有一个内部的 emit 例程，用于发出核心指令来“运行” AST 节点，然后有一个外部例程来发出构成分词器工作方式的包装代码。
这是内部例程
internal static void EmitPart(Ast ast, IList<int[]> prog)
{
int[] inst,jmp;
switch(ast.Kind)
{
case Ast.Lit: // literal value
// char <ast.Value>
inst = new int[2];
inst[0] = Char;
inst[1] = ast.Value;
prog.Add(inst);
break;
case Ast.Cat: // concatenation
if(null!=ast.Left)
EmitPart(ast.Left,prog);
if(null!=ast.Right)
EmitPart(ast.Right,prog);
break;
case Ast.Alt: // alternation
// first handle the cases where one
// of the children is null such as
// in (foo|) or (|foo)
if (null == ast.Right)
{
if (null == ast.Left)
{
// both are null ex: (|) - do nothing
return;
}
// we have to choose empty or Left
// split <i>, <<next>>
inst = new int[3];
inst[0] = Split;
prog.Add(inst);
var i = prog.Count;
EmitPart(ast.Left, prog);
inst[1] = i;
inst[2] = prog.Count;
return;
}
if (null == ast.Left)
{
// we have to choose empty or Right
// split <i>, <<next>>
inst = new int[3];
inst[0] = Split;
prog.Add(inst);
var i = prog.Count;
// emit the right part
EmitPart(ast.Right, prog);
inst[1] = i;
inst[2] = prog.Count;
return;
}
else // both Left and Right are filled ex: (foo|bar)
{
// we have to choose/split between left and right
// split <pc>, <<next>>
inst = new int[3];
inst[0] = Split;
prog.Add(inst);
inst[1] = prog.Count;
// emit the left hand side
EmitPart(ast.Left, prog);
// we have to skip past the alternate
// that comes next, so we jump
// jmp <<next>>
jmp = new int[2];
jmp[0] = Jmp;
prog.Add(jmp);
inst[2]= prog.Count;
// emit the right hand side
EmitPart(ast.Right,prog);
jmp[1] = prog.Count;
}
break;
case Ast.NSet:
case Ast.Set:
// generate a set or nset instruction
// with all the packed ranges
// which we first sort to ensure they're
// all arranged from low to high
// (n)set packedRange1Left, packedRange1Right, packedRange2Left, packedRange2Right...
inst = new int[ast.Ranges.Length + 1];
inst[0] = (ast.Kind==Ast.Set)?Set:NSet;
Array.Sort(ast.Ranges);
Array.Copy(ast.Ranges, 0, inst, 1, ast.Ranges.Length);
prog.Add(inst);
break;
case Ast.NUCode:
case Ast.UCode:
// generate a ucode or ncode instruction
// with the given unicode category value
// (n)ucode <ast.Value>
inst = new int[2];
inst[0] = (ast.Kind == Ast.UCode) ? UCode : NUCode;
inst[1] = ast.Value;
prog.Add(inst);
break;
case Ast.Opt:
if (null == ast.Left)
return; // empty ex: ()? do nothing
inst = new int[3];
// we have to choose between Left or empty
// split <pc>, <<next>>
inst[0] = Split;
prog.Add(inst);
inst[1] = prog.Count;
// emit Left
EmitPart(ast.Left, prog);
inst[2] = prog.Count;
if (ast.IsLazy)
{
// non-greedy, swap split
var t = inst[1];
inst[1] = inst[2];
inst[2] = t;
}
break;
// the next two forward to Rep
case Ast.Star:
ast.Min = 0;
ast.Max = 0;
goto case Ast.Rep;
case Ast.Plus:
ast.Min = 1;
ast.Max = 0;
goto case Ast.Rep;
case Ast.Rep:
// TODO: There's an optimization opportunity
// here wherein we can make the rep instruction
// take min and max values, or make a conditional
// branch instruction take a loop count. We don't.
//
// we need to generate a series of matches
// based on the min and max values
// this gets complicated
if (ast.Min > 0 && ast.Max > 0 && ast.Min > ast.Max)
throw new ArgumentOutOfRangeException("Max");
if (null == ast.Left)
return;
int idx;
Ast opt;
Ast rep;
switch (ast.Min)
{
case -1:
case 0:
switch (ast.Max)
{
// kleene * ex: (foo)*
case -1:
case 0:
idx = prog.Count;
inst = new int[3];
inst[0] = Split;
prog.Add(inst);
inst[1] = prog.Count;
EmitPart(ast.Left, prog);
jmp = new int[2];
jmp[0] = Jmp;
jmp[1] = idx;
prog.Add(jmp);
inst[2] = prog.Count;
if (ast.IsLazy)
{ // non-greedy - swap split
var t = inst[1];
inst[1] = inst[2];
inst[2] = t;
}
return;
// opt ex: (foo)?
case 1:
opt = new Ast();
opt.Kind = Ast.Opt;
opt.Left = ast.Left;
opt.IsLazy = ast.IsLazy;
EmitPart(opt,prog);
return;
default: // ex: (foo){,10}
opt = new Ast();
opt.Kind = Ast.Opt;
opt.Left = ast.Left;
opt.IsLazy = ast.IsLazy;
EmitPart(opt, prog);
for (var i = 1; i < ast.Max; ++i)
{
EmitPart(opt,prog);
}
return;
}
case 1:
switch (ast.Max)
{
// plus ex: (foo)+
case -1:
case 0:
idx = prog.Count;
EmitPart(ast.Left, prog);
inst = new int[3];
inst[0] = Split;
prog.Add(inst);
inst[1] = idx;
inst[2] = prog.Count;
if (ast.IsLazy)
{
// non-greedy, swap split
var t = inst[1];
inst[1] = inst[2];
inst[2] = t;
}
return;
case 1:
// no repeat ex: (foo)
EmitPart(ast.Left, prog);
return;
default:
// repeat ex: (foo){1,10}
rep = new Ast();
rep.Min = 0;
rep.Max = ast.Max -1;
rep.IsLazy = ast.IsLazy;
rep.Left = ast.Left;
EmitPart(ast.Left, prog);
EmitPart(rep, prog);
return;
}
default: // bounded minum
switch (ast.Max)
{
// repeat ex: (foo) {10,}
case -1:
case 0:
for (var i = 0; i < ast.Min; ++i)
EmitPart(ast.Left,prog);
rep = new Ast();
rep.Kind = Ast.Star;
rep.Left = ast.Left;
rep.IsLazy = ast.IsLazy;
EmitPart(rep,prog);
return;
case 1: // invalid or handled prior
// should never get here
throw new NotImplementedException();
default: // repeat ex: (foo){10,12}
for (var i = 0; i < ast.Min; ++i)
EmitPart(ast.Left, prog);
if (ast.Min== ast.Max)
return;
opt = new Ast();
opt.Kind = Ast.Opt;
opt.Left = ast.Left;
opt.IsLazy = ast.IsLazy;
rep = new Ast();
rep.Kind = Ast.Rep;
rep.Min = rep.Max = ast.Max - ast.Min;
EmitPart(rep, prog);
return;
}
}
// should never get here
throw new NotImplementedException();
}
}
您可以看到此例程的大部分复杂性在于渲染重复，例如 (foo){10,}，因为 Min 和 Max 的组合非常多。考虑到其他方面相对直接；该函数调用自身来渲染子表达式，在必须在两个表达式之间做出选择时渲染一个 split，在需要循环或跳过分支时渲染一个 jmp 指令，并且经常创建 split 和 jmp 指令，其中目标地址指向最后一个指令的后面。这是为了让我们能够将表达式链接在一起。分支中的最终位置实际上指向下一个尚未存在的指令的第一个位置。这没关系。它永远不会无效，因为外部 emit 例程总是在末尾添加至少一条指令。
为了发出分词器，我们必须从所有不同符号之间的主要分割开始。我们还必须发出 match 指令来报告匹配的符号。此外，我们必须 save 每个匹配的开始和结束位置。执行此操作的代码仍然比上面简单得多
internal static int[][] EmitLexer(params Ast[] expressions)
{
var prog = new List<int[]>();
int[] match, save;
// generate the primary split instruction
var split = new int[expressions.Length + 2];
split[0] = Compiler.Split;
prog.Add(split);
// for each expressions, render a save 0
// followed by the instructions
// followed by save 1, and then match <i>
for (var i = 0; i < expressions.Length; i++)
{
split[i + 1] = prog.Count;
// save 0
save = new int[2];
save[0] = Save;
save[1] = 0;
prog.Add(save);
// expr
EmitPart(expressions[i], prog);
// save 1
save = new int[2];
save[0] = Save;
save[1] = 1;
prog.Add(save);
// match <i>
match = new int[2];
match[0] = Match;
match[1] = i;
prog.Add(match);
}
// generate the error condition
// handling
split[split.Length - 1] = prog.Count;
// save 0
save = new int[2];
save[0] = Save;
save[1] = 0;
prog.Add(save);
// any
var any = new int[1];
any[0] = Any;
prog.Add(any);
// save 1
save = new int[2];
save[0] =Save;
save[1] = 1;
prog.Add(save);
// match -1
match = new int[2];
match[0] = Match;
match[1] = -1;
prog.Add(match);
return prog.ToArray();
}
一旦您掌握了它，这并不算太难。
这是我之前呈现的 NFA 分词器图所示的分词器的机器代码的完整转储
L0000: split L0001, L0008, L0020, L0024
L0001: save 0
L0002: set "A".."Z", "_", "a".."z"
L0003: split L0004, L0006
L0004: set "0".."9", "A".."Z", "_", "a".."z"
L0005: jmp L0003
L0006: save 1
L0007: match 0
L0008: save 0
L0009: split L0010, L0012
L0010: char "0"
L0011: jmp L0018
L0012: split L0013, L0014
L0013: char "-"
L0014: set "1".."9"
L0015: split L0016, L0018
L0016: set "0".."9"
L0017: jmp L0015
L0018: save 1
L0019: match 1
L0020: save 0
L0021: set "\t", "\n", "\v", "\f", "\r", " "
L0022: save 1
L0023: match 2
L0024: save 0
L0025: any
L0026: save 1
L0027: match -1
请注意我们是如何保存每个分词器符号段的开始和结束处的字符位置的。这是为了我们能够根据这些开始和结束位置进行捕获。Regex.CompileLexer() 会自动将这些插入指令流中。我们还有一个从 **L0024** 开始的最终匹配，它处理我们的错误条件，也由上述函数插入。它只是匹配任何字符并返回 -1 作为符号。它的优先级最低，所以只有当其他所有内容都失败时才会匹配。
执行机器代码
为了支持多个路径（通过 split 进入），我们的机器虚拟化了多个协程，它们类似于线程，但采用协作式调度。每个协程负责运行其中一个路径。上面，主协程将运行从 **L0001** 开始的路径，由于 split，还将启动其他协程，从 **L0008**、**L0020** 和 **L0024** 开始。
从虚拟角度看，每个执行线程（由协程表示）都尝试根据其前面的指令来匹配当前输入。您可以想象它们同时运行，但在幕后，它们都同步运行，这样我们就无需回溯输入流。如果这是真正并发的，那将需要回溯。这更有效率，并且产生相同的结果。由于创建协程几乎没有成本，因此我们不必担心频繁地创建和销毁它们，而我们将会这样做。一个协程通常运行一条指令，然后生成另一个协程来运行下一条指令。这可能看起来效率低下，但比替代方案（涉及从数组支持的列表中删除协程）效率更高。无论如何，这些都是结构体，所以我们不会因为对象创建而过度占用堆。
我们对协程进行优先级排序，以确保我们的匹配保持所需的非贪婪或贪婪。如果我们不这样做，我们就会遇到麻烦，因为我们的跳转基本上会被重新排序，我们不能允许这种情况发生。
为了确保我们获得了所需的最长匹配，我们只需持续运行直到所有协程退出。
我们的指令流由嵌套的 int[] 数组表示，而当前指令指针只是该数组中的一个整数索引。请记住，每个嵌套的 int[] 代表一条指令。每个协程都有指向主指令数组的指针以及它在该数组中的指令指针。它还有一个 Saved 列表，其中包含由 save 指令存储的所有已保存位置。我们将这些按协程存储，以便我们可以并发访问多个路径而不干扰保存位置。
我们将当前协程保存在一对交替列表中，以便同时保持优先级和效率。使用单个列表会在插入时需要复制，我们不希望那样。相反，我们创建两个列表，并在每个周期交换对它们的引用，并清空其中一个。这个想法我从 Russ Cox 的 C 代码中获得，并使用它，因为它是一个好主意。
基本上，我们构建了一个待执行协程的队列，然后让每个协程逐个字符地处理当前输入，过滤匹配（包括单个字符匹配，如 char 或 set，以及由 match 指示的整个匹配）——这是运行 VM 的完整 Lex() 例程。
public static int Lex(int[][] prog,LexContext input)
{
input.EnsureStarted();
int i,match=-2;
List<_Fiber> clist, nlist, tmp;
int[] pc;
int sp=0;
var sb = new StringBuilder();
IList<int> saved, matched;
matched = null;
saved = new List<int>();
clist = new List<_Fiber>(prog.Length);
nlist = new List<_Fiber>(prog.Length);
_EnqueueFiber(clist, new _Fiber(prog,0, saved), 0);
matched = null;
var cur = -1;
if(LexContext.EndOfInput!=input.Current)
{
var ch1 = unchecked((char)input.Current);
var ch2 = '\0';
if (char.IsHighSurrogate(ch1))
{
input.Advance();
ch2 = unchecked((char)input.Current);
cur = char.ConvertToUtf32(ch1, ch2);
}
else
cur = (int)ch1;
}
while(0<clist.Count)
{
bool passed = false;
for (i = 0; i < clist.Count; ++i)
{
var t = clist[i];
pc = t.Instruction;
saved = t.Saved;
switch (pc[0])
{
case Compiler.Char:
if (pc.Length!=0 && cur!= pc[1])
{
break;
}
goto case Compiler.Any;
case Compiler.Set:
if (!_InRanges(pc, cur))
{
break;
}
goto case Compiler.Any;
case Compiler.NSet:
if (_InRanges(pc, cur))
{
break;
}
goto case Compiler.Any;
case Compiler.UCode:
var str = char.ConvertFromUtf32(cur);
if (unchecked((int)char.GetUnicodeCategory(str,0) != pc[1]))
{
break;
}
goto case Compiler.Any;
case Compiler.NUCode:
str = char.ConvertFromUtf32(cur);
if (unchecked((int)char.GetUnicodeCategory(str,0)) == pc[1])
{
break;
}
goto case Compiler.Any;
case Compiler.Any:
if (LexContext.EndOfInput==input.Current)
{
break;
}
passed = true;
_EnqueueFiber(nlist, new _Fiber(t, t.Index+1, saved), sp+1);
break;
case Compiler.Match:
matched = saved;
match = pc[1];
// break the for loop:
i = clist.Count;
break;
}
}
if (passed)
{
var s = char.ConvertFromUtf32(cur);
sb.Append(s);
input.Advance();
if (LexContext.EndOfInput != input.Current)
{
var ch1 = unchecked((char)input.Current);
var ch2 = '\0';
if (char.IsHighSurrogate(ch1))
{
input.Advance();
++sp;
ch2 = unchecked((char)input.Current);
cur = char.ConvertToUtf32(ch1, ch2);
}
else
cur = (int)ch1;
}
++sp;
}
tmp = clist;
clist = nlist;
nlist = tmp;
nlist.Clear();
}
if (null!=matched)
{
var start = matched[0];
var end = matched[1];
input.CaptureBuffer.Append(sb.ToString(start, end - start));
return match;
};
return -1;
}
这是它调用的 _EnqueueFiber() 例程
static void _EnqueueFiber(IList<_Fiber> l, _Fiber t, int sp)
{
l.Add(t);
switch (t.Instruction[0])
{
case Compiler.Jmp:
_EnqueueFiber(l, new _Fiber(t, t.Instruction[1],t.Saved),sp);
break;
case Compiler.Split:
for (var j = 1; j < t.Instruction.Length; j++)
_EnqueueFiber(l, new _Fiber(t.Program, t.Instruction[j],t.Saved),sp);
break;
case Compiler.Save:
var saved = new List<int>(t.Saved.Count);
for (int ic = t.Saved.Count, i = 0; i < ic; ++i)
saved.Add(t.Saved[i]);
var slot = t.Instruction[1];
while (saved.Count < (slot + 1))
saved.Add(0);
saved[slot] = sp;
_EnqueueFiber(l, new _Fiber(t,t.Index+1, saved), sp);
break;
}
}
这里有一个奇怪的地方，除了这个项目整体的奇怪性之外，就是 Save 的实现，它必须存储由 sp 表示的当前字符串位置。它复制任何已保存的位置，确保列表中有足够的槽，然后将指定槽设置为 sp。我这样做是为了允许任意数量的槽来为这段代码进行未来proofing。当我们将来进行完整的正则表达式匹配时，我们可能需要大约 10 个反向引用，这意味着存储 20 个位置——每个反向引用的开始和结束。此外，我们可能会实现命名捕获组，这也需要更多的存储空间。另一个奇怪的地方是处理 Unicode 代理项，我们会在每次前进时处理。cur 保存当前的 UTF-32 整数值。
编写这个混乱的程序
这是我更大的 LexContext 包的一部分，它主要用于实现您自己的分词器和解析器。
LexDemo.csproj 代码演示了如何使用此代码。非常简单
static void Main(string[] args)
{
// compile a lexer
var prog = Regex.CompileLexer(
@"[A-Z_a-z][A-Z_a-z0-9]*", // id
@"0|(\-?[1-9][0-9]*)", // int
@"[ \t\r\n\v\f]" // space
);
// dump the program to the console
Console.WriteLine(Regex.ProgramToString(prog));
// our test data
var text = "fubar bar 123 1foo bar -243 @ 0";
Console.WriteLine("Lex: " + text);
// spin up a lexer context
// see: https://codeproject.org.cn/Articles/5256794/LexContext-A-streamlined-cursor-over-a-text-input
var lc = LexContext.Create(text);
// while more input to be read
while(LexContext.EndOfInput!=lc.Current)
{
// clear any current captured data
lc.ClearCapture();
// lex our next input and dump it
Console.WriteLine("{0}: \"{1}\"", Regex.Lex(prog, lc), lc.GetCapture());
}
}
这将产生如下分词结果
Lex: fubar bar 123 1foo bar -243 @ 0
0: "fubar"
3: " "
0: "bar"
3: " "
1: "123"
3: " "
1: "1"
0: "foo"
3: " "
0: "bar"
3: " "
1: "-243"
3: " "
-1: "@"
3: " "
1: "0"
有改进空间
这段代码还有待进一步开发。首先，有些指令，如点（dot），可以很容易地由 AST 使用但尚未实现。还需要添加更多的字符类。最终，最好包含一些最短字符串算法进行优化，一个可以编译成 IL 或 .NET 源代码的编译选项，以及一些更多匹配（而不是简单分词）的功能。
性能
我比较了我之前的正则表达式引擎所基于的 DFA 引擎的相对性能。
Lex: fubar bar 123 1foo bar -243 @#*! 0
DFA Lexed in 0.004 msec
Lex: fubar bar 123 1foo bar -243 @#*! 0
NFA Lexed in 0.049 msec
正如您所见，DFA 的速度是其 10 倍以上，而且虽然我们的小型机器还有改进的空间，但它永远无法像 DFA 那样快。
关注点
正则表达式的历史非常悠久，并且其演变也相当丰富。我发现 Russ 关于它们的文章从历史角度来看很有趣。代码可以追溯到 20 世纪 70 年代、80 年代和 90 年代，当时正则表达式不断发展，大多数都源自一些（不）著名的实现，例如awk。
延伸阅读
- 关于使用正则表达式的精彩指南：https://regexper.cn/tutorial.html
- Russ Cox 实现正则表达式的资源：https://swtch.com/~rsc/regexp/
- 以及他关于使用 VM 实现正则表达式的特定指南：https://swtch.com/~rsc/regexp/regexp2.html
- 词法分析/分词入门：https://en.wikipedia.org/wiki/Lexical_analysis#Tokenization
历史
- 2019 年 1 月 18 日 - 初次提交