Interpreter pattern

The Interpreter ( English interpreter pattern ) is a design pattern in the field of software development and belongs to the category of behavior (english behavioral patterns ). The pattern is one of the so-called GoF patterns.

The interpreter pattern defines a representation of the grammar of a language and the ability to interpret the language sentences.

Use

If similar problems must be solved often enough, it is often useful to describe the problem in a simple language. Examples of such a problem is the evaluation of regular expressions, and the calculation of logical or mathematical formulas.

UML diagram

Components

The abstract class Abstract design pressure prescribes a method Interpret () that are implemented by all derived, concrete classes must and evaluates the corresponding expression.

A TerminalerAusdruck stands for an expression that has no sub-expression, that is, for a fixed value within a molded according to the grammatical sentence. For example, number is a numerical value within a mathematical formula.

A non-terminal expression is an expression that consists of sub-expressions, such as addition or multiplication, which both require two operands as sub-expressions. A subexpression can be a TerminalerAusdruck and a non-terminal expression.

For the to-interpret a sentence parse tree from non-terminal and terminal expressions are constructed according to the grammar. This can be done by an external parser or the clients themselves. The client evaluates this syntax tree by calling the method Interpret () for the highest expression.

In the context of the specific values ​​of the terminal expressions are encapsulated with which the sentence is to be interpreted, for example, the assignment of variables.

Benefits

The grammar can be easily changed by this design pattern or extended, the same sentence or expression by changing the context to be interpreted again and again to new ways.

Disadvantages

Complex grammars and very large sets of the interpreter pattern is unsuitable, since the class hierarchy is too large and the efficiency suffers at high syntax trees. If complex grammars are processed, parser generators are better suited. Large syntax trees are typically converted to other structures and processes, for example with the aid of the state machine.

Example

In the inverse Polish Notation (RPN ) expressions are given according to the following grammar:

Expression :: = plus | minus | variable | number plus :: = expression expression ' ' minus :: = expression expression '-' variable :: = 'a ' | ' b ' | ' c' | ... | 'z' number :: = '-'? ('0 '| '1 ' | '2 ' | ... | '9 ')

Examples of expressions that match this grammar are

1 1 a 2 3 - 5 4 - a b

The interpreter looks for each terminal - expression and for each non-terminal expression in front of a concrete class that implements a common interface. This interface requires that each class can interpret a to her matching phrase in a context needs. The context here is the assignment of the variables:

