How to use Warshall's algorithm for transitive closure to determine canonical LR(1) parser closures?

Question

I'm trying to implement Warshall's algorithm to quickly compute LR(1) closures.

I think I understand how it works for LR(0):

• The nodes of the graph are LR items, like A → B • C
• The edges are "transitions" starting from A → B • C to C → • D

The trouble is, LR(1) requires computation of lookaheads, and I can't figure out how to incorporate them into the algorithm.
It seems to me that even if I know the transitive closure of any given LR item I still need to go through all the same computation just to figure out what the lookahead set for each item is.

Is it even possible to use Warshall's algorithm to calculate canonical LR(1) closures, or is it only possible for more restricted cases (like LR(0), SLR(1), etc.)?

Answer 1

I don't think you can use Warshall's algorithm for this, because every time you add a new item, you may have to add other items. It's an iterative process. The directed graph or connectivity matrix would keep changing. I could be wrong about this. I computed the closure of LR(1) item sets with an iterative process while keeping an array of items already included in the closure set. You can download my LRSTAR Parser Generator and you may decide that you don't need to write your own parser generator. Note: I used the Digraph algorithm from DeRemer's paper, instead of Warshall's algorithm, for computation of the look-ahead sets. See the list of papers implemented in LRSTAR.