Das deutsche Python-Forum • Baeume in Python

Seite 1 von 2

Baeume in Python

Verfasst: Mittwoch 14. September 2005, 10:52

von 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

Re: Baeume in Python

Verfasst: Mittwoch 14. September 2005, 15:33

von Leonidas

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.

Re: Baeume in Python

Verfasst: Donnerstag 15. September 2005, 13:07

von 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

Re: Baeume in Python

Verfasst: Mittwoch 21. September 2005, 09:22

von der_Gerhard

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?

Verfasst: Mittwoch 21. September 2005, 09:30

von jens

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.

Verfasst: Mittwoch 21. September 2005, 09:51

von der_Gerhard

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

Verfasst: Mittwoch 21. September 2005, 14:15

von Joghurt

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.

Verfasst: Mittwoch 21. September 2005, 22:28

von 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']

Verfasst: Dienstag 4. Oktober 2005, 10:07

von der_Gerhard

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.

Verfasst: Dienstag 4. Oktober 2005, 10:10

von jens

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.

Verfasst: Dienstag 4. Oktober 2005, 12:20

von der_Gerhard

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.

Verfasst: Dienstag 4. Oktober 2005, 15:49

von jens

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

Verfasst: Dienstag 4. Oktober 2005, 18:17

von rayo

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)

Verfasst: Mittwoch 5. Oktober 2005, 00:47

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

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.

Verfasst: Mittwoch 5. Oktober 2005, 09:14

von rayo

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

Hab PyParsing noch nie verwendet

Gruss

Verfasst: Mittwoch 19. Oktober 2005, 13:33

von der_Gerhard

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?

Verfasst: Donnerstag 20. Oktober 2005, 11:42

von der_Gerhard

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.

Verfasst: Donnerstag 20. Oktober 2005, 21:29

von 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?

Verfasst: Freitag 21. Oktober 2005, 09:07

von der_Gerhard

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

Verfasst: Samstag 22. Oktober 2005, 21:01

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