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
/ **
* 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
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.