CODEWITHSUNDEEP
antlr4
Pape Traore
Pape Traore

Reputation: 83

The following sets of rules are mutually left-recursive in ANTLR

The expr and condition gives me this error, it seems that antlr see it like a possible infinite recursion loop. How can i avoid it?

query : relationName '<-' expr;

relationName : identifier ;

identifier : (LETTER | IDENTIFIER1 | IDENTIFIER2)+;

expr : atomicExpr
       | selection
       | projection 
       | renaming
       | union
       | difference
       | product
       | naturalJoin;

atomicExpr : relationName | expr;

selection : 'select' (condition) atomicExpr;

condition : conjunction ('||' conjunction)*;

conjunction : comparison ('&&' comparison)*;

comparison : operand op operand | condition;

Upvotes: 1

Views: 1052

Answers (1)

Mike Lischke
Mike Lischke

Reputation: 53337

The rule expr is indirect left recursive because it contains atomicExpr which also uses expr on the left hand side. However, atomicExpr is a pretty useless rule. By defining:

expr : relationName
       | selection
       | projection 
       | renaming
       | union
       | difference
       | product
       | naturalJoin;
selection : 'select' (condition) expr;

you will get exactly the same syntax, but without that recursion.

condition is a bit more difficult because the left recursion involves 3 rules (condition uses conjunction on the left hand side, which uses comparison, which uses condition again). You can resolve that by combining the separate rules into one:

condition:
    comparison
    | condition LOGICAL_AND condition
    | condition LOGICAL_OR condition
;
comparison: operand (op operand)?

LOGICAL_OR: '||';
LOGICAL_AND: '&&';

Precedence is ensured by the order of the alternatives. Later alts have a smaller precedence. And since this rule is recursive also on the right hand side, you don't need loops here.

Upvotes: 2

Related Questions