Re: [Grammatica-users] Lookahead feature?

[Thomas Moschny]

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

pgpR2oXF2Xy_X.pgp
Description: PGP signature