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

[Richard Clark]

Hi David,

When you say:
> it can lookahead k tokens and decide
> to reduce ES -> CE or ES -> PE
it sounds like you're expecting ANTLR to look for the longest match
(a/k/a the best match). That's not automatically provided in ANTLR (it
takes the first unambiguous match it can.) What you want would require
trying the longer possible paths and backtracking if they don't fit.

You can add this backtracking yourself, either with syntactic
predicates or by enabling the backtracking option. In this case, it
sounds like you could resolve your issues by explicitly giving PE
precedence via a syntactic predicate:

es: (pe) => pe
   | ce
   | E
  ;

which means "try out pe speculatively. If it works, use it, otherwise
try the remaining options."

If you turn on backtracking globally, it implicitly adds these
predicates all over the place,  complicating the generated code. It's
considered good style to either enable backtracking ona  rule by rule
bacis or supply your own syntactic predicates.

BTW, I wasn't able to reproduce your problem fully as I suspect your
example grammar isn't quite what you intended. "PE -> n | PE n" is
left-recursive and reduces down to "PE -> n+", which is probably not
what you had in mind.

Take care,

 ...Richard


On 8/9/07, david shepherd <davidshepherd at rocketmail.com> wrote:
>
>  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 .