Editing Interpreter pattern

{{Short description|Approach in computer programming}}
{{Refimprove|date=November 2008}}

In [[computer programming]], the '''interpreter pattern''' is a [[design pattern (computer science)|design pattern]] that specifies how to evaluate sentences in a language.
The basic idea is to have a [[Class (computer science)|class]] for each symbol ([[Terminal symbol|terminal]] or [[Nonterminal symbol|nonterminal]]) in a [[Domain specific languages|specialized computer language]]. The [[abstract syntax tree|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.<ref name=GoF>{{cite book |author1=Gamma, Erich |author2-link=Richard Helm |author2=Helm, Richard |author3=Johnson, Ralph |author4=Vlissides, John |
 title=Design Patterns: Elements of Reusable Object-Oriented Software |
 publisher=Addison-Wesley |
 year=1994 |
 isbn=0-201-63361-2
 |author1-link=Erich Gamma |title-link=Design Patterns }}</ref>{{rp|243}} See also [[Composite pattern]].

==Overview==
The Interpreter
<ref name="GoF2">{{cite book|author=Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides|title=Design Patterns: Elements of Reusable Object-Oriented Software|year=1994|publisher=Addison Wesley|isbn=0-201-63361-2|pages=[https://archive.org/details/designpatternsel00gamm/page/243 243ff]|url-access=registration|url=https://archive.org/details/designpatternsel00gamm/page/243}}</ref>
design pattern is one of the twenty-three well-known 
''[[Design Patterns|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?===

Source:<ref>{{cite web|title=The Interpreter design pattern - Problem, Solution, and Applicability|url=http://w3sdesign.com/?gr=b03&ugr=proble|website=w3sDesign.com|access-date=2017-08-12}}</ref>

* A [[Backus-Naur form|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 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?===
* Define a grammar for a simple language by defining an <code>Expression</code> class hierarchy and implementing an <code>interpret()</code> operation.
* Represent a sentence in the language by an abstract syntax tree (AST) made up of <code>Expression</code> instances.
* Interpret a sentence by calling <code>interpret()</code> on the AST.

The expression objects are composed recursively into a composite/tree structure that is called
''abstract syntax tree'' (see [[Composite pattern]]).
<br>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 ==
* 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|reason=Need reference to a language doing this|date=September 2022}}.

== Structure ==
=== UML class and object diagram ===
[[File:w3sDesign Interpreter Design Pattern UML.jpg|frame|none|A sample UML class and object diagram for the Interpreter design pattern.<ref>{{cite web|title=The Interpreter design pattern - Structure and Collaboration|url=http://w3sdesign.com/?gr=b03&ugr=struct|website=w3sDesign.com|access-date=2017-08-12}}</ref>]]

In the above [[Unified Modeling Language|UML]] [[class diagram]], the <code>Client</code> class refers to the common <code>AbstractExpression</code> interface for interpreting an expression
<code>interpret(context)</code>.
<br>
The <code>TerminalExpression</code> class has no children and interprets an expression directly.
<br>
The <code>NonTerminalExpression</code> class maintains a container of child expressions
(<code>expressions</code>) and forwards interpret requests
to these <code>expressions</code>.
<br>

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

=== UML class diagram ===
[[Image:Interpreter_UML_class_diagram.svg]]

== Example ==
<!-- Wikipedia is not a list of examples. Do not add examples from favorite programming languages here; this page exists to explain the design pattern, not to show how it interacts with subtleties of every language extant. Feel free to add examples at: http://en.wikibooks.org/wiki/Computer_Science_Design_Patterns/Interpreter -->

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

<syntaxhighlight lang="c++">
#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';
}
</syntaxhighlight>

The program output is:

<syntaxhighlight lang="c++">
0
1
</syntaxhighlight>

== See also ==
* [[Backus–Naur form]]
* [[Combinator#Combinatory logic in computing|Combinatory logic in computing]]
* ''[[Design Patterns]]''
* [[Domain-specific language]]
* [[Interpreter (computing)]]

== References ==
<references/>

== External links ==
{{wikibooks|Computer Science Design Patterns|Interpreter}}
* [http://lukaszwrobel.pl/blog/interpreter-design-pattern Interpreter implementation] in [[Ruby (programming language)|Ruby]]
* [https://github.com/jamesdhutton/Interpreter Interpreter implementation] in [[C++]]
* [http://sourcemaking.com/design_patterns/interpreter SourceMaking tutorial]
* [http://c2.com/cgi/wiki?InterpreterPattern Interpreter pattern description from the Portland Pattern Repository]

{{Design Patterns Patterns}}

[[Category:Articles with example C Sharp code]]
[[Category:Articles with example Java code]]
[[Category:Software design patterns]]