Diskussion:Interpreter (Entwurfsmuster)

Sinn und Unsinn des Musters

Ich bezweifele, dass das Muster in der Praxis tatsächlich angewendet wird.

Zunächst einmal geht es in dem Muster nicht darum, dem Alltags-Benutzer eine „Programmiersprache“ zur Verfügung zu stellen und einen Interpreter mitzuliefern. Niemand wird seine Alltags-Programme durch explizite Knotenbildung in einem Baum schreiben.

Es kann also nur für den Fall gedacht sein, dass in eine Applikation fest ein bestimmtes „Programm“ eingebaut werden soll, das vom Applikationsersteller leicht zu ändern sein soll.

Für das im GoF-Buch gegebene Beispiel (Interpretieren eines festen regulären Ausdrucks) würde man das aber niemals so machen. Selbst wenn man keinen Pattern Matcher (z.B. GNU regexp) zur Verfügung hätte (der das „Programm“ in eine Zustandsmaschine umwandelt), würde man viel einfacher einen Parser schreiben, in dem jedes Nichtterminalsymbol der kontextfreien Grammatik durch eine rekursive Funktion geparst wird (die dasselbe tut wie die abstrakte Methode Interpret() des Musters). (Ich gehe davon aus, dass sich das Muster eh nur auf kontextfreie oder fast-kontextfreie Sprachen anwenden lässt, auch wenn das nirgends steht.) Das ist viel weniger aufwändig und genau so leicht erweiterbar und änderbar wie der Baum, der bei dem Muster von Hand in die Applikation kodiert werden muss.

GoF schreiben ja auch selbst, dass das Muster nur anwendbar sei, wenn die Grammatik einfach ist (dann kommt man aber mit den rekursiven Funktionen leichter zum Ziel). Bei komlexen Grammatiken solle man besser einen Parser-Generator (also Lex/Yacc) benutzen. Später behaupten sie dann aber, das Muster werde benutzt, um Compiler zu implementieren; die Smalltalk-Compiler seien damit implementiert. Das widerspricht sich, denn die Grammatik einer „echten“ Programmiersprache ist alles andere als einfach.

Ich bin also auf der Suche nach einem einfachen Beispiel aus der Praxis mit einer einfachen Grammatik, bei dem der Nutzen des Musters klar wird. --Wikiplex 09:37, 4. Sep. 2009 (CEST)

Ich hab mir das Muster jetzt mal genauer angeguckt, d.h. den Artikel hier gelesen, das entsprechende Kapitel im GoF-Book und mein (nicht soo besonders weitreichendes) Wissen über Compilerbau wieder etwas aufgefrischt. Und ich sehe durchaus Sinn in diesem Muster, wenngleich ich keine revolutionären Ansätze erkenne. Im Prinzip eigentlich straight forward OO für Sprachen (und ggf. anderes; siehe GoF:255). Aber mal der Reihe nach:

• >>> Zunächst einmal geht es in dem Muster nicht darum, dem Alltags-Benutzer eine „Programmiersprache“ zur Verfügung zu stellen und einen Interpreter mitzuliefern. <<< ==> jein. In gewisser Weise kann es schon darum gehen. Stichwort Scripting, DSLs, etc. Allerdings ist das Muster allgemeiner.
• >>> Niemand wird seine Alltags-Programme durch explizite Knotenbildung in einem Baum schreiben. <<< Das wird auch nicht behauptet. Der Syntaxbaum wird von nem Parser erzeugt, der nicht Teil des Musters ist. Siehe GoF:247 - Implementation Punkt 1
• >>> Es kann also nur für den Fall gedacht sein, dass in eine Applikation fest ein bestimmtes „Programm“ eingebaut werden soll, <<< Nein. Beispiel: Ich will n wissenschaftlichen Taschenrechner bauen. Der soll n Term entgegennehmen und den unter Berücksichtigung einer momentanen Variablenbelegung(-->Kontext) auswerten. Der Term - sagen wir mal 3*x^2+2*x+7 ist direkte Eingabe des Benutzers und nicht etwa hardgecoded.
• >>> würde man viel einfacher einen Parser schreiben <<< Das ist aber doch gar nicht Sinn und Zweck des Musters. Der Parser wird ja nicht durch den Interpreter ersetzt, sondern diesem vorgeschaltet. Parser erzeugt Syntaxbaum, Interpreter wertet den aus. Und mit diesem Muster steckt der Interpreter eben direkt im Baum selbst. Implementiert man noch einen Visitor, ist dieser quasi der Interpreter als separate Klasse. Leider ist das im GoF-Book nicht ganz so klar beschrieben. Was der Hinweis, dass man Parsergeneratoren als Alternative nehmen kann, soll, weiß ich nicht. IMHO ist das keine Alternative, sondern behandelt etwas anderes. Die GoF schreiben ja selbst "it doesn't address parsing."
• >>> Ich gehe davon aus, dass sich das Muster eh nur auf kontextfreie oder fast-kontextfreie Sprachen anwenden lässt, auch wenn das nirgends steht. <<< Richtig das geht mit kontextsensitiven Sprachen(Chomsky Typ 1) schon nicht mehr. Zumindest nicht ohne Änderungen am Pattern. Das ist aber nicht weiter tragisch, da kontextfrei ja schon so gut wie alles Interessante abdeckt. Sofern du also nicht gerade natürliche Sprachen interpretieren willst, ist das kein Problem.
• >>> Das ist viel weniger aufwändig und genau so leicht erweiterbar und änderbar wie der Baum, der bei dem Muster von Hand in die Applikation kodiert werden muss. <<< Der Punkt ist, dass man durch Subtypbildung die Grammatik erweitern kann ohne den bisherigen Code anfassen zu müssen. Will man beispielsweise in meinem obigen Taschenrechner-Beispiel trigonometrische Funktionen implementieren, schreibt man sich einfach passende Klassen. Der bestehende Code bleibt gleich. Nachteil ist allerdings, dass es sehr viele Klassen gibt.
• >>> GoF schreiben ja auch selbst, dass das Muster nur anwendbar sei, wenn die Grammatik einfach ist (dann kommt man aber mit den rekursiven Funktionen leichter zum Ziel). Bei komlexen Grammatiken solle man besser einen Parser-Generator (also Lex/Yacc) benutzen. <<< Das ist wie gesagt der Punkt, den ich auch nicht ganz verstehe. Für komplexe Grammatiken, nimmt das Problem der class bloat zu. Zudem kann der Syntaxbaum performancetechnisch problematisch sein (dem kann man mit Flyweight ggf. etwas entgegenwirken). Das wäre mein Argument für "nur einfache Sprachen". Also mathematische Terme: ja, DSLs: jjoa, Programmiersprachen: eher nicht, natürliche Sprachen: unmöglich.
• >>> Ich bin also auf der Suche nach einem einfachen Beispiel aus der Praxis <<< Ich wäre für Taschenrechner, Funktionsplotter, o.ä.

