parser_original.cs


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

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


        static void Main(string[] args)
        {
            // these few prime numbered facts are in the fact table
            // therefore they are "true"
            dictFacts.Add("fact2", null);
            dictFacts.Add("fact3", null);
            dictFacts.Add("fact5", null);
            dictFacts.Add("fact7", null);
            dictFacts.Add("fact11", null);
            dictFacts.Add("fact13", null);
            dictFacts.Add("fact17", null);
            dictFacts.Add("fact19", null);


            int len = predicates.Length;


            int i;


            // 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(predicates[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(predicates[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")
            {
            }
        }


        // 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, String> dictFacts = new Dictionary<STRING,STRING>();


        // evaluate a simple boolean predicate
        static bool EvaluatePredicate(string predicate)
        {
            strInput = predicate;
            ichInput = 0;
            strLookaheadToken = null;
            return EvaluateOr();
        }


        // this starts the recursive descent parser -- or is the outer clause
        // the other clauses happen in the natural order (outermost first)
        static bool EvaluateOr()
        {
            bool v1 = EvaluateAnd();


            for (; ; )
            {
                string s = PeekToken();
                if (s == null)
                    return v1;


                if (s != "|")
                    break;


                ReadToken();


                bool v2 = EvaluateAnd();


                v1 |= v2;
            }


            return v1;
        }


        static bool EvaluateAnd()
        {
            bool v1 = EvaluateOptionalNot();


            for (; ; )
            {
                string s = PeekToken();
                if (s == null)
                    return v1;


                if (s != "&")
                    break;


                ReadToken();


                bool v2 = EvaluateOptionalNot();


                v1 &= v2;
            }


            return v1;
        }


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


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


            bool v1 = EvaluateFact();


            if (invert)
                return !v1;
            else
                return v1;
        }


        static bool EvaluateFact()
        {
            string s = ReadToken();


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


            if (s == "(")
            {
                bool v = EvaluateOr();
                s = ReadToken();
                if (s != ")")
                    throw new ParseException();
                return v;
            }


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


            return dictFacts.ContainsKey(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++];
        }
    }
}

Comments (0)

Skip to main content