C# 中的 GLR 解析：如何使用已知最强大的解析算法
5.00/5 (7投票s)
GLR 解析速成课程，可用于解析高度模糊的语法。
引言
本文旨在教授如何使用广义 LR 解析来解析高度模糊的语法。我提供了一些实现它的实验性代码。我想避免让代码完整和成熟，因为那将涉及增加很多复杂性，这样更容易学习。网上关于 GLR 解析的信息不多，所以我将这篇文章和相关代码发布到公共领域。我唯一的要求是，如果你使用它，请在你的项目某处提及 honey the codewitch（那就是我！）。
概念化这个混乱的局面
GLR 代表 **G**eneralized **L**eft-to-right **R**ightmost derivation（广义从左到右最右推导）。这个缩写展开后有点笨拙，但它本质上的意思是，它从左到右、自底向上地处理模糊解析（广义）。“自底向上”从何而来？它在**R**ightmost derivation中有所暗示。
使用最右形式的解析器会创建右关联树，并从*叶子到根*工作。这比从根向下到叶子工作要不那么直观，但它是一种更强大的解析方式，与自顶向下解析不同，它可以处理左递归（和右递归），而左递归语法会导致自顶向下解析栈溢出或无限运行，具体取决于实现细节。无论哪种方式，这都是不可取的。从叶子开始向根构建解析树可以避免这个问题，并提供更强大的识别能力。缺点是，为它创建*转换语法*（可以将一种语言转换为另一种语言）要困难得多，而且由于向上构建树的反直觉性，通常使用起来有点笨拙。
广义 LR 解析器通过在底层使用任何标准 LR 解析器来工作。LR 解析器是一种下推自动机，这意味着它使用堆栈和状态机进行处理。LR 解析器本身是确定性的，但我们的 GLR 解析器不是。我们稍后会解决这个问题。首先，我们需要概述标准 LR 解析表和 GLR 解析表之间唯一的根本区别。如果你还不理解这个表，请不要担心。现在理解具体细节并不重要。
标准 LR 解析表/状态表如下所示
上面是使用这个工具生成的。
它看起来基本像一个电子表格。不过，请看奶油色单元格。看到有两个值了吗？这会导致 LR 解析表出现错误，因为它不能在每个单元格中保存两个值。GLR 解析表单元格是数组，因此它们可以保存多个值。上面的表格，尽管那些奶油色冲突单元格，对于 GLR 解析器来说是完全可以接受的。
任何时候出现这样的冲突，都是由于语法中的局部或全局歧义。换句话说，一个语法可能不模糊，但如果你有时只向前看一点点，那不足以消除歧义。可以说，语法中的生成是局部模糊的。否则，如果语法普遍模糊，那么它就是全局模糊。无论哪种情况，这都会导致多个值被输入到处理语法该部分的 GLR 表单元格中。
无论是局部还是全局歧义，都会导致 GLR 解析器在其遇到多值单元格时分叉其堆栈和任何其他上下文信息，并尝试以每种不同的方式进行解析。如果单元格中只有一个值，则不会发生分叉。如果有两个值，解析器会分叉其堆栈一次。如果有三个值，解析器会分叉其堆栈两次，依此类推。
由于我们正在尝试多种解析路径，可以说我们的解析器是非确定性的。这会影响性能，对于 GLR 解析器，性能与正在运行的分叉数量成反比。此外，每个分叉都会导致一个新的解析树。请注意，对于高度模糊的语法，这种分叉可以是指数级的。你需要为这种歧义付出代价。
这是可以接受的，因为 GLR 解析旨在解析高度模糊的自然/人类语言，并且成本是内在的——在这种情况下是预料之中的，而且我认为 GLR 仍然是迄今为止最高效的广义解析算法，因为它只在需要时才变得非确定性。如前所述，GLR 解析器不会解析为单个解析树，而是返回模糊解析的所有可能解析树，再次强调，这就是处理歧义的方式，而标准 LR 解析器首先就不会接受模糊语法。
生成 LR 解析表
我们将从一个基本任务开始——从给定的语法创建像上面这样的解析表。对于任何非平凡的任务，你都无法手动生成这些表，所以不要费心尝试。如果你需要一个工具来检查你的工作，试试这个。它接受 Yacc 格式的语法，并可以使用各种 LR 算法生成解析表。
你可能需要阅读这篇文章来理解规则、语法和符号。虽然它是为教授 LL(1) 解析器而写的，但相同的概念，如规则、符号（非终结符和终结符）以及 FIRST/FOLLOWS 集也适用于这种解析方式。强烈建议你阅读它，因为它对上述所有内容进行了详尽的阐述。因为它本身就足以成为一篇文章，所以我在此省略了它。
让我们从 Stephen Jackson 在这里提供的一个关于生成这些表的优秀资源开始。我们将按照他的教程来生成我们的表。我用这个教程自学了如何生成这些表，教程说它们是 LALR(1) 算法，但我被告知这实际上是 SLR(1) 算法。我对两者都没有足够的了解，无法确定。幸运的是，这真的不重要，因为 GLR 可以在底层使用任何 LR 算法。唯一的规定是，表中出现的冲突越少，GLR 解析器的效率就越高。功能较弱的算法会产生更多的冲突。因此，虽然你可以将 LR(0) 用于 GLR 解析器，但由于所有局部歧义，它会显著降低性能。我提供的代码没有实现 LR(0)，因为没有充分的理由这样做。
让我们从链接页面向下半部分教程中的语法开始
- S → N
- N → V = E
- N → E
- E → V
- V → x
- V → * E
通常，第一个规则（0）/非终结符 S 是在表生成过程中创建的。我们用它来增强语法，并将其指向实际的起始符号，在本例中是 N，然后是输入结束标记（未显示）
话虽如此，我们将忽略这一点，直接使用现有语法。请注意，上述语法的终结符要么是小写字母，如“x”，要么是字面值，如“=”。我们通常会为这些终结符分配描述性名称（例如“equals”），但在这里这样也可以。
我们需要一种数据结构，它很像一个规则，但有一个重要的补充——一个索引属性，指示规则中的位置。例如，我们会使用两个这样的结构来表示上面的规则 0：
S → • N
S → N •
这个圆点表示规则中的一个位置。我们将每个数据结构称为一个 LR(0) 项，或者 `LR0Item`。上面第一个表示 N 是接下来要遇到的符号，而第二个表示 N 刚刚被遇到。我们需要生成这些项的集合。
我们从起始规则开始，创建一个像上面第一个那样的 `LR0Item`，圆点在 N 之前。现在，由于圆点在一个非终结符 (N) 之前，我们需要添加每个 N 规则，并在开头添加一个圆点。现在我们的项集（我们的 `LR0Item` 集合）看起来像这样
S → • N
N → • V = E
N → • E
到目前为止一切顺利，但我们还没完成，因为现在我们有两个新的 `LR0Item`，它们在一个非终结符（分别是 V 和 E）之前有一个圆点，所以我们必须为这两个规则重复上述步骤，这意味着我们的项集现在将看起来像这样
S → • N
N → • V = E
N → • E
E → • V
V → • x
V → • * E
现在我们的项集已完成，因为点号只出现在我们已经添加到项集中的终结符或非终结符之前。由于这是我们的第一个项集，我们将其称为项集 0 或 `i0`。
现在我们要做的就是将每个可能的输入**应用到项集，并增加接受规则的游标，从而创建其余的项集。别担心，这里有一个例子：
我们从给它一个 **x** 开始。在项集中，只有一个条目会接下来接受它，那就是倒数第二个 `LR0Item` - *V → • x*，所以我们将创建我们的下一个项集 `i1`，其结果是那个移动
** 我们不需要实际传递每个输入。我们只需要查看项集中已有的下一个终结符。对于 `i0`，下一个终结符是 **\*** 和 **x**。这些就是我们使用的输入。
V → x •
这是 `i1` 的单个条目。现在我们必须回到 `i0`，这次移动到 `*`，这会产生
V → * • E
这是项集 `i2` 目前的单个条目，但我们还没有完成。和之前一样，圆点在一个非终结符 **E** 之前，所以我们需要添加所有以 **E** 开头的规则。在这种情况下只有一个，即 *E → • V*，这使我们目前的项集如下
V → * • E
E → • V
请注意，当我们添加新项时，光标位于开头。再次，我们在规则 *E → • V* 中有一个圆点在一个非终结符之前，所以我们必须添加所有的 **V** 规则，这使我们得到了 `i2` 的最终项集
V → * • E
E → • V
V → • x
V → • * E
看，我们再次遇到了 `i0` 中的 *V → • x* 和 *V → • * E* 项！这可能会发生，也应该发生。它们是因为 *E → • V* 而被添加的。现在我们完成了，因为游标只在已添加的终结符或非终结符之前。
现在我们需要再次移动到 `i0`，这次是针对非终结符 `V`。移动到 **V** 产生了以下项集 `i3`
N → V • = E
E → V •
生成这些项集的另一个困难是重复项。必须检测重复的项集，并且不能重复它们。
总之，如果你遇到困难，这里是其余的项集
i4:
S → N •
i5:
N → E •
i6:
V → * E •
i7:
E → V •
i8:
N → V = • E
E → • V
V → • x
V → • * E
i9:
N → V = E •
生成这些项集有点棘手，可能比看起来更复杂，而且我还没有列出上面所有我们需要做的事情。在构建这些项集时，你需要创建某种项集之间的转换映射。例如，在 `i0` 上，我们可以通过 **x** 转换到 `i1`，通过 **\*** 转换到 `i2`。我们知道这一点是因为我们在创建 `i0` 项集时已经解决了这个问题。Stephen Jackson 的教程将其作为一个单独的步骤，但为了效率，我们希望将其合并到上面的步骤中。这既方便又高效。请记住检测和整理重复集。
现在，我要告诉你一个我一直保留到现在的秘密：上面的每个项集都代表状态机中的一个状态，而上面的转换是状态之间的转换。对于上面的语法，我们有 10 个状态，`i0` 到 `i9`。我是这样存储和呈现上述数据，作为状态机的：
sealed class LRFA
{
public HashSet<LR0Item> ItemSet = new HashSet<LR0Item>();
public Dictionary<string, LRFA> Transitions = new Dictionary<string, LRFA>();
// find every state reachable from this state, including itself (all descendants and self)
public ICollection<LRFA> FillClosure(ICollection<LRFA> result = null)
{
if (null == result)
result = new HashSet<LRFA>();
if (result.Contains(this))
return result;
result.Add(this);
foreach(var trns in Transitions)
trns.Value.FillClosure(result);
return result;
}
}
基本上，这允许你存储计算出的转换以及项集。字典将符号映射到 `LRFA` 状态。这个名字很难看，但它代表 LR 有限自动机，每个 `LRFA` 实例代表有限状态机中的一个状态。现在我们有了它，我们将对我们的算法进行一次快速操作，而不是运行状态机，我们将遍历它并创建一个新的语法，其中嵌入了状态转换。那是我们的下一步。
由于需要，下面的状态编号与上面的演示不同。我希望你能跟随链接中的相关教程，但下面的内容是程序生成的，我无法控制状态创建的顺序。
对于下一步，我们将遍历我们刚刚创建的状态机，遵循每个转换。从 `i0` 开始。在这里，我们从 `i0` 到每个转换，通过起始符号，到输入结束（在下面的语法中由 $ 表示），所以我们首先将 `0/S/$` 写为规则的左侧，这表示 `i0`，起始符号 **S** 和特殊的输入结束 **$**，因为没有实际的项集对应。从那里，我们只有一个转换要遵循，即在 **N** 上，它将我们引导到 `i1`，所以我们将其写为单个右侧 `0/N/1`，从而得到
0/S/$ → 0/N/1
那些符号名称有点丑，但这没关系，因为计算机喜欢它们，我发誓。说实话，我们需要它们有几个原因。第一，这将消除从规则到规则的转换歧义，因为现在我们为每个转换可能性都有了新规则；第二，我们稍后可以用它来获得表中一些先行信息，我们稍后会讲到。
接下来我们必须跟随 **N**，所以我们照做，并重复。请注意，我们在这里创建了两个左侧相同的规则。那是因为我们有两个转换。
0/N/1 → 0/V/2 2/=/3 3/E/4
0/N/1 → 0/E/9
我们只需在 `LR0Item` 的索引为 0 时执行此操作。这是我们所追求的
0/S/$ → 0/N/1
0/N/1 → 0/V/2 2/=/3 3/E/4
0/N/1 → 0/E/9
0/V/2 → 0/x/6
0/V/2 → 0/*/7 7/E/8
0/E/9 → 0/V/2
3/E/4 → 3/V/5
3/V/5 → 3/x/6
3/V/5 → 3/*/7 7/E/8
7/E/8 → 7/V/5
7/V/5 → 7/x/6
7/V/5 → 7/*/7 7/E/8
最后，我们可以开始制作解析表了。这些表通常足够稀疏，可以使用字典，尽管嵌套数组的矩阵也可以，只要你有更多的内存。
LR 解析器可以执行四种操作：移入（shift）、归约（reduce）、跳转（goto）和接受（accept）。前两种是主要操作，这也是 LR 解析器常被称为移入-归约解析器的原因。
解析表的创建不像 LL(1) 解析器那样简单，但我们已经取得了很大的进展。现在，如果你使用字典和字符串符号，对于直接的 LR 解析表，你可能需要像 `Dictionary
没错，一个字典数组，里面有一个元组，或者在 GLR 的情况下，一个字典数组，里面有一个元组集合。
现在，另一种方法，使用整数符号 ID，可以表示为 `int[][][]` 表示直接 LR，或 `int[][][][]` 表示 GLR。尽管效率高，但如此多的嵌套令人困惑，最好将这种形式用于生成的解析器。无论如何，你可以从基于字典的解析表创建这些数组。下面我们将使用字典形式。
用每个状态的一个元素初始化解析表数组。上面我们有 10 个状态，所以我们的声明看起来像 `new Dictionary
接下来，计算我们之前作为 `List
创建一个项集列表（`List
现在，对于闭包中的每个 `LRFA`，将其在闭包中的索引作为解析表的字典数组的索引。你做的第一件事是为该数组条目创建字典。
然后遍历该 `LRFA` 中的每个转换。对于任何符号，将其用作字典键。如果它是终结符，这将是一个“移入”操作；如果它是一个非终结符，则是一个“跳转”操作。要创建移入或跳转操作的元组，将 `RuleOrStateId` 设置为转换目标状态的索引。你可以通过对闭包列表使用 `IndexOf()` 来找到此索引。
现在，在循环中处理该 `LRFA` 时，扫描其项集，查找一个 `LR0Item`，其索引位于末尾，且关联规则的左侧是起始符号。如果找到，则在解析表中该关联状态的字典中添加一个条目，键为结束符号 ($)，值为一个元组，其中 `RuleOrStateId` 为 -1，`Left` 和 `Right` 都设置为 null。这表示一个“接受”动作。
现在我们需要填写归约。这可能有点复杂。还记得我们扩展的语法吗？现在是时候使用它了。首先，我们获取*那个*语法的 FOLLOW 集。这描述起来既不简单又冗长，所以我将具体的细节推迟到我之前链接的这篇文章中。项目包含一个 `FillFollows()` 函数，它会为你计算 FOLLOW 集。
现在你有了它们，你需要将语法中的每个扩展规则映射到其左侧的 FOLLOWS。我为此使用了一个字典，例如 `Dictionary
注意：对于像 A → 这样的空/零规则，你需要在下面稍作不同地处理它们。
现在，对于上面映射字典中的每个条目，你需要执行以下操作
获取规则及其最终编号**——最终编号是构成解析表的字典数组的索引（还记得那个东西吗？）。对于映射条目 `Value` 中 FOLLOW 项的每个条目，向解析表添加一个元组。要为此创建元组，只需将规则剥离为未扩展形式，找到该规则在语法中的索引，然后使用该索引以及规则的左侧和右侧作为元组中相应位置的值。例如，如果索引为 1 的规则是 *N → V = E*，那么元组将是 `(RuleOrStateId: 1, "N" , new string[] { "V", "=", "E" })`。现在，检查字典是否已经有此 FOLLOW 符号的条目。如果存在且相同，则没有问题。这可能会发生，但没关系。如果存在且不同，则这是一个冲突。如果现有元组表示移入，则这是一个*移入-归约*冲突。这并非解析杀手。有时，这些冲突是不可避免的，例如 C 家族语言中的悬空 else。通常，移入将优先。如果现有元组表示归约操作，则这是一个*归约-归约*冲突。这将使标准 LR 解析器停滞不前。对于 GLR 解析器，两种替代方案都将被解析。总之，如果这是一个 GLR 表并且元组已经存在，只需添加另一个元组。如果它是一个常规 LR 解析器，并且它是一个移入，只需选择一个动作（通常是移入）作为优先级，理想情况下向用户发出关于冲突的警告，但对于 GLR 则不然。如果前一个元组是归约，则发出错误，但对于 GLR 则不然。
** 对于空/零规则，你需要从规则的左侧获取最终编号。
我们做到了！这是大量工作，但现在我们有了一个可用的解析表。对于生产代码，你可能需要某种进度指示器，因为对于实际语法，此操作可能需要相当长的时间。
使用标准 LR(1) 进行解析
无论算法是 LALR(1)、SLR(1) 还是完整的 LR(1)，解析表在整体结构上都是相同的。GLR 解析表有一个重要的区别，即单元格是数组。
因此，对于 LR，我们的解析代码（GLR 除外）无论算法如何都相同。然而，由于 GLR 使用这些原则进行解析，我们将在此处介绍标准 LR 解析。
用 LR 进行解析有点复杂，但一旦你克服了一些相关的难点，整体上就很简单了。
你需要解析表、一个堆栈和一个词法分析器。词法分析器会为你提供带有符号、值以及通常行/位置信息的标记。如果词法分析器只报告符号 ID，你需要进行查找以获取符号，因此你至少还需要一个字符串数组。
解析表将使用以下指令指导解析器以及堆栈和输入的使用
- 移位：在我们的解析表中，由 (#,null,null) 元组（其中 # 是索引）表示。
- 将索引 # 压入堆栈。
- 读取输入中的下一个标记并将其存储。
- 归约：在我们的解析表中，由 (#,left,right) 表示（其中 # 是规则 ID，left 和 right 是规则符号）
- 向输出报告规则。
- 获取规则右侧的标记数量，并相应地从堆栈中弹出。
- 现在，堆栈顶部的数字表示一个新状态。从规则的左侧获取符号，并使用左侧作为字典中的输入标记，在新状态下查阅解析表。将你刚刚获得的值推到堆栈顶部。
- 接受：由 (-1,null,null) 表示。已接受解析并完成。
如果找不到条目，则为语法错误。
让我们回顾一下 Stephen Jackson 的伟大著作
让我们逐步完成解析 **_x = * x_** 的第一步。第一步是初始化堆栈并读取第一个标记，基本上是将 0 压入堆栈
| 输入 | 输出 | 堆栈 | 下一篇 |
| x = * x$ | 0 | 移入 1 |
我们在状态 0 中找到的第一个标记是 **x**，这表明我们必须移位到状态 1。1 被压入堆栈，我们前进到下一个标记。这导致我们得到以下结果
| 输入 | 输出 | 堆栈 | 下一篇 |
| x = * x$ | 0 | 移入 1 | |
| = * x$ | 0, 1 | 归约 4 |
当我们进行归约时，我们会报告归约所用的规则。规则 4，*V → x*，右侧有 1 个标记（**x**）。弹出堆栈一次，使其只剩下 0。在状态 0 中，V（规则 4 的左侧）的 goto 值为 3，所以我们向堆栈推入一个 3。这一步为我们的表增加了一行
| 输入 | 输出 | 堆栈 | 下一篇 |
| x = * x$ | 0 | 移入 1 | |
| = * x$ | 0, 1 | 归约 4 | |
| = * x$ | 4 | 0, 3 | 移入 8 |
这是整个过程
| 输入 | 输出 | 堆栈 | 下一篇 |
| x = * x$ | 0 | 移入 1 | |
| = * x$ | 0, 1 | 归约 4 | |
| = * x$ | 4 | 0, 3 | 移入 8 |
| * x$ | 4 | 0, 3, 8 | 移入 2 |
| x$ | 4 | 0, 3, 8, 2 | 移入 1 |
| $ | 4 | 0, 3, 8, 2, 1 | 归约 4 |
| $ | 4, 4 | 0, 3, 8, 2, 7 | 归约 3 |
| $ | 4, 4, 3 | 0, 3, 8, 2, 6 | 归约 5 |
| $ | 4, 4, 3, 5 | 0, 3, 8, 7 | 归约 3 |
| $ | 4, 4, 3, 5, 3 | 0, 3, 8, 9 | 归约 1 |
| $ | 4, 4, 3, 5, 3, 1 | 0, 4 | 接受 |
就其本身而言，这看起来用处不大，但我们可以轻松地用这些信息构建树。在这里，Stephen Jackson 解释了结果：
Stephen Jackson 写道在我们的示例 *x = * x* 中，我们得到输出 *4, 4, 3, 5, 3, 1*。回顾一下，我们将根据示例构造对象。
第一次归约 (r4) 发生时，我们刚刚输入了终结符 *x*。根据规则 4，`V → x`，x 映射到非终结符 V。因此我们有了第一个对象，*V(x)*。
第二次归约（r4）发生在输入整个字符串之后，这意味着我们将最后一个 *x* 转换为 V。这给了我们第二个对象，*V(x)*。此时我们可以将对象重新代入字符串，得到 *V(x) = * V(x)*。
归约 3 只是将最后一个 *V(x)* 映射到 *E(V(x))*. 得到 *V(x) = * E(V(x))*.。
剩余的映射是
- V(x) = V(* E(V(x)))
- V(x) = E(V( * E(V(x))))
- N(V(x) = E(V( * E(V(x)))))
- S(N(V(x) = E(V( * E(V(x))))))
这是一种笨拙的看待方式。但它展示了如何将 LR 解析方法映射到构造函数。如果我们给每个规则一个函数，那么如何生成代码就应该显而易见了。例如，*V(x)* 可以用来将标记 *x* 转换为 V 类型的一个对象。任何 E 类型的对象都是通过给构造函数一个 V 类型的对象来形成的。依此类推，直到我们通过给 S 类型的对象一个 N 类型的对象来创建 S 类型的对象，从而达到这个例子的最终结束。
GLR 解析
当然，使用 GLR 进行解析比上述方法更复杂一些，但至少它基于相同的原理。使用 GLR 时，最好制作一个总体的解析器类，然后将实际的解析任务委托给一个工作类。这样，你就可以通过生成多个工作线程来同时运行多个解析，这正是我们需要的。每个工作线程管理自己的堆栈、输入游标和任何其他状态。
真正的复杂之处不在于运行工作者，人们可能会这样想，而在于管理输入标记流。问题是，即使我们让它们同步运行，每个工作者可能处于与下一个工作者略微不同的位置，所以我们必须做的是创建一个*滑动窗口*来管理输入。窗口应在必要时扩展（当工作者在输入中彼此之间距离更远时）并在可能时收缩（例如当工作者被移除或工作者彼此靠近时）。我使用我的LookAheadEnumerator<Token>类来处理实际窗口的大部分簿记工作。其余的是确保窗口正确滑动——一旦所有工作者都向前移动/推进，计算每个工作者移动的次数。取所有这些中的最小值，并将主游标向前推进那么多。最后，更新工作者的输入位置，从其位置减去该最小值。我注意到许多其他 GLR 产品要求将整个输入加载到内存中（基本上作为 `string`），然后才能进行解析。如果那样做，这不会那么困难，但灵活性值得权衡。这样，你就可以直接从大型文件或网络流中进行解析，而无需担心。
对于大型文档来说，唯一的问题是您可能希望直接使用拉式解析器，而不是生成树，这可能会占用大量的内存。拉式解析器使用起来可能有点棘手，因为虽然它有点像 `XmlReader`，但它也会同时从不同的解析中读取，这意味着您每次 `Read()` 之后都必须检查 `TreeId`，以查看您当前正在处理哪个“树”。
总之，在实现此功能时，我们像以前一样使用解析表，但遇到同一单元格中的多个元组时除外。当我们找到多个元组时，我们必须为每个额外的元组“分叉”一个新的工作器，该工作器拥有自己的堆栈副本和自己的独立输入游标（通过 `LookAheadEnumerator
在生成解析树时有一个小问题，这与我们同时解析多棵树的事实有关。当解析器分叉一个工作器时（如存在尚未见过的新 `TreeId` 所指示），我们必须（类似于解析本身）克隆树堆栈以适应它。基本上，我们可能正在愉快地使用 `TreeId` 为 1 的工作器进行解析，并且已经构建了一棵部分树，突然我们分叉并开始看到 `TreeId` 为 2。当这种情况发生时，我们必须克隆 #1 的树堆栈，然后继续，并根据需要添加到每个树堆栈。最后，每个最终接受的树 ID 最终都是我们返回的解析树。
编写这个混乱的程序
我没有为您提供解析器生成器，而只是一个实验性解析器以及定义语法并从中生成解析器的功能。解析器生成器的工作方式相同，只是我们初始化解析器时使用的数组将由生成的代码产生。这会使事情变得更容易一些。
所有直接相关的代码都位于命名空间 **C** 下。其他命名空间提供与我们上面所做的事情不直接相关的支持代码。您会在项目中看到诸如 *LexContext.cs* 之类的文件，它在命名空间 **LC** 下将文本光标公开为 LexContext 类。我们用它来帮助解析我们的 CFG 文件，我们很快就会讲到，但这与我们上面探讨的表构建或解析无关，因为 CFG 文档是微不足道的，并且是用手动编写的解析器解析的。这里说的 CFG 文档，是指**C**ontext **F**ree **G**rammar 文档（上下文无关文法文档）。这对于 GLR 来说有点用词不当，因为 GLR 技术上也可以从有上下文的文法中解析，但它仍然具有常规 CFG 的所有属性，所以这个名称是没问题的，事实上它仍然是首选，因为所有适用于 CFG 的数学属性也适用于此处。
打开解决方案并导航到 IDE 中的“scratch”项目。这是我们用于摆弄解析器的游乐场。
现在我们来试试。创建一个新的 CFG 文档。由于我喜欢用 JSON 做示例，所以我们来为 JSON 定义一个，我们将其命名为 *json.cfg*
（该文档已随项目提供给您，以节省您的打字时间。）
json -> object | array
object -> lbrace rbrace | lbrace fields rbrace
fields -> field | field comma fields
field -> string colon value
array -> lbracket rbracket | lbracket values rbracket
values -> value | value comma values
value -> string | number | object | array | boolean | null
boolean -> true | false
太棒了，但现在怎么办？首先，我们需要将它加载到一个 `CfgDocument` 类中
var cfg = CfgDocument.ReadFrom(@"..\..\json.cfg");
cfg.RebuildCache(); // not necessary, but recommended
第二行不是必需的，但强烈建议使用，尤其是在处理大型语法时。任何时候更改语法，都需要重建缓存。由于我们不打算更改它，只是加载它并从中生成表，这意味着我们现在可以缓存它。
还有 `Parse()` 函数和 `ReadFromUrl()` 函数。 `ToString()` 完成了相关转换回上述格式（除了长格式，不使用 `|` ），而它的一个重载可以接受参数 "y"，这将使其生成 Yacc 格式的语法，用于像我之前链接的 JISON 可视化工具。
一个 `CfgDocument` 由 `CfgRule` 表示的 `Rules` 组成。在上面的场景中，我们从文件中加载了这些规则，但你可以自己添加、删除和修改它们。规则有一个左侧和右侧，它们由符号组成。同时，每个符号由一个字符串表示，其中保留的终结符符号 `#EOS` 和 `#ERROR` 由 `CfgDocument` 自动生成。使用文档来查询终结符、非终结符和规则。你还可以使用它来创建 FIRST、FOLLOW 和 PREDICT 集。所有这些都通过相应的 `FillXXXX()` 函数访问。如果你还记得，我们使用 FOLLOW 集来创建上面的 LR 和 GLR 解析表。这就是我们从哪里得到它们的地方，除了我们的 CFG 是一个扩展语法规则，就像之前看到的 *0/S/$ -> 0/N/1*。
这一切都很好，但我们真正追求的是什么呢？——解析表！还记得关于如何生成它们的冗长解释吗？我已将所有这些内容放在 *CfgDocument.LR.cs* 中，它提供了 `TryToLR1ParseTable()` 和 `TryToGlrParseTable()`。前一个函数不会生成真正的 LR(1) 表，因为那些表会非常庞大。相反，它接受一个参数，告诉我们想要哪种 LR(1) 族表。目前唯一的选项是 LALR(1) 的 `Lalr1`，但这正好适合我们。`TryToGlrParseTable()` 将提供我们所需的 GLR 表。
这些函数都会返回一个 `CfgMessage` 对象列表，可用于报告任何出现的警告或错误。对于 GLR 表创建，不会有任何警告或错误，因为即使是冲突的单元格（模糊语法）也是有效的，但我为了保持一致性仍然提供了它。遍历消息并报告它们，或者简单地将它们传递给 `CfgException.ThrowIfErrors()`，以便在任何消息为 `ErrorLevel.Error` 时抛出异常。输出值分别给出我们的 `CfgLR1ParseTable` 或 `CfgGlrParseTable`。现在我们有了这些，我们几乎有足够的信息来创建一个解析器。
为了解析，我们需要实现 `IEnumerable
回到更简单的事情。一个是我们通过简单调用 `FillSymbols()` 并将其转换为 `string[]` 获得的符号表。另一个是错误哨兵 (`int[]`)，这需要一些解释。在发生错误的情况下，解析器会努力继续解析，以便在一次遍历中发现所有错误。这说起来容易做起来难。我们使用一种简单的技术，称为“恐慌模式”错误恢复，这是一种局部错误恢复形式。这要求我们定义一个安全的结束点，以便在遇到错误时使用。对于像 C 这样的语言，这可能意味着 `;/semi` 和 `}/rbrace`，这是非常合理的。对于 JSON，我们将使用 `]/rbracket`、`,/comma` 和 `}/rbrace`。当发生错误时，我们会收集输入标记，直到找到其中一个，然后弹出堆栈，直到找到一个有效的哨兵状态或用完要弹出的状态。理想情况下，我们只将此方法用于标准 LR 解析器，而将某种形式的全局错误恢复用于 GLR 解析器。然而，后者并不简单，并且在此处未实现，尽管它会带来更好的错误处理。我们的 `errorSentinels` 数组将包含我们两个终结符在符号表中的索引。
最后，我们可以创建一个解析器。这是从头到尾的整个过程
var cfg = CfgDocument.ReadFrom(@"..\..\json.cfg");
cfg.RebuildCache();
// write our grammar out in YACC format
Console.WriteLine(cfg.ToString("y"));
// create a GLR parse table. We can use a standard LR parse table here.
// We're simply demoing the GLR parser
CfgGlrParseTable pt;
var msgs = cfg.TryToGlrParseTable(out pt);
// there shouldn't be any messages for GLR, but this is how we process them if there were
foreach(var msg in msgs)
Console.Error.WriteLine(msg);
CfgException.ThrowIfErrors(msgs);
// create the symbol table to map symbols to indices which we treat as ids.
var syms = new List<string>();
cfg.FillSymbols(syms);
// our parsers don't use the parse table directly.
// they use nested arrays that represent it for efficiency.
// we convert it using ToArray() passing it our symbol table
var pta= pt.ToArray(syms);
// now create our error sentinels. If this is an empty array only #EOS will be considered
var errorSentinels = new int[] { syms.IndexOf("rbracket"), syms.IndexOf("rbrace") };
// let's get our input
string input;
using (var sr = new StreamReader(@"..\..\data2.json"))
input = sr.ReadToEnd();
// now make a tokenizer with it
var tokenizer = new JsonTokenizer(input);
var parser = new GlrTableParser(pta, syms.ToArray(), errorSentinels,tokenizer);
// uncomment the following to display the raw pull parser output
/*
while(parser.Read())
{
Console.WriteLine("#{0}\t{1}: {2} - {3}",
parser.TreeId, parser.NodeType, parser.Symbol, parser.Value);
}
// reset the parser and tokenizer
tokenizer = new JsonTokenizer(input);
parser = new GlrTableParser(pta, syms.ToArray(), errorSentinels,tokenizer);
*/
Console.WriteLine();
Console.WriteLine("Parsing...");
Console.WriteLine();
// now for each tree returned, dump it to the console
// there will only be one unless the grammar is ambiguous
foreach(var pn in parser.ParseReductions())
Console.WriteLine(pn);
要尝试不同的语法，只需切换语法文件名、错误哨兵、词法分析器和输入即可。 *Test14.cfg* 是一个小的模糊语法，可用于测试。我建议使用诸如 `bzc` 这样的输入字符串。
总之，对于 JSON 语法和相关输入，我们得到
%token lbrace rbrace comma string colon lbracket rbracket number null true false
%%
json : object
| array;
object : lbrace rbrace
| lbrace fields rbrace;
fields : field
| field comma fields;
field : string colon value;
array : lbracket rbracket
| lbracket values rbracket;
values : value
| value comma values;
value : string
| number
| object
| array
| boolean
| null;
boolean : true
| false;
Parsing...
+- json
+- object
+- lbrace {
+- fields
| +- field
| +- string "backdrop_path"
| +- colon :
| +- value
| +- string "/lgTB0XOd4UFixecZgwWrsR69AxY.jpg"
+- rbrace }
同时，按照上面的建议对 Test14 执行操作会生成两棵解析树
%token a c d b z
%%
S : a A c
| a B d
| b A d
| b B c;
A : z;
B : z;
Parsing...
+- A
+- b b
+- A
| +- z z
+- #ERROR c
+- S
+- b b
+- B
| +- A
| +- z z
+- c c
第一个不好，因为它尝试了错误的归约——或者说，这次归约没有成功，但理论上，如果使用正确的语法并给定不同的输入字符串，它可能会成功。你会注意到错误恢复仍然很差，这仍在进行中。我正在尝试不同的技术来改进它，以便它在许多情况下无需清空堆栈即可继续。无论如何，我们的第二棵树导致了有效的解析。对于某些语法，由于模糊性，多棵树可能有效且无错误。对于某些输入，每棵树可能都有错误，但每棵树中的错误可能不同。弄清楚选择哪棵树不是 GLR 解析器的工作。它在很大程度上取决于你打算用它做什么。例如，对于 C#，由于语言的歧义，你可能会得到许多不同的树，但应用类型信息可以将树缩小到代码表示的单个有效树。
血腥的细节
`GlrTableParser` 将任务委托给 `GlrWorker`，后者本身实现了 LR(1) 解析器。我们为解析的每个路径生成一个这样的工作器。只有第一个工作器由 `GlrTableParser` 自身创建。之后，工作器在解析过程中自行创建。在每个分叉处，我们为每个替代路径创建一个新的工作器，这在高度模糊的语法中可能会导致指数级增长的 `GlrWorker` 创建，因此请确保你的语法紧凑以获得最佳性能。当我们在当前状态和位置的解析表单元格中存在多个条目时，我们就知道遇到了分叉。在这里，我们看到 `GlrWorker.Read()` 中的解析表查找。请注意粗体代码，以及它如何在第一个元组之后为每个元组生成更多工作器。
public bool Read()
{
if(0!=_errorTokens.Count)
{
var tok = _errorTokens.Dequeue();
tok.SymbolId = _errorId;
CurrentToken = tok;
return true;
}
if (_continuation)
_continuation = false;
else
{
switch (NodeType)
{
case LRNodeType.Shift:
_ReadNextToken();
break;
case LRNodeType.Initial:
_stack.Push(0);
_ReadNextToken();
NodeType = LRNodeType.Error;
break;
case LRNodeType.EndDocument:
return false;
case LRNodeType.Accept:
NodeType = LRNodeType.EndDocument;
_stack.Clear();
return true;
}
}
if (0 < _stack.Count)
{
var entry = _parseTable[_stack.Peek()];
if (_errorId == CurrentToken.SymbolId)
{
_tupleIndex = 0;
_Panic();
return true;
}
var tbl = entry[CurrentToken.SymbolId];
if(null==tbl)
{
_tupleIndex = 0;
_Panic();
return true;
}
int[] trns = tbl[_tupleIndex];
// only create more if we're on the first index
// that way we won't create spurious workers
if (0 == _tupleIndex)
{
for (var i = 1; i < tbl.Length; ++i)
{
_workers.Add(new GlrWorker(_Outer, this, i));
}
}
if (null == trns)
{
_Panic();
_tupleIndex = 0;
return true;
}
if (1 == trns.Length)
{
if (-1 != trns[0]) // shift
{
NodeType = LRNodeType.Shift;
_stack.Push(trns[0]);
_tupleIndex = 0;
return true;
}
else
{ // accept
//throw if _tok is not $ (end)
if (_eosId != CurrentToken.SymbolId)
{
_Panic();
_tupleIndex = 0;
return true;
}
NodeType = LRNodeType.Accept;
_stack.Clear();
_tupleIndex = 0;
return true;
}
}
else // reduce
{
RuleDefinition = new int[trns.Length - 1];
for (var i = 1; i < trns.Length; i++)
RuleDefinition[i - 1] = trns[i];
for (int i = 2; i < trns.Length; ++i)
_stack.Pop();
// There is a new number at the top of the stack.
// This number is our temporary state. Get the symbol
// from the left-hand side of the rule #. Treat it as
// the next input token in the GOTO table (and place
// the matching state at the top of the set stack).
// - Stephen Jackson, https://web.cs.dal.ca/~sjackson/lalr1.html
var state = _stack.Peek();
var e = _parseTable[state];
if (null == e)
{
_Panic();
_tupleIndex = 0;
return true;
}
_stack.Push(_parseTable[state][trns[1]][0][0]);
NodeType = LRNodeType.Reduce;
_tupleIndex = 0;
return true;
}
}
else
{
// if we already encountered an error
// return EndDocument in this case, since the
// stack is empty there's nothing to do
NodeType = LRNodeType.EndDocument;
_tupleIndex = 0;
return true;
}
}
请参阅前面关于运行解析的教程。看到我们最初如何抓取 `_tupleIndex` 给出的元组，然后将其重置为零了吗？那是因为我们只想*一次*采取备用路径。工作器只有在第一次被 `Read()` 时才采取备用路径，之后，它会为遇到的每个备用路径生成额外的工作器，这些工作器在初始 `Read()` 之后也会恢复到第一个路径，并为遇到的任何备用路径生成更多工作器，依此类推。是的，再次强调，这可能会产生指数级的工作器。这是算法的本质。遍历每个可能的路径需要对每个可能的选择进行指数级的访问。
另外请注意，我们如何报告在归约过程中使用的规则定义。这对于解析器的用户来说至关重要，以便能够将终结符与它们所属的规则匹配起来。它简单地存储为 `int[]`，其中索引零是左侧符号的 ID，其余是右侧符号的 ID。
另一个问题是从现有工作器创建新工作器。我们必须复制其堆栈和其他状态，并接收一个独立的输入游标和一个元组索引，以告诉我们在初始读取时选择哪条路径。在初始读取时，我们跳过例程的第一部分，这就是 `_continuation` 的用途——我们从中断的地方重新开始解析。这是接受现有工作器的工作器构造函数：
public GlrWorker(GlrTableParser outer,GlrWorker worker,int tupleIndex)
{
_Outer = outer;
_parseTable = worker._parseTable;
_errorId = worker._errorId;
_eosId = worker._eosId;
_errorSentinels = worker._errorSentinels;
ErrorTokens = new Queue<Token>(worker.ErrorTokens);
_tokenEnum = worker._tokenEnum;
var l = new List<int>(worker._stack);
l.Reverse();
_stack = new Stack<int>(l) ;
Index = worker.Index;
_tupleIndex = tupleIndex;
NodeType = worker.NodeType;
Id = outer.NextWorkerId;
CurrentToken = worker.CurrentToken;
unchecked { ++outer.NextWorkerId; }
_continuation = true;
_workers = worker._workers;
}
在这里，我们创建了新的工作器，使用一种笨拙但必要的方式来克隆堆栈——我真的应该使用我自己的堆栈实现来解决这个问题，但对于这段代码我没有。我们为工作器分配一个新的 ID，指示它是一个延续，复制我们的解析表和错误哨兵引用，并创建一个队列来保存我们需要报告的错误。这里没有显示，但 `_Outer` 实际上是一个包装 `_outer` 的属性，`_outer` 本身是一个 `WeakReference
这涵盖了我们工作器类的核心。现在让我们来看看委托给它的 `GlrTableParser`。主要地，我们关注做大部分工作的 `Read()` 方法
public bool Read()
{
if (0 == _workers.Count)
return false;
_workerIndex = (_workerIndex + 1) % _workers.Count;
_worker = _workers[_workerIndex];
while(!_worker.Read())
{
_workers.RemoveAt(_workerIndex);
if (_workerIndex == _workers.Count)
_workerIndex = 0;
if (0 == _workers.Count)
return false;
_worker = _workers[_workerIndex];
}
var min = int.MaxValue;
for(int ic=_workers.Count,i=0;i<ic;++i)
{
var w = _workers[i];
if(0<i && w.ErrorCount>_maxErrorCount)
{
_workers.RemoveAt(i);
--i;
--ic;
}
if(min>w.Index)
{
min=w.Index;
}
if (0 == min)
break;
}
var j = min;
while(j>0)
{
_tokenEnum.MoveNext();
--j;
}
for (int ic = _workers.Count, i = 0; i < ic; ++i)
{
var w = _workers[i];
w.Index -= min;
}
return true;
}
如果没有任何工作器，我们就完成了。然后，我们按循环方式递增 `_workerIndex`，并用它来选择当前要委托给所有当前工作器中的哪个工作器。对于每个工作器，从 `_workerIndex` 开始，我们尝试从下一个工作器 `Read()`，如果它返回 false，我们就将其从 `_workers` 中移除，并尝试下一个工作器。我们继续这个过程，直到找到一个读取成功的工作器，或者我们用完工作器。如果我们用完工作器，我们就返回 false。
现在，在成功 `Read()` 之后，我们检查所有工作器，通过检查它们的 `Index` 来判断它们在当前主游标上前进了多少。我们对所有工作器都这样做，因为有些工作器在上次 `Read()` 调用期间可能没有向前移动。无论如何，最小前进量是我们想要滑动窗口的量，所以我们将主游标增加那么多。接下来，我们通过从它们的 `Index` 中减去该最小值来修复所有工作器的 `Index`。最后，我们返回 true 以指示读取成功。
关于解析器，还有一件有趣的事情是 `ParseReductions()` 方法，它将从读取器返回树。当然，这些树比从拉式解析器获得的原始报告更容易处理。以下是该方法：
public ParseNode[] ParseReductions(bool trim = false, bool transform = true)
{
var map = new Dictionary<int, Stack<ParseNode>>();
var oldId = 0;
while (Read())
{
Stack<ParseNode> rs;
// if this a new TreeId we haven't seen
if (!map.TryGetValue(TreeId,out rs))
{
// if it's not the first id
if (0 != oldId)
{
// clone the stack
var l = new List<ParseNode>(map[oldId]);
l.Reverse();
rs = new Stack<ParseNode>(l);
}
else // otherwise create a new stack
rs = new Stack<ParseNode>();
// add the tree id to the map
map.Add(TreeId, rs);
}
ParseNode p;
switch (NodeType)
{
case LRNodeType.Shift:
p = new ParseNode();
p.SetLocation(Line, Column, Position);
p.Symbol = Symbol;
p.SymbolId = SymbolId;
p.Value = Value;
rs.Push(p);
break;
case LRNodeType.Reduce:
if (!trim || 2 != RuleDefinition.Length)
{
p = new ParseNode();
p.Symbol = Symbol;
p.SymbolId = SymbolId;
for (var i = 1; RuleDefinition.Length > i; i++)
{
var pc = rs.Pop();
_AddChildren(pc, transform, p.Children);
if ("#ERROR" == pc.Symbol)
break;
}
rs.Push(p);
}
break;
case LRNodeType.Accept:
break;
case LRNodeType.Error:
p = new ParseNode();
p.SetLocation(Line, Column, Position);
p.Symbol = Symbol;
p.SymbolId = _errorId;
p.Value = Value;
rs.Push(p);
break;
}
oldId = TreeId;
}
var result = new List<ParseNode>(map.Count);
foreach (var rs in map.Values)
{
if (0 != rs.Count)
{
var n = rs.Pop();
while ("#ERROR" != n.Symbol && 0 < rs.Count)
_AddChildren(rs.Pop(), transform, n.Children);
result.Add(n);
}
}
return result.ToArray();
}
这只是一种迭代解释解析结果的方法，就像 Stephen Jackson 上面所涵盖的那样，只不过他的是递归的，并且只处理一棵解析树。考虑到不同的树信息可能以任何顺序返回，以递归方式实现这一点将非常困难，甚至不可能。
敬请关注 GLoRy，一个将这段代码提升到新水平的解析器生成器，可以生成几乎所有可解析内容的解析器。
历史
- 2020年2月18日 - 初次提交