Skip to content

Interpreter

Intent

Represent each rule of a small grammar as a class, parse a sentence into a tree of those objects, and evaluate the tree by asking every node to interpret itself against a context. Users get a language they can write without a deployment; you pay with a tokenizer, a parser and a grammar you now own.

When to use and when not to

Use it when

  • Rules arrive as text from people who do not ship code: alert thresholds, fraud rules, search filters, feature-flag targeting.
  • The grammar is small and stable: comparisons, AND, OR, NOT and parentheses, with no ambition to become a programming language.
  • You need more than evaluation: list the fields a rule reads, render it back, translate it to SQL. A tree can be walked; a compiled regex cannot.

Leave it out when, which is most of the time:

  • The grammar is someone else's. Thresholds in JSON or YAML, schedules in cron syntax, file patterns in globs, text patterns in regular expressions: the stdlib already has the parser and the evaluator.
  • The expressions are Python. ast.parse(text, mode="eval") gives you the tree; allowlist the node types and walk it.
  • The rules are built in code, not parsed from text: that is Specification, the same tree assembled with operators and no parser.
  • The grammar keeps growing (functions, types, string escapes, error recovery): use a parser generator or reconsider the feature.

Structure

The grammar as classes: one abstract node, one leaf that compares a field with a literal, three non-terminals for the operators, and a Parser that turns tokens into the tree. The Context is a plain mapping.

classDiagram
    class Expression {
        <<abstract>>
        +evaluate(record: Mapping~str,object~) bool
    }
    class Comparison {
        +field: str
        +op: str
        +value: Value
        +evaluate(record: Mapping~str,object~) bool
    }
    class And {
        +left: Expression
        +right: Expression
        +evaluate(record: Mapping~str,object~) bool
    }
    class Or {
        +left: Expression
        +right: Expression
        +evaluate(record: Mapping~str,object~) bool
    }
    class Not {
        +inner: Expression
        +evaluate(record: Mapping~str,object~) bool
    }
    class Token {
        +kind: str
        +text: str
        +position: int
    }
    class Parser {
        -_tokens: List~Token~
        -_pos: int
        +parse() Expression
    }
    Expression <|-- Comparison
    Expression <|-- And
    Expression <|-- Or
    Expression <|-- Not
    And o-- "2" Expression
    Or o-- "2" Expression
    Not o-- "1" Expression
    Parser ..> Token : consumes
    Parser ..> Expression : builds

The non-terminals hold other expressions and nothing else, so the tree is a Composite. Parser is the only class that knows the grammar's syntax; the nodes know only its meaning. Comparison is a leaf because the record, not the tree, supplies the field's value.

Canonical example in Python

The nodes come first (code/patterns/interpreter.py, tested by code/patterns/tests/test_interpreter.py):

code/patterns/interpreter.py — the expression nodes
class Expression(ABC):
    """The abstract expression: every node, leaf or not, evaluates itself against a record.

    An ``ABC`` so that the tree can be walked by ``isinstance`` and ``match`` alike;
    the concrete nodes are frozen dataclasses, so a parsed rule is a value with
    equality and a hash, which makes caching parsed rules by their text trivial.
    """

    @abstractmethod
    def evaluate(self, record: Mapping[str, object]) -> bool: ...


OPERATORS: Mapping[str, Callable[[object, object], bool]] = {
    "=": operator.eq,
    "!=": operator.ne,
    "<": operator.lt,
    "<=": operator.le,
    ">": operator.gt,
    ">=": operator.ge,
}


def lookup(record: Mapping[str, object], field: str) -> object:
    """The Context is a plain mapping; an unknown field is an error, never a silent False."""
    if field not in record:
        raise NotFoundError(f"record has no field {field!r}")
    return record[field]


def compare(op: str, actual: object, expected: Value) -> bool:
    try:
        if op == "IN":
            if not isinstance(expected, tuple):
                raise ValidationError("IN needs a list of values")
            return actual in expected
        return OPERATORS[op](actual, expected)
    except TypeError as exc:
        raise ValidationError(f"cannot apply {op} to {actual!r} and {expected!r}") from exc


