Rolex：C# 中支持 Unicode 的词法分析器生成器

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

引言

词法分析通常是解析的第一阶段。在我们可以分析结构化文档之前，必须将其分解为称为标记（tokens）或词素（lexemes）的词法元素。大多数解析器都采用这种方法，从词法分析器获取标记，并将其作为基本输入。词法分析器也可以在解析器之外使用，并用于诸如最小化器或仅需要查找文档中模式的简单扫描器之类的工具中，因为词法分析器本质上作为复合正则表达式匹配器工作。

Rolex 生成词法分析器，使此过程既轻松又相对直观，无论是在定义它们还是使用它们方面。Rolex 生成的代码使用一种简单但可靠快速的 DFA 算法。所有匹配均在线性时间内完成。由于它不回溯，因此您无法为其提供潜在的二次方时间表达式。正则表达式很简单。没有捕获组，因为它们不需要。没有锚点，因为它们会使匹配复杂化，并且在分词器中用处不大。没有惰性表达式，但有一个定义多字符结束条件的机制，这可以满足惰性表达式 80% 的用途。

使用 Rolex 的主要优势是速度。生成的标记器速度非常快。使用 Rolex 的主要缺点是，除了正则表达式语法有限之外，生成复杂词法分析器需要花费时间。基本上，您在构建过程中预先支付 Rolex 的性能。

更新：用更快的变体替换了 FA 引擎，以加快代码生成速度，并进行了一些错误修复。移除了“prototype”选项。

更新 2：进一步提高了 FA 引擎的性能，并添加了 externaltoken 功能。

更新 3：简化了 DFA 表示 - 展平为整数数组。增加了使用 GraphViz 渲染词法分析器 DFA 和 NFA 图的能力。

更新 4：添加了图形输出，修复了代码生成中的错误，并改进了输出。

概念化这个混乱的局面

Rolex 命令行界面

使用 Rolex 相对简单。以下是使用界面

