Python Interpreter Pattern

The Interpreter Pattern is a behavioral design pattern that defines the grammar of a language and establishes an interpreter to interpret sentences in that language. Simply put, it is like a small compiler that can parse and execute expressions with specific syntactic rules.

Core Idea

Imagine a calculator scenario: when you input"2 + 3 * 4"an expression like this, the calculator needs to understand the meaning of the string and perform calculations according to mathematical operation rules. The Interpreter Pattern is a design solution that implements this process of "understanding" and "execution".

Applicable Scenarios

The Interpreter Pattern is especially suitable for the following situations:

  • When there is a need to interpret and execute a language or expression
  • When the grammar is relatively simple and not overly complex
  • When execution efficiency is not a key consideration
  • When grammar rules need to be frequently extended

Pattern Structure

Let's understand the core components of the Interpreter Pattern through a class diagram:

Component Description

AbstractExpression

  • Defines the interface for interpretation operations
  • Usually containsinterpret()method

TerminalExpression

  • Implements the interpretation operations related to terminal symbols in the grammar
  • Cannot be decomposed into smaller expressions

NonterminalExpression

  • Implements the interpretation operations related to nonterminal symbols in the grammar
  • Usually contains references to other expressions

Context

  • Contains some global information needed by the interpreter
  • Stores input and output results

Basic Syntax and Implementation

Abstract Expression Class

Example

from abc import ABC, abstractmethod

class Expression(ABC):
    """Abstract expression class, defines the interpretation interface"""
   
    @abstractmethod
    def interpret(self, context):
        """Interpretation method, implemented by concrete subclasses"""
        pass

Terminal Expression

Example

class NumberExpression(Expression):
    """Number expression - terminal expression"""
   
    def __init__(self, number):
        self.number = number
   
    def interpret(self, context):
        # Directly return the numeric value
        return self.number
   
    def __str__(self):
        return f"Number({self.number})"

Nonterminal Expression

Example

class AddExpression(Expression):
    """Addition expression - nonterminal expression"""
   
    def __init__(self, left, right):
        self.left = left    # Left expression
        self.right = right  # Right expression
   
    def interpret(self, context):
        # Interpret the left and right expressions respectively, then add them together
        return self.left.interpret(context) + self.right.interpret(context)
   
    def __str__(self):
        return f"({self.left} + {self.right})"

class SubtractExpression(Expression):
    """Subtraction expression - nonterminal expression"""
   
    def __init__(self, left, right):
        self.left = left
        self.right = right
   
    def interpret(self, context):
        return self.left.interpret(context) - self.right.interpret(context)
   
    def __str__(self):
        return f"({self.left} - {self.right})"

class MultiplyExpression(Expression):
    """Multiplication expression - nonterminal expression"""
   
    def __init__(self, left, right):
        self.left = left
        self.right = right
   
    def interpret(self, context):
        return self.left.interpret(context) * self.right.interpret(context)
   
    def __str__(self):
        return f"({self.left} * {self.right})"

Complete Example: Simple Calculator

Let's implement a complete simple calculator to interpret mathematical expressions:

Example

class CalculatorContext:
    """Calculator context, stores calculation-related information"""
   
    def __init__(self):
        self.variables = {}  # Store variable values
   
    def set_variable(self, name, value):
        """Set variable value"""
        self.variables[name] = value
   
    def get_variable(self, name):
        """Get variable value"""
        return self.variables.get(name, 0)

class VariableExpression(Expression):
    """Variable expression - terminal expression"""
   
    def __init__(self, name):
        self.name = name
   
    def interpret(self, context):
        # Get the variable value from the context
        return context.get_variable(self.name)
   
    def __str__(self):
        return self.name

class Calculator:
    """Calculator class - builds and interprets expressions"""
   
    @staticmethod
    def parse_expression(expression_str, context):
        """
Parse string expressions into an expression tree
Simplified here; actual applications may require a more complex parser
        """
        # Simple expression parsing (for real projects, it is recommended to use a dedicated parsing library)
        tokens = expression_str.replace('(', ' ( ').replace(')', ' ) ').split()
        return Calculator._parse_tokens(tokens)
   
    @staticmethod
    def _parse_tokens(tokens):
        """Recursively parse the token list"""
        if not tokens:
            return None
           
        token = tokens.pop(0)
       
        if token == '(':
            # Start parsing compound expressions
            left = Calculator._parse_tokens(tokens)
            operator = tokens.pop(0)
            right = Calculator._parse_tokens(tokens)
            tokens.pop(0)  # Remove ')'
           
            if operator == '+':
                return AddExpression(left, right)
            elif operator == '-':
                return SubtractExpression(left, right)
            elif operator == '*':
                return MultiplyExpression(left, right)
        else:
            # Parse basic expressions (numbers or variables)
            if token.isdigit() or (token[0] == '-' and token[1:].isdigit()):
                return NumberExpression(int(token))
            else:
                return VariableExpression(token)

# Usage example
def main():
    # Create context
    context = CalculatorContext()
    context.set_variable('x', 10)
    context.set_variable('y', 5)
   
    # Manually build expression: (x + 3) * (y - 2)
    expression = MultiplyExpression(
        AddExpression(VariableExpression('x'), NumberExpression(3)),
        SubtractExpression(VariableExpression('y'), NumberExpression(2))
    )
   
    print(f"Expression: {expression}")
    result = expression.interpret(context)
    print(f"Result: {result}")  # Output: (10 + 3) * (5 - 2) = 39
   
    # Use the parser
    simple_expr = AddExpression(NumberExpression(5), NumberExpression(3))
    print(f"Simple expression: {simple_expr} = {simple_expr.interpret(context)}")

