Implementierung von 'read' für einen linksassoziativen Baum in Haskell

Dies ist eine Situation, in der die Verwendung einer Parsing-Bibliothek den Code erstaunlich kurz und extrem ausdrucksstark macht. (Ich war erstaunt, dass es so war, als ich experimentierte, um das zu beantworten!)

Ich werde Parsec verwenden (dieser Artikel enthält einige Links für weitere Informationen) und es in " Anwendungsmodus "(statt monadisch), da wir die zusätzliche Kraft / Fußschießfähigkeit von Monaden nicht benötigen.

Code

Zuerst die verschiedenen Importe und Definitionen:

Nun ist die Grundeinheit des Baumes entweder ein einzelnes Zeichen (das ist keine Klammer) oder ein eingeklammerter Baum. Der eingeklammerte Baum ist nur ein normaler Baum zwischen ( und ) . Und ein normaler Baum ist nur Einheiten, die links-assoziativ in Zweige gesetzt werden (es ist extrem selbstrekursiv). In Haskell mit Parsec:

(Ja, das ist der ganze Parser!)

Wenn wir wollten, könnten wir ohne paren und unit auskommen, aber der obige Code ist sehr aussagekräftig, also können wir ihn so lassen wie er ist.

Als kurze Erklärung (Ich habe Links zur Dokumentation bereitgestellt):

• (<|>) bedeutet im Grunde "linker Parser oder rechter Parser";
• (<?>) ermöglicht es Ihnen, schönere Fehlermeldungen zu erstellen;
• noneOf wird parse alles, was nicht in der angegebenen Liste von Zeichen ist;
• between dauert drei Parser, und gibt den Wert des dritten Parsers zurück, solange er durch die erste und die zweite begrenzt ist;
• char analysiert sein Argument wörtlich.
• many1 analysiert ein oder mehrere seiner Argumente in eine Liste (es scheint, dass die leere Zeichenfolge ungültig ist, daher many1 , anstatt many , die null oder mehr analysiert);
• eof stimmt überein das Ende der Eingabe.

Wir können % verwenden. co_de% Funktion zum Ausführen des Parsers (es gibt parse zurück, Either ParseError Tree ist ein Fehler und Left ist ein korrekter Parse).

Als Right

Wenn Sie es als read like-Funktion verwenden, könnte das etwa so aussehen:

(Ich habe read verwendet, um Konflikte mit read' zu vermeiden; wenn Sie eine Prelude.read -Instanz haben wollen, müssen Sie etwas mehr arbeiten, um Read (oder was auch immer erforderlich) zu implementieren, aber es sollte nicht zu schwer mit dem eigentlichen Parsing bereits abgeschlossen sein.)

Beispiele

Einige grundlegende Beispiele:

Fehler demonstrieren:

Und schließlich der Unterschied zwischen readPrec und tree :

Fazit

Parsec ist unglaublich! Diese Antwort kann lang sein, aber der Kern davon ist nur 5 oder 6 Zeilen Code, die die ganze Arbeit erledigen.

Das sieht sehr ähnlich aus wie eine Stapelstruktur. Wenn Sie auf Ihre Eingabe-Zeichenfolge "ABC(DE)F" stoßen, finden Sie Leaf ein beliebiges Atom, das Sie finden (nicht-Klammern), und fügen es in eine Akkumulatorliste ein. Wenn Sie 2 Einträge in der Liste haben, geben Sie Branch zusammen. Dies könnte mit etwas wie (Hinweis, ungetestet, nur um eine Idee zu geben) gemacht werden:

Das mag einige Modifikationen erfordern, aber ich denke, es ist genug, um Sie auf die richtige Spur zu bringen.

Die Parsec-Antwort von dbaupp ist sehr einfach zu verstehen. Als Beispiel für einen "Low-Level" -Ansatz ist hier ein handgeschriebener Parser, der eine Erfolgsfortsetzung verwendet, um das links-assoziative Baumgebäude zu behandeln: