.NET 2.0+

Interpreter Design Pattern

by Richard Carr, published at http://www.blackwasp.co.uk/Interpreter.aspx

The interpreter pattern is a design pattern that is useful when developing domain-specific languages or notations. The pattern allows the grammar for such a notation to be represented in an object-oriented fashion that can easily be extended.

Example Interpreter

Earlier in this article an example of the interpreter pattern was described. This explained that the pattern could be used to process Polish notation mathematical functions. In the remainder of this article we will implement the grammar required for a simplified Polish notation that permits the use of integer values and the addition (+) and subtraction (-) operators. We will also create a parser that converts a string containing Polish notation into a hierarchy of expressions.

Creating the Grammar

The grammar for the Polish notation interpreter will be very simple. There will be one terminal expression that can be used to represent an integer. Two non-terminal expressions will be created to represent the addition and subtraction operators. You could easily add further operators with additional classes. No context class will be necessary as no global information will be required.

To create the base class, open a new console application project and add the following code:

public abstract class ExpressionBase
{
    public abstract int Evaluate();
}

The base class includes one method, which evaluates an expression and returns the calculated value as an integer. As there is no Context class, the method needs no parameters.

To add the terminal expression class that will be used to represent integers, add the following code:

public class IntegerExpression : ExpressionBase
{
    int _value;

    public IntegerExpression(int value)
    {
        _value = value;
    }

    public override int Evaluate()
    {
        return _value;
    }

    public override string ToString()
    {
        return _value.ToString();
    }
}

As you can see, when an IntegerExpression object is created, the value that it represents is passed into the constructor. When the expression is evaluated this value is returned. To make debugging easier and to allow the expression to be output to the console the ToString method has been overridden. This returns a string representation of the value.

Next we can add the two non-terminal expression classes:

public class AdditionExpression : ExpressionBase
{
    ExpressionBase _expr1;
    ExpressionBase _expr2;

    public AdditionExpression(ExpressionBase expr1, ExpressionBase expr2)
    {
        _expr1 = expr1;
        _expr2 = expr2;
    }

    public override int Evaluate()
    {
        int value1 = _expr1.Evaluate();
        int value2 = _expr2.Evaluate();
        return value1 + value2;
    }

    public override string ToString()
    {
        return string.Format("({0} + {1})", _expr1, _expr2);
    }
}


public class SubtractionExpression : ExpressionBase
{
    ExpressionBase _expr1;
    ExpressionBase _expr2;

    public SubtractionExpression(ExpressionBase expr1, ExpressionBase expr2)
    {
        _expr1 = expr1;
        _expr2 = expr2;
    }

    public override int Evaluate()
    {
        int value1 = _expr1.Evaluate();
        int value2 = _expr2.Evaluate();
        return value1 - value2;
    }

    public override string ToString()
    {
        return string.Format("({0} - {1})", _expr1, _expr2);
    }
}

The non-terminal expression classes are quite simple. When creating a new object two expressions are passed to the constructor. These are held within the class for use during evaluation. Each may represent an integer value or another operator with further expressions to be interpreted recursively. When the Evaluate method is called the two expressions are evaluated before the addition or subtraction occurs and the result is returned. Again, the ToString method is overridden to allow the expression to be viewed easily. The ToString method may also include recursive calls.

The code so far completes the key classes of the interpreter design pattern. However, in this case we will also create a parser that can convert strings such as "+ 5 6" into the grammar understood by the interpreter. The parser will be very simple and will not including any validation of the input string. It will split the string into a list of commands and recursively convert each symbol into an expression.

The code for the parser is as follows:

public class Parser
{
    public ExpressionBase Parse(string polish)
    {
        List<string> symbols = new List<string>(polish.Split(' '));
        return ParseNextExpression(symbols);
    }

    public ExpressionBase ParseNextExpression(List<string> symbols)
    {
        int value;
        if (int.TryParse(symbols[0], out value))
        {
            symbols.RemoveAt(0);
            return new IntegerExpression(value);
        }
        else
        {
            return ParseNonTerminalExpression(symbols);
        }
    }

    private ExpressionBase ParseNonTerminalExpression(List<string> symbols)
    {
        string symbol = symbols[0];
        symbols.RemoveAt(0);

        ExpressionBase expr1 = ParseNextExpression(symbols);
        ExpressionBase expr2 = ParseNextExpression(symbols);

        switch (symbol)
        {
            case "+":
                return new AdditionExpression(expr1, expr2);
            case "-":
                return new SubtractionExpression(expr1, expr2);
            default:
                string message = string.Format("Invalid Symbol ({0})", symbol);
                throw new InvalidOperationException(message);
        }
    }
}