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

[Joel E. Denny]

On Fri, 6 Apr 2007, Xin Chen wrote:

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

What do you do if the previous state is one of the incomplete predecessors 
of the new state?  That is, what do you do about potential successor 
loops?

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