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

Matthew Ford Matthew.Ford at forward.com.au
Wed Mar 20 10:31:31 PST 2002

Randall try

          : (variableDecl) => variableDecl
          | expression;

This will look ahead as far as it needs to  to determine if the input is
variableDecl when Antlr sees (variableDecl)=>
and only take that branch if the input matches.  This is one of the
strengths of Antlr.

----- Original Message -----
From: "Randall Nortman" <antlr-list at wonderclown.com>
To: <antlr-interest at yahoogroups.com>
Sent: Thursday, March 21, 2002 4:49 AM
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
> 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/


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

More information about the antlr-interest mailing list