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

Randall Nortman antlr-list at wonderclown.com
Wed Mar 20 09:49:56 PST 2002


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?

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

Any assistance or insight would be greatly appreciated.

Randall Nortman

 

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



More information about the antlr-interest mailing list