Newt：一个功能强大且小巧的 C# 解析器生成器

• 下载源代码 (Newt) - 79.5 KB

以下是 Visual Studio 2017 集成的内容

• 下载 Cauldron (二进制文件) - 6.4 MB

引言

我一直对可用的解析器生成器产品感到不满。要么它们像 Cocos/R 那样有限且笨拙，要么它们像 ANTLR 的最新版本那样庞大且复杂。更糟糕的是，它们的语法会变得过于复杂以至于难以阅读，或者它们使用像 GLR 或 LL(k) 解析与 FA 结合之类的复杂引擎来处理解析过程，这使得它们的实现和使用都更加困难。

我也不喜欢它们中很少有提供拉取解析器——即你可以循环并一次调用 read 来获取一块数据。这对于解析海量的 JSON 数据等大型文档，或者甚至只是任何解析树足够大的内容至关重要。

最初，我打算编写一个解析器生成器，允许用户选择底层算法来解决这些限制中的一些问题，直到我偶然发现了一种更好且似乎不常见的方法，即使用一个非常简单的算法——LL(1)——来解析非常复杂的语法并生成合理的解析树。由于它是 LL，它允许在解析过程中进行简单的读取和遍历。

背景

要充分理解这一点，你可能需要至少对解析器生成器有所了解。如果你不了解，我会尽量简化讲解，那些不熟悉的部分可能对于使用最终结果并不重要，只是为了理解其背后的完整机制。

我将避免在这里谈论代码，而是谈论语法。首先，让我们定义一下我们所说的语法，在这种情况下，是上下文无关语法（如果你在意的话，是乔姆斯基层级的 Type-2）。

本质上，语法就是一系列规则。规则由左侧和一个或多个右侧符号组成，*或者*是一个 epsilon，它可以出现一次，并且单独出现。

什么是符号？它只是一个标识符。它可以是任何东西，只要你能回溯到它并再次找到它。例如，一个符号可以是字符串 "foo" ，你可以通过字符串是否相同来判断它是否与另一个字符串相同。

A -> a B 

A -> C B d

这里我们有两个规则，它们具有相同的左侧符号，并在右侧有一个符号列表。

具有相同左侧符号的一组规则统称为“非终结符”。这里，我们定义了具有两个规则的非终结符 A 。我们可以在任何其他规则中引用它，甚至可以使非终结符自引用/递归。当然，我们也可以在同一个语法中定义其他非终结符，例如

B -> B A
B -> A
B -> <epsilon>

Epsilon 在这里仅表示“无”或“空”。

规则如何定义解析？嗯，我们使用这些规则来了解我们正在解析的语法的层次结构。我们还没有讨论终结符，只有非终结符。

非终结符是解析树的节点，终结符是叶子。上下文无关语法可以通过符号引用终结符，但并不关心它们的定义方式。通常，终结符是使用小的正则表达式和字符串文字定义的。

上面，我们可以看到 B 引用了 A。B 也引用了它自己。这通过替换定义了一个零次或多次的循环。每次迭代，A 被解析的 A 定义替换，而 B 被另一个 B 实例替换。幸运的是，我们还有另外两条规则定义了循环的终止——要么是单独的 A，要么是空的（空/epsilon）。

我们就此打住。这对计算机来说可能没问题，但定义要解析的东西的方式非常糟糕。所以，与其教你所有细节，不如就说 CFG 就是那个丑陋的东西。

幸运的是，我们不必手动创建它们。我们可以使用类似 EBNF 的东西来描述表达式，然后生成这些语法。考虑以下自我描述的 EBNF 语法

grammar<start>=productions;
productions= productions production | production;
production=identifier ["<" attributes ">"] "=" expressions ";";
expressions= expressions "|" expression | expression;
symbol = literal | regex | identifier | 
    "(" expressions ")" | 
    "[" expressions "]" |
    "{" expressions "}";
expression = { symbol };
attributes= attributes "," attribute | attribute;
attribute= identifier ["=" attrval];
attrval= literal | integer | identifier;

literal = '"([^"\\]|\\.)*"';
regex = '\'([^\'\\]|\\.)*\'';
identifier= '[A-Z_a-z][\-0-9A-Z_a-z]*';
integer='\-?[0-9]+';
whitespace<hidden>= '[ \v\f\t\r\n]';
lineComment<hidden>= '//[^\n]*';
blockComment<hidden,blockEnd="*/">="/*";

