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

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
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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 (former) Modvoice
Gerhard

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

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
Python-Forum Veteran
Beiträge: 8502
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

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.

GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

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

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

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

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
Python-Forum Veteran
Beiträge: 8502
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

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.

GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

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
Python-Forum Veteran
Beiträge: 8502
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

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

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

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

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:

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
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

Hi,
ich bins nochmal.
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:
[snip]
Die Struktur der Eingabedatei hat leider noch weitere Eigenschaften, so kann es z.B. sein, dass einer Variablen (Array) mehrere Werte, oder gar kein Wert zugewiesen werden koennen. Dies wuerde dann so aussehen:

Code: Alles auswählen

template T1 :=
{
   c1 := d1,
   b1 :=
   {
      b2 :=
      {
         a3 := 2,
         b3 := 3
      },
      a2 := 4
   },
   a1 := 5,
   a3 :=
   {
   	7,
      8,
      9
   },
   a4 := 
   {
      10
   },
   a5 :=
   {
   }
}
Ich versuche schon den ganzen Tag im vorhandenen Code "rumzubasteln", so dass der Parser das schluckt. Bisher leider ohne Erfolgsaussichten. Any hints?
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

Hi,
der_Gerhard hat geschrieben: Ich versuche schon den ganzen Tag im vorhandenen Code "rumzubasteln", so dass der Parser das schluckt. Bisher leider ohne Erfolgsaussichten. Any hints?
ich habs hinbekommen, indem ich diese Zeilen hinzugefuegt/geaendert habe.

Code: Alles auswählen

array = Suppress('{') + ZeroOrMore(delimitedList(value)) + Suppress(ZeroOrMore('}'))
        item = Group(Optional(Suppress('{')) + key + Suppress(':=') + (value | body | array))
Konstrukte der Art

Code: Alles auswählen

template a:=
{
 a5:=
  {
      b:=5
   },
   {
      c:=6
   }
}
werden auch umgesetzt, aber leider in ['a', ['a5', ['b', '5']], ['c', '6']]. Korrekt waere
['a', ['a5', ['b', '5'], ['c', '6']]].
Sieht jemand den Fehler?

[edit] Au weia. Wo kein Fehler ist, kann auch niemand einen sehen.[/edit]

Hier nochmal die komplette Funktion;

Code: Alles auswählen

def makeGrammar(self):
        value = Word(alphanums + "_'()")
        value.setParseAction(lambda source, loc, toks: [toks[0]])
        key = Word(alphanums + "_")
        body = Forward()
        array = Suppress('{') + ZeroOrMore(delimitedList(value)) + Suppress(ZeroOrMore('}'))
        item = Group(Optional(Suppress('{')) + key + Suppress(':=') + (value | body | array))
        body << Suppress('{') + Optional(Suppress(ZeroOrMore('{'))) \
                + Dict(delimitedList(item)) + Suppress(ZeroOrMore('}'))
        template = Suppress(Keyword('template')) + item
        templates = Dict(OneOrMore(template)) + StringEnd()
        return templates
Edit (Leonidas): Code in Python-Tags gesetzt.
Zuletzt geändert von der_Gerhard am Freitag 21. Oktober 2005, 10:24, insgesamt 1-mal geändert.
BlackJack

der_Gerhard hat geschrieben:

Code: Alles auswählen

def makeGrammar(self):
        value = Word(alphanums + "_'()")
        value.setParseAction(lambda source, loc, toks: [toks[0]])
        key = Word(alphanums + "_")
        body = Forward()
        array = Suppress('{') + ZeroOrMore(delimitedList(value)) + Suppress(ZeroOrMore('}'))
        item = Group(Optional(Suppress('{')) + key + Suppress(':=') + (value | body | array))
        body << Suppress('{') + Optional(Suppress(ZeroOrMore('{'))) \
                + Dict(delimitedList(item)) + Suppress(ZeroOrMore('}'))
        template = Suppress(Keyword('template')) + item
        templates = Dict(OneOrMore(template)) + StringEnd()
        return templates
Die `parseAction` bei `value` bewirkt nichts, kann also wegfallen. Und die ganzen ``zeroOrMore('{')`` und auch die entsprechenden schliessenden Klammern machen die Grammatik ziemlich "komisch" und wohl auch uneindeutig. Die Klammern sind schliesslich da um einen Block oder eine Verschachtelungsebene zu identifizieren.

