[antlr-interest] can antlr handle some ambiguity, specifically this one...

Josh Scholar joshscholar at nightstudies.net
Thu Aug 9 13:29:01 PDT 2007


The problem is that PE is left recursive, and even with backtracking
on, Antlr won't accept left recursive grammars.  But it will
automatically rewrite the rule for you using EBNF iteration replacing
left recursion if you place the cursor on the rule and select the menu
item "Refactor->Remove Left Recursion".

So the grammar, in Antlr syntax starts as:

es      :        ce | pe | E;
ce      :        pe E;
pe      :        'n' | pe 'n';
E       :        'e';

and becomes:

es      :        ce | pe | E;
ce      :        pe E;
pe      :        ('n') ('n')*;
E       :        'e';

Note that rule names should not lower case in Antlr, that's reserved
for token names.

On 8/9/07, david shepherd <davidshepherd at rocketmail.com> wrote:
>  I have really enjoyed using ANTLR and ANTLRWorks, but have run into
>  problems because of the LL parsing technology.  I thought that
>  antlr should be able to parse:
>
>  ES -> CE | PE | E
>  CE -> PE E
>  PE -> n | PE n
>  E  -> e
>
>  because it can lookahead k tokens and decide to reduce ES -> CE or ES -> PE.
>  In practice, I can't get anltr to handle the ambiguity in ES -> CE | PE | E .
>
> It wants to always reduce to CE, even when PE is necessary.  I thought
> that the LL(*), or the * lookahead would allow it to parse 'n n e n',
> but it cannot parse this.
>
>  Am I doing something wrong, or is this a consequence of LL grammars?
>
>  Thanks,
>  David Shepherd
>  Postdoctoral Fellow at UBC
>
> PS-I
> have gotten an LR parser to parse this example, but the antlr and
> antlrworks environment is much preferred, if it can handle this issue.
>
>
>
>
>


More information about the antlr-interest mailing list