抱歉没有语法高亮！

当你研究它时，假设你懂基本的正则表达式，它应该会逐渐变得清晰。这用它描述的语法描述了一个 EBNF 语法。

• [ ] 可选匹配方括号内的任何内容
• { } 重复匹配花括号内的任何内容
• ( ) 标准分组
• < > 属性集——特殊声明符，以某种方式修改或指定语法或解析树
• " " 字符串字面量
• ' ' 正则表达式——非回溯，基本。
• | 选择——简单的连接是隐式的，就像在正则表达式中一样。

这是一种更轻松的描述语法的方式！我们可以从中创建一个 CFG。问题是，CFG 无法开箱即用地与一些常见的解析算法一起工作，包括本文附带的算法。语法不是“LL(1)”，这意味着有两个具有相同左侧和相同第一个右侧符号的规则。

由于 expressions，该语法是左递归的，这意味着它可能导致无限循环。我们不想要那个。

幸运的是，有数学上的解决方法。它们可以通过所谓的左因子化来解决。Tutorials Point 上的左因子化

我们必须做的是*重构* CFG 语法，以便与我们的小型 LL(1) 解析器一起使用。

包含的项目处理了这个问题。左因子化的问题在于它会膨胀解析树。你必须创建额外的规则来绕过解析算法的限制。额外的规则意味着额外的非终结符，这反过来又意味着解析树上有额外的无用节点。“这有什么大不了的！”你可能会说。我说，当你解析一个 C# 文件，它使用了 7 个嵌套的非终结符来启动一个表达式时，再来找我。另外，解析树越深，解析和处理它的复杂度和资源消耗就越大。

我所做的是允许非终结符和终结符拥有与之关联的属性。你在上面的 EBNF 中会注意到几个。（上面有“hidden”、“start”和“blockEnd”）

以下是当前支持的

• type - 必须是一个字符串字面量，表示 .NET 或 C# 的内在类型名称 - 用于终结符，通过 .NET 中的 System.ComponentModel.TypeConverter 框架将词法分析器生成的字符串值强制转换为指定的类型，因此你可以添加自己的。请参阅 MS 文档。
• hidden - 布尔值，用于终结符，指示解析器丢弃它们并且不报告它们。这对于空格和注释很有用，并且在某些其他情况下也很有用，例如 HTML 中的 CDATA 部分，如果你不想解析它们的话。
• blockEnd - 字符串字面量，用于终结符，为 C 和 HTML 注释块等指定跳过结束点。这些结构不容易用非回溯 FA 匹配，因此这是一种特殊模式（但对解析器很常见），只需跳过直到在输出中找到指定的字符串字面量。然后，它会将整个文本作为终结符报告。指定 "*/" 对于 C 块注释很有用。指定 "]]>" 对于 CDATA 部分很有用。指定 "-->" 对于 SGML/XML/HTML 注释很有用。
  (上面未使用的:)
• substitute - 字符串字面量，用于终结符或非终结符，以指示一个要替换该符号报告的替代符号（必须已定义）。它不影响解析，只影响解析的报告。仍然遵循相同的规则，并且在内部符号仍然具有其底层标识——它只是从未被报告。

另一个你没看到的，是系统后台使用的一个最强大的功能。它被称为“collapse”，它所做的就是用其子节点列表替换自身。换句话说，它从解析树中移除自身，并将其子节点向上提升到其父节点，因此它基本上“隐藏”在树中，但会传播其子节点。

将“collapse”添加到在左因子化过程中创建的任何非终结符上，会产生看起来与生成它们的语法建议完全一样的解析树。

如果你熟悉解析器生成器，你就会知道，当 EBNF 语法像上面一样富有表现力时，最后一点要求很高。

Using the Code

像往常一样，我将在此提供示例代码来说明大部分内容。这建立在我的正则表达式引擎之上。

请注意，虽然 API 相对容易上手，但这只是一个我开始的研究项目，我并没有做太多重构或注释。我决定按原样提交，因为我将在接下来的**一年**里继续开发它，而且距离提交到 GitHub 还有至少两周时间，所以我的读者可以先睹为快。请投票支持 Pedro！（或者我）

// This demonstrates loading the ebnf.ebnf grammar file and 
// then using it to parse itself.
//
var grammarfile = @"..\..\..\ebnf.ebnf";

