SGF-Parsing

Anleitung

Eine Zeichenkette im Smart Game Format parsen.

SGF ist ein Standardformat zum Speichern von Dateien für Brettspiele, insbesondere Go.

SGF ist ein ziemlich einfaches Format. Eine SGF-Datei enthält normalerweise einen einzelnen Baum aus Knoten, wobei jeder Knoten eine Eigenschaftsliste ist. Die Eigenschaftsliste enthält Schlüssel-Wert-Paare. Jeder Schlüssel darf nur einmal vorkommen, kann aber mehrere Werte haben.

In dieser Übung parst du eine SGF-Zeichenkette und gibst eine Baumstruktur aus Eigenschaften zurück.

Eine SGF-Datei kann so aussehen:

(;FF[4]C[root]SZ[19];B[aa];W[ab])

Das ist ein Baum mit drei Knoten:

• Der oberste Knoten hat drei Eigenschaften: FF[4] (Schlüssel = „FF“, Wert = „4“), C[root] (Schlüssel = „C“, Wert = „root“) und SZ[19] (Schlüssel = „SZ“, Wert = „19“). (FF gibt die Version von SGF an, C ist ein Kommentar und SZ ist die Größe des Bretts.)
  • Der oberste Knoten hat ein einzelnes Kind, das eine einzelne Eigenschaft hat: B[aa]. (Schwarz spielt auf den Punkt, der als „aa“ kodiert ist, also den 1-1-Punkt.)
    • Der B[aa]-Knoten hat ein einzelnes Kind, das eine einzelne Eigenschaft hat: W[ab].

Wie du dir vorstellen kannst, enthält eine SGF-Datei viele Knoten mit einem einzelnen Kind, deshalb gibt es dafür eine Kurzschreibweise.

SGF kann Variationen des Spiels kodieren. Go-Spieler gehen beim Nachspielen viel zurück (probieren wir das, klappt nicht, probieren wir jenes), und SGF unterstützt Variationen von Zugfolgen. Zum Beispiel:

(;FF[4](;B[aa];W[ab])(;B[dd];W[ee]))

Hier hat der Wurzelknoten zwei Variationen. Die erste (die per Konvention angibt, was tatsächlich gespielt wird) ist die, in der Schwarz auf 1-1 spielt. Schwarz bekam diese Datei von seinem Lehrer geschickt, der auf einen sinnvolleren Zug im zweiten Kind des Wurzelknotens hinwies: B[dd] (4-4-Punkt, eine sehr übliche Eröffnung, um sich die Ecke zu sichern).

Ein Schlüssel kann mehrere zugehörige Werte haben. Zum Beispiel:

(;FF[4];AB[aa][ab][ba])

Hier wird AB (Schwarz hinzufügen) verwendet, um drei schwarze Steine auf dem Brett hinzuzufügen.

Alle Eigenschaftswerte sind vom SGF-Texttyp. Andere Werttypen musst du nicht implementieren. Du kannst die vollständige Dokumentation des Texttyps lesen, aber eine Zusammenfassung der wichtigsten Punkte findest du unten:

• Zeilenumbrüche werden entfernt, wenn sie direkt nach einem \ stehen, andernfalls bleiben sie als Zeilenumbrüche erhalten.
• Alle Whitespace-Zeichen außer Zeilenumbrüchen werden in Leerzeichen umgewandelt.
• \ ist das Escape-Zeichen. Jedes Nicht-Whitespace-Zeichen nach \ wird unverändert eingefügt. Jedes Whitespace-Zeichen nach \ folgt den oben genannten Regeln. Beachte, dass SGF keine Escape-Sequenzen für Whitespace-Zeichen wie \t oder \n hat.

Verwechsle nicht:

• Die Zeichenkette, wie sie in einem String-Literal in den Tests dargestellt wird
• Die Zeichenkette, die an den SGF-Parser übergeben wird

Escape-Sequenzen in den String-Literalen wurden möglicherweise schon vom Parser der Programmiersprache verarbeitet, bevor sie an den SGF-Parser übergeben werden.

SGF (und das Parsen im Allgemeinen) hat noch ein paar weitere Feinheiten, die du größtenteils ignorieren kannst. Du kannst davon ausgehen, dass die Eingabe in UTF-8 kodiert ist, die Tests keine Charset-Eigenschaft enthalten, darum musst du dich also nicht kümmern. Außerdem kannst du davon ausgehen, dass alle Zeilenumbrüche im Unix-Stil sind (\n, in den Tests kommen kein \r oder \r\n vor) und dass in den Tests keine optionalen Whitespaces zwischen Eigenschaften, Knoten usw. vorkommen.

Fehlermeldungen

Manchmal ist es notwendig, eine Exception auszulösen. Wenn du das tust, solltest du immer eine aussagekräftige Fehlermeldung angeben, die verrät, woher der Fehler kommt. Das macht deinen Code lesbarer und hilft erheblich beim Debuggen. Wenn du weißt, dass die Fehlerquelle von einem bestimmten Typ ist, kannst du eine der eingebauten Fehlertypen auslösen, solltest aber trotzdem eine aussagekräftige Nachricht angeben.

Diese Übung erfordert, dass du die raise-Anweisung verwendest, um eine ValueError zu „werfen“, wenn der Eingabe passende Trennzeichen fehlen, sie nicht in Großbuchstaben geschrieben ist, keinen Baum mit Knoten bildet oder überhaupt keinen Baum bildet. Die Tests bestehen nur, wenn du die exception sowohl mit raise auslöst als auch ihr eine Nachricht mitgibst.

Um eine ValueError mit einer Nachricht auszulösen, schreibe die Nachricht als Argument an den exception-Typ:

# if the tree properties as given do not have proper delimiters.
raise ValueError("properties without delimiter")

# if the tree properties as given are not all in uppercase.
raise ValueError("property must be in uppercase")

# if the input does not form a tree, or is empty.
raise ValueError("tree missing")

# if the input is a tree without any nodes.
raise ValueError("tree with no nodes")