Interpreter-Pattern aus Backus-Naur erstellen

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/