--Der Hâkawâti ✉ 14:26, 4. Sep. 2009 (CEST)

Taschenrechner ist ein gutes Beispiel. Da hast du eine Grammatik mit Regeln wie expression ::= ['+'|'-']? term (('+'|'-')term)*, um die Eingabe-Sprache festzulegen (Backus-Naur-Form). So, was wollen wir jetzt? Einen Interpreter schreiben, der Ausdrücke auswertet, die gemäß dieser Grammatik gültig sind. Dabei soll uns das Muster behilflich sein. Es soll uns behilflich sein, unseren Interpreter zu „programmieren“, ihn nachträglich abändern und erweitern zu können. (Kann auch sein, dass es das nicht ist, was wir wollen. Dann verstehe ich das Muster überhaupt nicht. Ich glaube, wir [oder zumindest ich] sind uns auch nicht einig, wann wir von Parser und wann von Parser-Generator sprechen.)

• Das hat nichts mit Scripting für den Alltags-Benutzer zu tun. Das ist, was ich mit "kein Alltags-Programm" meine. Auch nicht mit Programmen in einer DSL, höchstens um einen Interpreter für eine DSL. (Als Beispiel: kein XSLT-Sheet-„Programm“, sondern einen XSLT-Prozessor. Es geht also um eine Ebene obendrüber.)
• Um das Parsen der Eingabe kommen wir nicht herum. Ich würde dazu, im einfachsten Fall, ganz ohne Hilfsmittel, eine Funktion expression() schreiben, die die Terminalsymbole der Eingabe matcht (frisst) und dann eine weitere Funktion term() aufruft usw. Gleichzeitig werten diese Funktionen den Ausdruck auf einem internen Stack aus.
• Wenn ich ein bisschen mehr Ahnung habe oder wenn die Grammatik ein wenig komplexer wird, komme ich drauf, dass ich einen Parser-Generator wie Lex/Yacc benutzen kann, dem ich die Produktionen der Grammatik eingeben kann und der mir dann den Parser erzeugt. Das sind bei Lex/Yacc dann immer noch C-Funktionen, die ich mit eigenem Code füllen kann. Die Funktionen haben sozusagen Hooks, um eigenen Code reinzuhängen, der dann die Auswertung des Ausdrucks/Programms durchführt.
• Mit jeder der beiden Methoden habe ich jetzt einen Interpreter, dem ich deinen Ausdruck 3*x^2+2*x+7 oder irgendeinen anderen geben kann und der diesen Ausdruck dann auswertet. (Das Problem der Variablenbelegung lassen wir mal aus. Dazu wertet man halt vorher einen anderen Ausdruck aus, wie etwa x:=4.)
• Was ist jetzt mit dem Muster? Dort muss ich für jede Eingabe, die ich auswerten will, also für jedes 3*x^2+2*x+7 ein Stück C++-Code erzeugen, das mir den Objekt-Syntax-Baum zusammenstöpselt, und dann auf diesem Baum Evaluate() aufrufen (s. S. 254 in GoF). Daraus folgt, dass entweder der Parser-Generator in die Applikation eingebaut ist oder dass du halt a priori nur einen einzigen festen Ausdruck jemals auswerten willst (dessen Code du auch ohne Parser-Generator ins Programm hart kodieren kannst) oder dass du zur Laufzeit anfängst, deinen Objekt-Syntax-Baum (sprich: dein interpretiertes Programm) zu verändern.
• Außerdem kenne ich kein Parser-Generator-Tool, das so etwas leistet (was nicht heißt, dass es keins gibt). Geparst werden muss die Eingabe aber (Zeichen müssen gefressen werden), es sei denn, die Eingabe ist immer dieselbe und unterscheidet sich nur durch die Belegung der Variablen.
• Es stimmt nicht, dass du beim Erweitern um trigonometrische Funktionen einfach nur Subklassen bilden musst. Du musst diese Klassen instanziieren und die Objekte müssen in den Baum an den richtigen Stellen reingehängt werden, damit sie dein Programm ergeben.

Insgesamt bleibt mir rätselhaft, wie das Muster von Vorteil sein soll. Wenn ich es selbst beim Taschenrechner schon nicht sehe, dann... aber ich lasse mich gerne vom Gegenteil überzeugen! --Wikiplex 18:23, 4. Sep. 2009 (CEST)

Das ist irgendwie noch etwas durcheinander. Fangen wir mal mit den Begriffen an.

• Tokenizer: Ein Satz in einer Sprache als String Ausgabe: Ein Satz in einer Sprache als Liste von Tokens
• Parser: Eingabe: Satz in einer Sprache (als Tokenliste) Ausgabe: Sytaxbaum
• Parser-Generator: Eingabe: Sprache in EBNF Ausgabe: Der Code eines Parsers in einer Programmiersprache; [ich muss hier aber dazu sagen, dass ich noch keinen praktisch ausprobiert hab]
• Interpreter: Eingabe: Ein interpretierbares Etwas Ausgabe: kommt drauf an.

