Problem: Interpreting a Language - Interpreter Pattern | OneNoughtOne

0/246

System Design (LLD)Interpreter Pattern

Interpreter Pattern (Overview)

LevelAdvanced

Duration90 mins

TopicInterpreter Pattern

1 / 4

Problem: Interpreting a Language

When Your Application Needs Its Own Language

Every sufficiently complex software system eventually faces a fascinating challenge: the need to express and evaluate domain-specific rules that are too dynamic or too numerous to hardcode. Whether it's mathematical expressions in a spreadsheet, search queries in a database, validation rules in a form builder, or routing conditions in a workflow engine—these all share a common characteristic: they require interpreting a language.

The Interpreter Pattern addresses one of the most intellectually rich problems in software engineering: how do you give your users (or your system) the ability to express complex ideas in a structured, parseable format that your program can understand and execute? This isn't merely about parsing strings—it's about creating computational meaning from textual or structural representations.

What You Will Learn

By the end of this page, you will understand the fundamental problem that drives the Interpreter Pattern: the need to process structured expressions within applications. You'll see why this problem is both ubiquitous and deceptively complex, and why naive solutions quickly become unmanageable. We'll explore the formal underpinnings of language interpretation while keeping the discussion grounded in practical engineering scenarios.

The Ubiquity of Embedded Languages

Before we dive into the Interpreter Pattern itself, let's appreciate just how pervasive the need for language interpretation is in modern software. You interact with interpreted languages constantly—often without realizing it.

Every day, you use systems that interpret languages:

