Interpreter Pattern — Grammar Evaluation for Domain Languages

What You'll Learn

You will learn how the Interpreter pattern models a Domain-Specific Language by representing grammar rules as classes and evaluating expressions by walking an Abstract Syntax Tree. You will see how it applies the Composite pattern for tree structures.

Why It Matters

Applications often need to evaluate user-defined formulas, search queries, or business rules. Writing a full parser and compiler is overkill. Interpreter provides a lightweight way to define and evaluate a grammar by mapping each production rule to a class. If your application needs to evaluate (price * quantity) - discount, you can model this as an expression tree and evaluate it recursively without writing a parser.

Real-World Use

Spreadsheet applications evaluate cell formulas like SUM(A1:A10) * 2 using an Interpreter over the formula's parse tree. DodaTech's rule engine lets users define discount policies as expressions like order.total > 100 AND customer.tier == "gold" and interprets them against runtime data. Adding a new operator like contains means adding one expression class — no parsing or compilation changes needed.

The Pattern

AbstractExpression declares the interpret method. TerminalExpression represents literal values. NonterminalExpression represents grammar rules composed of sub-expressions.

from abc import ABC, abstractmethod

class Expression(ABC):
    @abstractmethod
    def interpret(self, context: dict) -> int:
        pass

class Number(Expression):
    def __init__(self, value: int):
        self._value = value

    def interpret(self, context: dict) -> int:
        return self._value

class Variable(Expression):
    def __init__(self, name: str):
        self._name = name

    def interpret(self, context: dict) -> int:
        return context.get(self._name, 0)

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

    def interpret(self, context: dict) -> int:
        return self._left.interpret(context) + self._right.interpret(context)

class Subtract(Expression):
    def __init__(self, left: Expression, right: Expression):
        self._left = left
        self._right = right

    def interpret(self, context: dict) -> int:
        return self._left.interpret(context) - self._right.interpret(context)

class Multiply(Expression):
    def __init__(self, left: Expression, right: Expression):
        self._left = left
        self._right = right

    def interpret(self, context: dict) -> int:
        return self._left.interpret(context) * self._right.interpret(context)

expression = Multiply(
    Add(Number(3), Variable("x")),
    Subtract(Variable("y"), Number(1))
)

context = {"x": 5, "y": 10}
result = expression.interpret(context)
print(f"(3 + x) * (y - 1) = {result}")

context2 = {"x": 1, "y": 4}
print(f"(3 + x) * (y - 1) = {expression.interpret(context2)}")

(3 + x) * (y - 1) = 72
(3 + x) * (y - 1) = 12

Structure

classDiagram
    class AbstractExpression {
        <>
        +interpret(context): int
    }
    class TerminalExpression {
        +interpret(context): int
    }
    class NonterminalExpression {
        +interpret(context): int
    }
    TerminalExpression ..|> AbstractExpression
    NonterminalExpression ..|> AbstractExpression
    NonterminalExpression --> AbstractExpression : left
    NonterminalExpression --> AbstractExpression : right

Real-World Usage

• SQL WHERE clause evaluation — WHERE age > 18 AND status = 'active' is interpreted against each row.
• Python eval() and exec() — interpret arbitrary Python expressions and statements at runtime.
• Regular expression engines — compile a pattern into a syntax tree and interpret it against input strings.
• Java javax.script.ScriptEngine — interprets JavaScript, Groovy, or other scripting languages embedded in Java.

Related Patterns

• Composite shares the tree structure; Interpreter adds evaluation semantics.
• Visitor can traverse the AST and perform operations without modifying expression classes.
• Flyweight shares terminal nodes across the syntax tree to save memory.
• Strategy can select different interpretation strategies at runtime.

Pros and Cons

The expression tree Multiply(Add(Number(3), Variable("x")), Subtract(Variable("y"), Number(1))) directly mirrors the mathematical expression (3 + x) * (y - 1). Each node knows how to evaluate itself. The context dictionary provides variable values at evaluation time — the same expression tree can be evaluated with different contexts to produce different results.

Practice Questions

1. Implement a BooleanExpression Interpreter that supports AND, OR, and NOT operators.
2. How would you add a pow (power) operator to the arithmetic Interpreter above?
3. What are the alternatives to Interpreter when the grammar has hundreds of rules?
4. Combine Interpreter with Visitor to implement a pretty-printer for the expression tree.

Challenge

Implement a comparison operator (GreaterThan) that returns 1 if the left side is greater than the right side, and 0 otherwise. Extend it to support chained comparisons like x > 5 AND y < 10.

Real-World Task

Identify a simple DSL or expression format in your application (search filters, config conditions, formula fields). Implement it using the Interpreter pattern and use DodaTech's AST visualiser to verify correct evaluation.