Hello There Calculator

Question

The open source project I work on uses Antlr4 pretty heavily, but I don't know much about it. I thought I would use April's Community Challenge as an opportunity to learn something about grammars, lexers, and parsers.

My calculator only handles integer multiplication, division, addition, and subtraction, but it does handle the order of operations correctly. Whitespace is stripped away, so it's optional, and the calculator will throw an ArgumentException if it's passed an expression that it doesn't understand.

Is there anything I could have done better? I do think I want to go back and add support for exponentiation and parenthesis later, but that's later.

GitHub repo here.

BasicMathGrammar.g4

grammar BasicMath;

/*
 * Parser Rules
 */

compileUnit : expression+ EOF;

expression :
    expression MULTIPLY expression #Multiplication
    | expression DIVIDE expression #Division
    | expression ADD expression #Addition
    | expression SUBTRACT expression #Subtraction
    | NUMBER #Number
    ; 

/*
 * Lexer Rules
 */

NUMBER : INT; //Leave room to extend what kind of math we can do.

INT : ('0'..'9')+;
MULTIPLY : '*';
DIVIDE : '/';
SUBTRACT : '-';
ADD : '+';

WS : [ \t\r\n] -> channel(HIDDEN);

IntegerMathVisitor.cs

class IntegerMathVisitor : BasicMathBaseVisitor<int>
{
    public override int VisitCompileUnit(BasicMathParser.CompileUnitContext context)
    {
        // There can only ever be one expression in a compileUnit. The other node is EOF.
        return Visit(context.expression(0));
    }

    public override int VisitNumber(BasicMathParser.NumberContext context)
    {
        return int.Parse(context.GetText());
    }

    public override int VisitAddition(BasicMathParser.AdditionContext context)
    {
        var left = WalkLeft(context);
        var right = WalkRight(context);

        return left + right;
    }

    public override int VisitSubtraction(BasicMathParser.SubtractionContext context)
    {
        var left = WalkLeft(context);
        var right = WalkRight(context);

        return left - right;
    }

    public override int VisitMultiplication(BasicMathParser.MultiplicationContext context)
    {
        var left = WalkLeft(context);
        var right = WalkRight(context);

        return left * right;
    }

    public override int VisitDivision(BasicMathParser.DivisionContext context)
    {
        var left = WalkLeft(context);
        var right = WalkRight(context);

        return left / right;
    }

    private int WalkLeft(BasicMathParser.ExpressionContext context)
    {
        return Visit(context.GetRuleContext<BasicMathParser.ExpressionContext>(0));
    }

    private int WalkRight(BasicMathParser.ExpressionContext context)
    {
        return Visit(context.GetRuleContext<BasicMathParser.ExpressionContext>(1));
    }

ThrowExceptionErrorListener.cs (This lets me throw exceptions on bad input.)

class ThrowExceptionErrorListener : BaseErrorListener, IAntlrErrorListener<int>
{
    //BaseErrorListener implementation
    public override void SyntaxError(IRecognizer recognizer, IToken offendingSymbol, int line, int charPositionInLine, string msg, RecognitionException e)
    {
        throw new ArgumentException("Invalid Expression: {0}", msg, e);
    }

    //IAntlrErrorListener<int> implementation
    public void SyntaxError(IRecognizer recognizer, int offendingSymbol, int line, int charPositionInLine, string msg, RecognitionException e)
    {
        throw new ArgumentException("Invalid Expression: {0}", msg, e);
    }
}

Calculator.cs

public static class Calculator
{
    public static int Evaluate(string expression)
    {
        var lexer = new BasicMathLexer(new AntlrInputStream(expression));
        lexer.RemoveErrorListeners();
        lexer.AddErrorListener(new ThrowExceptionErrorListener());

        var tokens = new CommonTokenStream(lexer);
        var parser = new BasicMathParser(tokens);

        var tree = parser.compileUnit();

        var visitor = new IntegerMathVisitor();

        return visitor.Visit(tree);
    }
}

Unit Tests

[TestClass]
public class EvaluateTests
{
    [TestMethod]
    public void OrderedOperation()
    {
        var expr = "1 + 6 - 2 * 3 / 2";
        // 2 * 3 = 6
        // 6 / 2 = 3
        // 1 + 6 = 7
        // 7 - 3 = 4
        Assert.AreEqual(4, Calculator.Evaluate(expr));
    }

