面向对象解析：打破传统（第四部分）
4.96/5 (16投票s)
一种非传统的可扩展的语言解析方法。
引言
本文描述了一种非传统的、面向对象且可扩展的计算机语言解析技术。 具体来说，它涉及直接将 C# 解析为 codeDOM 对象，但相同的技术也可以应用于任何计算机语言。 包含源代码。 这是关于 codeDOM 系列的第四部分，但对于任何对解析技术感兴趣的人都可能有用。 在前面的部分中，我讨论了“CodeDOMs”，展示了一个 C# codeDOM，并为 codeDOM 提供了 WPF UI 和 IDE。
背景
在本系列的第一部分中，我讨论了传统计算机语言由于其文本性质通常是如何封闭的，以及定义它们的传统方法，即使用语法来生成解析逻辑，将文本形式转换为可以由编译器进一步处理的抽象语法树（AST）。 本系列中描述的 codeDOM 思想的主要目标是打破仅以文本形式定义计算机语言的传统，并摆脱文本的限制。 然而，现实情况是，如果它不能轻松地与文本进行互操作，codeDOM 就不会被广泛使用。 因此，是时候添加解析现有 C# 源文件的功能了。
解析应该如何工作？
我的解析逻辑的主要设计目标是能够轻松地对语言进行可能的修改，这与传统的解析技术不同。 应该能够添加新的 codeDOM 对象或对现有对象进行子类化，并在不修改单独的语法并重新生成解析逻辑的情况下包含解析支持。 我还决定解析是 codeDOM 对象将始终需要的一个关键功能，并且我想将解析代码包含在其中，以便它们“知道”如何解析自己。 如果您添加或更改 codeDOM 对象，则应能够在内部提供或修改必要的文本解析逻辑，而无需更改其他任何地方。 每个 codeDOM 对象都封装了它自己的解析能力，这就是我称这种技术为“面向对象解析”的原因。
旧的传统方法的一部分似乎仍然是必要的：将语言文本转换为一系列标记。 从那里，我们如何赋予我们的对象解析自己的能力？ 我的想法是思考人类在查看代码时是如何解析代码的，并尝试赋予我的对象相同的能力。 有时您会从关键字中识别代码 - 这很容易。 但有时它是从大括号或其他符号的位置，或者仅仅是代码中的一般模式。 例如，考虑一个 C# 属性和一个方法
public int Property { get; set; }
protected string Method(int parameter) { /*body*/ }
两者看起来都像一个可选修饰符后跟某种类型，然后是名称。 属性然后有围绕 get/set 方法的大括号，而方法有带有可选参数的括号和包含主体的大括号。 我们希望能够识别我们正在查看的内容，而无需向前看太远，因此即使属性主体中的 set/get 方法可能对人类来说很显眼，最好还是避免依赖它们。 根据看起来不同的第一个事物，我们可以说，如果名称后的下一个标记是开大括号（'{'），那么它很可能是一个属性，如果它是开括号（'('），那么它很可能是一个方法。 这两种情况也应该出现在类型声明中，而不是在方法体内部，所以作用域也可以考虑在解析中（稍后会详细介绍）。
我最终想到让每个 codeDOM 对象注册一个特定的标记（或标记），表明它可能找到了它自己的文本实例，并提供一个回调方法，该方法可以在确切决定并尝试解析其自身的新实例之前执行一些额外的验证。 出现的一个复杂情况是，某些标记可能指示多个不同对象中的任何一个。 我的解决方案是简单地允许与标记一起注册优先级，如果一个对象在标记流中“看到”的内容看起来不对，它就会推迟解析，下一个“排队”的对象就有机会了。 C# 的很大一部分可以通过依赖唯一的关键字和符号来解析，但在少数情况下需要这种优先级链（并且可以通过让更常用的对象首先检查来优化）。 选择优先级值确实需要在创建新对象时了解现有对象，但这是非常松散的耦合，并且值之间有很大的间隔（例如增加 100），因此新对象很容易“插入”到现有的优先级链中。
上下文敏感关键字和作用域
C# 语言有一些上下文敏感关键字，例如用于属性的‘get’、‘set’和‘value’。 只有当它们出现在预期的作用域中时，它们才是关键字 - 在其他地方，它们可以用于其他名称，例如局部变量。 我通过在注册用于解析的标记时包含一种类型的形式的作用域来处理此问题，并且如果父对象不是预期的类型，则不会激活回调。
在实现作用域时，我想到 C# 中许多不是上下文敏感的关键字也可以是。 例如，‘public’、‘private’、‘protected’等修饰符仅用于类型声明和类型的成员 - 没有理由让它们成为全局的。 全局关键字越少，受限名称就越少，当您编写像这样的项目（它模拟语言本身）时，将局部变量命名为语言关键字并不少见。 当然，C# 提供了‘@’前缀来规避名称冲突，但上下文敏感关键字似乎仍然很有意义 - 为什么不 whenever you can 使用它们？
最后，我使解析对于某些 C# 全局关键字具有上下文敏感性，因为没有额外的开销（我不想费力地强制它们成为全局的）。 例如，上述修饰符不会注册用于解析，因为它们被许多不同的对象使用。 相反，它们在标记流中被忽略，直到由另一个标记（如‘class’）触发的对象进行解析，然后它会稍微向后解析以获取任何修饰符。 因此，它们最终被有效地视为上下文敏感关键字而不是全局关键字。 这与 C# 规范不同并不重要，因为该技术将为有效的 C# 代码产生有效的结果。 无效的程序可能会解析不同，但这也不是问题，只要错误消息适当即可。 事实上，我确信我的解析器在某些无效代码的情况下实际上会产生比 C# 编译器本身更好的结果，但它在其他情况下也可能不准确，因为它尚未在无效代码上进行彻底测试。
只需尝试在 VS 中删除方法上的开大括号（'{'），然后观察从那里到文件末尾的错误 - 处理无效代码比这更容易，但大多数解析器并不怎么努力（实际上，很好地处理这种情况可能是反对上下文敏感解析的一个论点 - 这是一种权衡）。 请注意，理论上，如果您正在编辑 codeDOM 树并使用增量解析来解析更改，那么未匹配的大括号将产生一个错误消息，并且不会对受影响块之外的任何代码产生任何影响。 这是 codeDOM 相对于文本的又一个好处 - 理论上，编辑代码可以轻松完成，但不会因为您尚未完成编辑并且暂时有未匹配的大括号而导致从编辑点到文件末尾出现大量错误消息（VS 试图通过在您键入开大括号时自动插入闭合大括号来避免这种混乱，但这 hardly covers all editing situations）。
实现细节
每个 codeDOM 类都实现了一个名为“AddParsePoints()”的静态方法，用于将一个或多个标记注册到 Parser 类。 CodeObject 基类在静态构造函数（使用反射，但这是启动时一次性的）中调用所有这些方法。 对于要解析的每个文件或代码片段，都会实例化 Parser 类，并将文本解析为 Token，同时还将每个标记分类为标识符、符号、注释、字面量等。 将跳过空格和注释，以免它们干扰标记的解析，但（与大多数编译器不同）它们会被保留而不是被丢弃。 注释会保留在它们之前的 Token 上，并稍后附加到从该标记解析的对象上。 将为已注册且位于正确作用域的标记执行回调，回调会执行任何其他必要的验证，如果一切看起来都很好，它将从标记流中解析 codeDOM 对象的一个实例（否则它返回 null 以指示解析器该标记未被解析）。
例如，这是 ClassDecl 类的新 PARSING 区域（为简单起见，已删除一些处理编译器指令等边缘情况的代码）
#region /* PARSING */
// The token used to parse the code object.
public new const string ParseToken = "class";
internal static void AddParsePoints()
{
// Classes are only valid with a Namespace or TypeDecl parent, but we'll allow
// any IBlock so that we can properly parse them if they accidentally end up at
// the wrong level (only to flag them as errors).
// This also allows for them to be embedded in a DocCode object.
Parser.AddParsePoint(ParseToken, Parse, typeof(IBlock));
}
// Parse a ClassDecl.
public static ClassDecl Parse(Parser parser, CodeObject parent, ParseFlags flags)
{
return new ClassDecl(parser, parent);
}
protected ClassDecl(Parser parser, CodeObject parent)
: base(parser, parent)
{
parser.NextToken(); // Move past 'class'
ParseNameTypeParameters(parser); // Parse the name and any type parameters
ParseModifiersAndAnnotations(parser); // Parse any attributes and/or modifiers
ParseBaseTypeList(parser); // Parse the optional base-type list
ParseConstraintClauses(parser); // Parse any constraint clauses
new Block(out _body, parser, this, true); // Parse the body
}
#endregion
请参阅源代码以了解子例程的详细信息，但您可以了解大体思路。 不明显的一点是，ParseModifiersAndAnnotations() 方法实际上是在标记流中（从未使用过的标记列表中）向后解析，而其余的解析是向前进行的。 这实际上是更复杂的语言特性之一 - 大多数都更简单。
值得注意的是，我们还没有解析符号引用，所以大多数符号引用将解析为 UnresolvedRef 对象（以红色显示）。 内置类型（如‘int’、‘string’、‘object’等）是例外，因为它们由关键字解析，并且引用的类型是已知的。
复杂性
对于任何人来说，解析像 C# 这样复杂的语言并不像我到目前为止所展示的那么简单，这应该不足为奇。 出现的一些复杂情况包括
Block和Expression都需要各种特殊处理才能解析。 这在Block的“解析构造函数”以及Expression类上的特殊静态Parse()方法中得到处理。- 除了优先级之外，运算符还需要处理左/右结合性。这是通过使用不同的方法注册它们来处理的，并且
Expression.Parse()在解析表达式时会检索并使用它。 Parser类必须“最大化”标记，将“+=”视为一个标记而不是两个单独的标记。 相反，“>>”标记可能必须被视为两个单独的标记，具体取决于上下文（“A<T1, B<T2>>” vs “A >> B”） - 这是 C# 语法中一个众所周知的歧义。- 在某些情况下，有必要确定一系列标记是否看起来像有效的类型引用，而嵌套的泛型类型使此过程相当复杂。 泛型类型（和方法）在文档注释中也有一个备用语法（“
A{T}”），必须进行处理。 - 条件表达式（“
a ? b : c”）非常棘手，因为它们可以嵌套在非常复杂的表达式中，并且可空类型也使用‘?’标记。 内置的可空类型（如“int?”）由关键字解析，但区分其他可能的可空类型与条件表达式需要递归前瞻标记。 - 条件编译器指令非常复杂，因为它们可以分割任何本应解析为单个对象的代码。 需要大量特殊逻辑来处理这种情况，并且很可能存在一些罕见但可能但尚未处理的情况，但通过调整要解析的源来避免这种情况也很容易。
- 还有许多其他不太重要的复杂情况。
尽管这种解析技术原则上相对简单，但解析像 C# 这样复杂的语言绝不会简单。 这样做的一个主要优点是对象基本上知道如何解析自己，使其面向对象且可扩展。
这真的有效吗？
是的，它确实有效。 您可能会认为这项技术在只有传统解析方法才能处理的真正复杂的代码上会崩溃。 我只能说，我已经把它喂给了我能找到的每一堆 C# 代码，并且它都能够消化它们。 当然，一开始偶尔会有一些小问题，但我能够在我“面向对象解析”设计的范围内轻松地修复它们。
在我实现这个的过程中，有时我不确定它是否真的能处理所有情况。 现在它已经完成并且运行得很好，我认为大多数计算机语言应该使用类似的方法而不是旧的传统方法来解析。 我相信其他人可以改进我提供的实现，但总的来说，这种技术对我来说似乎更好。 我相信这会有争议，所以我想我是在给自己招惹麻烦……总之，至少这种方法允许语言对用户开放且易于扩展。
性能：这比传统解析慢吗？
我倒不这么认为。 大部分时间都花在了磁盘 I/O 上，如果您大部分消除了磁盘 I/O（通过连续两次运行测试），我看到的性能在每秒数十万行代码（100K 到 500K+，取决于 CodeDOM 版本、多线程、服务器模式 GC，当然还有被解析的代码库和 CPU 类型）。 这相当快。 它主要是将文本解析为标记，对每个标记进行哈希表查找，以及相当直接的解析。 一些 C# 功能可能有点棘手，需要对标记流进行一些前瞻，但这些情况并不经常发生。 目前还没有进行任何性能调优，所以可能还有改进的空间。 在以后的文章中，我将与 Roslyn 进行比较时，将更仔细地研究性能。
格式化
解析后的代码在 codeDOM 中保留了换行信息，因此在输出为文本时，它应该与原始输入非常相似，可能除了空格之外。 有一些选项可以控制制表符与空格的使用，这些可以在配置文件中设置。 输出中的空格符合 C# 的常见默认格式，但可以轻松添加选项以使用任何所需的格式。 可以通过添加对自动对齐的支持来处理用于对齐的额外空格，其中一些已经添加。 此 codeDOM 目前不设计为精确复制空格（尽管可以使用更多内存来轻松添加此类支持）。 但是，它非常接近，包括处理一些多行对齐场景。 可以轻松添加其他此类场景和/或空格选项，并且将根据需要添加。
Nova Studio 提供了“Diff”选项，该选项使用配置文件中配置的 diff 工具比较输入文本和输出，因此这对于查看可能存在的差异很有用。 通过此解析器运行代码的一个好处是，它会自动根据配置的设置对其进行重新格式化。 还有一个可用的“AutomaticFormattingCleanup”选项（可以在配置文件中打开）。 它执行以下操作：
- 删除单行函数体中的可选大括号，并将其添加到多行函数体中。
- 如果方法的大括号在新行上，则强制空大括号在单行上。
- 如果属性的 get/set 访问器具有单行函数体，则强制它们在单行上。
- 强制构造函数初始化器在新行上开始。
- 将出现在行尾的操作符移动到下一行的开头。
- 删除不需要的表达式中的括号，或者默认使用它们。
- 删除过多的空行或不合适位置的空行。
使用附加源代码
本期添加的新代码位于 Nova.CodeDOM 项目的新“Parsing”文件夹中，以及大多数现有 CodeDOM 类中各种与解析相关的、被分隔为带有“PARSING”注释的区域的方法。 此外，Nova.Examples 包含两个新测试，用于解析现有文件和代码片段，Nova.Studio 现在可以加载、解析、保存或 diff 任何 C# 文件（它使用 .config 文件中设置的任何 diff 工具来 diff 原始输入文件与 codeDOM 输出）。 尝试加载源代码中的各种文件，或尝试您自己项目中的一些文件。 与手动生成的代码不同，其中局部引用通常会解析，您会看到解析后的代码中的大多数引用都是未解析的 - 所以您会看到很多红色。 像往常一样，提供了一个单独的 ZIP 文件，其中包含二进制文件，以便您无需先构建即可运行它们。
摘要
我构建了一个违反计算机科学法则的解析器，正如很久以前在古代卷轴中所记载的那样……所以，也许我会被逐出教会。 它不是你通常的做法，但它似乎能快速轻松地完成工作，并且允许轻松地扩展我的 codeDOM 和新对象。 如果您愿意，您可以回到语法、解析器生成器和 AST，但我将坚持我的直接将文本解析为 codeDOM 对象的技术。
当然，还有很多工作要做。 我的 Nova Studio “IDE”目前一次只能加载一个文件，这不太有用。 它需要能够加载“.sln”和“.csproj”文件以及它们包含的所有源文件。 在我的下一篇文章中，我将添加面向 VS 解决方案和项目文件的 codeDOM 类和解析，以便可以轻松地将整个项目或解决方案加载到 codeDOM 中。