Interpreter (Entwurfsmuster)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 mathematischen Formeln.

UML-Diagramm[Bearbeiten]

UML-Klassendiagramm

Bestandteile[Bearbeiten]

Die 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 NichtterminalAusdruck 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[Bearbeiten]

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[Bearbeiten]

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, eignen sich Parsergeneratoren besser. Große Syntaxbäume werden üblicherweise in andere Strukturen konvertiert und zum Beispiel mit Hilfe von Zustandsautomaten bearbeitet.

Beispiel[Bearbeiten]

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 Expressable {
    /**
     * 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 Expressable {
    /** Left operation */
    private Expressable leftOperand = null;
    /** Right operation */
    private Expressable rightOperand = null;
 
    /**
     * Constructor
     * @param LEFT Left expression
     * @param RIGHT Right expression
     */
    public Plus(final Expressable LEFT, final Expressable RIGHT) { 
        leftOperand  = LEFT; 
        rightOperand = RIGHT;
    }
 
    /* (non-Javadoc)
     * @see interpreter.Expressable#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 Expressable {
    /** Left operation */
    private Expressable leftOperand = null;
    /** Right operation */
    private Expressable rightOperand = null;
 
    /**
     * Constructor
     * @param LEFT Left expression
     * @param RIGHT Right expression
     */
    public Minus(final Expressable LEFT,
            final Expressable RIGHT) { 
        leftOperand  = LEFT; 
        rightOperand = RIGHT;
    }
 
    /* (non-Javadoc)
     * @see interpreter.Expressable#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 Expressable {
    /** Variable name */
    private String name = null;
 
    /**
     * Constructor
     * @param NAME
     */
    public Variable(final String NAME) {
        name = NAME;
    }
 
    /* (non-Javadoc)
     * @see interpreter.Expressable#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 Expressable {
    /** Number object */
    private int number = 0;
 
    /**
     * Constructor
     * @param NUMBER
     */
    public Number(final int NUMBER) {
        number = NUMBER;
    }
 
    /* (non-Javadoc)
     * @see interpreter.Expressable#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 Expressable parseExpression(final String EXPRESSION) {
        Expressable syntaxTree = null;
        Pattern numberPattern = Pattern.compile("[+-]?\\d+");
 
        Stack<Expressable> expressionStack = new Stack<Expressable>();
        for (String token : EXPRESSION.split(" ")) {
            if  (token.equals("+")) {
                Expressable subExpression = new Plus(expressionStack.pop(),
                        expressionStack.pop());
                expressionStack.push(subExpression);
            }
            else if (token.equals("-")) {
                Expressable 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 Expressable 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 Expressable {
    /** Operand */
    Expressable operand = null;
 
    /**
     * Constructor
     * @param OPERAND
     */
    public SqrFunction(final Expressable OPERAND)  {
        operand = OPERAND;
    }
 
    /* (non-Javadoc)
     * @see interpreter.Expressable#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")) {
        Expressable subExpression = new SqrFunction(expressionStack.pop());
                expressionStack.push( subExpression );
     }

Verwandte Entwurfsmuster[Bearbeiten]

Der 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]

  1.  Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides: Entwurfsmuster. 5 Auflage. Addison-Wesley, 1996, ISBN 3-8273-1862-9, S. 319.
  2. Gamma, Erich; Richard Helm, Ralph Johnson, and John Vlissides (1995). Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley. pp. 247 ISBN 0-201-63361-2