Antlr4 Arithmetic Grammar Is Ignoring Order of Precedence (PEMDAS)

Viewed 37

Grammar Definition

In my understanding ANTLR4 support left recursion to respect order of precedence for arithmetic. With that said here's the grammar:

grammar Arithmetic;

arithmetic: arithmeticExpression;

arithmeticExpression:
    LPARAN inner = arithmeticExpression RPARAN                      # Parentheses
    | left = arithmeticExpression POW right = arithmeticExpression  # Power
    | left = arithmeticExpression MUL right = arithmeticExpression  # Multiplication
    | left = arithmeticExpression DIV right = arithmeticExpression  # Division
    | left = arithmeticExpression ADD right = arithmeticExpression  # Addition
    | left = arithmeticExpression SUB right = arithmeticExpression  # Subtraction
    | arithmeticExpressionInput                                     # ArithmeticInput;

arithmeticExpressionInput: NUMBER;

number: NUMBER;

/* Operators */
LPARAN: '(';
RPARAN: ')';
POW: '^';
MUL: '*';
DIV: '/';
ADD: '+';
SUB: '-';

/* Data Types */
NUMBER: '-'? [0-9]+;

/* Whitespace & End of Lines */
EOL: '\r'? '\n';
WS: [ \t]+ -> channel(HIDDEN);

Note: I've simplified the grammar for testing.

Input

5 + 21 / 7 * 3

Output Parse Tree

Output Tree

Problem

In the outputted parse tree starting at the arithmetic. You can see that the Order of Precedence is not following PEMDAS even though it's defined via left recursion in the grammar. This is also observed when debugging the visitor code generated by Antlr with the function call being VisitAddition.

I've google this and I can't see what I'm doing wrong compared to examples as they all look the same.

Environment

ANTLR Version: 4.11.1

Build Target: CSharp

.NET Project Packages:

  1. Antlr4BuildTasks@11.1.0
  2. Antlr4.Runtime.Standard@4.11.1
1 Answers

As mentioned in the comments by @sepp2k (Thank you).

The issue is with the grammar because both the multiplication, division, addition and subtraction into seperate OR rule lines. Essentially creating PEMDAS when it should be PE(MD)(AS).

Here's an example of the fixed grammar:

arithmeticExpression:
    arithmeticExpressionInput                                                           # ArithmeticInput
    | LPARAN inner = arithmeticExpression RPARAN                                        # Parentheses
    | left = arithmeticExpression operator = POW right = arithmeticExpression           # Power
    | left = arithmeticExpression operator = (MUL|DIV) right = arithmeticExpression #
        MultiplicationOrDivision
    | left = arithmeticExpression operator = (ADD|SUB) right = arithmeticExpression #
        AdditionOrSubtraction;

and now the outputted parse tree is much cleaner:

Fixed Grammar Pase tree

Related