parser_compiling.cs


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


using System;
using System.Collections.Generic;
using System.Text;


namespace ParserCompiling
{
    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>();
        private static List<int> compiledOpcodes = new List<int>();
        private static List<int[]> compiledPredicates = new List<int[]>();
        private static bool[] truthTable = null;


        // our execution machine supports 3 operators
        // positive integers in the machine indicate a fact number to evaluate
        const int opOr = -1;
        const int opAnd = -2;
        const int opNot = -3;


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


            int i;


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


            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], EvaluatePredicate(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++)
                    EvaluatePredicate(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”)
            {
            }
        }


        // this only happens if there’s bugs in my stack machine code, user
        // input cannot cause this — don’t imitate this awful exception class
        // real exceptions should follow the design guidelines 🙂
        class EvalException : Exception
        {
            public EvalException() : base(“Stack Machine Code was bogus”)
            {
            }
        }


        // Compile a simple boolean predicate
        static int[] CompilePredicate(string predicate)
        {
            compiledOpcodes.Clear();
            strInput = predicate;
            ichInput = 0;
            strLookaheadToken = null;


            CompileOr();
            return compiledOpcodes.ToArray();
        }


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


                compiledOpcodes.Add(opOr);
            }
        }


        static void CompileAnd()
        {
            CompileOptionalNot();


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


                if (s != “&”)
                    break;


                ReadToken();


                CompileOptionalNot();


                compiledOpcodes.Add(opAnd);
            }
        }


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


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


            CompileFact();


            if (invert)
                compiledOpcodes.Add(opNot);
        }


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


                compiledOpcodes.Add(GetFactNumber(fact));
            }
        }


        // 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];


        // evaluate the given compiled predicate
        // the integers are in postfix order
        static bool EvaluatePredicate(int[] predicate)
        {
            int evalStackPtr  = 0;
            bool val1;
            foreach (int op in predicate)
            {
                switch (op)
                {
                case opOr:
                    val1 = evalStack[–evalStackPtr];
                    evalStack[evalStackPtr-1] |= val1;
                    break;


                case opAnd:
                    val1 = evalStack[–evalStackPtr];
                    evalStack[evalStackPtr-1] &= val1;
                    break;


                case opNot:
                    val1 = evalStack[evalStackPtr-1];
                    evalStack[evalStackPtr-1] = !val1;
                    break;


                default:
                    evalStack[evalStackPtr++] = truthTable[op];
                    break;
                }
            }


            if (evalStackPtr != 1)
                throw new EvalException();


            return evalStack[0];
        }


        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