Interpreter

Represent a small language as classes and evaluate it

My status

The problem

A rule such as "(3 + 4) * 2" arrives as a string, and you hand-write one big function with string splitting and nested ifs.

The idea

Make one class per grammar rule, each with interpret().

Reach for it when

A simple, stable grammar (rules, filters, formulas)

The picture from life

Reading sheet music: each symbol has a meaning (a note, a rest, a repeat) and the musician combines them according to rules to play a tune. Or a calculator: it understands numbers and the operators +, -, x, and evaluates a sentence like "3 4 + 2 x" by following the grammar.

The problem

What goes wrong when you do not use it.

A rule such as "(3 + 4) * 2" arrives as a string, and you hand-write one big function with string splitting and nested ifs. Every new operator makes it messier, and the rules cannot be reused or combined.

✗ Before

A giant function with string checks. Every new operator makes it longer and harder to follow.

Reach for it when

A simple, stable grammar (rules, filters, formulas)
You must evaluate the same expression many times
Expressions should be built and combined from parts

The idea

How the pattern fixes it.

Make one class per grammar rule, each with interpret(). A number returns itself; an Add holds two sub-expressions and adds their results. A whole sentence becomes a tree whose root you ask to interpret.

✓ After

implements
creates

Each rule of the language is a small class. A sentence becomes a tree of these objects.

Who is who

Expression: interpret() returns a number.
Num (terminal): Returns its own value.
Add, Sub, Mul (non-terminal): Hold two sub-expressions and combine their results.
parse(): Builds the tree from text (here, postfix).

Build it in steps

1Write the grammar rules in plain words.
2One class per rule with interpret().
3Build a tree from the input.
4Call interpret() on the root.

Watch it run

Step through the calls. Tap an arrow to jump to it.

Step 1/10

'3 4 + 2 *' was parsed into Mul(Add(3, 4), 2). Ask the top node.

interpret()

The code

Python and Java. Try writing the classes yourself from the diagram first.

class Num:
    def __init__(self, value):
        self.value = value

    def interpret(self):
        return self.value


class Add:
    def __init__(self, left, right):
        self.left, self.right = left, right

    def interpret(self):
        return self.left.interpret() + self.right.interpret()


class Sub:
    def __init__(self, left, right):
        self.left, self.right = left, right

    def interpret(self):
        return self.left.interpret() - self.right.interpret()


class Mul:
    def __init__(self, left, right):
        self.left, self.right = left, right

    def interpret(self):
        return self.left.interpret() * self.right.interpret()


def parse(text):                                   # postfix: "3 4 + 2 *"
    stack = []
    for token in text.split():
        if token in ("+", "-", "*"):
            right, left = stack.pop(), stack.pop()
            stack.append({"+": Add, "-": Sub, "*": Mul}[token](left, right))
        else:
            stack.append(Num(int(token)))
    return stack.pop()


def demo():
    return parse("3 4 + 2 *").interpret(), parse("10 2 3 * -").interpret()

What you gain

Easy to add new rules as classes
Expressions are objects you can store and reuse

What it costs

Grows heavy for big grammars; use a parser generator instead
Slow compared with compiled code

You have already met it in

Regular expression engines
SQL or rule-engine conditions built as trees
Spring Expression Language (SpEL)

Often mixed up with

CompositeThe expression tree is a Composite; Interpreter adds the idea of evaluating it by a grammar.
VisitorVisitor puts the operations outside the nodes; Interpreter puts interpret() inside each node.

Make it stick

Add a Div node and a variable node Var("x"), and evaluate "x 3 +" with x supplied in a dictionary.

My notes

Confidence

Composite Visitor Iterator