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