[antlr-interest] Issue with backtracking - non determinism ?

Thibaut Colar tcolar at colar.net
Mon Jun 15 12:12:11 PDT 2009


Hello there, I've been learning and using ANTLR with online docs and the
book.

I've been witting the grammar for a new prog. Language called Fan, and
it's basically all working now, though that took quite some effort,
since I'm new to antlr, and the Fan syntax is fairly difficult.

For reference here is the current whole grammar:
http://svn.colar.net/Fan_antlr/src/Fan.g

Anyway, I have one issue left, I'm not sure exactly what to call it (non
determinism ?) or exactly how to resolve it.

I have a shorter subset of the grammar here to illustrate the problem
and debug it in antlrworks:
http://svn.colar.net/Fan_antlr/src/Test.g

The basic issue is as follow (Please refer to Test.g):

If I test my grammar with a ternary expression such as:
    "foo ? bar :  beer"   it 's fine
Now if I have:
    " foo ? bar : beer[0..2]     it fails

What's happening is that, antlr will interpret "bar:beer[0..2]" as a
list (of map type bar:beer), which is a valid match in the grammar,
however  it will then fail, because  the rest of the ternary
expression('else' case) is then missing (: expr)

It should interpret like this: expr(foo) '?' expr(bar) ':'
expr(list(beer[0..2]))  which would be a valid ternary then.

The issue is cause by the ':' being meaningful as both a map type
separator and a ternary separator, and I guess antlr is matching
whatever matches first.

However shouldn't ANTLR backtrack anyway once it sees it can't match the
rest of the ternary expr, or is bactracking just not gonna help since it
Did find a match for list already ?

How can i solve this?
1) It seem checking first for id's and for map/list last would solve the
issue, but in most other cases (not ternary expr) i actually want to
match the longest option first (map/list)

2) I was thinking of setting  a variable/state while "within" a ternary
expression and in this case try first with maps/list disabled(skipping
them), but apparently when backtracking is enabled the code generated by
ANTLR does NOT evaluate my variable (if state.bactracking==0) so it
won't do it.


Any help/ideas would be greatly appreciated.








More information about the antlr-interest mailing list