Interessant ist jetzt was dieses "interpretierbare Etwas" ist. Das kann ein String sein. Dann hat der Interpreter einen Tokenizer und einen Parser eingebaut. Man kann das aber auch getrennt betrachten, sodass der Interpreter nur dem Parser nachgeschaltet ist, d.h. das "interpretierbare Etwas" ist nichts anderes, als der Syntaxbaum, den der Parser ausgespuckt hat. Und genau diese Sichtweise auf den Begriff Interpreter hat das Muster. d.h. dem Muster ist es vollkommen egal woher der Syntaxbaum kommt. Das ist Aufgabe des Parsers und interessiert nicht weiter.

Zu den einzelnen Punkten:

• Richtig. Es geht z.B. um den Interpreter für eine DSL, also einer, der einen Satz in der DSL interpretiert.
• Hier vermischst du Parser und Interpreter. Betrachte das als zwei getrennte Aufgaben (Separation Of Concerns). So kannst du die Syntax ändern ohne den Parser anfassen zu müssen und umgekehrt. Der Parser kann aber in der tat so ähnlich funktionieren, wie du vorgeschlagen hast. Syntaxanalyse durch rekursiven Abstieg. Ein bisschen komplizierter ist es im Detail aber dennoch, da u.U. mehrere Möglichkeiten durchprobiert werden müssen. Aber das führt jetzt zu weit.
• Lex/Yacc hab ich zwar noch nicht benutzt, ist aber letztendlich noch mehr als ein Parsergenerator. Es wird hier ja nicht nur ein Parser generiert, sondern ein ganzer Compiler. Man kann damit auch Interpreter schreiben, letztendlich kann das Ding aber wohl noch mehr. Und ich glaub, ich versteh jetzt auch, warum ein Parser-Generator als Alternative zum Interpreter gehandelt wird. Gemeint sind wohl solche Compiler-Compiler. Danke für den Anstubser.
• Genau. Und wenn du Parser und Interpreter trennst, wird aus Ansatz 1 der Parser und aus dem Muster der Interpreter.
• Jein. Man muss wie gesagt einen Parser zusätzlich haben, der den Baum aufbaut, jedoch keinen Parser-Generator! Zudem kann man mit dem Muster auch andere Dinge machen. Der Baum muss ja nicht unbedingt einen Satz in einer Sprache sein. Ein Beispiel haben die GoF auf Seite 255 geliefert.
• -
• Um den Interpreter zu erweitern ist wirklich nur Subtypbildung nötig. Der Parser muss natürlich auch noch erweitert werden. Das ist aber nicht mehr Sache des Musters.

--Der Hâkawâti ✉ 11:57, 6. Sep. 2009 (CEST)

>>> [ich muss hier aber dazu sagen, dass ich noch keinen praktisch ausprobiert hab] <<< Probier doch mal Lex/Yacc = Flex/Bison aus. Da ist das Tutoriums-Beispiel ein Taschnerechner, kein Witz. :-)

Mir verdreht sich das Hirn; ich brauche ein konkretes Beispiel. Ich werde jetzt mal ganz konkret, indem ich die erste Produktion des Taschenrechner-Beispiels in Perl implementiere. (Der Code geht noch weiter. Er ist von mir, und ich benutze ihn in meinen XML-Kursen, um zu demonstrieren, was "Parsen" bedeutet. Das ist z.B. wichtig, wenn man SAX erklären will oder was eigentlich ein XML-Parser macht, aber egal):

# expression ::= ['+'|'-']? term (('+'|'-')term)*
# term ::= factor (('/'|'*') factor)*
# factor ::= ['0'|'1'|...|'9']+ | '('expression')'

sub expression() {
  my $neg = 0; # noch keine Negation des ersten Terms erkannt
  if($sym eq "+") {  # $sym steht immer auf dem aktuellen Eingabesymbol
    getNextSymbol(); # holt nächstes $sym
  }
  elsif($sym eq "-") {
    $neg = 1; # Negation des ersten Terms erkannt
    getNextSymbol();
  }
  term(); # rekursiver Abstieg
  if($neg) {
    push @stack, (- pop @stack); # oberstes Stack-Element negieren
  }
  while($sym eq "+" || $sym eq "-") {
    my $op = $sym;
    getNextSymbol();
    term();
    my $zahl1 = pop @stack;
    my $zahl2 = pop @stack;
    if($op eq "+") { push @stack, $zahl2 + $zahl1;}
    else           { push @stack, $zahl2 - $zahl1;}

  }
}

So, was willst du selbst als Kodierer jetzt in Einklang mit dem Muster als Code-Zeilen hinschreiben, um ein Äquivalent zu diesem Perl-Code zu erhalten? Ich nehme an, Folgendes, wenn ich auf S. 254 von GoF schaue:

LiteralExpression* plus  = new LiteralExpression("+");
LiteralExpression* minus = new LiteralExpression("-");

AlternationExpression* firstOr = new AlternationExpression(plus, minus);
NoneOrOneExpression* firstNOOE = new NoneOrOneExpression( firstOr );

RecursiveExpression* term = new RecursiveExpression(); // rules later

SequenceExpression* firstSeq = new SequenceExpression( firstNOOE, term );
// usw.

theWholeExpression.Parse();

Das ist grauenhaft. Aber du sagst ja, dass dies, da es ja bereits der (implizite) Syntaxbaum ist, eh aus dem Parser-Generator kommt und du es daher gar nicht von Hand kodieren musst. Ich kenne kein Tool, das so etwas ausspuckt. Und wo ist der Parser-Code? Versteckt in den Unterklassen von Expression und erzeugt vom Parser-Generator und abgelegt in den Methoden Parse()? Was aber musst du denn dann überhaupt noch tun? Irgendwo musst du den Code für die eigentliche Auswertung unterbringen (= den Interpreter). Dazu soll Expression eine Methode Interpret() haben, die vom Parser (der ja eingebaut worden sein muss) angestossen wird, wenn der entsprechende Ausdruck auf der Eingabe erkannt (gefressen) worden ist? Wie veränderst du jetzt Produktionen der Grammatik durch Subtypbildung? Mir verdreht sich das Hirn... --Wikiplex 12:01, 7. Sep. 2009 (CEST)

