data-structures - 如何实现图结构堆栈？

Question

好的，所以我想做一个 GLR 解析器生成器。我知道存在这样的程序比我可能会做的更好，但我这样做是为了好玩/学习，所以这并不重要。

我一直在阅读有关 GLR 解析的文章，并且我认为我现在对它有了相当高的理解。但现在是开始做正事的时候了。

图结构堆栈 (GSS) 是 GLR 解析器中使用的关键数据结构。从概念上讲，我知道 GSS 是如何工作的，但到目前为止我所看到的资料都没有解释如何实现 GSS。我什至没有要支持的权威操作列表。有人可以为我指出一些很好的 GSS 示例代码/教程吗？谷歌到目前为止没有帮助。我希望这个问题不是太模糊。

Answer 1

首先，如果你还没有，你应该阅读 McPeak 关于 GLR 的论文 http://www.cs.berkeley.edu/~smcpeak/papers/elkhound_cc04.ps .这是一篇学术论文，但它提供了关于 GSS、GLR 以及用于实现它们的技术的很好的细节。它还解释了实现 GLR 解析器的一些棘手问题。

实现图结构堆栈分为三个部分。

一、图数据结构本身

二、堆栈

三、 GLR 对 GSS 的使用

你是对的，谷歌没有太大帮助。除非你喜欢阅读算法书籍，否则它们也没有多大帮助。

一、图数据结构

罗布关于“直接代表”的回答最容易实现。它很像一个链表，除了每个节点都有一个下一个节点的列表而不是一个。

该数据结构是有向图，但正如 McPeak 所述，GSS 可能具有 epsilon 语法的循环。

二、堆栈

图结构堆栈在概念上只是一个常规堆栈列表。对于明确的语法，您只需要一个堆栈。当出现解析冲突时，您需要更多堆栈，以便您可以同时执行两个解析操作并保持两个操作创建的不同状态。使用图形可以利用这些堆栈共享元素的事实。

了解如何首先使用链表实现单个堆栈可能会有所帮助。链表的头部是栈顶。将一个元素插入堆栈只是创建一个新的头部并将其指向旧的头部。从堆栈中弹出一个元素只是将指针移动到 head->next。

在 GSS 中，原理是相同的。推送一个元素只是创建一个新的头节点并将其指向旧的头。如果你有两个移位操作，你会将两个元素推到旧头上，然后有两个头节点。从概念上讲，这只是两个不同的堆栈，它们共享除顶部元素之外的每个元素。弹出一个元素只是通过跟随每个下一个节点将头指针向下移动堆栈。

三、 GLR 对 GSS 的使用

这是 McPeak 的论文很有用的地方。

GLR 算法通过合并具有相同状态元素的堆栈头来利用 GS​​S。这意味着一个状态元素可能有多个子元素。在归约时，GLR 算法必须从栈头探索所有可能的路径。

您可以通过维护每个节点的确定性深度来优化 GLR。这只是与堆栈中拆分的距离。这样您就不必总是搜索堆栈拆分。

这是一项艰巨的任务!祝你好运!