parser_jitting.cs


// parser_jitting.cs
// this program is offered as is with no warranty implied and confers no rights.


using System;
using System.Collections.Generic;
using System.Text;
using System.Reflection;
using System.Reflection.Emit;


namespace ParserJitting
{
    public class Program
    {
        // a few sample predicates, we will use these in a loop to simulate more of them
        private static string[] predicates = {
                “fact1”,
                “fact2”,
                “fact3”,
                “fact2 & fact1”,
                “fact3 & fact2”,
                “fact4 | fact5”,
                “!fact4 & fact5”,
                “!(fact1 & fact2) | !fact5”,
            };



        // it ain’t object oriented but it’s only a benchmark 🙂
        private static int ichInput = 0;
        private static string strInput = null;
        private static string strLookaheadToken = null;
        private static Dictionary<String, int> dictFacts = new Dictionary<String,int>();
       
        public static bool[] truthTable = null;


        static void Main(string[] args)
        {
            int len = predicates.Length;


            int i;


            List<BooleanDelegate> compList = new List<BooleanDelegate>();


            // compile the predicates
            for (i = 0; i< len; i++)
            {
                compList.Add(CompilePredicate(predicates[i]));
            }


            BooleanDelegate[] compiledPredicates = compList.ToArray();


            truthTable = new bool[dictFacts.Count];


            // these few prime numbered facts are in the fact table
            // therefore they are “true”
            SetFact(“fact2”);
            SetFact(“fact3”);
            SetFact(“fact5”);
            SetFact(“fact7”);
            SetFact(“fact11”);
            SetFact(“fact13”);
            SetFact(“fact17”);
            SetFact(“fact19”);


            // dump some test evaluations so we can be sure things are working ok
            for (i = 0; i< len; i++)
                Console.WriteLine(“{0} => {1}”, predicates[i], compiledPredicates[i]());


            System.Diagnostics.Stopwatch clock = new System.Diagnostics.Stopwatch();


            clock.Start();


            // the real benchmark
            for (int j = 0; j < 1000000; j++)
                for (i = 0; i< len; i++)
                    compiledPredicates[i]();


            clock.Stop();


            Console.WriteLine(“time {0:n0}ms”, clock.ElapsedMilliseconds);
        }


        // ultra lame exception class, please do better than this in your code 🙂
        class ParseException : Exception
        {
            public ParseException() : base(“Syntax Error”)
            {
            }
        }


        static int predCount = 0;
        static ILGenerator il;
        delegate bool BooleanDelegate();


        // Compile a simple boolean predicate
        static BooleanDelegate CompilePredicate(string predicate)
        {
            strInput = predicate;
            ichInput = 0;
            strLookaheadToken = null;


            string strName = String.Format(“pred{0}”, predCount++);


            DynamicMethod dm = new DynamicMethod(strName , typeof(bool), new Type[] {}, typeof(Program), true);
            il = dm.GetILGenerator();


            CompileOr();
            il.Emit(OpCodes.Ret);
            return (BooleanDelegate)dm.CreateDelegate(typeof(BooleanDelegate));
        }


        // this starts the recursive descent parser — or is the outer clause
        // the other clauses happen in the natural order (outermost first)
        static void CompileOr()
        {
            CompileAnd();


            for (; 😉
            {
                string s = PeekToken();
                if (s == null)
                    break;


                if (s != “|”)
                    break;


                ReadToken();


                CompileAnd();


                il.Emit(OpCodes.Or);
            }
        }


        static void CompileAnd()
        {
            CompileOptionalNot();


            for (; ; )
            {
                string s = PeekToken();
                if (s == null)
                    break;


                if (s != “&”)
                    break;


                ReadToken();


                CompileOptionalNot();


                il.Emit(OpCodes.And);
            }
        }


        static void CompileOptionalNot()
        {
            bool invert = false;
            string s = PeekToken();


            while (s == “!”)
            {
                invert = !invert;
                ReadToken();
                s = PeekToken();
            }


            CompileFact();


            if (invert)
                il.Emit(OpCodes.Not);
        }


        static void CompileFact()
        {
            string s = ReadToken();


            if (s == null)
                throw new ParseException();


            if (s == “(“)
            {
                CompileOr();
                s = ReadToken();
                if (s != “)”)
                    throw new ParseException();
            }
            else
            {
                string fact = s;
                if (fact == null)
                    throw new ParseException();


                int ifact = GetFactNumber(fact);


                il.Emit(OpCodes.Ldsfld, typeof(Program).GetField(“truthTable”));
                il.Emit(OpCodes.Ldc_I4, ifact);
                il.Emit(OpCodes.Ldelem_I1);
            }
        }


        // reuse the lookahead if there is one, this consumes a token
        static string ReadToken()
        {
            if (strLookaheadToken == null)
            {
                PeekToken();
            }


            string ret = strLookaheadToken;
            strLookaheadToken = null;
            return ret;
        }


        // this sets up the lookahead token without actually consuming it
        static string PeekToken()
        {
            // give back the lookahead token again if we already computed it
            if (strLookaheadToken != null)
                return strLookaheadToken;


            strLookaheadToken = GetToken();


            return strLookaheadToken;
        }


        // this reads a token from the input stream and is unaware of lookahead concerns
        static string GetToken()
        {
            if (ichInput >= strInput.Length)
                return null;


            char ch = ‘\0’;


            for (; ; )
            {
                ch = getc();
                if (ch != ‘ ‘ && ch != ‘\t’)
                    break;
            }


            int idx = ichInput – 1;


            if (ch >= ‘a’ && ch <= ‘z’ ||
              ch >= ‘A’ && ch <= ‘Z’ ||
              ch == ‘_’)
            {


                while (‘\0’ != (ch = getc()))
                    if (ch >= ‘a’ && ch <= ‘z’ ||
                      ch >= ‘A’ && ch <= ‘Z’ ||
                      ch >= ‘0’ && ch <= ‘9’ ||
                      ch == ‘_’)
                        continue;
                    else
                        break;


                if (ch != ‘\0’) ichInput–;
                return strInput.Substring(idx, ichInput – idx);
            }


            // the single character tokens for valid operators
            switch (ch)
            {
                case ‘!’: case ‘&’: case ‘|’: case ‘(‘: case ‘)’:
                    return strInput.Substring(idx, 1);
            }


            // error token
            return null;
        }


        // fetch the next character from the input stream
        static char getc()
        {
            if (ichInput >= strInput.Length)
                return ‘\0’;


            return strInput[ichInput++];
        }


        // fixed size stack — we could do better if we needed to but
        // this is good enough for this test
        static bool[] evalStack = new bool[16];
        static int GetFactNumber(string fact)
        {
            if (!dictFacts.ContainsKey(fact))
                dictFacts.Add(fact, dictFacts.Count);


            return dictFacts[fact];
        }


        static void SetFact(string fact)
        {
            // facts that are mentioned in no predicates may be disregarded
            if (!dictFacts.ContainsKey(fact))
                return;


            truthTable[dictFacts[fact]] = true;
        }
   }
}



 

Comments (0)

Skip to main content