@dataclass(frozen=True, slots=True)
class Comparison(Expression):
    """The terminal expression: one field of the record against one literal."""

    field: str
    op: str
    value: Value

    def evaluate(self, record: Mapping[str, object]) -> bool:
        return compare(self.op, lookup(record, self.field), self.value)


@dataclass(frozen=True, slots=True)
class And(Expression):
    left: Expression
    right: Expression

    def evaluate(self, record: Mapping[str, object]) -> bool:
        return self.left.evaluate(record) and self.right.evaluate(record)


@dataclass(frozen=True, slots=True)
class Or(Expression):
    left: Expression
    right: Expression

    def evaluate(self, record: Mapping[str, object]) -> bool:
        return self.left.evaluate(record) or self.right.evaluate(record)


@dataclass(frozen=True, slots=True)
class Not(Expression):
    inner: Expression

    def evaluate(self, record: Mapping[str, object]) -> bool:
        return not self.inner.evaluate(record)

Every node has one method, and that method is the meaning of one production. lookup makes an unknown field an error rather than a silent False, which is the difference between a rule that is wrong and a rule that merely looks right.

The grammar and the parser:

code/patterns/interpreter.py — tokens and the recursive-descent parser
# The grammar, lowest precedence first. One method of ``Parser`` per line.
#   expr       := and_expr ("OR" and_expr)*
#   and_expr   := unary ("AND" unary)*
#   unary      := "NOT" unary | "(" expr ")" | comparison
#   comparison := FIELD op SCALAR | FIELD "IN" "(" SCALAR ("," SCALAR)* ")"
#   op         := "=" | "!=" | "<" | "<=" | ">" | ">="
KEYWORDS = frozenset({"AND", "OR", "NOT", "IN"})
TOKEN_RE = re.compile(
    r"""
    (?P<ws>\s+)
  | (?P<number>\d+(?:\.\d+)?)
  | (?P<string>"[^"]*")
  | (?P<unterminated>"[^"]*$)
  | (?P<op><=|>=|!=|=|<|>)
  | (?P<lparen>\()
  | (?P<rparen>\))
  | (?P<comma>,)
  | (?P<word>[A-Za-z_][A-Za-z0-9_.]*)
    """,
    re.VERBOSE,
)


@dataclass(frozen=True, slots=True)
class Token:
    kind: str
    text: str
    position: int


def tokenize(text: str) -> list[Token]:
    """Split the text into tokens; keywords are case-insensitive, everything else is literal."""
    tokens: list[Token] = []
    position = 0
    while position < len(text):
        matched = TOKEN_RE.match(text, position)
        if matched is None:
            raise ParseError(f"unexpected character {text[position]!r} at position {position}")
        kind, lexeme = matched.lastgroup or "", matched.group()
        if kind == "unterminated":
            raise ParseError(f"unterminated string at position {position}")
        if kind == "word" and lexeme.upper() in KEYWORDS:
            kind, lexeme = "keyword", lexeme.upper()
        if kind != "ws":
            tokens.append(Token(kind, lexeme, position))
        position = matched.end()
    tokens.append(Token("eof", "", len(text)))
    return tokens


