Lex：用于正则表达式的优化编译器

• 下载源码 - 1 MB

引言

这基本上是一个优化编译器的试验场，它使用正则表达式而不是传统的源代码作为输入格式，并生成专门的字节码进行匹配。字节码可以由包含的Pike虚拟机运行，以匹配文本。

这也许不是目前最快的C# NFA正则表达式引擎，但它支持Unicode和惰性表达式，并且由于优化编译器正在变得越来越快。

更新：已向编译器添加最终优化（根优化）。

更新 2：显著改进了优化。现在可以实现纯DFA（如果可能）。

概念化这个混乱的局面

概述

Pike虚拟机是一种运行正则表达式的技术，它依赖于输入程序来指示如何匹配。VM是一个解释器，运行执行匹配操作的字节码。字节码本身是从一个或多个正则表达式编译而来的。

基本上，Pike VM是一个小型的协作调度的并发VM，用于运行该字节码。它有一些巧妙之处可以避免回溯。它可能极其强大且可扩展，但这个版本仍处于早期阶段，并且是一个正在进行中的项目。VM本身是稳健的，但正则表达式可以做得更好，并且可以添加更多正则表达式功能，例如锚点。

特点

• 一个用于从Lex的汇编语言汇编字节码的汇编器
• 一个用于将字节码转换回汇编语言的反汇编器
• 一个将正则表达式转换为字节码的优化编译器
• 一个链接器，用于将不同的程序片段链接在一起
• 一个用于运行匹配的虚拟机实现

使用汇编器时，可以使用以下指令

宏/其他

• <label>: 表示一个标签/分支目标 - 这是程序内地址的别名
• regex (<expression>) 将正则表达式展开为代码
• ; 表示行注释。分号之后到行尾的所有内容将被汇编器忽略

说明

• match <symbol> 表示如果机器到达此处，则表示匹配成功，应返回指示的整数符号ID。
• jmp <label1>, <label2>, [<label3>, ... <labelN>] 表示机器应该分支到所有指示的目标标签，并按顺序优先级尝试。
• any 匹配任何单个字符并向前移动。
• char "<char>" 匹配指定的字符并向前移动。
• set ("<firstChar>".."<lastChar>" | "<char>") { , ("<firstChar>".."<lastChar>" | "<char>") } 匹配指定范围内的任何字符并向前移动。
• nset ("<firstChar>".."<lastChar>" | "<char>") { , ("<firstChar>".."<lastChar>" | "<char>") } 匹配不在指定范围内的任何字符并向前移动。
• ucode <cat> 匹配指定整数Unicode类别的任何字符并向前移动。
• nucode <cat> 匹配非指定Unicode类别的任何字符并向前移动。
• save <slot> 将当前输入位置保存在指示的整数槽中。

这是一个使用它来词法分析一组简单符号的示例

• 一个形式为 [A-Z_a-z][0-9A-Z_a-z]* 的ID
• 一个形式为 (0|\-?[1-9][0-9]*) 的整数
• 或者一个形式为 [\t\n\v\f\r ] 的空格

; simple lexer example by codewitch honey crisis

split id, int, space, error

id: ; [A-Z_a-z][0-9A-Z_a-z]*
save 0
set "A".."Z", "_", "a".."z"
id_loop: split id_part, id_done
id_part: set "0".."9", "A".."Z", "_", "a".."z"
jmp id_loop
id_done: save 1
match 0

int: ; (0|\-?[1-9][0-9]*)
save 0
split int_zero, int_nonzero
int_zero:
char "0"
jmp int_done
int_nonzero: split int_neg, int_pos
int_neg: char "-"
int_pos: set "1".."9"
int_loop: 
split int_part, int_done
int_part: set "0".."9"
jmp int_loop
int_done: save 1
match 1

space: ; [\t\n\v\f\r ]
save 0
set "\t", "\n", "\v", "\f", "\r", " "
save 1
match 2

error: ; anything not caught above returns -1
save 0
any
save 1
match -1

我们通常不会这样大规模地写出汇编代码。我们会将正则表达式用作词法分析器规范的一部分，或者甚至可能在词法分析器规范中嵌入一些汇编代码，但上面的代码是整个词法分析器规范的汇编代码。它本身不完整，因为它缺少符号表，但代码是有效的，这样您就可以从头到尾看到它。通常，当我们链接词法分析器规范时，这部分代码会为您生成。