    [TestMethod]
    [ExpectedException(typeof(ArgumentException))]
    public void BadInput()
    {
        var expr = "1 + 5 + 2(3)";
        int value = Calculator.Evaluate(expr);
    }

    [TestMethod]
    public void SimpleAddition()
    {
        Assert.AreEqual(2, Calculator.Evaluate("1 + 1"));
    }

    [TestMethod]
    public void RepeatedAddition()
    {
        Assert.AreEqual(10, Calculator.Evaluate("1 + 2 + 3 + 4"));
    }

    [TestMethod]
    public void SimpleSubtraction()
    {
        Assert.AreEqual(2, Calculator.Evaluate("4 - 2"));
    }

    [TestMethod]
    public void RepeatedSubtraction()
    {
        Assert.AreEqual(5, Calculator.Evaluate("10 - 3 - 2"));
    }

    [TestMethod]
    public void SimpleMultiplication()
    {
        Assert.AreEqual(4, Calculator.Evaluate("2 * 2"));
    }

    [TestMethod]
    public void RepeatedMultiplication()
    {
        Assert.AreEqual(8, Calculator.Evaluate("2 * 2 * 2"));
    }

    [TestMethod]
    public void SimpleDivision()
    {
        Assert.AreEqual(2, Calculator.Evaluate("4 / 2"));
    }

