13
\$\begingroup\$

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"));
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ "Hello There Calculator", really? That's your title? I would have expected something much better from you, ducky! \$\endgroup\$ – Simon Forsberg Apr 24 '15 at 21:02
  • \$\begingroup\$ Best I could do @SimonAndréForsberg. It was my "Hello World" ANTLR project. Feel free to change it if you've got something better. \$\endgroup\$ – RubberDuck Apr 24 '15 at 21:03
  • \$\begingroup\$ Discussion continues in this chat room \$\endgroup\$ – rolfl Apr 29 '15 at 10:34
  • \$\begingroup\$ A bit old but, besides the discussion about ANTLR, (1/2)*3 == 1/(2*3) and the order of evaluation here doesn't matter. \$\endgroup\$ – Federico Nov 8 '16 at 1:18
  • 1
    \$\begingroup\$ Bit late on this one, but I feel the inherant need to point out that BEDMAS (order of evaluation) is very important. In the example Federico provided, is equivalent to saying 0.5 * 3 == 1 / 6 which is false. That is just evaluating the brackets portion as BEDMAS requires brackets be evaluated first. \$\endgroup\$ – Kraang Prime Apr 15 '17 at 19:47
8
\$\begingroup\$

First, I have to mention that I'm very happy that you chose to explore ! ...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.

\$\endgroup\$
  • 2
    \$\begingroup\$ It does come with an error listener "for free" actually. The ConsoleListener. You're right about leaving a comment there through. As for the name, I'm leaving it unless someone can come up with something better. I don't think ThrowingErrorListener is an improvement. It still starts with a verb (ish). \$\endgroup\$ – RubberDuck Apr 24 '15 at 20:43
  • 2
    \$\begingroup\$ Well I would have suggested ExceptionThrowingErrorListener but that seemed a bit... over-the-top ;) \$\endgroup\$ – Mathieu Guindon Apr 24 '15 at 20:46
  • \$\begingroup\$ I like ThrownExceptionErrorListener. Or SyntaxErrorListener. Or ErrorListener. \$\endgroup\$ – Millie Smith Apr 28 '15 at 0:43
4
\$\begingroup\$

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);
}
\$\endgroup\$
0
\$\begingroup\$

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);
\$\endgroup\$
  • 1
    \$\begingroup\$ context.GetText() simply gives a string representation of of the start- and end token of said context. It does not glue together any token, the parser will treat these tokens separately. I know I won't be able to convince you of this fact OP, but this remark is just for people who stumble upon this incorrect remark. Mat is correct in his last remark in the chat chat.stackexchange.com/rooms/23172/… \$\endgroup\$ – Bart Kiers May 3 '15 at 18:27
  • \$\begingroup\$ Right @BartKiers and in this case, the start and end of the context contains two tokens that get smushed together by my Visitor. Now, will you please undelete your answer so that I may give it the checkmark for future visitors? \$\endgroup\$ – RubberDuck May 3 '15 at 18:30
  • \$\begingroup\$ Let me rephrase a little bit. The GetText method is returning the two consecutive tokens together as one string, when it is sent through Int.Parse, it is interpreted as a single number. I understand perfectly well what is going on here @BartKiers, and that is exactly what I describe above. I resent the fact that you imply I don't understand what's happening and you've been totally unwilling to have a civil discussion about it. \$\endgroup\$ – RubberDuck May 3 '15 at 18:38
  • \$\begingroup\$ The expression 1+1 2-2 3*3 would trigger syntax errors for the rule compileUnit : expression EOF;. If you let ANTLR's default error recovery mechanism handle this, then odd things might happen, obviously. But using NUMBER inside a parser rule would not result in 1 2 being glued together as one token 12. I will stop now because you seems to be getting agitated again, and will probably soon be flagging these comments again. Best of luck. \$\endgroup\$ – Bart Kiers May 3 '15 at 18:47
  • \$\begingroup\$ I've not tried attaching my custom error listener to the parser. Maybe something is getting swallowed there that I'm not aware of. I'll look into it. Thanks. \$\endgroup\$ – RubberDuck May 3 '15 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.