[Top][All Lists]
[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: |
Fri, 06 Apr 2007 11:11:51 -1000 |
I thought over this for a while. One can either split after merge, or avoid
merge in the first place.
To split after merge, indeed one needs to trace back to see which state is the
first merge point to be split. There may be complications when more than two
states are merged together, or when the successor of a merged state is merged
to a third state. In such cases which two of the three should we split or
should we split all three? It's hard to answer.
To avoid merge in the first place, if still use my proposed method, now the
task is to add the ability to forsee future conflicts. We don't need to look
back at precessors, just need to look down at successors. If there exists a
simple criteria based on current states' configurations and contexts, then it's
trivial, but we don't know this yet. Otherwise, the direct way is to generate
all successors for both states to check so before merging
. One may say it's too costly to do so, the current yacc and bison are using
BFS style of navigation to generate all the states and this not compatible. I
say we can change the BFS navigation to DFS navigation, then the procedure
becomes:
1) whenever a new states is found to be potentially compatible to a previous
state, the previous state already has all its successors ready, and it's
trivial to check its successors to see if a conflict exists,
2) we generate all successors for the new state to see if a conflict exists.
3.1) If the two states' successors have the same conflict or none has a
conflict then they can be combined, now we're just copying contexts and our
work of generating successors for the new state is not wasted, and this is what
we always need to do to combine two compatible states;
3.2) otherwise these two states cannot be combined, then just add all
successors of the new state into the parsing machine, and none of our work is
wasted.
What do you think about this?
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
> ;
>
- Re: LR(1) paser generator based on Pager's algorithm, (continued)
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/01
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/01
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/02
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/02
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/02
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/03
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
- Re: LR(1) paser generator based on Pager's algorithm,
Xin Chen <=
- Re: LR(1) paser generator based on Pager's algorithm, Joel E. Denny, 2007/04/07
- Re: LR(1) paser generator based on Pager's algorithm, Xin Chen, 2007/04/15
Re: LR(1) paser generator based on Pager's algorithm, Akim Demaille, 2007/04/15