[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
statement
: (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.
matthew
----- 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
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/
>
>
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list