CODEWITHSUNDEEP
recursionantlrll-grammarleft-recursion
Joe
Joe

Reputation: 2452

ANTLR failure due to left recursion. How to solve?

Here is a simple grammar for an SQL select statement

grammar SQL;
@rulecatch {
    //We want to stop parsing when SyntaxException is encountered
    //So we re-throw the exception
    catch (SyntaxException e) {
        throw e;
    }
}

eval 
    :  sql_query
    ;

sql_query
    : select_statement from_statement
    | select_statement from_statement where_statement
    ;

select_statement
    : 'select' attribute_list
    ;

from_statement
    : 'from' table_name
    ;

where_statement
    : 'where' attribute_name operator constant
    ;

attribute_list
    : '*'
    | attribute_name
    | attribute_name ',' attribute_list?
    ;

table_name
    : string_literal
    ;

attribute_name
    : string_literal
    ;

operator
    : '=' | '!=' | '>' | '>=' | '<' | '<=' 
    ;

constant
    : INTEGER
    | '"' string_literal '"'
    ;

fragment DIGIT: '0'..'9';
INTEGER: DIGIT+ ; 
fragment LETTER: 'a'..'z'|'A'..'Z';
string_literal: LETTER | LETTER string_literal;
WS : (' ' | '\t' | '\n' | '\r' | '\f')+  {$channel=HIDDEN;};

The Tool is nagging about the sql_query definition as well as the attribute_list definition. Honestly I do not see any left recursion in my code to start with.

Could anyone explain what's going on?

Upvotes: 0

Views: 61

Answers (1)

Bart Kiers
Bart Kiers

Reputation: 170148

No, ANTLR did not say your grammar is left recursive. It complained about the fact that some rules have non-LL(*) decisions due to recursive rule invocations. Rewrite the following rules as follows and you'll be alright:

sql_query
    : select_statement from_statement where_statement?
    ;

attribute_list
    : '*'
    | attribute_name (',' attribute_list?)?
    ;

Upvotes: 1

Related Questions