Nachtrag: Was mich vielleicht weiterbringt, ist das Beispiel in der englischen Wikipedia. Muss ich mir jetzt mal in Ruhe anschauen. --Wikiplex 13:11, 7. Sep. 2009 (CEST)

Den Nachtrag hab ich leider zu spät gesehen. Hier erstmal, das, was ich in der Zwischenzeit geschrieben hab. Das mit der englischen Wikipedia guck ich mir gleich mal an...

>>> probier doch mal Lex/Yacc = Flex/Bison aus. Da ist das Tutoriums-Beispiel ein Taschnerechner, kein Witz. :-) <<< Werd ich mir mal angucken. Steht zumindest jetzt auf meiner ToDo-Liste. Danke für den Hinweis.

Ein konkretes Beispiel. OK. Kein Problem. Hier also ein objektorientierter Ansatz dargestellt in pascalartigem Pseudocode (kann man IMHO am besten lesen), der dem Perl-Beispiel in etwa entsprechen sollte (bin kein Fan von Perl).

Das Programm besteht aus drei Komponenten: Tokenizer, Parser und Interpreter. Der Tokenizer kriegt einen String, sagen wir mal "3+5*7-42" und wandelt den in eine Liste von Tokens: (Value, 3), (Plus,), (Value, 5), (Times,), (Value, 7), (Minus,), (Value, 42) Der Parser nimmt nun die Tokens und baut daraus einen Syntaxbaum. Und der Interpreter interpretiert den und spuckt das Ergebnis aus.

Tokenizer = class
private
  s: string;
public
  constructor Create(s: string);
  function getNextToken(): Token;
end;

Parser = class
private
  tokenizer: Tokenizer;
public
  constructor Create(tokenizer: Tokenizer);
  function parse(): SyntaxTreeRoot;
end;

// der Interpreter steckt wie im Muster direkt im Syntaxbaum. Man könnte diesen über 
// das Visitor-Pattern auslagern(würde man wahrscheinlich auch so machen), der 
// Einfachheit halber lass ich das aber jetzt. Das Beispiel soll möglichst einfach sein.
// Ebenso habe ich auf "Context" verzichtet. Das einzubauen sollte aber trivial sein.

// Aufruf:
tokenizer := Tokenizer.Create('3+5*7-42'); 
// Der String kann natürlich auch aus nem Edit-Feld oder so kommen. 
//Um einen anderen String zu parsen ist also definitiv kein anderer Code nötig.

parser := Parser.Create(tokenizer);
syntaxTreeRoot := parser.parse();
return syntaxTreeRoot.interpret();

Wie Tokenizer und Parser intern realisiert sind, ist ausdrücklich *nicht* Teil des Patterns. Letztendlich kommt beim Aufruf von

syntaxTreeRoot := parser.parse();

in etwa folgendes heraus:

// Dieser Code steht nirgends, sondern soll nur verdeutlichen, was der Parser erzeugt. 
// Für ein Objektdiagramm zu malen und hier einzustellen, bin ich zu faul.

// 3+5*7-42
mul := Multiplication.Create(5, 7); // 5 * 7
add := Addition.Create(3, mul); // 3 + (5*7)
sub := Substraction(add, 42); // (3+(5*7)) - 42
syntaxTreeRoot := SyntaxTreeRoot.Create(sub);

Der Interpreter steckt nun in den Klassen Multiplication, Addition, etc.:

// <<AbstractExpression>>
Expression = abstract class
public
  function interpret: Integer;
end;

// <<TerminalExpression>>
Number = class(Expression)
private
  value: Integer;
public
  constructor Create(value: Integer);
  begin
    Self.value := value;
  end;
  function interpret: Integer;
  begin
    return value;
  end;
end;

// <<NonterminalExpression>>
Addition = class(Expression)
private
  addend1: Expression;
  addend2: Expression;
public
  constructor Create(addend1, addend2);
  begin
    Self.addend1 := addend1;
    Self.addend2 := addend2;
  end;
  function interpret();
  begin
    return addend1.interpret() + addend2.interpret();
  end;
end;

// Substraction, Multiplication, etc. analog Addition

Wie wird das nun erweitert? Angenommen wir wollten die Quadratwurzel ermöglichen.

• Tokenizer und Parser müssen erweitert werden. Das ist aber *nicht* Teil des Musters.
• Eine Klasse SquareRoot muss eingeführt werden:

// <<NonterminalExpression>>
SquareRoot = class(Expression)
private
  radicand: Expression;
public
  constructor Create(radicand);
  begin
    Self.radicand := radicand;
  end;
  function interpret();
  begin
    return sqrt(radicand.interpret());
  end;
end;

• Für den Interpreter-Teil ist das alles. Bestehender Code muss *nicht* angefasst werden. Das Interpretieren wird genau so immer noch funktionieren. Das heißt natürlich noch lange nicht, dass man Tokenizer und Parser nicht ändern muss. Was deren Design angeht, sind nochmal separate Überlegungen erforderlich. Das ist aber nicht mehr Teil des Musters.

Angenommen wir wollen nur die Syntax ändern, beispielsweise Postfix- statt geklammerter Infix-Notation einlesen:

• Tokenizer bleibt, weil sich an den Tokens ja nichts ändert
• Parser muss geändert werden, weil sich die Syntax geändert hat
• Interpreter bleibt, weil diese immer noch gleich ist

Angenommen wir wollen die Interpretation ändern, beispielsweise nicht mehr im Ring der Ganzen Zahlen, sondern in nem Restklassenring, sagen wir mal in $\mathbb {Z} /7\mathbb {Z}$, rechnen:

• Tokenizer bleibt gleich, weil sich an den Tokens nix ändert (wir könnten hier auch die Schreibweise mit den eckigen Klammern einführen)
• Parser bleibt ebenfalls. Selbst, wenn wir den Tokenizer dahingehend geändert haben, dass er die Schreibweise mit den Eckigen Klammern liest.
• Der Interpreter implementiert nun die neue Semantik. Wenn wir hier noch das Visitor-Pattern bemühen, müssen wir hier sogar auch nur eine Klasse ändern bzw. ableiten.

