Interpreter Pattern – Building Flexible Language Interpreters in Programming

1. Introduction

The Interpreter Pattern is a behavioral design pattern created to solve a fascinating problem: how can a program "understand" and "execute" commands based on a grammar you define yourself?

Imagine you're building an application that lets users enter mathematical expressions like "3 + 5 * 2", or a search tool with custom syntax like "name:John AND age>25". The Interpreter Pattern is the key to transforming those "meaningless" strings into concrete actions.

At its core, this pattern operates on three principles:

• Read the input according to a predefined grammar structure

• Parse that structure into smaller components

• Execute each component to produce the final result

Real-world example: When you write an SQL query like SELECT * FROM users WHERE age > 18, the database engine uses a form of interpreter to parse and execute this command.

2. Architecture

The Interpreter Pattern consists of these main components:

AbstractExpression This is an interface or abstract class that declares the Interpret() method – the core method that all concrete expressions must implement. It defines the common "contract" for interpretation.

TerminalExpression Represents the most basic elements in the grammar – the "leaves" of the syntax tree. They contain no sub-expressions.

Example: In the expression "3 + 5", the numbers 3 and 5 are TerminalExpressions.

NonterminalExpression Represents more complex grammar rules that can contain one or more sub-expressions (both Terminal and Nonterminal).

Example: In "3 + 5", the addition operator + is a NonterminalExpression because it combines two sub-expressions.

Context An object containing global information needed for the interpretation process. The Context is shared among all nodes in the syntax tree, facilitating data and state transfer throughout processing.

3. Pros and Cons

Advantages

• Easy grammar extension: Adding new rules only requires creating a new Expression class without affecting existing code (following the Open/Closed Principle).

• Clear separation: Each grammar rule is encapsulated in its own class, making code readable and maintainable.

• Flexibility: Allows changing interpretation behavior without modifying the grammar structure.

• High reusability: Expressions can be combined in various ways.

Disadvantages

• Complex with large grammars: Each rule needs its own class; complex grammars lead to "class explosion" – too many classes to manage.

• Performance limitations: Recursive tree traversal can be slow with large inputs.

• Difficult debugging: Execution flow is distributed across many classes, making error tracking challenging.

4. When to Use

The Interpreter Pattern is suitable when:

• Simple and stable grammar: The pattern works best with grammars that have few rules and rarely change over time.

• Performance isn't the top priority: If you need to process millions of expressions per second, consider other approaches.

• Building a DSL (Domain-Specific Language): When you want to create a custom language for a specific domain.

Practical applications:

• Compilers and interpreters

• SQL, XML, JSON parsers

• Advanced search tools with custom syntax

• Rule engines

• Regular expressions

5. C# Implementation Example

Problem: Build a program that analyzes aircraft model codes to determine the brand, model number, and aircraft type.

Grammar rules:

• Code starts with "A" (Airbus) or "B" (Boeing)

• Length of 4-5 characters

• Ending with "F" means cargo/freighter aircraft

Step 1: Create Context

csharp

class Context
{
    private string ac_model = "";
    private bool isAircraft = false;

    public Context(string _ac_model)
    {
        this.ac_model = _ac_model;
    }

    public string getModel()
    {
        return this.ac_model;
    }

    public int getLenght()
    {
        return this.ac_model.Length;
    }

    public string getLastChar()
    {
        return this.ac_model[this.ac_model.Length - 1].ToString();
    }

    public string getFirstChar()
    {
        return this.ac_model[0].ToString();
    }

    public void setIsAircraft(bool _isAircraft)
    {
        this.isAircraft = _isAircraft;
    }

    public bool getIsAircraft()
    {
        return this.isAircraft;
    }
}

The Context stores the aircraft model code and an isAircraft flag to mark whether the input is valid.

Step 2: Create AbstractExpression

csharp

interface Expression
{
    void InterpretContext(Context context);
}

A simple interface with a single method – the common ground for all expressions.

Step 3: Create NonterminalExpression

csharp

