Home/ Behavioral/ Interpreter
Behavioral

Interpreter

Define a grammar for a language and provide an interpreter to evaluate sentences in that language.

Advanced Pattern #15 of 23
01 — Intent

What is the Interpreter Pattern?

Interpreter defines a representation for a language's grammar using a class hierarchy, and provides an interpreter that uses the representation to interpret sentences in that language. Each grammar rule becomes a class; evaluating an expression means calling interpret() on the tree of rule objects.

It is most useful for simple, domain-specific languages (DSLs) — mathematical expressions, query languages, configuration rule engines, boolean filters.

Real-world analogy: A simple calculator. The expression 3 + 5 * 2 is parsed into a tree: Add(3, Multiply(5, 2)). Each node is an Interpreter class. Calling interpret() on the root evaluates the whole expression recursively.
02 — Problem

The Problem It Solves

You need to evaluate boolean search expressions like java AND (spring OR hibernate) NOT legacy. The grammar is recursive — expressions can be nested. A single massive if-else parser becomes unmaintainable when the grammar grows.

Interpreter maps each grammar rule to a class: AndExpression, OrExpression, NotExpression, TerminalExpression. The expression tree is built from these, and interpret(context) evaluates it naturally.

03 — Solution

Participants

AbstractExpression
Declares the interpret(context) method that all concrete expressions implement.
TerminalExpression
Implements interpretation for the leaf nodes of the grammar — the base cases that don't contain sub-expressions.
NonterminalExpression
Implements grammar rules that contain other expressions. Calls interpret() on its children and combines results.
Context
Contains global information for the interpreter — variables, input data, or state that expressions need during evaluation.
Client
Builds the abstract syntax tree from TerminalExpressions and NonterminalExpressions, then calls interpret(context) on the root.
04 — Structure

Visual Flow Diagram

«interface» Expression interpret(ctx) TerminalExpression interpret() → base case NonterminalExpression left, right: Expression interpret() → left+right.interpret() Context variables / input Parse tree: AND( OR("java","spring"), NOT("legacy") ).interpret(ctx) → true/false
05 — Implementation

Java Code Example

Java — Boolean Search Expression Interpreter
// AbstractExpression
public interface Expression {
    boolean interpret(String context);
}

// TerminalExpression — leaf node, checks if word is in context
public class TerminalExpression implements Expression {
    private final String word;
    public TerminalExpression(String word) { this.word = word; }

    public boolean interpret(String ctx) {
        return ctx.contains(word); // base case
    }
}

// NonterminalExpression — AND
public class AndExpression implements Expression {
    private final Expression left, right;
    public AndExpression(Expression l, Expression r) { left=l; right=r; }

    public boolean interpret(String ctx) {
        return left.interpret(ctx) && right.interpret(ctx);
    }
}

// NonterminalExpression — OR
public class OrExpression implements Expression {
    private final Expression left, right;
    public OrExpression(Expression l, Expression r) { left=l; right=r; }

    public boolean interpret(String ctx) {
        return left.interpret(ctx) || right.interpret(ctx);
    }
}

// NonterminalExpression — NOT
public class NotExpression implements Expression {
    private final Expression expr;
    public NotExpression(Expression e) { expr = e; }

    public boolean interpret(String ctx) {
        return !expr.interpret(ctx);
    }
}

// Client builds AST and evaluates
public class Main {
    public static void main(String[] args) {
        // Build: "java AND (spring OR hibernate) AND NOT legacy"
        Expression java      = new TerminalExpression("java");
        Expression spring    = new TerminalExpression("spring");
        Expression hibernate = new TerminalExpression("hibernate");
        Expression legacy    = new TerminalExpression("legacy");

        Expression query = new AndExpression(java,
                               new AndExpression(
                                   new OrExpression(spring, hibernate),
                                   new NotExpression(legacy)));

        System.out.println(query.interpret("java spring microservices")); // true
        System.out.println(query.interpret("java legacy code"));         // false (has legacy)
        System.out.println(query.interpret("python django"));             // false (no java)
    }
}
06 — Applicability

When to Use / Avoid

✓ Use When

  • Grammar is simple and stable — complex grammars need real parser generators
  • Efficiency is not critical — interpreter is not the fastest evaluation method
  • Building a DSL: rule engines, query filters, config expressions, math parsers
  • Adding new expression types is more common than changing the grammar rules