--Der Hâkawâti ✉ 15:16, 7. Sep. 2009 (CEST)

Beispiel in der englischen Wikipedia

Nach dem Lesen dieses Beispiels sehe ich endlich Klara... Das (oder was wir daraus machen) sollte man auch hier im Artikel bringen. Hier einige Anmerkungen:

• Klasse Evaluator sollte besser Parser heißen, denn das ist, was sie hauptsächlich tut.
• Klasse Number braucht man in dem Beispiel nicht. Die Grammatik sieht es auch nicht vor. Sonst muss der Parser auch Zahlen parsen können und einen entsprechenden Knoten in den Baum einfügen.
• Um den Interpreter zu erweitern um eine Quadrier-Funktion sqr muss lediglich eine neue Klasse gebaut werden:

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;
    }
}

• Damit in den Syntax-Baum sqr-Knoten eingebaut werden, muss der Parser erweitert werden um

	    else if(token.equals("sqr")) {
		Expression subExpression = new SqrFunction(expressionStack.pop());
                expressionStack.push( subExpression );
	    }

• "Following the interpreter pattern there is a class for each grammar rule." Das stimmt so nicht. Es muss heißen "for each non-terminal expression and for each terminal expression". Dabei entsprechen Nichtterminal-Ausdrücke Nichtterminal-Symbolen und Terminal-Ausdrücke Klassen von (!) Terminal-Symbolen. Terminal-Ausdrücke sind genau diejenigen, die keine Kinder im Syntaxbaum haben (s. S. 245 in GoF-Buch). Daher muss auch das UML-Diagramm im Artikel abgeändert werden: TerminalSymbol muss zu TerminalAusdruck werden usw.

• Ein Großteil der Komplexität ist in den Parser verlegt. Dieser baut den Syntaxbaum aus einer einfachen Beschreibung auf ("w x z - +"). Ohne den Parser dürfte es einem sehr schwer fallen, einen korrekten Baum für das Programm, das man interpretiert haben möchte, von Hand zusammenzustöpseln. Aber: Wie kommt man zu diesem Parser ohne einen geeigneten Parser-Generator? Das Interpretieren des Baumes ist einfach im Gegensatz zum Aufbauen des Baumes (=Parsen). Außerdem ist der hier gegebene Parser auch noch sehr einfach (was an der Einfachheit der UPN liegt), was suggerieren kann, dass der Parser gar kein Problem ist und en passant mitgebaut werden kann.

• Bei großen Programmen entstehen Syntax-Bäume mit abertausenden von Objekt-Knoten, die im Speicher gehalten dann interpretiert werden. Ist das praktikabel, was Speicherplatz und Geschwindigkeit angeht?

• GoF gibt als Intention des Musters: "Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language". Den Interpreter sehe ich im Muster, die Darstellung für die Grammatik nur halb: Die Klassenstruktur sagt letztlich nur, welche Terminal- und Nichtterminal-Symbole es gibt und welche Kinder ein Nichtterminal-Symbol hat, aber nicht in welcher Reihenfolge und mit welchen Alternativen! Ein Großteil der "representation for its grammar" ist in den Parser verlagert. Daher sind m.E. Interpreter und Parser nicht voneinander zu trennen, wenn das Muster seine Intention erfüllen soll.

• Wenn der Parser ganz herausgelöst ist, dann läuft es darauf hinaus, dass immer wieder dasselbe Programm interpretiert wird, u.U. mit anderen Variablenbelegungen (=anderer Kontext). Vielleicht gibt es hierfür sinnvolle Beispiele.

• Alles in allem sehe ich immer noch kein überzeugendes Beispiel, das den Einsatz des Musters rechtfertigt. Der Taschenrechner ist schön, um das Muster zu verdeutlichen, aber er rechtfertigt den Einsatz des Musters nicht.

Es bleibt spannend... --Wikiplex 15:05, 7. Sep. 2009 (CEST)

Ui, ich glaub, du hast schonmal n Großteil verstanden. Schön.

• >>> Wie kommt man zu diesem Parser ohne einen geeigneten Parser-Generator? <<< So, wie man zu jedem Parser kommt. Wentweder über einen Generator oder indem man ihn selbst schreibt. Wo ist da das Problem?
• >>> Außerdem ist der hier gegebene Parser auch noch sehr einfach (was an der Einfachheit der UPN liegt), was suggerieren kann, dass der Parser gar kein Problem ist und en passant mitgebaut werden kann. <<< Es ist einfach nicht Teil des Musters. Äpfel sind keine birnen und Parser sind keine Interpreter. Man kann natürlich Apfel-Birnen-Brei machen, trotzdem sind es unterschiedliche Früchte.
• Wenn die Syntax eben kompliziert ist, dann schreibt man sich den Parser natürlich nicht selbst, sondern man schreibt nur die Grammatik und lässt sich den Parser generieren. Das ist noch kein Argument gegen das Muster.
• >>> Bei großen Programmen entstehen Syntax-Bäume mit abertausenden von Objekt-Knoten, die im Speicher gehalten dann interpretiert werden. Ist das praktikabel, was Speicherplatz und Geschwindigkeit angeht? <<< Dafür kann man ggf. das Flyweight-Muster nehmen. Dass bei komplexen Sprachen und großen, zu interpretierenden Strings das trotzdem langsam sein kann, steht außer Frage und wird ja von den GoF auch explizit genannt. In dem Fall sollte man Compiler-Compiler in Erwägung ziehen.
• >>> den Interpreter sehe ich im Muster, die Darstellung für die Grammatik nur halb: <<< OK. Da hast du Recht. Das haben die GoF etwas missverständlich formuliert. Gemeint ist wohl nicht eine Repräsentation der Grammatik selbst, sondern eine Repräsentation des Satzes in "grammatikalischen Objekten". Is schwer zu formulieren.
• >>> Wenn der Parser ganz herausgelöst ist, dann läuft es darauf hinaus, dass immer wieder dasselbe Programm interpretiert wird, u.U. mit anderen Variablenbelegungen (=anderer Kontext). <<< Nein, eben nicht. Der Parser kann doch ganz unterschiedliche Strings parsen. Siehe mein Beispiel oben.

