Interpreter pattern

In computer programming, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a language. The basic idea is to have a class for each symbol (terminal or nonterminal) in a specialized computer language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate (interpret) the sentence for a client. See also Composite pattern.

Overview

The Interpreter design pattern is one of the twenty-three well-known GoF design patterns that describe how to solve recurring design problems to design flexible and reusable object-oriented software, that is, objects that are easier to implement, change, test, and reuse.

What problems can the Interpreter design pattern solve?

• A grammar for a simple language should be defined
• so that sentences in the language can be interpreted.

When a problem occurs very often, it could be considered to represent it as a sentence in a simple language (Domain Specific Languages) so that an interpreter can solve the problem by interpreting the sentence.

For example, when many different or complex search expressions must be specified. Implementing (hard-wiring) them directly into a class is inflexible because it commits the class to particular expressions and makes it impossible to specify new expressions or change existing ones independently from (without having to change) the class.

What solution does the Interpreter design pattern describe?

• Define a grammar for a simple language by defining an Expression class hierarchy and implementing an interpret() operation.
• Represent a sentence in the language by an abstract syntax tree (AST) made up of Expression instances.
• Interpret a sentence by calling interpret() on the AST.

The expression objects are composed recursively into a composite/tree structure that is called abstract syntax tree (see Composite pattern).
The Interpreter pattern doesn't describe how to build an abstract syntax tree. This can be done either manually by a client or automatically by a parser.

See also the UML class and object diagram below.

Uses

• Specialized database query languages such as SQL.
• Specialized computer languages that are often used to describe communication protocols.
• Most general-purpose computer languages actually incorporate several specialized languages.

Structure

UML class and object diagram

A sample UML class and object diagram for the Interpreter design pattern.

In the above UML class diagram, the Client class refers to the common AbstractExpression interface for interpreting an expression interpret(context).
The TerminalExpression class has no children and interprets an expression directly.
The NonTerminalExpression class maintains a container of child expressions (expressions) and forwards interpret requests to these expressions.

The object collaboration diagram shows the run-time interactions: The Client object sends an interpret request to the abstract syntax tree. The request is forwarded to (performed on) all objects downwards the tree structure.
The NonTerminalExpression objects (ntExpr1,ntExpr2) forward the request to their child expressions.
The TerminalExpression objects (tExpr1,tExpr2,…) perform the interpretation directly.

UML class diagram

Example

BNF

The following Backus–Naur form example illustrates the interpreter pattern. The grammar

expression ::= plus | minus | variable | number
plus ::= expression expression '+'
minus ::= expression expression '-'
variable ::= 'a' | 'b' | 'c' | ... | 'z'
digit = '0' | '1' | ... | '9'
number ::= digit | digit number

defines a language that contains Reverse Polish Notation expressions like:

a b +
a b c + -
a b + c a - -

C#

This structural code demonstrates the Interpreter patterns, which using a defined grammar, provides the interpreter that processes parsed statements.

namespace DesignPatterns.Interpreter
{
    // "Context"
    class Context
    {
    }

    // "AbstractExpression"
    abstract class AbstractExpression
    {
        public abstract void Interpret(Context context);
    }

    // "TerminalExpression"
    class TerminalExpression : AbstractExpression
    {
        public override void Interpret(Context context)
        {
            Console.WriteLine("Called Terminal.Interpret()");
        }
    }

    // "NonterminalExpression"
    class NonterminalExpression : AbstractExpression
    {
        public override void Interpret(Context context)
        {
            Console.WriteLine("Called Nonterminal.Interpret()");
        }
    }

    class MainApp
    {
        static void Main()
        {
            var context = new Context();

            // Usually a tree
            var list = new List<AbstractExpression>();

            // Populate 'abstract syntax tree'
            list.Add(new TerminalExpression());
            list.Add(new NonterminalExpression());
            list.Add(new TerminalExpression());
            list.Add(new TerminalExpression());

            // Interpret
            foreach (AbstractExpression exp in list)
            {
                exp.Interpret(context);
            }
        }
    }
}

Java

Following the interpreter pattern there is a class for each grammar rule.

import java.util.Map;

interface Expression {
    public int interpret(final Map<String, Expression> variables);
}

class Number implements Expression {
    private int number;
    public Number(final int number)       { this.number = number; }
    public int interpret(final Map<String, Expression> variables)  { return number; }
}

class Plus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Plus(final Expression left, final Expression right) {
        leftOperand = left;
        rightOperand = right;
    }
		
    public int interpret(final Map<String, Expression> variables) {
        return leftOperand.interpret(variables) + rightOperand.interpret(variables);
    }
}

class Minus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Minus(final Expression left, final Expression right) {
        leftOperand = left;
        rightOperand = right;
    }
		
    public int interpret(final Map<String, Expression> variables) {
        return leftOperand.interpret(variables) - rightOperand.interpret(variables);
    }
}

class Variable implements Expression {
    private String name;
    public Variable(final String name)       { this.name = name; }
    public int interpret(final Map<String, Expression> variables) {
        if (null == variables.get(name)) return 0; // Either return new Number(0).
        return variables.get(name).interpret(variables);
    }
}

While the interpreter pattern does not address parsing a parser is provided for completeness.

import java.util.Map;
import java.util.Stack;

class Evaluator implements Expression {
    private Expression syntaxTree;

    public Evaluator(final String expression) {
        final Stack<Expression> expressionStack = new Stack<Expression>();
        for (final String token : expression.split(" ")) {
            if (token.equals("+")) {
                final Expression subExpression = new Plus(expressionStack.pop(), expressionStack.pop());
                expressionStack.push(subExpression);
            } else if (token.equals("-")) {
                // it's necessary to remove first the right operand from the stack
                final Expression right = expressionStack.pop();
                // ..and then the left one
                final Expression left = expressionStack.pop();
                final Expression subExpression = new Minus(left, right);
                expressionStack.push(subExpression);
            } else
                expressionStack.push(new Variable(token));
        }
        syntaxTree = expressionStack.pop();
    }

    public int interpret(final Map<String, Expression> context) {
        return syntaxTree.interpret(context);
    }
}

Finally evaluating the expression "w x z - +" with w = 5, x = 10, and z = 42.

import java.util.Map;
import java.util.HashMap;

public class InterpreterExample {
    public static void main(final String[] args) {
        final String expression = "w x z - +";
        final Evaluator sentence = new Evaluator(expression);
        final Map<String, Expression> variables = new HashMap<String, Expression>();
        variables.put("w", new Number(5));
        variables.put("x", new Number(10));
        variables.put("z", new Number(42));
        final int result = sentence.interpret(variables);
        System.out.println(result);
    }
}

See also

• Backus–Naur form
• Combinatory logic in computing
• Design Patterns
• Domain-specific language
• Interpreter (computing)

External links

• Interpreter implementation in Ruby
• Interpreter implementation in C++
• SourceMaking tutorial
• Interpreter pattern description from the Portland Pattern Repository