bison-patches
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

 From: Xin Chen Subject: Re: LR(1) paser generator based on Pager's algorithm Date: Tue, 03 Apr 2007 21:02:26 -1000

```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.

```

reply via email to

 [Prev in Thread] Current Thread [Next in Thread]