class CheckExpression : Expression
{
    public void InterpretContext(Context context)
    {
        string ac_model = context.getModel();
        
        // Check: starts with A or B, length 4-5 characters
        if (ac_model.StartsWith("A") || ac_model.StartsWith("B"))
        {
            if (ac_model.Length == 4 || ac_model.Length == 5)
            {
                context.setIsAircraft(true);
                Console.WriteLine(ac_model + " is an aircraft...");
            }
            else
            {
                context.setIsAircraft(false);
                Console.WriteLine(ac_model + " is not aircraft...");
            }
        }
        else
        {
            context.setIsAircraft(false);
            Console.WriteLine(ac_model + " is not aircraft...");
        }
    }
}

CheckExpression acts as a "gatekeeper," determining whether the input is a valid aircraft code.

Step 4: Create TerminalExpressions

csharp

class BrandExpression : Expression
{
    public void InterpretContext(Context context)
    {
        if (context.getIsAircraft() == true)
        {
            if (context.getFirstChar().Equals("A"))
                Console.WriteLine("Brand is Airbus");
            else if (context.getFirstChar().Equals("B"))
                Console.WriteLine("Brand is Boeing");
        }
        else
            Console.WriteLine("Brand could not be interpreted");
    }
}

class ModelExpression : Expression
{
    public void InterpretContext(Context context)
    {
        if (context.getIsAircraft() == true)
        {
            Console.WriteLine("Model is : " + context.getModel().Substring(1, 3));
        }
        else
            Console.WriteLine("Model could not be interpreted");
    }
}

class TypeExpression : Expression
{
    public void InterpretContext(Context context)
    {
        if (context.getIsAircraft() == true)
        {
            string ac_model = context.getModel();
            if (context.getLenght() == 5 && context.getLastChar().Equals("F"))
            {
                Console.WriteLine("Aircraft type is Cargo/Freighter");
            }
            else
                Console.WriteLine("Aircraft type is Passenger Transportation");
        }
        else
            Console.WriteLine("Type could not be interpreted");
    }
}

Each TerminalExpression handles a specific aspect: brand, model number, or aircraft type.

Step 5: Client Usage

csharp

class Program
{
    static void Main(string[] args)
    {
        List<Context> lstAircrafts = new List<Context>();
        List<Expression> lstExpressions = new List<Expression>();

        // List of model codes to analyze
        lstAircrafts.Add(new Context("A330"));
        lstAircrafts.Add(new Context("A330F"));
        lstAircrafts.Add(new Context("B777"));
        lstAircrafts.Add(new Context("B777F"));
        lstAircrafts.Add(new Context("TheCode")); // Invalid

        // Chain of expressions for interpretation
        lstExpressions.Add(new CheckExpression());
        lstExpressions.Add(new BrandExpression());
        lstExpressions.Add(new ModelExpression());
        lstExpressions.Add(new TypeExpression());

        // Execute
        for (int ac_index = 0; ac_index < lstAircrafts.Count; ac_index++)
        {
            for (int exp_index = 0; exp_index < lstExpressions.Count; exp_index++)
            {
                lstExpressions[exp_index].InterpretContext(lstAircrafts[ac_index]);
            }
            Console.WriteLine("-----------------------------------");
        }
        Console.ReadLine();
    }
}
```

**Output:**
```
A330 is an aircraft...
Brand is Airbus
Model is : 330
Aircraft type is Passenger Transportation
-----------------------------------
A330F is an aircraft...
Brand is Airbus
Model is : 330
Aircraft type is Cargo/Freighter
-----------------------------------
B777 is an aircraft...
Brand is Boeing
Model is : 777
Aircraft type is Passenger Transportation
-----------------------------------
...

6. Related Design Patterns

• Composite Pattern: The Abstract Syntax Tree (AST) in Interpreter is often built using the Composite structure, with parent nodes containing child nodes.

• Iterator Pattern: Commonly used to traverse the syntax tree systematically.

• Visitor Pattern: When you need to add new operations to the syntax tree without modifying Expression classes, Visitor is the ideal choice.

• Flyweight Pattern: Can be combined to share identical TerminalExpressions, optimizing memory usage.

If you found this article helpful, explore more in the Design Patterns Series to enhance your programming skills!

References

[1] Refactoring.Guru. https://refactoring.guru/design-patterns

[2] Design Patterns for Dummies, Steve Holzner, PhD

[3] Head First Design Patterns, Eric Freeman

[4] Gang of Four Design Patterns 4.0

[5] Dive into Design Patterns