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

[Xin Chen]

Joel,

I don't know besides just try and find out. I'll let you know if I have any new 
idea. 

Regards,
Xin

----- Original Message -----
From: "Joel E. Denny" <address@hidden>
Date: Saturday, April 7, 2007 8:44 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 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.
>