Implement the Interpreter Pattern for DSLs in C

The Interpreter design pattern defines a grammatical representation for a domain-specific language (DSL) and provides an interpreter to evaluate sentences within that language. This article demonstrates how to implement this pattern in C# to parse and evaluate custom expressions. By breaking down language rules into terminal and non-terminal expression classes arranged in an Abstract Syntax Tree (AST), you can build lightweight, extensible domain-specific evaluation engines.

Core Components of the Pattern

The pattern relies on four primary components:

  1. Context: Holds global state, variables, or environment information needed during interpretation.
  2. Abstract Expression (IExpression): Declares the Interpret operation common to all nodes in the syntax tree.
  3. Terminal Expression: Implements the interpretation for primitive elements (e.g., numbers, variable identifiers) that terminate an AST branch.
  4. Non-Terminal Expression: Implements interpretation for composite grammar rules (e.g., addition, logical AND) and recursively evaluates child expressions.

1. Define the Context and Expression Interface

The context contains runtime variables that expressions can query, and the interface enforces the interpretation contract.

using System.Collections.Generic;

public class Context
{
    private readonly Dictionary<string, int> _variables = new();

    public void SetVariable(string name, int value) => _variables[name] = value;
    
    public int GetVariable(string name)
    {
        if (_variables.TryGetValue(name, out var value))
        {
            return value;
        }
        throw new KeyNotFoundException($"Variable '{name}' not defined.");
    }
}

public interface IExpression
{
    int Interpret(Context context);
}

2. Implement Terminal Expressions

Terminal expressions do not contain sub-expressions. They return immediate values or resolve variables from the context.

// Evaluates literal integer values
public class NumberExpression : IExpression
{
    private readonly int _value;

    public NumberExpression(int value)
    {
        _value = value;
    }

    public int Interpret(Context context) => _value;
}

// Evaluates variable references using the context
public class VariableExpression : IExpression
{
    private readonly string _name;

    public VariableExpression(string name)
    {
        _name = name;
    }

    public int Interpret(Context context) => context.GetVariable(_name);
}

3. Implement Non-Terminal Expressions

Non-terminal expressions represent grammar operations. They hold references to child IExpression instances and combine their results.

// Addition Operation
public class AddExpression : IExpression
{
    private readonly IExpression _left;
    private readonly IExpression _right;

    public AddExpression(IExpression left, IExpression right)
    {
        _left = left;
        _right = right;
    }

    public int Interpret(Context context) => _left.Interpret(context) + _right.Interpret(context);
}

// Multiplication Operation
public class MultiplyExpression : IExpression
{
    private readonly IExpression _left;
    private readonly IExpression _right;

    public MultiplyExpression(IExpression left, IExpression right)
    {
        _left = left;
        _right = right;
    }

    public int Interpret(Context context) => _left.Interpret(context) * _right.Interpret(context);
}

4. Construct and Interpret the Syntax Tree

To evaluate a domain expression such as (x + 5) * y, manually assemble the AST nodes or construct them using a simple parser.

using System;

class Program
{
    static void Main()
    {
        // Setup context with dynamic values
        var context = new Context();
        context.SetVariable("x", 10);
        context.SetVariable("y", 2);

        // Represent DSL syntax: (x + 5) * y
        IExpression expression = new MultiplyExpression(
            new AddExpression(
                new VariableExpression("x"),
                new NumberExpression(5)
            ),
            new VariableExpression("y")
        );

        // Interpret the AST
        int result = expression.Interpret(context);
        Console.WriteLine($"Result: {result}"); // Output: 30
    }
}

When to Use This Pattern

  • Simple Grammar: The Interpreter pattern works best when the grammar of your DSL is relatively simple and stable.
  • Extensibility: Adding new operations (such as SubtractExpression or DivideExpression) is straightforward and requires creating a new class without modifying existing AST nodes.
  • Trade-off: For complex grammars with many production rules, maintaining dozens of expression classes can become unwieldy. In those scenarios, dedicated parser generators like ANTLR or parser combinators are preferred.