Click here to Skip to main content
11,490,003 members (61,917 online)
Click here to Skip to main content
Add your own
alternative version

TinyLisp: A Language and Parser to See LINQ Expressions in Action

, 12 Jun 2010 CPOL 14.5K 234 27
A small program that parses expressions and evaluates them using LINQ Expressions
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Linq.Expressions;

namespace TinyLisp {
    // this class builds up the Abstract Syntax Tree
    class ExpressionNode : CodeNode {

        // some public properties on it
        public char Operator { get; set; }
        public int Start { get; private set; }
        public int End { get; private set; }
        public string StringExpression { get; private set; }

        // lists or operators and integers to match stream against
        private static readonly char[] Operators = "+-*/".ToCharArray();
        private static readonly char[] Ints = "0123456789".ToCharArray();

        // Displaytext for visualization
        public override string Text {
            get { return Operator + ""; }
        }

        // constructor to create expression tree by parsing a string
        public ExpressionNode(CharStream Stream) {

            // keep track of start of current expression within whole epxression
            this.Start = Stream.Position;
            this.StringExpression = Stream.Stream;

            // assert that we have a bracket to start this expresison 
            if (Stream.Current != '(') throw new Exception("a (sub)expression must always start with a '(' at position " + Stream.Position);

            // skip to next character 
            Stream.MoveNext(); 

            // get the operator wich should be here now
            if (Operators.Contains(Stream.Current)) this.Operator = Stream.Current;
            else throw new Exception("Unexpected character '" + Stream.Current + "' at position " + Stream.Position + ".\n\nThe first character after the '(' at position " + this.Start + " that started this (sub)expression must be its operator [+, -, *, /].");

            // loop over the characters in the stream and try to figure them out one by one
            while (true) {

                // skip to next character
                Stream.MoveNext(); 

                // is it a '(' marking the start of new sub expression?
                if (Stream.Current == '(') {
                    // start a new sub expression from here and add that
                    this.Operands.Add(new ExpressionNode(Stream));
                    continue;
                }

                //  is it a ')' marking end of current expression?
                if (Stream.Current == ')') {
                    // this expression is done, mark ending and break loop 
                    this.End = Stream.Position;
                    break;
                }

                // is it an int?                
                if (Ints.Contains(Stream.Current)) {
                    // add int and loop to go to next char
                    this.Operands.Add(new IntNode(Stream.Current));
                    continue;
                }                

                // If none of the above was true, we have an error. Our language does not allow this situation. Very important to give a meaningful error message.
                string sTemplate = 
@"Unexpected character '{0}' at position {1}. 
Expecting either: 
- an int [0..9] for the current expression, that started with the '(' at position {2}
- a '(' for the start of a new subexpression
- a ')' to close the current expression";
                throw new Exception(string.Format(sTemplate, Stream.Current, Stream.Position, this.Start));
            }
        }

        // Empty constructor to create Expression by hand
        public ExpressionNode() { }

        // convert to Linq Expression
        public override Expression ToExpression() {
            // the public method only starts the recursive internal one for the first child
            return ToExpressionInternal(0);
        }

        // This Method returns a Linq ExpressionTree that is equivalent to our AST.
        // In our language, because he operator does not have to sit inbetween the two operands, we can have more than 2 operands for each operator.
        // In Linq.Expressions, the BinaryOperators can have only 2 operands: left and right.
        // We need to nest the operands into a binary tree when there are more than 2. Right becomes a new tree wih the rest of the operands.
        private Expression ToExpressionInternal(int Child) {

            // if this is the last (or only) child, just return that. Can't use a binary operator on 1 operand
            if (Child == Operands.Count - 1) {
                return Operands[Child].ToExpression();
            } else {
                // so we have more than one, let's deal with that case:

                // assign this node to the left operand
                Expression left = Operands[Child].ToExpression();

                // Recurse for the remaining child(ren) for the righthand operand. 
                // If there's more than 1 remaining they'll need to be nested into a tree also
                Expression right = ToExpressionInternal(Child + 1);

                // Put left and right together in a BinaryOperator and return that subtree
                switch (Operator) {
                    case '+': return Expression.Add(left, right);
                    case '-': return Expression.Subtract(left, right);
                    case '*': return Expression.Multiply(left, right);
                    case '/': return Expression.Divide(left, right);
                    default: throw new Exception();
                }
            }
        }
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

gjvdkamp
Leaseplan Corporation
Netherlands Netherlands
Gert-Jan is a Senior Quantitative Risk Manager at Leaseplan Corporation. In that job he doesn't get to code much he does these little projects to keep his skills up and feed the inner geek.
Follow on   LinkedIn

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150520.1 | Last Updated 12 Jun 2010
Article Copyright 2010 by gjvdkamp
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid