// 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();
if (s != "&") break;
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; } }}