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.

Practice

1. What is the main purpose of the Interpreter pattern in system design?

easy

A. To manage user authentication and authorization

B. To define a grammar for a simple language and interpret sentences in that language

C. To store data persistently in a database

D. To create multiple threads for parallel processing

Solution

1. Step 1: Understand the role of the Interpreter pattern

   The Interpreter pattern defines a way to evaluate sentences in a language by representing grammar rules as classes.

2. Step 2: Match the purpose with options

   Only To define a grammar for a simple language and interpret sentences in that language correctly describes defining a grammar and interpreting sentences, which is the core of the Interpreter pattern.

3. Final Answer:

   To define a grammar for a simple language and interpret sentences in that language -> Option B

4. Quick Check:

   Interpreter pattern = Define grammar and interpret [OK]

Hint: Interpreter pattern = grammar + interpretation [OK]

Common Mistakes:

• Confusing Interpreter with concurrency patterns
• Thinking it manages data storage
• Mixing it up with security patterns

2. Which of the following is the correct way to define an interpret() method in an expression interface for the Interpreter pattern?

easy

A. def interpret(context): return self

B. def interpret(): return context

C. def interpret(self): return None

D. def interpret(self, context): pass

Solution

1. Step 1: Recall the method signature for interpret in Interpreter pattern

   The interpret method usually takes a context parameter and is defined as an instance method with self.

2. Step 2: Compare options with correct signature

   def interpret(self, context): pass correctly defines interpret(self, context) with a placeholder pass, matching the pattern's interface.

3. Final Answer:

   def interpret(self, context): pass -> Option D

4. Quick Check:

   interpret method = instance method with context parameter [OK]

Hint: interpret() needs self and context parameters [OK]

Common Mistakes:

• Omitting self parameter in method
• Not passing context argument
• Returning wrong values or missing parameters

3. Given the following Python-like pseudocode for an Interpreter pattern, what will be the output?

class TerminalExpression:
    def __init__(self, data):
        self.data = data
    def interpret(self, context):
        return self.data in context

class AndExpression:
    def __init__(self, expr1, expr2):
        self.expr1 = expr1
        self.expr2 = expr2
    def interpret(self, context):
        return self.expr1.interpret(context) and self.expr2.interpret(context)

expr1 = TerminalExpression('apple')
expr2 = TerminalExpression('banana')
and_expr = AndExpression(expr1, expr2)
print(and_expr.interpret(['apple', 'banana', 'cherry']))

medium

A. True

B. False

C. Error due to missing method

D. None

Solution

1. Step 1: Evaluate TerminalExpression interpret calls

   expr1.interpret checks if 'apple' is in the list ['apple', 'banana', 'cherry'] -> True. expr2.interpret checks if 'banana' is in the list -> True.

2. Step 2: Evaluate AndExpression interpret

   AndExpression returns True if both expr1 and expr2 interpret return True. Both are True, so result is True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Both terms in list -> True [OK]

Hint: AND expression true only if both sub-expressions true [OK]

Common Mistakes:

• Assuming 'in' checks keys instead of values
• Confusing AND with OR logic
• Forgetting to return boolean result

4. In the following code snippet implementing the Interpreter pattern, what is the error?

class OrExpression:
    def __init__(self, expr1, expr2):
        self.expr1 = expr1
        self.expr2 = expr2
    def interpret(self, context):
        return self.expr1.interpret(context) | self.expr2.interpret(context)

medium

A. Using bitwise OR operator instead of logical OR

B. Missing return statement in interpret method

C. Incorrect constructor parameters

D. interpret method missing context parameter

Solution

1. Step 1: Identify operator used in interpret method

   The code uses the bitwise OR operator '|' instead of the logical OR operator 'or' for boolean logic.

2. Step 2: Explain why this is an error

   Bitwise OR can cause unexpected results with booleans and is not the intended logical operation for combining expressions.

3. Final Answer:

   Using bitwise OR operator instead of logical OR -> Option A

4. Quick Check:

   Logical OR needs 'or', not '|' [OK]

Hint: Use 'or' for logical OR, not '|' [OK]

Common Mistakes:

• Confusing bitwise and logical operators
• Forgetting to return a value
• Incorrect method signatures

5. You want to design a system using the Interpreter pattern to evaluate complex search queries combining keywords with AND, OR, and NOT. Which design approach best supports scalability and easy extension?

hard

A. Store all queries as strings and parse them manually each time without classes

B. Use a single class with many if-else statements to handle all expression types

C. Create separate classes for TerminalExpression, AndExpression, OrExpression, and NotExpression implementing a common interface

D. Implement only TerminalExpression and handle AND/OR/NOT outside the interpreter

Solution

1. Step 1: Identify design principles for Interpreter pattern

   Using separate classes for each expression type following a common interface allows modularity and easy extension.

2. Step 2: Evaluate options for scalability and maintainability

   Create separate classes for TerminalExpression, AndExpression, OrExpression, and NotExpression implementing a common interface supports adding new expressions without changing existing code, unlike monolithic if-else or manual parsing.

3. Final Answer:

   Create separate classes for TerminalExpression, AndExpression, OrExpression, and NotExpression implementing a common interface -> Option C

4. Quick Check:

   Separate classes + common interface = scalable design [OK]

Hint: Use separate classes per expression type for easy extension [OK]

Common Mistakes:

• Using one class with complex conditionals
• Parsing strings manually every time
• Handling logic outside interpreter classes