    [TestMethod]
    public void RepeatedDivision()
    {
        Assert.AreEqual(2, Calculator.Evaluate("8 / 2 / 2"));
    }
}

Answer 1

First, I have to mention that I'm very happy that you chose to explore antlr! ...looking at what you've done here, you now know more about Visitor and ErrorNode than I do!

But ANTLR aside...

Classes are internal unless specified otherwise; still it would be nice to be explicit about it, and stick that internal modifier in front of your internal classes.

I don't like the name you've chosen for ThrowExceptionErrorListener - it makes the type's name sound like a method, as throw is a verb, and class names should be nouns. How about ThrowingErrorListener?

I'm not sure about this line here:

lexer.RemoveErrorListeners();

You just instantiated it, does it come with error listeners for free? If so, that deserves a comment. If not, then that line could be removed.

Answer 2

You could take a page out of functional programming and shorten the visitors for the multiply, divide, subtract, and add:

public override int VisitAddition(BasicMathParser.AdditionContext context)
{
    return VisitHelper(context, (left, right) => left + right);
}

public override int VisitSubtraction(BasicMathParser.SubtractionContext context)
{
    return VisitHelper(context, (left, right) => left - right);
}

public override int VisitMultiplication(BasicMathParser.MultiplicationContext context)
{
    return VisitHelper(context, (left, right) => left * right);
}

public override int VisitDivision(BasicMathParser.DivisionContext context)
{
    return VisitHelper(context, (left, right) => left / right);
}

private int VisitHelper(BasicMathParser.ExpressionContext context, Func<int, int, int> apply)
{
    var left = WalkLeft(context);
    var right = WalkRight(context);

    return apply(left, right);
}

And in C# 6 it'll become:

public override int VisitAddition(BasicMathParser.AdditionContext context) =>
    VisitHelper(context, (left, right) => left + right);

I'm almost alright with not declaring local variables though. The function names are descriptive enough, especially knowing we're traversing a tree:

public override int VisitAddition(BasicMathParser.AdditionContext context)
{
    return WalkLeft(context) + WalkRight(context);
}

public override int VisitSubtraction(BasicMathParser.SubtractionContext context)
{
    return WalkLeft(context) - WalkRight(context);
}

public override int VisitMultiplication(BasicMathParser.MultiplicationContext context)
{
    return WalkLeft(context) * WalkRight(context);
}

public override int VisitDivision(BasicMathParser.DivisionContext context)
{
    return WalkLeft(context) / WalkRight(context);
}

Answer 3

From a now deleted answer by Bart Kiers.

You've given multiplication a higher precedence than division. Usually, these have the same precedence. I.e., the expression 1 / 2 * 3 is usually evaluated as (1 / 2) * 3 (from left to right), which is 1.5. But in your case, it will be evaluated as 1 / (2 * 3), which is 0.16666666666.

Also, your NUMBER rule matches the INT rule, meaning that INT could never become a token of its own (it cannot be used inside a parser rule). Whenever this happens, make that rule a fragment (see: https://stackoverflow.com/questions/6487593/what-does-fragment-means-in-antlr).

You're also probably not trying to match multiple expressions, but rather a single expression. I.e. compileUnit : expression+ EOF; should be compileUnit : expression EOF;.

And ANTLR4 supports more compact character classes. Instead of doing ('0'..'9'), you can use [0-9].

Here is a demo in Java (easily ported to C#) that shows a way to handle operator precedence properly:

grammar BasicMath;

compileUnit : expression EOF;

expression
    : expression op=( MULTIPLY | DIVIDE ) expression #mulExpression
    | expression op=( ADD | SUBTRACT ) expression    #addExpression
    | '(' expression ')'                             #parensExpression
    | NUMBER                                         #numberExpression
    ;

NUMBER : INT;

fragment INT : [0-9]+;

MULTIPLY : '*';
DIVIDE   : '/';
SUBTRACT : '-';
ADD      : '+';

WS : [ \t\r\n] -> channel(HIDDEN);

And a driver class to test it:

public class Main {

  public static void main(String[] args) throws Exception {
    String expression = "1 / 2 * 3";
    BasicMathLexer lexer = new BasicMathLexer(new ANTLRInputStream(expression));
    BasicMathParser parser = new BasicMathParser(new CommonTokenStream(lexer));
    Double value = new IntegerMathVisitor().visit(parser.compileUnit());
    System.out.println(expression + " = " + value);
  }
}

class IntegerMathVisitor extends BasicMathBaseVisitor<Double> {

  @Override
  public Double visitCompileUnit(@NotNull BasicMathParser.CompileUnitContext ctx) {
    return this.visit(ctx.expression());
  }

  @Override
  public Double visitParensExpression(@NotNull BasicMathParser.ParensExpressionContext ctx) {
    return this.visit(ctx.expression());
  }

  @Override
  public Double visitMulExpression(@NotNull BasicMathParser.MulExpressionContext ctx) {
    if (ctx.op.getType() == BasicMathLexer.MULTIPLY) {
      return super.visit(ctx.expression(0)) * this.visit(ctx.expression(1));
    } else {
      return super.visit(ctx.expression(0)) / this.visit(ctx.expression(1));
    }
  }

  @Override
  public Double visitAddExpression(@NotNull BasicMathParser.AddExpressionContext ctx) {
    if (ctx.op.getType() == BasicMathLexer.ADD) {
      return super.visit(ctx.expression(0)) + this.visit(ctx.expression(1));
    } else {
      return super.visit(ctx.expression(0)) - this.visit(ctx.expression(1));
    }
  }

  @Override
  public Double visitNumberExpression(@NotNull BasicMathParser.NumberExpressionContext ctx) {
    return Double.valueOf(ctx.NUMBER().getText());
  }
}

---

Which is all technically spot on and extremely good advice. However, changing expression+ EOF to expression EOF breaks the visitor, because calling context.GetText() "glues" together adjacent tokens that were previously separated by the white space. This results in 1+12-23*3, with no way to catch the error (to the best of my knowledge), because as far as the parser and lexer are concerned, there is no error. I overcome this issue by leaving the compileUnit rule unchanged and checking the number of expressions in my Calculator class, and throwing an exception if more than one expression was passed into the evaluate method.

var tree = parser.compileUnit();

var exprCount = tree.expression().Count;
if (exprCount > 1)
{
    throw new ArgumentException(String.Format("Too many expressions. Only one can be evaluated. {0} expressions were entered.", exprCount));
}

var visitor = new IntegerMathVisitor();

return visitor.Visit(tree);