Lexly：一个小型字节码可编程词法分析器/生成器

• 下载源代码 - 326.3 KB
• 从 GitHub 下载最新版本

引言

从哪里开始呢？我甚至不确定如何对它进行分类，只能说它又是另一个词法分析器生成器。但它算是一个奇特的玩意儿，就词法分析器而言。

我的 Rolex 词法分析器非常高效，但它无法处理 Unicode——或者说，如果能处理，你可能需要等待一周才能完成表格计算。DFA（确定性有限自动机）实际上无法处理 Unicode，而 Rolex 是基于 DFA 的。这是一个算法问题。

在需要 Unicode 支持的项目中，我开始使用昆士兰理工大学的 Garden Points Lexer 作为我首选的词法分析器——大多数现实世界中的重要项目都需要。我很喜欢它。它非常快，而且足够容易使用，但它很笨拙，我需要生成几个文件才能将其集成到我使用的任何东西中，而且它烦人地只将Stream作为唯一的流式输入源——不支持TextReader或IEnumerable<char>。我最终会生成一个词法分析器文件来喂给它，然后再生成更多代码文件来支持它，并且它每个命名空间只能渲染一个扫描器。这使得它在您提前规划的项目中还可以，但仍然不理想。

我想要一个支持 Unicode 的扫描器，偶然发现了Russ Cox 关于基于 VM 的正则表达式引擎的页面。这为我创建这个词法分析器生成器指明了基本方向。我根据那里提供的信息创建了这个工具，它生成了包含微型虚拟机（运行存储在int[][]数组中的字节码）的词法分析器。

什么意思？

词法分析器内部有一个虚拟机。该虚拟机运行用于匹配输入的专门指令集。这个项目将生成其中一个词法分析器，以及任意数量的“程序”，每个程序都是一个词法分析的配方。

基本上，程序就是词法分析器。这个工具不是强迫您携带一个库来运行这个字节码，而是为您生成在您拥有 CodeDOM 提供商的任何 .NET 语言（通常是 C# 或 VB.NET）中运行该字节码的代码。

概念化这个混乱的局面

我们这里有几个正在进行的事情。

首先，我们有Tokenizer类。它由该工具生成，但代码始终相同。它使用 Pike 虚拟机（以其创造者 Rob Pike 命名）的衍生版本来实现一个分词器/词法分析器/扫描器，这是一个通常只有十几个指令的微型虚拟机。这个虚拟机的酷之处在于它有“线程”——实际上是协程，它们就像线程一样，但进行协作调度而非抢占式调度。

我最近写了一篇关于这些漂亮的小型机器的文章，在这里。这基本上是那个文章的续集，但我会重新介绍一些内容。

接下来是生成代码的工具，包括这个分词器类，它还将从输入规范中编译和汇编词法分析器代码，以创建要馈送给这个分词器类的字节码。这将在下面解释。

最后，我们有汇编代码本身，您可以编写它，因为这个项目包含一个汇编器，或者您可以将正则表达式编译成这个代码。或者，您可以在单个词法分析器规范中混合使用正则表达式和汇编。

首先，我们的问题是从流式源匹配文本输入。我们不得回溯，并且必须足够灵活以匹配 Chomsky 层次结构中的任何类型 3 语言——也就是说，我们必须匹配正则表达式。例外是回溯特定的表达式。

宏汇编器指令集

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

宏/其他

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

说明

