Interpreter (Entwurfsmuster)
Der Interpreter (englisch interpreter pattern) ist ein Entwurfsmuster aus dem Bereich der Softwareentwicklung und gehört zu der Kategorie der Verhaltensmuster (englisch behavioural patterns). Das Muster ist eines der sogenannten GoF-Muster.
Das Interpretermuster definiert eine Repräsentation für die Grammatik einer Sprache und die Möglichkeit, Sätze dieser Sprache zu interpretieren.[1]
Verwendung
BearbeitenWenn ähnliche Probleme oft genug gelöst werden müssen, ist es häufig sinnvoll, das Problem mit einer einfachen Sprache zu beschreiben. Beispiele für ein solches Problem sind das Auswerten von regulären Ausdrücken und die Berechnung von logischen oder mathematischen Formeln.
UML-Diagramm
Bearbeiten
Bestandteile
BearbeitenDie abstrakte Klasse AbstrakterAusdruck schreibt eine Methode Interpretiere() vor, die von allen abgeleiteten, konkreten Klassen implementiert werden muss und den entsprechenden Ausdruck auswertet.
Ein TerminalerAusdruck steht für einen Ausdruck, der keinen Unterausdruck hat, d. h. für einen festen Wert innerhalb eines gemäß der Grammatik geformten Satzes. Z. B. steht Zahl für einen Zahlenwert innerhalb einer mathematischen Formel.
Ein NonterminalerAusdruck steht für einen Ausdruck, der aus Unterausdrücken besteht, zum Beispiel Addition oder Multiplikation, die beide zwei Operanden als Unterausdrücke benötigen. Ein Unterausdruck kann sowohl ein TerminalerAusdruck als auch ein NichtterminalAusdruck sein.
Für den zu interpretierenden Satz wird gemäß der Grammatik ein Syntaxbaum aus Nichtterminal- und Terminalausdrücken aufgebaut. Dies kann durch einen externen Parser oder den Klienten selbst geschehen. Der Klient wertet diesen Syntaxbaum aus, indem er für den obersten Ausdruck die Methode Interpretiere() aufruft.
Im Kontext werden die konkreten Werte der Terminalausdrücke gekapselt, mit denen der Satz interpretiert werden soll, z. B. die Belegung von Variablen.
Vorteile
BearbeitenDie Grammatik kann durch dieses Entwurfsmuster leicht geändert oder erweitert, derselbe Satz oder Ausdruck durch Ändern des Kontextes immer wieder auf neue Art und Weise interpretiert werden.
Nachteile
BearbeitenFür komplexe Grammatiken und sehr große Sätze ist das Interpretermuster ungeeignet, da die Klassenhierarchie zu groß wird und die Effizienz bei großen Syntaxbäumen leidet. Sollen komplexe Grammatiken verarbeitet werden, eignet sich Rekursiver Abstieg oder Parsergenerator besser. Große Syntaxbäume werden üblicherweise in andere Strukturen konvertiert und zum Beispiel mit Hilfe von Zustandsautomaten bearbeitet.
Beispiele
BearbeitenDiese C++11 Implementierung basiert auf dem vor C++98 Beispielcode im Buch Entwurfsmuster.
#include <iostream>
#include <map>
#include <cstring>
class Kontext;
class BoolscherAusdruck {
public:
BoolscherAusdruck() = default;
virtual ~BoolscherAusdruck() = default;
virtual bool werteAus(Kontext&) = 0;
virtual BoolscherAusdruck* ersetze(const char*, BoolscherAusdruck&) = 0;
virtual BoolscherAusdruck* kopiere() const = 0;
};
class VariablenAusdruck;
class Kontext {
public:
Kontext() :m() {}
bool lookup(const VariablenAusdruck* key) { return m.at(key); }
void weiseZu(const VariablenAusdruck* key, bool value) { m[key] = value; }
private:
std::map<const VariablenAusdruck*, bool> m;
};
class VariablenAusdruck : public BoolscherAusdruck {
public:
VariablenAusdruck(const char* name_) :name(nullptr) {
name = strdup(name_);
}
virtual ~VariablenAusdruck() = default;
virtual bool werteAus(Kontext& einKontext) {
return einKontext.lookup(this);
}
virtual BoolscherAusdruck* ersetze(const char* name_, BoolscherAusdruck& ausdruck) {
if (0 == strcmp(name_, name)) {
return ausdruck.kopiere();
} else {
return new VariablenAusdruck(name);
}
}
virtual BoolscherAusdruck* kopiere() const {
return new VariablenAusdruck(name);
}
VariablenAusdruck(const VariablenAusdruck&) = delete; // Dreierregel
VariablenAusdruck& operator=(const VariablenAusdruck&) = delete;
private:
char* name;
};
class UndAusdruck : public BoolscherAusdruck {
public:
UndAusdruck(BoolscherAusdruck* op1, BoolscherAusdruck* op2)
:operand1(nullptr), operand2(nullptr) {
operand1 = op1;
operand2 = op2;
}
virtual ~UndAusdruck() = default;
virtual bool werteAus(Kontext& einKontext) {
return operand1->werteAus(einKontext) && operand2->werteAus(einKontext);
}
virtual BoolscherAusdruck* ersetze(const char* name_, BoolscherAusdruck& ausdruck) {
return new UndAusdruck(operand1->ersetze(name_, ausdruck),
operand2->ersetze(name_, ausdruck));
}
virtual BoolscherAusdruck* kopiere() const {
return new UndAusdruck(operand1->kopiere(), operand2->kopiere());
}
UndAusdruck(const UndAusdruck&) = delete; // Dreierregel
UndAusdruck& operator=(const UndAusdruck&) = delete;
private:
BoolscherAusdruck* operand1;
BoolscherAusdruck* operand2;
};
int main() {
BoolscherAusdruck* ausdruck;
Kontext kontext;
VariablenAusdruck* x = new VariablenAusdruck("X");
VariablenAusdruck* y = new VariablenAusdruck("Y");
ausdruck = new UndAusdruck(x, y);
kontext.weiseZu(x, false);
kontext.weiseZu(y, true);
bool resultat = ausdruck->werteAus(kontext);
std::cout << resultat << '\n';
kontext.weiseZu(x, true);
kontext.weiseZu(y, true);
resultat = ausdruck->werteAus(kontext);
std::cout << resultat << '\n';
}
Die Programmausgabe ist:
0
1
In der umgekehrten polnischen Notation (UPN) sind Ausdrücke gemäß folgender Grammatik gegeben:
expression ::= plus | minus | variable | number
plus ::= expression expression '+'
minus ::= expression expression '-'
variable ::= 'a' | 'b' | 'c' | ... | 'z'
number ::= '-'? ('0' | '1' | '2' | ... | '9')+
Beispiele für Ausdrücke, die dieser Grammatik entsprechen, sind
1 1 + a 2 + 3 - 5 4 - a b + +
Der Interpreter sieht für jeden Terminal-Ausdruck und für jeden Nichtterminal-Ausdruck eine konkrete Klasse vor, die eine gemeinsame Schnittstelle implementiert. Diese Schnittstelle schreibt vor, dass die jeweilige Klasse einen zu ihr passenden Ausdruck in einem Kontext interpretieren können muss. Der Kontext ist hier die Belegung der Variablen:
import java.util.*;
/**
* Interface for all expression types
*/
interface IExpressable {
/**
* Interprets the passed variables
* @param variables
* @return Result
*/
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;
}
}
Der Interpreter beschäftigt sich nicht mit dem Parsen des ursprünglichen Ausdrucks und dem Erzeugen des Syntax-Baumes, der dem Ausdruck entspricht.[2] Der Vollständigkeit halber hier die Implementierung eines einfachen Parsers. Er ist unvollständig in dem Sinne, dass er manche nicht-gültige Ausdrücke nicht verwirft! (Aber alle gültigen Ausdrücke parst er korrekt und erzeugt den Syntax-Baum dafür.)
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));
}
}
Es ist nun recht einfach, die Grammatik zu erweitern und die erweiterten Ausdrücke zu interpretieren. Um eine Quadrier-Funktion sqr einzubauen (einen unären Operator), muss nur eine neue Klasse eingeführt werden:
/**
* 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;
}
}
Der (unvollständige) Parser kann folgendermaßen erweitert werden, um auch sqr-Ausdrücke zu parsen:
else if(token.equals("sqr")) {
IExpressable subExpression = new SqrFunction(expressionStack.pop());
expressionStack.push( subExpression );
}
Verwandte Entwurfsmuster
BearbeitenDer Syntaxbaum wird durch ein Kompositum beschrieben.
Ein Visitor kann das Verhalten aller Nichtterminalsymbole in sich kapseln, um die Anzahl der Klassen zu verringern und/oder das Verhalten dieser austauschbar zu gestalten.
Mit Hilfe des Flyweight können Terminalsymbole gemeinsam genutzt werden.
Ein Iterator kann verwendet werden, um den Syntaxbaum zu traversieren.
Einzelnachweise
Bearbeiten- ↑ Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides: Entwurfsmuster. 5. Auflage. Addison-Wesley, 1996, ISBN 3-8273-1862-9, S. 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, S. 247