[antlr-interest] Working around the LALL(k) vs. LL(k) problem ?

[Matthew Ford]

It depends what you mean by "ambiguous".
I assume you mean for some given k lookahead the grammar is not "ambiguous".
But you still have to decide what value of k you need and this may change as
your grammar evolves.

Ideally I would like a language that is not "ambiguous" with a lookahead of
1 token.  However as I designed the language for ease of use by the user
(rather then the parser) I found this was not possible.

I think the Antlr's  (   )=> solution is very good.
matthew
----- Original Message -----
From: "Randall Nortman" <antlr-list at wonderclown.com>
To: <antlr-interest at yahoogroups.com>
Sent: Thursday, March 21, 2002 10:11 AM
Subject: Re: [antlr-interest] Working around the LALL(k) vs. LL(k) problem ?


> On Wed, Mar 20, 2002 at 10:03:18AM -0800, mzukowski at bco.com wrote:
> > > -----Original Message-----
> > > From: Randall Nortman [mailto:antlr-list at wonderclown.com]
> > >
> > > I'm working on my first ANTLR grammar, and I keep getting bitten by
> > > the fact that ANTLR uses linear approximation of LL(k).  I'm wondering
> > > if there are any general strategies for avoiding or working around
> > > this problem.  Can predicates be used?
> [...]
> >
> > statement: (IDENTIFIER IDENTIFIER)=>variableDecl | expression;
> >
>
> Of course!  I was trying to put the predicate on variableDecl instead
> of statement.  Sorry, I should have figured that one out on my own.
>
> > > On a related note, I'm designing both the syntax of this language and
> > > the parser together, using ANTLR along the way to catch problems in my
> > > syntax.  However, I feel like I spend as much time trying to figure
> > > out why ANTLR doesn't like a rule as I do developing the syntax
> > > itself.  I never know if an error message from ANTLR is because my
> > > syntax is bad or because I'm just not representing it in a way that
> > > ANTLR likes.  Might there be a better tool for developing the grammar
> > > independent of the parser?  (I want to make sure I have a regular
> > > grammar, which can be parsed without referencing any semantic
> > > information such as symbol tables, so the tool should be able to
> > > validate this.)
> >
> > If you look at the generated code, it's usually pretty easy to figure
out
> > what antlr is trying to do.  What other problems have been on the antlr
side
> > instead of the bad syntax side?  I'm not familiar enough with other
tools to
> > recommend any alternatives.
>
> As another example, here's one of the things I ran into early on that
> confused me.  It was a case of '(A|B)|C' being different from
> 'A|B|C'.  The following testcase is an extreme simplification of the
> grammar I originally wrote that caused the problem:
>
>   test: (ID | paren) | ID paren;
>
>   paren: "(" test ")";
>
> As such, there is a nondeterminism on 'test'.  Remove the grouping
> parenthesis, and it works just fine.  This was very non-intuitive to
> me, and took many hours to track down.  (The situation was
> considerably more complex in real life, but this is what I eventually
> narrowed it down to.)
>
> I'm not knocking ANTLR at all; I think it's a wonderful system.  As I
> get used to the way it works, I'm having fewer and fewer problems.
> But what I ideally want in this stage of language design is to simply
> write straight EBNF (no predicates), and have something to analyze it
> and tell me if the grammar is ambiguous or not.  Once I'm sure I've
> got a good grammar, then I can worry about how to parse it.  Doing
> both at once is a little inconvenient.  (Not to mention that having
> redundant information, like the predicate above that solves my
> problem, clutters up the grammar, making it harder to read.)
>
> Thanks for the help.
>
> Randall Nortman
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>


 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/