3. Interpreter-Pattern aus Backus-Naur erstellen

Interpreter-Pattern aus Backus-Naur erstellen

  • D

    Also ich bin ja manchmal ein wenig Begriffsstutzig- trotzdem glaub ich, hab ich das Interpreter-Pattern jetzt verstanden. Ich ging von falschen Voraussetzungen aus- wodurch ich jeden erdenklichen Schluß ziehen konnte- nur nicht den Richtigen.

    Der Interpreterbaum beschreibt ja die komplette Grammatik und man jagt seine Token da durch, um am Ende hoffentlich sein Ergebnis zu bekommen.

    Hier mal ein Beispiel für eine Grammatik:

    ausdruck ::= literal | and | or | not | '(' ausdruck ')' .
and      ::= ausdruck '&' ausdruck .
or       ::= ausdruck '|' ausdruck .
not      ::= '!' ausdruck .

literal ::= ('A' | 'B' | ... | 'Z' | zahl)* .
zahl    ::= ['-'] (ziffer)* ['.' (ziffer)*] .
ziffer  ::=  '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0' .

    Die Frage ist mehr eine Verständnisfrage- und ich möchte nichts von Rindviechern, wie Bison's oder Yacc's hören.. 😃
    Wie generiere ich jetzt meinen Parserbaum daraus?

    0
  • H

    Moin,

    das Interopreter Pattern sagt mir vom Namen nichts.
    Ich denke aber, dass du einen Syntaxtree aufbauen möchtest?

    Dann kannst du "im Prinzip" die EBNF Regeln in Quellcode übersetzen. Mit viel Rekursion, Stacks und halt einer Baumstruktur ist das gar nicht mal so unmöglich wie es sich vielleicht anhört. Such mal nach ein paar Folien über Compilerbau, da wirst du geholfen. Weitere Stichwörter: Bottom-Up Parsing, Top-Down Parsing.

    Übrigens: Ich hoffe deine Grammar ist nur ein Beispiel, normalerweise würdest du so keine Sprache bauen (schau dir mal die Definition von "ausdruck" an).

    Oh ja und... juhu, das Forum geht wieder 🙂

    0
  • D

    Ist meine erste bnf ^^ aber nein, ich wollte dies nur beispielhaft darstellen.
    Das Interpreter-Pattern ist ein Pattern der GoF, Ein Verhaltensmuster das Gramatikbäume beschreibt.

    0
  • F

    DocJunioR schrieb:

    Das Interpreter-Pattern ist ein Pattern der GoF, Ein Verhaltensmuster das Gramatikbäume beschreibt.

    Hehe, das ist eine gewaltige Ladung GoFSpeak 😃

    Das "Interpreter Pattern" ist, analog zum "Function Pattern" u.ä., im Prinzip lediglich der Ratschlag eine DSL zu nutzen wenn dies sinnvoll ist.

    0
  • H

    Achso 🙂 Also auf Wikipedia (hier) steht ein imo ziemlich gutes Beispiel für einen objektorientierten Parser. Das Beispiel lässt zwar viel Freiraum für Interpretation, aber das tun ja viele gute Beispiele.

    Wenn's dir wirklich um ne eigene Minisprache geht, hol dir was fertiges. Der Aufwand sowas selber zu schreiben, rechtfertigt in den seltensten Fällen den Aufwand.

    0
  • D

    DSL = Digital Subscripter Line?
    DSL = Definitive Software Library?

    oder wie oder was oder warum oder wie jetz?
    *gg* und was hat das mit meiner Aussage über das Interpreter Pattern zu tun?

    @ Headhunter Danke, aber ich hab den GAmma hier zu liegen 😉

    0
  • B

    DocJunioR schrieb:

    DSL = Digital Subscripter Line?
    DSL = Definitive Software Library?

    Domain-Specific Language

    0
  • D

    Ich bin dafür, Abkürzungen abzuschaffen oder wenigstens noch einen Kontext, Subkontext, Metakontext und Sub-Subkontext hinzuzufügen..

    Edit: Wo ich schon vom Gamma rede- der beschreibt ja das Erbauer Pattern zum Bauen von Kompositae/en/ums (?) so nen Interpreter ist ja mehr oder weniger genau das.. Werd mich mal dran probieren..

    0
  • ?

    Schau dir mal spirit2 an.
    Bei den Beispielen ist schon ein Parser mit Interpreter für ein Mini C dabei:
    https://svn.sourceforge.net/svnroot/spirit/trunk/final/libs/spirit/example/qi/mini_c/

    0
  • F

    DocJunioR schrieb:

    Ich bin dafür, Abkürzungen abzuschaffen oder wenigstens noch einen Kontext, Subkontext, Metakontext und Sub-Subkontext hinzuzufügen..

    <a href= schrieb:

    Google: dsl programming, 1. Treffer">
    Domain-specific programming language - Wikipedia, the free ...

    A domain-specific programming language (domain-specific language, DSL) is a programming language designed for, and intended to be useful for, ...
    en.wikipedia.org/wiki/Domain-specific_programming_language - 43k -

    Würdest du kurz über meine Aussage - die nur zum Teil als Erklärung für Headhunter gedacht war - nachdenken, könntest du den Kontext vielleicht sogar noch ein wenig weiter eingrenzen.

    DocJunioR schrieb:

    Edit: Wo ich schon vom Gamma rede- der beschreibt ja das Erbauer Pattern zum Bauen von Kompositae/en/ums (?) so nen Interpreter ist ja mehr oder weniger genau das.. Werd mich mal dran probieren..

    Nein, ganz und gar nicht, ein Builder ist kein Interpreter.

    Vielleicht solltest du dich nicht ganz so engstirnig auf GoF pur fixieren, und dabei alles andere ausblenden. Es geht nicht um "so nen Interpreter [Pattern?]" - selbst wenn du dem Buch treu bleibst und direkt den ( ⚠ Kontextwarnung ⚠ ) AST interpretierst, ist es ganz schlicht ein Interpreter, etwas das auch und vor allem unabhängig vom GoF Interpreter Pattern existiert.

    0
  • K

    finix schrieb:

    Es geht nicht um "so nen Interpreter [Pattern?]" - selbst wenn du dem Buch treu bleibst und direkt den ( ⚠ Kontextwarnung ⚠ ) AST interpretierst, ist es ganz schlicht ein Interpreter, etwas das auch und vor allem unabhängig vom GoF Interpreter Pattern existiert.

    Äh, ohne GoF gelesen zu haben: Was hat ein Interpreter mit nem Parser zu tun?! Ein Parser baut den AST *auf*, ein Interpreter baut ihn *ab* (wenn man so will … er traversiert ihn halt).

    0
  • D

    @ finix - zu den Abkürzungen: diese war mir tatsächlich nicht geläufig. Wollte damit auch nur sagen, dass es meines erachtens zuviele Abk. gibt.

    Zum Erbauer Pattern. Ich hab nicht gesagt, dass der Erbauer ein Interpreter ist, sondern dass man mit dem Erbauer ein Kompositum erstellt und der Interpreter ist mit dem Kompositum verwandt. Dieser Teilsatz bezog sich auf das Objekt, nicht aufs Subjekt. Macht man manchmal in der deutschen Sprache 😉

    Ich hab garnicht vor, mich engstirnig an die GoF zu halten- es gab auch bei mir ein Leben vor der GoF, ja sogar ein Leben vor der oop oder strukturierten Programmierung ^^ und es wird auch eines danach geben.

    0
  • F

    Konrad Rudolph schrieb:

    Äh, ohne GoF gelesen zu haben: Was hat ein Interpreter mit nem Parser zu tun?! Ein Parser baut den AST *auf*, ein Interpreter baut ihn *ab* (wenn man so will … er traversiert ihn halt).

    Naja, wenn man mit Interpreter Softwareprogramm/-modul meint, dann beinhaltet ein Interpreter zumeist einen Parser.

    Und es ist auch nicht gesagt dass die VM, die Runtime, den AST "abbaut", ihn ausführt - empirisch gesehen (lies: das sagt mein aus dem Stegreif Bauchgefühl 😉 ) bekommen die wenigsten überhaupt einen AST zu Gesicht. So spontan fiele mir nur Ruby ein als Implementation die (derzeit noch) den AST direkt ausführt.

    0
  • F

    DocJunioR schrieb:

    @ finix - zu den Abkürzungen: diese war mir tatsächlich nicht geläufig. Wollte damit auch nur sagen, dass es meines erachtens zuviele Abk. gibt.

    Hatte ich anders gelesen. Im Prinzip hast du ja Recht, aber DSL ist relativ geläufig, vor allem in diesem Kontext, und da sind Abkürzungen schon durchaus sinnvoll. Aber solange es nicht so schlimm wird wie Englisch, das wohl bald nur noch aus Abkürzungen und Akronymen bestehen wird...

    DocJunioR schrieb:

    Zum Erbauer Pattern. Ich hab nicht gesagt, dass der Erbauer ein Interpreter ist, sondern dass man mit dem Erbauer ein Kompositum erstellt und der Interpreter ist mit dem Kompositum verwandt. Dieser Teilsatz bezog sich auf das Objekt, nicht aufs Subjekt. Macht man manchmal in der deutschen Sprache 😉

    Ich versteh's immer noch nicht, aber du wirst schon wissen was du meinst 😃

    DocJunioR schrieb:

    Ich hab garnicht vor, mich engstirnig an die GoF zu halten- es gab auch bei mir ein Leben vor der GoF, ja sogar ein Leben vor der oop oder strukturierten Programmierung ^^ und es wird auch eines danach geben.

    Das wichtigste ist das daneben 😉

    0
  • K

    finix schrieb:

    Naja, wenn man mit Interpreter Softwareprogramm/-modul meint, dann beinhaltet ein Interpreter zumeist einen Parser.

    Hm, ich würde genau das Gegenteil sagen, nämlich, dass ein Interpreter überhaupt keinen Parser beinhalten muss. Das sind getrennte Module. Ein Interpreter kann den AST z.B. auch schon vorgekaut in Form von Bytecode bekommen, den er dann interpretiert (=> Java-VM. Ja, das *ist* eine Weiterverarbeitung des AST). Für mich ist der Parser halt genau das, was einen AST erstellt und mehr nicht. Wohingegen der Interpreter das ist, was als Eingabe die Ausgabe des Parsers oder eines Zwischencodegenerators bekommt.

    0
  • F

    Konrad Rudolph schrieb:

    finix schrieb:

    Naja, wenn man mit Interpreter Softwareprogramm/-modul meint, dann beinhaltet ein Interpreter zumeist einen Parser.

    Hm, ich würde genau das Gegenteil sagen, nämlich, dass ein Interpreter überhaupt keinen Parser beinhalten muss. Das sind getrennte Module. Ein Interpreter kann den AST z.B. auch schon vorgekaut in Form von Bytecode bekommen, den er dann interpretiert (=> Java-VM. Ja, das *ist* eine Weiterverarbeitung des AST). Für mich ist der Parser halt genau das, was einen AST erstellt und mehr nicht. Wohingegen der Interpreter das ist, was als Eingabe die Ausgabe des Parsers oder eines Zwischencodegenerators bekommt.

    So sehe ich das im Endeffekt auch. Bloß ist ein Interpreter tendenziell eher das Gesamtprogramm oder -modul (welches auch zumeist Quellcode interpretiert), was du als Interpreter bezeichnest würde ich eher VM oder Runtime o.ä. nennen.

    edit:

    <a href= schrieb:

    http://de.wikipedia.org/wiki/Interpreter">Ein Interpreter (im Sinne der Softwaretechnik) ist ein Software-Programm, das einen Programm-Quellcode im Gegensatz zu Assemblern oder Compilern nicht in eine auf dem System direkt ausführbare Datei umwandelt, sondern den Quellcode einliest, analysiert und ausführt. Die Analyse des Quellcodes erfolgt also zur Laufzeit des Programms

    Wie auch immer, im ursprünglichen Kommentar ging es darum das sämtliche Beispiele etc. zum Interpreter Pattern die ich bisher gesehen habe einen AST aufbauen und diesen direkt interpretieren.

    0
  • K

    finix schrieb:

    Wie auch immer, im ursprünglichen Kommentar ging es darum das sämtliche Beispiele etc. zum Interpreter Pattern die ich bisher gesehen habe einen AST aufbauen und diesen direkt interpretieren.

    Ah. Dann kennst Du einen anderen Interpreter Pattern als ich. Aber wie gesagt: Ich habe GoF nie gelesen, das, was ich kenne, stammt aus Wikipedia und einigen anderen Quellen bzw. Codes. Daher wäre ich natürlich mal interessiert, wie "dein" Interpreter-Pattern aussieht, wenn er den AST aufbaut.

    Um Missverständnisse zu vermeiden: Das, was ich als Interpreter pattern kenne, sähe in C++ einfach so aus:

    class expression {
public:
    virtual object* eval(context&) = 0;
    virtual ~expression() {}
};