Ich fange mal von "oben" an aus der Grammatik einen möglichen Quelltext zu erstellen:

Code: Alles auswählen

"template" + item
"template {{{{{{{{{ " + delimitedList(item) + "}}}"
Das sieht an dieser Stelle schon ziemlich falsch aus.

Code: Alles auswählen

def make_grammar():
    value = Word(alphanums)
    identifier = Word(alphas, alphanums)
    body = Forward()
    assignement = Group(identifier + Suppress(':=') + (value | body))
    assignements = Dict(delimitedList(assignement))
    list_ = Group(delimitedList(value))
    body << Suppress('{') + (assignements | list_) + Suppress('}')
    template = Suppress(Keyword('template')) + assignement
    templates = Dict(OneOrMore(template)) + StringEnd()
    return templates
Versuch mal, ob das klappt. Eine Liste im Ergebnis erkennt man daran, das sie keine Zeichenkette ist und keine Schlüssel besitzt, also `len(x.keys()) == 0` gilt, wenn `x` das entsprechende `ParserResult` Objekt ist.

Die Grammatik ist nicht besonders schön, weil man mehr als ein Token vorausschauen muss um entscheiden zu können, ob man eine Liste oder ein weiteres "Dictionary" nach einem '{' hat.

Wo kommen die Daten denn her? Gibt's vielleicht eine offizielle Grammatik dafür?
der_Gerhard
User
Beiträge: 14
Registriert: Mittwoch 21. September 2005, 09:06

Hi BlackJack,
erst nochmals Danke fuer deine Bemuehungen; du scheinst meine letzte Hoffnung zu sein :-)
BlackJack hat geschrieben:Und die ganzen ``zeroOrMore('{')`` und auch die entsprechenden schliessenden Klammern machen die Grammatik ziemlich "komisch" und wohl auch uneindeutig. Die Klammern sind schliesslich da um einen Block oder eine Verschachtelungsebene zu identifizieren.
Dies war ein unschoener Versuch, mehrere sich oeffnende und schliessende Klammern parsen zu koennen (sieht man gleich im Beispiel).
BlackJack hat geschrieben:

Code: Alles auswählen

def make_grammar():
...[snip]
Versuch mal, ob das klappt. Eine Liste im Ergebnis erkennt man daran, das sie keine Zeichenkette ist und keine Schlüssel besitzt, also `len(x.keys()) == 0` gilt, wenn `x` das entsprechende `ParserResult` Objekt ist.
Also logisch ist die neue Funktion, aber der Interpreter meckert bei der ersten verschachtelten Zuweisung:
pyparsing.ParseException: Expected "}" (at char 205), (line:14, col:5): Dies ist am Ender der Anweisung b1:={...},
Die Grammatik ist nicht besonders schön, weil man mehr als ein Token vorausschauen muss um entscheiden zu können, ob man eine Liste oder ein weiteres "Dictionary" nach einem '{' hat.
Da muss ich dir recht geben, leider ist sie so festgeschrieben.
Wo kommen die Daten denn her? Gibt's vielleicht eine offizielle Grammatik dafür?
Die Daten sind in Dateien enthalten. Sie belegen Datenstrukturen mit speziellen Werten. Es kann aber davon ausgegangen werden, dass die Dateien syntaktisch korrekt sind, d.h. es waere auch egal, wenn eine falsche Klammerung in der Datei nicht vom Parser angemeckert wird, solange das erzeugte Dictionary bzw. Liste korrekt ist.
Nein, leider gibt es keine offizielle Grammatik. Ich gebe aber mal ein vollstaendiges Beispiel an, welches alle Sonderfaelle enthaelt.
Meine im letzten Post angegebene Funktion macht doch alles richtig, auch wenn sie nicht sauber programmiert ist, bis natuerlich auf die Parameterliste, aber die ist kommt spaeter.
Ich hatte wohl gestern nach ein paar Stunden Konzentration auf die Funktion nen Knick in der Optik.

Da aber die Templates spaeter auch wieder ausgegeben werden muessen, habe ich das Problem, dass ich wissen muss wieviele Klammer an jede Stelle gesetzt werden muessen, d.h. aus

Code: Alles auswählen

template a:=
{
 c0:=
 {
    {
       {
          b:=5
       }
    }
 }
}
wird ['a', ['c0', ['b', '5']]], woraus ich nicht mehr auf die Anzahl der Klammern schliessen kann. Also waere eine Moeglichkeit die Lieste folgendermassen aussehen zu lassen:
['a', ['c0', ['{', '{', 'b', '5', '}', '}']]] oder? Ich sehe da im Moment keine einfacher Moeglichkeit.

Code: Alles auswählen

template Typ1 name1 (Parameterliste z.B. template Typ2 name 2, template ... ) :=
{
   //Fall 1: Normale Zuweisung
   c1 := d1,
   //Fall 2: Normale verschachtelte Zuweisung
   b1 :=
   {
      b2 :=
      {
         a3 := 2,
         b3 := 3
      },
      a2 := 4
   },
   //Fall 3: Leere Liste
   a3 :=
   {
   },
   //Fall 4: Liste mit einem Element
   a4 := 
   {
      10
   },
   //Fall 5: Liste mit mehreren Elementen
   a5 :=
   {
      7,
      8,
      9   
   },
   //Sonderfall 1: Zuweisung(en) in geschweiften Klammern
   a6:=
   {
      a7:=
      {
         {
            a8 := 7,
            a9 := 8
         },
         {
            a10 := 99
         }
      }
   },
   //Sonderfall 2: mehrere Klammern
   a11:=
   {
      {
         {
            a12 := 42,
            a13 :=
            {
               a14 := 17   
            }
         }
      }
   }
}
Mann, mann mann. Ich dir auf jedenfall ein paar Bier schuldig, da du mir jetzt schon ein gutes Stueck weitergeholfen hast. Ich teste mal weiter und schreibe, wenn ich eine Loesung gefunden habe.

Gruss
Gerd
BlackJack

Okay ich bin jetzt bei folgendem gelandet:

Code: Alles auswählen

value = Word(alphanums).setResultsName('value')
identifier = Word(alphas, alphanums).setResultsName('identifier')
block = Forward()
assignment = Group(identifier + Suppress(':=')
                   + (value | block)).setResultsName('assignement')
assignments = Group(delimitedList(assignment)).setResultsName('assignments')
list_ = Group(Optional(delimitedList(value | block))).setResultsName('list')
block << Suppress('{') + (assignments | list_) + Suppress('}')
template_signature = identifier # TODO: Noch zu erweitern.
template = Group((Suppress(Keyword('template')) + template_signature
                 + Suppress(':=') + block)).setResultsName('template')
templates = OneOrMore(template).setResultsName('templates') + StringEnd()
templates.ignore(dblSlashComment)
Das parst zumindestend Dein Beispiel mit den Sonderfällen (inklusive Kommentaren).

Die `Dict()`s habe ich rausgeschmissen. Jetzt sind alles Listen/Sequenzen. Und ich habe den Untergrammatiken Namen gegeben, damit man zwischen 'assignments' und 'list' einfacher unterscheiden kann. Wirklich nötig sind nur 'assignments' und 'list' aber mit den anderen ist `result.asXML()` jetzt ganz nett lesbar.

Sonderfall 1 und 2 werden dadruch erschlagen, dass in Listen auch Blöcke erlaubt sind. In Deinem Sonderfall 1 ist `a7` dann eine Liste mit zwei Elementen, nämlich zwei Zuweisungsblöcke und im Sonderfall 2 is `a11` eine Liste, die eine Liste enthält, die wiederum einen Zuweisungsblock enthält.

Hier noch eine kleine Funktion, die aus einem Parser-Ergebnis wieder Quelltext erzeugt:

Code: Alles auswählen

def ast2str(ast):
    def template2str(template):
        name, body = template
        return ('template %s := ' % name) + node2str(body)
    
    def node2str(node):
        if isinstance(node, basestring):
            return node
        node_type = node.getName()
        if node_type == 'assignments':
            result = ', '.join('%s := %s' % (identifier, node2str(value))
                               for identifier, value in node)
        elif node_type == 'list':
            result = ', '.join(map(node2str, node))
        else:
            raise Exception('Unknown block type %r' % node_type)
        return '{ %s }' % result
    
    return '\n'.join(map(template2str, ast))
Da kommt eine Zeile pro Template heraus, also ohne hübsche Einrückung, aber man sieht hoffentlich ganz gut, wie man die Zuweisungsblöcke von den Listen unterscheiden kann und das keine Informationen verloren gegangen sind.
Antworten