How can I resolve this without using backtrack=true?

Question

I'm trying to make a grammar that doesn't have operator precedence, but requires that either you use one operator or enclose them in parenthesis. (Using test instead of id|int_literal etc and + instead of a list of valid operators here for simplicity). So for example:

test + test ///valid!
(test + test) + test ///valid!
(test + test) + (test + test) /// valid!
test + test + test /// invalid!

Is there any way to write a grammar for this that doesn't require backtrack=true? I don't think left-factoring really makes sense here and I'm not sure how a syntactic predicate would help.

Here's what I have (requires backtrack=true):

fragment
bexpr : 'test' | '(' cbebr ')';

fragment
cbexpr : bexpr '+' bexpr;

expr : bexpr | cbexpr;

Answer 1

You might want to look at How to remove global backtracking from your grammar.

The ambiguity lies in the fact that both alternatives of expr can start with a bexpr. You need to get rid of this ambiguity. The key lies in the observation that a + only occurs without parentheses if it is the entire expression. So we end up with:

expr : operand ('+' operand)?;
operand : '(' expr ')' | 'test';

In other words: if an operator expression occurs as an operand, then it must be enclosed in parentheses.