imported>AndreAdrian: /* Nachteile */ recursive decent parser dazu

2023-05-09T11:20:19Z

Nachteile: recursive decent parser dazu

Neue Seite

Der '''Interpreter''' (englisch {{lang|en|''interpreter pattern''}}) ist ein [[Entwurfsmuster]] aus dem Bereich der [[Softwareentwicklung]] und gehört zu der Kategorie der [[Verhaltensmuster (Software)|Verhaltensmuster]] (englisch {{lang|en|''behavioural patterns''}}). Das Muster ist eines der sogenannten [[Viererbande (Softwareentwicklung)|GoF-Muster]].

Das Interpretermuster definiert eine Repräsentation für die Grammatik einer Sprache und die Möglichkeit, Sätze dieser Sprache zu interpretieren.<ref>{{Literatur |Autor=[[Erich Gamma]], [[Richard Helm]], [[Ralph Johnson]], [[John Vlissides]] |Titel=Entwurfsmuster |Auflage=5 |Verlag=[[Addison-Wesley]] |Ort= |Datum=1996 |ISBN=3-8273-1862-9 |Seiten=319}}</ref>

== Verwendung ==
Wenn ä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 [[Mathematische Formel|mathematischen Formeln]].

== UML-Diagramm ==
[[Datei:Interpreter UML class diagram de.svg|ohne|UML-Klassendiagramm]]

== Bestandteile ==
Die abstrakte Klasse <code>AbstrakterAusdruck</code> schreibt eine Methode <code>Interpretiere()</code> vor, die von allen abgeleiteten, konkreten Klassen implementiert werden muss und den entsprechenden Ausdruck auswertet.

Ein <code>TerminalerAusdruck</code> 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 <code>NonterminalerAusdruck</code> 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 <code>TerminalerAusdruck</code> 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 <code>Interpretiere()</code> 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 ==
Die 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 ==
Fü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 [[Zustandsautomat]]en bearbeitet.

== Beispiele ==
Diese C++11 Implementierung basiert auf dem vor C++98 Beispielcode im Buch Entwurfsmuster.

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

Die Programmausgabe ist:

<syntaxhighlight lang="cpp">
0
1
</syntaxhighlight>

In der [[Umgekehrte polnische Notation|umgekehrten polnischen Notation (UPN)]] sind Ausdrücke gemäß folgender Grammatik gegeben:

<pre>
expression ::= plus | minus | variable | number
plus ::= expression expression '+'
minus ::= expression expression '-'
variable ::= 'a' | 'b' | 'c' | ... | 'z'
number ::= '-'? ('0' | '1' | '2' | ... | '9')+
</pre>

Beispiele für Ausdrücke, die dieser Grammatik entsprechen, sind

<pre>
1 1 +
a 2 + 3 -
5 4 - a b + +
</pre>

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:

<syntaxhighlight lang="java">
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;
}
}
</syntaxhighlight>

Der Interpreter beschäftigt sich nicht mit dem Parsen des ursprünglichen Ausdrucks und dem Erzeugen des Syntax-Baumes, der dem Ausdruck entspricht.<ref>[[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</ref> 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.)

<syntaxhighlight lang="Java">
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));
}
}
</syntaxhighlight>

Es ist nun recht einfach, die Grammatik zu erweitern und die erweiterten Ausdrücke zu interpretieren. Um eine Quadrier-Funktion <code>sqr</code> einzubauen (einen unären Operator), muss nur eine neue Klasse eingeführt werden:

<syntaxhighlight lang="Java">
/**
* 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;
}
}
</syntaxhighlight>

Der (unvollständige) Parser kann folgendermaßen erweitert werden, um auch <code>sqr</code>-Ausdrücke zu parsen:

<syntaxhighlight lang="Java">
else if(token.equals("sqr")) {
IExpressable subExpression = new SqrFunction(expressionStack.pop());
expressionStack.push( subExpression );
}
</syntaxhighlight>

== Verwandte Entwurfsmuster ==
Der Syntaxbaum wird durch ein [[Kompositum (Entwurfsmuster)|Kompositum]] beschrieben.

Ein [[Besucher (Entwurfsmuster)|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 [[Fliegengewicht (Entwurfsmuster)|Flyweight]] können Terminalsymbole gemeinsam genutzt werden.

Ein [[Iterator (Entwurfsmuster)|Iterator]] kann verwendet werden, um den Syntaxbaum zu traversieren.

== Einzelnachweise ==
<references />

{{Navigationsleiste Entwurfsmuster}}

[[Kategorie:Verhaltensmuster (Software)]]
[[Kategorie:Viererbande-Entwurfsmuster]]

Interpreter (Entwurfsmuster) - Versionsgeschichte

imported>AndreAdrian: /* Nachteile */ recursive decent parser dazu