Search code examples
antlrantlr4abnf

How to remove left-recursion from grammar rules


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 ?


Solution

  • 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
     ;
    

    ?