// parse our document into an EBNF DOM
// Note that an EBNF document is not a CFG grammar
// but it can be used to create one. It's also possible
// to create CFG grammars in other ways.
EbnfDocument doc = EbnfDocument.ReadFrom(grammarfile);

// create a CFG (context free grammar) from the DOM
var cfg = doc.ToCfGrammar();

// Write out the current CFG
Console.WriteLine(cfg);

// LL(1) is restrictive and most grammars won't be
// ready for LL(1) parsing without modification.
// We must remove left recursion, and then left
// factor the grammar to remove any ambiguity.
// PrepareLL1() does all of this, and returns any
// messages, warnings, and errors
//
// Note that this alters the grammar itself. 
Console.WriteLine("Preparing grammar for LL(1) parsing.");
var msgs = cfg.PrepareLL1();
bool hasError = false;
foreach (var m in msgs) {
    if (CfgErrorLevel.Error == m.ErrorLevel)
        hasError = true;
    Console.WriteLine(m);
}
if (hasError)
    return;

// write out the results of preparing the CFG grammar
Console.WriteLine();
Console.WriteLine("Modified grammar follows:");
Console.WriteLine();
Console.WriteLine(cfg);
Console.WriteLine();

// A parser uses a lexer to tokenize input, and a parser (based on a CFG) in order 
// to parse. A CFG is used to compute the parser. A lexer comes from elsewhere.
// In this case, we built it about using the DOM. We didn't have to. All we need to
// do is make sure that the tokens the lexer produces and the symbols the parser
// expects for the terminals match up. This is all handled for you if you just
// use the built-in facilities for lexing.
//
// use the DOM and the CFG together to create a lexer. CFGs don't know about lexing,
// only parsing. The DOM here knows what its lexer terminals are, so it is 
// responsible for building the lexer we'll pass to the parser later. It needs the 
// CFG so it can tie symbol names together with their ids and feed those to the lexer
// so that they agree on which symbols mean what.

// NOTE: If you do this before preparing the grammar, the lexer won't match up with the 
// modified CFG and you'll get a parse error, probably immediately.
var lexer = doc.ToLexer(cfg);

Console.WriteLine("Generating Table Driven Parser");
            
// cheap trick, but File.Exists doesn't work for UNC paths
try
{
    File.Delete(@"..\..\..\EbnfLLTableDrivenParser.Generated.cs");
}
catch { }
            
using (StreamWriter sw = new StreamWriter
      (File.OpenWrite(@"..\..\..\EbnfLLDrivenTableParser.Generated.cs")))
    // here below we generate a class that will parse the grammar represented by the cfg.
    // we write this to a file which is then used in this C# project to parse when the 
    // PARSER compile constant is defined. This method produces a table driven parser
    cfg.WriteCSharpTableDrivenLL1ParserClassTo(sw, "EbnfLLTableDrivenParser", null, lexer);

Console.WriteLine("Generating Compiled Parser");
try
{
    File.Delete(@"..\..\..\EbnfLLCompiledParser.Generated.cs");
}
catch { }
using (StreamWriter sw = new StreamWriter
      (File.OpenWrite(@"..\..\..\EbnfLLCompiledParser.Generated.cs")))
    // here we generate a class same as above but for the compiled parser. It doesn't use
    // tables to parse it generates switch cases for pretty much everything
    cfg.WriteCSharpCompiledLL1ParserClassTo(sw, "EbnfLLCompiledParser", null, lexer);

// parse itself
//
// here we tell the CFG to create an LL1Parser using the specified lexer we created.
// this is how to make a runtime parser and lexer - no code generation required, but 
// not as efficient
LLParser parser = cfg.ToLL1Parser(lexer, null);
            

Console.WriteLine("Using generated parser.");
parser.Close();
var pc = ParseContext.CreateFromFile(grammarfile);
            
// pick your poison - we've generated two classes, a table
// driven one, and a straight compiled one. The table driven
// one is usually a better choice, especially for large 
// grammars, but they should both be fast, and the compiled
// one probably takes less memory.

// commment out both lines below to use the runtime parser

parser = new EbnfLLTableDrivenParser(pc);
//parser = new EbnfLLCompiledParser();

// we use a parse context as the cursor over our input.
// restarting a parser simply allows you to feed it a new
// parse context. That way you can recycle an instance over
// several documents
parser.Restart(ParseContext.CreateFromFile(grammarfile));
            
