[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: Mon, 09 Apr 2007 18:09:55 -1000


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


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

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

reply via email to

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