Help with left grammar factoring to remove left recursion

Question

I have a small custom scripting language, and I'm trying to update it to be able to boolean expressions like a > 2 and a > 2 and (b < 3 or c > 5) . These are the brackets that I have here.

Here (edited from the original post based on the answer from @Bart Kiers) is the full grammar that detects the problem. This is a shortened version of my actual grammar, but a problem also arises here.

 grammar test; options { language = 'JavaScript'; output = AST; } statement : value_assignment_statement EOF ; value_assignment_statement : IDENT '=' expression ; value_expression : value_list_expression | IDENT ; value_list_expression : value_enumerated_list ; value_enumerated_list : '{' unary+ '}' ; term : LPAREN expression RPAREN | INTEGER | value_expression ; unary : ( '+' | '-' )* term ; mult : unary ( ('*' | '/') unary)* ; expression : mult ( ('+' | '-') mult )* ; boolean : boolean_expression EOF ; boolean_expression : boolean_or_expression ; boolean_or_expression : boolean_and_expression (OR boolean_and_expression)* ; boolean_and_expression : boolean_rel_expression (AND boolean_rel_expression)* ; boolean_rel_expression : boolean_neg_expression relational_operator boolean_neg_expression ; boolean_neg_expression : (NOT)? atom ; atom : LPAREN boolean_expression RPAREN //| expression ; relational_operator : '=' | '>' | '<'; LPAREN : '('; RPAREN : ')'; AND : 'and'; OR : 'or'; NOT : 'not'; IDENT : LETTER LETTER+; INTEGER : DIGIT+; WS : (' ' | '\n' | '\r' | '\t')+ { $channel = HIDDEN; }; fragment DIGIT : '0'..'9'; fragment LETTER : ('a'..'z' | 'A'..'Z'); 

My attempt to place boolean expressions in parentheses, such as a > 2 or (b < 3) , is on the comment line in the atom rule. When I uncomment this line and include it in the grammar, ANTLR gives me this error:

The [fatal] atom rule has a non-LL (*) solution due to recursive rule calls available from alts 1,2. Solve using left factoring or using syntactic predicates or using the backtrack = true parameter.

I would like to address this by deleting the recursion, but I cannot make the transition from the Wikipedia description on how to remove left recursion to my own things.

When using this grammar, I sometimes want to use statement as the root with input, for example abc = 2 + 3 , which assigns a value to a variable called abc. In other cases, I want to use grammar to evaluate an expression using boolean as the input root, for example abc > 3 and (xyz < 5 or xyz > 10) . When I tried using @Bart's answer as a model, it worked fine until I tried to combine the parts of the grammar used by statement with those used by boolean . They should both be able to use expression , but that I am stuck with this left recursion error.

So, how can I get around the parentheses and avoid the problem with left recursion?

Answer 1

Boolean expressions are the same as additive multiplicative expressions, and therefore should not be separated from them. Here's how to consider all types of expressions:

 grammar test; parse : expression EOF ; expression : or ; or : and (OR and)* ; and : rel (AND rel)* ; rel : add (('=' | '>' | '<') add)* ; add : mult (('+' | '-') mult)* ; mult : unary (('*' | '/') unary)* ; unary : '-' term | '+' term | NOT term | term ; term : INTEGER | IDENT | list | '(' expression ')' ; list : '{' (expression (',' expression)*)? '}' ; AND : 'and'; OR : 'or'; NOT : 'not'; IDENT : LETTER LETTER*; INTEGER : DIGIT+; WS : (' ' | '\n' | '\r' | '\t')+ { $channel = HIDDEN; }; fragment DIGIT : '0'..'9'; fragment LETTER : ('a'..'z' | 'A'..'Z'); 

which will analyze the input example:

 abc > 3 and (xyz < 5 or xyz > {1, 2, 3}) 

into the following parse tree: