Interpreter Design Pattern

The Interpreter Design Pattern is used to model a grammar of a language using a set of classes along with an interpreter that uses the representation to interpret sentences in the language. The definitions of a language grammar is represented as hierarchical representation of Expression classes, where each expression class is cable of interpreting and evaluating itself.

Let's take an example of an algebraic expression 2 + 3. To model this expression we need ConstantExpression that represents the constant operands(2 and 3) and then AndExpression that takes two ConstantExpression expressions operands and performs addition operation. All Expression classes must implement a common interface 'Expression'.

Above expression can Modelled as :
AndExpression(ConstantExpression(2), ConstantExpression(3))

Similarly, (2 + 6) + (1 + 9) can be modelled as:
AndExpression(AndExpression(ConstantExpression(2), ConstantExpression(6)), AndExpression(ConstantExpression(1), ConstantExpression(9)))


Structure of the Interpreter Design Pattern

The Interpreter Design Pattern consists of the following components:
  • Abstract Expression : This interface declares an interpret() method that concrete expressions must implement. It represents the abstract syntax tree nodes.

  • Terminal Expression : Concrete expressions that implement the AbstractExpression interface for terminal symbols in the grammar. They represent the leaves of the abstract syntax tree

  • Non-terminal Expression : Concrete expressions that implement the AbstractExpression interface for non-terminal symbols in the grammar. They represent nodes with one or more child expressions.

  • Context : The context contains information that is global to the interpreter. It may include variables, constants, or other contextual information required during interpretation.

  • Client : The client is responsible for building the abstract syntax tree using terminal and non-terminal expressions. It also provides the context in which the interpretation will occur.

Advantages of Interpreter Design Pattern

The Interpreter Design Pattern offers several advantages that make it a valuable tool for language interpretation:
  • Modularity and Extensibility : The pattern promotes a modular design, allowing each expression to be implemented as a separate class. This modularity facilitates the addition of new expressions and the extension of the language grammar.

  • Clear Separation of Concerns : The pattern enforces a clear separation of concerns between the interpreter and the language expressions. This separation makes it easier to understand, maintain, and extend the interpreter.

  • Ease of Grammar Changes : Making changes to the language grammar becomes easier with the Interpreter pattern. New expressions can be added or existing ones modified without affecting the overall structure of the interpreter.

  • Reuse of Expression Classes : Expression classes can be reused across different interpreters if they conform to the same interface. This reusability promotes code sharing and reduces redundancy.

  • Dynamic Interpretation : The Interpreter pattern supports dynamic interpretation, where expressions can be interpreted at runtime based on user input or other dynamic factors. This dynamic nature is beneficial for scenarios where the language evolves dynamically.

  • Pattern Compatibility : The Interpreter pattern can be combined with other design patterns, such as the Composite pattern for handling complex expressions or the Flyweight pattern for optimizing memory usage. This compatibility enhances the overall design.

  • Portability : Interpreters built using this pattern can be portable across different platforms and environments. The interpretation logic remains consistent, allowing the same interpreter to be used in various contexts.

When we should use Interpreter Pattern

  • It is not suitable for building a whole large interpreter for a language. It can be used when the grammar of the language is simple.
  • When we want to model a simple a recursive grammar.
  • When simple implementation is high priority then than efficiency.

Implementation of Interpreter Design Pattern

Interpreter Design Pattern UML Diagram

The Expression interface requires all expression classes to have common 'evaluate' method which ensure all expressions can be handled equally.

Expression.java
public interface Expression {
    public int evaluate();
}

The WholeNumber class implements the Expression interface and it represents a number operand. Inside evaluate method, it just returns the numerical value. In the arithmetic expression tree, it is known as TerminalExpressions and represents the leaf node.

WholeNumber.java
public class WholeNumber implements Expression {
    private int number;

    public WholeNumber(int number) {
        this.number = number;
    }

    public WholeNumber(String str) {
        this.number = Integer.parseInt(str);
    }

    @Override
    public int evaluate() {
        return number;
    }
}

Now we will create concrete implementation of Expression interface to represent Addition, Subtraction, Multiply and Division binary operations. It contains two Expressions as operands and represents the internal nodes of expression tree also known as NonTerminalExpressions.

Addition.java
public class Addition implements Expression {
    private Expression leftOperand;
    private Expression rightOperand;
 
    public Addition(Expression leftOp, Expression rightOp){
        this.leftOperand = leftOp;
        this.rightOperand = rightOp;
    }
 
    @Override
    public int evaluate(){
        return leftOperand.evaluate() + rightOperand.evaluate();
    }
}