• match <symbol> 表示如果机器到达此处，则匹配成功，应返回指定的整数符号 ID。
• jmp <label> 表示机器应无条件分支到目标标签。
• split <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]* 的标识符
• 一个形式为 (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 VM 的内部工作原理，所以请务必阅读。如果你的极客品味和我一样，那将是非常有趣的。

基本上，我创建了一个协作调度的并发虚拟机来运行那个汇编语言代码——嗯，更准确地说，是运行那个汇编代码生成的字节码。它有一些巧妙之处，可以避免回溯，并使其在能力范围内尽可能快。它具有极强的潜力和高度的可扩展性，但它仍处于婴儿期，并且是一个正在进行中的项目。虚拟机本身是可靠的，但正则表达式部分还需要加强。

在名为Lex.csproj的独立项目中，有用于汇编和反汇编这些指令或从正则表达式编译它们的 API。这一切都在Lex类下。Lexly 使用此代码来发挥其魔力。

词法分析器规范格式

如果您使用过 Rolex，那么规范格式应该会很熟悉

它是一种基于行的语法，其中每个规则的形式为

symbolname [ "<" attributes ">" ] "=" ( literalString | quotedRegex ) 

其中symbolname是标识符，attributes是逗号分隔的属性/值对列表，literalString是 JSON 格式的转义字符串字面量（双引号"），而quotedRegex是括在单引号'中的正则表达式。

还有一种新的规则形式，可以使用汇编来指定

symbolname [ "<" attributes ">" ] { 
   
   <assembly code> 

}

请注意缺少等号。

这是上面显示的汇编代码相同的词法分析器，只是它以正确的词法分析器规范形式呈现

id= '[A-Z_a-z][0-9A-Z_a-z]*'
int= '0|\-?[1-9][0-9]*'
space= '[\t\n\v\f\r ]'

这样要短得多！

现在，如果需要，我们可以使用汇编和正则表达式的组合

id {
   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: 
} 
int= '0|\-?[1-9][0-9]*'
space= '[\t\n\v\f\r ]'

或者，使用宏

id {
   ; equiv to above!
   regex ([A-Z_a-z])
   regex ([0-9A-Z_a-z]*)
} 
int= '0|\-?[1-9][0-9]*'
space= '[\t\n\v\f\r ]'

您可以使用regex()汇编宏在当前位置注入任何正则表达式的汇编代码。这可以节省一些输入和调试时间。

请注意，我们从未使用过match或save，与我们上面最初显示的汇编代码不同。这是因为当链接器将我们的词法分析器符号连接在一起时，这段围绕的代码是自动插入的。

请注意，上面的每个块都有自己的命名容器，标签在命名容器内是唯一的。这意味着您不能跳转到符号之间，但您可以从同一个表达式返回不同的match符号，从而获得相同的结果。

实际上不需要汇编代码。您可以生成一个正则表达式来匹配几乎任何内容。话虽如此，您可以优化汇编代码，并且有些事情您可以用汇编做到而不能用正则表达式单独做到，例如返回不同的符号，如上所述。目前，它主要是一种炫酷的功能，但最终我计划添加一些仅用正则表达式无法实现的功能。

支持的属性

• hidden 表示词法分析器在遇到此符号时应跳过它而不报告。
• blockEnd="<value>" 表示词法分析器应继续扫描直到找到指定值，并将其消耗掉。这对于具有多字符结束条件的符号非常有用，例如 C 块注释、XML CDATA 部分和 HTML/SGML/XML 注释。也可以使用惰性匹配的正则表达式来完成此操作，但这通常更直接。
• id=<value> 表示与此符号关联的数值。这独立于符号的优先级，符号的优先级基于文档顺序。

目前不支持大小写不敏感。

其他技术

此项目依赖于Slang/Deslanged和CodeDOM Go! Kit进行代码生成。您会在此项目中发现一些奇怪的代码，这些代码可能是该项目的一部分，或者是其他包含项目（如 Lex 和 LexContext）的最小化部分。后者是使用CSBrick创建的。

我包含了构建这些源文件的构建工具，但没有包含这些工具的源代码。如果您想要源代码，您必须下载我不断增长的Build Pack。

编写这个混乱的程序

在使用任何内容进行编码之前，您需要让 Lexly 为您生成一些代码。有几种方法可以强制 Visual Studio 使用 Lexly：

将 Lexly 作为预构建步骤运行

首先，让我们设置 Lexly。这是用法屏幕

Lexly generates a lexer/tokenizer

Lexly.exe <inputfile> [/output <outputfile>] [/name <name>]
   [/namespace <codenamespace>] [/language <codelanguage>]
   [/noshared] [/ifstale]

   <inputfile>      The input file to use.
   <outputfile>     The output file to use - default stdout.
   <name>           The name to use - default taken from <inputfile>.
   <codelanguage>   The code language - default based on output file - default C#
   <codenamepace>   The code namespace
   <noshared>       Do not generate the shared dependency code
   <ifstale>        Do not generate unless <outputfile> is older than <inputfile>.

Any other switch displays this screen and exits.

• inputfile - 必需，指定前面描述的输入词法分析器规范。
• outputfile - 可选，要生成的输出文件——默认为 stdout。
• name - 可选，这是要生成的类的名称。如果未指定，则可以从文件名中获取。
• codelanguage - 可选，要生成的代码的语言。大多数系统支持 VB 和 CS（C#），但有些系统可能支持其他语言。您的体验可能会有所不同，因为这应该适用于许多（如果不是大多数）语言，但提前知道它将与哪些语言一起使用很难。
• codenamepace - 可选，如果指定，表示将在其下生成代码的 .NET 命名空间
• noshared - 可选，如果指定，表示生成的代码中不包含共享代码。当一个项目中有多个分词器时，这可能很有用。第一个分词器源文件可以不带此开关生成，然后后续的分词器源文件应带此开关生成，这样共享代码就只有一份副本。
• ifstale - 可选，如果指定，表示除非输入文件已更改，否则不会生成输出。这实际上不是必需的，因为这个生成器速度很快，但指定它也没有多大坏处。

以下是 C# 项目的说明——VB 项目的导航略有不同：导航到您的项目选项，然后是生成事件。在生成事件中，您需要为 Lexly 指定要使用的命令行。这是在LexlyDemo.csproj项目中设置的

"$(SolutionDir)Lexly\bin\Release\Lexly.exe" "$(ProjectDir)Example.lx" 
               /output "$(ProjectDir)ExampleTokenizer.cs" /namespace LexlyDemo

注意我们尽可能使用宏来避免硬编码路径，并注意我们如何引用了文件路径。这很重要。为要生成的每个词法分析器添加一个命令行。然后，每次生成项目时都会生成这些命令。我建议将 lexly exe 放在您要用它构建的项目或解决方案文件夹中，这样任何下载您源代码树的人都可以按原样构建它。如果您不为 C# 构建，请确保使用/language选项。

将 Lexly 作为 Visual Studio 自定义工具运行

您可以通过安装LexlyDevStudio.vsix将此工具设置为 Visual Studio 自定义工具，或者以推荐且功能更强大的方式将其用作预构建步骤。它需要一个词法分析器规范文件，并会生成一个实现Tokenizer以及您在所需 .NET 语言中的特定程序的代码文件。自定义工具的名称是 Lexly。使用此方法无法控制任何命令行选项。

针对生成的代码进行编码

使用分词器很简单。

var text = "foo 123 bar";
var tokenizer = new ExampleTokenizer(text); // generated from Example.lx
foreach (var tok in tokenizer)
{
    switch(tok.SymbolId)
    {
        case ET.id:
            Console.WriteLine("Input was id: " + tok.Value);
            break;
        case ET.@int:
            Console.WriteLine("Input was int: " + tok.Value);
            break;
        case ET.space:
            Console.WriteLine("Input was space: " + tok.Value);
            break;
        default:
            Console.WriteLine("Error in input: " + tok.Value);
            break;
    }
}

在ExampleTokenizer上，您会为规范文件中的每个符号找到一个常量。这将获得您的符号id。上面，它被别名为ET以节省一些输入。

如果您想从string或char[]数组以外的其他内容读取，您必须实现IEnumerable<char>来包装另一个源。可以使用TextReader等来实现这一点，我以前这样做过，但这超出了本项目范围。

限制

这个工具目前还不支持正则表达式的很多功能。它主要是一个我创建的用于运行的基线。它支持 Unicode 测试，如[[:IsDigit:]]和[[:IsLetter:]]，但不支持[[:digit:]]或其他标准的字符类。它不支持锚点或捕获组。这是一个正在进行中的项目。

这也不是最快的词法分析器实现。相反，它是一个非常非常灵活的词法分析器，并且生成词法分析器速度很快。要获得迄今为止最高效的词法分析器，请使用**Rolex**，但请记住它无法很好地处理 Unicode。

关注点

您可以反汇编项目中的任何词法分析器，只需引用**Lex**程序集，然后执行此操作

Console.WriteLine("Disassembly:");
Console.WriteLine(L.Lex.Disassemble(ExampleTokenizer.Program));

您可以通过设置Program字段来更改任何生成的Tokenizer派生类的词法分析器程序，但您需要确保您的程序与您的BlockEnds和NodeFlags匹配。此外，对于大多数情况，这只是一个有趣的技巧，不应该在生产环境中使用。

代码生成的工作原理

在 Lexly 的 Export 文件夹中，有用于创建 CodeDOM 树的主文件。这是使用deslang.exe（前面已链接）完成的，它被引用为预构建步骤，生成Deslanged.Export.cs。这并不是在运行时在Lexly本身中完成的，而是在 Lexly 构建时完成的。

这些 CodeDOM 树包含那些源文件中的代码，以 CodeDOM 树的形式。它们会根据需要使用CodeDomVisitor进行修复——这在Program.cs中运行时发生。在进行这些更改后，整个内容将以目标语言输出。

历史

• 2020 年 1 月 19 日 - 初始提交