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;
}
}
}
