使用 Parsley 解析任何内容：一种不同的方法
4.97/5 (9投票s)
使用 Parsley 组合式解析器生成器来解析一个包含回溯的复杂语法。
更新： 语法错误修复（微小改动 - 文章中未体现），代码生成有所改进。新增 `shared` 属性，将生成函数标记为公共。语法略微复杂，但现在可以捕获注释。
包含更多错误修复和下一步的文章2 在此处。
引言
最初，Parsley 仅仅生成基于递归下降 LL(1) 的解析器。尽管它非常灵活，并具有许多超越 LL(1) 限制的功能，但最终我考虑了使用“子解析器”和“子语法”来允许简单和复杂的组合解析的想法，这最终使得解析变得更加容易。它还允许我将解析分解为独立的单元，既解决了冲突，又扩展了最终解析器（或多个解析器）的灵活性，并将大型语法分解为可维护的块。
请注意，Parsley 仍在开发中，所以它还有点粗糙和脾气暴躁，但只要给予它一些爱和耐心，它就会好起来。
Slang 是 C# 的 CodeDOM 兼容子集，我将其用于我的代码生成工具。它允许您使用 C# 编写 CodeDOM 构造，而不是手动构建它们。有关 Slang 的更多信息，请参阅链接。
最初，我使用手动构建的递归下降解析技术编写了 Slang 解析器，该技术类似于微软生产 C# 编译器所使用的技术。然而，维护是一项艰巨的任务，尽管源代码分布在多个文件中，但它很快就变得令人难以承受。与微软不同，我没有一个团队可以将解析器不同部分的构建委托给他们。
为此，我需要一个能帮助我构建解析器的工具。我考虑过使用 ANTLR，但我不喜欢它的 API 或语法格式，而且我为 C# 找到的语法生成了一个 800K+ 的源文件用于解析 C#6 —— 但它无法解析！不，谢谢。继续寻找，我还找到了 Coco/R 的语法，但它使用了太多嵌入式状态来解决解析问题，以至于难以理解，导致我遇到了与我的手写解析器相同的维护和理解问题！出于各种原因，我坚持使用 LL 解析而不是 LR 解析，所以像 Gppg 这样的工具被排除在外，即使它们可以解析 C#。如果您不知道 LL 和 LR 解析之间的区别，在这里并不重要，但 LL 是自上而下解析的，使用语法来指导解析，而 LR 是自下而上解析的，使用下一个输入来指导解析。第一个使用语法来查找有效输入，第二个使用输入来尝试将其与语法匹配。第二个不利于直观的语法导向操作。
背景
这就是我创建 Parsley 的原因。虽然我专门为此任务构建了它，但它是一个很棒的通用解析器生成器，尽管还有点不成熟。它允许您将手写解析代码与生成的解析代码混合在一起，这非常适合解析真正复杂的语法和非 LL(1) 的语法——也就是说，需要多个符号前瞻的 LL 语法。这样，我就可以在 XBNF 中描述 LL(1) 的“简单”构造，例如
Expression<start, follows="semi rparen rbracket comma">=AssignExpression;
RelationalExpression = TermExpression { ("<"|"<="|">"|">=") TermExpression };
EqualityExpression = RelationalExpression { ("=="|"!=") RelationalExpression };
BitwiseAndExpression = EqualityExpression { "&" EqualityExpression };
BitwiseOrExpression = BitwiseAndExpression { "|" BitwiseAndExpression };
同时使用我们自己的代码构建更复杂的东西。对于 Parsley 无法生成的部分——那些更棘手的构造——我使用了 Parsley 的“`virtual`”特性，它允许我们使用 C# 或 Slang（C# 子集）的组合来编写部分语法。此外，我们可以使用 Parsley 的组合语法特性来解析那些可能与更大语法冲突的构造。此外，我们可以利用 Parsley 的自动回溯特性，这使得解析歧义构造变得更容易。Parsley 使用试错法来处理自动回溯，但我们将在下面探讨所有这些。
必备组件
本文已经涵盖了如此多的内容，以至于我将使用 Parsley 的背景知识推迟到我的相关文章中。强烈建议您先阅读该文章，因为我不会在这里再次介绍基础知识。这里的语法大约有两百行长。本文旨在在一个高级且非常复杂的语法中使用 Parsley 的所有特性。
本文还假设您理解递归下降解析的基础知识，这是一种非常基本的解析技术，适用于手动编写的解析器。Parsley 有点罕见，因为它生成这些递归下降例程，而大多数生成的解析器使用表驱动方法。Parsley 充分利用这种基于例程的方法，让您可以做一些使用表驱动解析器不易完成的事情，例如完全接管解析。理解它们如何构建的基础知识在这里至关重要，但非常容易学习。你们中的许多人可能在某个时候编写过一个，因为它是解析某物最直观的逻辑方式。
您应该已经使用过解析器生成器，才能完全理解本文，但我会尽量使文章中需要它们的部分不必要理解整体。尽可能地吸收。
还建议您理解Slang，即我用于代码生成的 CodeDOM 兼容 C# 子集，因为 Parsley 使用它，您在语法中使用它，而且 Parsley 最初存在的原因就是为了替换 Slang 当前有点可疑的手写解析器，该解析器难以维护且错误报告糟糕。Parsley 的构建旨在帮助缓解这些问题。
构建这个大杂烩
Parsley 作为我更大的构建包——一套用于构建工具的工具——的一部分提供。它使用自身来构建自身，这意味着您需要以发布模式构建它两次，才能解决锁定错误，然后才能运行所有内容。如果您不这样做，您的解决方案将无法构建。
概念化这个混乱的局面
我们在这里处理两个主要事情，语法本身，以及由此生成的代码。
如果需要，我们使用生成的代码进行调试。在生成的解析器代码中设置断点很容易，因为尽管代码量很大，但它都经过了精巧的模块化。每个非终结符生成/解析构造都有自己的函数，所有生成的函数都以两种方式之一工作，具体取决于它们是否回溯。然而，两者都易于理解，尽管有两种不同的实现，但它们的接口完全相同。
高级 Parsley 复习
每个解析函数都以其所代表的非终结符生产规则命名。终结符没有或不需要解析函数。每个解析函数的签名如下：`ParseNode ParseXXXX(ParserContext context)`，其中 `XXXX` 是您的非终结符生产规则/解析构造的名称。这在我们将使用非终结符生产规则上的 `virtual` 特性接管解析的区域尤为重要，因为我们委托给这些函数。否则，对于无代码解析操作——希望它们中的大多数！——您不需要担心这些。
在语法中使用特殊虚拟非终结符生产规则时，您会这样声明它们：
MyNonTerminal<firsts="MyFirst1 myFirst2 ..."> { // code here } : where { // code here }
您不总是需要 `where` 子句，但在大多数情况下您确实需要声明 `firsts`，以便解析器能够找到您的生产。`firsts` 由以空格分隔的语法符号（可以是终结符或非终结符）列表组成，这些符号可以出现在您的生产的开始处。没有它，解析器将不知道如何评估您的虚拟构造，并且永远不会调用它。在极少数情况下，这没关系，因为您可能只从代码中调用它的其他虚拟中使用此虚拟。然而，如果语法要“看到”它，您需要声明您的 `firsts`。这构成了绝大多数情况。如果这不清楚，请不要担心，因为我们稍后将通过实际代码来解决它。
我上面注意到解析例程的签名是 `ParseNode ParseXXXX(ParserContext context)`，其中 `XXXX` 是生产的名称。您将在虚拟生产中自行实现此功能。看到 `context` 参数和 `ParseNode` 返回值了吗？谢天谢地，这没什么好担心的。这构成了您在每个虚拟解析函数中的基本“API”。您有责任使用 `context` 和可用的 `ParseXXXX()` 函数来解析您的标记并从中返回一个 `ParseNode`，自行处理所有错误，并处理输入中出现的终结符。这在上面链接的 Parsley 文章中已涵盖，因此如需进一步阅读，请参阅该文章的末尾以进行复习。
关于使用 `where`：`where` 有两个作用；它允许您覆盖语法中的冲突并为您的生成指定自己的窄化约束。您的职责是使用 `context` 检查输入，并返回一个布尔值，指示您的生成是否通过/合格/将被评估。如果您简单地从一个常规的非虚拟生成中返回 `true`，它将启用自动回溯，我们最终会介绍。在之前的 Parsley 文章中，我们讨论了使用 `where` 来区分标识符和关键字。在 `where` 例程中，请注意 `context` 不会推进主光标，因此您可以在不干扰解析的情况下提前读取。您不能在 `where` 子句中修改真正的 `ParserContext`。请注意，`virtual` 生成不会自动回溯，因为解析方法的整个代码都留给您处理。
Parsley 的新功能
本文提供的更新代码库中使用了一些新功能。我们可以使用 `firsts` 和 `follows` 来操纵解析表，以自定义我们的解析。我们上面简要介绍了 `firsts`，但它可应用于任何非终结符生产，而不仅仅是虚拟。它实际做的是添加到生产中可以作为第一个项出现的现有列表中。除非像上面那样是虚拟生产，否则您通常不需要扩展 `firsts`。然而，每当某物只出现在代码中时，Parsley 就需要一些帮助将其集成到解析中，因为它无法仅凭代码辨别语法。`firsts` 在这里特别方便。
另一个解析表操作属性是 `follows`。`follows` 允许您指定特定生成之后可以出现什么。请注意，这不意味着生成中的最终符号。相反，它意味着任何可以跟随它的东西。解析表需要此信息才能生成代码，并且在几乎所有情况下都会自动从语法中获取，但有时我们可能希望出于自己的目的扩展成员之后可以出现的可能性列表。其中一个目的可能是为子解析器/子语法提供替代的解析终止条件。
NamespaceName<follows="lbrace">= Identifier { "." Identifier };
在这里，我们告诉解析器 `NamespaceName` 后面可以跟着一个左大括号 `{`。原因是在我们的特定情况下，`NamespaceName` 仅在语法中作为 `using` 指令的一部分被调用，因此解析器不知道 `lbrace` 可以跟随它，因为它无法追踪语法来找出。到目前为止，它只知道 `;`，因为它出现在 `UsingDirective` 生产中（此处省略）。另一个调用它的情况是解析 `namespace` 时，它在代码中使用 `virtual` 生产来完成。当在命名空间中使用时，名称后面可以跟着一个左大括号。由于该规则仅在代码中强制执行，我们需要向语法提示它也可以在左大括号处停止。请记住，您可以指定多个以空格分隔的符号，但不能使用字面符号值，例如 `)`。您可能在其他情况下使用此功能，我们稍后将介绍。如果您理解 LL 解析中的 first 和 follows 集合，这很容易理解，但使用它并不要求知道这些。如果您使用已经存在的内容扩展 `firsts` 或 `follows`，它只会产生关于重复规则的警告。
还引入了其他属性，例如 `abstract` 和 `virtual`，但您应该不需要它们。但是，为了清晰起见，可以指定它们。
您可能需要的一个属性是 `dependency`。此属性应应用于只在代码中引用的任何非终结符生成，这样语法就不会将其消除。如果需要对终结符生成执行相同的操作，请设置 `terminal` 属性。
您会发现需要为生成添加 `follows` 的方法之一是使用调试器。当它出现语法错误时，找到引发 `context.Error()` 的方法，并找出预期的符号列表——它将通过 `if` 块中的各种比较显示出来。其中一个 `if` 块可能应该返回一个其子节点为 `new ParseNode[0]` 的节点——至少如果它是一个右结合列表的一部分，通常如此。您需要在此 `if` 中为比较添加一个值。您可以通过查找（如果需要，使用调用堆栈）语法中最近的非终结符生成来完成此操作，就像上面一样，我们将爬过已分解的非终结符堆栈，直到在调用堆栈中找到 `ParseNamespaceName()`。然后我们要将 `lbrace` 添加到 `follows` 集合中以将该 if 条件放置在那里，这就是我们所做的，然后，您的解析就完成了。
有解析器和生成器经验的人可能会想知道我们为什么需要给语法所有这些提示。原因在于 `virtual` 生成和 `@import` 的子解析器。解析器无法在不将其所有规则添加到主语法的情况下跟踪其他解析器的语法，这可能会产生冲突并最终违背子解析器的目的。解析器也无法跟踪代码，因此它不知道您的虚拟生成中的代码如何使用其他解析函数（本质上是其他生成）。因此，当您需要使用这些功能时，有时需要给 Parsley 提供一点帮助。
大型语法如何有效使用 Parsley
对于大型、与语言无关的语法，Parsley 不够快，无法实现。从一种编程语言翻译到另一种语言所需的时间实在太多。然而，在 C# 专用模式下，使用 `/fast` 选项，Parsley 足够快。强烈建议您在处理大型语法时使用此选项。
`/fast` 选项开启的另一个功能是能够将局部类与解析器一起使用。这意味着您可以将几乎所有代码从语法中移出，放入一个常规的 C# 局部类文件中，该文件是解析器类的别名。
在处理大量代码时，您确实应该这样做。Slang 仍然是实验性的，错误报告也比较粗糙——这也是我在这里制作新解析器的原因之一！将其保留在一个局部类中，类似于在 ASP.NET 中使用“代码隐藏”文件，可以帮助您将主要代码保存在一个单独的文件中，这才是它真正应该去的地方，使语法更清晰，代码更易于调试。此外，您还可以通过这种方式在 Visual Studio 中获得 Intellisense（或 MonoDevelop 中的等效功能）。
由于使用了宏（需要后处理），这种技术不适用于生成 `Evaluate()` 方法的语法导向操作。在未来的版本中，我将允许语法导向操作的代码隐藏，但它不会提供宏支持。
即使是小型语法，也使用 `/fast` 进行原型设计也不是一个坏主意，因为这样可以缩短构建时间。
请注意，当使用 `/fast` 时，最好（但非必需）将 Gplex 词法分析器（`/gplex` 选项）与 Parsley 一起使用。这可以在牺牲少量性能和语言独立性的情况下，实现更快的生成和更多功能。您通常会需要额外的功能，特别是 Unicode 支持，而且 Parsley 中 rolex 词法分析器规范的生成目前尚未更新到最新功能。
同时使用 `/fast` 和 `/gplex` 应该会将您的构建时间缩短到一个非常合理的程度，即使对于非常大的语法也是如此，但您的代码只能是 C#。
关于大型语法的另一个问题是，将其分解为子解析器/子语法可能更容易构建。它们与常规解析器和语法完全相同，但有两点不同：它们的起始生产规则有一个 `follows` 属性，用于指定其可选的终止条件（如果需要，通常是流的末尾），并且顶层公共解析方法的实现略有不同，因为它会检查末尾是否有额外的冗余内容，如果发现则抛出异常。这是由于添加了 `follows` 元素，这可能会导致提前终止。
我们在 XBNF 中使用 `@import` 功能来导入子解析器，它只是另一个 XBNF 文件，可能也有自己的导入等等，就像 C++ 头文件一样。每个导入路径都是相对于导入它的文档的。请注意，重复引用同一个文件名是可以的，因为只会加载第一个。URL 也许可以工作，但尚未测试，相对路径不适用于 URL。
@import "SlangExpression.xbnf"
请注意，任何 `\` 字符都必须转义。
`@import` 指令必须出现在任何生产之前。词法分析器顺序由导入顺序决定，因此如果需要某个终结符最后出现，您可能需要在其上使用负数 `priority` 属性。请注意，目前 `ifstale` 存在一个错误（需要实现），它不会跟踪您的导入，因此您必须修改主文件，它才能知道需要重新构建语法。
所有导入的语法加上主语法会创建一个文件，每个语法一个类。所有语法共享同一个词法分析器，它是所有语法中终结符的组合。所有语法共享同一个总体符号表。只有当常量在语法中使用，或者 `abstract` 属性或 `terminal` 属性被设置时，它们才会被添加到类中。只在代码中使用的生产如果需要为该解析器类创建常量，则必须使用上述之一进行提示。请注意，您不能在不同的语法中声明重复的生产，因此只有一个语法可以控制特定终结符或非终结符生产的属性。这带来的一个缺点是，在语法代码中有时您无法提取常量，因为终结符在另一个语法中定义，但您没有在您的语法中使用该终结符，只在代码中使用。在这种情况下，当您在代码中使用它时，您必须引用另一个解析器类（由另一个语法创建）中的常量。抱歉。我知道这有点烦人，但我还没有找到除了跟踪代码或将所有常量转储到每个解析器类之外的解决方案，但这在语法很大时会创建巨大的类，所以我决定不这样做。
每个语法都有自己的解析器，有自己的生产规则和规则。这意味着每个语法对其他语法来说都是一个黑箱。好处是，两个解析器可以有相似的规则而不会冲突。这对于隔离 C# 表达式和 C# 语句（它们在解析器看来有时非常相似）非常有帮助。这就是 Parsley 的组合解析功能。您不能指定导入解析器的类名。它总是通过获取语法中 `start` 生产的名称来派生。请记住，尽管它们是具有不同“解析表”的不同解析器，但解析器共享相同的符号表和词法分析器/标记器。
为了解析 Slang，我们将结合使用这些特性，将语言转换为解析树。我们将在下一节中最终探讨这一点。
使用这个烂摊子
首先，让我们解析一些表达式！
// Slang.xbnf
// This is the XBNF spec for Slang Expressions (gplex version - unicode enabled)
// Slang is a CodeDOM compliant subset of C#
// Expressions
Expression<start, follows="semi rparen rbracket comma">=AssignExpression;
RelationalExpression = TermExpression { ("<"|"<="|">"|">=") TermExpression };
EqualityExpression = RelationalExpression { ("=="|"!=") RelationalExpression };
BitwiseAndExpression = EqualityExpression { "&" EqualityExpression };
BitwiseOrExpression = BitwiseAndExpression { "|" BitwiseAndExpression };
AndExpression= BitwiseOrExpression { "&&" BitwiseOrExpression };
OrExpression= AndExpression { "||" AndExpression };
AssignExpression= OrExpression { ("="|"+="|"-="|"*="|"/="|"%="|"&="|"|=") OrExpression };
TermExpression= FactorExpression { ("+"|"-") FactorExpression };
FactorExpression= UnaryExpression { ("*"|"/"|"%") UnaryExpression };
MemberFieldRef = "." Identifier;
MemberInvokeRef = "(" [ MethodArg { "," MethodArg } ] ")";
MemberIndexerRef = "[" Expression { "," Expression } "]";
MemberAnyRef<collapsed> = MemberFieldRef | MemberInvokeRef | MemberIndexerRef ;
MethodArg = [ outKeyword | refKeyword ] Expression;
TypeRef = Type;
IntrinsicType= boolType |
charType |
stringType |
floatType |
doubleType |
decimalType |
sbyteType |
byteType |
shortType |
ushortType |
intType |
uintType |
longType |
ulongType |
objectType ;
TypeBase = (identifier { "." identifier }) | IntrinsicType;
// the first follows is for fields and methods, second two
// are for base types and custom attributes, respectively
Type<follows="Identifier lbrace rbracket">=TypeElement { TypeArraySpec };
TypeElement = TypeBase [ TypeGenericPart ];
TypeGenericPart= "<" [ Type { "," Type } ] ">";
TypeArraySpec= "[" { TypeArraySpecRank } "]";
TypeArraySpecRank = comma;
// parse casts manually because they're weird. it's just easier
CastExpression<virtual, firsts="lparen"> {
return _ParseCastExpression(context);
}
// much easier to code this as a virtual and parse manually
ArraySpec<virtual,firsts="lbracket"> {
return _ParseArraySpec(context);
}
NewExpression= newKeyword TypeElement ( NewObjectPart | NewArrayPart );
NewObjectPart<collapsed>= "(" [ Expression { "," Expression } ] ")";
NewArrayPart<collapsed>= ArraySpec;
// this is necessary so we can get Parsley to generate a
// method called ParseTypeCastExpressionPart() which we use
// when resolving casts
TypeCastExpressionPart<dependency, collapsed>= Type ")";
ArraySpecExpressionList<dependency ,collapsed>= Expression { "," Expression } "]";
ArrayInitializer<dependency>= "=" "{" [ Expression { "," Expression } ] "}";
SubExpression<collapsed> = "(" Expression ")" : where { return !_IsCastExpression(context);}
// use the where clause to override first first conflict.
UnaryExpression= ("+"|"-"|"!") UnaryExpression | ("++"|"--") PrimaryExpression |
SubExpression | PrimaryExpression : where { return true;}
FieldRef<dependency>= Identifier { MemberAnyRef };
// This is a virtual but here's the basic description
//TypeOrFieldRef = ( Identifier | IntrinsicType )
//{ MemberAnyRef } | (TypeRef) {MemberAnyRef}+ : where {return true;}
TypeOrFieldRef<virtual,firsts="Identifier IntrinsicType">
{ return _ParseTypeOrFieldRef(context); }
PrimaryExpression=
TypeOrFieldRef { MemberAnyRef } |
verbatimStringLiteral { MemberAnyRef } |
characterLiteral { MemberAnyRef } |
integerLiteral { MemberAnyRef } |
floatLiteral { MemberAnyRef } |
stringLiteral { MemberAnyRef } |
boolLiteral { MemberAnyRef } |
nullLiteral |
CastExpression |
typeOf "(" Type ")" { MemberAnyRef } |
nameOf "(" Identifier ")" { MemberAnyRef } |
defaultOf "(" Type ")" { MemberAnyRef } |
NewExpression { MemberAnyRef } |
thisRef { MemberAnyRef } |
baseRef { MemberAnyRef } ;
// Identifier exists as a non-terminal solely to attach a semantic predicate to identifiers.
// we collapse it because we don't need it in the final parse tree but in the grammar
// we have to refer to "Identifier" instead of identifier or verbatimIdentifer to apply
// this constraint.
Identifier<collapsed> = verbatimIdentifier |
identifier : where { return !Keywords.Contains(context.Value); }
// be careful about the order of the terminals.
// remember they have priorities in the final lexer
verbatimIdentifier='@(_|[[:IsLetter:]])(_|[[:IsLetterOrDigit:]])*';
// begin keywords
outKeyword="out";
refKeyword="ref";
typeOf="typeof";
nameOf="nameOf";
defaultOf="default";
newKeyword="new";
stringType="string";
boolType="bool";
charType="char";
floatType="float";
doubleType="double";
decimalType="decimal";
sbyteType="sbyte";
byteType="byte";
shortType="short";
ushortType="ushort";
intType="int";
uintType="uint";
longType="long";
ulongType="ulong";
objectType="object";
boolLiteral = "true|false";
nullLiteral = "null";
thisRef = "this";
baseRef = "base";
verbatimStringLiteral='@"([^"|""])*"';
// bury this
identifier<priority=-100>='(_|[[:IsLetter:]])(_|[[:IsLetterOrDigit:]])*';
stringLiteral='"([^\\"\'\a\b\f\n\r\t\v\0]|\\[^\r\n]|
\\[0-7]{3}|\\x[0-9A-Fa-f]{2}|\\u[0-9A-Fa-f]{4}|\\U[0-9A-Fa-f]{8})*"';
characterLiteral='[\u0027]([^\\"\'\a\b\f\n\r\t\v\0]|\\[^\r\n]|\\[0-7]{3}|\\
x[0-9A-Fa-f]{2}|\\u[0-9A-Fa-f]{4}|\\U[0-9A-Fa-f]{8})[\u0027]';
lte="<=";
lt="<";
gte=">=";
gt=">";
eqEq="==";
notEq="!=";
eq="=";
inc="++";
addAssign="+=";
add="+";
dec="--";
subAssign="-=";
sub="-";
mulAssign="*=";
mul="*";
divAssign="/=";
div="/";
modAssign="%=";
mod="%";
and="&&";
bitwiseAndAssign="&=";
bitwiseAnd="&";
or="||";
bitwiseOrAssign="|=";
bitwiseOr="|";
not="!";
lbracket="[";
rbracket="]";
lparen="(";
rparen=")";
lbrace="{";
rbrace="}";
comma=",";
colonColon="::";
dot=".";
integerLiteral = '(0x[0-9A-Fa-f]{1,16}|([0-9]+))([Uu][Ll]?|[Ll][Uu]?)?';
floatLiteral= '(([0-9]+)(\.[0-9]+)?([Ee][\+\-]?[0-9]+)?[DdMmFf]?)|
((\.[0-9]+)([Ee][\+\-]?[0-9]+)?[DdMmFf]?)';
lineComment<hidden>='\/\/[^\n]*';
blockComment<hidden,blockEnd="*/">="/*";
whitespace<hidden>='[ \t\r\n\v\f]+';
这不算太糟。你可以看到我们有一些 `virtual` 生成，它们转发到这里未显示的方法。它们在“代码隐藏”局部类中。我们还在 `Identifier` 上有一个 `where` 约束，以确保它不是关键字。我们还将 `-100` 分配给了 `identifier` 的 `priority` 属性。这对于确保我们在词法分析器/词法生成器中优先处理关键字很重要。不要将此与 `Identifier` 混淆，`Identifier` 与 `identifier` 不同，是非终结符。
`TypeCastExpressionPart` 有点有趣，因为它是一个 `Type` 后跟一个右括号。我们用它来匹配强制转换的一部分。具体来说，这里加粗的部分：( **string )** foo; 这样做是一个小技巧，告诉解析器 `Type` 后面可以跟一个右括号。另一种方法，会导致稍微不同的行为，是在 `Type` 上指定 `follows="rparen"` 来告诉解析器同样的事情。区别在于前者会“吃掉”右括号，而后者不会。最终，由于它是折叠的，我们如何做并不重要，因为子节点无论如何都会简单地附加到父节点，从而消除这部分，同时保留底层类型和括号。无论哪种方式，一开始都不太直观，但这是任何语法中、对于大多数解析器生成器都会出现的一种模式，所以了解它是如何工作的很重要。大多数解析器生成器要求您以第一种方式进行操作，但 Parsley 也为您提供了第二种方式。我经常在此语法中使用后一种技术，但上述是一个例外。
我们还在 `Unary` 表达式上有一个 `where` 子句，其评估结果为 `true`。因此，我们不会看到它与 `PrimaryExpression` 下方的 `CastExpression` 之间的冲突，否则这些冲突会显现出来，但这确实强制解析器在此处创建回溯代码，即使在这种情况下我们不会使用它——尽管我们在其他情况下确实使用了它。这没关系，因为它实际上不会影响解析。另一个选择是使用 `virtual` 生成自行解析。注意，正如我所说，我们确实会回溯，但稍后当我们检查表达式是否为强制转换时——请参见下文。
我们在 `SubExpression` 上有一个 `where` 子句，这是因为强制转换和括号中的表达式看起来非常相似。例如，`(Foo.Bar)` 可以是带括号的表达式（对 `Foo` 的 `Bar` 成员的引用），也可能是强制转换为 `Foo.Bar` 类型。我们无法确定，除非继续进行并查找紧跟右括号的 `Expression`。这就是 `where` 子句在这种情况下所做的事情。请记住，在 `where` 内部，`context` 永远不会改变主光标，因此我们可以根据需要对其进行解析，而不会影响解析的其余部分。
让我们看看我们委托的一些代码
static bool _IsCastExpression(ParserContext context)
{
context = context.GetLookAhead(true);
try
{
if (lparen != context.SymbolId)
return false;
context.Advance();
ParseNode type = ParseTypeCastExpressionPart(context);
ParseNode expr = ParseUnaryExpression(context);
return true;
}
catch (SyntaxException)
{
}
return false;
}
首先，请注意我们将 `context` 替换为前瞻上下文。只要此方法只在 `where` 子句中调用，我们就不需要这样做。但是，我不想让它变得脆弱，而且创建另一个前瞻光标非常便宜。`Parsley` 是为前瞻设计的。尽可能多地使用它。无论您做什么，回溯都会带来性能上的劣势，因为您会多次检查同一文本。这是算法的性质，但考虑到这个劣势，Parsley 高效地使用该链接中的代码处理前瞻光标本身，而且前瞻的前瞻性能损失可以忽略不计。底线是，这通常是多余的，但没关系。当我们获取前瞻时传递 `true` 只是为了避免调用 `EnsureStarted()`。它只是为我们启动它。
接下来在 try 块中，我们查找一个 `(`，如果找不到，我们立即返回 `false`。之后，我们跳过括号并委托给语法中的 `TypeCastExpressionPart`——我们刚才在上面探讨过它。最后，我们解析我们的表达式，再次委托给语法生成的解析方法。如果两者都没有引发语法错误，那就是一个强制转换。否则，通过排除法，它是一个子表达式。
我们实际上不需要 `type` 或 `expr` 变量，因为它们只是被丢弃了，但我为了清晰起见添加了它们，这样您就可以看到返回值被丢弃了。此方法的作用是，当我们在表达式中遇到 `(` 时，我们可以区分子表达式和类型转换表达式。
同时，`_ParseCastExpression()` 只是做同样的事情，但是构建一个解析节点或根据需要引发错误。
我们遇到了解析诸如 foo**[10][][,,,]** 之类的问题，虽然可以使用语法结构来构建它，但我们遇到了第一个元素的歧义，它可能没有表达式。基本上，语法无法区分 foo**[10][][,,,]**，因为第一个元素可以有表达式但可能没有，而其余元素不能有。因此，我们无法判断第一个元素是否已指定。虽然这应该可以在 LL(1) 中实现——我想——但写一个 `virtual` 生产规则更容易，如下所示
static ParseNode _ParseArraySpec(ParserContext context)
{
int line = context.Line;
int column = context.Column;
long position = context.Position;
if (lbracket!=context.SymbolId)
context.Error("Expecting start of array spec");
ParseNode lb = null;
ParseNode expr = null;
ParseNode init = null;
ParserContext pc = context.GetLookAhead(true);
pc.Advance();
if (rbracket!=context.SymbolId)
{
lb = new ParseNode(lbracket, "lbracket", context.Value,
context.Line, context.Column, context.Position);
context.Advance();
expr = ParseArraySpecExpressionList(context);
return new ParseNode(ArraySpec, "ArraySpec",
new ParseNode[] { expr }, line, column, position);
}
else
{
expr = ParseTypeArraySpec(context);
init = ParseArrayInitializer(context);
return new ParseNode(ArraySpec, "ArraySpec",
new ParseNode[] { expr, init }, line, column, position);
}
}
再一次，我们的许多工作都只是委托给了像 `ArraySpecExpressionList` 这样的现有产品。我们只需要解析不同的部分并将它们组合成一个新的 `ParseNode`。看到我们在这里是如何使用一点点前瞻的吗？那是为了解决我上面提到的歧义。
而所有最糟糕的野兽，是 `TypeOrFieldRef`。这是一个极其模糊的解析，逻辑错综复杂。我不知道如何使任何解析器生成器能够干净地解析它，如果可以的话，但有了 Parsley，我们再次拥有 `virtual` 生产，当我们需要时可以完全控制。基本上，我们必须区分类型引用 `Foo.Bar.Baz
目前，在上面的语法中，我们的起始生成是 `Expression`，它允许您解析表达式。在下一节中，我们将将其用作子解析器，因为我们将向整体语法添加更多内容，但目前，它是顶层的。
你可以这样使用它
var test = "(object)4*(2+1)";
var tokenizer = new SlangTokenizer(test);
_WriteTree(SlangParser.Parse(tokenizer),Console.Out);
这很容易。您会注意到上面的表达式解析成功，即使它不能编译。这没关系，因为解析器的工作不是验证代码的正确性，而是验证语法的正确性。它除了知道 `object` 是一个内置类型之外，一无所知。编译器只会在代码解析后验证此代码。
卷起袖子，我们才刚开始。
这是我们的下一段
// Slang.xbnf
// This is the XBNF spec for Slang Statements (gplex version - unicode enabled)
// Slang is a CodeDOM compliant subset of C#
@import "SlangExpression.xbnf";
// Statements
// must reference a symbol here rather than ";" or XBNF thinks it's a terminal
// TODO: test terminal=false attribute setting in Parsley
EmptyStatement= semi;
VariableDeclarationStatement= (varType | Type) Identifier [ "=" Expression ] ";";
ExpressionStatement=Expression ";" : where { return _WhereExpressionStatement(context); }
// enable automatic backtracking here
VariableDeclarationOrLabelOrExpressionStatement<collapsed>=
VariableDeclarationStatement|
ExpressionStatement |
LabelStatement
: where { return true; }
ElsePart<collapsed> = "else" StatementOrBlock;
IfStatementPart<collapsed>= "if" "(" Expression ")" StatementOrBlock ;
// backtracking seems to be choosing incorrectly on trailing else here
// make it virtual
//IfStatement=IfStatementPart [ ElsePart ]
IfStatement<virtual, firsts="ifKeyword"> { return _ParseIfStatement(context);}
GotoStatement= "goto" identifier ";";
// we already check to disambiguate in ExpressionStatement,
// so all we do here is override the first first conflict
LocalAssignStatement<dependency, collapsed>=ExpressionStatement |
VariableDeclarationStatement : where { return true; }
// for trailing part of for first line:
ForIncPart<dependency, collapsed> = [ Expression ] ")";
// "for" "(" (LocalAssignStatement | EmptyStatement)
// (Expression ";" | EmptyStatement) ForIncPart StatementOrBlock
ForStatement<virtual, firsts="forKeyword"> { return _ParseForStatement(context); }
: where {return true;} // enable automatic backtracking
WhileStatement= "while" "(" Expression ")" StatementOrBlock;
ReturnStatement= "return" Expression ";";
ThrowStatement= "throw" [ Expression ] ";";
TryStatement= "try" StatementBlock ( { CatchClause }+ [ FinallyPart ] | FinallyPart );
CatchClause= "catch" "(" Type [ Identifier ] ")" StatementBlock;
FinallyPart<collapsed> = "finally" StatementBlock;
// look for : to disambiguate between this and a primary expression
LabelStatement= identifier ":" : where {
context.Advance();
return colon==context.SymbolId;
}
StatementOrBlock = (Statement | StatementBlock);
Statement<start>=
EmptyStatement |
VariableDeclarationOrLabelOrExpressionStatement |
IfStatement |
GotoStatement |
ForStatement |
WhileStatement |
ReturnStatement |
GotoStatement |
TryStatement ;
StatementBlock= "{" {Statement} "}";
ifKeyword="if";
gotoKeyword="goto";
elseKeyword="else";
// have to hint forKeyword as terminal because it never appears except
// in code or attributes
forKeyword<terminal>="for";
throwKeyword="throw";
whileKeyword="while";
returnKeyword="return";
tryKeyword="try";
catchKeyword="catch";
finallyKeyword="finally";
semi=";";
varType="var";
colon=":";
directive<hidden,blockEnd="\n">='#[A-Za-z]+';
那可真是个小麻烦，不是吗？幸运的是，我们已经能够在语法中定义它的大部分内容，而不是在代码中。请注意，我们现在使用 `@import` 来导入我们上面构建的表达式语法。
我可能不需要将 `ForStatement` 设为 `virtual`，但这很容易，否则 `for` 语句的语法会因为与局部赋值的冲突而变得复杂。请注意，我们确实定义了 `LocalAssignStatement` 等构造，因为我们可以直接委托给解析器来解析它，而不是自己解析。我们明智地使用解析器的内置函数，例如 `ExpressionStatement`，使解析过程非常简单。
static ParseNode _ParseForStatement(ParserContext context)
{
var line = context.Line;
var column = context.Column;
var position = context.Position;
var children = new List<ParseNode>();
if (forKeyword != context.SymbolId)
context.Error("Expecting for");
children.Add(new ParseNode(forKeyword, "forKeyword", "for",
context.Line, context.Column, context.Position));
context.Advance();
if (lparen != context.SymbolId)
context.Error("Expecting ( in for loop");
children.Add(new ParseNode(lparen, "lparen",
"(", context.Line, context.Column, context.Position));
context.Advance();
if (semi == context.SymbolId)
{
children.AddRange(ParseEmptyStatement(context).Children);
}
else
children.Add(ParseLocalAssignStatement(context));
if (semi == context.SymbolId)
{
children.AddRange(ParseEmptyStatement(context).Children);
}
else
{
children.AddRange(ParseExpressionStatement(context).Children);
}
children.AddRange(ParseForIncPart(context).Children);
children.Add(ParseStatementOrBlock(context));
return new ParseNode(ForStatement, "ForStatement",
children.ToArray(), line, column, position);
}
你可以看到这一切都非常简单，大部分工作都委托给了像 `ParseExpressionStatement()` 这样的生成解析例程。
`LabelStatement` 上的 `where` 条件很简单。它只是查找一个 `identifier`（不是 `Identifier`，`Identifier` 会包含像 `@namespace` 这样的东西），后面跟着“`:`”，以便区分——用我们的前瞻功能很容易实现。
`ExpressionStatement` 稍微复杂一点，因为我们必须确保不要将其与 `VariableDeclarationStatement` 混淆，`VariableDeclarationStatement` 在开头可能看起来与表达式相似。
现在事情变得棘手起来，好在 Parsley 的设计允许混入手写代码，我们将在下一节中更多地使用它。
C# 和 Slang 中的类型和成员非常模糊。您可能首先有自定义属性，然后是成员属性，最后是可能是字段、属性、构造函数、方法或嵌套类型的东西。当您弄清楚它是什么时，您已经深入解析。我们自己接管成员解析。我们也接管了大部分类型声明解析，因为它也变得模糊，特别是涉及到前导自定义属性时。应该指出的是，像 ANTLR 这样的 LL(k) 解析器应该能够解决这个问题，而不需要太多处理，但 Parsley 是 LL(1)。我最终会将其变成 LL(k) 甚至 LL(*)，但我还不知道如何实现。
@import "SlangStatement.xbnf";
@import "SlangExpression.xbnf";
// Custom Attributes
CustomAttribute= TypeBase [ "(" [ CustomAttributeArgList ] ")"];
//CustomAttributeArgList<virtual, firsts="Identifier Expression">
//{ return _ParseCustomAttributeArgList(context); }
CustomAttributeArgList = CustomAttributeArg { "," CustomAttributeArg };
CustomAttributeArg = Identifier "=" Expression | Expression : where { return true; }
CustomAttributeTarget= (assemblyKeyword | returnKeyword) ":";
CustomAttributeGroup<follows="Member TypeDecl">=
"[" [ CustomAttributeTarget ] CustomAttribute { "," CustomAttribute } "]";
CustomAttributeGroups<dependency,
follows="Member TypeDecl Identifier namespaceKeyword">= { CustomAttributeGroup }+;
// Types
// since it's only used in code, we need to give it follows
TypeAttributes<follows="classKeyword enumKeyword structKeyword
interfaceKeyword partialKeyword">= { publicKeyword | internalKeyword | privateKeyword };
EnumPart<collapsed> = "{" EnumFields "}" | ":" Type "{" EnumFields "}";
EnumFields<collapsed>= [ EnumField { "," EnumField } ];
EnumField= Identifier "=" Expression ;
Where<dependency,follows="lbrace">= "where" WhereClauses;
WhereClauses<dependency,virtual,firsts="Identifier"> { return _ParseWhereClauses(context);}
: where { return !ExpressionParser.Keywords.Contains(context.Value); }
WhereClause<dependency,follows="lbrace">=
Identifier ":" WhereClausePart { "," WhereClausePart };
WhereClausePart= (Type | newKeyword "(" ")" );
BaseType<dependency,collapsed,follows="comma whereKeyword lbrace">= Type;
BaseTypes<abstract>;
TypeDeclPart<virtual,firsts="colon whereKeyword lbrace", follows="rbrace">
{ return _ParseTypeDeclPart(context);}
TypeParams<follows="colon whereKeyword lbrace"> =
[ "<" [ CustomAttributeGroup ] Identifier { "," Identifier } ">" ];
// we narrow the attributes this accepts as a base in our parse routine for parse member
// TODO: do it for non-nested types
Enum<dependency>= MemberAttributes "enum" Identifier EnumPart;
Struct<dependency>= MemberAttributes "struct" Identifier TypeParams TypeDeclPart;
Class<dependency>= MemberAttributes "class" Identifier TypeParams TypeDeclPart;
Interface<dependency>= MemberAttributes "interface" Identifier
[ "<" TypeParams ">" ] TypeDeclPart;
TypeDecl<start,virtual,follows="TypeDecl usingKeyword namespaceKeyword rbrace lbracket",
firsts="TypeAttributes structKeyword classKeyword enumKeyword
interfaceKeyword partialKeyword lbracket"> { return _ParseTypeDecl
(context,false,null,context.Line,context.Column,context.Position,null); }
// Members
MemberAttribute<collapsed>= newKeyword | constKeyword | publicKeyword |
protectedKeyword | internalKeyword | privateKeyword | staticKeyword | overrideKeyword;
MemberAttributes<dependency> = { MemberAttribute };
// private implementation types are really difficult to parse so we use a virtual
// for it. The trouble is in the ambiguity because the type leads the identifier, so
// it's hard to know where the type ends and the identifier begins.
// note that we restrict the Identifier below,
// by copying it's where clause.
PrivateImplementationType<virtual,firsts="Identifier">
{ return _ParsePrivateImplementationType(context); }
: where { return !ExpressionParser.Keywords.Contains(context.Value); }
// need the follows because it's only referenced by code
// the grammar can't trace it
MethodParamList<dependency,follows="rparen">= [ MethodParam { "," MethodParam } ];
MethodParam= [ outKeyword | refKeyword ] Type Identifier;
ParamList<dependency>= [ Param { "," Param } ];
Param= Type Identifier;
// property accessors are weird for the parser because one
// can be optional, but only one of each may be specified
// and in any order. This is easier with a virtual
PropertyAccessors<virtual,firsts="PropertyGet PropertySet">
{ return _ParsePropertyAccessors(context); }
PropertyGet<dependency>= "get" ( StatementBlock | ";" );
PropertySet<dependency>= "set" ( StatementBlock | ";" );
ConstructorChain = ( "base" | "this" ) "(" ParamList ")";
// below we add rbrace to the follows sets for each to
// production below to allow member decls to be inside a
// { } block (for type decls)
Constructor<abstract>;
Method<abstract>;
Property<abstract>;
Event<abstract>;
Field<abstract>;
// methods/properties and fields are also tough to disambiguate.
// we could have used automatic backtracking for below but the error reporting
// is just bad with it right now. Better to write a bunch of code because the
// errors in the code inside methods and such were bubbling up here and
// interfering with error reporting
Member<virtual,follows="rbrace",
firsts="lbracket MemberAttributes Type eventKeyword Identifier">
{
return _ParseMember(context);
} : where { return true; } // ignore conflicts here. handled by the routine
Members<virtual,firsts="Member"> { return _ParseMembers(context); }
: where { return true; } // method handles first-first conflicts
assemblyKeyword="assembly"; // for assembly targets
voidType<terminal>="void"; // basically for methods
partialKeyword="partial";
classKeyword="class";
enumKeyword="enum";
structKeyword="struct";
interfaceKeyword="interface";
getKeyword="get";
setKeyword="set";
eventKeyword="event";
publicKeyword="public";
privateKeyword="private";
protectedKeyword="protected";
internalKeyword="internal";
staticKeyword="static";
// specify terminal here since this is only reference in code
// we need to make sure it generates a constant
abstractKeyword<terminal>="abstract";
constKeyword="const";
overrideKeyword="override";
whereKeyword="where";
我不是警告过你吗？我们在这里大量委托给方法。生成的代码太含糊，无法处理干净。解析诸如私有实现类型（`IEnumerator **IEnumerable.**GetEnumerator()`）之类的事情对于解析器来说真的很难处理。此外，属性访问器很复杂，因为它们可以以任何顺序出现，并且每种类型最多只能有一个。这很难在语法中描述。这是可以做到的，但这会迫使你写出所有可能的情况。请注意，我们有一些抽象的非终结符生成。我们将需要它们创建的常量来构建解析节点。
私有实现类型是解析起来比较棘手的一种，它使用我作为最后手段采用的技术。
static ParseNode _ParsePrivateImplementationType(ParserContext context)
{
var l = context.Line;
var c = context.Column;
var p = context.Position;
var pc2 = context.GetLookAhead(true);
// here's a trick. We're going to capture a subset of tokens and then
// create a new ParserContext, feeding it our subset.
var toks = new List<Token>();
while (EosSymbol != pc2.SymbolId &&
(identifier2 == pc2.SymbolId ||
verbatimIdentifier == pc2.SymbolId ||
ExpressionParser.dot == pc2.SymbolId))
{
toks.Add(pc2.Current);
pc2.Advance();
}
if (EosSymbol == pc2.SymbolId)
pc2.Error("Unexpected end of file parsing private implementation type");
if (2 < toks.Count)
{
// remove the last two tokens
toks.RemoveAt(toks.Count - 1);
toks.RemoveAt(toks.Count - 1);
// now manufacture a comma token
// to get ParseType to terminate
var t = default(Token);
t.SymbolId = comma;
t.Value = ",";
t.Line = pc2.Line;
t.Column = pc2.Column;
t.Position = pc2.Position;
toks.Add(t);
var pc3 = new ParserContext(toks);
pc3.EnsureStarted();
var type = ExpressionParser.ParseType(pc3);
// advance an extra position to clear the trailing ".", which we discard
var adv = -1;
while (adv < toks.Count)
{
context.Advance();
++adv;
}
return new ParseNode(PrivateImplementationType,
"PrivateImplementationType", new ParseNode[] { type }, l, c, p);
}
return new ParseNode(PrivateImplementationType,
"PrivateImplementationType", new ParseNode[0], l, c, p);
}
请记住，`ParserContext` 驱动一个实现 `IEnumerable
我不会包含 `ParseMember()`，因为它很长，但主要原因，以及此生成最初具有虚拟性的原因，是错误处理。成员声明有许多在语法中不易指定的约束。例如，`Abstract` 告诉我们一个方法不能有方法体。此外，语句中的错误会冒泡并变得混乱，所以现在这样更好。
最后，我们有了顶级语法，它再次大量委托给代码，这次是为了解决歧义问题。
@import "SlangExpression.xbnf";
@import "SlangStatement.xbnf";
@import "SlangType.xbnf";
NamespaceName<follows="lbrace">= Identifier { "." Identifier };
UsingDirective= "using" NamespaceName ";";
// this is what we want, but it's really ambiguous
// so use a virtual
// CompileUnit<start> = { UsingDirective } { Namespace | TypeDecl }
CompileUnit<start,virtual> { return _ParseCompileUnit(context); }
// this is what we want but it's a lot of
// work so we make it virtual instead
// Namespace= "namespace" NamespaceName "{" {UsingDirective } {TypeDecl} "}"
// rbrace is enforced in code but we specify it here for readability
Namespace<virtual,firsts="namespaceKeyword", follows="rbrace">
{ return _ParseNamespace(context);}
// make sure this gets a constant as it's only used in code
namespaceKeyword<terminal>= "namespace";
usingKeyword= "using";
这其实解析起来不算太糟糕，只是对于 LL(1) 来说有点困难，所以这就是虚拟生成和委托给生成方法的真正闪光点所在。
static ParseNode _ParseNamespace(ParserContext context)
{
var line = context.Line;
var column = context.Column;
var position = context.Position;
var children = new List<ParseNode>();
if (namespaceKeyword != context.SymbolId)
context.Error("Expecting namespace");
children.Add(new ParseNode(namespaceKeyword, "namespaceKeyword",
context.Value, context.Column, context.Line, context.Position));
context.Advance();
children.Add(ParseNamespaceName(context));
if (lbrace != context.SymbolId)
context.Error("Expecting { in namespace declaration");
context.Advance();
while (usingKeyword == context.SymbolId)
{
children.Add(ParseUsingDirective(context));
}
while (EosSymbol != context.SymbolId && ExpressionParser.rbrace != context.SymbolId)
{
children.Add(TypeDeclParser.ParseTypeDecl(context));
}
if (rbrace != context.SymbolId)
context.Error("Expecting } in namespace declaration");
context.Advance();
return new ParseNode(Namespace, "Namespace", children.ToArray(), line, column, position);
}
一切都非常直接。请注意，我们不允许此处存在嵌套命名空间。这是故意的，因为 CodeDOM 不支持它们。
现在让我们来使用它。演示程序只是解析自身并将结果转储到屏幕上。
stm = File.OpenRead(@"..\..\Program.cs");
var tokenizer = new SlangTokenizer(stm);
var pt = SlangParser.Parse(tokenizer);
_WriteTree(pt, Console.Out);
这将在你的控制台窗口中吐出一团糟，代表解析树。
现在我们可以解析 95% 的 Slang。剩下的是注释和指令，我们将在下一篇文章中介绍。
在后续文章中，我们将使用 Parsley 将解析树渲染为 CodeDOM 抽象语法树。
历史
- 2019年12月31日：首次提交
- 2020年1月1日：更新