7

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

我了解它对 LR(0) 的工作原理:

  • 图的节点是LR 项,例如A → B • C
  • 边缘是从A → B • C到的“过渡”C → • D

问题是,LR(1) 需要计算前瞻,我不知道如何将它们合并到算法中。
在我看来,即使我知道任何给定 LR 项目的传递闭包,我仍然需要通过所有相同的计算来确定每个项目的前瞻集是什么。

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

4

1 回答 1

2

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

于 2014-05-13T05:17:27.313 回答