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

[Xin Chen]

Joel,

That looks to be a valid counter-example. I think we indeed need to consider 
about splitting states before a conflict actually happens. Or we do combine, 
and when conflict occurs, use GLR or LR(2) to solve it. 

Or when the programmer has such a mysterious conflict, he has to rewrite his 
grammar until that conflict disappears. But that's not why we are here.

Xin

----- Original Message -----
From: "Joel E. Denny" <address@hidden>
Date: Tuesday, April 3, 2007 6:18 am
Subject: Re: LR(1) paser generator based on Pager's algorithm
To: Xin Chen <address@hidden>
Cc: Paul Hilfinger <address@hidden>, Akim Demaille <address@hidden>, 
address@hidden

> On Mon, 2 Apr 2007, Xin Chen wrote:
> 
> > Yeah, please think more about it to see if any counter example 
> can be 
> > found. BTW, I'm thinking about whether I can find a constructive 
> proof 
> > on this.
> 
> So this one takes a bit more work:
> 
>  S: 'a' A 'a'
>   | 'b' A 'b'
>   ;
>  A: 'a' 'a' B
>   ;
>  B: 'a'
>   | %prec 'a'
>   ;
> 
> You'll have to avoid the merge creating this item set:
> 
>  A: 'a' . 'a' B ['a' 'b']
> 
> It's harder to foresee the S/R conflict that the merge here creates 
> in its 
> successor.  Moreover, imagine if the productions for B were much 
> more 
> complex.  Imagine if A had other RHSs ending in other nonterminals.
> 
> By the way, here's an extended grammar that makes all productions 
> useful 
> so that Menhir (at least) reports no warnings:
> 
>  S: 'a' A 'a'
>   | 'b' A 'b'
>   | 'c' c
>   ;
>  A: 'a' 'a' B
>   ;
>  B: 'a'
>   | %prec 'a'
>   ;
>  c: 'a' 'a' 'b'
>   | A
>   ;
> 
> > For the short report comparison.pdf, I sent it to the Bison 
> > maintainers' email list. If you lost it, I think Akim can send 
> you one 
> > copy.
> 
> There's no message from you in the bison-maintainers archive.  
> Maybe it 
> was never approved.  Anyway, if it's important to our discussion 
> and you 
> don't want to post it publicly, you could always send it to me 
> privately.