7

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.)?

user541686
  • 205,094
  • 128
  • 528
  • 886

1 Answers1

2

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.

  • 1
    +1 thanks! Actually (a long time later) I ended up not using any particular algorithm because the longer I looked at it, the less potential room I saw for improvement. I ended up making my own LR(k) parser generator, though it was pretty painful! (It works for every k, but it might take exponentially long in k depending on the grammar.) – user541686 May 13 '14 at 05:34