gistfile1.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Reflection.Emit;
using System.Reflection;

namespace StreamProject
{
    struct StreamState
    {
        private String Data;
        private int Place;

        public static StreamState Create(String Data) { return new StreamState { Data = Data, Place = 0 }; }

        public bool AtEnd { get { return Place >= Data.Length; } }
        public char Current { get { return Data[Place]; } }
        public StreamState Next { get { return new StreamState { Data = Data, Place = Place + 1 }; } }
    }

    struct AstNode
    {
        public String NodeType;
        public Object Value;
        public List<AstNode> Children;

        public static AstNode Create(String NodeType, Object Value, params AstNode[] Children)
        {
            return new AstNode
            {
                NodeType = NodeType,
                Value = Value,
                Children = new List<AstNode>(Children)
            };
        }
    }

    struct ParseResult
    {
        public bool Success;
        public StreamState After;
        public AstNode Node;

        public static ParseResult Fail { get { return new ParseResult { Success = false }; } }
    }

    class Program
    {
        static String Digits = "0123456789";
        static ParseResult ParseNumber(StreamState Stream)
        {
            var s = "";
            while (!Stream.AtEnd && Digits.Contains(Stream.Current))
            {
                s += Stream.Current;
                Stream = Stream.Next;
            }

            if (s.Length > 0)
            {
                return new ParseResult
                {
                    Success = true,
                    After = Stream,
                    Node = AstNode.Create("NUMBER", Convert.ToInt32(s))
                };
            }
            else
                return ParseResult.Fail;
        }

        static Dictionary<String, int> OperatorTable = new Dictionary<string, int>();

        static ParseResult ParseOperator(StreamState Stream)
        {
            if (Stream.AtEnd) return ParseResult.Fail;

            //TODO: Parse multi character operators.
            if (OperatorTable.ContainsKey(new String(Stream.Current, 1)))
                return new ParseResult
                {
                    Success = true,
                    After = Stream.Next,
                    Node = AstNode.Create("OPERATOR", new String(Stream.Current, 1))
                };
            else
                return ParseResult.Fail;
        }

        static String Whitespace = " \t\r\n";

        static ParseResult ParseWhitespace(StreamState Stream)
        {
            while (!Stream.AtEnd && Whitespace.Contains(Stream.Current))
                Stream = Stream.Next;
            return new ParseResult { Success = true, After = Stream };
        }

        static ParseResult ParseTerm(StreamState Stream)
        {
            var n = ParseNumber(Stream);
            if (n.Success) return n;

            if (Stream.Current == '(')
            {
                var r = ParseExpression(Stream.Next);
                if (!r.Success) return ParseResult.Fail;
                if (r.After.Current != ')') return ParseResult.Fail;
                r.After = r.After.Next;
                return r;
            }

            return ParseResult.Fail;
        }

        static ParseResult __parseExpression(AstNode LHS, StreamState Stream, int MinimumPrecedence)
        {
            while (true)
            {
                var parsedOp = ParseOperator(Stream);
                if (parsedOp.Success == false) return new ParseResult
                {
                    Success = true,
                    Node = LHS,
                    After = Stream
                };

                var precedence = OperatorTable[parsedOp.Node.Value.ToString()];
                if (precedence < MinimumPrecedence) return new ParseResult
                {
                    Success = true,
                    Node = LHS,
                    After = Stream
                };

                var op = parsedOp.Node.Value;

                var parsedRHS = ParseTerm(parsedOp.After);

                if (parsedRHS.Success == false) return ParseResult.Fail;

                //Parsed one operator. Now we need to keep pulling them off the input as long as their precedence isn't > than this one.

                while (true)
                {
                    parsedOp = ParseOperator(parsedRHS.After);
                    if (parsedOp.Success)
                    {
                        var nextPrecedence = OperatorTable[parsedOp.Node.Value.ToString()];
                        if (nextPrecedence > precedence)
                            parsedRHS = __parseExpression(parsedRHS.Node, parsedRHS.After, nextPrecedence);
                        else
                            break;
                    }
                    else
                        break;
                }

                Stream = parsedRHS.After;
                LHS = AstNode.Create("BINARYOP", op, LHS, parsedRHS.Node);
            }
        }

        static ParseResult ParseExpression(StreamState Stream)
        {
            // Shunting Yard algorithm. Sort of.
            var firstLHS = ParseTerm(Stream);
            if (firstLHS.Success) return __parseExpression(firstLHS.Node, firstLHS.After, 0);
            else return ParseResult.Fail;
        }

        static void Main(string[] args)
        {
            OperatorTable.Add("+", 1);
            OperatorTable.Add("-", 1);
            OperatorTable.Add("*", 2);
            OperatorTable.Add("/", 2);

            while (true)
            {
                var input = Console.ReadLine();
                
                var r = ParseExpression(StreamState.Create(input));
                if (r.Success)
                {
                    Console.WriteLine("PARSED.");
                    PrintNode(r.Node, 0);

                    // Well, it's parsed. Now lets COMPILE IT!!!
                    // .net comes with the Reflection.Emit api which makes this AMAZINGLY SIMPLE.

                    var assemblyName = new System.Reflection.AssemblyName("CILGenerationStream");
                    var assemblyBuilder = AppDomain.CurrentDomain.DefineDynamicAssembly(assemblyName, AssemblyBuilderAccess.RunAndSave);
                    var moduleBuilder = assemblyBuilder.DefineDynamicModule("Module");
                    var typeBuilder = moduleBuilder.DefineType("Demo");
                    var methodBuilder = typeBuilder.DefineMethod("Execute", MethodAttributes.Static | MethodAttributes.Public, typeof(int), System.Type.EmptyTypes);

                    var ilBuilder = methodBuilder.GetILGenerator();

                    //Oh god finally...

                    CompileAst(ilBuilder, r.Node);
                    //ilBuilder.EmitWriteLine("Hello WatchPeopleCode");

                    //ilBuilder.Emit(OpCodes.Ldc_I4, 42);
                    ilBuilder.Emit(OpCodes.Ret);

                    typeBuilder.CreateType();
                    moduleBuilder.CreateGlobalFunctions();

                    var dynamicType = assemblyBuilder.GetType("Demo");
                    var execMethod = dynamicType.GetMethod("Execute");

                    var result = execMethod.Invoke(null, null);
                    Console.WriteLine(result.ToString());
                }
                else
                    Console.WriteLine("FAIL.");
            }
        }

        private static void CompileAst(ILGenerator ilBuilder, AstNode astNode)
        {
            if (astNode.NodeType == "NUMBER")
                ilBuilder.Emit(OpCodes.Ldc_I4, (astNode.Value as int?).Value);
            else if (astNode.NodeType == "BINARYOP")
            {
                foreach (var child in astNode.Children) CompileAst(ilBuilder, child);
                if (astNode.Value.ToString() == "+") ilBuilder.Emit(OpCodes.Add);
                else if (astNode.Value.ToString() == "-") ilBuilder.Emit(OpCodes.Sub);
                else if (astNode.Value.ToString() == "*") ilBuilder.Emit(OpCodes.Mul);
                else if (astNode.Value.ToString() == "/") ilBuilder.Emit(OpCodes.Div);
                else throw new InvalidOperationException("WTF????");
            }
        }

        static void PrintNode(AstNode Node, int Depth)
        {
            Console.Write(new String(' ', Depth * 2));
            Console.WriteLine("{0} - {1}", Node.NodeType, Node.Value == null ? "NULL" : Node.Value.ToString());
            foreach (var child in Node.Children)
                PrintNode(child, Depth + 1);
        }
    }
}