Subtraction.java
public class Subtraction implements Expression {
    private Expression leftOperand;
    private Expression rightOperand;
 
    public Subtraction(Expression leftOp, Expression rightOp){
        this.leftOperand = leftOp;
        this.rightOperand = rightOp;
    }
 
    @Override
    public int evaluate(){
        return leftOperand.evaluate() - rightOperand.evaluate();
    }
}

Multiply.java
public class Multiply implements Expression {
    private Expression leftOperand;
    private Expression rightOperand;
 
    public Multiply(Expression leftOp, Expression rightOp){
        this.leftOperand = leftOp;
        this.rightOperand = rightOp;
    }
 
    @Override
    public int evaluate(){
        return leftOperand.evaluate() * rightOperand.evaluate();
    }
}

Divide.java
public class Divide implements Expression {
    private Expression numerator;
    private Expression denominator;
 
    public Divide(Expression numerator, Expression denominator){
        this.numerator = numerator;
        this.denominator = denominator;
    }
 
    @Override
    public int evaluate(){
        try {
            return numerator.evaluate() / denominator.evaluate();
        } catch (ArithmeticException e) {
            System.out.println("Division by Zero Exception");
            throw e;
        }
    }
}

InterpreterPatternExample is the arithmetic expression parser that takes a postfix expression and evaluate it using above expression classes. In postfix representation of an expression the operator comes after the operand. Example (1 2 +) is the postfix representation of (1 + 2)

InterpreterPatternExample.java
import java.util.Stack;

public class InterpreterPatternExample {
    public static void main(String args[]) {
 Stack stack = new Stack();
 String postFix = "5 3 * 2 + 1 - 4 /"; // (5 * 3 + 2 - 1)/4

 String[] tokenList = postFix.split(" ");
 for (String s : tokenList) {
     if (isOperatorString(s)) {
  Expression rightOp = (Expression)stack.pop();
  Expression leftOp = (Expression)stack.pop();
  Expression operator = getOperatorHandler(s, leftOp,
   rightOp);
  int result = operator.evaluate();
  stack.push(new WholeNumber(result));
     } else {
  Expression num = new WholeNumber(s);
  stack.push(num);
     }
 }
 System.out.println(((Expression)stack.pop()).evaluate());
    }

    public static boolean isOperatorString(String str) {
 if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/"))
     return true;
 else
            return false;
    }

    public static Expression getOperatorHandler(String str, Expression left,
     Expression right) {
 switch (str) {
     case "+":
  return new Addition(left, right);
     case "-":
  return new Subtraction(left, right);
     case "*":
  return new Multiply(left, right);
     case "/":
  return new Divide(left, right);
     default:
  return null;
 }
    }
}

Output

4

Important points about Interpreter pattern
  • Interpreter can be used to implement a simple language grammar.
  • This pattern comes under behavioral design pattern.

Best Practices of Interpreter Design Pattern

To ensure a robust and maintainable implementation of the Interpreter Design Pattern, follow these best practices:
  • Clear Definition of Grammar : Clearly define the grammar for the language you are interpreting. This includes specifying terminal and non-terminal symbols and their relationships. A well-defined grammar is crucial for creating expressive and correct interpreters.

  • Separate Terminal and Non-terminal Expressions : Clearly separate terminal expressions (leaves) from non-terminal expressions (nodes) in your implementation. This enhances the clarity of the code and makes it easier to extend the grammar.

  • Use the Composite Pattern for Expressions : If the grammar involves complex expressions with nested structures, consider using the Composite Pattern to represent expressions as composites of simpler expressions. This simplifies the creation and interpretation of complex expressions.

  • Modular Design : Design your interpreter in a modular way, with each expression class responsible for a specific language construct. This promotes code organization and maintainability.

  • Use Context for State Information : Utilize the context to store and manage state information relevant to interpretation. The context can store variable values, constants, or other information needed during the interpretation process.

  • Error Handling : Implement error handling mechanisms to handle invalid or unexpected input. This is crucial for providing meaningful feedback when interpreting expressions that do not conform to the defined grammar.

  • Consider Caching Results : Depending on the nature of your interpreter, consider implementing caching mechanisms to store and reuse previously computed results. This can improve performance, especially for expressions with repetitive subexpressions.

  • Consistent Naming Conventions : Use consistent and meaningful naming conventions for your expression classes. This makes it easier for developers to understand the purpose of each class and its role in the interpreter.
Related Topics
Mediator Design Pattern
Bridge Design Pattern
Prototype Design Pattern
Builder Design Pattern
Factory Design Pattern
List of Design Patterns