Glory：.NET 的 GLR 解析器生成器
5.00/5 (4投票s)
Glory 几乎可以解析任何内容，甚至包括自然语言。为您的项目添加强大的解析器。解析 C# 等语言，或将人类语言解析集成到您的 AI 代码中。
引言
我发现针对 .NET 的 GLR 解析器选择非常少。我找到的要么不完整，要么是某个更大项目的一部分。Glory 旨在让 .NET 开发者能够使用强大的 GLR 解析器来解析自然语言。
概念化这个混乱的局面
概述
GLR 解析是通用解析算法中最强大的，但它也像其他自底向上解析技术一样存在一些不便。Glory 在很大程度上掩盖了这一点，但要做到完全隐藏是不可能的。
另一方面，它也拥有 LR 解析的优点，例如在非歧义文法中的强大功能、效率以及处理左递归的能力。
由于能够处理左递归和歧义文法，GLR 解析器可以接受任何文法。这仅仅是解析效率的问题。歧义越多，效率越低，返回的解析树也就越多。
如前所述，广义 LR (GLR) 解析是一种建立在现有 LR 解析算法（如 LR(1)、LALR(1) 或 LR(0)）之上的解析技术。Glory，像大多数 GLR 解析器一样，底层使用 LALR(1)，因为它在功能和表格大小方面优于 LR(1)。也可以使用 LR(0)，但由于文法冲突的频繁发生，这会降低解析性能。
命令行界面
命令行是 Glory 的主要接口，因此了解它非常重要。首先，这里是使用说明屏幕，对于换行请谅解。
Glory generates a GLR parser and optional lexer spec
glory.exe <inputfile> [/output <outputfile>] [/rolex <rolexfile>]
[/namespace <codenamespace>] [/class <codeclass>]
[/langage <codelanguage>] [/fast] [/noshared]
[/verbose] [/ifstale] [/noparser]
<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
<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 output files are older than
the input files.
<noparser> Generate any specified lexers with the appropriate
symbol table but do not generate the parser output.
inputfile是解析器将从中生成 XBNF 规范（稍后详述）。outputfile是可选的，指定要生成的输出代码文件。如果未指定，代码将输出到stdout。rolexfile是可选的，指定要生成的 **rolex** 词法分析器规范文件。如果未指定，则不会生成 **rolex** 规范。codenamespace是生成代码的命名空间。如果未指定，代码将不会在命名空间下生成。codeclass是要使用的解析器类的名称。如果不指定，它将与outputfile相同，除非outputfile未指定，在这种情况下，它将从 XBNF 文法的起始元素获取名称。codelanguage是要生成代码的语言。如果不指定，它将基于outputfile的文件扩展名。如果outputfile未指定，则默认为 C#。fast表示代码生成应跳过解析步骤，直接生成 C# 代码。指定codelanguage时，此选项无效。noshared跳过生成共享代码。这对于在同一项目中生成第二个解析器很重要。第一个解析器应在不带此开关的情况下生成，后续解析器应带此开关生成。如果此处指定了 noshared，当 Rolex 用于生成词法分析器/标记化代码时，也应将其指定给 Rolex。您不希望源代码中有重复的共享代码，因为这会导致编译错误。verbose发出所有文法转换和验证消息，包括有关重构规则的消息。对于大型文法和大量重构，这可能会产生巨大的输出，但它允许您查看所做的更改。无论如何，您还可以在生成的代码的文档注释中看到更改。ifstale除非输入已修改，否则跳过生成输出。这对于预构建步骤很有用，因为它避免了每次都重建解析器的开销。
您可能希望将此工具与 **Rolex**（解决方案中包含的标记化器）一起使用。这是使用 **Glory** 最简单的方法。几乎所有的解析器（特别是 PEG 解析器除外）都需要词法分析器/标记化器，**Glory** 也不例外。关于 **Rolex** 的更多信息，我写了一篇关于创建 Rolex 的文章，尽管您应该使用此代码库，因为它更新。使用 rolex 时，您需要使用其 /external 选项指定解析器的命名空间。
XBNF 文法格式
Glory 以 XBNF 文法文档作为输入，并生成一个源文件作为输出。如果您使用过我其他的解析器生成器，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 的值未指定，因此它隐式为 start=true。
这告诉解析器 Json 是起始产生式。如果未指定，将使用文法中的第一个非终结符。此外，这可能会在生成过程中导致警告，因为它不是一个好的做法。只有 start 的第一次出现才会被尊重。
Object | Array 告诉我们 Json 产生式由对象或数组派生。Object 产生式包含一个重复的 {} 结构和一个可选的 [] 结构，其中本身包含对 Field 的引用。Array 类似，但它使用 "[" 和 "]"，并引用 Value 而不是 Field。
表达式
( )括号允许您创建子表达式，例如Foo (Bar|Baz)。[ ]可选表达式允许子表达式出现零次或一次。{ }此重复结构重复子表达式零次或多次。{ }+此重复结构重复子表达式一次或多次。|此交替结构派生出子表达式中的任意一个。- 连接是隐式的，用空白分隔
终结符
终结符全部在底部定义，但它们可以出现在文档中的任何位置。XBNF 认为任何不引用其他产生式的产生式都是终结符。您可以使用 terminal 属性强制将某个元素设为终结符（见下文）。
正则表达式在 ' 单引号之间，字面量表达式在 " 双引号之间。您可以通过使用 XBNF 结构或正则表达式来声明一个终结符。正则表达式语言和功能的具体细节取决于您使用的词法分析器生成器。并非所有词法分析器都支持终结符上的所有属性。目前，Glory 只会生成 Rolex 规范。但是，只要它们可以被包装以暴露 IEnumerable<Token> 接口，您就可以使用其他词法分析器生成器。
属性
collapsed 元素告诉 Glory 此节点不应出现在解析树中。相反，它的子节点将被传播到其父节点。如果文法需要非终结符或终结符来解析某个结构，但对解析树的消费者无用，则这很有帮助。上面，我们使用它来显著修剪解析树中不需要的节点，包括折叠 JSON 文法中不必要的终结符，如 :。这是因为它们无助于定义任何内容，它们仅帮助解析器识别输入，因此我们可以丢弃它们以减小解析树的大小。请注意，collapsed 不会影响 GlrTableParser 及其派生类报告的内容，它仅影响最终的解析树。
hidden 元素告诉词法分析器/标记化器跳过此终结符。这对于注释和空格等很有用。
blockEnd 属性适用于具有多字符结束条件的终结符，例如 C 块注释、XML CDATA 部分和 SGML/XML/HTML 注释。如果存在，词法分析器将继续直到匹配到 blockEnd 指定的字面量。Rolex 支持此功能，但将来可能会有其他工具支持。我过去曾使用 GPLEX 成功实现过，但由于它很丑陋，我删除了所有 GPLEX 支持代码。
terminal 属性将产生式声明为显式终结符。即使这样的产生式引用了其他产生式，它也被认为是终结符。如果它引用了其他产生式，那么这些其他产生式将以终结符的形式包含进来，就好像它们是原始表达式的一部分一样。这允许您从多个终结符定义创建复合终结符。
ignoreCase 属性指定匹配时不应考虑大小写。这仅适用于终结符，并且仅与 Rolex 一起使用。
type 属性指定 .NET 类型或关联的*求值代码块*（见下文）的内置 C# 类型。从这些“类型化”的非终结符返回的值会自动转换为目标类型，从而无需转换返回值或使用 int.Parse() 等进行转换。它会为您处理。此外，它使生成的例程返回一个类型化的值，而不仅仅是 object。
priority 属性用特定优先级标记终结符产生式。负数优先级低于正数。必须是整数。默认情况下，项的优先级为 priority 0。
errorSentinel 属性将终结符标记为错误发生时的恢复点之一。这有助于解析器在出错后找到方向，以便继续解析。
错误处理
Glory 目前使用简单的“恐慌模式”错误恢复过程，它需要文法作者提供一些帮助。errorSentinel 属性应用于将终结符标记为恢复点——基本上，在发生错误时，解析器将“吞噬”标记直到遇到其中一个符号，然后尝试恢复堆栈状态，以便哨兵被接受为有效解析。最好使用诸如语句结束标记、方法结束标记等。指定这些符号越多越好，但有一个限度，具体取决于文法。这部分不有趣也不容易——它需要耐心。最好的方法是先添加一个或两个错误哨兵，然后尝试带有错误的文法。如果它吞噬了过多的文本，请在该文本中找到一个您可以使用的哨兵，并将其标记为属性。将来，Glory 将使用全局通用错误恢复技术而不是这种局部错误恢复技术。
@include 指令
@include 指令允许您将文法分解成多个文件，并将它们包含到主文法中。这有助于大型文法项目更好地组织。像任何指令一样，它必须出现在任何产生式之前。路径以 JSON 风格的字符串字面量形式作为单个参数指定。路径相对于包含它们的文档的路径，而不是当前路径。例如：
@include "spec/types.xbnf"
@options 指令
@options 指令允许您在文法中使用自己的设置来覆盖 Glory 的大部分命令行参数。当一个文法包含其他文法时，只有顶层文法的 @options 设置才会被尊重。格式如下：
@options option1=optionValue1, option2=optionValue2, option2=optionValue3;
@options 指令可以出现一次，并且像 @include 一样，必须出现在任何产生式之前。选项值可以是带引号的字符串、数字、boolean 或 null。当前可用的选项如下，并对应于它们的命令行参数：outputfile、codenamespace、codeclass、codelanguage、rolexfile、fast 和 verbose。与属性一样，值为 true 的布尔值不需要显式指定其值，只需指定其名称即可，因此 verbose 和 verbose=true 是等效的。同样，这些会覆盖命令行选项。您通常会使用下面的 Visual Studio 集成。
歧义文法
这值得单独讨论。由于 GLR 解析器生成器接受任何形式的文法，因此它可能更容易使用。事实恰恰相反。GLR 没有“无效”的概念，所以您的文法错误不会被检测到，只会产生与您预期的不同的解析树。更糟糕的是，已证明无法检测任何文法是否普遍存在歧义，因此 Glory 甚至无法警告您。
使用 Glory 并非易事。您必须能够处理文法和解析器输出中的歧义。这需要您在设计文法时手动检查返回的树。此外，对于复杂的“实际”文法，表格生成可能需要大量时间，因此我的建议是，在原型设计时，使用 @include 并仅生成您需要测试的文法部分，因为您绝对需要进行测试。
我包含了一个 Slang 表达式文法，这是 C# 表达式的一个子集。C# 是一个有歧义的语言，难以解析。选择多个解析树的唯一方法是通过应用类型信息来缩小返回的树，而演示程序并未这样做。它只是返回给定表达式的所有可能的解析树。有时结果会令人惊讶，因为它会找到您没想到的语法组合。再次，请参阅上面的测试免责声明。但是，即使您的文法是准确的，也可能会发生这种情况，因为 Glory 善于找到解析的所有可能性——比人类做得更好。
编写这个混乱的程序
我们将从文法中的 XBNF 代码块开始。
求值代码块
求值代码块使用 lambda/匿名方法之类的语法在文法中指定。形式为 => { ... } 在非终结符产生式末尾。
identifier [ < attributes > ] = expressions => { ... }
例如
Foo = Bar Baz => { // my code } // notice we don't terminate with a semi-colon
这表示要与该非终结符关联的代码块。此代码用于解析操作，由 EvaluateXXXX() 方法触发。在此代码中，您会获取一个 ParseNode 对象（由 node 指示）并对其进行求值，返回结果。如果您不返回结果，将返回默认值。请参阅下面的示例。
关于文法符号约定：我在文法中使用标题大写表示非终结符。这并非必需，但最终更好，因为像 EvaluateXXXX() 这样的函数直接从非终结符名称获取 XXXX 部分。因此，非终结符 foo 将生成 Evaluatefoo()。这显然是不理想的，但并非无法解决。我曾考虑过改变名称以“纠正”这一点，但最终我决定不进行意外的代码更改。这样，就可以清楚地知道这些方法的最终名称是什么。符号常量也是直接从符号名称生成的，因此如果您想与 Microsoft 的命名约定保持一致，您也会将终结符命名为 Pascal 格式/.NET 格式。但是，这远不重要，尤其是因为与非终结符不同，它们的名称不会被附加到任何东西。
让我们来看一个表达式解析器的文法。
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+';
我们可以获得一个解析树，但我们无法对其进行求值。让我们通过在文法中添加一些代码来解决这个问题。
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 | identifier
{
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 static 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 == ExpressionParser.integer)) {
return int.Parse(node.Children[0].Value);
}
else {
throw new NotImplementedException("Variables are not implemented.");
}
}
else {
return 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 = ExpressionParser.[integer]) Then
Return Integer.Parse(node.Children(0).Value)
Else
Throw New NotImplementedException("Variables are not implemented.")
End If
Else
Return 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 | identifier
{
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 | identifier
{
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]);
to
if(node.Children.Length==1) // integer | identifier
{
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 parser = new ExpressionParser(exprTokenizer);
foreach(var pt in parser.ParseReductions())
Console.WriteLine("{0} = {1}",text,ExpressionParser.Evaluate(pt));
创建解析器与创建标记化器是分开的步骤，因为实际上可以使用除 Rolex 标记化器以外的其他标记化器来使用此解析器，但您必须提供自己的 Token 结构和实现 IEnumerable<Token> 的类。出于性能原因，没有 IToken 接口。但是，您的标记必须具有以下字段：（int）SymbolId、（string）Symbol、（string）Value、（int）Line、（int）Column 和（long）Position。请参阅 Glory\Export\Token.cs 下的参考源。修改原始文件将改变 Glory 的行为，并可能使其损坏。
我们之所以循环并打印可能的结果，是因为解析器可能会返回多个树。我们可以只选择第一个，因为使用这个无歧义的文法永远只会有一个，但我希望向您展示从 Glory 获取解析树通常是什么样的，即使是对于有歧义的文法。这就是我们循环遍历 ParseReductions() 返回的所有解析树的原因，尽管在这种情况下只有一个。
最后，现在我们有了 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 | identifier
{
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 Exception(string.Format("Reference to undefined variable {0}",
node.Children[0].Value));
}
} 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<string,int> 实例，我们用它来保存我们的变量。我们还将 state 传递给我们的每个求值方法。这一点很重要，因为求值方法除了 state 和部分解析树之外，无法访问任何其他状态。
当我们遇到标识符时，我们会使用简单的字典查找来解析它。
现在我们必须更改调用它的代码，以传递我们的变量。
var text = "3*5+a*2";
var vars = new Dictionary<string, int>();
vars["a"] = 1;
var exprTokenizer = new ExpressionTokenizer(text);
var parser = new ExpressionParser(exprTokenizer);
foreach(var pt in parser.ParseReductions())
Console.WriteLine("{0} = {1}",text,ExpressionParser.Evaluate(pt,vars));
好了，搞定了。
但是，这有点复杂。所以我添加了一些快捷方式来简化。首先，有虚拟变量，名为 <Production>1 到 <Production>N，其中 <Production> 是文法中某个产生式的名称。
对于上面的文法，我们有 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 | identifier
{
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 Exception(string.Format
("Reference to undefined variable {0}",identifier1));
}
} 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+';
看看吧！一旦您掌握了它，就很容易理解了。宏使事情变得清晰，并保持简单。
演示项目是 C# 语言，并包含几个您可以尝试的文法。
文法中的代码区域
在产生式之间的任何地方，您都可以使用 { } 指定要添加到解析器类中的代码区域。任何字段或方法都必须是静态的或 const 的，并且不能以文法中任何符号的名称命名。
这些区域将作为类的成员添加，并且可以从任何求值代码块访问。
用作预构建步骤
只需导航到项目选项下的“生成事件”（C#），然后将其添加到预构建事件命令行。在 VB 中查找项目选项中的预构建事件位置比 C# 中更复杂，但请仔细查找。它就在那里。
无论哪种方式，您都需要知道要提供什么，所以这里是。您需要生成两样东西——一个解析器和一个标记化器/词法分析器。每个都有自己的命令行要执行。对于解析器，您将使用 *glory.exe*，对于标记化器/词法分析器，您通常会使用 *rolex.exe*。您希望 *glory.exe* 先运行，并确保为其提供正确的参数以生成词法分析器文件（假设文法未指定）。之后，您几乎肯定会希望运行 *rolex.exe*。如果您是从头开始创建自己的词法分析器，则可以跳过第二个命令行，但大多数人不会这样做。
总之，这里是基本用法（请参阅 GloryDemo 和 GloryDemoVB）。
"glory.exe" "$(ProjectDir)Expression.xbnf" /output "$(ProjectDir)ExpressionParser.cs"
/rolex "$(ProjectDir)Expression.rl" /namespace GloryDemo /ifstale
"rolex.exe" "$(ProjectDir)Expression.rl" /output "$(ProjectDir)ExpressionTokenizer.cs"
/namespace GloryDemo /external GloryDemo /ifstale
首先，在路径周围加上引号，包括宏和初始可执行文件路径。这里我们只指定了“glory.exe”和“rolex.exe”，但您可能需要提供它们的完整路径，除非它们在您的 PATH 中。我经常会把必要的工具复制到解决方案文件夹，然后设置生成步骤来使用该 EXE。这样，如果您将项目复制到另一台机器，它仍然可以生成。希望这很清楚。
请注意，在 Rolex 中我们指定了 /external GloryDemo。这强制 Rolex 使用指定命名空间中已声明的外部 Token 结构，而不是生成一个。这是因为 Glory 提供了自己的 Token 结构。
请注意，我们使用了宏来引用*项目*目录。宏列表可在预构建事件的编辑窗口中找到，只需点击/浏览即可。
Visual Studio 集成
我已从该项目中移除了 Visual Studio 集成，因为存在太多问题。
我最终将为我所有的解析器发布一个 Visual Studio 集成包。存在两个阻止发布的问题：语言无关的代码生成需要对自定义工具功能进行严重的破解，而且我还没有弄清楚如何在生成共享代码之前检测到项目中是否已存在共享代码。这尤其是一个问题，因为 Rolex 必须使用 Glory 的 Token 定义，但 Rolex 自定义工具无法判断项目中是否已存在 Token 结构。Microsoft 没有过多记录其可扩展性功能，因此我不确定何时能够解决这些问题。
另一个问题是，对于实际文法，LR 表格生成可能需要很长时间，因此它会使 Visual Studio 冻结相当长一段时间。最好将其作为生成步骤来完成。
关注点
我的丈夫会说多种语言并学习语言学，我们终于有了一个汇聚的项目。我教他 XBNF，他希望我能从中得到一部分米斯特克语或西班牙语的文法，然后我就可以生成解析/翻译树，据他说他可以用这些树做些什么，我不知道。应该很有趣。万岁 GLR。
历史
- 2020年2月22日 - 初始提交