我正在尝试实现 Warshall 算法来快速计算 LR(1) 闭包。
我想我明白 LR(0) 是如何工作的:
A → B • C A → B • C 开始的“过渡”至 C → • D 问题是，LR(1) 需要计算前瞻，我不知道如何将它们合并到算法中。
在我看来，即使我知道任何给定 LR 项的传递闭包，我仍然需要通过所有相同的计算来确定每个项的前瞻集是什么。
甚至可以使用 Warshall 的算法来计算规范的 LR(1) 闭包，还是只能用于更受限制的情况(如 LR(0)、SLR(1) 等)？
最佳答案
我认为您不能为此使用 Warshall 的算法，因为每次添加新项目时，您可能都必须添加其他项目。这是一个迭代过程。有向图或连接矩阵会不断变化。我可能是错的。我使用迭代过程计算了 LR(1) 项集的闭包，同时保留了已包含在闭包集中的一组项。你可以下载我的LRSTAR Parser Generator并且您可能决定不需要编写自己的解析器生成器。注意:我使用 DeRemer 论文中的 Digraph 算法而不是 Warshall 算法来计算前瞻集。见 list of papers implemented in LRSTAR .
关于parsing - 如何使用 Warshall 的传递闭包算法来确定规范的 LR(1) 解析器闭包？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17002542/