--Der Hâkawâti ✉ 15:41, 7. Sep. 2009 (CEST)

Habe jetzt dein Pascal-Beispiel und den Rest gelesen.

• Dein Tokenizer+Parser entspricht dem Evaluator im Java-Beispiel (der m.E. auch Parser heißen sollte). Für ein einfaches Beispiel kann man Tokenizer und Parser ruhig zusammenziehen, denke ich. Allerdings hast du ja eine sehr schöne und erweiterungsfähige Entkopplung von Tokenizer, Parser und Interpreter aufgezeigt. Vielleicht ist die Entkopplung einer der Hauptgesichtspunkte des Musters und sollte unbedingt im finalen Beispiel angedeutet werden.
• >>> Dieser Code steht nirgends, sondern soll nur verdeutlichen, was der Parser erzeugt. <<< Ja, dein Parser baut den Baum auf wie im Muster gewünscht und wie im Java-Beispiel gegeben. Statt "mul := Multiplication.Create(...)" usw. hinzuschreiben kann er ja auch einfach die Operation ausführen. Sehe ich. Ich sehe auch, dass du - im Gegensatz zu mir - das Muster verstanden hast. :-)
• Interpretieren und Erweitern gehen in deinem Beispiel genau so wie in dem Java-Beispiel. OK, gut.
• >>> Angenommen wir wollen nur die Syntax ändern, beispielsweise Postfix- statt geklammerter Infix-Notation einlesen <<< und >>> Angenommen wir wollen die Interpretation ändern <<<. Das ist sehr kreativ, gratuliere. Stimmt, damit hat man maximale Flexibilität durch Entkopplung erreicht. Nur: Ist das wirklich praxisrelevant oder eher akademisch?
• >>> Wenn wir hier noch das Visitor-Pattern bemühen, müssen wir hier sogar auch nur eine Klasse ändern bzw. ableiten. <<< Das sehe ich nicht. Du musst doch überall mod 7 rechnen. (Oder willst du nur das Endergebnis, d.h. den interpretierten Wert des obersten Objektes mudulo 7 nehmen, was ja ausreichen würde?)
• >>> So, wie man zu jedem Parser kommt. Wentweder über einen Generator oder indem man ihn selbst schreibt. Wo ist da das Problem? <<<. Grins. Hast du schon mal einen geschrieben? Versuch es doch mal für die nicht-vollständig geklammerte Infix-Notation (Grammatik im Perl-Beispiel). Du wirst sehen, dass das 97% der Zeit in Anspruch nimmt (3% für den Parser), wenn du dich nicht total verhedderst. Und das ist nur eine einfache Grammatik. Dafür sind ja eigentlich Parser-Generatoren erfunden worden. Aber die sind noch viel schwerer zu schreiben. Da ist auch noch ein Haufen Formale-Sprachen-Theorie zu beachten. (Weißt du noch, was LALR(1)-Sprachen sind?) Und jetzt schreib einen Parser-Generator für Parser, die auf dein Interpretierer-Muster passen... Das machst du nicht mal so zum Spaß.
• >>> >>> Wenn der Parser ganz herausgelöst ist, dann läuft es darauf hinaus, dass immer wieder dasselbe Programm interpretiert wird <<< <<< Damit meine ich, dass jemand auf die Idee kommen kann, dass er nur den Objekt-Syntax-Baum erhält oder dieser fest in den Code eingebaut ist, und dass dann immer wieder dieses eine Programm interpretiert wird. Könnte ja sein, dass es dafür eine Anwendung gibt. Ein fixes XSLT-Sheet z.B. Aber ich halte das für an den Haaren herbeigezogen.
• Es läuft m.E. immer wieder auf dieselben Punkte hinaus: a) Hat man einen Parser (oder Parser-Generator) zur Verfügung oder ist dieser einfach zu schreiben? b) Wenn ja: Was ist ein gutes Beispiel, das den Einsatz des Musters (mit den von dir aufgezeigten Vorteilen) rechtfertigt? Du wirst wohl niemandem die Funktionsweise der UPN oder die Auswertung vollständig geklammerter Ausdrücke mit obigen Code-Geschützen erklären und implementieren, außer vielleicht im akademischen Umfeld.
• Ich würde ja schon gerne das Java-Beispiel, eventuell erweitert um deine verschiedenen Parser/Interpretierer-Kombinationen, in den Artikel aufnehmen, jetzt, da ich das Muster verstanden habe und das Thema abschließen will. Aber in mir regt sich ständig Widerstand: "Das da ist nicht praxisnah, das ist alles akademisch. Ich würde doch niemals so einen Auswerter für arithmetische Ausdrücke bauen."
• BTW: Kennst du ein freies Tool, um UMl-Diagramme zu erzeugen? Ich möchte einige Diagramme verbessern. Ich kenne nur Umbrello, aber das erzeugt "irgendwie keine Standard-Bilder" (für es besser auszudrücken bin ich jetzt zu faul). Irgendwas für ganz einfache Diagramme ohne farbliche Schnörkel usw. Die Dagramme sollen so aussehen wie im Artikel.

--Wikiplex 15:41, 9. Sep. 2009 (CEST)

