如何使用Warshall的算法进行传递闭包来确定规范的LR(1)解析器闭包？

Question

我正在尝试实现Warshall的算法来快速计算LR(1)闭包.

我想我理解LR(0)的工作原理:

• 图的节点是LR项,如A ? B • C
• 边缘是"过渡"从开始A ? B • C到C ? • D

问题是,LR(1)需要计算前瞻,我无法弄清楚如何将它们合并到算法中.
在我看来,即使我知道任何给定的LR项目的传递闭包,我仍然需要经历所有相同的计算,只是为了弄清楚每个项目的前瞻设置是什么.

甚至可以使用Warshall的算法来计算规范的LR(1)闭包,还是只能用于更受限制的情况(如LR(0),SLR(1)等)？

Answer 1

我认为你不能为此使用 Warshall 算法，因为每次添加新项目时，你可能都必须添加其他项目。这是一个迭代的过程。有向图或连接矩阵会不断变化。我可能是错的。我通过迭代过程计算了 LR(1) 项集的闭包，同时保留了闭包集中已包含的项数组。您可以下载我的LRSTAR 解析器生成器，并且您可能会决定不需要编写自己的解析器生成器。注意：我使用 DeRemer 论文中的有向图算法而不是 Warshall 算法来计算前瞻集。请参阅LRSTAR 中实现的论文列表。