✕ Avoid When

  • Grammar is large or complex — use ANTLR, JavaCC, or a real parser instead
  • Performance is critical — recursive tree traversal is slow for complex expressions
  • Grammar changes frequently — every change ripples through many classes
07 — Real World

Real-World Examples

08 — Trade-offs

Pros & Cons

Pros

  • Easy to extend — add new expression types without touching existing ones
  • Grammar rules are first-class objects — easy to combine, test, and reuse
  • Natural mapping between grammar and class hierarchy

Cons

  • Class explosion for complex grammars — one class per grammar rule
  • Hard to maintain if grammar is large or changes frequently
  • Performance poor for deeply nested expressions
09 — Break & Prevent

How Interpreter Can Be Broken

⚠ Attack Vectors

  • Deeply nested expressions → stack overflow: Recursive interpret() calls on a deeply nested expression tree exhaust the call stack
  • Mutable context shared across threads: Two threads evaluate expressions on the same Context simultaneously — one overwrites variables the other is reading
  • Missing null check in non-terminal: If a child expression is null (e.g., new AndExpression(left, null)), interpret() throws NPE deep in recursion with no useful stack trace
  • Grammar ambiguity: Two grammar rules match the same input — expressions produce different results depending on which node the client builds first

✓ Prevention

  • Depth limit: Track nesting depth in the context — throw if it exceeds a max (e.g., 100 levels) to prevent stack overflow from malicious or malformed input
  • Immutable or thread-local context: Pass a new Context instance per evaluation thread — never share mutable Context across concurrent evaluations
  • Null-guard in constructors: Every non-terminal's constructor validates that child expressions are non-null using Objects.requireNonNull()
  • Iterative evaluation for deep trees: Replace recursive interpret() with an explicit evaluation stack (Deque) for grammars that may produce deep trees
Java — Break & Fix
// ❌ BREAKING — null child expression
Expression bad = new AndExpression(java, null);
bad.interpret("java spring"); // NPE inside AndExpression.interpret()

// ✅ FIX — null-guard in constructor
public AndExpression(Expression l, Expression r) {
    this.left  = Objects.requireNonNull(l, "left expression required");
    this.right = Objects.requireNonNull(r, "right expression required");
}

// ❌ BREAKING — no depth limit, malicious input → StackOverflow
public boolean interpret(String ctx) {
    return left.interpret(ctx) && right.interpret(ctx); // unlimited depth
}

// ✅ FIX — depth-aware context
public class Context {
    private int depth = 0;
    private static final int MAX_DEPTH = 100;

    public void enterExpression() {
        if (++depth > MAX_DEPTH)
            throw new IllegalStateException("Expression too deeply nested");
    }
    public void exitExpression() { depth--; }
}

public boolean interpret(Context ctx) {
    ctx.enterExpression();
    try {
        return left.interpret(ctx) && right.interpret(ctx);
    } finally {
        ctx.exitExpression();
    }
}
10 — Related Patterns

How Other Patterns Relate

Composite
Often Used Together
The abstract syntax tree is a Composite tree. NonterminalExpressions are composites; TerminalExpressions are leaves. Interpreter is essentially Composite applied to language grammars.
Visitor
Often Used Together
Visitor can add new operations to an AST without changing expression classes — e.g., a TypeCheckVisitor and an EvalVisitor both traverse the same tree using the Visitor pattern.
Iterator
Often Used Together
Iterator traverses the expression tree during interpretation. A breadth-first or depth-first iterator can be used instead of direct recursion to avoid stack overflow.
11 — Quick Recap

Interview Cheat Sheet

  1. What: Maps grammar rules to classes. Builds an AST (abstract syntax tree) from expression objects. Calls interpret(context) on the root to evaluate the expression recursively.
  2. How: Expression interface with interpret(ctx). TerminalExpression = leaf (base case). NonterminalExpression = composite (delegates to children). Client builds tree, calls root.interpret().
  3. When not to use: For complex grammars use ANTLR or JavaCC. Interpreter is only practical for simple, stable, DSL-style grammars with ~5–15 rules.
← PreviousCommand Next →Iterator