Interpreter

The Problem It Solves

A domain keeps sprouting mini-languages: filter expressions (“status = OPEN AND amount > 100”), search queries, rule conditions, formula cells. Hard-coding each as string parsing + if-chains makes every new operator an edit to fragile parsing code. Interpreter formalizes the alternative: define the language’s grammar as a class hierarchy, parse input into a tree of those classes, and evaluate the tree recursively — new operators become new classes.

From Grammar to Classes

 GRAMMAR (EBNF)                     CLASS HIERARCHY (1:1 with rules)

 expr   → term ('OR' term)*         «interface» Expression
 term   → factor ('AND' factor)*      + interpret(ctx): boolean
 factor → '(' expr ')' | atom              △          △        △
 atom   → field op value            AndExpr   OrExpr    TerminalExpr
                                    (left,right)      (field,op,value)

 parse("a=1 AND b=2")  →  And(Term(a=1), Term(b=2))   ← AST of Expression objects
 eval: recurse down the tree, booleans bubble up

Each grammar production becomes one class; sentences become trees; interpretation is post-order recursion.

Mechanics

interface Expression {
    boolean interpret(Map<String, String> ctx);
}

record Terminal(String field, String expected) implements Expression {
    public boolean interpret(Map<String, String> ctx) {
        return expected.equalsIgnoreCase(ctx.get(field));
    }
}

record And(Expression left, Expression right) implements Expression {
    public boolean interpret(Map<String, String> ctx) {
        return left.interpret(ctx) && right.interpret(ctx);
    }
}

record Or(Expression left, Expression right) implements Expression {
    public boolean interpret(Map<String, String> ctx) {
        return left.interpret(ctx) || right.interpret(ctx);
    }
}

// parsed tree:
Expression rule = new And(
    new Terminal("status", "OPEN"),
    new Or(new Terminal("tier", "GOLD"), new Terminal("amount", "HIGH")));

rule.interpret(Map.of("status", "OPEN", "tier", "SILVER"));  // → false

Adding Not or comparison operators (>): one new record each. Nothing existing edits.

Where Parsing Ends and Interpreting Begins

The pattern covers interpretation only. Parsing text → tree needs a tokenizer/parser (recursive descent, Pratt, or parser generators like ANTLR). Production systems almost always pair: ANTLR generates the parser; interpreter classes evaluate the resulting AST.

Honest Usage Assessment

Hand-rolled interpreters are rare in application code today:

Situation	Better tool
Full general-purpose grammar	Parser generator (ANTLR/JavaCC)
Simple property conditions	SpEL/MVEL/existing expression libs
Stable small DSL with few operators	Interpreter is genuinely fine
Rules engine at scale	Dedicated engine (Drools)

Its lasting value is conceptual: it teaches grammar-to-class-hierarchy mapping — the same thinking behind AST tooling, regex engines, and query planners.

Interview Framing

• Asked to design a promotion-rule evaluator, sketching Expression + two composites + terminal shows the mapping skill without over-committing to a parser build.
• Complexity note worth stating: deep expression trees recurse per character of structure — evaluation is O(tree size); pathological nesting risks stack depth (iterative evaluators fix it).