Angel \”Java\” Lopez on Blog

September 10, 2010

Writing an Interpreter in .NET (Part 6)

Filed under: .NET, Programming Languages, Test-Driven Development — ajlopez @ 11:10 am

In this part of the series, I added many features: string processing, binary expressions, arithmetic expressions, parsing of these expressions using precedence and parenthesis.

The code can be download from InterpreterStep06.zip.

String processing

The lexer now can process strings, delimited with quotes, and recognizing escape characters. It supports multiline strings. Some tests (they are more in code):

        [TestMethod]
        public void ProcessSimpleString()
        {
            Lexer lexer = new Lexer("\"foo\"");
            Token token = lexer.NextToken();
            Assert.IsNotNull(token);
            Assert.AreEqual(TokenType.String, token.TokenType);
            Assert.AreEqual("foo", token.Value);
            Assert.IsNull(lexer.NextToken());
        }
        [TestMethod]
        [ExpectedException(typeof(LexerException), "Unclosed string")]
        public void RaiseIfStringIsUnclosed()
        {
            Lexer lexer = new Lexer("\"foo");
            Token token = lexer.NextToken();
        }

Binary and Arithmetic Expressions

I added a new abstract class (derived after the tests on a concrete one, BinaryArithmeticExpression):

BinaryExpression evaluates two expression, left and right, and apply the abstract operation:

    public abstract class BinaryExpression : IExpression
    {
        IExpression leftExpression;
        IExpression rightExpression;
        public BinaryExpression(IExpression leftExpression, IExpression rightExpression)
        {
            this.leftExpression = leftExpression;
            this.rightExpression = rightExpression;
        }
        public IExpression LeftExpression { get { return this.leftExpression; } }
        public IExpression RightExpression { get { return this.rightExpression; } }
        public object Evaluate(BindingEnvironment environment)
        {
            object leftValue = this.leftExpression.Evaluate(environment);
            object rightValue = this.rightExpression.Evaluate(environment);
            return Apply(leftValue, rightValue);
        }
        public abstract object Apply(object leftValue, object rightValue);
    }

I defined arithmetic operators (to expand in future steps):

    public enum ArithmeticOperator
    {
        Add,
        Subtract,
        Multiply,
        Divide
    }

BinaryArithmeticExpression uses Microsoft.VisualBasic.CompilerServices.Operators. Those helpers can add, subtract, multiply, divide two objects, detecting if they are real or integer numbers:

    public class BinaryArithmeticExpression : BinaryExpression
    {
        private ArithmeticOperator @operator;
        public ArithmeticOperator Operator { get { return this.@operator; } }
        public BinaryArithmeticExpression(IExpression leftExpression, IExpression rightExpression, ArithmeticOperator @operator)
            : base(leftExpression, rightExpression)
        {
            this.@operator = @operator;
        }
        public override object Apply(object leftValue, object rightValue)
        {
            switch (this.@operator)
            {
                case ArithmeticOperator.Add:
                    return Operators.AddObject(leftValue, rightValue);
                case ArithmeticOperator.Subtract:
                    return Operators.SubtractObject(leftValue, rightValue);
                case ArithmeticOperator.Multiply:
                    return Operators.MultiplyObject(leftValue, rightValue);
                case ArithmeticOperator.Divide:
                    return Operators.DivideObject(leftValue, rightValue);
            }
            throw new InvalidOperationException(string.Format("Unknow operator '{0}'", this.@operator));
        }
    }

Some test (more in code):

        [TestMethod]
        public void EvaluateAddExpression()
        {
            ConstantExpression leftExpression = new ConstantExpression(1);
            ConstantExpression rightExpression = new ConstantExpression(2);
            BinaryArithmeticExpression expression = new BinaryArithmeticExpression(leftExpression, rightExpression, ArithmeticOperator.Add);
            Assert.AreEqual(3, expression.Evaluate(null));
        }
        [TestMethod]
        public void EvaluateSubtractExpression()
        {
            ConstantExpression leftExpression = new ConstantExpression(1);
            ConstantExpression rightExpression = new ConstantExpression(2);
            BinaryArithmeticExpression expression = new BinaryArithmeticExpression(leftExpression, rightExpression, ArithmeticOperator.Subtract);
            Assert.AreEqual(-1, expression.Evaluate(null));
        }

Parser enhancements

The parser has new private methods ParseSimpleExpression, ParseFactorExpression:

Those are the implementation I wrote to satisfy the tests (more in code):

        [TestMethod]
        public void ParseAndEvaluateAddAndMultiplyExpression()
        {
            Parser parser = new Parser("1+2*3");
            IExpression expression = parser.ParseExpression();
            Assert.IsNotNull(expression);
            Assert.IsInstanceOfType(expression, typeof(BinaryArithmeticExpression));
            Assert.AreEqual(7, expression.Evaluate(null));
            Assert.IsNull(parser.ParseExpression());
        }
        [TestMethod]
        public void ParseAndEvaluateAddAndMultiplyExpressionWithParenthesis()
        {
            Parser parser = new Parser("(1+2)*3");
            IExpression expression = parser.ParseExpression();
            Assert.IsNotNull(expression);
            Assert.IsInstanceOfType(expression, typeof(BinaryArithmeticExpression));
            Assert.AreEqual(9, expression.Evaluate(null));
            Assert.IsNull(parser.ParseExpression());
        }

In this way, I can recognize the binary operators, process them in precedence, and use parenthesis to alter the evaluation order.

All tests in green:

Good code coverage:

Next steps

I would like to add real numbers, function definitions, more operators, if, for commands, etc.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: