Interpreter pattern in LLD - System Design Guide

Problem Statement

When a system needs to evaluate or process sentences or expressions in a language, hardcoding the logic for each possible expression leads to complex, rigid, and unmaintainable code. This makes it difficult to add new expressions or modify existing ones without changing the core logic.

Solution

The Interpreter pattern defines a grammar for the language and uses a set of classes to represent each rule or expression. Each class knows how to interpret or evaluate itself. This way, the system can parse and evaluate sentences by composing these classes, making it easy to extend or modify the language without changing the overall structure.

Architecture

Client

(uses parser)

→Context

↓

TerminalExpression

↓

NonTerminalExpression

This diagram shows the Client using a Context and an Abstract Expression interface. Terminal and NonTerminal Expressions implement the interface to interpret parts of the input.

Trade-offs

✓ Pros

→

Simplifies parsing and evaluating complex languages by breaking down expressions into manageable classes.

→

Makes it easy to add new grammar rules by adding new expression classes without changing existing code.

→

Improves maintainability by encapsulating interpretation logic within expression classes.

✗ Cons

→

Can lead to a large number of classes if the grammar is complex, increasing codebase size.

→

Not efficient for very complex or large languages due to recursive interpretation overhead.

→

Requires a well-defined grammar; otherwise, the pattern can become confusing and hard to manage.

Use when you have a simple grammar or language to interpret, and you want to represent sentences as a tree of expressions that can be evaluated or interpreted.

Avoid when the language grammar is very complex or when performance is critical, as the recursive interpretation can be slow and hard to optimize.

Real World Examples

SQL databases

Use the Interpreter pattern internally to parse and evaluate SQL queries by representing query components as expressions.

Regular expression engines

Interpret regex patterns by breaking them into expression trees that can be evaluated against input strings.

Spreadsheet software (e.g., Microsoft Excel)

Interpret formulas entered by users by parsing them into expression trees for evaluation.

Code Example

The before code uses hardcoded string parsing and evaluation logic inside one class, making it hard to extend. The after code uses the Interpreter pattern by defining an abstract Expression class and concrete classes for numbers and operations. Each class knows how to interpret itself, making the system extensible and easier to maintain.

LLD

### Before: Without Interpreter Pattern (hardcoded evaluation)
class Evaluator:
    def evaluate(self, expression):
        if '+' in expression:
            left, right = expression.split('+')
            return int(left) + int(right)
        elif '-' in expression:
            left, right = expression.split('-')
            return int(left) - int(right)
        else:
            return int(expression)

# Usage
expr = "3+5"
eval = Evaluator()
print(eval.evaluate(expr))  # Output: 8


### After: With Interpreter Pattern
from abc import ABC, abstractmethod

class Expression(ABC):
    @abstractmethod
    def interpret(self):
        pass

class Number(Expression):
    def __init__(self, value):
        self.value = value
    def interpret(self):
        return self.value

class Add(Expression):
    def __init__(self, left, right):
        self.left = left
        self.right = right
    def interpret(self):
        return self.left.interpret() + self.right.interpret()

class Subtract(Expression):
    def __init__(self, left, right):
        self.left = left
        self.right = right
    def interpret(self):
        return self.left.interpret() - self.right.interpret()

# Client code to parse "3+5" into expression tree
left = Number(3)
right = Number(5)
expression = Add(left, right)
print(expression.interpret())  # Output: 8

Alternatives

Parser combinator

Builds complex parsers by combining simpler parsers functionally rather than using class hierarchies.

Use when: When you want a functional approach to parsing with better composability and error handling.

Visitor pattern

Separates operations from the object structure, allowing new operations without changing classes.

Use when: When you want to add new operations on a fixed set of expression classes without modifying them.

State machine

Models language parsing as state transitions rather than recursive interpretation.

Use when: When the language can be represented as states and transitions, especially for simpler or linear grammars.

Summary

Interpreter pattern helps evaluate sentences or expressions by representing grammar rules as classes.

It improves maintainability and extensibility by encapsulating interpretation logic within expression objects.

It is best suited for simple languages or expressions but can be inefficient for complex grammars.