总之，最终，这些东西会被解析，然后编译成一个包含我们指令的int[][]数组。我们可以将它与我们的符号表和其他信息一起提供给Tokenizer，让它启动并为我们进行词法分析。

无论我们有多少个词法分析器，我们只需要项目中的一个Tokenizer类——我们只需向Tokenizer提供不同的程序来让它运行不同的词法分析。也就是说，生成器会为每个词法分析器程序生成一个Tokenizer派生类，但这是为了方便，这样您的代码在使用之前就不必手动填充Tokenizer了。如果这还不清楚，请继续等待，稍后会演示。

但是它是如何工作的？！

我在这篇文章中介绍了Pike虚拟机的内部工作原理，请务必阅读。如果您是我的那种技术宅，那会很有趣。这篇文章主要是关于优化编译器的。

基本上，我们理想情况下想要做的是将上面提供的指令转换为更快的指令。这是实现“纯粹”DFA匹配的典型理想，但与上面是相同的。

save 0
switch case "A".."Z","_","a".."z":id_part, case "0":int_done,
case "-":int_neg,case "1".."9":int_digits,case "\t", "\n", "\v", "\f", "\r", " ":space,
default:error

; ([A-Z_a-z][0-9A-Z_a-z]*) part
id_part:
switch case "0".."9","A".."Z","_","a".."z":id_part, default:id_done
id_done:
save 1
match 0

; (0|\?[1-9][0-9]*) part
int_neg:
set "1".."9"
int_digits:
switch case "0".."9":int_digits, default:int_done
int_done:
save 1
match 1

; ([\t\r\n\v\f ]) part
space:
save 1
match 2

error:
any
save 1
match -1

DFA匹配是Pike虚拟机能执行的最快匹配，而且它能做到这一点是因为我添加了一个名为switch的特殊指令，我们几乎在上面所有的位置都使用了它。基本上，我们想要消除尽可能多的jmp指令，特别是带有多个操作数的jmp，这也包括switch的default。这可以降低我们的光纤数量，从而降低我们访问字符的次数。我们希望每个字符只访问一次。然而，每个光纤必须依次访问相同的字符（即使有些实际上不检查它），所以光纤的数量最终是性能的决定因素。一个光纤是理想的，但由于需要存储save状态，这个引擎无法达到这一点。

与大多数优化编译器一样，为了优化，我们需要为要编译的正则表达式创建一个执行图。这是一个有向图，它为我们提供了代码“流”的视图。因为这是正则表达式，我们可以使用经典的NFA和DFA有向图来表示我们的执行流。

解析后，将抽象语法树从解析器转换为类似上面的NFA（表示“id”）相对容易。然后，我们可以执行经典的最小化技术来获得等效的DFA。

这很有价值，因为每个epsilon转移（虚线虚线）都解析为一个jmp指令，请记住我们不想要这些，特别是带有多个操作数的。一旦有了DFA，我们就可以简单地将每个转移（实线）解析为switch中的一个case（每个状态都是一个switch），然后跳转到相关目标状态的代码。这是纯粹的DFA。这就是我一开始添加switch指令的原因。

问题在于支持根词法分析器状态，其中我们可能有惰性正则表达式。我们无法在执行图中表示惰性正则表达式，因此无法优化它们。此外，它们会使起始状态复杂化，因为它们不能成为DFA的一部分。我们必须改用jmp跳转到每个表达式的起始状态，这会大大降低性能，特别是对于大型词法分析器，因为它会创建大量光纤。

因此，即使对于优化后的图，我们通常也会在开始时有jmp指令，如下所示：

L0000: save 0
L0001: jmp L0002, L0008, L0013, L0016
L0002: set "A".."Z", "_", "a".."z"
L0003: jmp L0004, L0006
L0004: set "0".."9", "A".."Z", "_", "a".."z"
L0005: jmp L0003
L0006: save 1
L0007: match 0
L0008: switch case "-":L0009, case "0":L0011, case "1".."9":L0010
L0009: switch case "1".."9":L0010
L0010: switch case "0":L0011, case "1".."9":L0010
L0011: save 1
L0012: match 1
L0013: switch case "\t".."\r", " ":L0014
L0014: save 1
L0015: match 2
L0016: any
L0017: save 1
L0018: match -1

