Interpreter Pattern

Introduction

The Interpreter pattern is one of the behavioral design patterns that provides a way to evaluate language grammar or expressions. It defines a grammatical representation for a language and an interpreter to interpret sentences in the language. This pattern is particularly useful when you need to parse and execute simple languages or domain-specific languages (DSLs).

Concept

The Interpreter pattern involves creating an abstract syntax tree (AST) that represents the grammar of the language. Each node in the AST corresponds to a rule in the grammar, and each leaf node represents a terminal symbol. The interpreter then traverses this tree to evaluate the expression.

Key Components

1. Abstract Expression: Declares an interface for executing parts of the sentence represented by the abstract syntax tree.
2. Terminal Expression: Implements an Abstract Expression corresponding to terminal symbols in the grammar (i.e., leaf nodes).
3. Nonterminal Expression: Implements an Abstract Expression corresponding to nonterminal symbols in the grammar (i.e., internal nodes with children).
4. Context: Contains information that's global to the interpreter.
5. Client: Builds or creates an abstract syntax tree representing a sentence in the language.

Examples

Let's walk through a simple example where we create an interpreter for a basic arithmetic expression language that supports addition and subtraction.

Step 1: Define the Abstract Expression

First, we define an interface for our expressions:

1interface Expression {
2interpret(context: Context): number;
3}

Step 2: Implement Terminal Expressions

Next, we implement terminal expressions for numbers:

1class NumberExpression implements Expression {
2private value: number;
3 
4constructor(value: string) {
5  this.value = parseInt(value);
6}
7 
8interpret(context: Context): number {
9  return this.value;
10}
11}

Step 3: Implement Nonterminal Expressions

Then, we implement nonterminal expressions for addition and subtraction:

1class AddExpression implements Expression {
2private left: Expression;
3private right: Expression;
4 
5constructor(left: Expression, right: Expression) {
6  this.left = left;
7  this.right = right;
8}
9 
10interpret(context: Context): number {
11  return this.left.interpret(context) + this.right.interpret(context);
12}
13}
14 
15class SubtractExpression implements Expression {
16private left: Expression;
17private right: Expression;
18 
19constructor(left: Expression, right: Expression) {
20  this.left = left;
21  this.right = right;
22}
23 
24interpret(context: Context): number {
25  return this.left.interpret(context) - this.right.interpret(context);
26}
27}

Step 4: Define the Context

The context can be a simple object that holds any global information needed during interpretation:

1class Context {
2// This could hold variables or other state
3}

Step 5: Build and Interpret the Expression Tree

Finally, we build an expression tree and interpret it:

1function parseExpression(input: string): Expression {
2const tokens = input.split(' ');
3let left: Expression;
4let right: Expression;
5 
6if (tokens.length === 3) {
7  left = new NumberExpression(tokens[0]);
8  right = new NumberExpression(tokens[2]);
9 
10  switch (tokens[1]) {
11    case '+':
12      return new AddExpression(left, right);
13    case '-':
14      return new SubtractExpression(left, right);
15    default:
16      throw new Error('Unsupported operation');
17  }
18}
19 
20throw new Error('Invalid input');
21}
22 
23const expression = parseExpression("3 + 5");
24const context = new Context();
25console.log(expression.interpret(context)); // Output: 8

Explanation

In this example, we define a simple language that supports addition and subtraction. We create an abstract syntax tree where each node is an instance of Expression. The NumberExpression class represents terminal symbols (numbers), while AddExpression and SubtractExpression represent nonterminal symbols (operations). The interpret method is recursively called on the nodes to evaluate the expression.

What's Next?

In the next section, we will explore the Iterator Pattern, which provides a way to traverse a collection of objects without exposing its underlying representation. This pattern is useful for accessing elements in a sequence without knowing the structure of the sequence.

Stay tuned!