How to use the Warshall transitive closure algorithm to determine the canonical closures of the LR (1) parser?

Question

I am trying to implement the Warshall algorithm to quickly calculate LR (1) closures.

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

• Graph nodes LR elements , for example A → B • C
• Edges are “transitions,” starting from A → B • C to C → • D

The problem is that LR (1) requires the calculation of lookaheads, and I cannot figure out how to include them in the algorithm.
It seems to me that even if I know the transitive closure of any given LR element, I still need to go through all the same calculations to find out what for each element has the form.

Is it possible to use the Warshall algorithm to calculate the canonical closures of LR (1), or is this only possible for more limited cases (for example, LR (0), SLR (1), etc.)?

Answer 1

I do not think that you can use the Warshall algorithm for this, because every time you add a new element, you may have to add other elements. This is an iterative process. A directed graph or connectivity matrix will constantly change. I could be wrong about this. I calculated the closure of the LR (1) element sets using an iterative process, preserving the array of elements already included in the closure set. You can download my LRSTAR parser generator and decide that you don’t need to write your own parser generator. Note: I used the Digraph algorithm from the DeRemer article instead of the Warshall algorithm to calculate prediction sets. See the list of documents implemented in LRSTAR .