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
> Grammatica-users@nongnu.org
> http://lists.nongnu.org/mailman/listinfo/grammatica-users
_______________________________________________
Grammatica-users mailing list
Grammatica-users@nongnu.org
http://lists.nongnu.org/mailman/listinfo/grammatica-users
