Xtext Grammar Ambiguities (Backtracking is not working)

Question

I am trying to use Xtext to design a simple language for operations on sets of numbers.

Here are some examples of strings in the language:

• {2,1+6} (A set of numbers 2 and 7)
• {1+3, 3+5} + {2..5} (A union of sets {4, 8} and {2, 3, 4, 5})

I am using the following grammar:

grammar org.example.Set with org.eclipse.xtext.common.Terminals

generate set "http://www.set.net/set"




SetAddition returns SetExpression:
    SetMultiplication ({SetAddition.left=current} '+' right=SetMultiplication)*     
;

SetMultiplication returns SetExpression:
    SetPrimary ({SetMultiplication.left=current} ('*'|'\\') right=SetPrimary)*
;

SetPrimary returns SetExpression:
    SetAtom | '(' SetAddition ')'
;

SetAtom returns SetExpression:
    Set | Range 
;

Set:
  lhs = '{' (car=ArithmeticTerm (',' cdr+=ArithmeticTerm)*)? '}'
;

Range:
    '{' lhs=ArithmeticTerm '.' '.' rhs=ArithmeticTerm '}'
;
ArithmeticTerm:
    Addition //| Multiplication
;

Addition returns ArithmeticTerm:
    Multiplication ({Addition.lhs=current} ('+'|'-') rhs=Multiplication)*
;

Multiplication returns ArithmeticTerm:
    Primary ({Multiplication.lhs=current} ('*'|'/'|'%') rhs=Primary)*
;

Primary returns ArithmeticTerm:
    ArithmeticAtom |
    '(' Addition ')'
;

ArithmeticAtom:
       value = INT 
;

When I execute MWE2 workflow, I get the following error:

error(211): ../net.certware.argument.language.ui/src-gen/net/certware/argument/language/ui/contentassist/antlr/internal/InternalL.g:420:1: [fatal] rule rule__SetAtom__Alternatives has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

I do have backtracking enabled in mwe2 file.

I have this fragment of code in it:

// The antlr parser generator fragment.
        fragment = parser.antlr.XtextAntlrGeneratorFragment auto-inject {
          options = {
              backtrack = true
          }
        }

And there is no other fragments that mention ANTLR in mwe2 file.

The version of Xtext I am using is Xtext 2.8.0 integrated in Full Eclipse available from Xtext Website.

Why does ANTLR suggest me to enable backtracking if it is already enabled? Is there anything wrong with my grammar?

Answer 1

The error stems from your syntax for

SetPrimary returns SetExpression:
    SetAtom | '(' SetAddition ')'
;

and

Primary returns ArithmeticTerm:
    ArithmeticAtom |
    '(' Addition ')'
;

which can be reduced to

SetPrimary returns SetExpression:
    ArithmeticAtom | '(' Addition ')' | '(' SetAddition ')'
;

Since Addition and SetAddition are indistinguishable with finite lookahead (both can start with an infinite number of opening ( ). Therefore you need backtracking in the first place - you may want to reconsider the syntax or the AST structure.

Anyway, please add the backtracking also to the XtextAntlrUiGeneratorFragment in your workflow.