Interpreter-Pattern aus Backus-Naur erstellen

Konrad Rudolph

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());

finix

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

DocJunioR

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

Konrad Rudolph

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.

DocJunioR

Tja, nur bringt mir spirit nichts, wenn ich java nutzen möchte.
Eigentlich suche ich einen Ansatz der erstmal nur das Design angeht, nicht die Programmiersprache. Muss dann zwar alles selbst machen, aber kann es dann einfach in einer anderen generieren..
Die Pattern sind auch nur Gedankenstützen. Trotzdem weiß ich immernoch nicht, wie ich jetzt aus meinem String

(a & b) | (c & ! d)

Den Baum

OR
     /  \ 
    /    \
  AND    AND
  / \    / \
 a   b  c  NOT
            |
            d

mache. Ob ich jetzt ein Interpreter Pattern generiere oder einfach nur einen Baum von Structs ist ja vollkommen wurscht..
Gibts da nicht nen 10-Zeiler, der mir die Funktionsweise näher bringt?
Hab Entscheidungsbäume bisher immer von hand generiert und in XML abgebildet, aber das ist mir jetzt zu viel Datenoverhead..

Edit: Hab grad das hier gefunden http://www.codeproject.com/useritems/Parser_Expression.asp
werd mich erstmal da durchgraben.. scheint ja mein Problem zu sein.

Edit2: Natürlich hab ich kein Problem damit, auch einfach nur nen Interpreter zu nutzen der direkt am Quellcode interpretiert, nur hab ich da auch keinen Plan, wie ich das parse..

Die Funktionsweise von Spirit kannst du ja auch in java nachstellen.
Du musst halt einfach dir eine Klassenhierarchie schreiben, welche die unterschiedlichen Regeln aneinander kettet.

Ist natürlich in Java etwas umständlicher, da es ja keine Operatorüberladung dort gibt...

Ansonsten, in nem 10 Zeiler ist das nicht generisch machbar.

DocJunioR

war auch nur so gemeint, dass ich keine idee hab, wie ich da anfange.
Wie gesagt, ich möchte gern das interpreter pattern nutzen, aber weiß nicht, wie ich den syntax baum aufbaue. hierfür brauche ich nur eine entsprechende Vorgehensweise...

class rule // evtl. noch ne komposition aus anderen rules einhängen
{
  virtual bool checkcontent(String content)=0;
}

class string_rule extends rule
{
  String muster;
  string_rule(String m){muster = m;}
  bool checkcontent(String content)
  {
    if(muster == content.substring(0,muster.length()))
      return true; //match
    return false;
}

Ist jetzt mal pseudocode. Fehlt natürlich auch viel. So würde es sinn machen, an die Regeln actions zu hängen, die z.B. dann die Erstellung des Baumes übernehmen.
Und um whitespaces etc. zu ignorieren, musst du natürlich Zeichen für Zeichen vergleichen.

finix

Ich schließe mich weiterhin den Tipps der anderen an. Wenn du nicht ANTLR o.ä. verwenden willst, lautet das richtige Suchwort "Parser", nicht "Interpreter Pattern".

DocJunioR schrieb:

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

eine VM ist nicht zwangsläufig stackbasiert, siehe beispielsweise Parrot.

DocJunioR

finix schrieb:

Ich schließe mich weiterhin den Tipps der anderen an. Wenn du nicht ANTLR o.ä. verwenden willst, lautet das richtige Suchwort "Parser", nicht "Interpreter Pattern".

Ist es nicht das, was ich die ganze Zeit impliziere?
Wenn ich aber explizit sage, ich brauch nen Parser, kommt immer gleich "nimm doch yacc, bison, etc. um dir einen zu bauen"..

finix

Schau doch mal unter http://de.wikipedia.org/wiki/Parser. Von dort aus einfach mal die relevanten Links anklicken, und auch auf die (Web-) Quellen achten.

Konrad Rudolph

DocJunioR schrieb:

Tja, nur bringt mir spirit nichts, wenn ich java nutzen möchte.

Ups, in der Tat. Dann schließe ich mich den anderen an und empfehle ANTLR.

Prof84

Ich würde mir mal ASTM verpassen:
http://www.omg.org/news/meetings/workshops/ADM_2005_Proceedings_FINAL/T-3_Newcomb.pdf

oder ASDL:
http://www.cs.princeton.edu/~danwang/Papers/dsl97/dsl97.html

auch nicht schlecht:
http://mr.teknowledge.com/wile/Papers/Abstract_Syntax_form_Concrete_Syntax_Distribution_Copy.pdf

*schlürf*
sitze gerade an Nessi :
http://www.nessi-europe.com/Nessi/