Interpreter

Learning Objectives

Represent a small grammar as an abstract syntax tree (AST) and evaluate it.

Write a recursive-descent parser for a tiny language.

Know the limits of the pattern and when to use parser libraries.

Prerequisites: Modules 35, 49.

Intuition and Definition

Intent: given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences.

Participants: Expression interface with evaluate(context), terminal expressions (numbers, variables), non-terminal expressions (operators combining sub-expressions) — a Composite — plus a parser that builds the tree and a Context holding variable values.

Why It Matters

Rule engines, alarm conditions ("coolant > 110 and rpm > 3000"), feature flags and configuration formulas are small languages. A tiny interpreter keeps them out of hard-coded ifs and lets non-programmers change them.

Syntax and Language Notes

Grammar for this module's rule language (EBNF):

expr   := term (("and" | "or") term)*
term   := value ((">" | "<") value)?
value  := NUMBER | IDENTIFIER | "(" expr ")"

Complete Example

#include <cctype>
#include <iostream>
#include <map>
#include <memory>
#include <stdexcept>
#include <string>

using Context = std::map<std::string, double>;

struct Expr {                                                    // AST node (Composite)
    virtual ~Expr() = default;
    virtual double eval(const Context& c) const = 0;
};
struct Num : Expr { double v; explicit Num(double x) : v(x) {} double eval(const Context&) const override { return v; } };
struct Var : Expr {
    std::string name; explicit Var(std::string n) : name(std::move(n)) {}
    double eval(const Context& c) const override { auto it = c.find(name); if (it == c.end()) throw std::runtime_error("unknown signal " + name); return it->second; }
};
struct Bin : Expr {
    std::string op; std::unique_ptr<Expr> l, r;
    Bin(std::string o, std::unique_ptr<Expr> a, std::unique_ptr<Expr> b) : op(std::move(o)), l(std::move(a)), r(std::move(b)) {}
    double eval(const Context& c) const override {
        if (op == "and") return (l->eval(c) != 0 && r->eval(c) != 0) ? 1 : 0;   // short-circuit
        if (op == "or")  return (l->eval(c) != 0 || r->eval(c) != 0) ? 1 : 0;
        double a = l->eval(c), b = r->eval(c);
        
…

coolant=112 rpm=2500 load=85 -> WARN
coolant=112 rpm=2500 load=40 -> ok
coolant=95 rpm=4000 load=90 -> ok
parse error: unexpected character at position 10

Step-by-Step Walkthrough

The parser turns the text into a tree: and(>(coolant,110), or(>(rpm,3000), >(load,80))).

Evaluation walks the tree with a context of current signal values; and/or short-circuit.

The third case is ok because coolant > 110 is false — the right side isn't even evaluated.

Malformed input is rejected with a clear message instead of misbehaving.

Common Mistakes

Growing a "tiny" language until it needs precedence rules, functions and error recovery — use a real parser generator or an embedded scripting language.

No validation of identifiers before evaluation (unknown signals at run time).

Evaluating untrusted expressions with eval()-style host-language execution — a security hole; always use a restricted interpreter.

Deep recursion on pathological input — limit nesting depth.

Trade-offs and Alternatives

Interpreter is right for small, stable grammars. For larger languages use parser generators (ANTLR), parser combinators, PEG libraries, or embed an existing language (Lua). For configuration, consider data formats (JSON/YAML) with schema validation instead of a language.

Real-World Use

Rule engines, alarm/telltale conditions, SQL WHERE clause evaluation, regular-expression engines, spreadsheet formulas, template languages, A2L/ODX-like calibration formulas.

Practice

Q1. (Easy) Which structural pattern does an AST use?

Answer: Composite.

Q2. (Medium) Why must and short-circuit?

Answer: For correctness (the right side might be invalid when the left is false, e.g. division by zero or a missing signal) and efficiency.

Q3. (Advanced) How would you add a "not" operator?

Answer: Extend the grammar (value := "not" value | ...), add a Not node whose eval returns !inner->eval(c), and parse not before other values in value().

Interview Question

Q1. "Why is building an AST better than evaluating the string directly each time?"

Answer: Parsing once separates syntax checking from evaluation: errors are reported up front, the tree can be validated (known identifiers, type checks), optimized (constant folding), visited for other purposes (pretty-printing, explaining why a rule fired), and evaluated many times quickly against changing contexts.

Quick Quiz

Q1. What are terminal expressions?

Answer: Leaves such as numbers and variables.

Q2. What is a context in the Interpreter pattern?

Answer: The current values (variables/signals) used during evaluation.

Q3. When should you stop hand-writing an interpreter?

Answer: When the grammar grows beyond a small, stable language — then use a parser library or an embedded language.

Summary

Interpreter = grammar → AST (Composite) → evaluate with a context.

Great for tiny rule languages; switch to tools as languages grow.

Related: Modules 35, 49.