// Beispiel-Implementierung:
class number_literal : public expression {
public:
     number_literal(int value) : m_value(value) {}
     object* eval(context& ctx) { return ctx.make_int_literal(m_value); }

private:
     int m_value;
}

    Und wenn man sich noch ein paar Klassen bauen würde, könnte man den AST in C++ folgendermaßen aufbauen. Dabei ist aber zu beachten, dass das C++-Code ist! Den AST definiere ich also in C++, der Interpreter pattern bekommt ihn fertig übergeben.

    method_call(
    "printf",
    method_call(
        "+", number_literal(23), reference("the_answer")
    )
).eval(context());
    0
  • F

    Konrad Rudolph schrieb:

    Um Missverständnisse zu vermeiden:

    Scheinbar zu spät dafür: http://www.c-plusplus.net/forum/viewtopic-var-p-is-1314706.html#1314706

    0
  • D

    and now for something completely different:

    ich bin also inzwischen so weit, dass ich weiß, dass mein Interpreter zwar interpretieren kann, aber den entsprechenden Parserbaum muss ich von hand bauen. Der Erbauer als Pattern dient zum Erstellen von Kompositae (oder wie auch immer man den Plural davon bildet.) Wenn ich den Expressionbaum aus dem Interpreter Pattern als Kompositum sehe, könnte ich also meinen Ausdruck (sagte ich schon, dass es sich um Aussagenlogik handelt?) in einen Parsebaum umwandeln und anschließend laufen lassen..

    Alledings erscheint es mir ein wenig aufwändig..
    Gibts da nicht einfachere Möglichkeiten?
    Zu stackbasierten Interpretern, manchmal auch VM genannt, hab ich bisher leider nicht sehr viel sinnvolles gefunden und mein Buchetat ist für meinen Urlaub draufgegangen..

    0
  • K

    Hi DocJunioR,

    treib's mal mit der Verwendung der GoF-Patterns nicht so weit, dass Du das Ziel aus den Augen verlierst. Wenn Du Boost.Spirit verwendest, dann hast Du den notwendigen Parser in wenigen Minuten zusammen und musst ihn nur noch wenig anpassen, damit er einen Parsebaum in dem von Dir gewünschten Format liefert. Aufwendig sollte das eigentlich nicht sein.

    0
Anmelden zum Antworten