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

[mzukowski at bco.com]

> -----Original Message-----
> From: Randall Nortman [mailto:antlr-list at wonderclown.com]
> Sent: Wednesday, March 20, 2002 9:50 AM
> To: antlr-interest at yahoogroups.com
> Subject: [antlr-interest] Working around the LALL(k) vs. 
> LL(k) problem?
> 
> 
> 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?  As an example, consider the
> following relatively simple grammar, which allows both simple
> arithmetic expressions and variable declarations:
> 
> ----- Begin Grammar
> block: ((statement)? ";")*; // Possibly empty statements, 
> delimited by ";"
> 
> statement: variableDecl | expression;
> 
> variableDecl: typeSpec IDENTIFIER (":=" expression)?; // 
> Optional initializer
> 
> typeSpec: IDENTIFIER;
> 
> expression: term ( ( "+" | "-" ) term)*;
> 
> term: factor ( ( "*" | "/" ) factor)*;
> 
> factor: IDENTIFIER | LITERAL | ("(" expression ")");
> ----- End Grammar
> 
> I get nondeterminism on the 'statement' rule, because the parser can't
> tell the difference between a variableDecl and an expression for an
> input of (IDENTIFIER IDENTIFIER ";").  Clearly, that should be parsed
> as a variable declaration, because an expression requires IDENTIFIERs
> to be separated by operators.  But because of linear approximation,
> ANTLR doesn't see that.  What's the best way to fix this problem?

statement: (IDENTIFIER IDENTIFIER)=>variableDecl | expression;

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

Monty

 

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