Interpreter (design pattern)
The Interpreter (English interpreter pattern ) is a design pattern in the field of software development and belongs to the category of behavioral patterns (English behavioral patterns ). The pattern is one of the so-called GoF patterns .
The interpreter pattern defines a representation for the grammar of a language and the ability to interpret sentences of that language.
use
When similar problems need to be solved often enough, it is often useful to describe the problem in simple language. Examples of such a problem are evaluating regular expressions and computing logical or mathematical formulas .
UML diagram
Components
The abstract class AbstrakterAusdruckprescribes a method Interpretiere()that must be implemented by all derived, concrete classes and that evaluates the corresponding expression.
A TerminalerAusdruckstands for an expression that has no sub-expression, i.e. H. for a fixed value within a sentence formed according to the grammar. For example, number stands for a number value within a mathematical formula.
A NonterminalerAusdruckstands for an expression that consists of subexpressions, for example addition or multiplication , both of which require two operands as subexpressions. A subexpression can be both a TerminalerAusdruckand a non-terminal expression.
For the sentence to be interpreted, a syntax tree is constructed from non-terminal and terminal expressions in accordance with the grammar . This can be done by an external parser or by the client itself. The client evaluates this syntax tree by Interpretiere()calling the method for the top expression .
The specific values of the terminal expressions with which the sentence is to be interpreted are encapsulated in the context , e.g. B. the assignment of variables.
advantages
The grammar can easily be changed or expanded through this design pattern, the same sentence or phrase can be interpreted in new ways again and again by changing the context.
disadvantage
The interpreter pattern is unsuitable for complex grammars and very large sentences because the class hierarchy becomes too large and the efficiency of large syntax trees suffers. If complex grammars are to be processed, parser generators are better suited. Large syntax trees are usually converted into other structures and processed, for example, with the help of state machines .
example
In reverse Polish notation (UPN) , 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 + +
For each terminal expression and for each non-terminal expression, the interpreter provides a concrete class that implements a common interface. This interface stipulates that the respective class must be able to interpret a suitable expression in a context. The context here is the assignment of the variables:
import java.util.*;
/**
* Interface for all expression types
*/
interface IExpressable {
/**
* Interprets the passed variables
* @param variables
* @return Result
*/
public int interpret(final HashMap<String, Integer> variables);
}
/**
* Class for a non-terminal expression
*/
class Plus implements IExpressable {
/** Left operation */
private IExpressable leftOperand = null;
/** Right operation */
private IExpressable rightOperand = null;
/**
* Constructor
* @param left Left expression
* @param right Right expression
*/
public Plus(final IExpressable left, final IExpressable right) {
leftOperand = left;
rightOperand = right;
}
/* (non-Javadoc)
* @see interpreter.IExpressable#interpret(java.util.HashMap)
*/
@Override
public int interpret(final HashMap<String, 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
*/
class Minus implements IExpressable {
/** Left operation */
private IExpressable leftOperand = null;
/** Right operation */
private IExpressable rightOperand = null;
/**
* Constructor
* @param left Left expression
* @param right Right expression
*/
public Minus(final IExpressable left,
final IExpressable right) {
leftOperand = left;
rightOperand = right;
}
/* (non-Javadoc)
* @see interpreter.IExpressable#interpret(java.util.HashMap)
*/
@Override
public int interpret(final HashMap<String, Integer> variables) {
return leftOperand.interpret(variables)
- rightOperand.interpret(variables);
}
}
/**
* Class for a terminal expression
*/
class Variable implements IExpressable {
/** Variable name */
private String name = null;
/**
* Constructor
* @param name
*/
public Variable(final String name) {
this.name = name;
}
/* (non-Javadoc)
* @see interpreter.IExpressable#interpret(java.util.HashMap)
*/
@Override
public int interpret(final HashMap<String, Integer> variables) {
return variables.get(name);
}
}
/**
* Class for a terminal expression
*/
class Number implements IExpressable {
/** Number object */
private int number = 0;
/**
* Constructor
* @param number
*/
public Number(final int number) {
this.number = number;
}
/* (non-Javadoc)
* @see interpreter.IExpressable#interpret(java.util.HashMap)
*/
@Override
public int interpret(final HashMap<String, Integer> variables) {
return number;
}
}
The interpreter is not concerned with parsing the original expression and creating the syntax tree that corresponds to the expression. For the sake of completeness, here is the implementation of a simple parser. It is incomplete in the sense that it does not discard some invalid expressions ! (But it parses all valid expressions correctly and creates the syntax tree for them.)
class Parser {
/**
* Parser method
* @param expression
* @return Parsed result
*/
static public IExpressable parseExpression(final String expression) {
IExpressable syntaxTree = null;
Pattern numberPattern = Pattern.compile("[+-]?\\d+");
Stack<IExpressable> expressionStack = new Stack<IExpressable>();
for (String token : expression.split(" ")) {
if (token.equals("+")) {
IExpressable subExpression = new Plus(expressionStack.pop(),
expressionStack.pop());
expressionStack.push(subExpression);
} else if (token.equals("-")) {
IExpressable 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 IExpressable tree = Parser.parseExpression(expression);
System.out.println(tree.interpret(variables));
}
}
It is now fairly easy to expand the grammar and interpret the expanded expressions. To sqradd a squaring function (a unary operator), just introduce a new class:
/**
* Class for a non-terminal expression
*/
class SqrFunction implements IExpressable {
/** Operand */
IExpressable operand = null;
/**
* Constructor
* @param operand
*/
public SqrFunction(final IExpressable operand) {
this.operand = operand;
}
/* (non-Javadoc)
* @see interpreter.IExpressable#interpret(java.util.HashMap)
*/
@Override
public int interpret(final HashMap<String,Integer> variables) {
int tmp = operand.interpret(variables);
return tmp*tmp;
}
}
The (incomplete) parser can be extended as sqrfollows to also parse expressions:
else if(token.equals("sqr")) {
IExpressable subExpression = new SqrFunction(expressionStack.pop());
expressionStack.push( subExpression );
}
Related design patterns
The syntax tree is described by a compound word.
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.
With the help of the Flyweight , terminal symbols can be shared.
An iterator can be used to traverse the syntax tree.
Individual evidence
- ↑ Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides : Design pattern . 5th edition. Addison-Wesley , 1996, ISBN 3-8273-1862-9 , pp. 319 .
- ↑ Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides : Design Patterns: Elements of Reusable Object-Oriented Software . Addison-Wesley, 1995, ISBN 0-201-63361-2 , p. 247