CODEWITHSUNDEEP
antlr
Heng Ye
Heng Ye

Reputation: 341

Mutually left recursive with simple calculator

When I attempt to compile my antlr4 calculator grammar, it turns out it is left recursive. I need to change it to make it correct.

I have tried rewriting the rules and using different parentheses locations but they all don't work. Here's my latest version of the error rules:

Parser:

expression: INT | DECIMAL | arithmetic;
arithmetic: expression OPERATION expression;

Lexer:

OPERATION: SUB | ADD | MULT | DIV;
SUB: '-';
ADD: '+';
MULT: '*';
DIV: '/';
DPOINT: '.';
INT: SUB? NUMBER+;
DECIMAL: SUB? NUMBER+ DPOINT NUMBER+;

I expect the compilation to be successful, but the following error occurs:

ANTLR Tool v4.4 (/tmp/antlr-4.4-complete.jar)
hZH.g4 -o /home/heng/workspace/Ultimate ZH Compiler/target/generated-sources/antlr4 -listener -no-visitor -encoding UTF-8
error(119): hZH.g4::: The following sets of rules are mutually left-recursive [expression, arithmetic]
1 error(s)

BUILD FAIL

How can I change my rules for the build to be successful?

Upvotes: 2

Views: 276

Answers (1)

Bart Kiers
Bart Kiers

Reputation: 170237

Inderect left recursive rules aren't supported, but direct left recursion is. So try this:

expression
 : expression OPERATION expression
 | INT 
 | DECIMAL
 ;

I'd not let the lexer match the - to a number, but let that be handled by the parser, like this:

expression
 : SUB expression
 | expression ( MULT | DIV ) expression
 | expression ( ADD | SUB ) expression
 | INT 
 | DECIMAL
 | OPAR expression CPAR
 ;

SUB: '-';
ADD: '+';
MULT: '*';
DIV: '/';
INT: NUMBER+;
DECIMAL: NUMBER+ '.' NUMBER+;
OPAR: '(';
CPAR: ')';

Also note that I gave * and / a higher precedence by moving them above + and -.

Upvotes: 3

Related Questions