Baeume in Python

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Gerhard

Mittwoch 14. September 2005, 10:52

Hi *,

erstmal ein Lob an den Betreiber dieses Forums.

Ich bin zugegebenermassen ein blutiger Anfaenger in Sachen Python, habe aber angefangen mich mit dem O'Reillybuch Learning Python in die Materie einzulesen.

Ich moechte nicht, dass ihr mir hier die Loesung meines Problems praesentiert, sondern ich brauche nur ein paar Tipps, wie man mit Python sinnvoll an die Aufgabe herangeht.

Mein Problem ist, dass ich verschachtelte Datenstrukturen der Art:

Code: Alles auswählen

template T1 :=
{
   c1 := 1,
   b1 :=
   {
      b2 :=
      {
         a3 := 2,
         b3 := 3
      },
      a2 := 4
   },
   a1 := 5
}
miteinander vergleichen muss:
Viele dieser Strukturen dieser Art liegen in einer Datei. Eine anzugebene Basissstruktur soll mit allen anderen Strukturen in der Datei verglichen werden um die Anzahl der gleichen Zeilen herauszufinden.

Meine Ueberlegungen sind erstmal die einzelnen Hierarchien zu sortieren, da dies die Anzahl der noetigen Vergleiche verringert.
Als Datenstruktur fuer solch ein Template kommt ja nur ein Baum in Frage (oder?).
Leider gibt es ja keine Datenstruktur "Baum" in Python, so dass ich dies mit verschachtelten Listen implementieren moechte.
Oder sollte ich die Datei nach XML umformen, da es ja fuer XML-Dateiverarbeitung schon einige Module fuer Python gibt.
Hat diese Vorgehensweise Aussichten auf Erfolg?
Fuer Hinweise oder Anmerkungen bin ich euch dankbar.

Gruesse
Gerd
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 14. September 2005, 15:33

Gerhard hat geschrieben:Als Datenstruktur fuer solch ein Template kommt ja nur ein Baum in Frage (oder?).
Leider gibt es ja keine Datenstruktur "Baum" in Python, so dass ich dies mit verschachtelten Listen implementieren moechte.
Das sieht eigentlich eher wie ein Dictionary (Dict aka Hash in anderen Sprachen) aus, also denke ich dass du so am schnellsten zum Ziel kommen solltest.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Gerhard

Donnerstag 15. September 2005, 13:07

Hi Leonidas,
Leonidas hat geschrieben:
Gerhard hat geschrieben:Als Datenstruktur fuer solch ein Template kommt ja nur ein Baum in Frage (oder?).
Leider gibt es ja keine Datenstruktur "Baum" in Python, so dass ich dies mit verschachtelten Listen implementieren moechte.
Das sieht eigentlich eher wie ein Dictionary (Dict aka Hash in anderen Sprachen) aus, also denke ich dass du so am schnellsten zum Ziel kommen solltest.
super, vielen dank fuer den Hinweis. Zum Glueck habe ich noch nicht so viel Zeit mit der Baumimplementierung vergeudet. Mit Dictionaries sollte es in der Tat einfacher zu realisieren sein.

Gruss
Gerd
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

Mittwoch 21. September 2005, 09:22

Hi,

ich bin mittlerweile auf den Code Snipped

"Einlesen einer Datei in ein Dictionary"
http://www.python-forum.de/viewtopic.ph ... highlight= gestossen, welcher fuer mein Programm hilfreich ist. Allerdings verstehe ich den regulaeren Ausdruck nicht richtig. Kann mir da jemand auf die Spruenge helfen?
Das Problem ist, dass wenn ich die Funktion file_to_dict auf eine wie von mir beschriebene Datei anwende, Hauptstrukturen, die noch Unterstrukturen besitzen logischerweise das erste Zeichen hinter dem Separator ":=" zugewiesen bekommen, also "{".
Hat jemand eine Idee, wie man die Funktion file_to_dict umschreiben kann, dass die Haupstruktur ein neues Dictionary mit den Unterstrukturen erhaelt?
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Mittwoch 21. September 2005, 09:30

Ich glaub du verrenst dich da ein wenig.

Hast du die Datenstruktur denn dir selbst ausgedacht, oder ist sie wirklich zwingend vorgeschrieben?

Ich würde mir da nämlich lieber eine einfachere Variante basteln, die man besser parsen könnte.

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

Mittwoch 21. September 2005, 09:51

Hi,
jens hat geschrieben:Ich glaub du verrenst dich da ein wenig.

Hast du die Datenstruktur denn dir selbst ausgedacht, oder ist sie wirklich zwingend vorgeschrieben?

Ich würde mir da nämlich lieber eine einfachere Variante basteln, die man besser parsen könnte.
ja, die Datenstruktur ist so vorgeschrieben mit theoretisch beliebeiger Verschachtelungstiefe.
Da ich noch ein Anfaenger in Sachen Python bin, kam mir die Funktion von Dookie recht gelegen und hatte die Hoffnung, dass man die zusaetzliche Funktionalitaet recht einfach hinzufuegen koennte.

Gruss
Gerhard
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Mittwoch 21. September 2005, 14:15

Also ich denke, in diesem Falle wirst du wohl einen kleinen Parser schreiben müssen; evtl. ist es auch einfacher, dir mit Yappy einen Parser generieren zu lassen, auch wenn das evtl. Overkill ist.
BlackJack

Mittwoch 21. September 2005, 22:28