这里存在一个优化机会，我们可以将可优化的表达式组转换成一个复合表达式。基本上，我们在较大的NFA词法分析器中创建微型DFA词法分析器。这会将我们的根jmp减少到只需要它的状态。做到这一点很棘手，因为必须以保留顺序的方式进行。这里是生成的代码的样子：

L0000: save 0
L0001: jmp L0002, L0014
L0002: switch case "\t".."\r", " ":L0003, case "-":L0005, case "0":L0009, case "1".."9":L0006, case "A".."Z", "_", "a".."z":L0011
L0003: save 1
L0004: match 2
L0005: switch case "1".."9":L0006
L0006: switch case "0".."9":L0006, default:L0007
L0007: save 1
L0008: match 1
L0009: save 1
L0010: match 1
L0011: switch case "0".."9", "A".."Z", "_", "a".."z":L0011, default:L0012
L0012: save 1
L0013: match 0
L0014: any
L0015: save 1
L0016: match -1

现在我们大有进展了！这几乎是一个“纯粹”的DFA，除了在L0001/L0014处的错误条件检查。我考虑过将该部分也优化掉，但实际上，它的性能已经接近完整的DFA了。

 

不过，我们可以做得更好。我们现在要做的就是找到jmp <next address>, <error label>后面跟着switch出现在代码开头的情况，因为当机器的其余部分是纯DFA时，这种情况经常出现。所以我们查找这些情况，消除jmp，并将其替换为switch的default情况，指向<error label>。

我还修复了FA发出例程，使其停止输出重复的save/match代码。结合起来，这可以在可能的情况下生成理想的DFA。优化后的代码看起来与上面DFA中的代码完全一样，只是顺序可能不同——DFA不关心顺序，而NFA关心，因为DFA不会产生歧义。我们知道这一点是因为有限自动机的各种数学证明，但这里我不会涵盖数学。

 

我们继续看代码。

Using the Code

核心类名为Lex，它公开了词法分析引擎的所有主要服务，从编译器到解释器/VM。

通常，您会用它来构建词法分析器，如下所示：

var program = Lex.CompileLexerRegex(false,
        @"[A-Z_a-z][A-Z_a-z0-9]*", // id
        @"0|(\-?[1-9][0-9]*)",     // int
        @"[ \t\r\n\v\f]"           // space
    );

然后您可以Run()、RunWithLoggingAndStatistics()或Dissassemble()程序。

另外，您也可以用更少的工作量输入汇编代码：

var program = Lex.AssembleFrom(@"..\..\program.lasm");

通过一点额外的工作，可以将汇编代码与编译的正则表达式代码混合使用。您可以直接在汇编代码中使用regex()宏，也可以使用Lex API链接来自汇编和编译的各种代码片段。

var intAsm = Lex.AssembleFrom(@"..\..\int.lasm");            
var prog = Lex.LinkLexerParts(true,new KeyValuePair<int,int[][]>[] {
        new KeyValuePair<int,int[][]>(0,Lex.CompileRegexPart(@"[A-Z_a-z][A-Z_a-z0-9]*")), // id
        new KeyValuePair<int,int[][]>(1,intAsm),
        new KeyValuePair<int,int[][]>(2,Lex.CompileRegexPart(@"[ \t\r\n\v\f]")) // space
});

我们正在构建KeyValuePair<int,int[][]>对象传递给LinkLexerParts()，其中Key是期望的匹配符号ID，Value是程序片段。

基本上，我们在这里做的是编译预链接的正则表达式片段，并将其与intAsm链接。

switch case "0":int_done, case "-":int_pos, case "1".."9":int_loop
int_pos: set "1".."9"
int_loop: 
jmp int_part, int_done
int_part: set "0".."9"
jmp int_loop
int_done:

请注意，这里没有save或match指令。它们由链接器添加。您的工作是生成介于这些指令之间的代码。

运行机器很简单：