// Dump our output to the console
// Since the Parser only keeps integer ids instead of symbol names around, the CFG
// is needed in order to do symbol-id to name resolution for printing.
// in your code you'll want to use the ints
OutputParseTo(Console.Out, parser, cfg);
parser.Close();

// one more time. This time grab the parse tree
parser.Restart(ParseContext.CreateFromFile(grammarfile));

var tree = parser.ParseSubtree();
parser.Close();
Console.WriteLine(tree.ToString(cfg)); // give it our parser so it can resolve ids

我包含了一个简单的表达式求值器和用于生成代码的“newt”命令行实用程序。

我还添加了修补性的语法高亮器。

这仍然是一个早期提交——还需要大约一年的工作我才会非常满意，但我已经在使用了，它很有趣，而且相当强大。

如果你像我一样仍然使用 VS2017，你可能需要安装 Visual Studio 的 4.7.2 或 4.8 目标包才能生成其中一些项目。

另一大杀器，Cauldron

我包含了一组独立的二进制文件，用于一个 VSIX 包，该包将 Newt 集成到 Visual Studio 中作为“自定义工具”——项目的源代码太大，无法在此分发，但我可以应要求提供。

安装后，你可以向项目中添加一个语法，将解决方案资源管理器中文档的自定义工具属性设置为 NewtParserGenerator。

现在，每当你编辑该文件并保存它时，代码就会自动生成。生成的类是 <Input Grammar Filename>Parser，例如，Ebnf.ebnf 将会创建 Ebnf.cs，其中包含 EbnfParser 类。最终，我可能会在语法中添加一个属性来指定其代码表示，以便你可以更改类名，但目前是这样做的。

Cauldron 还有其他生成器，我在这里简要提及。使用指定的名称作为自定义工具字段来为给定的输入文件实例化工具。如果你对它如何在 Visual Studio 中工作有疑问，请在此处评论提问。

• MergeMinifyPreprocessor 接受一个包含文件名列表（文件相对路径）的输入文件，并生成一个单一的、最小化的 C# 源代码“块”，你可以更容易地重新分发。我内部使用它来处理我庞大的代码库，当我想从我构建的巨大代码库中提取一部分代码时。你还可以指定 ;foo 来在列表中包含行“foo”作为原始文本。放在文件之间。或者放在顶部。使用 ;; 将使其始终出现在顶部。
• RegexGenerator：我建议你不要使用这个。它能工作，但解释你为什么要使用它需要另写一篇文章。它用于构建带有部分 FA 词法分析器的手动解析器。它也不会生成支持复杂错误恢复的类。
• TinyT4Preprocessor：我使用这个小东西生成的代码运行过应用程序中心的、进程内的 Web 服务器。它只是一个简陋的 T4 处理器，只生成 C#，并且不需要 Microsoft 的 CodeDom nuget 包。它唯一支持的模板指令是 template ，但你不需要其他指令。它支持基本的 T4。与 Microsoft 的 T4 引擎相比，它有一个主要优势——它进行流式处理。因此，你可以使用 HTTP 中的分块传输编码来提高大型文档的性能。Microsoft 的出于某种原因不进行流式处理。然而，它主要不是用于提供网页，而是用于编写 C# 代码生成例程。我更常在这些标签之间使用更多的 C# 代码，而不是 HTML！

关注点

我认为这可能与 NorKen Programmar 使用的算法非常相似，但我不确定，因为他们从未披露过他们的算法。我没有试图模仿他们，但我确实使用了类似于他们 EBNF 格式的东西，因为那是我见过的最简洁的。

历史

• 2019 年 5 月 11 日：首次提交
• 2019 年 5 月 13 日：更新
  • 移除了纯编译解析器支持，因为它太慢了，并且随之移除了 C#7 之前的支持。
  • 生成的表驱动解析器速度快了很多，我无法证明保留替代方案的合理性。
  • 添加了命令行工具支持和一个新的示例应用程序。移除了语法高亮器，因为它不是 .NET Core 应用程序。即将推出新更新，包括一个接受你的语法的 .NET Core 基于 Web 的语法高亮器。
• 2019 年 5 月 14 日：更新
  • 我已重新添加对较新版本 .NET 框架的支持。由于 .NET Core 中字典构造函数的不同，之前的版本无法正常工作。我还优化了表解析器生成，但牺牲了一点内存。
  • 既然 .NET 框架已回归，我已包含一个额外的示例。高亮器也回来了。