Re: LR(1) paser generator based on Pager's algorithm

[Joel E. Denny]

On Sun, 1 Apr 2007, Xin Chen wrote:

> > > shift/shift conflict.
> > 
> > I assume that's a typo.
> 
> No this is not a typo. If you read my short report comparison.doc, 

Where is that?  Sorry, if you attached it, it may have been stripped.  I 
did get your conf.jpg though.  Renaming the file to something like 
comparison.bogus often works.

> > > As for Dr. Pager's algorithm, I guess it can be patched like 
> > this: in 
> > > grammars where precedence rule is used to solve shift/reduce 
> > conflict, 
> > > combine two states iff they are weakly compatble AND none has a 
> > > shift/reduce conflict.
> > 
> > So, if we decide we can't merge them, how many predecessor states 
> > will we 
> > have to split in order to successfully separate the merged 
> > lookaheads?  
> 
> In this case, based on your example, we just don't merge states 5 and 7

Sure.

> In my impression, this can intuitively 
> cover all such cases, and this problem is already solved. A strict proof 
> may be needed. Then as Knuth said, be alerted, since "I have proved it, 
> but did not try it"..

Here's a counter-example:

  S: 'a' A 'a'
   | 'b' A 'b'
   ;
  A: 'a' 'a' 'a'
   | 'a' 'a'
   ;

Here's the additional itemset that must be split:

  A: 'a' . 'a' 'a' ['a' 'b']
   | 'a' . 'a'     ['a' 'b']

> > Pager's lane-tracing algorithm proposes splitting after 
> > constructing LR(0) 
> > states, but supposedly that's much slower.

Sorry, never mind the "slower" part as it seems I got a few papers 
confused.

> I didn't look at that paper carefully although I do have a copy. It may 
> be interesting to actually implement it to see the performance. As I 
> tried the original Knuth LR(1) algorithm is running pretty fast, you 
> just need to find the proper data structure. But according to page 261 
> of this "general practical method" paper, this general practical method 
> is easier to understand conceptually and easier to implement.

Yes, I found the lane-tracing algorithm harder to understand.  I'll need 
to read it again to see how it might be adapted to solve my problem.

> Besides 
> Dr. Pager's work, the re is another algorithm by David Spector (proposed 
> around 1981, then refined in 1988), which is similar to the lane-tracing 
> algorithm in that it splits from LR(0) state machine. In his 1988 paper 
> David Spector mentioned about Pager's "general practical method", and 
> interestingly stated that "unfortunately it is too slow".

I had looked through some of Spector's papers, and I believe this is the 
statement that I somehow remembered as a comparison between Pager's own 
algorithms.  Thanks.

In any case, it seems odd to me that my issue might never have been 
addressed before.  Perhaps experts rarely write such tortured grammars, 
and perhaps novices rarely recognize such a subtle problem.  I need to 
look harder through the literature.