var lc = LexContext.Create("my test input");
while (LexContext.EndOfInput != lc.Current)
{
    lc.ClearCapture();
    var acc = Lex.Run(prog, lc);
    Console.WriteLine("{0}: {1}",acc,lc.GetCapture());
}

acc将是match符号ID，或者错误为-1。

包含在LexDemo中的演示代码对各种词法分析器配置进行了性能测试。

var test = "fubar bar 123 1foo bar -243 0 baz 83";
Console.WriteLine("Lex: " + test);
var prog = Lex.CompileLexerRegex(false,
        @"[A-Z_a-z][A-Z_a-z0-9]*", // id
        @"0|(\-?[1-9][0-9]*)",     // int
        @"( |\t|\r|\n|\v|\f)"      // space
    );

Console.WriteLine("Unoptimized dump:");
Console.WriteLine(Lex.Disassemble(prog));
Console.WriteLine();

var progOpt = Lex.CompileLexerRegex(true,
        @"[A-Z_a-z][A-Z_a-z0-9]*", // id
        @"0|(\-?[1-9][0-9]*)",     // int
        @"( |\t|\r|\n|\v|\f)"      // space
    );

Console.WriteLine("Optimized dump:");
Console.WriteLine(Lex.Disassemble(progOpt));
Console.WriteLine();

var progDfa = Lex.AssembleFrom(@"..\..\dfa.lasm");

Console.WriteLine("DFA dump:");
Console.WriteLine(Lex.Disassemble(progDfa));
Console.WriteLine();

var result = -1;
var count = 0f ;
var maxFiberCount = 0;
var avgCharPasses = 0f;

LexContext lc = LexContext.Create(test);
while (LexContext.EndOfInput!=lc.Current)
{
    var stats = Lex.RunWithLoggingAndStatistics(prog, lc, TextWriter.Null, out result);
    maxFiberCount = stats.MaxFiberCount;
    if (stats.AverageCharacterPasses > avgCharPasses)
        avgCharPasses = stats.AverageCharacterPasses;

    ++count;
}

Console.WriteLine("NFA ran with "+maxFiberCount+" max fibers 
                   and " + avgCharPasses+ " average char passes");
count = 0f;
maxFiberCount = 0;
avgCharPasses = 0f;
count = 0;

lc = LexContext.Create(test);
while (LexContext.EndOfInput != lc.Current)
{
    var stats = Lex.RunWithLoggingAndStatistics(progOpt, lc, TextWriter.Null, out result);
    maxFiberCount = stats.MaxFiberCount;
    if (stats.AverageCharacterPasses > avgCharPasses)
        avgCharPasses = stats.AverageCharacterPasses;

    ++count;
}
Console.WriteLine("NFA+DFA (optimized) ran with " +  
        maxFiberCount+ " max fibers and " + avgCharPasses + " average char passes");

count = 0;
maxFiberCount = 0;
avgCharPasses = 0f;

lc = LexContext.Create(test);
while (LexContext.EndOfInput != lc.Current)
{
    var stats = Lex.RunWithLoggingAndStatistics(progDfa, lc, TextWriter.Null, out result);
    maxFiberCount = stats.MaxFiberCount;
    if (stats.AverageCharacterPasses > avgCharPasses)
        avgCharPasses = stats.AverageCharacterPasses;
                
    ++count;
}
Console.WriteLine("DFA ran with " + maxFiberCount + 
                  " max fibers and " + avgCharPasses+ " average char passes");

for (var i = 0; i < 5; ++i)
    test = string.Concat(test, test);

for (var i = 0; i < 10; ++i)
{
    Console.WriteLine("Pass #" + (i + 1));

    Console.Write("NFA: ");
    Perf(prog, test);

    Console.Write("NFA+DFA (optimized): ");
    Perf(progOpt, test);    
  
    Console.Write("DFA: ");
    Perf(progDfa, test);
}

代码相当复杂，但大部分工作是记账和统计转储。对API的实际调用相当简单。

目前就这些。请务必查看此工具包中包含的其他项目，例如Lexly，它是一个使用此引擎的词法分析器生成器。

历史

• 2020年2月2日 - 首次提交
• 2020年2月4日 - 修复了FA.Parse()中的错误 - 略微改进了优化（文章中未体现）