class Parser:
    """Recursive descent: one method per grammar rule; the token index is the only state.

    Precedence is the call structure: ``_or`` calls ``_and`` which calls ``_unary``,
    so ``a OR b AND c`` parses as ``a OR (b AND c)`` without a precedence table.
    """

    def __init__(self, tokens: Sequence[Token]) -> None:
        self._tokens = tokens
        self._pos = 0

    def parse(self) -> Expression:
        expression = self._or()
        self._expect("eof", "end of input")
        return expression

    @property
    def _current(self) -> Token:
        return self._tokens[self._pos]

    def _accept(self, kind: str, text: str | None = None) -> Token | None:
        token = self._current
        if token.kind == kind and (text is None or token.text == text):
            self._pos += 1
            return token
        return None

    def _expect(self, kind: str, what: str) -> Token:
        token = self._accept(kind)
        if token is None:
            raise self._fail(what)
        return token

    def _fail(self, what: str) -> ParseError:
        token = self._current
        found = "end of input" if token.kind == "eof" else repr(token.text)
        return ParseError(f"expected {what} at position {token.position}, found {found}")

    def _or(self) -> Expression:
        left = self._and()
        while self._accept("keyword", "OR"):
            left = Or(left, self._and())
        return left

    def _and(self) -> Expression:
        left = self._unary()
        while self._accept("keyword", "AND"):
            left = And(left, self._unary())
        return left

    def _unary(self) -> Expression:
        if self._accept("keyword", "NOT"):
            return Not(self._unary())
        if self._accept("lparen"):
            inner = self._or()
            self._expect("rparen", "')'")
            return inner
        return self._comparison()

    def _comparison(self) -> Expression:
        field = self._expect("word", "a field name").text
        if self._accept("keyword", "IN"):
            return Comparison(field, "IN", self._values())
        op = self._expect("op", "a comparison operator").text
        return Comparison(field, op, self._scalar())

    def _values(self) -> tuple[Scalar, ...]:
        self._expect("lparen", "'('")
        items = [self._scalar()]
        while self._accept("comma"):
            items.append(self._scalar())
        self._expect("rparen", "')'")
        return tuple(items)

    def _scalar(self) -> Scalar:
        if token := self._accept("number"):
            return float(token.text) if "." in token.text else int(token.text)
        if token := self._accept("string"):
            return token.text[1:-1]
        raise self._fail("a value")


def parse(text: str) -> Expression:
    """Text in, tree out. Parse once at save time; evaluate the tree per record."""
    return Parser(tokenize(text)).parse()

Three decisions to say out loud:

  • Precedence is the call structure. _or calls _and, which calls _unary, so a OR b AND c groups as a OR (b AND c) without a precedence table. A new precedence level is a new method between two existing ones.
  • Frozen dataclasses make a parsed rule a value. Equal text parses to equal trees and trees are hashable, so a cache of parsed rules is a dict. Parse once at save time, evaluate per record.
  • Two kinds of error, two exception types. ParseError carries a position and belongs to the person typing the rule; NotFoundError for a missing field belongs to whoever shaped the record. Validating a rule at save time means parsing it and checking fields_read against the schema.

Running python -m patterns.interpreter prints:

--- the rule as text, and the tree the parser builds from it ---
amount > 100 AND country = "US"
And(left=Comparison(field='amount', op='>', value=100), right=Comparison(field='country', op='=', value='US'))
--- three rules against three records ---
record                              big US order         risky   vip or bulk
amount=250 country=US tier=silver            yes            no            no
amount=80 country=DE tier=gold                no           yes           yes
amount=900 country=CA tier=bronze             no           yes           yes
--- the tree is data: a second operation without touching the nodes ---
fields read by 'risky': attempts, country
parsed rules are values: parse(text) == parse(text) -> True
--- errors say where and why ---
parse error in 'amount > AND': expected a value at position 9, found 'AND'
parse error in 'country = "US': unterminated string at position 10
parse error in '(amount > 1': expected ')' at position 11, found end of input
evaluation error: record has no field 'tier'
--- the match-statement evaluator agrees with the methods on all 9 cases: True ---

Pythonic variant

The evaluator does not have to live on the nodes. A match statement over the same frozen dataclasses does the dispatch in one function, and a second operation over the tree is a second function rather than a method on every class:

code/patterns/interpreter.py — the evaluator and a second walk as match statements
def evaluate(node: Expression, record: Mapping[str, object]) -> bool:
    """The evaluator as one function: ``match`` on the node type instead of a method per class.

    Same tree, same answers. The difference is where the next operation goes: a new
    function here, a new method on every node there (the Visitor trade-off).
    """
    match node:
        case Comparison(field, op, value):
            return compare(op, lookup(record, field), value)
        case And(left, right):
            return evaluate(left, record) and evaluate(right, record)
        case Or(left, right):
            return evaluate(left, record) or evaluate(right, record)
        case Not(inner):
            return not evaluate(inner, record)
    raise TypeError(f"not an expression node: {node!r}")


def fields_read(node: Expression) -> frozenset[str]:
    """A second operation over the same tree, without touching a node: what does the rule read?"""
    match node:
        case Comparison(field, _, _):
            return frozenset({field})
        case And(left, right) | Or(left, right):
            return fields_read(left) | fields_read(right)
        case Not(inner):
            return fields_read(inner)
    raise TypeError(f"not an expression node: {node!r}")

