好的，所以我想做一个 GLR 解析器生成器。我知道存在比我可能制作的更好的程序，但我这样做是为了娱乐/学习，所以这并不重要。
我一直在阅读有关 GLR 解析的内容，并且我认为我现在对它有了相当高的理解。但现在是开始做生意的时候了。
图结构堆栈 (GSS) 是 GLR 解析器中使用的关键数据结构。从概念上讲，我知道 GSS 是如何工作的，但到目前为止，我所看到的资料都没有解释如何实现 GSS。我什至没有要支持的权威操作列表。有人可以为我指出一些很好的 GSS 示例代码/教程吗？谷歌到目前为止没有帮助。我希望这个问题不要太含糊。
首先，如果您还没有阅读过，您应该阅读 McPeak 关于 GLR 的论文http://www.cs.berkeley.edu/~smcpeak/papers/elkhound_cc04.ps。这是一篇学术论文，但它提供了有关 GSS、GLR 以及用于实现它们的技术的详细信息。它还解释了实现 GLR 解析器的一些棘手问题。
您需要三个部分来实现图形结构的堆栈。
一、图数据结构本身
二、堆栈
三、GLR 对 GSS 的使用
你是对的，谷歌没有多大帮助。除非您喜欢阅读算法书籍，否则它们也不会有太大帮助。
一、图数据结构
Rob 关于“直接表示”的回答将最容易实现。它很像一个链表，除了每个节点都有一个下一个节点的列表，而不仅仅是一个。
此数据结构是有向图，但正如 McPeak 所述，GSS 可能具有用于 epsilon-grammars 的循环。
二、堆栈
图结构堆栈在概念上只是常规堆栈的列表。对于明确的语法，您只需要一个堆栈。当存在解析冲突时，您需要更多堆栈，以便您可以同时执行两个解析操作并保持两个操作创建的不同状态。使用图表可以让您利用这些堆栈共享元素的事实。
首先了解如何使用链表实现单个堆栈可能会有所帮助。链表的头部是栈顶。将元素压入堆栈只是创建一个新头并将其指向旧头。从堆栈中弹出一个元素只是将指针移动到 head->next。
在 GSS 中，原理是相同的。推送一个元素只是创建一个新的头节点并将其指向旧的头。如果您有两个移位操作，您会将两个元素推送到旧头上，然后有两个头节点。从概念上讲，这只是两个不同的堆栈，它们共享除顶部元素之外的每个元素。弹出一个元素只是通过跟随每个下一个节点将头指针向下移动到堆栈中。
三、GLR 对 GSS 的使用
这就是 McPeak 的论文值得一读的地方。
GLR 算法通过合并具有相同状态元素的堆栈头来利用 GSS。这意味着一个状态元素可能有多个孩子。在归约时，GLR 算法必须从栈头探索所有可能的路径。
您可以通过保持每个节点的确定性深度来优化 GLR。这只是与堆栈中拆分的距离。这样您就不必总是搜索堆栈拆分。
这是一项艰巨的任务！祝你好运！
你问的问题不是微不足道的。我看到了两种主要的方法：
直接代表。您的数据结构在内存中表示为节点对象/结构，其中每个节点在堆栈上都有一个指向其下方结构的引用/指针（也可以将引用设为双向）。这是列表和树通常在内存中表示的方式。在这种情况下它有点复杂，因为与树或列表不同，只需要维护对根节点或头节点的引用来跟踪树，这里我们需要维护所有引用的列表“顶级”节点。
邻接表表示。这类似于数学家喜欢思考图的方式：G = (V, E)。您维护一个边列表，由顶点索引，这些顶点是每条边的起点和终点。
第一个选项的优点是遍历可以更快，只要 GSS 不是太平。但是该结构稍微难以使用。您将不得不推出很多自己的算法。
第二种选择的优点是使用起来更直接。教科书中的大多数算法似乎都假设某种邻接表表示，这使得应用大量的图算法变得更容易。
一些资源：
邻接列表有多种类型，例如基于哈希表、基于数组等。维基百科邻接列表页面是一个很好的起点。
这是一个一直在努力解决同样问题的人的博客文章。代码是clojure，可能熟悉也可能不熟悉，但讨论值得一看，即使不熟悉。
我应该提到，鉴于这种模型的广泛应用，我认为我希望有更多关于表示有向无环图（或图结构化堆栈，如果您愿意）的信息。我认为还有空间找到更好的解决方案。