Parsley: C# 中的递归下降解析器生成器
4.88/5 (20投票s)
使用友好的语法格式在大多数主要 .NET 语言中生成功能强大、可维护的解析器
引言
.NET 有很多解析器生成器，但没有语言无关的解析器，它**带有**语法导向操作（语法中的代码）、语法谓词和自定义解析例程。Parsley 与众不同。Parsley 允许您以 C# 子集的形式编写语法中的代码，然后将其转换为目标解析器生成的语言，因此如果有人想在 VB 中使用您的解析器源代码，他们也可以使用，即使您的代码是 C#。市面上也很少有递归下降解析器生成器，大多数都偏爱表格生成方法。递归下降的优点是它比表格驱动方法更直观，并且解析例程完全可重写——而且代码是可读的。这个生成器有点像 **Coco/R**，它内部是 LL(1)，但允许您使用代码来解析比 LL(1) 更复杂的结构。我没有真正使用过 **Coco/R**，但我认为它是表格驱动的，不像 **Parsley**，**Parsley** 因此具有更多的代码功能，例如用于完全覆盖解析的虚拟非终结符。我不能确定 **Coco/R** 不做这些事情，但我相当确定。如果我是对的，**Parsley** 潜在地可以用比 **Coco/R** 更多的方式解析更多的语法。
更新： 改进了输出代码生成，增加了功能。见下文。
更新 2：语法中的错误修复，部分文章重写，功能添加
更新 3：添加了 GPLEXv1 支持！
更新 4：添加了实验性回溯支持
更新 5：添加了语法谓词、虚拟和抽象非终结符，以及 /fast 选项
更新 6： 添加了 @options 指令和 ParsleyDevstudio Visual Studio 集成包，适用于 Parsley、Rolex 和 Gplex
版权/许可声明：
虽然这里的大部分代码都是我的，但 GPLEXv1 不是我的项目，我还没有真正分叉它（我还没有修改源代码），但我可能会这样做，因为它没有得到维护。第一次构建也很困难，因为您需要 **gplex** 和 **gppg** 二进制文件才能第一次构建它，而且这些二进制文件可能很难找到。我还计划将其用于 Slang，因为它支持 Unicode，而 Rolex 不支持。我已将其包含在内，以即用型形式，只是为了让您我的生活更轻松。
Gardens Point LEX 版权所有 © 2006-2011 昆士兰科技大学 (QUT)。保留所有权利。
完整许可证包含在 *Gplex* 文件夹中的 *GPLEXcopyright.rtf* 中。
背景
解析器生成器构建解析器，将文本分解为有意义的符号层次结构，可以通过编程轻松处理。编译器使用解析器来解析您的代码。JSON 库使用解析器来解析 JSON，Excel 使用解析器来解码单元格中的公式。
解析器有各种算法，从简单的 LL(1) 到几乎难以理解的 GLR 解析算法。Parsley 是 LL(1)，这意味着它从上到下处理语法，创建左推导树和一个符号的先行。语法而不是输入指导解析。这是仅次于 LL(k/*) 的第二种最直观的解析方式，LL(k/*) 允许任意先行。
使用这个烂摊子
构建这个大杂烩
此代码作为我的大型 **构建工具** 项目的一部分提供。我已从发行版中剥离了二进制文件，但它们仍用于构建发行版。要引导它，您必须在 *Release* 中构建几次。第一次您会遇到锁定错误。没关系。第二次，您的错误面板中可能仍然有警告，但它已过时。构建成功，没有警告。
安装这个烂摊子
此发行版中包含的所有工具都有其自身的用处。您可能希望将 **deslang**、**csbrick**、**rolex** 和 **parsley** 复制到您的 `PATH` 某个位置。这使得在预构建步骤中使用它们变得更容易，因为您无需完全限定 EXE 路径。您可以运行 ParsleyDevstudio.vsix 安装程序来安装 Visual Studio 集成，尽管它不如将此作为预构建步骤的标准方式。
运行这个烂摊子
Parsley 通常作为命令行工具运行。它接受一个输入文件、一个可选的输出文件和各种参数，这些参数指定生成的代码选项。这是使用屏幕
Parsley generates a recursive descent parser and optional lexer spec
parsley.exe <inputfile> [/output <outputfile>] [/rolex <rolexfile>]
[/gplex <gplexfile>] [/gplexclass <gplexcodeclass>]
[/namespace <codenamespace>] [/class <codeclass>]
[/langage <codelanguage>] [/fast]
[/noshared] [/verbose] [/ifstale]
<inputfile> The XBNF input file to use.
<outputfile> The output file to use - default stdout.
<rolexfile> Output a Rolex lexer specification to the specified file
<gplexfile> Generate Gplex lexer specification to the specified file file. Will also generate supporting C# files (C# only)
<gplexcodeclass> Generate Gplex lexer specification with the specified class name. - default takes the name from <gplexfile>
<codenamespace> Generate code under the specified namespace - default none
<codeclass> Generate code with the specified class name - default derived from <outputfile> or the grammar.
<codelanguage> Generate code in the specified language - default derived from <outputfile> or C#.
<fast> Generate code quickly, without resolution using C# only - not valid with the <codelanguage> option.
<noshared> Do not include shared library prerequisites
<verbose> Output all messages from the generation process
<ifstale> Do not generate unless <outputfile> or <rolexfile> is older than <inputfile>.
Any other switch displays this screen and exits.
（抱歉，文本换行了！）
inputfile是将生成解析器的 XBNF 规范（下面会探讨）outputfile是可选的，指定要生成的输出代码文件。如果未指定，代码将转储到stdout。rolexfile是可选的，指定要生成的 **rolex** 词法分析器规范文件。如果未指定，则不会生成 **rolex** 规范。gplexfile是可选的，指定要生成的 **gplex** 词法分析器规范文件。如果未指定，则不生成。请注意，如果指定，将生成多个文件。这是支持 **gplex** 所必需的。gplexcodeclass是可选的，指定用于生成类的基类名称。"Expression" 将创建ExpressionTokenizer、ExpressionTokenizerEnumerator和ExpressionScanner。codenamespace是生成代码的命名空间。如果未指定，代码将不会在命名空间下生成。codeclass是要使用的解析器类的名称。如果您不指定一个，它将与outputfile相同，除非未指定，在这种情况下它将从 XBNF 语法中的起始元素获取名称。codelanguage是要生成的代码的语言。如果您不指定一个，它将基于outputfile的文件扩展名。如果未指定outputfile，它将默认为 C#。fast表示代码生成应跳过解析步骤，直接以 C# 发出。在指定codelanguage时，此选项无效。noshared跳过生成共享代码。这对于在同一项目中生成第二个解析器很重要。第一个解析器应该在没有此开关的情况下生成，后续解析器应该在此开关的情况下生成。如果在此处指定了 noshared，则在使用 **rolex** 生成词法分析器/标记器代码时，也应该将其指定给 **rolex**。您不希望源中有重复的共享代码，因为它会导致编译错误。此选项也适用于 **Gplex** 生成。verbose发出所有语法转换和验证消息，包括有关重构规则的消息。在大型语法中，如果重构很多，这会创建巨大的转储，但它允许您查看所做的更改。无论如何，您也可以在生成的代码的文档注释中看到更改。ifstale跳过生成输出，除非输入已修改。这对于预构建步骤很有用，因为它可以防止每次重建解析器带来的开销。
您可能希望将此工具与解决方案中包含的标记器之一结合使用。**Rolex** 最易于使用，但 **Gplex** 支持 Unicode，并且功能更强大。这些工具是词法分析器/标记器生成器。几乎所有解析器（特别是 PEG 解析器除外）都需要词法分析器/标记器，**Parsley** 也不例外。有关 **Rolex** 的更多阅读，我写了一篇关于此处创建 Rolex 的文章，尽管您应该使用此代码库，因为它更新得多，并且使用Deslanged Slang 技术大大简化了生成代码的维护，同时保持了性能。有关 **Gplex** 的更多阅读，我只会查看 **lex** 和 **flex** 资源，因为 **Gplex** 本身几乎没有文档，但它与这些工具相似。幸运的是，我已在 Parsley 中包含了生成与 **Rolex** 词法分析器几乎相同的接口，因此针对它们进行编码基本相同。构造函数略有不同。最终我会将它们统一起来，但这并非易事，因为 **Gplex** 的工作方式。如果您使用 **Gplex**，通常希望将 `fast` 选项与 **Parsley** 一起使用，因为标记器无论如何都是 C#。
编写这个混乱的程序
回到 Parsley，让我们检查一下我所有解析器都使用的 XBNF 语法格式
XBNF 格式旨在让您在了解一点语法组合知识后易于学习。
生产形式为
identifier [ < attributes > ] = expressions ;
我们将稍后讨论上述生产语法的更高级变体。
例如，这是一个简单的符合标准的 JSON 语法
// based on spec @ json.org
Json<start>= Object | Array;
Object= "{" [ Field { "," Field } ] "}";
Field= string ":" Value;
Array= "[" [ Value { "," Value } ] "]";
Value<collapsed>=
string |
number |
Object |
Array |
Boolean |
null ;
Boolean= true|false;
number= '\-?(0|[1-9][0-9]*)(\.[0-9]+)?([Ee][\+\-]?[0-9]+)?';
string= '"([^\n"\\]|\\([btrnf"\\/]|(u[0-9A-Fa-f]{4})))*"';
true= "true";
false= "false";
null= "null";
lbracket<collapsed>= "[";
rbracket<collapsed>= "]";
lbrace<collapsed>= "{";
rbrace<collapsed>= "}";
colon<collapsed>= ":";
comma<collapsed>= ",";
whitespace<hidden>= '[\n\r\t ]+';
首先要注意的是，`Json` 生产被标记为 `start` 属性。由于未指定值，因此它隐式为 `start=true`。
这告诉解析器 `Json` 是起始生产。如果未指定，将使用语法中的第一个非终结符。此外，这可能在生成期间导致警告，因为将其留作隐式不是一个好主意。只有 `start` 的第一个出现才会被接受。
`Object | Array` 告诉我们 `Json` 生产被派生为对象或数组。`Object` 生产包含一个重复 `{} `构造，以及一个可选的 `[]` 构造，它本身包含对 `Field` 的引用。`Array` 类似，只是它使用“`[`”和“`]`”，并且它引用 `Value` 而不是 `Field`。
表达式
- `( )` 括号允许您创建子表达式，例如 `Foo (Bar|Baz)`
- `[ ]` 可选表达式允许子表达式出现零次或一次
- `{ }` 此重复构造重复子表达式零次或多次
- `{ }+` 此重复构造重复子表达式一次或多次
- `|` 此交替构造派生任何一个子表达式
- 连接是隐式的，用空白分隔
终结符
所有终结符都定义在底部，但它们可以位于文档中的任何位置。XBNF 将任何不引用其他生产的生产视为终结符。您可以使用 `terminal` 属性（见下文）强制一个元素成为终结符。
正则表达式位于 `''` 单引号之间，字面表达式位于 `""` 双引号之间。您可以使用 XBNF 构造或使用正则表达式来声明终结符。正则表达式遵循 POSIX + 标准扩展范例，但目前不支持所有 POSIX。它们支持大部分。如果 POSIX 表达式不起作用，请将其视为一个 bug。Unicode 将在未来版本中得到支持。我已经开始支持 \p 和 \P 等构造，但正则表达式引擎需要进一步优化，**Rolex** 才能在合理的时间内创建该词法分析器。问题在于 Unicode 巨大的字母和数字范围正在扼杀我目前的实现，该实现对范围进行了约 80% 的优化。在这种情况下，另外 20% 正在扼杀性能，但优化它并非易事。
属性
`collapsed` 元素告诉 Parsley 此节点不应出现在解析树中。相反，它的子节点将被传播到其父节点。如果语法需要一个非终结符或终结符来解析一个构造，但这对解析树的消费者没有用，这会很有帮助。在 LL(1) 分解期间，必须创建生成的规则，并且它们的关联非终结符通常会被折叠。上面，我们使用它来显著修剪我们不需要的解析树节点，包括折叠 JSON 语法中不必要的终结符（例如 `:`）。这是因为它们无助于我们定义任何内容——它们只是帮助解析器识别输入，因此我们可以将它们抛出以使解析树更小。
“`hidden`”元素告诉 Parsley 跳过此终结符。这对于注释和空格等内容很有用。
`blockEnd` 属性用于具有多字符结束条件的终结符，例如 C 块注释、XML CDATA 节和 SGML/XML/HTML 注释。如果存在，词法分析器将继续，直到匹配到指定为 `blockEnd` 的字面值。
`terminal` 属性声明一个生产显式为终结符。即使它引用了其他生产，此类生产也被视为终结符。如果它引用了，那些其他生产将以其终结符形式包含在内，就好像它们是原始表达式的一部分一样。这允许您从多个终结符定义创建复合终结符。
`ignoreCase` 属性指定匹配时不应考虑大小写。这仅适用于终结符，并且仅适用于 Rolex。
`type` 属性指定关联**代码块**（见下文）的 .NET 类型或固有 C# 类型。从此类“类型化”非终结符返回的值会自动转换为目标类型，从而无需强制转换返回值，或使用 `int.Parse()` 等进行转换。它将为您处理。
`dependency` 属性将非终结符生成标记为您的解析器代码所需。
`firsts` 和 `follows` 属性是空格分隔的终结符和非终结符符号列表，它们向解析器提示特定非终结符生成中首先出现什么以及可以跟随什么。这些通常与虚拟生成结合使用（请参阅末尾的章节）
`priority` 属性将终结符生产标记为具有特定优先级。负数优先级低于正数。必须是整数。默认情况下，项目的 `priority` 为 0。
评估代码块
评估代码块使用 lambda/匿名方法类似的语法在语法中指定。`=> { ... }` 在非终结符生产的末尾。它们采用以下形式
identifier [ < attributes > ] = expressions => { ... }
例如
Foo = Bar Baz => { // my code } // notice we don't terminate with a semi-colon
这表示要与该非终结符关联的代码块。此代码用于解析动作，由 `EvaluateXXXX()` 方法触发。在此代码中，您获取一个 `ParseNode` 对象（由 `node` 表示）并对其进行评估，返回结果。如果您不返回结果，将返回默认值。请参阅下面的示例。
关于语法表示约定：我在语法中为非终结符使用首字母大写。这不是必需的，但最终会更好，因为像 `ParseXXXX()` 和 `EvaluateXXXX()` 这样的函数直接从非终结符名称中获取 `XXXX` 部分。因此，非终结符 `foo` 最终会生成 `Parsefoo()` 和 `Evaluatefoo()`。这显然是不可取的，但它不是一个障碍。我曾考虑过混淆名称以“纠正”这一点，但最终我决定不对代码进行意外更改。这样，就可以直接知道这些方法的最终名称是什么。符号常量也直接从符号名称生成，因此如果您想与 Microsoft 的命名准则保持一致，您也将您的终结符命名为 Pascal case/.NET case。然而，这远不重要，特别是与非终结符不同，它们的名称不会附加到任何东西上。
让我们看看表达式解析器的语法
Term<start>= Factor { ("+"|"-") Factor };
Factor= Unary { ("*"|"/") Unary };
Unary= ("+"|"-") Unary | Leaf;
Leaf= integer | identifier | "(" Term ")";
// we only need to declare terminals explicitly if we want
// constant names for them or to apply attributes to them
// we don't have to explicitly declare anything but whitespace
// we can define it all inline above but this is nicer
integer='[0-9]+';
identifier='[A-Z_a-z][0-9A-Z_a-z]*';
whitespace<hidden>='\s+';
现在是生成的 `_ParseXXXX()` 方法的工作方式
private static ParseNode _ParseLeaf(ParserContext context) {
int line = context.Line;
int column = context.Column;
long position = context.Position;
if ((ExpressionParser.integer == context.SymbolId)) {
// Leaf -> integer
ParseNode[] children = new ParseNode[1];
children[0] = new ParseNode(ExpressionParser.integer, "integer", context.Value, line, column, position);
context.Advance();
return new ParseNode(ExpressionParser.Leaf, "Leaf", children, line, column, position);
}
if ((ExpressionParser.identifier == context.SymbolId)) {
// Leaf -> identifier
ParseNode[] children = new ParseNode[1];
children[0] = new ParseNode(ExpressionParser.identifier, "identifier", context.Value, line, column, position);
context.Advance();
return new ParseNode(ExpressionParser.Leaf, "Leaf", children, line, column, position);
}
if ((ExpressionParser.Implicit3 == context.SymbolId)) {
// Leaf -> Implicit3 Term Implicit4
ParseNode[] children = new ParseNode[3];
children[0] = new ParseNode(ExpressionParser.Implicit3, "Implicit3", context.Value, line, column, position);
context.Advance();
children[1] = ExpressionParser._ParseTerm(context);
children[2] = new ParseNode(ExpressionParser.Implicit4, "Implicit4", context.Value, line, column, position);
if ((ExpressionParser.Implicit4 == context.SymbolId)) {
context.Advance();
return new ParseNode(ExpressionParser.Leaf, "Leaf", children, line, column, position);
}
context.Error("Expecting Implicit4");
}
context.Error("Expecting integer, identifier, or Implicit3");
return null;
}
您可以看到它根据 `context` 的当前符号进行解析，然后逐个解析子节点。终结符是内联解析的，而非终结符则转发到其相应的 `_ParseXXXX()` 方法。具有折叠子节点的非终结符生成方式略有不同，使用 `List
这对于解析很好，但对评估没有任何作用。也就是说，上述代码将向解析器类添加一个 `Parse()` 方法，但语法中没有足够的信息来创建 `Evaluate()` 方法。基本上，我们可以使用上述代码获取解析树，但无法对其进行评估。让我们通过向语法添加一些代码来解决这个问题
Term<start>= Factor { ("+"|"-") Factor } => {
int result = (int)EvaluateFactor(node.Children[0]);
int i = 2;
while (i<node.Children.Length)
{
if(node.Children[i-1].SymbolId==add)
result += (int)EvaluateFactor(node.Children[i]);
else // sub
result -= (int)EvaluateFactor(node.Children[i]);
i+=2;
}
return result;
}
Factor= Unary { ("*"|"/") Unary } => {
int result = (int)EvaluateUnary(node.Children[0]);
int i = 2;
// Because of the way the grammar is factored, this can
// end up being Factors when collapsed. We have to check
while (i<node.Children.Length)
{
if(node.Children[i].SymbolId==Unary) // Unary
{
if(node.Children[i-1].SymbolId==mul)
result *= (int)EvaluateUnary(node.Children[i]);
else // div
result /= (int)EvaluateUnary(node.Children[i]);
} else // Factor
{
if(node.Children[i-1].SymbolId==mul)
result *= (int)EvaluateFactor(node.Children[i]);
else // div
result /= (int)EvaluateFactor(node.Children[i]);
}
i+=2;
}
return result;
}
Unary= ("+"|"-") Unary | Leaf => {
if(node.Children.Length==1)
return EvaluateLeaf(node.Children[0]);
if(node.Children[0].SymbolId==add)
return EvaluateUnary(node.Children[1]);
else
return -(int)EvaluateUnary(node.Children[1]);
}
Leaf= integer | identifier | "(" Term ")" => {
if(node.Children.Length==1) // integer | identifer
{
if(node.Children[1].SymbolId==integer)
return int.Parse(node.Children[0].Value);
else // identifier
throw new NotImplementedException("Variables are not implemented.");
} else // Term
return EvaluateTerm(node.Children[1]);
}
// we only need to declare terminals explicitly if we want
// constant names for them or to apply attributes to them
// in this case we don't need divide, subtract or
// parentheses to be declared
add="+";
mul="*";
integer='[0-9]+';
identifier='[A-Z_a-z][0-9A-Z_a-z]*';
whitespace<hidden>='\s+';
注意由 `=> { ... }` 表示的代码块，它告诉我们的解析器如何**处理**我们创建的解析树。
这表示一个整数表达式解析器。由于语法中有代码，它会创建一个 `public` `ExpressionParser.Evaluate()` 方法，可用于调用它，从而评估一个简单的整数表达式，例如 `4+2*8`。
这是它为 `EvaluateLeaf()` 生成的代码。您可以看到代码与上面语法中关联的代码非常相似，只有细微的变化。
public static object EvaluateLeaf(ParseNode node, object state) {
if ((ExpressionParser.Leaf == node.SymbolId)) {
if ((node.Children.Length == 1)) {
if ((node.Children[1].SymbolId == ParsleyDemo.ExpressionParser.integer)) {
return int.Parse(node.Children[0].Value);
}
else {
throw new NotImplementedException("Variables are not implemented.");
}
}
else {
return ParsleyDemo.ExpressionParser.EvaluateTerm(node.Children[1]);
}
}
throw new SyntaxException("Expecting Leaf", node.Line, node.Column, node.Position);
}
这是 VB.NET 中的相同代码。
Public Overloads Shared Function EvaluateLeaf(ByVal node As ParseNode, ByVal state As Object) As Object
If (ExpressionParser.Leaf = node.SymbolId) Then
If (node.Children.Length = 1) Then
If (node.Children(1).SymbolId = ParsleyDemo.ExpressionParser.[integer]) Then
Return Integer.Parse(node.Children(0).Value)
Else
Throw New NotImplementedException("Variables are not implemented.")
End If
Else
Return ParsleyDemo.ExpressionParser.EvaluateTerm(node.Children(1))
End If
End If
Throw New SyntaxException("Expecting Leaf", node.Line, node.Column, node.Position)
End Function
如您所见，语法中的代码块已转换为目标语言。这就是 **Slang**。**Slang** 仍处于实验阶段，但它足以在代码块中进行简单的评估。这里有一个问题。`EvaluateUnary()`（以及 `Evaluate()` 和所有 `EvaluateXXXX()` 方法）返回 `object`！这是一个**整数**表达式解析器，因此返回 `int` 更合适。幸运的是，我们可以使用 `type` 属性告诉解析器要返回的类型。在这里，我们将 `type` 属性添加到我们更改了语法的元素中，我用粗体标出
Term<start,type="int">= Factor { ("+"|"-") Factor } => {
int result = EvaluateFactor(node.Children[0]);
int i = 2;
while (i<node.Children.Length)
{
if(node.Children[i-1].SymbolId==add)
result += EvaluateFactor(node.Children[i]);
else // sub
result -= EvaluateFactor(node.Children[i]);
i+=2;
}
return result;
}
Factor<type="int">= Unary { ("*"|"/") Unary } => {
int result = EvaluateUnary(node.Children[0]);
int i = 2;
// Because of the way the grammar is factored, this can
// end up being Factors when collapsed. We have to check
while (i<node.Children.Length)
{
if(node.Children[i].SymbolId==Unary) // Unary
{
if(node.Children[i-1].SymbolId==mul)
result *= EvaluateUnary(node.Children[i]);
else // div
result /= EvaluateUnary(node.Children[i]);
} else // Factor
{
if(node.Children[i-1].SymbolId==mul)
result *= EvaluateFactor(node.Children[i]);
else // div
result /= EvaluateFactor(node.Children[i]);
}
i+=2;
}
return result;
}
Unary<type="int">= ("+"|"-") Unary | Leaf => {
if(node.Children.Length==1)
return EvaluateLeaf(node.Children[0]);
if(node.Children[0].SymbolId==add)
return EvaluateUnary(node.Children[1]);
else
return -EvaluateUnary(node.Children[1]);
}
Leaf<type="int">= integer | identifier | "(" Term ")" => {
if(node.Children.Length==1) // integer | identifer
{
if(node.Children[1].SymbolId==integer)
return node.Children[0].Value;
else // identifier
throw new NotImplementedException("Variables are not implemented.");
} else // Term
return EvaluateTerm(node.Children[1]);
}
// we only need to declare terminals explicitly if we want
// constant names for them or to apply attributes to them
// in this case we don't need divide, subtract or
// parentheses to be declared
add="+";
mul="*";
integer='[0-9]+';
identifier='[A-Z_a-z][0-9A-Z_a-z]*';
whitespace<hidden>='\s+';
请注意，我们不仅在每个非终结符生产上标记了属性 `type="int"`，而且我们还稍微更改了代码（特别是在 `Leaf` 中），从
if(node.Children.Length==1) // integer | identifer
{
if(node.Children[1].SymbolId==integer)
return int.Parse(node.Children[0].Value);
else // identifier
throw new NotImplementedException("Variables are not implemented.");
} else // Term
return EvaluateTerm(node.Children[1]);
改为
if(node.Children.Length==1) // integer | identifer
{
if(node.Children[1].SymbolId==integer)
return node.Children[0].Value;
else // identifier
throw new NotImplementedException("Variables are not implemented.");
} else // Term
return EvaluateTerm(node.Children[1]);
这个更改不是必需的，但它稍微简化了一些事情。它利用 Microsoft 的 `TypeConverter` 框架与 `Convert.ChangeType()` 结合，自动将您的返回值转换为目标类型。
尽管有这些代码，但使用生成的代码非常简单
var text = "3*5+7*2";
var exprTokenizer = new ExpressionTokenizer(text);
var pt = ExpressionParser.Parse(exprTokenizer);
Console.WriteLine("{0} = {1}",text,ExpressionParser.Evaluate(pt));
Console.WriteLine();
创建解析器与创建标记器是分开的步骤，原因是因为实际上可以使用 **Rolex** 标记器以外的标记器与此解析器一起使用，但您必须提供自己的 `Token` 结构和实现 `IEnumerable
最后，我们现在有了 `Evaluate()`，但还有一个小问题需要解决，那就是变量，它们以前没有实现。我们可以使用 `Evaluate()` 中的 `state` 参数来实现变量，它允许我们将用户定义的值传递给我们的评估代码。我们必须更改语法中的代码才能支持它，所以让我们再次修改语法。
Term<start,type="int">= Factor { ("+"|"-") Factor } => {
int result = EvaluateFactor(node.Children[0],state);
int i = 2;
while (i<node.Children.Length)
{
if(node.Children[i-1].SymbolId==add)
result += EvaluateFactor(node.Children[i],state);
else // sub
result -= EvaluateFactor(node.Children[i],state);
i+=2;
}
return result;
}
Factor<type="int">= Unary { ("*"|"/") Unary } => {
int result = EvaluateUnary(node.Children[0],state);
int i = 2;
// Because of the way the grammar is factored, this can
// end up being Factors when collapsed. We have to check
while (i<node.Children.Length)
{
if(node.Children[i].SymbolId==Unary) // Unary
{
if(node.Children[i-1].SymbolId==mul)
result *= EvaluateUnary(node.Children[i],state);
else // div
result /= EvaluateUnary(node.Children[i],state);
} else // Factor
{
if(node.Children[i-1].SymbolId==mul)
result *= EvaluateFactor(node.Children[i],state);
else // div
result /= EvaluateFactor(node.Children[i],state);
}
i+=2;
}
return result;
}
Unary<type="int">= ("+"|"-") Unary | Leaf => {
if(node.Children.Length==1)
return EvaluateLeaf(node.Children[0],state);
if(node.Children[0].SymbolId==add)
return EvaluateUnary(node.Children[1],state);
else
return -EvaluateUnary(node.Children[1],state);
}
Leaf<type="int">= integer | identifier | "(" Term ")" => {
if(node.Children.Length==1) // integer | identifer
{
if(node.Children[0].SymbolId==integer)
return node.Children[0].Value;
else // identifier
{
if(state!=null)
{
int val;
var d = (IDictionary<string,int>)state;
if(d.TryGetValue(node.Children[0].Value,out val))
return val;
}
throw new SyntaxException(string.Format("Reference to undefined variable {0}",node.Children[0].Value),node.Line,node.Column,node.Position);
}
} else // Term
return EvaluateTerm(node.Children[1],state);
}
// we only need to declare terminals explicitly if we want
// constant names for them or to apply attributes to them
// in this case we don't need divide, subtract or
// parentheses to be declared
add="+";
mul="*";
integer='[0-9]+';
identifier='[A-Z_a-z][0-9A-Z_a-z]*';
whitespace<hidden>='\s+';
请注意，我们现在使用 `state` 变量来保存一个 `IDictionary
当我们遇到标识符时，我们使用简单的字典查找来解析它。
我们现在必须更改调用它的代码，以传入我们的变量
var text = "3*5+a*2";
var vars = new Dictionary<string, int>();
vars["a"] = 1;
var exprTokenizer = new ExpressionTokenizer(text);
var pt = ExpressionParser.ParseExpression(exprTokenizer);
Console.WriteLine("{0} = {1}",text,ExpressionParser.Evaluate(pt,vars));
然后就大功告成了。
然而，这有点复杂。所以我添加了一些简写来简化。首先，有虚拟变量 `
对于上述语法，我们有 `Unary1`、`Unary2`、`UnaryN`，以及 `Expression1`、`Expression2`、`ExpressionN`，以及 `Factor1` 和 `Factor2` 等等。我们还有 `SymbolId1`、`SymbolId2` 等。
数字是子节点中基于 **1** 的位置。`SymbolId1` 是 `node.Children[0].SymbolId` 的别名。终结符只指向 `node.Children[x].Value`，而非终结符产生式调用指定位置的非终结符的关联评估方法，例如，上述语法中的 Factor3 将解析为 `ExpressionParser.EvaluateFactor(node.Children[2], state)`！
您也可以像 `Unary[i]` 这样索引它们。此外，还有一个 `Child` 宏（`Child1`..`ChildN`，`Child[i]`），它让您能够在运行时评估节点类型，它会为您调用适当的 `EvaluateXXXX()` 方法。这在底层语法中存在折叠节点的情况下很有用，因为有时这意味着我们无法提前知道在评估函数中会看到哪些节点。我们将在下面讨论这一点
此外，这在您查看最终语法格式之前可能看起来不太直观
Term<start,type="int">= Factor { ("+"|"-") Factor } => {
int result = Factor1;
int i = 2;
while (i<Length)
{
if(SymbolId[i-1]==add)
result += Factor[i];
else // sub
result -= Factor[i];
i+=2;
}
return result;
}
Factor<type="int">= Unary { ("*"|"/") Unary } => {
int result = Unary1;
int i = 2;
// Because of the way the grammar is
// factored, this can end up being
// Factors when collapsed. We use
// Child[n] which is a "smart"
// macro that evaluates the symbol
// at runtime and calls the right
// EvaluateXXXX method
while (i<Length)
{
// Child always returns an object type so
// be sure to cast as necessary
if(SymbolId[i-1]==mul)
result *= (int)Child[i];
else // div
result /= (int)Child[i];
i+=2;
}
return result;
}
Unary<type="int">= ("+"|"-") Unary | Leaf => {
if(Length==1)
return Leaf1;
if(SymbolId[0]==add)
return Unary2;
else
return -Unary2;
}
Leaf<type="int">= integer | identifier | "(" Term ")" => {
if(Length==1) // integer | identifer
{
if(SymbolId[0]==integer)
return integer1;
else // identifier
{
if(state!=null)
{
int val;
var d = (IDictionary<string,int>)state;
if(d.TryGetValue(identifier1,out val))
return val;
}
throw new SyntaxException(string.Format("Reference to undefined variable {0}",identifier1),node.Line,node.Column,node.Position);
}
} else // Term
return Term2;
}
// we only need to declare terminals explicitly if we want
// constant names for them or to apply attributes to them
// in this case we don't need divide, subtract or
// parentheses to be declared
add="+";
mul="*";
integer='[0-9]+';
identifier='[A-Z_a-z][0-9A-Z_a-z]*';
whitespace<hidden>='\s+';
看看那个！一旦你掌握了它，它就很容易理解。宏使事情变得清晰并保持简单
语法中的代码区域
在生产之间，您可以使用 `{ }` 指定要添加到解析器类的代码区域。任何字段或方法必须是静态或常量，并且不能以语法中的任何符号命名。
这些区域作为类的成员添加。稍后我们将在下一节中创建一个辅助方法时讨论它们。
语法约束
语法约束，或语法谓词，通过指示一个 `boolean` 函数来帮助消除语法的歧义，该函数告诉解析器您的生产是否匹配。下面是一个示例，也使用了上面提到的代码区域，展示了 `where` 子句的使用，其形式为
identifer [ "<" attributes ">" ] = expressions (";" | [ "=>" "{" code "}" ] ) ":" "where" "{" code "}"
以下区分了 C# 关键字和标识符：（请注意，我们使用的终结符定义是 Unicode，因此它们需要 **Gplex** 词法分析器）
Identifier<collapsed> = verbatimIdentifier | identifier : where { return !Keywords.Contains(context.Value); }
verbatimIdentifier='@(_|[[:IsLetter:]])(_|[[:IsLetterOrDigit:]])*';
identifier='(_|[[:IsLetter:]])(_|[[:IsLetterOrDigit:]])*';
{
static HashSet<string> Keywords=_BuildKeywords();
static HashSet<string> _BuildKeywords()
{
var result = new HashSet<string>();
string[] sa = "abstract|as|ascending|async|await|base|bool|break|byte|case|catch|char|checked|class|const|continue|decimal|default|delegate|descending|do|double|dynamic|else|enum|equals|explicit|extern|event|false|finally|fixed|float|for|foreach|get|global|goto|if|implicit|int|interface|internal|is|lock|long|namespace|new|null|object|operator|out|override|params|partial|private|protected|public|readonly|ref|return|sbyte|sealed|set|short|sizeof|stackalloc|static|string|struct|switch|this|throw|true|try|typeof|uint|ulong|unchecked|unsafe|ushort|using|var|virtual|void|volatile|while|yield".Split(new char[] {'|'});
for(var i = 0;i<sa.Length;++i)
result.Add(sa[i]);
return result;
}
}
我们可以使用固定的字符串查找来创建 `_BuildKeywords()` 函数，这将更有效率，但代码量会大得多。
在这里，我们已将 `verbatimIdentifier` 指定在 `identifier` 之前，这使其在词法分析器/标记器中具有优先级。我们的非终结符 `Identifier`（不要与终结符 `identifier` 混淆）指定了一个逐字标识符或一个标识符，并使用 `where` 子句来确定它是否是关键字，在这种情况下，解析器在解析时不会将光标下的项视为 `Identifier`。对于经验丰富的用户来说，有一个技巧，您可以通过指定 `where` 子句并始终返回 `true` 来覆盖第一个-第一个或第一个-跟随的冲突。但是，只有在您知道自己在做什么时才使用此方法，因为它可能会使语法的一部分无法访问，并且不会警告您。我们不必折叠 `Identifier`，但我们这样做了，因为它在最终的解析树中不需要，并且只会创建一个不必要的额外节点。另请注意循环中前缀增量运算符的使用。请记住，**Slang** 不支持后缀增量，因为底层的 `CodeDOM` 无法以语言无关的方式实现。
抽象和虚拟非终结符
这些是同时使用的，这就是我们一起讨论它们的原因。这是一个强大的功能，用于解决生成代码无法处理的解析，例如 C# 中类型转换表达式和带括号子表达式之间的区别。我们将从虚拟非终结符开始，它们采用以下形式：
identifier "<" attributes ">" "{" code "}" // we must include at least the the "firsts" attribute!
首先，让我们回顾一下 `firsts` 属性。这只是告诉解析器在您的虚拟非终结符中哪些符号可以首先出现。这些必须与您的解析器函数匹配，否则解析器将无法正确找到您的非终结符！我还将非终结符标记为无操作 `virtual` 属性，仅为了可读性，但这是可选的。
Cast<virtual,firsts="lparen"> {
return _ParseCast(context);
}
请注意，我转发了一个函数。这样我就可以将所有代码保存在语法底部的一个代码区域中（我们上面已经讨论过）。请注意，我还在函数前加了一个下划线。这是为了确保名称不会与任何生成的解析函数冲突，包括 `ParseCast()` 本身，它将作为此虚拟非终结符声明的结果而生成。让我们看看 `_ParseCast()`
static ParseNode _ParseCast(ParserContext context) {
int line = context.Line;
int column = context.Column;
long position = context.Position;
if("("!=context.Value)
context.Error("Expecting ( as start of expression or cast");
ParseNode lp = new ParseNode(SlangParser.lparen, "lparen", context.Value, context.Line, context.Column, context.Position);
context.Advance();
ParseNode type = ParseTypeCastPart(context);
ParseNode expr = ParseExpression(context);
return new ParseNode(SlangParser.Cast, "Cast", new ParseNode[] {type,expr}, line, column, position);
}
在代码块中，我们使用其他解析例程并根据解析创建解析节点，直接使用解析器的 API：您可以看到这相当复杂。权力越大责任越大。在这里，您负责处理行号，手动解析终结符，移动光标，调用其他 `ParseXXXX()` 函数，并准确报告解析节点。请注意我们如何 `Advance()` 移动经过终结符，但我们不需要这样做来移动经过非终结符，因为其他 `ParseXXXX()` 函数会为我们完成。请记住传递 `context`。请注意我们如何小心地存储进入函数时的初始行、列和位置信息，因为我们会在最后报告它们。请注意，在报告解析终结符错误时，我们使用当前的行、列和位置。请务必小心，否则您的位置信息将是错误的。基本上，这允许您完全自行实现 `ParseXXXX()` 方法，而不是使用生成的代码。
看到我们是如何解析 `TypeCastPart` 的吗？我还没有向您展示定义，但它在这里
// this is necessary so we can get Parsley to generate a
// method called ParseTypeCastPart() which we use
// when resolving casts
TypeCastPart<include,collapsed>= Type ")";
请注意 `include` 属性的添加。这是一个虚拟属性，用于确保 `TypeCastPart` 出现在语法中，因为它在语法中除了代码之外没有被任何东西引用。属性强制非终结符存在于语法中。我们这里不需要 `include`，但我为了可读性而指定了它。如果我们没有指定 `collapsed`，我们就必须指定 `include`（或其他东西），否则 `ParseTypeCastPart()` 永远不会出现在语法中。由于我们实际上没有在解析树中报告它，而只是将其用于解析，所以我们折叠它。然而，那一部分是可选的。看它如何以“**)**”结尾？这是因为类型转换看起来像 `(string)foo`，因此为了让解析器知道“**)**”可以跟随 `Type`，我们必须在这里吃掉右括号。另一个选择是手动解析 `Type`，这太费劲了。
最后我们来到抽象非终结符。假设你想报告一个语法中实际不存在的非终结符。抽象非终结符只是允许你在语法中放置一个“空/无操作”非终结符，然后你的解析函数可以报告它，因为它有一个与之关联的符号常量。它们采用以下形式：
identifier "<" attributes ">" ;
除了属性之外，这个生产式没有指定任何内容。它只是用分号终止。它所做的只是在语法中生成一个符号，所以这……
Foo<abstract>;
生成一个您可以使用的常量符号，但没有 `ParseFoo()` 方法。您将从您的一个虚拟非终结符返回此符号。它不会在其他任何地方使用。请注意，您必须为语法中未引用的任何非终结符指定属性，其中包括**不能**在语法中引用的抽象非终结符。
有关更多信息，请参阅 *ParsleyDemo* 和 *ParsleyDemoVB* 项目。
@options 指令
“`@options`”指令允许您使用语法中的自己的设置覆盖 Parsley 的大部分命令行。如果语法导入了其他语法，则只有顶层语法的“`@options`”设置会生效。格式如下：
@options option1=optionValue1, option2=optionValue2, option2=optionValue3;
`@options` 指令可以出现一次，并且像 `@import` 一样，必须出现在任何生产之前。选项值可以是带引号的字符串、数字、`boolean` 或 `null`。当前可用的选项如下，并且与它们的命令行对应项：`outputfile`、`codenamespace`、`codeclass`、`codelanguage`、`rolexfile`、`gplexfile`、`gplexcodeclass`、`fast` 和 `verbose`。与属性一样，布尔值为 true 的值不需要显式指定其值，只需指定其名称即可，因此 `verbose` 和 `verbose=true` 是等效的。再次强调，这些将覆盖命令行选项。您通常会将它们与下面介绍的 Visual Studio 集成一起使用。
将此作为预构建步骤
只需导航到项目选项，在“生成事件”(C#) 下，将其添加到预生成事件命令行。在 VB 中，在项目选项中找到预生成事件位置比在 C# 中更复杂，但四处寻找。它就在那里。
无论哪种方式，您都需要知道要输入什么，所以这里是。您需要制作两样东西——一个解析器和一个标记器/词法分析器。每个都将有自己的命令行来执行。对于您的解析器，您将使用 parsley.exe，对于您的标记器/词法分析器，您将使用 rolex.exe 或 gplex.exe。您会希望 parsley.exe 首先运行，并确保为其提供正确的参数以为您生成一个词法分析器文件（假设语法中没有指示一个）。之后，您将根据您使用的词法分析器运行 rolex.exe 或 gplex.exe。如果您从头开始制作自己的词法分析器，则可以跳过第二个命令行，但大多数人永远不会这样做。
无论如何，以下是基础知识（参见 ParsleyDemo 和 ParsleyDemoVB）
"parsley.exe" "$(ProjectDir)Expression.xbnf" /output "$(ProjectDir)ExpressionParser.cs" /rolex "$(ProjectDir)Expression.rl" /namespace ParsleyDemo /ifstale "rolex.exe" "$(ProjectDir)Expression.rl" /output "$(ProjectDir)ExpressionTokenizer.cs" /namespace ParsleyDemo /ifstale
首先，用引号将路径括起来，包括宏，以及您的初始可执行路径。我们在这里只指定了“parsley.exe”和“rolex.exe”，但您可能需要输入它们的完整路径，除非它们在您的 `PATH` 中。演示项目只是使用解决方案中相关项目的二进制文件，但在其他情况下您无法使用。一个选项是将可执行文件包含在您的项目文件夹的某个位置，并使用相对路径引用它们。这样，如果您将项目复制到另一台机器，它仍然可以构建。我希望这很清楚。
请注意，我们使用宏来引用项目目录。如果您点击预构建事件的编辑窗口，宏列表可用。
以上是 Parsley 与 Rolex 结合使用的示例。与 Gplex 结合使用类似。
"parsley.exe" "$(ProjectDir)Slang.xbnf" /output "$(ProjectDir)SlangParser.cs" /gplex "$(ProjectDir)Slang.lex" /namespace CD /fast /ifstale "gplex.exe" /out:"$(ProjectDir)SlangScanner.cs" "$(ProjectDir)Slang.lex"
请注意 Gplex 命令行参数的语法如何不同，以及选项位于输入文件之前。请务必小心。我没有编写 Gplex，所以它的用法与我编写的程序中的用法有很大不同。
Visual Studio 集成
应要求，我为 Parsley、Rolex 和 Gplex 添加了开发工作室集成，可以通过 ParsleyDevstudio VSIX 包安装。此包中包含 3 个自定义工具，每个工具都会生成一个日志和特定程序的输出，作为主文件下的文件。
导航到 XBNF (Parsley, *.xbnf) 输入文件、Rolex 词法分析器输入文件 (*.rl) 或 Gplex 词法分析器输入文件 (*.lex)，并设置相应的自定义工具，然后**等待**，因为这些工具需要相当长的时间才能完成工作。我建议您只将其用于小型语法，或与 (仅限 C#) `fast` 选项和使用 `gplex` 词法分析器一起使用，以减少等待时间。不幸的是，由于 Visual Studio 提供的基础架构，我无法在不冻结开发工作室的情况下使这些自定义工具工作。
要进行设置，请安装 VSIX 包，然后导航到 XBNF 文档，在解决方案资源管理器中单击它以获取文档属性（通常在 VS 工作区的右下方），找到 `Custom Tool`，然后将其设置为 **Parsley** - 一旦您这样做，Parsley 将开始生成过程，因此 VS 将在几秒钟内无响应。其他自定义工具是 **Gplex** 和 **Rolex**。
Visual Studio 集成的限制
将 Parsley 集成到构建中的预构建步骤方法仍然是推荐的构建项目方式。但是，如果您选择改用 VS 自定义工具集成，请注意以下限制
- Parsley 的生成速度有点慢，有时 VS 会无缘无故地重新生成，导致不必要的性能损失
- 每个命名空间只支持一个词法分析器。这主要是由于 Gplex 和 Rolex 的限制，对于 Rolex，使用预构建方法可以规避此问题。尝试在同一个命名空间中生成多个词法分析器将导致编译错误。
- 自定义工具无法检测到对依赖文件（例如导入）的更改。如果这些文件发生更改，您必须手动重新运行该工具。
- 从文件中删除自定义工具时，生成的并非所有文件都会被删除，只有日志文件会被删除。您必须手动删除其他文件。
- 我还没有像我希望的那样广泛地测试这个集成。测试它有点困难，所以它正在进行中。
- 您无法在 VS 自动化构建（运行没有 UI 的 VS）期间使用自定义工具——这些工具只在设计时环境中工作。
- 我相当确定重命名顶级文件会破坏一些东西。
- 总的来说，你对命令行的控制不如命令行那么强大。
其中一些限制是由于我不得不采用的巨大黑客手段，以让 Visual Studio 识别单个自定义工具的多个输出文件。它根本不是为此设计的，这样做需要一些丑陋的魔法。有些，比如无响应的时间段，仅仅是 Parsley 和/或自定义工具的性质造成的。
请注意，您几乎肯定会希望在 XBNF 文档中使用 `@options` 指令，至少指定要生成的词法分析器文件。如果使用 Parsley 生成词法分析器文档，词法分析器文档将自动与其适当的自定义工具关联，因此词法分析器生成器也将根据需要运行。因此，尽管有 3 个 VS 自定义工具，但您主要只会自己使用“`Parsley`”，而其他工具将根据需要自动设置。
延伸阅读
有关使用高级 parsley 功能的后续文章：解析任何内容第 1 部分和第 2 部分。
有关 `firsts` 和 `follows` 以及 LL(1) 解析基础知识的更多信息，请参阅如何制作解析器，第 1 课
有关递归下降解析的更多信息，请参阅Geeks for Geeks 上的递归下降解析器。
历史
- 2019年12月19日：首次提交
- 2019年12月20日：更新
- 2019年12月21日：更新 2
- 2019年12月22日：更新 3
- 2019年12月23日：更新 4
- 2019年12月26日：更新 5
- 2019年1月9日：更新 6