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

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();
                }
            }
        }
    }
}