15. Interpreter

The Interpreter pattern defines a representation for a language’s grammar and provides an interpreter to evaluate sentences in that language. It maps each grammar rule to a class, building an abstract syntax tree that can be evaluated recursively.

Intent and Motivation link

Intent: Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

Motivation: Domain-specific mini-languages appear everywhere: search query syntax (name:Alice AND age>30), configuration rules (if temperature > 100 then alert), and arithmetic expressions (3 + 4 * 2). Hard-coding parsers with nested if-else becomes unmaintainable. Interpreter models each grammar production as a class (NumberExpression, AddExpression, VariableExpression) that implements a common interpret(Context) method. Composite expressions combine simpler ones, forming a tree that evaluates bottom-up.

Use Interpreter when the grammar is simple; for complex languages, use parser generators (ANTLR, yacc).

Structure (UML-like) link

  ┌──────────────────┐
│   Expression     │ (interface)
├──────────────────┤
│ + interpret(ctx) │
└────────▲─────────┘
         │
    ┌────┴────────────────────┐
    │                         │
┌───┴────────────┐    ┌───────┴──────────┐
│TerminalExpr.   │    │ NonTerminalExpr. │
│ (Number, Var)  │    │ (Add, Subtract)  │
├────────────────┤    ├──────────────────┤
│ + interpret()  │    │ - left, right    │
└────────────────┘    │ + interpret()     │
                      └──────────────────┘

┌──────────┐
│ Context  │ — stores variable bindings and global state
└──────────┘
  

Participants:

• AbstractExpression — declares interpret(context).
• TerminalExpression — implements grammar rules for terminal symbols (literals, variables).
• NonterminalExpression — implements grammar rules for productions; composes other expressions.
• Context — contains information global to the interpreter (variable map, etc.).
• Client — builds the expression tree and invokes interpret().

Java Example link

  import java.util.*;

// Context
class EvalContext {
    private final Map<String, Integer> variables = new HashMap<>();
    void set(String name, int value) { variables.put(name, value); }
    int get(String name) { return variables.getOrDefault(name, 0); }
}

// Expression interface
interface Expression {
    int interpret(EvalContext ctx);
}

// Terminal — number literal
class NumberExpr implements Expression {
    private final int value;
    NumberExpr(int value) { this.value = value; }
    public int interpret(EvalContext ctx) { return value; }
}

// Terminal — variable
class VariableExpr implements Expression {
    private final String name;
    VariableExpr(String name) { this.name = name; }
    public int interpret(EvalContext ctx) { return ctx.get(name); }
}

// Non-terminal — addition
class AddExpr implements Expression {
    private final Expression left, right;
    AddExpr(Expression left, Expression right) {
        this.left = left; this.right = right;
    }
    public int interpret(EvalContext ctx) {
        return left.interpret(ctx) + right.interpret(ctx);
    }
}

// Usage — interpret "x + 3" where x = 7
EvalContext ctx = new EvalContext();
ctx.set("x", 7);
Expression expr = new AddExpr(new VariableExpr("x"), new NumberExpr(3));
System.out.println(expr.interpret(ctx)); // 10
  

JavaScript Example link

  // Simple boolean rule interpreter
const rules = {
  and: (left, right, data) => left(data) && right(data),
  or: (left, right, data) => left(data) || right(data),
  gt: (field, value) => (data) => data[field] > value,
  eq: (field, value) => (data) => data[field] === value
};

function interpret(node, data) {
  if (node.type === 'gt') return rules.gt(node.field, node.value)(data);
  if (node.type === 'eq') return rules.eq(node.field, node.value)(data);
  if (node.type === 'and') {
    return rules.and(
      (d) => interpret(node.left, d),
      (d) => interpret(node.right, d),
      data
    );
  }
  return false;
}

const rule = {
  type: 'and',
  left: { type: 'gt', field: 'age', value: 18 },
  right: { type: 'eq', field: 'country', value: 'US' }
};

console.log(interpret(rule, { age: 25, country: 'US' })); // true
console.log(interpret(rule, { age: 16, country: 'US' })); // false
  

Real-World Use Cases link

Pros and Cons link

When to Use vs When NOT to Use link

Use when:

• The grammar is simple and does not change frequently.
• Efficiency is not critical (interpretation overhead is acceptable).
• The language is small enough that class-per-rule is manageable.
• You need runtime evaluation of user-defined expressions or rules.

Do NOT use when:

• The grammar is complex (use ANTLR, Lex/Yacc, or a parser combinator library).
• Performance is critical and expressions are evaluated millions of times (compile to bytecode).
• The language changes frequently in ways that break many expression classes.
• A simple eval() or embedded scripting language (Groovy, Lua) is sufficient.

Common Mistakes link

1. Using Interpreter for complex languages — leads to hundreds of classes; use a parser generator instead.
2. No error handling in interpret() — undefined variables or type mismatches crash silently.
3. Mutable expression trees — expressions should be immutable once constructed.
4. Mixing parsing with interpretation — separate the parser (builds tree) from the interpreter (evaluates tree).
5. Security risks — interpreting user-supplied expressions without sandboxing enables code injection.

Related Patterns link

• Composite — expression trees are composites of terminal and non-terminal expressions.
• Flyweight — terminal expressions for common literals can be shared flyweights.
• Strategy — different interpretation strategies for the same expression tree.
• Visitor — traverses and operates on expression trees without modifying expression classes.
• Template Method — non-terminal expressions can use Template Method for shared interpretation steps.