8 - Interpreter

Previously in the series, I have analysed a relatively simple and straightforward design pattern — Facade. In this article, I will analyse and implement a pattern, which has a similar structure to Composite but is used in a different context and for a different purpose — the Interpreter design pattern.

Table of Contents

• What is the Interpreter design pattern?
• Analysis
• Implementation
• Your Contribution

What is the Interpreter design pattern?

The Interpreter is a behavioural design pattern, which intention in the GoF book is described like this:

Given a language, define a representation for its grammar along with an inter­preter that uses the representation to interpret sentences in the language.

The main idea behind this is that a language is a set of valid sentences. Each of those sentences can be constructed by following a set of grammar rules defining the language. Sometimes the program which needs to interpret those sentences process a lot of repeated occurrences of similar requests that are a combination of a set of grammar rules, but all of these requests are composed using the same grammar rules. For instance, arithmetic expressions could be different and provide a different result (addition, subtraction, multiplication, division), but all of them are constructed of the same basic rules defining the language of arithmetic expressions.

So where the Interpreter design pattern plays its role? Well, this pattern could represent each of those basic rules as a separate class representing a separate grammar rule and by making a hierarchy of these rules you can define any sentence of that particular language. Also, having a separate class for every grammar rule makes it easy to change the grammar itself and maintain it, adding new kinds of interpret operations becomes an easy task, too.

It could sound complicated at first, but let’s move to the analysis and implementation parts where you can find some specific examples of the Interpreter design pattern and its usage.

Analysis

The class diagram below shows the general structure of the Interpreter design pattern:

• AbstractExpression — declares an abstract interpret() operation that is common to all nodes in the abstract syntax tree;
• TerminalExpression — implement an interpret() operation associated with terminal symbols in the grammar;
• NonterminalExpression — implement an interpret() operation for nonterminal symbols in the grammar. This operation typically calls itself recursively on the variables representing other expressions (grammar rules);
• Context — contains the global information of the interpreter which is shared among the expression instances;
• Client — builds an abstract syntax tree representing a particular sentence in the language that the grammar defines and invokes the interpret() operation.

Composite vs Interpreter

The Interpreter design pattern’s similarity to the Composite is evident. The Interpreter itself uses the Composite design pattern to build and represent a sentence in a simple language as a tree. But that’s all — the Composite pattern is only used to define the static properties of the system, to define the structure (it is a structural design pattern, right?), but the Interpreter represents the language itself, defines the behaviour, has some additional logic to interpret each entity in the tree, shares the same context between them — that’s the main difference and the reason why this pattern is considered as a behavioural design pattern.

Applicability

The usage of the Interpreter design pattern is quite dedicated to interpreting languages in which statements could be represented as an abstract syntax tree. Usually, this kind of languages has a simple grammar defined in specific rules e.g. RegEx (regular expression), bar codes, mathematical expressions/notations, etc. Also, the Interpreter design pattern should be used when the efficiency is not a critical concern since building and parsing expression trees for the bigger sentences of the language is relatively inefficient (e.g. comparing to parsers and interpreters which translate the expression tree to the other form before interpreting it).

Implementation

Let’s say you want to create a program that parses and solves the postfix mathematical expression. A postfix a.k.a. Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands e.g. 69+242-*+ which is equivalent to 6+9+(4-2)*2.

The postfix expression contains two types of symbols — numbers and operators. Talking in PEG terms, numbers are terminal symbols and operators are nonterminal symbols.

The evaluation of the postfix expression could be implemented using the stack data structure by processing the expression from left to right:

for each token in the postfix expression:
  if token is an operator:
    operand_2 ← pop from the stack
    operand_1 ← pop from the stack
    result ← evaluate token with operand_1 and operand_2
    push result back onto the stack
  else if token is an operand:
    push token onto the stack
result ← pop from the stack

Let’s change this algorithm a little bit. By processing the postfix expression from left to right and instead of evaluating the expression on finding the operator’s symbol, we could build an expression tree and evaluate it later. This kind of expression tree would look like this:

Terminal expressions (numbers) do not have any children in the expression tree, but each nonterminal expression (arithmetic operation) has two children — terminal and/or nonterminal expressions. To evaluate this kind of expression tree the program just has to start from the root, recursively execute (interpret) each expression and accumulate the final result.

I expect you have already noticed that the Interpreter design pattern fits the problem of implementing the postfix mathematical expression parser just perfectly. So let’s jump straight to the implementation details!

Class diagram

The class diagram below shows the implementation of the Interpreter design pattern:

IExpression defines a common interface for both terminal and nonterminal expressions which implement the interpret() method:

• Number — a terminal expression for numbers;
• Multiply — a nonterminal expression of the multiplication operation;
• Subtract — a nonterminal expression of the subtraction operation;
• Add — a nonterminal expression of the addition operation.

All of the nonterminal expressions contain left and right expressions of type IExpression which are used in the interpret() method to calculate the result of the arithmetic operation.

ExpressionContext class contains the solution steps of the postfix expression and is used by the ExpressionSection widget to retrieve those steps and the IExpression interface implementing classes to add a specific solution step to the context.

ExpressionSection uses the ExpressionHelpers class to build the expression tree of the postfix expression and the ExpressionContext to retrieve the solution steps of the specific postfix expression.

IExpression

An interface that defines the interpret() method to be implemented by the terminal and nonterminal expression classes. Dart language does not support the interface as a class type, so we define an interface by creating an abstract class and providing a method header (name, return type, parameters) without the default implementation.

ExpressionContext

A class to define the context which stores the solution steps of the postfix expression and is used by the Client and classes implementing the IExpression interface.

ExpressionHelpers

A helper class is used by the Client to build the expression tree from the provided postfix expression input.

Number

A terminal expression class to define the number in postfix expression.

Nonterminal expressions

Add defines the addition operation and adds the addition solution step to the ExpressionContext. The result of this operation — left and right expressions’ sum.

Subtract defines the subtraction operation and adds the subtraction solution step to the ExpressionContext. The result of this operation — left and right expressions’ difference.

Multiply defines the multiplication operation and adds the multiplication solution step to the ExpressionContext. The result of this operation — left and right expressions’ product.

Example

First of all, a markdown file is prepared and provided as a pattern’s description:

InterpreterExample widget contains the list of postfix expressions. For each expression in the postfixExpressions list, an ExpressionSection widget is created and a specific postfix expression is passed to it using the constructor.

ExpressionSection uses the provided postfixExpression and builds its expression tree using the ExpressionHelpers class on the ‘Solve’ button click.

The buildExpressionTree() method returns a single nonterminal expression of type IExpression which is used to calculate the final result of the provided postfix expression. The widget/method itself does not care about the specific implementation of the nonterminal expression, it only calls the interpret() method on the expression to get the final result. Also, a list of solution steps to get the final result are retrieved from the ExpressionContext using the getSolutionSteps() method and presented in the UI.

The final result of the Interpreter design pattern’s implementation looks like this:

As you can see in the example, every postfix expression is evaluated on a ‘Solve’ button click, all the solution steps are provided to the UI along with the final result.

All of the code changes for the Interpreter design pattern and its example implementation could be found here.

Your Contribution

💖 or 🦄 this article to show your support and motivate me to write better!
💬 Leave a response to this article by providing your insights, comments or wishes for the next topic.
📢 Share this article with your friends, colleagues in social media.
➕ Follow me on dev.to or any other social media platform.
⭐ Star the Github repository.