Interpreter
Interpreter turns a sentence in a small language - say, the expression `x + 5 - 2` - into a tree of objects, one class per rule (number, variable, addition, subtraction). Getting the answer is just calling one method on the root: each object works out its own piece by asking its children for theirs, so the tree evaluates itself.
Problem
Imagine building a small calculator that evaluates arithmetic expressions typed in as text, like `x + 5 - 2`, where `x` is a variable that can hold any number. The rules are tiny - numbers, variables, addition, subtraction - but they combine in endless ways: `x + 5`, `(x + 5) - 2`, `2 - (x + 5)`, and so on.
A quick fix is one big function that scans the string and handles each case with a pile of if/else. It works for a couple of examples, then falls apart as soon as expressions nest deeper or a new operator shows up, because parsing and evaluating are tangled together in one place with no reusable pieces.
What's missing is a way to treat "a number", "a variable", "a sum", and "a difference" as separate, composable building blocks - instead of special cases buried inside one big block of code.
Solution
Interpreter turns each grammar rule into its own class, all sharing one `interpret` method that produces a result when called. Simple pieces of the expression - a number, a variable - become terminal expression classes that know their value directly. Compound pieces - a sum, a difference - become nonterminal expression classes that hold their sub-expressions and combine whatever those return.
The expression `x + 5 - 2` is built once into a small tree: a subtraction node holding an addition node (variable `x` and number `5`) and a number node (`2`). Evaluating the whole expression is just calling `interpret` on the root - the recursion works its way down the tree and combines the results back up. Adding a new operator, like multiplication, means adding one new nonterminal class - the rest of the tree, and the rest of the grammar, doesn't change.
When to Use
- Reach for Interpreter when the language you need to evaluate is genuinely small and its sentences map cleanly onto a tree of a handful of rule types.
- It pays off when the grammar is expected to stay stable; a rapidly growing rule set is a sign to switch to a parser generator instead.
- It's a reasonable choice when raw evaluation speed matters less than having a clear, testable, one-rule-per-class model of the language.
Real-World Examples
- **Regex engines** - a compiled pattern becomes a tree of matcher nodes (literal, concatenation, alternation, repetition) that walk an input string and report a match.
- **ORM query builders** - libraries like SQLAlchemy or Django's ORM build a tree of filter and predicate objects from chained method calls, then interpret that tree into SQL at execution time.
- **Spreadsheet formula engines** - an expression like `=A1 + B2 * 2` is parsed into a tree of cell references and operators that the spreadsheet interprets to produce the cell's displayed value.
Structure
Every node in the tree implements a shared `interpret` operation. On the diagram, Subtract (the root) and Add (its branch) are nonterminals that call `interpret` on their children before answering; the Number and Variable leaves (`2`, `x`, `5`) are terminals that answer right away. The Client builds this tree and calls `interpret` on the root; the `{ x: 10 }` values feeding the Variable leaf are the Context, threaded through every call but not drawn as a box of its own.
Participants
The one method - `interpret` - that every node in the tree must implement. On the diagram, every box shares it: Subtract, Add, and the Number/Variable leaves all expose the same `interpret`, so the Client can call it on the root without caring which concrete class answers.
A leaf of the tree with no children, which answers immediately. On the diagram, these are the Number and Variable boxes - `2`, `x`, `5` - each just returning its own value.
A node built from sub-expressions that must call `interpret` on its children before it can answer. On the diagram, these are Subtract (the root) and Add (its branch), which combine what their children return.
The variable bindings threaded through every `interpret` call - here, `{ x: 10 }`. It has no box of its own on the diagram, since it's data carried alongside the tree, not part of its structure - it only surfaces where the Variable leaf reads `x`.
Builds the tree for `x + 5 - 2` and starts evaluation by calling `interpret` on the root. On the diagram, this is the Client box, and the value it gets back is the root's answer, `13`.
class NumberExpression {
constructor(value) { this.value = value; }
interpret(_context) { return this.value; }
}
class VariableExpression {
constructor(name) { this.name = name; }
interpret(context) {
if (!(this.name in context)) {
throw new Error(`Unknown variable: ${this.name}`);
}
return context[this.name];
}
}
class AddExpression {
constructor(left, right) { this.left = left; this.right = right; }
interpret(context) {
return this.left.interpret(context) + this.right.interpret(context);
}
}
class SubtractExpression {
constructor(left, right) { this.left = left; this.right = right; }
interpret(context) {
return this.left.interpret(context) - this.right.interpret(context);
}
}
const tree = new SubtractExpression(
new AddExpression(
new VariableExpression('x'),
new NumberExpression(5),
),
new NumberExpression(2),
);
const context = { x: 10 };
console.log(tree.interpret(context));Step 1 of 6
NumberExpression is a terminal expression - it just returns a literal
`interpret(_context)` ignores the context entirely and returns `this.value` - a leaf of the expression tree that needs no further evaluation.
Step 2 of 6
VariableExpression is also terminal, but reads from the context
`interpret(context)` looks up `this.name` in `context` and throws if it's missing - variables only resolve to a value at interpretation time, using whatever context is passed in.
Step 3 of 6
AddExpression is a nonterminal - it combines two subexpressions
It stores `left` and `right` expressions, and `interpret(context)` recursively calls `this.left.interpret(context) + this.right.interpret(context)` - it doesn't care whether `left`/`right` are numbers, variables, or other expressions.
Step 4 of 6
SubtractExpression follows the exact same recursive shape
It's structurally identical to `AddExpression`, just subtracting `right`'s result from `left`'s - each grammar rule gets its own expression class.
Step 5 of 6
The client composes an expression tree matching (x + 5) - 2
`SubtractExpression` wraps an `AddExpression` (itself wrapping `VariableExpression('x')` and `NumberExpression(5)`) and `NumberExpression(2)` - nesting expression objects is literally how the grammar's syntax tree is built.
Step 6 of 6
interpret() walks the whole tree with one context
`tree.interpret(context)` with `context = { x: 10 }` triggers the recursive calls set up above, resolving to `(10 + 5) - 2 = 13`.
interface Expression {
interpret(context: Record<string, number>): number;
}
class NumberExpression implements Expression {
constructor(private readonly value: number) {}
interpret(_context: Record<string, number>): number {
return this.value;
}
}
class VariableExpression implements Expression {
constructor(private readonly name: string) {}
interpret(context: Record<string, number>): number {
if (!(this.name in context)) {
throw new Error(`Unknown variable: ${this.name}`);
}
return context[this.name];
}
}
class AddExpression implements Expression {
constructor(
private readonly left: Expression,
private readonly right: Expression,
) {}
interpret(context: Record<string, number>): number {
return this.left.interpret(context) + this.right.interpret(context);
}
}
class SubtractExpression implements Expression {
constructor(
private readonly left: Expression,
private readonly right: Expression,
) {}
interpret(context: Record<string, number>): number {
return this.left.interpret(context) - this.right.interpret(context);
}
}
const tree: Expression = new SubtractExpression(
new AddExpression(
new VariableExpression('x'),
new NumberExpression(5),
),
new NumberExpression(2),
);
console.log(tree.interpret({ x: 10 }));import java.util.Map;
interface Expression {
int interpret(Map<String, Integer> context);
}
class NumberExpression implements Expression {
private final int value;
NumberExpression(int value) { this.value = value; }
public int interpret(Map<String, Integer> context) { return value; }
}
class VariableExpression implements Expression {
private final String name;
VariableExpression(String name) { this.name = name; }
public int interpret(Map<String, Integer> context) {
if (!context.containsKey(name))
throw new IllegalArgumentException("Unknown variable: " + name);
return context.get(name);
}
}
class AddExpression implements Expression {
private final Expression left, right;
AddExpression(Expression left, Expression right) { this.left = left; this.right = right; }
public int interpret(Map<String, Integer> context) {
return left.interpret(context) + right.interpret(context);
}
}
class SubtractExpression implements Expression {
private final Expression left, right;
SubtractExpression(Expression left, Expression right) { this.left = left; this.right = right; }
public int interpret(Map<String, Integer> context) {
return left.interpret(context) - right.interpret(context);
}
}
Expression tree = new SubtractExpression(
new AddExpression(
new VariableExpression("x"),
new NumberExpression(5)
),
new NumberExpression(2)
);
System.out.println(tree.interpret(Map.of("x", 10)));interface IExpression
{
int Interpret(Dictionary<string, int> context);
}
class NumberExpression : IExpression
{
private readonly int _value;
public NumberExpression(int value) => _value = value;
public int Interpret(Dictionary<string, int> context) => _value;
}
class VariableExpression : IExpression
{
private readonly string _name;
public VariableExpression(string name) => _name = name;
public int Interpret(Dictionary<string, int> context)
{
if (!context.TryGetValue(_name, out int value))
throw new ArgumentException($"Unknown variable: {_name}");
return value;
}
}
class AddExpression : IExpression
{
private readonly IExpression _left, _right;
public AddExpression(IExpression l, IExpression r) { _left = l; _right = r; }
public int Interpret(Dictionary<string, int> ctx) =>
_left.Interpret(ctx) + _right.Interpret(ctx);
}
class SubtractExpression : IExpression
{
private readonly IExpression _left, _right;
public SubtractExpression(IExpression l, IExpression r) { _left = l; _right = r; }
public int Interpret(Dictionary<string, int> ctx) =>
_left.Interpret(ctx) - _right.Interpret(ctx);
}
IExpression tree = new SubtractExpression(
new AddExpression(
new VariableExpression("x"),
new NumberExpression(5)
),
new NumberExpression(2)
);
var context = new Dictionary<string, int> { ["x"] = 10 };
Console.WriteLine(tree.Interpret(context));from __future__ import annotations
from abc import ABC, abstractmethod
Context = dict[str, int]
class Expression(ABC):
@abstractmethod
def interpret(self, context: Context) -> int: ...
class NumberExpression(Expression):
def __init__(self, value: int) -> None:
self.value = value
def interpret(self, context: Context) -> int:
return self.value
class VariableExpression(Expression):
def __init__(self, name: str) -> None:
self.name = name
def interpret(self, context: Context) -> int:
if self.name not in context:
raise ValueError(f'Unknown variable: {self.name}')
return context[self.name]
class AddExpression(Expression):
def __init__(self, left: Expression, right: Expression) -> None:
self.left, self.right = left, right
def interpret(self, context: Context) -> int:
return self.left.interpret(context) + self.right.interpret(context)
class SubtractExpression(Expression):
def __init__(self, left: Expression, right: Expression) -> None:
self.left, self.right = left, right
def interpret(self, context: Context) -> int:
return self.left.interpret(context) - self.right.interpret(context)
tree = SubtractExpression(
AddExpression(VariableExpression('x'), NumberExpression(5)),
NumberExpression(2),
)
print(tree.interpret({'x': 10}))Step 1 of 6
Expression is the abstract interface every node implements
`interpret(context)` is `@abstractmethod` - both terminal and nonterminal expressions share this one method, so they can be nested interchangeably.
Step 2 of 6
NumberExpression is a terminal expression - it just returns a literal
`interpret` ignores `context` and returns `self.value` - a leaf of the expression tree that needs no further evaluation.
Step 3 of 6
VariableExpression is also terminal, but reads from the context
`interpret` looks up `self.name` in `context` and raises `ValueError` if it's missing - variables only resolve to a value at interpretation time.
Step 4 of 6
AddExpression is a nonterminal - it combines two subexpressions
It stores `left` and `right`, and `interpret` recursively calls `self.left.interpret(context) + self.right.interpret(context)` - it doesn't care what kind of `Expression` `left`/`right` actually are.
Step 5 of 6
SubtractExpression follows the exact same recursive shape
It's structurally identical to `AddExpression`, just subtracting `right`'s result from `left`'s - each grammar rule gets its own `Expression` subclass.
Step 6 of 6
The client builds and interprets the tree for (x + 5) - 2
`tree` nests `AddExpression(VariableExpression('x'), NumberExpression(5))` inside `SubtractExpression(..., NumberExpression(2))`, and `tree.interpret({'x': 10})` walks it to `(10 + 5) - 2 = 13`.
Click "Run" to execute this code in a sandboxed frame and see console output here.
TypeScript runs as plain JavaScript here - type annotations are stripped, not type-checked.
Click "Run" to execute this code in a sandboxed frame and see console output here.
Advantages
- The grammar lives in code as a set of classes, so adding a rule is as local as adding one more expression class rather than touching a central parser.
- Each rule is a small, self-contained class, which makes it easy to unit-test a single piece of grammar in isolation from the rest.
- Because sub-expressions are ordinary objects, they nest and recombine naturally - a complex sentence is just a bigger tree built from the same small parts.
Disadvantages
- One class per grammar rule scales badly - a language with dozens of rules means dozens of small classes to navigate and keep straight.
- Beyond a handful of rules, a hand-rolled interpreter is usually outclassed by a proper parser generator or parsing library, which handles ambiguity and error recovery far better.
- Interpreting the tree directly on every evaluation is slower than compiling the expression once into a more efficient form, and deep trees risk hitting recursion limits.
Question 1 of 10
Beyond a handful of grammar rules, what is usually the better alternative to a hand-rolled Interpreter?
Correct! Beyond a handful of rules, a hand-rolled interpreter is usually outclassed by a proper parser generator or parsing library, which handles ambiguity and error recovery far better.
Not quite. Beyond a handful of rules, a hand-rolled interpreter is usually outclassed by a proper parser generator or parsing library, which handles ambiguity and error recovery far better.
Question 2 of 10
Which listed benefit of Interpreter concerns testing?
Correct! Each rule is a small, self-contained class, which makes it easy to unit-test a single piece of grammar in isolation from the rest.
Not quite. Each rule is a small, self-contained class, which makes it easy to unit-test a single piece of grammar in isolation from the rest.
Question 3 of 10
What does adding a new operator like multiplication require in this design?
Correct! Adding a new operator, like multiplication, means adding one new nonterminal class - the rest of the tree, and the rest of the grammar, doesn't change.
Not quite. Adding a new operator, like multiplication, means adding one new nonterminal class - the rest of the tree, and the rest of the grammar, doesn't change.
Question 4 of 10
What does the Context participant represent in the x + 5 - 2 example?
Correct! The Context is the variable bindings, like { x: 10 }, threaded through every interpret call; it has no box of its own on the diagram since it's data carried alongside the tree, surfacing only where the Variable leaf reads x.
Not quite. The Context is the variable bindings, like { x: 10 }, threaded through every interpret call; it has no box of its own on the diagram since it's data carried alongside the tree, surfacing only where the Variable leaf reads x.
Question 5 of 10
What does Interpreter turn a sentence in a small language into?
Correct! Interpreter turns a sentence into a tree of objects, one class per rule, and evaluating it is just calling one method on the root, which recurses down to its children.
Not quite. Interpreter turns a sentence into a tree of objects, one class per rule, and evaluating it is just calling one method on the root, which recurses down to its children.
Question 6 of 10
What is a stated drawback of Interpreter as the number of grammar rules grows?
Correct! One class per grammar rule scales badly - a language with dozens of rules means dozens of small classes to navigate and keep straight.
Not quite. One class per grammar rule scales badly - a language with dozens of rules means dozens of small classes to navigate and keep straight.
Question 7 of 10
In the JavaScript implementation, how does AddExpression's interpret method get its result?
Correct! AddExpression stores left and right expressions, and interpret(context) recursively calls this.left.interpret(context) + this.right.interpret(context) - it doesn't care whether left/right are numbers, variables, or other expressions.
Not quite. AddExpression stores left and right expressions, and interpret(context) recursively calls this.left.interpret(context) + this.right.interpret(context) - it doesn't care whether left/right are numbers, variables, or other expressions.
Question 8 of 10
Why can interpreting a tree directly be slower than compiling an expression once into a more efficient form?
Correct! Interpreting the tree directly on every evaluation is slower than compiling the expression once into a more efficient form, and deep trees risk hitting recursion limits.
Not quite. Interpreting the tree directly on every evaluation is slower than compiling the expression once into a more efficient form, and deep trees risk hitting recursion limits.
Question 9 of 10
What distinguishes a terminal expression class from a nonterminal one?
Correct! Simple pieces of the expression, like a number or a variable, become terminal classes that know their value directly, while compound pieces, like a sum or a difference, become nonterminal classes that hold sub-expressions and combine what those return.
Not quite. Simple pieces of the expression, like a number or a variable, become terminal classes that know their value directly, while compound pieces, like a sum or a difference, become nonterminal classes that hold sub-expressions and combine what those return.
Question 10 of 10
Why does a single big if/else function for evaluating expressions like x + 5 - 2 eventually fall apart?
Correct! A single big function works for a couple of examples, then falls apart as expressions nest deeper or a new operator shows up, because parsing and evaluating are tangled together in one place with no reusable pieces.
Not quite. A single big function works for a couple of examples, then falls apart as expressions nest deeper or a new operator shows up, because parsing and evaluating are tangled together in one place with no reusable pieces.