How to remove left-recursion from grammar rules

1
votes

The following set of antlr grammar lines gives me the error for number_operation & number_argument as given below

The following sets of rules are mutually left-recursive

number_funtion : COUNT LEFT_PAREN number_argument RIGHT_PAREN

number_operation : 
number_argument (number_operator number_argument)+ | LEFT_PAREN number_argument (number_operator number_argument)+ RIGHT_PAREN 
| prefix_operator number_argument | LEFT_PAREN prefix_operator number_argument RIGHT_PAREN;

number_argument : number_column | number_function | digit_constant | number_operation ;

In order to avoid the left recursion, modifying number_operation with all possible combinations of every element of number_argument can be done like below, however will result in a longer rule.

number_operation :
number_column (number_operator number_argument)+ | LEFT_PAREN number_column (number_operator number_column)+ RIGHT_PAREN
| prefix_operator number_column | LEFT_PAREN prefix_operator number_column RIGHT_PAREN
//and other combinations

Can someone suggest what is the best way to remove the left recursion here ?

1
antlrantlr4abnf
Internally, Antlr4 removes direct left-recursion. The general procedure to remove indirect left-recursion is to just unfold one rule into the other, then remove useless parentheses and reorder alts. If you have two rules that participate in indirect left-recursion, you end up with two rules after the transformation. In this case, I would insert the RHS of number_operation into the rule for number_argument. – kaby76

1 Answers

1
votes

How about something like this:

number_operation
 : number_operation (number_operator number_argument)+
 | number_argument_2 (number_operator number_argument)+
 | LEFT_PAREN number_argument (number_operator number_argument)+ RIGHT_PAREN
 | prefix_operator number_argument
 | LEFT_PAREN prefix_operator number_argument RIGHT_PAREN
 ;

number_argument
 : number_column
 | number_function
 | digit_constant
 | number_operation
 ;

number_argument_2
 : number_column
 | number_function
 | digit_constant
 ;

?