Skip to content
a Programmer

Interpreter Design Pattern (Behavioral)

Intent

Section titled “Intent”

Interpreter is a behavioral design pattern that defines a grammatical representation for a language and provides an interpreter to deal with this grammar. It is used to evaluate sentences in a language by representing each grammar rule as a class.

Problem

Section titled “Problem”

Suppose you have a specific, recurring set of problems that can be solved by processing a simple language or set of rules (e.g., SQL parsing, mathematical expressions, or regular expressions). Building a hard-coded solution for every possible variation of these rules is inefficient and difficult to maintain.

If the problem occurs frequently enough, you might want to express instances of the problem as sentences in a simple language. However, you then need a mechanism to parse and execute these sentences.

Solution

Section titled “Solution”

The Interpreter pattern suggests defining a class for each symbol (terminal or non-terminal) in the language. You represent the grammar of the language as an Abstract Syntax Tree (AST).

Each class in the tree implements an interpret() method. This method takes a context (global information) and performs the evaluation. Non-terminal expressions delegate the work to their child expressions, effectively traversing the tree until the entire sentence is evaluated.

Real-World Analogy

Section titled “Real-World Analogy”

Think of a musical score. The sheet music acts as the language. Each note, rest, and dynamic marking is a symbol with a specific meaning. A musician acts as the interpreter. They read the symbols (the grammar) and translate them into sounds (the execution), using their knowledge of music theory as the context.

Structure

Section titled “Structure”
  1. Abstract Expression: Declares an abstract interpret() method that all nodes in the syntax tree must implement.
  2. Terminal Expression: Implements the interpret() method for symbols that do not contain other expressions (the “leaves” of the grammar).
  3. Non-terminal Expression: Represents grammar rules that combine other expressions. Its interpret() method typically calls interpret() on its children and combines the results.
  4. Context: Contains global information or data that is required by the interpreter to perform its task.
  5. Client: Builds the Abstract Syntax Tree representing a specific sentence in the defined language and triggers the interpretation.

Structure (Class Diagram)

Section titled “Structure (Class Diagram)”
classDiagram
    class Context {
    }
    class AbstractExpression {
        <<interface>>
        +interpret(Context)
    }
    class TerminalExpression {
        +interpret(Context)
    }
    class NonTerminalExpression {
        -child1: AbstractExpression
        -child2: AbstractExpression
        +interpret(Context)
    }

    AbstractExpression <|-- TerminalExpression
    AbstractExpression <|-- NonTerminalExpression
    NonTerminalExpression o-- AbstractExpression
    Client --> AbstractExpression
    Client --> Context

Pseudocode

Section titled “Pseudocode”
# The Context holds data used during interpretation.
class Context:
    variables = {}
    method set(name, value): variables[name] = value
    method get(name): return variables[name]


# The Abstract Expression interface.
interface Expression:
    method interpret(context): int


# Terminal expression for variables.
class VariableExpression implements Expression:
    field name: string
    method interpret(context): return context.get(name)


# Non-terminal expression for addition.
class AddExpression implements Expression:
    field left: Expression
    field right: Expression
    method interpret(context):
        return left.interpret(context) + right.interpret(context)


# Client builds the tree: (x + y)
# Context provides values: x=10, y=5

Applicability

Section titled “Applicability”
  • Simple Grammars: Use the pattern when the grammar of the language is simple. Complex grammars are better handled by specialized parser generators.
  • Efficiency is not the main concern: Interpreting an AST is generally slower than translating the language into a lower-level format.
  • Rule Engines: Use it when you need to represent and evaluate business rules that can be expressed as a tree structure.

How to Implement

Section titled “How to Implement”
  1. Define the grammar of the language.
  2. Create an abstract interface for the expressions with an interpret(context) method.
  3. Create terminal expression classes for the literal symbols in the language.
  4. Create non-terminal expression classes for each rule in the grammar. These classes should store references to other expressions.
  5. Create a context class to store any global state.
  6. The client constructs the Abstract Syntax Tree and calls interpret() on the root node.

Pros and Cons

Section titled “Pros and Cons”

Pros:

  • Easy to Change Grammar: Because each rule is represented by a class, you can change or extend the grammar using inheritance.
  • Simplifies Implementation: Defining the grammar rules as classes makes the logic for evaluating expressions clear and organized.

Cons:

  • Complexity with Large Grammars: A class is required for every rule; for complex languages, the class hierarchy becomes unmanageable.
  • Performance: Building and traversing an AST is resource-intensive compared to other parsing techniques.

Relations with other Design Patterns

Section titled “Relations with other Design Patterns”
  • Composite: The Abstract Syntax Tree is often an instance of the Composite pattern.
  • Flyweight: You can use Flyweight to share terminal symbols within the AST to save memory.
  • Iterator: The interpreter can use an Iterator to traverse the structure.
  • Visitor: You can use Visitor to encapsulate operations on the AST instead of putting the logic inside the expression classes.

Code Examples

Section titled “Code Examples”

Code Examples (C#)

Section titled “Code Examples (C#)”
// Context
public class Context
{
    public string Input { get; set; }
    public int Output { get; set; }
}


// Abstract expression
public abstract class Expression
{
    public abstract void Interpret(Context context);
}


// Concrete expressions
public class OneExpression : Expression
{
    public override void Interpret(Context context)
    {
        if (context.Input.StartsWith("1"))
        {
            context.Output += 1;
            context.Input = context.Input.Substring(1);
        }
    }
}


public class TwoExpression : Expression
{
    public override void Interpret(Context context)
    {
        if (context.Input.StartsWith("2"))
        {
            context.Output += 2;
            context.Input = context.Input.Substring(1);
        }
    }
}


// Usage
class Program
{
    static void Main()
    {
        var context = new Context { Input = "12121" };


        var tree = new List&lt;Expression&gt;
        {
            new OneExpression(),
            new TwoExpression()
        };


        while (!string.IsNullOrEmpty(context.Input))
        {
            foreach (var exp in tree)
                exp.Interpret(context);
        }


        Console.WriteLine($"Resultado: {context.Output}");
    }
}