Usage: rolex.exe <inputfile> [/output <outputfile>] [/class <codeclass>]
   [/namespace <codenamespace>] [/language <codelanguage> [/external <externaltoken>]
   [/ignorecase] [/noshared] [/ifstale] [/nfagraph <dfafile>] [/dfagraph <nfafile>]
   [/graph <graphfile>] [/dpi <dpi>]

Rolex generates a lexer/scanner/tokenizer in the target .NET language

   <inputfile>      The input lexer specification
   <outputfile>     The output source file - defaults to STDOUT
   <codeclass>      The name of the main class to generate - default derived from <outputfile>
   <codenamespace>  The namespace to generate the code under - defaults to none
   <codelanguage>   The .NET language to generate the code in - default derived from <outputfile>
   <externaltoken>  The namespace of the external token if one is to be used - default not external
   <ignorecase>     Create a case insensitive lexer - defaults to case sensitive
   <noshared>       Do not generate the shared code as part of the output - defaults to generating the shared code
   <ifstale>        Only generate if the input is newer than the output
   <staticprogress> Do not use dynamic console features for progress indicators
   <nfafile>        Write the NFA lexer graph to the specified image file.*
   <dfafile>        Write the DFA lexer graph to the specified image file.*
   <graphfile>      Write all the individual rule DFAs to a graph.*
   <dpi>            The DPI of any outputed graphs - defaults to 300.*

   * Requires GraphViz to be installed and in the PATH

• inputfile（必需）- 指示要从中生成词法分析器的规范文件。这些将在下面描述。
• outputfile - 指示要生成到的输出代码文件，或默认为 stdout。
• codeclass - 指示生成的标记器类的名称。默认情况下，它从 outputfile 派生。
• codelanguage - 指示要为其生成代码的语言。这基于 outputfile 的扩展名（如果已指定），或默认为 C#。
• codenamespace - 指示要在此命名空间下渲染代码。默认为无命名空间。
• ignorecase - 指示整个规范应视为不区分大小写，除非在某个规则上指定了 ignoreCase=false。
• noshared - 指示不应生成共享依赖代码。默认情况下，Rolex 在标记器输出文件中生成所有依赖代码。如果您生成多个标记器，则只需要一份共享代码，因此只需为第二个及之后的标记器指定 noshared，以避免因代码重复而导致的编译错误。
• externaltoken - 指示 Rolex 应使用给定命名空间中提供的标记，而不是生成自己的标记。某些解析器提供自己的 token 结构。默认情况下，生成自己的 Token 结构。
• ifstale - 指示除非 outputfile 比 inputfile 旧，否则不应发生生成。这在预构建步骤中很有用，因此除非输入发生更改，否则输出不会重新构建。这对于生成耗时复杂的词法分析器规范尤其有用。
• nfagraph - 为词法分析器生成 NFA 状态机的图形。主要用于调试表达式。
• dfagraph - 为词法分析器生成 DFA 状态机的图形。
• graph - 为每个规则生成图形，包括块结束。可能很大。
• dpi - 生成的任何图形的 DPI - 默认为 300。

Rolex 词法分析器规范

词法分析器规范主要设计用于由其他工具（如 Parsley）进行机器生成。但是，如果您不怕正则表达式，手动使用它也很容易。

它是一种基于行的格式，每行类似于以下内容

ident<id=1,ignoreCase>= '[A-Z_][0-9A-Z_]*'

或更一般地说

identifier [ "<" attributes ">" ] "=" ( "'" regexp "'" | "\"" literal "\"" )

每个属性都是一个标识符，后面可选地跟 = 和一个 JSON 风格的字符串、布尔值、整数或其他值。如果未指定值，则为 true，这意味着上面 ignoreCase 设置为 true。请注意，字面量表达式用双引号括起来，正则表达式用单引号括起来。

有一些可用的属性，如下所示

• id - 表示与此符号关联的非负整数 ID
• ignoreCase - 表示表达式应被解释为不区分大小写
• hidden - 指示此符号应被词法分析器忽略，不报告
• blockEnd - 指示指定符号的多字符结束条件。遇到时，词法分析器将继续读取直到找到 blockEnd 值，并将其消耗掉。这对于具有多字符结束条件的表达式很有用，例如 C 块注释、HTML/SGML 注释和 XML CDATA 部分。这可以是一个正则表达式（单引号）或一个字面量（双引号）。

规则在匹配内容方面可能有些歧义。如果存在歧义，则规范中的第一个规则将被匹配，生成一组按 id（数字最小的优先）和否则按文档顺序优先排序的规则。

正则表达式语言支持基本的非回溯构造和常见的字符类，以及 [:IsLetter:]/[:IsLetterOrDigit:]/[:IsWhiteSpace:]/等，它们映射到 .NET 中的相应类。确保转义单引号，因为它们在 Rolex 中用于分隔表达式。

生成的代码 API

Rolex 使用简单的 API 暴露生成的标记器。每个标记器都是一个类，每个符号都声明为该类上的整数常量。标记器在构造时，接受一个 IEnumerator<char>，这通常是一个 string，但也可以是 char[] 数组或您实现的自定义源。或者，它将接受一个 TextReader。标记器 class 支持对标记的 foreach 枚举，这些标记的信息使用 Token struct 返回。Token struct 分别通过 Line、Column、Position、SymbolId 和 Value 返回行、列、位置、符号和捕获信息。标记器类上的 TabWidth 属性允许您设置输入设备的制表符宽度，默认为 4，以防它使用不同的宽度。这允许在奇怪的设备情况下准确返回列信息。希望您可以忽略它。请注意，列和位置并不相同！您的位置基本上是输入中的 UTF-32 代码点索引。如果您将字符串传递给标记器，Token.Position（当转换为 int 时）不一定是您在字符串中的绝对索引。这是因为某些字符需要代理对来表示它们。要获取字符索引，请使用 Token.AbsoluteIndex。另一方面，Column 属性是基于 1 的，与 Line 相同，表示输入设备布局中的位置。这包括计算制表符、换行符和回车符。

让我们将我们涵盖的内容结合起来，开始进行一些词法分析。首先，让我们创建一个规范文件，Example.rl

id='[A-Z_a-z][0-9A-Z_a-z]*'
int='0|\-?[1-9][0-9]*'
space<hidden>='[\r\n\t\v\f ]'
lineComment<hidden>= '\/\/[^\n]*'
blockComment<hidden,blockEnd="*/">= "/*"

上面，我们定义了 id 和 int，其余是隐藏的空白和注释。

现在，我们需要从 Rolex 中提取一些代码。

Rolex.exe Example.rl /output ExampleTokenizer.cs /namespace RolexDemo

将 ExampleTokenizer.cs 包含在我们的项目中后，我们可以这样使用它：

var input = "foo bar/* foobar */ bar 123 baz -345 fubar 1foo *#( 0";
var tokenizer = new ExampleTokenizer(input);
foreach(var tok in tokenizer)
{
    Console.WriteLine("{0}: {1} at column {2}", tok.SymbolId, tok.Value,tok.Column);
}

这将向控制台输出此内容：

0: foo at column 1
0: bar at column 4
0: bar at column 20
1: 123 at column 24
0: baz at column 28
1: -345 at column 32
0: fubar at column 37
1: 1 at column 43
0: foo at column 44
-1: * at column 48
-1: # at column 49
-1: ( at column 50
1: 0 at column 52

使其工作的底层算法极其简单。它是一种基于 DFA 的算法，使用标准的幂集构造技术构建，该技术被修改为一次使用字符范围而不是一次处理一个字符，以便它可以处理 Unicode。最小化基于 Hopcroft 算法（以前基于 Huffman 算法）。我之前几乎所有东西都使用了这个幂集构造技术（带有范围），但在这里没有，它在处理 Unicode 时遇到了问题。我之前认为这不可行，直到我看到一些其他库， namely "brics" in Java and its C# port "Fare" 正在使用这种技术，但它们的实现对我没有帮助，因为我们的代码差异太大。我最终自己解决了。我猜，仅仅知道这是可能的就足以让我解决它。这在我奋斗了多年之后。但然后我发现我的解决方案不起作用！最后，我仔细研究了 Fare 的代码，并从中吸取了足够多的经验，以便用我的代码创建一个类似的方法。我已经将版权声明包含在它影响的单个源文件中。至少完成了。我曾考虑在 Rolex 中使用 Fare，但调查后发现，它似乎根本不处理 Unicode 代理字符，而且错误处理很差，即使以我宽松的标准来看也是如此，所以我还是选择了自己的实现。Fare 在处理大型状态机时可能稍快一些，而且我知道在处理大型字符集时它会快得多，但它作弊，并且对代理值不起作用。Rolex 的正则表达式引擎内部是 UTF-32，所以没有这个问题，但它在生成表时需要更长的时间。

总之，问题解决了，我更酷的解决方案，如 Lexly，我基于 Pike VM 的词法分析器，在原始性能上无法与老式的 DFA 竞争，无论我做什么优化。DFA 不是酷技术。它们不像 小型字节码解释器 之类的东西。它们大部分都很无聊。但它们能做好工作，而且很快，这就是我们想要的。

正如我提到的，主要缺点是除了生成代码需要更长时间之外，它们还无法轻松支持诸如锚点、惰性匹配或捕获组之类的复杂构造，而无需“黑客”DFA 算法。对于分词器来说，这些功能并不重要。惰性匹配可能很重要，但 Rolex 提供了一种替代方案。

权衡是为了速度。Rolex 的词法分析速度比基于 NFA 的 Lexly 词法分析器快约 10 倍，比手动调优的基于 DFA 的 Lexly 词法分析器快约 2 倍，这仅仅是因为它不必托管一个复杂的虚拟机来运行它。

它仍然使用 Deslang/Slang 技术来渲染代码，但我已将其与 Build Pack 分离，并且只需将 Export 文件夹的内容包含在解决方案文件夹中的 deslang.exe 工具中，以满足预构建步骤的要求。它负责将 Export 文件夹的内容转换为 Deslanged.cs 代码，其中包含该文件夹中所有代码文件的 CodeDOM 表示。请注意，该文件夹中的文件不是完整的 C#，而是 Slang，一个符合 CodeDOM 的 C# 子集。如果您修改它们，如果不了解如何使用它，可能会破坏东西。

历史

• 2020 年 1 月 25 日 - 首次提交
• 2020 年 2 月 4 日 - 修复了 FA.Parse() 中的错误
• 2020 年 2 月 11 日 - 提高了生成速度，修复了 FA.Parse() 中的另一个错误
• 2020 年 2 月 25 日 - 提高了生成速度，添加了“externaltoken”功能
• 2023 年 11 月 18 日 - 简化了表，添加了选项，进行了少量错误修复
• 2023 年 11 月 20 日 - 进行了少量错误修复，添加了选项，改进了代码生成