PyParsing ist auch ganz nett um sich einen Parser für eigene "Spezialsprachen" zu basteln.

Edit: Hier ist ein Parser, der zumindest Dein Beispiel versteht:

Code: Alles auswählen

from pyparsing import Keyword, alphas, nums, alphanums, Word, Forward, \
                      delimitedList, Suppress, Group, OneOrMore, Dict, \
                      StringEnd

source = """template T1 :=
{
   c1 := 1,
   b1 :=
   {
      b2 :=
      {
         a3 := 2,
         b3 := 3
      },
      a2 := 4
   },
   a1 := 5
}
template T2 := { x1 := 42, z2 := 23 }
"""

def make_grammar():
    integer = Word(nums)
    integer.setParseAction(lambda source, loc, toks: [int(toks[0])])
    identifier = Word(alphas, alphanums)
    body = Forward()
    item = Group(identifier + Suppress(':=') + (integer | body))
    body << Suppress('{') + Dict(delimitedList(item)) + Suppress('}')
    template = Suppress(Keyword('template')) + item
    templates = Dict(OneOrMore(template)) + StringEnd()
    return templates

grammar = make_grammar()
result = grammar.parseString(source)
print 'List:', result.asList()
print 'Keys:', result.keys()
print 'T1/b1/a2:', result['T1']['b1']['a2']
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

Dienstag 4. Oktober 2005, 10:07

Hi BlackJack,
BlackJack hat geschrieben:PyParsing ist auch ganz nett um sich einen Parser für eigene "Spezialsprachen" zu basteln.

Edit: Hier ist ein Parser, der zumindest Dein Beispiel versteht:

Code: Alles auswählen

from pyparsing import Keyword, alphas, nums, alphanums, Word, Forward, \
                      delimitedList, Suppress, Group, OneOrMore, Dict, \
                      StringEnd

source = """template T1 :=
{
   c1 := 1,
   b1 :=
   {
      b2 :=
      {
         a3 := 2,
         b3 := 3
      },
      a2 := 4
   },
   a1 := 5
}
template T2 := { x1 := 42, z2 := 23 }
"""

def make_grammar():
    integer = Word(nums)
    integer.setParseAction(lambda source, loc, toks: [int(toks[0])])
    identifier = Word(alphas, alphanums)
    body = Forward()
    item = Group(identifier + Suppress(':=') + (integer | body))
    body << Suppress('{') + Dict(delimitedList(item)) + Suppress('}')
    template = Suppress(Keyword('template')) + item
    templates = Dict(OneOrMore(template)) + StringEnd()
    return templates

grammar = make_grammar()
result = grammar.parseString(source)
print 'List:', result.asList()
print 'Keys:', result.keys()
print 'T1/b1/a2:', result['T1']['b1']['a2']
vielen dank fuer deine Bemuehung. Das funktioniert super, aber leider sind nicht nur Zahlen als Werte erlaubt, sondern auch Strings.
Kennt jemand eine brauchbare Einfuehrung in das Pyparsing Modul? Alles was ich gefunden habe setzt schon ein gehoeriges Wissen bezueglich Parsen vorraus, was ich leider nicht besitze.
Erste leihenhafte try and error versuche, den Code abzuaendern, so dass auch Stings als Zuweisung erlaubt sind schlugen leider fehl.
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Dienstag 4. Oktober 2005, 10:10

Nur ein Schuss in's blaue. Vielleicht reicht es aus, wenn du die Zeile:

Code: Alles auswählen

    integer.setParseAction(lambda source, loc, toks: [int(toks[0])])
durch

Code: Alles auswählen

    integer.setParseAction(lambda source, loc, toks: [toks[0]])
änderst.

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

Dienstag 4. Oktober 2005, 12:20

Hi Jens,
jens hat geschrieben:Nur ein Schuss in's blaue. Vielleicht reicht es aus, wenn du die Zeile:

Code: Alles auswählen

    integer.setParseAction(lambda source, loc, toks: [int(toks[0])])
durch

Code: Alles auswählen

    integer.setParseAction(lambda source, loc, toks: [toks[0]])
änderst.
leider daneben.
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Dienstag 4. Oktober 2005, 15:49

Naja, wobei sich integer auch ziemlich nach Zahl anhöhrt ;)

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Dienstag 4. Oktober 2005, 18:17

ich würde eher mit diesem ins blaue schiessen & zusätzlich das int() weglassen :)

Code: Alles auswählen

integer = Word(nums)
mit

Code: Alles auswählen

integer = Word(nums, alphas, alphanums)
BlackJack

Mittwoch 5. Oktober 2005, 00:47

rayo hat geschrieben:

Code: Alles auswählen

integer = Word(nums)
mit

Code: Alles auswählen

integer = Word(nums, alphas, alphanums)
Eher:

Code: Alles auswählen

integer = Word(alphanums)
Wobei dann der Name `integer` vielleicht nicht mehr ganz so passend ist. :wink:

Eine andere Einführung zu PyParsing als die Webseite und die mitgelieferten Beispiele kenne ich auch nicht. Aber eigentlich ist das doch (E)BNF recht geradlinig in Klassen übersetzt.
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Mittwoch 5. Oktober 2005, 09:14

Ja passend ist er sicher nicht mehr. Ich hab einfach die 3 nacheinander genommen weil es so beim identifier = Word(alphas, alphanums) auch so ist :D

Hab PyParsing noch nie verwendet :)

Gruss
Antworten