antlr - Help with left factoring a grammar to remove left recursion -

antlr - Help with left factoring a grammar to remove left recursion -

i have little custom scripting language, , trying update allow boolean expressions such a > 2 , a > 2 , (b < 3 or c > 5). it's parenthetical expressions having problem here.

here (edited since original post based on reply @bart kiers) total grammar exhibits problem. pared-down version of actual grammar, problem occurs here too.

grammar test; options { language = 'javascript'; output = ast; } statement : value_assignment_statement eof ; value_assignment_statement : ident '=' look ; value_expression : value_list_expression | ident ; value_list_expression : value_enumerated_list ; value_enumerated_list : '{' unary+ '}' ; term : lparen look rparen | integer | value_expression ; unary : ( '+' | '-' )* term ; mult : unary ( ('*' | '/') unary)* ; look : 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 //| look ; relational_operator : '=' | '>' | '<'; lparen : '('; rparen : ')'; , : '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 effort accommodate parenthetical boolean expressions such a > 2 or (b < 3) in commented-out line in atom rule. when uncomment line , include in grammar, antlr gives me error:

[fatal] rule atom has non-ll(*) decision due recursive rule invocations reachable alts 1,2. resolve left-factoring or using syntactic predicates or using backtrack=true option.

i address removing recursion, can't seem create transition wikipedia description on how remove left recursion own stuff.

in using grammar, want utilize statement root input such abc = 2 + 3, assigns value variable named abc. other times want utilize grammar evaluate look boolean root input such abc > 3 , (xyz < 5 or xyz > 10). when tried utilize @bart's reply model, worked fine until tried merge parts of grammar used statement parts used boolean. should both able utilize expression, that's i'm stuck left recursion error.

so, how can both handle parentheses , avoid left recursion problem?

boolean expressions same additive- , multiplicative expression, , should hence not separated them. here's how business relationship types of expressions:

grammar test; parse : look eof ; look : or ; or : , (or and)* ; , : rel (and rel)* ; rel : add together (('=' | '>' | '<') add)* ; add together : mult (('+' | '-') mult)* ; mult : unary (('*' | '/') unary)* ; unary : '-' term | '+' term | not term | term ; term : integer | ident | list | '(' look ')' ; list : '{' (expression (',' expression)*)? '}' ; , : '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 parse illustration input:

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

into next parse tree:

antlr grammar left-recursion