Embedded Languages in Everyday Software
Application	Interpreted Language	Example Expression
Microsoft Excel / Google Sheets	Formula Language	=SUM(A1:A10) * IF(B1>100, 1.1, 1.0)
SQL Databases	SQL Query Language	SELECT * FROM users WHERE age > 21 AND status = 'active'
Regular Expressions	Regex Pattern Language	^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+.[a-zA-Z0-9-.]+$
Template Engines	Template Syntax	Hello, {{ user.name }}! You have {{ notifications.count }} alerts.
Search Engines	Query Syntax	site:github.com "interpreter pattern" language:java
Build Systems (make, gradle)	Build DSL	$(wildcard src/*.cpp): gcc -c $< -o $@
Configuration (nginx, Apache)	Config DSL	location /api { proxy_pass http://backend:3000; }
Game Modding	Scripting Languages	on_player_enter(zone) { spawn_enemy(zone.center) }
Financial Systems	Rule Languages	IF risk_score > 0.7 AND amount > 10000 THEN flag_for_review
Workflow Engines	Condition Languages	when: approval_count >= 2 and role == 'manager'

The common thread:

All of these systems share a fundamental requirement: they need to take structured text (or data) that represents some kind of computation, parse it into an understandable form, and then execute it to produce a result. This is the essence of interpretation.

The question is: when you need this capability in your own application, how do you implement it correctly? The Interpreter Pattern provides one answer—and understanding when it's the right answer (and when it isn't) is crucial to effective software design.

DSL vs General-Purpose Language

A Domain-Specific Language (DSL) is a language designed for a specific problem domain, with limited scope but high expressiveness within that domain. SQL is a DSL for data querying; regex is a DSL for pattern matching. In contrast, general-purpose languages like Python or Java are designed to solve any computational problem. The Interpreter Pattern is almost always applied to DSLs, not general-purpose languages—the complexity difference is astronomical.

Anatomy of the Interpretation Problem

To understand the Interpreter Pattern, we need to understand what interpretation actually involves. Language interpretation is a multi-stage process, each stage with its own complexities and design considerations.

The interpretation pipeline:

┌─────────────────────────────────────────────────────────────────────────────┐
│                        LANGUAGE INTERPRETATION PIPELINE                      │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  ┌──────────────┐    ┌──────────────┐    ┌──────────────┐    ┌───────────┐ │
│  │    INPUT     │    │    LEXER     │    │   PARSER     │    │  OUTPUT   │ │
│  │   (String)   │───▶│ (Tokenizer)  │───▶│ (Syntax      │───▶│ (Result)  │ │
│  │              │    │              │    │  Analyzer)   │    │           │ │
│  │ "3 + 5 * 2"  │    │ [3, +, 5,    │    │    [+]       │    │   "13"    │ │
│  │              │    │  *, 2]       │    │   /   \      │    │           │ │
│  │              │    │              │    │ [3]  [*]     │    │           │ │
│  │              │    │              │    │     /   \    │    │           │ │
│  └──────────────┘    └──────────────┘    │   [5]  [2]   │    └───────────┘ │
│                                          └──────────────┘                   │
│                                                 │                           │
│                      ┌──────────────────────────┘                           │
│                      ▼                                                      │
│               ┌──────────────┐                                              │
│               │ INTERPRETER  │                                              │
│               │ (Evaluator)  │                                              │
│               │              │                                              │
│               │ Walks the    │                                              │
│               │ tree and     │                                              │
│               │ computes     │                                              │
│               │ results      │                                              │
│               └──────────────┘                                              │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘

Stages of Language Interpretation

•Lexical Analysis (Tokenization) — The input string is broken into tokens (meaningful units). The string "3 + 5 * 2" becomes tokens: NUMBER(3), PLUS, NUMBER(5), MULTIPLY, NUMBER(2). This stage handles whitespace, comments, and basic syntax validation.
•Syntactic Analysis (Parsing) — Tokens are organized into a hierarchical structure that represents the grammatical structure of the expression. This structure is typically an Abstract Syntax Tree (AST). Parsing enforces grammar rules like operator precedence.
•Semantic Analysis (Optional) — For complex languages, this stage checks that the expression makes semantic sense (e.g., type checking, variable scope resolution). Simple DSLs often skip this stage.
•Interpretation (Evaluation) — The AST is traversed, and each node is evaluated according to its type. The Interpreter Pattern specifically addresses this stage by representing each grammar rule as a class.

The Interpreter Pattern's scope:

The Interpreter Pattern primarily concerns itself with the evaluation stage—specifically, how to structure the classes that represent and evaluate the parsed grammar. It provides a systematic way to define the relationship between grammar rules and their implementation.

However, understanding the full pipeline is essential because the pattern's utility depends heavily on what comes before (parsing) and what comes after (how results are used). A poorly designed grammar or an inefficient parser can make even a well-implemented Interpreter Pattern impractical.

A Concrete Motivating Example

Let's ground our discussion in a concrete scenario. Imagine you're building a form validation system for an enterprise application. The business team needs to define validation rules that can change without deploying new code.

The requirements:

Business Requirements

•Validation rules must be configurable by non-technical users
•Rules can be complex, involving multiple fields and conditions
•Rules must be stored in a database and evaluated at runtime
•The system must provide clear error messages when validation fails
•New rule types should be addable without core system changes

Example validation rules in a domain-specific syntax:

# Simple field validations
age >= 18
email MATCHES "^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$"
name IS_NOT_EMPTY
 
# Compound validations
(age >= 18) AND (country == "US")
 
# Complex business rules
(accountType == "premium") OR (referralCount >= 5)
(startDate < endDate) AND (budget >= minimumBudget)
(role == "admin") OR ((role == "manager") AND (department == userDepartment))
 
# Conditional validations (if X then Y must be true)
(hasChildren == true) IMPLIES (dependentsCount > 0)
 
# Aggregate validations
SUM(lineItems.amount) <= creditLimit
COUNT(attachments) >= 1

The naive approach and its problems:

A developer new to interpretation might start with a direct, procedural approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// ❌ PROBLEMATIC: Direct string parsing approach
 
function evaluateRule(rule: string, formData: Record<string, any>): boolean {
    // Handle OR
    if (rule.includes(' OR ')) {
        const parts = rule.split(' OR ');
        return parts.some(part => evaluateRule(part.trim(), formData));
    }
    
    // Handle AND
    if (rule.includes(' AND ')) {
        const parts = rule.split(' AND ');
        return parts.every(part => evaluateRule(part.trim(), formData));
    }
    
    // Handle parentheses (somehow...?)
    if (rule.startsWith('(') && rule.endsWith(')')) {
        return evaluateRule(rule.slice(1, -1), formData);
    }
    
    // Handle comparison operators
    if (rule.includes(' >= ')) {
        const [field, value] = rule.split(' >= ');
        return formData[field.trim()] >= Number(value.trim());
    }
    
    if (rule.includes(' == ')) {
        const [field, value] = rule.split(' == ');
        const cleanValue = value.trim().replace(/"/g, '');
        return formData[field.trim()] === cleanValue;
    }
    
    // And so on for every operator...
    
    throw new Error(`Unknown rule format: ${rule}`);
}

Why This Approach Fails

This implementation has critical flaws:

• Operator precedence is ignored — 'A OR B AND C' should parse as 'A OR (B AND C)' but the naive split treats all operators equally.

• Nested parentheses break — '((A AND B) OR C) AND D' cannot be correctly parsed with simple string matching.

• No clear grammar — The rules are implicitly defined in code, making extensions error-prone.

• Poor error handling — Invalid syntax produces cryptic errors.

• Unmaintainable — Each new operator requires modifying multiple code paths.

The Fundamental Challenge: Grammar and Recursion

The core difficulty with language interpretation lies in grammar—the formal rules that define what constitutes a valid expression and how expressions are structured. Grammars are inherently recursive, and this recursion must be handled correctly.

What is a grammar?

A grammar is a set of rules (productions) that define:

What symbols are valid in the language (vocabulary)
How symbols can be combined (syntax)
The hierarchical structure of valid expressions (derivation)

Here's a formal grammar for our validation rule language:

┌─────────────────────────────────────────────────────────────────────────────┐
│                    GRAMMAR FOR VALIDATION RULE LANGUAGE                      │
├─────────────────────────────────────────────────────────────────────────────┤
│                                                                             │
│  expression    ::= orExpression                                             │
│                                                                             │
│  orExpression  ::= andExpression ( "OR" andExpression )*                    │
│                                                                             │
│  andExpression ::= primary ( "AND" primary )*                               │
│                                                                             │
│  primary       ::= comparison                                               │
│                  | "(" expression ")"                                       │
│                  | "NOT" primary                                            │
│                                                                             │
│  comparison    ::= identifier operator value                                │
│                                                                             │
│  operator      ::= ">=" | "<=" | ">" | "<" | "==" | "!=" | "MATCHES"        │
│                                                                             │
│  identifier    ::= [a-zA-Z_][a-zA-Z0-9_.]*                                  │
│                                                                             │
│  value         ::= number | string | "true" | "false" | identifier          │
│                                                                             │
│  number        ::= [0-9]+("."[0-9]+)?                                       │
│                                                                             │
│  string        ::= '"' [^"]* '"'                                            │
│                                                                             │
└─────────────────────────────────────────────────────────────────────────────┘
 
PRECEDENCE (lowest to highest):
  1. OR
  2. AND  
  3. NOT
  4. Comparison operators
  5. Parentheses (grouping)

Why grammars are recursive:

Notice how expression can contain orExpression, which contains andExpression, which contains primary, which can contain... expression again (inside parentheses). This recursion enables nested expressions of arbitrary depth:

(a AND b) — one level
((a AND b) OR c) — two levels
(((a OR b) AND c) OR (d AND e)) — three levels

This recursive nature is what makes naive string splitting fail and what makes a structured approach essential.

Key Challenges in Language Interpretation

•Precedence handling — In 'a OR b AND c', the AND should bind tighter than OR. Grammar structure encodes this, but code must enforce it.
•Associativity — Is 'a - b - c' evaluated as '(a - b) - c' (left associative) or 'a - (b - c)' (right associative)? Most operators are left-associative.
•Recursive descent — Parsing requires handling recursion without infinite loops, typically through careful grammar design.
•Error recovery — When syntax is invalid, should parsing halt immediately or attempt to continue? Good error messages require context preservation.
•Context sensitivity — Some expressions depend on context (variable types, scopes). This adds semantic analysis requirements.

The Abstract Syntax Tree as Solution

The Abstract Syntax Tree (AST) is the data structure that makes language interpretation tractable. It transforms the linear structure of text into a hierarchical structure that mirrors the logical structure of the expression.

Why an AST?

The AST serves multiple purposes:

Captures structure — The tree hierarchy explicitly represents precedence and grouping
Enables evaluation — Traversing the tree naturally handles recursion
Supports transformation — The tree can be optimized, analyzed, or transpiled
Decouples parsing from evaluation — The same AST can be evaluated, pretty-printed, or converted to other formats

INPUT: (age >= 18) AND ((country == "US") OR (verified == true))
 
                                   [AND]
                                  /     \
                                 /       \
           [GreaterOrEqual]             [OR]
              /        \              /      \
         [age]        [18]           /        \
                        [Equal]           [Equal]
                       /      \          /       \
                 [country]  ["US"]  [verified]  [true]
 
 
TREE NODE TYPES:
  ┌─────────────────────────────────────────────────────────────────┐
  │  BinaryExpression:  left: Expression, op: Operator, right: Expr │
  │  UnaryExpression:   op: Operator, operand: Expression           │
  │  Literal:           value: number | string | boolean            │
  │  Identifier:        name: string                                │
  │  FunctionCall:      name: string, args: Expression[]            │
  └─────────────────────────────────────────────────────────────────┘

Evaluation via tree traversal:

Once you have an AST, evaluation becomes a straightforward recursive process:

If the node is a Literal, return its value
If the node is an Identifier, look up its value in the context
If the node is a BinaryExpression, evaluate left and right recursively, then apply the operator
If the node is a UnaryExpression, evaluate the operand, then apply the operator

This is where the Interpreter Pattern enters: it provides a class-based structure for implementing this evaluation logic in an extensible, maintainable way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// Conceptual evaluation function
 
function evaluate(node: ASTNode, context: Context): any {
    switch (node.type) {
        case 'Literal':
            return node.value;
            
        case 'Identifier':
            return context.lookup(node.name);
            
        case 'BinaryExpression': {
            const left = evaluate(node.left, context);
            const right = evaluate(node.right, context);
            
            switch (node.operator) {
                case 'AND': return left && right;
                case 'OR':  return left || right;
                case '>=':  return left >= right;
                case '==':  return left === right;
                // ... other operators
            }
        }
        
        case 'UnaryExpression': {
            const operand = evaluate(node.operand, context);
            
            switch (node.operator) {
                case 'NOT': return !operand;
                // ... other unary operators
            }
        }
    }
}
 
// Usage:
// const ast = parse("(age >= 18) AND (verified == true)");
// const result = evaluate(ast, { age: 25, verified: true });
// result === true

The Interpreter Pattern's Insight

The switch statement in the conceptual evaluator hints at a design smell: we're dispatching based on type, which in object-oriented design often suggests polymorphism. The Interpreter Pattern replaces this switch with a class hierarchy where each node type knows how to interpret itself. This is the pattern's core contribution.

When Does This Problem Arise?

Not every application needs language interpretation. The problem typically emerges when certain conditions are present. Understanding these conditions helps you recognize when the Interpreter Pattern (or interpretation in general) is appropriate.

Signals that you need a language:

Indicators for Language Interpretation

•Configuration complexity exceeds key-value pairs — When simple settings evolve into conditional logic ('if X > 10 then Y, else Z'), you're seeing emergent language needs.
•Business rules are dynamic — Rules that change frequently or are defined by non-engineers often need a structured, interpretable format.
•User-defined expressions — Spreadsheet formulas, search queries, template syntax—whenever users compose expressions, you have a language.
•Domain experts think in structured terms — Financial analysts think in formulas; security engineers think in rule conditions. Capturing their mental models often requires a DSL.
•Repetitive pattern matching in code — If you find yourself writing many variations of similar conditional logic, a DSL might consolidate and clarify.
•Cross-platform consistency — When the same logic must execute on multiple platforms (server, client, mobile), a language abstraction ensures consistency.

Good Candidates

•Mathematical expression evaluators
•Validation rule engines
•Query languages (search, filtering)
•Template systems with logic
•Workflow condition languages
•Access control policy languages
•Financial formula interpreters
•Bot command parsers

Poor Candidates

•General-purpose programming (too complex)
•Simple key-value configurations
•Fixed, rarely-changing business logic
•Single-use parsing needs
•Performance-critical inner loops
•When existing tools suffice (SQL, regex)

The Complexity Trap

Building an interpreter is a significant investment. Before embarking on this path, exhaust simpler alternatives: Can you use an existing DSL? Can you expose a configuration API? Can you use an embedded scripting language like Lua or JavaScript? The Interpreter Pattern is powerful but carries real implementation and maintenance costs.

The Problem Statement Crystallized

Let's crystallize everything we've discussed into a precise problem statement that the Interpreter Pattern addresses.

The Interpreter Pattern Problem Statement

Given: • A language with a defined grammar (set of rules) • Expressions in that language that must be evaluated at runtime • The grammar is relatively simple (not a full programming language) • Extensibility matters more than raw performance

Challenge: • How do we represent the grammar in code? • How do we parse expressions into evaluable structures? • How do we evaluate expressions consistently and extensibly? • How do we add new expression types without rewriting existing code?

Constraints: • The solution must be maintainable as the grammar evolves • Different operations on the same AST may be needed (evaluate, print, validate) • Error handling must be clear and actionable

What we need from a solution:

An effective solution to the interpretation problem provides:

A clear mapping from grammar rules to code constructs — Each rule should have an obvious implementation location.
Polymorphic evaluation — Each expression type should know how to evaluate itself, eliminating large switch statements.
Easy extensibility — Adding a new operator or expression type should require adding a new class, not modifying existing ones.
Composability — Complex expressions should be built by composing simpler expressions.
Separation of concerns — Parsing should be separate from evaluation, which should be separate from error handling.

The Interpreter Pattern, which we'll explore in the next page, addresses exactly these requirements through a class hierarchy that mirrors the grammar structure.

Summary: The Interpretation Challenge

We've established the foundation for understanding the Interpreter Pattern. Let's consolidate what we've learned:

Key Takeaways: The Problem Space

•Language interpretation is ubiquitous — From spreadsheet formulas to SQL queries, DSLs permeate software systems.
•The interpretation pipeline has stages — Lexing, parsing, semantic analysis, and evaluation each have distinct responsibilities.
•Grammars are recursive — This recursion requires structured handling that naive string parsing cannot provide.
•The AST is central — It transforms linear text into hierarchical structure that enables clean evaluation.
•Not every problem needs interpretation — The complexity cost is real; evaluate alternatives first.
•The problem invites polymorphism — Type-dispatched evaluation suggests a class hierarchy solution.

What's next:

Now that we understand the problem—the need to interpret structured expressions in a language—we're ready to explore the Interpreter Pattern's solution. The next page will show how representing grammar rules as classes creates an elegant, extensible architecture for language interpretation.

Page Complete

You now understand the fundamental problem that the Interpreter Pattern solves: interpreting structured expressions in a domain-specific language. You've seen why naive approaches fail, why grammars are inherently recursive, and why the AST is central to interpretation. Next, we'll see how the Interpreter Pattern leverages object-oriented design to create a grammar representation as classes.