• >>> Nur: Ist das wirklich praxisrelevant oder eher akademisch? <<< Was meinst du konkret? Die Trennung von Tokenizer, Parser und Interpreter? Ich geh mal fest davon aus, dass die in diversen Compilern und Interpretern genau so gemacht wird. bzw. eigentlich noch detaillierter. Compiler transformieren den Syntaxbaum dann in eine Zwischensprache, optimieren dort und produzieren erst dann den eigentlichen Output. Oder meinst du, dass die vorgeschlagenen Änderungen akademisch wären? Also gerade beim Beispiel Formelparser fallen mir x sinnvolle Beispiele für Erweiterungen/Veränderungen ein. Oder hab ich dich ganz missverstanden?
• >>> Du musst doch überall mod 7 rechnen. <<< Richtig. Das geschähe aber alles in der Visitor-Klasse. Ich hab mir da mit dem Visitor-Pattern durch den Kopf gehen lassen. Auch, wenn es die GoF vorschlagen, Visitor wäre dazu unnötig kompliziert. Man kann den Interpreter auch straight-forward einfach so in ne separate Klasse packen. Das ganze accept-Zeug ist dazu unnötig.
• >>> Grins. Hast du schon mal einen geschrieben? <<< Schon mehrmals. Auch schon relativ "große"(einige tausend LOC). u.a. einen für ne DSL. Zugegebenermaßen aber noch keinen "richtigen", d.h. nur Quick'n'Dirty mit Stringfunktionen was zusammengefriemelt. Das hab ich jetzt aber mal nachgeholt. Ich hab mal dein Perl-Beispiel einigermaßen sauber objektorientiert in C++ umgesetzt. Mit Tokenizer, LL(1)-Parser und Interpreter-Pattern, jedoch ohne den Visitor. Ich kommentier das noch n bisschen und dann kriegst du ne Mail...
• >>> Du wirst sehen, dass das 97% der Zeit in Anspruch nimmt <<< Ich stelle ja gar nicht in Frage, dass der Parser die schwierigere Aufgabe ist. Der Interpreter beschränkt sich ja darauf, das Muster anzuwenden und n bisschen zu rechnen. Da ist nix groß dahinter. So schwer ist der Parser aber auch nicht. Das Schwierigste war, mich wieder in C++ einzufinden...
• >>> Und jetzt schreib einen Parser-Generator für Parser, die auf dein Interpretierer-Muster passen... Das machst du nicht mal so zum Spaß. <<< Das hab ich auch gar nicht vor zu machen...
• >>> Ich würde ja schon gerne das Java-Beispiel, eventuell erweitert um deine verschiedenen Parser/Interpretierer-Kombinationen, in den Artikel aufnehmen, jetzt, da ich das Muster verstanden habe und das Thema abschließen will. Aber in mir regt sich ständig Widerstand <<< Wenn dir das Beispiel mit den arithmetischen Ausdrücken nicht gefällt, dann gibt es immer noch viel allgemeiner Beispiele für Anwendungen des Musters. Die GoF bringen doch selbst schon diese Beispiele. Natürlich sind Sprachen das naheliegendste Beispiel, weil das eben gerade die Methapher des Musters ist. Beispiel: Programm zum Zusammenstellen eines Rechners. Monitor, Rechner, Drucker, CPU, RAM, GraKa, HD, ... Über das Interpreter-Muster kann der Preis berechnet werden. Ähnlich gehts auch mit Autos oder was weiß ich noch alles. Bei Autos könnte man z.B. zusätzlich noch das Gesamtgewicht bestimmen, o.ä. Die ganzen Beispiele haben aber wieder den Nachteil, dass sie sich von der Metapher des Musters entfernen und daher wohl etwas schwerer ersichtlich ist, warum es sich hierbei um das Interpreter-Muster handelt...
• >>> Kennst du ein freies Tool, um UMl-Diagramme zu erzeugen? <<< Mehrere. Und alle haben andere Macken. ;-) Um schnell einfache Modelle zusammenzubasteln nehm ich meistens Violet. Bei großen Diagrammen ist das nicht mehr so toll, aber um mal schnell jemandem ne Idee zu zeigen prima geeignet. ArgoUML ist recht umfangreich und für Klassendiagramme annehmbar. Hat aber auch noch n paar Bugs. Umbrello kenn ich auch, finde es aber kaum benutzbar. Viel zu buggy. Besonders einfach, aber leider auch buggy ist Dia. Das benutz ich für ERMs, weil ich da kein besseres Tool gefunden hab. Das Netbeans-UML-Plugin hab cih auch mal ausprobiert, bin aber nicht so begeistert davon. StarUML hab ich auf der Windows-Partition laufen und bisher nur angetestet. Sehr umfangreich, auf den ersten Blick weniger Bugs als die anderen genannten Programme, aber auch schwieriger in der Bedienung. Und läuft leider nicht unter Linux. Vielleicht bringt mich StarUML aber sogar dazu mal wieder Wine zu installieren. Das Prog sieht jedenfalls sehr vielversprechend aus. Ansonsten gibts hier noch ne Liste... --Der Hâkawâti ✉ 22:54, 10. Sep. 2009 (CEST)

Ok, ich gebe mich geschlagen und habe das Bsp. aus der englischen Wikipedia erweitert und in den Artikel aufgenommen. Beachte bitte, dass der Parser nicht vollständig ist, d.h., er meldet keinen Fehler bei unsinnigen Eingaben wie w x. Jetzt müssten wir nur noch die relevanten Teile dieser fruchtbaren Diskussion in den Artikel einfließen lassen. Ich habe aber gerade keine Lust. ;-)

• Ja, Tokenizer ist normalerweise vom Parser getrennt. Der Tokenizer wird vom Parser angestoßen. Der sagt ihm (dem Tokenizer), welche Tokens er jetzt im Eingabestrom erkennen kann, und der Tokenizer versucht das dann und meldet zurück. Ja, schick mir mal bitte deinen C++-Parser. Ich schick dir dann 2 Bison/Flex-Programme, die ich vor ein paar Jahren mal geschrieben und gerade ausgegraben habe. Eins davon ist für vollst. geklammerte Ausdrücke. :-)
• So richtig überzeugt von der Einsetzbarkeit des Musters bin ich immer noch nicht. Deine DSL für den Zusammenbau eines Computers oder Autos klingt interessant. Ob so was wirklich über das Muster abgehandelt wird? Wo GoF ein solches Beispiel bringt, sehe ich nicht. Wahrscheinlich habe ich auch einfach zu wenig Ahnung von Compilerbau. Müsste man mal einen Spezialisten fragen.
• Bezüglich des Parser-Problems habe ich mir aber Folgendes überlegt: Du kannst ja Lex/Yacc (=Bison/Flex) dazu benutzen, um einen Parser/Compiler für deine DSL zu schreiben. Die Ausgabe eines Parser-Laufes ist eine Folge von Anweisungen, die besagen, wie der Syntax-Baum mit Hilfe des Stacks aufgebaut wird. Das sind ja immer Anweisungen der Form Expression subExpression = new Minus(expressionStack.pop(), expressionStack.pop()); expressionStack.push( subExpression );, d.h., es wird immer was vom Stack genommen (A und B), ein neues Objekt X wird erzeugt, das A und B als Kinder im Baum hat, und X wird dann wieder auf den Stack geschoben. Dafür kann man sich ja ein ganz einfaches Zwischenformat ausdenken. Die Applikation, die ein DSL-Programm parsen und interpretieren soll, ruft zunächst den mit Yacc erzeugen Parser/Compiler als Subprozess auf, liest dann das erzeugte Zwischenformat, um den Syntaxbaum aufzubauen, und ruft auf diesem Baum dann interpret() auf. So kommt man um das Parser-Problem rum.
• Danke für die Hinweise zu den Tools. Werde gleich mal Violet ausprobieren.