* import java.util. ;   / **   * Interface for all expression types   * / Able Express interface {      / **       * Interprets the passed variable       * @ Param VARIABLES       * @ Return Result       * /      public int interpret (final String, HashMap Integer> VARIABLES ); }   / **   * Class for a non -terminal expression   * / Plus class implements Express Able {      / ** Left operation * /      Private Express Able leftOperand = null;      / ** Right operation * /      Private Express Able RightOperand = null;        / **       * Constructor       * @ Param LEFT Left expression       * @ Param RIGHT Right expression       * /      public Plus (final Express Able LEFT, final Express Able RIGHT) {          leftOperand = LEFT;          RightOperand = RIGHT;      }        / * (Non- Javadoc )       * @ See # interpreter.Expressable interpreter ( java.util.HashMap )       * /      @ Override      public int interpret (final String, HashMap Integer> VARIABLES ) {          return leftOperand.interpret ( VARIABLES )                  RightOperand.interpret ( VARIABLES );      }        / **       * Converts the content to a readable string by overloading the Object       * Method.       * @ Return String representation       * /      public String toString () {          return leftOperand.toString () " "                  RightOperand.toString ();      } }   / **   * Class for a non -terminal expression   * / Minus class implements Express Able {      / ** Left operation * /      Private Express Able leftOperand = null;      / ** Right operation * /      Private Express Able RightOperand = null;        / **       * Constructor       * @ Param LEFT Left expression       * @ Param RIGHT Right expression       * /      public minus (final Express Able LEFT,              final Express Able RIGHT) {          leftOperand = LEFT;          RightOperand = RIGHT;      }        / * (Non- Javadoc )       * @ See # interpreter.Expressable interpreter ( java.util.HashMap )       * /      @ Override      public int interpret (final String, HashMap Integer> VARIABLES ) {          return leftOperand.interpret ( VARIABLES )                  - RightOperand.interpret ( VARIABLES );      } }   / **   * Class for a terminal expression   * / class variable implements Express Able {      / ** Variable name * /      private String name = null;        / **       * Constructor       * @ Param NAME       * /      public variable ( final String NAME) {          name = NAME;      }        / * (Non- Javadoc )       * @ See # interpreter.Expressable interpreter ( java.util.HashMap )       * /      @ Override      public int interpret (final String, HashMap Integer> VARIABLES ) {          VARIABLES.get return ( name);      } }   / **   * Class for a terminal expression   * / class Number implements Express Able {      / ** Number object * /      private int number = 0;        / **       * Constructor       * @ Param NUMBER       * /      public Number ( final int NUMBER) {          number = NUMBER;      }        / * (Non- Javadoc )       * @ See # interpreter.Expressable interpreter ( java.util.HashMap )       * /      @ Override      public int interpret (final String, HashMap Integer> VARIABLES ) {          return number;      } } The interpreter does not deal with the parsing of the original expression and the generation of the syntax tree that matches the expression. For completeness, here the implementation of a simple parser. It is incomplete in the sense that he does not reject some non- valid expressions! ( But all valid expressions to parse correctly and generates the syntax tree for it. )

Class Parser {      / **       * Parser method       * @ Param EXPRESSION       * @ Return Parsed result       * /      static public Express Able ParseExpression ( final String EXPRESSION ) {          Express Able syntaxTree = null;          Pattern number pattern = Pattern.compile ("[ -] \ \ d ? ");            Stack stack = new Stack expression ();          for ( String token: EXPRESSION.split ( "")) {              if ( token.equals (" " )) {                  Express Able subexpression = new Plus ( expressionStack.pop ()                          expressionStack.pop ());                  expressionStack.push ( subexpression);              }              else if ( token.equals ("-" )) {                  Express Able subexpression = new Minus ( expressionStack.pop ()                          expressionStack.pop ());                  expressionStack.push ( subexpression);              }              else if ( numberPattern.matcher ( token ). matches () ) {                  expressionStack.push ( new Number ( Integer.parseInt ( token.trim () )));              }              else expressionStack.push (new variable ( token ) );          }            syntaxTree = expressionStack.pop ();            return syntaxTree;      } }   / **   * Test class   * / public class InterpreterExample {      / **       * Test method for the interpreter       * @ Param ARGUMENTS       * /      public static void main ( final String [ ] ARGUMENTS ) {          final String EXPRESSION = "w x z - -2 ";          final HashMap String, Integer> VARIABLES =                  new HashMap String, Integer> ();            VARIABLES.put ( "w", 5);          VARIABLES.put ( "x " 33);          VARIABLES.put ("Z", 10);            final Express Able TREE = Parser.parseExpression ( EXPRESSION );            System.out.println ( TREE.interpret ( VARIABLES ) );      } } It's now pretty easy to extend the grammar and interpret the extended expressions. To install a squaring function sqr ( a unary operator ), a new class must be introduced:

/ **   * Class for a non -terminal expression   * / SqrFunction class implements Express Able {      / ** Operand * /      Express Able operand = null;        / **       * Constructor       * @ Param OPERAND       * /      public SqrFunction (final Express Able OPERAND ) {          operand = OPERAND;      }        / * (Non- Javadoc )       * @ See # interpreter.Expressable interpreter ( java.util.HashMap )       * /      @ Override      public int interpret (final HashMap VARIABLES ) {          int tmp = operand.interpret ( VARIABLES );          return tmp * tmp;      } } The (incomplete ) parser can be extended as follows to parse even sqr Terms:

Else if ( token.equals ( " sqr " )) {          Express Able subexpression = new SqrFunction ( expressionStack.pop ());                  expressionStack.push ( subexpression);       } Related design patterns

The syntax tree is described by a compound.

A Visitor can encapsulate the behavior of all non-terminal symbols in order to reduce the number of classes and / or to make the behavior of these interchangeable.

Using the Flyweight terminal symbols can be shared.

An iterator can be used to traverse the syntax tree.

415112
de