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

[Xin Chen]

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
>   ;
>