--Wikiplex 13:00, 11. Sep. 2009 (CEST)

• >>> Deine DSL für den Zusammenbau eines Computers oder Autos klingt interessant. <<< Das hast du falsch verstanden, Es geht hier nicht um eine DSL, d.h. es gibt gar keinen Parser. Das Objekt-Geflecht wird auf andere Weise erzeugt. z.B. über Factory-Methoden (die nicht-GoF-Version).
• >>> Ob so was wirklich über das Muster abgehandelt wird? Wo GoF ein solches Beispiel bringt, sehe ich nicht. <<< GoF:255: "Given a similar class hierachy for representing automotive part assemblies [...]". Ob man so etwas als Interpreter-Pattern betrachtet, ist eine Frage des Standpunktes. Man kann ein Auto als Satz in einer Sprache über Autoteilen betrachten. Man kann auch einfach sagen, das ist nur ein Kompositum mit einer über der Hierarchie definierten Methode. Ein Muster besteht eben nicht nur aus einer Ansammlung von Klassen und deren Beziehungen, sondern gibt auch eine Metapher, ein Denkmuster, für deren Verwendung vor. --Der Hâkawâti ✉ 23:16, 14. Sep. 2009 (CEST)

UML-Diagramm und eineltender Text: "Ausdruck" statt "Symbol"

Ich würde gerne das im Artikel verwendete UML-Diagramm gegen das folgende austauschen:

(So wie es auch in GoF aussieht, eingedeutscht.)

Die Begründung wurde schon in obiger Diskussion gegeben: >>> Dabei entsprechen Nichtterminal-Ausdrücke Nichtterminal-Symbolen und Terminal-Ausdrücke Klassen von (!) Terminal-Symbolen. Terminal-Ausdrücke sind genau diejenigen, die keine Kinder im Syntaxbaum haben (s. S. 245 in GoF-Buch). Daher muss auch das UML-Diagramm im Artikel abgeändert werden: TerminalSymbol muss zu TerminalAusdruck werden usw. <<<

Es muss dann auch der Anfang des Artikels ein wenig umgeschrieben werden. Aktuelles Diagramm und Text suggerieren, dass für jedes Nichtterminal-Symbol eine Klasse eingeführt wird; das stimmt nicht, nur für Nichtterminal-Ausdrücke (die für viele Nichtterminal-Symbole stehen können.)

Es wird wird immer von Symbolen gesprochen, es sollte aber von Ausdrücken ausgegangen werden (wie im GoF-Buch). Zu Symbolen kommt man durch die Annahme, dass die Grammatik immer eine kontextfreie ist. Das mag für alle praktischen Anwendungen so sein, ist aber nicht explizit vom Muster vorgeschrieben. Dort wird nur gesagt, wie sich ein (abstrakter) Ausdruck durch Unterausdrücke interpretieren lässt.

Jemand was dagegen? --Wikiplex 14:49, 11. Sep. 2009 (CEST)

Was das nun mit Kontextfreiheit zu tun hat, verstehe ich nicht ganz, aber ich finde auch, dass Ausdruck hier richtiger wäre als Symbol. --Der Hâkawâti ✉ 23:19, 14. Sep. 2009 (CEST)

Das war auch etwas wirr von mir. :-) Ich habe mich gefragt, warum im aktuellen Artikel und Bild immer von "Symbolen" gesprochen wird. Meine Annahme ist, dass der Autor eben eine (kontextfreie) Grammatik vor sich sah (da kommen ja die Begriffe Nichtterminalsymbol und Terminalsymbol her). Das Muster ist aber ein wenig allgemeiner, denn es passt auf alle Ausdrücke, die irgendwie aus Unterausdrücken zusammengesetzt sind, nicht nur auf solche, bei denen, wie in einer Grammatik, die Reihenfolge der (möglichen) Unterausdrücke vorgegeben ist. Wenn ich Zeit finde, ersetze ich Bild und Text. Grüße! --Wikiplex 09:35, 15. Sep. 2009 (CEST)

Zusatz: erledigt. --Wikiplex 10:25, 15. Sep. 2009 (CEST)

Ich bezweifle, dass das Beispiel allgemeiner ist., d.h. ich bezweifle, dass man das Muster auch für nicht-kontextfreie Grammatiken verwenden kann. Zumindest nicht ohne das Muster wesentlich zu verändern. Oder verstehe ich dich falsch? - Der Hâkawâti ✉ 10:37, 15. Sep. 2009 (CEST)

Du hast doch oben das Beispiel mit dem Programm zum Zusammenstellen eines Rechners oder der Preisberechnung für ein Auto gebracht. Da kommt es auf die Reihenfolge nicht an, sondern nur auf die Inklusion, auf das Enthaltensein einer Menge in einer Obermenge. Dazu braucht man keine kontextfreie Grammatik. Das Muster ist aber dazu geeignet, solche Mengenhierarchien zu "interpretieren" (auszuwerten). --Wikiplex 10:57, 17. Sep. 2009 (CEST)