This is the Visitor trade-off in miniature: methods on nodes make a new node cheap; functions with match make a new operation cheap. Rule engines add operations (explain, translate, lint) far more often than node types.

When the rule language is Python itself, do not write a parser at all. ast gives you the tree; your job is the allowlist:

import ast

ALLOWED = (ast.Expression, ast.BoolOp, ast.UnaryOp, ast.Compare, ast.Name, ast.Constant, ast.Tuple,
           ast.And, ast.Or, ast.Not, ast.Gt, ast.GtE, ast.Lt, ast.LtE, ast.Eq, ast.NotEq, ast.In, ast.Load)


def parse_python_rule(text: str) -> ast.Expression:
    tree = ast.parse(text, mode="eval")
    for node in ast.walk(tree):
        if not isinstance(node, ALLOWED):
            raise ValueError(f"{type(node).__name__} is not allowed in a rule")
    return tree

Then evaluate with a match over ast nodes exactly as above. Never eval(text): a rule is user input, and eval runs it with your process's privileges.

Reach for When
re, fnmatch, json, cron, string.Template The grammar already exists; you only need the evaluator someone else wrote
Specification objects with operator overloads Rules are assembled in code or from a form, never parsed from text
ast.parse plus an allowlist and match Rules are written in Python syntax by people you trust to write Python
Tokenizer plus recursive descent (this page) A small, stable, user-facing language of your own
A parser generator (Lark, ANTLR) Anything bigger, or anything that needs good error recovery

Real-world usage

  • re is the Interpreter you use every day: re.compile parses a pattern language into a matcher, and the matcher interprets it against each string. fnmatch and glob translate a smaller language into regular expressions instead of interpreting it directly.
  • string.Template, str.format and f-strings interpret a substitution mini-language; ast.literal_eval is the allowlisted evaluator for one tiny grammar.
  • sqlite3 ships a complete SQL parser and interpreter; every ORM that accepts amount__gt=100 builds the same tree without text.
  • Frameworks: Django's Q lookups and Elasticsearch's query DSL are trees you build; Prometheus alert rules, jq filters and feature-flag targeting rules are trees parsed from text.
Looks like Interpreter How to tell them apart
Specification The same tree (And, Or, Not over leaves) built with operators in code instead of parsed from text. Specification has a fixed grammar and no parser; add a parser and you have arrived here.
Composite The syntax tree is a Composite; Interpreter adds the grammar that produces it and the evaluate that consumes it.
Visitor When the tree needs a second operation (render to SQL, list fields), put it in a Visitor or in a match function as fields_read does. Interpreter defines the nodes; Visitor keeps them closed while operations grow.
Strategy A strategy is a fixed algorithm chosen at runtime; an interpreted rule is an algorithm described at runtime. Rules often decide which strategy applies.
Flyweight Terminal nodes that carry no per-tree state can be shared across trees; the Gang of Four name this as the classic use of Flyweight.

Where it appears in LLD problems

  • Design a rate limiter (LLD) — which rule applies to a request: path = "/api/orders" AND tier = "free", parsed once from configuration. Say out loud that a dict keyed by endpoint does the job until the rules need OR.
  • Design Stack Overflow — search syntax such as [python] is:unanswered score:5: a tokenizer and a flat grammar parsed into Specification filters, with ranking left to a Strategy.
  • Design an in-memory key-value store with transactions — the REPL's SET a 1, BEGIN, ROLLBACK line grammar: a tokenizer and a dispatch table, which is as much Interpreter as the problem needs.

Interview tips

Interview tip

Write the grammar before the classes, a few lines of EBNF on the whiteboard, then say "one method per production, precedence is the call order, the nodes are frozen dataclasses so a parsed rule is a value I can cache". Then name what you would use instead: ast with an allowlist if the rules are Python, Specification if they come from a form, re or cron if the language already exists.

Common mistake

eval(rule_text). It is the one-line interpreter that also runs __import__("os").system(...) with your process's privileges; ast.literal_eval handles literals only, and an allowlisted ast walk is the safe version. Runner-up: parsing a grammar with parentheses using regular expressions. Regular languages cannot count brackets; the day a user nests two levels, that approach is over.