Behavioral
Interpreter Pattern
Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language. The foundation of expression evaluators, rule engines, query parsers, and DSLs.
Overview · Behavioral · Singleton · Factory Method · Abstract Factory · Builder · Prototype · Adapter · Bridge · Composite · Decorator · Facade · Flyweight · Proxy · Observer · Strategy · Command · Template Method · Chain of Resp. · State · Mediator · Iterator · Visitor · Memento · Interpreter
01
Section One · The Problem
Why Interpreter Exists
You’re building a business rules engine. Users define rules like: "age > 18 AND (country == 'US' OR country == 'UK')". These rules are stored as strings in a database and evaluated at runtime against customer data. The naive approach: parse the string with a giant if/else chain or regex.
Naive approach — hard-coded rule parsing
// ✗ Hard-coded string parsing — no grammar, no extensibility boolean evaluate(String rule, Customer c) {
if (rule.contains("AND")) {
String[] parts = rule.split("AND");
return evaluate(parts[0], c) && evaluate(parts[1], c);
} else if (rule.contains("OR")) {
String[] parts = rule.split("OR");
return evaluate(parts[0], c) || evaluate(parts[1], c);
} else if (rule.contains(">")) {
// parse left/right, compare...
} else if (rule.contains("==")) {
// string equality...
}
// What about nested parentheses? NOT? Operator precedence? // This quickly becomes unmaintainable spaghetti.
}
What goes wrong:
- No formal grammar — the parsing logic is ad-hoc; adding
NOT,>=, or nested expressions requires rewriting the parser - Operator precedence ignored —
split("AND")doesn’t respect parentheses or precedence - Can’t compose expressions — no tree structure; complex rules can’t be built from simpler ones
- No reuse — each new operator/literal requires duplicating parsing logic
- Untestable — the monolithic evaluator can’t be unit-tested at the expression level
Without Interpreter — ad-hoc string parsing
This is the problem Interpreter solves — define a formal grammar for the language, represent each grammar rule as a class, and build a tree (AST) of expression objects that can interpret() themselves. Adding a new operator = adding one class.
02
Section Two · The Pattern
What Is Interpreter?
Interpreter is a behavioral pattern that defines a representation for a grammar and an interpreter that evaluates sentences in that language. Each grammar rule becomes a class. Terminal symbols (literals, variables) are leaf nodes; non-terminal symbols (operators, combinators) are composite nodes containing sub-expressions. The resulting tree structure is evaluated recursively.
GoF Intent: “Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.”
— Gamma, Helm, Johnson, Vlissides (1994)
— Gamma, Helm, Johnson, Vlissides (1994)
Analogy — mathematical expression evaluation: Consider
3 + 4 * 2. A human parses this into a tree: the root is +, the left child is 3, the right child is * (4, 2). To evaluate: the * node interprets itself (4 × 2 = 8), then the + node interprets itself (3 + 8 = 11). Each node is an “expression object” that knows how to evaluate itself. Numbers are terminal expressions (leaves); operators are non-terminal expressions (composites). The entire tree is the “interpreter.”
Key insight: Interpreter = Composite pattern applied to a grammar. Each grammar rule produces a class. The class hierarchy mirrors the grammar’s BNF. Sentences in the language are represented as trees of expression objects. Evaluation is a recursive tree traversal where each node “interprets” itself.
Define a grammar:
Expr = Number | Expr '+' Expr | Expr '*' Expr | '(' Expr ')'▶
Each production rule becomes a class:
NumberExpr, AddExpr, MulExpr. The grammar is the class hierarchy.Parse input into an Abstract Syntax Tree (AST) of expression objects
▶
"3 + 4 * 2" becomes: AddExpr(NumberExpr(3), MulExpr(NumberExpr(4), NumberExpr(2)))Each expression class has an
interpret(context) method▶
Leaf nodes return their value. Composite nodes evaluate children recursively, then combine results with their operator.
Adding a new operator (e.g.
SubtractExpr) = adding one class▶
Open/Closed for grammar rules. Existing expression classes are untouched. The parser must handle the new syntax, but the interpreter is extensible.
03
Section Three · Anatomy
Participants & Structure
| Participant | Role | In the Analogy |
|---|---|---|
| AbstractExpression (interface) | Declares the interpret(Context) method. All grammar rules implement this interface. Forms the common type for the AST tree nodes. | The “mathematical entity” contract — every number and operator can be “evaluated.” |
| TerminalExpression | Implements interpret() for terminal symbols (literals, variables). Leaf nodes of the AST. E.g., NumberExpr(5) returns 5; VarExpr("x") looks up x in the context. | Numbers in a math expression — they just are their value. |
| NonTerminalExpression | Implements interpret() for grammar rules involving other expressions. Contains references to sub-expressions (like Composite). E.g., AddExpr(left, right) evaluates left + right. | Operators (+, *, /) — they combine the values of their operands. |
| Context | Contains global information the interpreter needs during evaluation — variable bindings, function definitions, configuration. Passed to every interpret() call. | The “variable table” — mapping variable names to values (x=5, y=3). |
| Client | Builds (or receives) the AST and calls interpret(context) on the root. May include a parser that converts string input into the AST. | You writing 3 + x on paper and asking “evaluate this with x=7.” |
Interpreter — UML Class Diagram
Interpreter = Composite for grammars:
- Terminal expressions are leaves; non-terminal expressions are composites containing sub-expressions.
- The
interpret()method is the equivalent of Composite’s recursiveoperation(). - If you understand Composite, you understand Interpreter’s structure.
- The difference is that Interpreter defines a language with grammar rules, while Composite defines a part-whole hierarchy.
04
Section Four · How It Works
The Pattern In Motion
Scenario: Evaluate the expression "3 + x * 2" with the context {x = 5}. The expression is parsed into an AST, then the root’s interpret() is called recursively.
Step 1 — Parse
"3 + x * 2" into an AST▶
AST:
AddExpr( NumberExpr(3), MulExpr( VarExpr("x"), NumberExpr(2) ) ). Operator precedence handled during parsing — * binds tighter than +.Step 2 — Call
root.interpret(ctx) where ctx = {x:5}▶
AddExpr.interpret(ctx) is called. It must evaluate its left and right children first.Step 3 — Left child:
NumberExpr(3).interpret(ctx)▶
Returns
3. Terminal expression — just returns its value. No recursion needed.Step 4 — Right child:
MulExpr.interpret(ctx)▶
Recursively evaluates its children:
VarExpr("x").interpret(ctx) → looks up x in context → 5. NumberExpr(2).interpret(ctx) → 2. Returns 5 × 2 = 10.Step 5 —
AddExpr combines: left(3) + right(10)▶
Returns
13. The entire expression is evaluated by recursive tree traversal. Each node only knows its own operation.Interpreter — AST Evaluation Tree
The pattern in pseudocode
// ── Build the AST manually (normally a parser does this) ── Expression expr = new AddExpr(
new NumberExpr(3),
new MulExpr(
new VarExpr("x"),
new NumberExpr(2)
)
);
// ── Create context with variable bindings ── Map<String, Integer> ctx = Map.of("x", 5);
// ── Evaluate: recursive tree traversal ── int result = expr.interpret(ctx);
System.out.println(result); // 13 // ── Change x to 10 — same AST, different result ──
ctx = Map.of("x", 10);
System.out.println(expr.interpret(ctx)); // 3 + 10*2 = 23
Separation of parsing and interpreting:
- The Interpreter pattern focuses on the evaluation of the AST, not the parsing of the input string.
- In practice, you need a parser (recursive descent, Pratt parser, or a library like ANTLR) to convert
"3 + x * 2"into the AST. - The pattern handles what happens after parsing.
05
Section Five · Java Stdlib
You Already Use This
Interpreter appears wherever a “mini-language” is parsed and evaluated — regex engines, expression languages, SQL parsers, and template systems.
IN JAVA
Example 1
java.util.regex.Pattern — compiles a regex string ("[a-z]+\\d{2,3}") into an internal AST of expression nodes (character classes, quantifiers, alternations). Matcher interprets this AST against input strings. Each regex construct is a node type. Example 2
javax.el.ExpressionFactory (JSP/JSF Expression Language) — ${user.name} is parsed into an AST and interpreted against a context. ValueExpression and MethodExpression are the expression interfaces. Example 3
Spring SpEL (Spring Expression Language) — "#root.name?.toUpperCase()" is parsed by SpelExpressionParser into an AST of SpelNode objects. getValue(context) interprets the tree. SpEL supports method calls, operators, collections, and ternary expressions. Example 4
java.text.Format subclasses — MessageFormat.format("Hello 0, you have 1 items", name, count) parses the pattern string into format segments (literal text + placeholders). Each segment is interpreted against the arguments array. Stdlib usage — Spring SpEL as Interpreter
// Spring SpEL is a full Interpreter implementation SpelExpressionParser parser = new SpelExpressionParser();
// Parse string → AST Expression expr = parser.parseExpression("name.length() > 5 AND age >= 18");
// Create context (variable bindings) StandardEvaluationContext ctx = new StandardEvaluationContext();
ctx.setVariable("name", "Alexander");
ctx.setVariable("age", 25);
// Interpret — recursive AST evaluation Boolean result = expr.getValue(ctx, Boolean.class); // true
Stdlib usage — Regex as Interpreter
// java.util.regex.Pattern compiles regex into an interpreter AST Pattern p = Pattern.compile("[A-Z][a-z]+ \\d+"); // parse → AST Matcher m = p.matcher("Hello 42 World 7"); // interpret against input while (m.find()) {
System.out.println(m.group()); // "Hello 42" — not "World 7" (no space \\d+)
}
// Internally: CharClass('A-Z') → CharClass('a-z') → Quantifier(+) → Literal(' ') → ...
Every DSL parser is an Interpreter:
- SQL parsers (H2, JOOQ), JPQL (Hibernate), Cron expressions (Quartz), JSON Path (Jayway), XPath, CSS selectors — all parse a string into an AST and evaluate it.
- The Interpreter pattern is the theoretical foundation.
- In practice, most use parser generators (ANTLR, JavaCC) rather than hand-coding the pattern.
06
Section Six · Implementation
Build It Once
Domain: Arithmetic Expression Evaluator with variables. Grammar: Expr = Number | Variable | Expr '+' Expr | Expr '-' Expr | Expr '*' Expr. Each rule is a class with interpret(Map<String,Integer>).
Java — Interpreter Pattern Arithmetic Evaluator (core)
// ── Abstract Expression ── interface Expression {
int interpret(Map<String, Integer> ctx);
}
// ── Terminal: Number ── record NumberExpr(int value) implements Expression {
public int interpret(Map<String, Integer> ctx) { return value; }
}
// ── Terminal: Variable ── record VarExpr(String name) implements Expression {
public int interpret(Map<String, Integer> ctx) { return ctx.get(name); }
}
// ── NonTerminal: Add ── record AddExpr(Expression left, Expression right) implements Expression {
public int interpret(Map<String, Integer> ctx) {
return left.interpret(ctx) + right.interpret(ctx);
}
}
Interpreter — Full Implementation
Java — Complete Interpreter + Expressions + Parser + Driver
import java.util.*;
// ═══ Expression Interface ═══ interface Expression {
int interpret(Map<String, Integer> ctx);
}
// ═══ Terminal: Number Literal ═══ record NumberExpr(int value) implements Expression {
public int interpret(Map<String, Integer> ctx) { return value; }
@Override public String toString() { return String.valueOf(value); }
}
// ═══ Terminal: Variable Reference ═══ record VarExpr(String name) implements Expression {
public int interpret(Map<String, Integer> ctx) {
if (!ctx.containsKey(name))
throw new IllegalArgumentException("Undefined: " + name);
return ctx.get(name);
}
@Override public String toString() { return name; }
}
// ═══ NonTerminal: Addition ═══ record AddExpr(Expression left, Expression right) implements Expression {
public int interpret(Map<String, Integer> ctx) {
return left.interpret(ctx) + right.interpret(ctx);
}
@Override public String toString() { return "(" + left + " + " + right + ")"; }
}
// ═══ NonTerminal: Subtraction ═══ record SubExpr(Expression left, Expression right) implements Expression {
public int interpret(Map<String, Integer> ctx) {
return left.interpret(ctx) - right.interpret(ctx);
}
@Override public String toString() { return "(" + left + " - " + right + ")"; }
}
// ═══ NonTerminal: Multiplication ═══ record MulExpr(Expression left, Expression right) implements Expression {
public int interpret(Map<String, Integer> ctx) {
return left.interpret(ctx) * right.interpret(ctx);
}
@Override public String toString() { return "(" + left + " * " + right + ")"; }
}
// ═══ Simple Parser (converts postfix notation to AST) ═══ class PostfixParser {
public static Expression parse(String postfix) {
Deque<Expression> stack = new ArrayDeque<>();
for (String token : postfix.split(" ")) {
switch (token) {
case "+" -> { var r = stack.pop(); stack.push(new AddExpr(stack.pop(), r)); }
case "-" -> { var r = stack.pop(); stack.push(new SubExpr(stack.pop(), r)); }
case "*" -> { var r = stack.pop(); stack.push(new MulExpr(stack.pop(), r)); }
default -> {
try { stack.push(new NumberExpr(Integer.parseInt(token))); }
catch (NumberFormatException e) { stack.push(new VarExpr(token)); }
}
}
}
return stack.pop();
}
}
// ═══ Driver ═══ public class InterpreterDemo {
public static void main(String[] args) {
// Postfix: "3 x 2 * +" means 3 + (x * 2) Expression expr = PostfixParser.parse("3 x 2 * +");
System.out.println("AST: " + expr);
Map<String, Integer> ctx1 = Map.of("x", 5);
System.out.println("x=5 → " + expr.interpret(ctx1)); // 13 Map<String, Integer> ctx2 = Map.of("x", 10);
System.out.println("x=10 → " + expr.interpret(ctx2)); // 23 // Another expression: "a b + c -" means (a + b) - c Expression expr2 = PostfixParser.parse("a b + c -");
Map<String, Integer> ctx3 = Map.of("a", 10, "b", 20, "c", 5);
System.out.println("(a+b)-c = " + expr2.interpret(ctx3)); // 25
}
}
/* Output:
AST: (3 + (x * 2))
x=5 → 13
x=10 → 23
(a+b)-c = 25
*/
Python — Interpreter Pattern Arithmetic Evaluator
from abc import ABC, abstractmethod
# ═══ Abstract Expression ═══ class Expression(ABC):
@abstractmethod
def interpret(self, ctx: dict) -> int: pass # ═══ Terminal: Number ═══ class NumberExpr(Expression):
def __init__(self, value): self.value = value
def interpret(self, ctx): return self.value
def __repr__(self): return str(self.value)
# ═══ Terminal: Variable ═══ class VarExpr(Expression):
def __init__(self, name): self.name = name
def interpret(self, ctx): return ctx[self.name]
def __repr__(self): return self.name
# ═══ NonTerminal: Add, Sub, Mul ═══ class AddExpr(Expression):
def __init__(self, left, right): self.left, self.right = left, right
def interpret(self, ctx): return self.left.interpret(ctx) + self.right.interpret(ctx)
def __repr__(self): return f"({self.left} + {self.right})" class SubExpr(Expression):
def __init__(self, left, right): self.left, self.right = left, right
def interpret(self, ctx): return self.left.interpret(ctx) - self.right.interpret(ctx)
class MulExpr(Expression):
def __init__(self, left, right): self.left, self.right = left, right
def interpret(self, ctx): return self.left.interpret(ctx) * self.right.interpret(ctx)
# ═══ Postfix Parser ═══ def parse_postfix(tokens: str) -> Expression:
stack = []
ops = {"+": AddExpr, "-": SubExpr, "*": MulExpr}
for t in tokens.split():
if t in ops:
r, l = stack.pop(), stack.pop()
stack.append(ops[t](l, r))
else:
try: stack.append(NumberExpr(int(t)))
except ValueError: stack.append(VarExpr(t))
return stack[0]
# ═══ Driver ═══
expr = parse_postfix("3 x 2 * +") # 3 + x*2
print(f"x=5: {expr.interpret({'x': 5})}") # 13
print(f"x=10: {expr.interpret({'x': 10})}") # 23
Records are perfect for expression nodes:
- Java records give you immutable fields, equals/hashCode, and toString for free — ideal for AST nodes which are value objects.
- The
interpret()method is the only behavior. This makes the pattern extremely concise in modern Java.
07
Section Seven · Watch Out
Common Mistakes
Mistake #1 — Using Interpreter for complex grammars: The Interpreter pattern creates one class per grammar rule. For a language with 50+ grammar rules (SQL, a full programming language), you end up with a massive class hierarchy that’s hard to maintain. The GoF themselves warn: Interpreter is for simple grammars only. Fix: For complex languages, use a parser generator (ANTLR, JavaCC) or a dedicated library. Interpreter is best for grammars with 5-15 rules.
Mistake #2 — Ignoring performance (exponential blowup):
- Naive recursive interpretation can be extremely slow for deeply nested expressions or repeated subexpressions.
- Each
interpret()call walks the tree from scratch. - Fix: Cache results (memoization) if expressions contain repeated sub-trees. For hot paths, compile the AST to bytecode (
MethodHandle) or use a stack-based evaluator instead of recursive tree walking.
Mistake #3 — No error handling in interpret():
- If a
VarExprreferences an undefined variable, or division by zero occurs, the interpreter crashes with a cryptic exception. - Fix: Validate the AST before interpretation. Throw domain-specific exceptions (
UndefinedVariableException,DivisionByZeroException) with information about which expression failed. Include the position in the original input if available.
Mistake #4 — Mixing parsing logic into expression classes:
- Developers sometimes put string parsing inside the expression constructor.
- This couples the AST to a specific input format.
- Fix: Keep parsing separate from interpretation. The parser produces the AST; the expression classes only know how to
interpret(). This allows the same AST to be built from different input formats (JSON, XML, string syntax).
Mistake #5 — Mutable context without scoping:
- If the context is a single flat
Mapand expressions can modify it (e.g. assignment), you lose track of scope. - A variable defined in a sub-expression leaks into parent scope.
- Fix: Use a scoped context (chain of maps or a linked stack). When entering a new scope (function call, let binding), push a new frame. When exiting, pop it.
08
Section Eight · Decision Guide
When To Use Interpreter
Use Interpreter When
- You have a simple, well-defined grammar (5-15 rules) that users specify as strings evaluated at runtime
- The language is stable — grammar rules don’t change frequently (adding operators is occasional)
- You need user-configurable rules — business rules, filters, validation expressions stored in a database or config file
- Expressions need to be composed from simpler parts (AND/OR chains, arithmetic from +/*/- building blocks)
- You want runtime evaluation with different contexts (same expression, different variable bindings)
Avoid Interpreter When
- The grammar is complex (30+ rules, ambiguous, context-sensitive) — use ANTLR or a parser generator
- Performance is critical — recursive tree walking is slow; compile to bytecode or use a stack VM instead
- A standard language already exists for the job — don’t reinvent SQL, regex, or cron expressions
- The expressions are static (known at compile time) — just write Java code; no need for runtime interpretation
Interpreter vs. Alternatives
| Approach | Best For | Complexity |
|---|---|---|
| Interpreter ← this | Simple DSLs, rule engines, expression evaluators (5-15 rules) | Low — one class per rule |
| ANTLR / Parser Generator | Complex grammars (SQL, programming languages, config formats) | Medium — grammar file generates parser + visitor |
| Scripting Engine (GraalVM, Nashorn) | Full scripting (JavaScript, Python, Ruby embedded in Java) | High — full language runtime |
| Strategy + Chain of Responsibility | Conditional logic without a grammar (simple if/else chains) | Minimal — no parsing at all |
Decision Flowchart
09
Section Nine · Practice
Problems To Solve
Interpreter problems test whether you can define a grammar, build an AST, implement recursive evaluation, handle contexts, and understand the tradeoff between simplicity and scalability.
| Difficulty | Problem | Key Insight |
|---|---|---|
| Easy | Boolean Expression Evaluator Grammar: Expr = true | false | Var | Expr AND Expr | Expr OR Expr | NOT Expr. Build expression classes: BoolLiteral, VarExpr, AndExpr, OrExpr, NotExpr. Context maps variable names to boolean values. Evaluate: "isAdmin AND (hasPermission OR isSuperUser)" with given context. | Tests basic Interpreter with boolean domain. NotExpr is a unary non-terminal (one child). AndExpr/OrExpr are binary. The context maps strings to booleans. Short-circuit evaluation is optional but demonstrates optimization. |
| Medium | SQL WHERE Clause Interpreter Mini-grammar: Condition = field op value | Condition AND Condition | Condition OR Condition. Operators: =, !=, >, <, LIKE. Build an AST that evaluates rows (Map<String, Object>) against the condition. Example: "age > 18 AND name LIKE 'J%'" evaluated against {age:25, name:"John"} → true. | Tests Interpreter with mixed types (int comparison, string pattern matching). The LIKE operator requires simple wildcard handling (% = any). The context is a row (Map of field→value). This mirrors how query engines filter rows — each row is passed through the condition AST. |
| Medium | Arithmetic with Functions + Infix Parser Extend the basic arithmetic interpreter with: functions ( max(a,b), min(a,b), abs(x)), parenthesised expressions, and a proper infix parser (recursive descent or Pratt). Input: "max(3 + x, y * 2) - abs(z)". Context: {x:4, y:3, z:-5}. | Tests combining Interpreter with a real parser. Functions are non-terminal expressions with N children. The parser must handle arity (how many arguments?). Demonstrates that the pattern is about evaluation; parsing is a separate concern but must produce the correct AST. |
| Hard | Mini Rule Engine with Assignment + Conditions Grammar: Program = Statement*, Statement = Assignment | IfStatement, Assignment = var '=' Expr, IfStatement = 'if' Condition 'then' Statement*. Build: program AST, scoped context (assignment modifies context for subsequent statements), conditional execution. Example: "x = 5; y = x * 2; if y > 8 then z = y + 1" → context: {x:5, y:10, z:11}. | Tests Interpreter for an imperative mini-language with mutable context. Assignments modify the context (side effects); if conditionally executes sub-statements. This requires a scoped, mutable context and sequential statement execution. Demonstrates where Interpreter overlaps with a tree-walking interpreter for a programming language. Key: statements return void but modify context; expressions return values. |
Interview Tip:
- When asked about Interpreter, the interviewer wants to see: (1) grammar → class hierarchy mapping (terminal vs. non-terminal); (2) recursive
interpret(context)evaluation; (3) separation of parsing from interpretation; (4) when NOT to use it (complex grammars → ANTLR, performance-critical → compiler). - Stand-out answers mention: regex
Patternas JDK example, Spring SpEL, the connection to Composite pattern, and that modern alternatives (sealed classes + pattern matching, or embedded scripting via GraalVM) often replace hand-rolled Interpreter in production.