Re: [Grammatica-users] Lookahead feature?

[Per Cederberg]

I like the idea of LL(*) grammars. Might be a nice project
for a new and improved version of Grammatica. Especially
since the ANTLR source code can be studied for good ideas
and (probably) a quality implementation.

> BTW: What is the best way to start debugging a grammar
> that makes Grammatica think about it for more than 1
> hour on a recent desktop computer?

I didn't understand the question above. Is there some
word missing?

Cheers,

/Per

On wed, 2005-09-07 at 20:09 +0200, Thomas Moschny wrote:
> On Sunday 04 September 2005 22:43, Per Cederberg wrote:
> > Well, the nicer way to rewrite the grammar would be like
> > this I think:
> >
> > Goal = a+ AorB;
> > AorB = A | B ;
> > A    = b ;
> > B    = c ;
> 
> It's a bit nicer, yes, but this sort of transformation can be very tricky in 
> a 
> bigger grammar, say for example, one for the Java language.
> 
> Imagine a rule of this sort:
> Identifier = ID ("." ID)*; 
> and Identifier's all over your grammar. You'll have to do a lot of 
> transformations, and at the end, the grammar becomes overly complicated.
> 
> > The root problem isn't solvable by an LL parser, as the
> > number of needed look-ahead tokens is possibly infinite.
> > [...]
> > The issue also goes away if you use an LR parser generator.
> > But then again, those come with another set of issues that
> > you might not want to handle... :)
> 
> Exactly. That was the reason why I was looking for an LL-style parser 
> generator :)
> 
> Meanwhile, I searched a bit around, and found some approaches to this sort of 
> problems. Terence Parr, author of ANTLR, has some nice thoughts on what he 
> calls LL(*)-parsing here:
> http://www.antlr.org/workshop/ANTLR2004/proceedings/LL-star.pdf
> A mechanism like that would be really nice to have in Grammatica.
> 
> Other interesting approaches are "specificity parsing" (see the metafront 
> project, http://www.brics.dk/metafront) and "packrat parsing" (see e.g. the 
> Rats! parser generator, http://www.cs.nyu.edu/rgrimm/xtc/rats.html). Both use 
> linear time algorithms, I think.
> 
> BTW: What is the best way to start debugging a grammar that makes Grammatica 
> think about it for more than 1 hour on a recent desktop computer?
> 
> Regards,
> Thomas
> _______________________________________________
> Grammatica-users mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/grammatica-users