Interpreter Pattern

  • Description: Define a grammar as a class hierarchy where each rule maps to a node, then walk the resulting AST to evaluate sentences in the language — useful for tiny DSLs; for anything non-trivial, use a parser generator instead.
  • My Notion Note ID: K2C-2-23
  • Created: 2026-05-22
  • Updated: 2026-05-22
  • License: Reuse is very welcome. Please credit Yu Zhang and link back to the original on yuzhang.io

Table of Contents

1. Intent

  • Given a language with a defined grammar, build a class per grammar rule, instantiate an AST from a sentence, then interpret(context) recursively.
  • Rules of the grammar → classes; sentences → object trees.
  • Best fit: small, stable DSLs — regex (the textbook GoF example), boolean filters, configuration expressions, calculator-like arithmetic, simple query languages.
  • For real languages with non-trivial parsing or evaluation requirements: use a parser generator (ANTLR, Bison, PEG) and treat AST as data, not behavior.

2. Structure

  • AbstractExpression — interface with interpret(Context&).
  • TerminalExpression — leaf nodes (literals, variables, identifiers).
  • NonterminalExpression — composite; holds child expressions; implements rules built from sub-expressions.
  • Context — global info during interpretation (variable bindings, input stream, output buffer).
  • Client — builds the AST (by hand or via a parser) and calls interpret.

The AST is a Composite. Interpretation is recursive descent through that Composite.

3. C++ Example

Boolean expression grammar: Expr ::= Var | And(Expr, Expr) | Or(Expr, Expr) | Not(Expr).

#include <memory>
#include <string>
#include <unordered_map>
#include <iostream>

using Context = std::unordered_map<std::string, bool>;

struct BoolExpr {
    virtual ~BoolExpr() = default;
    virtual bool interpret(const Context&) const = 0;
};

class Var : public BoolExpr {
    std::string name_;
public:
    explicit Var(std::string n) : name_(std::move(n)) {}
    bool interpret(const Context& c) const override { return c.at(name_); }
};

class And : public BoolExpr {
    std::unique_ptr<BoolExpr> lhs_, rhs_;
public:
    And(std::unique_ptr<BoolExpr> l, std::unique_ptr<BoolExpr> r) : lhs_(std::move(l)), rhs_(std::move(r)) {}
    bool interpret(const Context& c) const override { return lhs_->interpret(c) && rhs_->interpret(c); }
};

class Or : public BoolExpr {
    std::unique_ptr<BoolExpr> lhs_, rhs_;
public:
    Or(std::unique_ptr<BoolExpr> l, std::unique_ptr<BoolExpr> r) : lhs_(std::move(l)), rhs_(std::move(r)) {}
    bool interpret(const Context& c) const override { return lhs_->interpret(c) || rhs_->interpret(c); }
};

class Not : public BoolExpr {
    std::unique_ptr<BoolExpr> e_;
public:
    explicit Not(std::unique_ptr<BoolExpr> e) : e_(std::move(e)) {}
    bool interpret(const Context& c) const override { return !e_->interpret(c); }
};

int main() {
    // (a AND b) OR (NOT c)
    auto expr = std::make_unique<Or>(
        std::make_unique<And>(std::make_unique<Var>("a"), std::make_unique<Var>("b")),
        std::make_unique<Not>(std::make_unique<Var>("c"))
    );

    Context ctx{{"a", true}, {"b", false}, {"c", false}};
    std::cout << expr->interpret(ctx) << "\n";  // true (NOT c is true)
}

Notice: parsing (string → AST) is not part of the Interpreter pattern. GoF treats AST construction as separate; in practice a tiny recursive-descent parser feeds it.

4. When to Use / When Not To

Use when:

  • Grammar is small, stable, and recursive in shape.
  • Sentences are evaluated frequently; precompiled AST beats reparsing.
  • You want operations on the tree expressed as methods (or Visitor, see § 6) rather than table-driven interpretation.

Avoid when:

  • Grammar is large or evolving — class explosion; one class per production gets unmanageable past ~20 rules.
  • Performance matters — tree-walking interpreters are 10–100x slower than bytecode VMs or JIT.
  • You need anything beyond evaluation (good error messages, static analysis, optimization passes) — use a real parser generator + a proper IR.

Default position in modern code: reach for a parser generator (ANTLR, Boost.Spirit, PEGTL, Lark, tree-sitter) or an existing expression library (CEL, JsonLogic, mu-expressions); the Interpreter pattern itself is rarely written from scratch.

5. Variants and Pitfalls

  • Tree-walking vs bytecode — Interpreter as GoF describes is tree-walking. Real interpreters compile AST → bytecode for one to two orders of magnitude speedup. Tree-walking is for teaching and tiny DSLs only.
  • Class explosion — each grammar rule → class. Grammar with 50 productions = 50 classes. Mitigation: collapse similar rules (BinaryOp with an enum), or generate the classes from the grammar.
  • Recursion depth — tree walk uses host-language stack. Deep expressions overflow. Convert recursion to a worklist for production code.
  • Mixing parsing in nodes — GoF deliberately splits parsing from interpretation; some implementations conflate them, then the parser is impossible to replace.
  • Context object — global state for the walk. Make it the place for variable bindings, output, errors; don't let interpretation reach into globals.
  • Adding new operations — methods on each node scale linearly with operation count. Use Visitor (§ 6) to isolate each new operation.

6. Related Patterns

  • Composite — the Interpreter's AST is a Composite. Interpreter adds the interpret operation to a Composite tree of expression nodes.
  • Visitor — the standard way to add operations to an Interpreter's AST without modifying each node. Eval, pretty-print, type-check, optimize → each as a separate Visitor. See Visitor Pattern.
  • Iterator — used to step through tokens or AST children.
  • Flyweight — when many leaf nodes are identical (e.g., the same Var("x")), share a single instance.
  • Modern replacement — parser generators — ANTLR, Bison/Yacc, PEGTL, Boost.Spirit. They generate the AST + parser; you write only the semantic actions. For anything beyond a calculator, default to one of these.
  • Modern replacement — std::variant AST — represent the AST as a sum type and evaluate with std::visit (see Visitor Pattern § 4). Same effect, less boilerplate, no virtual hierarchy.

7. References

  • Gamma, Helm, Johnson, Vlissides. Design Patterns. Interpreter chapter.
  • Aho, Lam, Sethi, Ullman. Compilers: Principles, Techniques, and Tools ("Dragon Book") — for the real story on parsing + IR.
  • ANTLR — modern parser generator.
  • PEGTL — header-only C++ PEG parser.
  • Boost.Spirit — C++ expression-template parser.
  • tree-sitter — incremental parser generator used by editors.