Interpreter pattern

Approach in computer programming

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Interpreter pattern" – news · newspapers · books · scholar · JSTOR (November 2008) (Learn how and when to remove this message)

|

In computer programming, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a language. The basic idea is to have a class for each symbol (terminal or nonterminal) in a specialized computer language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate (interpret) the sentence for a client.[1]: 243 See also Composite pattern.

## Overview

[edit]

The Interpreter [2] design pattern is one of the twenty-three well-known GoF design patterns that describe how to solve recurring design problems to design flexible and reusable object-oriented software, that is, objects that are easier to implement, change, test, and reuse.

### What problems can the Interpreter design pattern solve?

[edit]

Source:[3]

* A grammar for a simple language should be defined
* so that sentences in the language can be interpreted.

When a problem occurs very often, it could be considered to represent it as a sentence in a simple language (Domain Specific Languages) so that an interpreter can solve the problem by interpreting the sentence.

For example, when many different or complex search expressions must be specified. Implementing (hard-wiring) them directly into a class is inflexible because it commits the class to particular expressions and makes it impossible to specify new expressions or change existing ones independently from (without having to change) the class.

### What solution does the Interpreter design pattern describe?

[edit]

* Define a grammar for a simple language by defining an `Expression` class hierarchy and implementing an `interpret()` operation.
* Represent a sentence in the language by an abstract syntax tree (AST) made up of `Expression` instances.
* Interpret a sentence by calling `interpret()` on the AST.

The expression objects are composed recursively into a composite/tree structure that is called abstract syntax tree (see Composite pattern).
The Interpreter pattern doesn't describe how to build an abstract syntax tree. This can be done either manually by a client or automatically by a parser.

See also the UML class and object diagram below.

## Uses

[edit]

* Specialized database query languages such as SQL.
* Specialized computer languages that are often used to describe communication protocols.
* Most general-purpose computer languages actually incorporate several specialized languages[citation needed].

## Structure

[edit]

### UML class and object diagram

[edit]

A sample UML class and object diagram for the Interpreter design pattern.[4]

In the above UML class diagram, the `Client` class refers to the common `AbstractExpression` interface for interpreting an expression `interpret(context)`.
The `TerminalExpression` class has no children and interprets an expression directly.
The `NonTerminalExpression` class maintains a container of child expressions (`expressions`) and forwards interpret requests to these `expressions`.

The object collaboration diagram shows the run-time interactions: The `Client` object sends an interpret request to the abstract syntax tree. The request is forwarded to (performed on) all objects downwards the tree structure.
The `NonTerminalExpression` objects (`ntExpr1,ntExpr2`) forward the request to their child expressions.
The `TerminalExpression` objects (`tExpr1,tExpr2,…`) perform the interpretation directly.

### UML class diagram

[edit]

## Example

[edit]

This C++11 implementation is based on the pre C++98 sample code in the book.

#include <iostream>
#include <map>
#include <cstring>

class Context;

class BooleanExp {
public:
BooleanExp() = default;
virtual ~BooleanExp() = default;
virtual bool evaluate(Context&) = 0;
virtual BooleanExp* replace(const char*, BooleanExp&) = 0;
virtual BooleanExp* copy() const = 0;

class VariableExp;

class Context {
public:
Context() :m() {}
bool lookup(const VariableExp* key) { return m.at(key); }
void assign(VariableExp* key, bool value) { m[key] = value; }
private:
std::map<const VariableExp*, bool> m;

class VariableExp : public BooleanExp {
public:
VariableExp(const char* name_) :name(nullptr) {
name = strdup(name_);

virtual ~VariableExp() = default;
virtual bool evaluate(Context& aContext) {
return aContext.lookup(this);

virtual BooleanExp* replace( const char* name_, BooleanExp& exp ) {
if (0 == strcmp(name_, name)) {
return exp.copy();
} else {
return new VariableExp(name);

virtual BooleanExp* copy() const {
return new VariableExp(name);

VariableExp(const VariableExp&) = delete; // rule of three
VariableExp& operator=(const VariableExp&) = delete;
private:
char* name;

class AndExp : public BooleanExp {
public:
AndExp(BooleanExp* op1, BooleanExp* op2)
:operand1(nullptr), operand2(nullptr) {
operand1 = op1;
operand2 = op2;

virtual ~AndExp() = default;
virtual bool evaluate(Context& aContext) {
return operand1->evaluate(aContext) && operand2->evaluate(aContext);

virtual BooleanExp* replace(const char* name_, BooleanExp& exp) {
return new AndExp(
operand1->replace(name_, exp),
operand2->replace(name_, exp)

virtual BooleanExp* copy() const {
return new AndExp(operand1->copy(), operand2->copy());

AndExp(const AndExp&) = delete; // rule of three
AndExp& operator=(const AndExp&) = delete;
private:
BooleanExp* operand1;
BooleanExp* operand2;

int main() {
BooleanExp* expression;
Context context;
VariableExp* x = new VariableExp("X");
VariableExp* y = new VariableExp("Y");
expression = new AndExp(x, y);

context.assign(x, false);
context.assign(y, true);
bool result = expression->evaluate(context);
std::cout << result << '\n';

context.assign(x, true);
context.assign(y, true);
result = expression->evaluate(context);
std::cout << result << '\n';

The program output is:

## See also

[edit]

* Backus–Naur form
* Combinatory logic in computing
* Design Patterns
* Domain-specific language
* Interpreter (computing)

## References

[edit]

1. ^ Gamma, Erich; Helm, Richard; Johnson, Ralph; Vlissides, John (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley. ISBN 0-201-63361-2.
2. ^ Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (1994). Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley. pp. 243ff. ISBN 0-201-63361-2.`{{cite book}}`: CS1 maint: multiple names: authors list (link)
3. ^ "The Interpreter design pattern - Problem, Solution, and Applicability". w3sDesign.com. Retrieved 2017-08-12.
4. ^ "The Interpreter design pattern - Structure and Collaboration". w3sDesign.com. Retrieved 2017-08-12.

## External links

[edit]

The Wikibook Computer Science Design Patterns has a page on the topic of: Interpreter

* Interpreter implementation in Ruby
* Interpreter implementation in C++
* SourceMaking tutorial
* Interpreter pattern description from the Portland Pattern Repository

* v
* t
* e

Software design patterns

Gang of Four
patterns|

| Creational|

* Abstract factory
* Builder
* Factory method
* Prototype
* Singleton

|

Structural|

* Adapter
* Bridge
* Composite
* Decorator
* Facade
* Flyweight
* Proxy

Behavioral|

* Chain of responsibility
* Command
* Interpreter
* Iterator
* Mediator
* Memento
* Observer
* State
* Strategy
* Template method
* Visitor

Concurrency
patterns|

* Active object
* Balking
* Binding properties
* Double-checked locking
* Event-based asynchronous
* Guarded suspension
* Join
* Lock
* Monitor
* Proactor
* Reactor
* Read–write lock
* Scheduler
* Scheduled-task pattern
* Semaphore
* Thread pool
* Thread-local storage

Architectural
patterns|

* Front controller
* Interceptor
* MVC
* MVP
* MVVM
* ADR
* ECS
* n-tier
* Specification
* Publish–subscribe
* Naked objects
* Service locator
* Active record
* Identity map
* Data access object
* Data transfer object
* Inversion of control
* Model 2
* Broker

Other
patterns|

* Blackboard
* Business delegate
* Composite entity
* Dependency injection
* Guard clause
* Intercepting filter
* Lazy loading
* Mock object
* Null object
* Object pool
* Servant
* Twin
* Type tunnel
* Method chaining
* Delegation

Books|

* Design Patterns
* Enterprise Integration Patterns

People|

* Christopher Alexander
* Erich Gamma
* Ralph Johnson
* John Vlissides
* Grady Booch
* Kent Beck
* Ward Cunningham
* Martin Fowler
* Robert Martin
* Jim Coplien
* Douglas Schmidt
* Linda Rising

Communities|

* The Hillside Group
* Portland Pattern Repository

See also|

* Anti-pattern
* Architectural pattern

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template