if __name__ == "__main__":
    main()

Advanced Application: SQL WHERE Condition Interpreter

Let's look at a more practical example - implementing a simplified SQL WHERE condition interpreter:

Example

class SQLContext:
    """SQL query context"""
   
    def __init__(self, record):
        self.record = record  # Data records
   
    def get_value(self, field):
        """Get field value"""
        return self.record.get(field)

class FieldExpression(Expression):
    """Field expression"""
   
    def __init__(self, field_name):
        self.field_name = field_name
   
    def interpret(self, context):
        return context.get_value(self.field_name)

class ConstantExpression(Expression):
    """Constant expression"""
   
    def __init__(self, value):
        self.value = value
   
    def interpret(self, context):
        return self.value

class EqualsExpression(Expression):
    """Equality comparison expression"""
   
    def __init__(self, left, right):
        self.left = left
        self.right = right
   
    def interpret(self, context):
        return self.left.interpret(context) == self.right.interpret(context)

class AndExpression(Expression):
    """AND expression"""
   
    def __init__(self, left, right):
        self.left = left
        self.right = right
   
    def interpret(self, context):
        return self.left.interpret(context) and self.right.interpret(context)

class OrExpression(Expression):
    """OR expression"""
   
    def __init__(self, left, right):
        self.left = left
        self.right = right
   
    def interpret(self, context):
        return self.left.interpret(context) or self.right.interpret(context)

# Usage example: simulate SQL WHERE condition filtering
def sql_demo():
    # Simulate data records
    records = [
        {'name': 'Alice', 'age': 25, 'department': 'Engineering'},
        {'name': 'Bob', 'age': 30, 'department': 'Sales'},
        {'name': 'Charlie', 'age': 28, 'department': 'Engineering'},
        {'name': 'Diana', 'age': 35, 'department': 'Marketing'}
    ]
   
    # Build WHERE condition: (department = 'Engineering') AND (age > 26)
    class GreaterThanExpression(Expression):
        def __init__(self, left, right):
            self.left = left
            self.right = right
       
        def interpret(self, context):
            return self.left.interpret(context) > self.right.interpret(context)
   
    # Build expression tree
    condition = AndExpression(
        EqualsExpression(FieldExpression('department'), ConstantExpression('Engineering')),
        GreaterThanExpression(FieldExpression('age'), ConstantExpression(26))
    )
   
    print("Qualifying records:")
    for record in records:
        context = SQLContext(record)
        if condition.interpret(context):
            print(f"- {record['name']}, {record['age']} years old, {record['department']}")

if __name__ == "__main__":
    sql_demo()

Pros and Cons of the Pattern

Advantages

  1. Easy to extend grammar: Adding new expression classes can extend grammar rules
  2. Easy to implement: Each expression class is relatively simple and easy to implement and maintain
  3. Strong flexibility: Can dynamically change the interpretation approach
  4. Follows the Open/Closed Principle: Open for extension, closed for modification

Disadvantages

  1. Performance issues: The Interpreter Pattern is usually inefficient, especially for complex grammars
  2. Increased complexity: For complex grammars, a large number of classes are generated, increasing system complexity
  3. Difficult debugging: Debugging complex expression trees can be difficult

Best Practices and Considerations

When to Use

  • When the grammar is relatively simple and stable
  • When execution efficiency is not the primary consideration
  • When new grammar rules need to be added frequently

Alternatives

For complex grammars, consider the following alternatives:

  • Use existing parser generators(such as ANTLR, PLY)
  • Use compiler/interpreter frameworks
  • Consider other design patterns, such as the Visitor Pattern to handle abstract syntax trees

Performance Optimization Tips

Example

class OptimizedExpression(Expression):
    """Optimized expression base class"""
   
    def __init__(self):
        self._cache = {}  # Add caching mechanism
   
    def interpret(self, context):
        # Use cache to avoid repeated calculations
        cache_key = id(context)
        if cache_key not in self._cache:
            self._cache[cache_key] = self._do_interpret(context)
        return self._cache[cache_key]
   
    def _do_interpret(self, context):
        """Actual interpretation logic, implemented by subclasses"""
        pass

Practice Exercises

Exercise 1: Extend the Calculator

Add the following functionality to the calculator:

  • Division operation
  • Modulo operation
  • Support parenthesized precedence

Exercise 2: Implement a Boolean Expression Interpreter

Create a boolean expression interpreter that supports:

  • AND, OR, NOT operations
  • Comparison operations (>, <, >=, <=, ==, !=)
  • Variable substitution

Exercise 3: Design a Rule Engine

Use the Interpreter Pattern to design a simple rule engine that can:

  • Parse business rules
  • Evaluate rules based on input data
  • Output decision results

Summary

The Interpreter pattern provides an elegant solution for handling Domain-Specific Languages (DSL). Although in actual projects, for complex grammars we tend to use professional parsing tools, understanding the principles of the Interpreter pattern is of great significance for mastering compilation principles and language processing.

Remember the core ideas of design patterns:Not every pattern fits every scenario; choosing the solution that best suits the current needs is the key。

Other extensions