Interpreter (Entwurfsmuster)

Der Interpreter (englisch: Interpreter) ist ein Entwurfsmuster aus dem Bereich der Softwareentwicklung und gehört zu der Kategorie der Verhaltensmuster (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.

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

UML-Diagramm

Bestandteile

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

Ein TerminalAusdruck 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 TerminalAusdruck als auch ein NichtterminalAusdruck sein.

Für den Satz, der interpretiert werden soll, 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

Die Grammatik kann durch dieses Entwurfsmuster leicht geändert oder erweitert werden. Derselbe Satz oder Ausdruck kann 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 Klassenhierachie 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

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 + +


Das Interpreter-Muster sieht für jeden Terminal-Ausdruck und für jeden Nichtterminal-Ausdruck eine konkrete Klasse vor, die ein gemeinsames Interface implementiert. Dieses Interface 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.*;
 
// Abstract expression 
interface Expression {
    public int interpret(HashMap<String,Integer> variables);
}
 
// Nonterminal expression 
class Plus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Plus(Expression left, Expression right) { 
        leftOperand  = left; 
        rightOperand = right;
    }
    public int interpret(HashMap<String,Integer> variables)  { 
        return leftOperand.interpret(variables) + rightOperand.interpret(variables);
    }
}
 
// Nonterminal expression 
class Minus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Minus(Expression left, Expression right) { 
        leftOperand  = left; 
        rightOperand = right;
    }
    public int interpret(HashMap<String,Integer> variables)  { 
        return leftOperand.interpret(variables) - rightOperand.interpret(variables);
    }
}
 
// Terminal expression
class Variable implements Expression {
    private String name;
    public Variable(String name)       { this.name = name; }
    public int interpret(HashMap<String,Integer> variables)  { 
        return variables.get(name); 
    }
}
 
// Terminal expression
class Number implements Expression {
    private int number;
    public Number(int number)       { this.number = number; }
    public int interpret(HashMap<String,Integer> variables)  { return number; }
}

Das Interpreter-Muster beschäftigt sich nicht mit dem Parsen des ursprünglichen Ausdrucks und dem Erzeugen des Syntax-Baumes, der dem Ausdruck entspricht.^[1] 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 {
    static public Expression parseExpression(String expression) {
        Expression syntaxTree;
        Pattern numberPattern = Pattern.compile("[+-]?\\d+");
 
        Stack<Expression> expressionStack = new Stack<Expression>();
        for (String token : expression.split(" ")) {
            if  (token.equals("+")) {
                Expression subExpression = new Plus(expressionStack.pop(), expressionStack.pop());
                expressionStack.push( subExpression );
            }
            else if (token.equals("-")) {
                Expression 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;
    }
}
 
public class InterpreterExample {
    public static void main(String[] args) {
        String expression = "w x z - + -2 +";
        HashMap<String,Integer> variables = new HashMap<String,Integer>();
        variables.put("w", 5);
        variables.put("x", 3);
        variables.put("z", 10);
        Expression syntaxTree = Parser.parseExpression( expression );
        int result = syntaxTree.interpret(variables);
        System.out.println(result);
    }
}

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:

// Nonterminal expression
class SqrFunction implements Expression {
    Expression operand;
    public SqrFunction(Expression op)  {
        operand = op;
    }
    public int interpret(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")) {
                Expression subExpression = new SqrFunction(expressionStack.pop());
                expressionStack.push( subExpression );
         }

Verwandte Entwurfsmuster

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.

Referenzen

1. ↑ 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

Entwurfsmuster der Viererbande

Erzeugungsmuster:  Abstrakte Fabrik | Singleton | Builder | Fabrikmethode | Prototyp

Strukturmuster:  Adapter | Brücke | Decorator | Fassade | Flyweight | Kompositum | Stellvertreter

Verhaltensmuster:  Observer | Visitor | Interpreter | Iterator | Kommando | Memento | Schablonenmethode | Strategie | Vermittler | Zustand | Zuständigkeitskette

(Klassenmuster sind kursiv dargestellt)