Left recursive ANTLR grammar

Question

I have written a grammar but getting a left recursive error.

grammar Lang;

options
{
    output  = AST;
    language    = C;
    ASTLabelType= pANTLR3_BASE_TREE;
    backtrack   = true;
}

start   : primary_expression+
    ;

primary_expression
                : '{' expression '}'
                | expression ',' expression
                ;

expression
                : logical_or_expression
                | logical_or_expression '?' expression ':' expression
                | logical_or_expression '?' ':' expression
                | logical_or_expression '?' expression
                ;

logical_or_expression
                : logical_and_expression
                | logical_and_expression '|' logical_or_expression
                ;

logical_and_expression
                : primary_expression
                | primary_expression '&' logical_and_expression
                ;

I am getting the following error:

[12:41:35] error(210): The following sets of rules are mutually left-recursive [primary_expression, logical_and_expression, logical_or_expression, expression]
[12:41:35] Aborting because the following rules are mutually left-recursive: [[Lang.primary_expression,index=2,line=19], [Lang.logical_and_expression,index=5,line=36], [Lang.logical_or_expression,index=4,line=31], [Lang.expression,index=3,line=24]]

---

Corrected grammar

grammar Lang;
options 
{
    // Note that in the C implementation, all implementations of trees and
    // adaptors pass around pANTLR3_BASE_TREE, which contains a super pointer
    // to your own implementation of a tree node and tree and so on. Hence
    // the node type is ALWAYS pANTLR3_BASE_TREE and there is no need to define
    // the type (the definition is silently ignored if you leave it there)
    //
    //output    = AST;
    language    = C;
    //ASTLabelType= pANTLR3_BASE_TREE;
    backtrack   = true;
}

start   : primary_expression+
    ;

primary_expression
                : '{' expression '}'
                | expression ',' expression
                ;

expression
                : logical_or_expression
                | logical_or_expression '?' expression ':' expression
                | logical_or_expression '?' ':' expression
                | logical_or_expression '?' expression
                ;

logical_or_expression
                : logical_and_expression
                | logical_and_expression '|' logical_or_expression
                ;

logical_and_expression
                : STRING
                | STRING '&' logical_and_expression
                ;

/* We're going to ignore all white space characters */
WS  
    :   (' ' | '\t' | '\r'| '\n') {$channel=HIDDEN;}
    ;

STRING
    :   ('a'..'z' | 'A'..'Z' | '0'..'9' | '_')+
    ;

Salbu

I am using antlrworks-1.4.3.jar. – Salbu

With v4 the error remains same: – Salbu

C:\Users\agupta\Desktop>java -cp antlr-4.0-complete.jar org.antlr.v4.Tool Lang4.g error(119): Lang4.g::: The following sets of rules are mutually left-recursive [primary_expression, logical_and_expression, expression, logical_or_expression] – Salbu

As I told, I am new to grammars, so this must be the mistake. Can you suggest me how to correct this. I just want a grammar to handle the following => "," "{" "}" "?:" "|" "&" – Salbu

Thanks for the hint :). I have corrected the grammar by adding the terminals and generated the code. – Salbu

Answer 1

Antlr 4 can handle direct left recursive, but can not cope with indirect left recursive. In the first case, "primary_expression" and "logical_and_expression: primary_expression ..." formed indirect left recursive. But now antlr4 can not generate 'c' codes.

grammar test3;

options
{
    language    = Java;
}

start   : 
    expression+
    ;

expression : 
    primary_expression
    | expression '&' expression
    | expression '|' expression
    | expression '?' expression ':' expression
    | expression '?' expression 
    | expression '?' ':' expression 
    | expression ',' expression
    | '{' expression '}'
    ;

primary_expression : // variable or constant definition, such as
    VARIABLE 
    | NUMBER
    ;
VARIABLE :
    ('A'..'Z')+
    ;

NUMBER :
    ('0'..'9') +
    ;

Myeloid