Agent Grammar: The Interpreter Design Pattern

In building my communication model for my agent application, I wanted to use some design patterns that I have not used in the course of my writing. The Interpreter Design pattern uses a grammar and an interpreter for that grammar. Basically, this pattern defines a domain language used as a simple grammar where the rules of the domain interpret sentences to solve a particular problem. Grammar rules each have their own class and this hierarchical structure provides an easy to use map for interpretation. Ron Ayoub has a good article on The Code Project at

http://www.codeproject.com/KB/architecture/InterpreterPatternParsing.aspx for "Parsing Algebraic Expressions Using the Interpreter Pattern". The classes used in this article are AXExceptions, AXParser,AXValidator, ExpressionContext, Expressions, ExpressionFactory, and AXTokenizer. The idea is to perform lexical analysis by transforming a character sequence into a token sequence. The token sequence is validated and the ExpressionFactory is used to translate the token sequence into a sequence of Expression objects. This becomes an Expression Object to be parsed. This expression tree is then parsed and evaluated by substitution. Besides the interpreter pattern, the factory, template method and composite are included in this application as well.
I wanted to show some of the building blocks that I am using for my application with the following from the article:

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

namespace AgentGrammar
{
internal class Token
{
private Dictionary _patterns = null;
public Token()
{
_patterns = new Dictionary();
}
public void AddPattern(string pattern)
{
if (string.IsNullOrEmpty(pattern))
throw new AXException("The pattern cannot be null or an empty string.");
if (_patterns.ContainsKey(pattern))
throw new AXException("The pattern has already been added to the tokenizer.");

try
{
_patterns.Add(pattern, new Regex(pattern));
}
catch
{
throw new AXException("The pattern must be a valid regular expression.");
}
}

public bool RemovePattern(string pattern)
{
return _patterns.Remove(pattern);
}

public List Tokenize(string text)
{
List tokens = new List();

for (int i = 0; i < matched =" false;" j =" text.Length"> 0 && !matched; j--)
{
foreach(KeyValuePair pair in _patterns)
{
if (pair.Value.IsMatch(text.Substring(i, j)))
{
matched = true;
tokens.Add(text.Substring(i, j));
i += j - 1;
break;
}
}
}

if (!matched)
{
throw new AXTokenException(i, "Unrecognized character sequence starting at index " +
i.ToString() + ".");
}
}

return tokens;
}


}
}

The structural foundations for the interpreter pattern is presented below for the Parser class.

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

public sealed class Parser
{

private ExpressionFactory _factory = null;
private Token _tokenizer = null;

public Parser()
{
_factory = new ExpressionFactory();
_tokenizer = new Token();
AddAssociationInternal(@"^[a-z]$", typeof(VariableExpression));
AddAssociationInternal(@"^\d+(\.\d+)?$", typeof(NumericExpression));

//constants
AddAssociationInternal(@"^PI$", typeof(PIExpression));
AddAssociationInternal(@"^E$", typeof(EExpression));
}


//More methods not included....

private List TokensToExpressions(List tokens)
{
List expressions = new List();

for (int i = 0; i < copy =" text.Replace("> tokens = _tokenizer.Tokenize(copy);
List expressions = TokensToExpressions(tokens);

//AXValidator.Validate(expressions); //throws

//RemoveExcessParens(expressions);
while (expressions.Count > 1)
{
//int i = DetermineHighestPrecedence(expressions);
//CollapseExpression(expressions, i);
//RemoveExcessParens(expressions);
}

return expressions[0];
}

}

This internal class creates expressions. I like the use of the Dictionary object.

internal class ExpressionFactory
{
private Dictionary> _associations = null;

public ExpressionFactory()
{
_associations = new Dictionary>();
}

public void AddAssociation(string pattern, Type type)
{
if (string.IsNullOrEmpty(pattern))
throw new AXException("The pattern cannot be null or an empty string.");
if (type == null)
throw new AXException("The type cannot be null.");
if (_associations.ContainsKey(pattern))
throw new AXException("The pattern has already been associated with a type.");

try
{
_associations.Add(pattern, new KeyValuePair(new Regex(pattern),type));
}
catch
{
throw new AXException("The pattern must be a valid regular expression.");
}
}

public bool RemoveAssociation(string pattern)
{
return _associations.Remove(pattern);
}

public Expression Create(string token)
{
if (!string.IsNullOrEmpty(token))
{
foreach (KeyValuePair> pair in _associations)
{
if (pair.Value.Key.IsMatch(token))
{
ConstructorInfo info = pair.Value.Value.GetConstructor(Type.EmptyTypes);
return (Expression)info.Invoke(null);
}
}
}

return null;
}
public sealed class Context
{
public enum Variable
{
a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
}
private Dictionary _bindings;
public Context()
{
_bindings = new Dictionary();
}

public void Bind(Variable variable, double value)
{
_bindings[variable] = value;
}

public double Lookup(Variable variable)
{
if (_bindings.ContainsKey(variable))
return _bindings[variable];
else
return double.NaN;
}

}

public abstract class Expression
{
protected bool _isBound;
public Expression()
{
_isBound = false;
}
public bool IsBound()
{
return _isBound;
}
public void Bind(params object[] arguments)
{
InnerBind(arguments);
_isBound = true;
}

public double Evaluate(ExpressionContext context)
{
double result = InnerEvaluate(context);

if (Math.Abs(result) <= ZERO_THRESHOLD)
return 0;
else
return result;
}
protected abstract void InnerBind(params object[] arguments);
protected abstract double InnerEvaluate(ExpressionContext context);
}
public sealed class PIExpression: Expression
{
protected override double InnerEvaluate(ExpressionContext context)
{
return Math.PI;
}
}

public sealed class EExpression: Expression
{
protected override double InnerEvaluate(ExpressionContext context)
{
return Math.E;
}
}
We can see all the elements of the interpreter pattern in the above code-Parser, Context, and Expressions. Consider the example of "e+PI" for parsing in using the above code.

Parser parse = new Parser();
Expression express = parse.Parse("E+PI");
Context ct = new Context();
MessageBox.Show(express.Evaluate(ct).ToString());

Clearly, the code above provides a pattern for a both a language and grammar for communication and is extensible for adding additional grammatical rules by subclassing the Expression class.