Parser Combinators: Warum sie Regex bei komplexen Aufgaben schlagen
Parsing verwandelt unstrukturierten Text in strukturierte Daten. Regex wird bei komplexen Aufgaben schnell unübersichtlich, tree-sitter ist oft überdimensioniert – dazwischen liegen Parser Combinators. Der Artikel erklärt anhand von TypeScript-Beispielen, wie ein partieller Parser funktioniert, wie sich mehrere Parser zu Sequenzen verketten lassen und wie daraus ein vollständiger Parser für Formate wie die Ausgabe von ping entsteht.
Aber Regex wird bei komplexen Aufgaben schnell unübersichtlich, und tree-sitter ist oft überdimensioniert – für diesen Mittelweg sind Parser Combinators perfekt.
- ArneCode
Ich mag die Animationen wirklich sehr, sie machen intuitiv verständlich, was passiert!
Ein Nachteil, den Parser-Kombinatoren meiner Meinung nach haben, zum Beispiel im Vergleich zu Parser-Generator-Bibliotheken (bei denen der Parser aus einer separaten Grammatikdatei generiert wird), ist, dass man viel Mapping-/Unwrapping-Code hinzufügen muss. Meiner Meinung nach macht das die Parser schwerer lesbar.
Als Versuch, das zu verbessern, habe ich an einer Parser-Kombinator-Bibliothek in Rust gearbeitet.
Sie fügt zwei zusätzliche Kombinatoren hinzu (capture und bind), die die Ergebnisse von Parsern in Buckets speichern (bind) und die in diesen Buckets gespeicherten Werte später verwenden können, um Ergebnisse zu konstruieren (capture).
Dadurch kann man den Unwrapping-/Mapping-Code eliminieren und die Grammatik von der Ergebniskonstruktion trennen.
Wenn du Zeit hast, würde ich mich sehr über Feedback freuen!
Du findest sie hier: https://github.com/ArneCode/marser
- marginalia_nu
Ich verstehe nicht, warum das nicht auf einer einzigen Seite sein kann. Das macht es wirklich schwer, auf frühere "Kapitel" zurückzugreifen, wenn man neue Informationen bekommt, weil es eine Slideshow ist. Man kann auch nicht suchen.
Scheint, als würden wir aus seltsamen ästhetischen Gründen unnötig Einschränkungen des Papiermediums wieder einführen, die es in digitalen Medien nicht gibt?
- akst
Ich finde das eine wirklich coole Website und liebe dieses Thema
Aber ich denke, du solltest diese Seite vielleicht auf kleineren Bildschirmen testen, es ist nur sehr begrenzter Bildschirmplatz für den interessanten Inhalt, die obere rechte Hälfte hat viel Padding, der scrollbare Inhalt hat im Grunde 1/3 des verfügbaren Bildschirmplatzes, die linke Seite hat irgendwie nochmal 1/3
Schau, deine Website, deine Vision, ich verstehe das und ich respektiere, dass du mit der UI etwas anderes ausprobierst, aber wenn dein Ziel hier ist, deine Ideen zu vermitteln, würde ich als Leser es schätzen, mehr Bildschirmplatz für den Inhalt zu haben. Als ich auf den Link geklickt habe, um diesen speziellen Beitrag zu sehen, bin ich einfach nicht an deinen anderen Beiträgen interessiert (oder zumindest nicht, bis ich den gelesen habe, für den ich mir extra Mühe gemacht habe).
Nur so nebenbei, ich benutze gerade ein MacBook Air.
- BoppreH
Wenn du Python verwendest und dein Problem zu groß für einen einzelnen Regex, aber zu klein für einen vollwertigen Parser wie im Artikel ist, kann ich den eingebauten re.Scanner[0] empfehlen. Es ist ein regex-basierter Tokenizer[1] (also kein rekursives Parsen) im `re`-Modul, der aus irgendwelchen Gründen in keiner offiziellen Dokumentation auftaucht.
Du gibst ihm ein Muster für jeden Token-Typ und eine Funktion zur Verarbeitung jedes Treffers, und du bekommst eine Liste verarbeiteter Tokens zurück.
Wichtig ist, dass er die Liste in einem Durchgang verarbeitet und sicherstellt, dass die Treffer zusammenhängend sind, während ein naives `re.findall` mit Capture-Gruppen nicht übereinstimmende Zeichen ignoriert. Du bekommst außerdem eine Referenz auf den laufenden Scanner, sodass du die Position des Treffers für die Fehlerberichterstattung aufzeichnen kannst.
import re
# Initialisiere den Scanner.
scanner = re.Scanner([
(r"\d+", lambda scanner, token: ('COUNT', int(token))),
(r"\w+", lambda scanner, token: ('ANIMAL', token.removesuffix('s'))),
(r"[,. ]", None), # None -> Token überspringen.
])
# Scanne einen Beispielstring.
results, remainder = scanner.scan("45 pigeons, 23 cows, 11 spiders.")
# Stelle sicher, dass wir alles geparst haben.
assert not remainder
print(results)
# [('COUNT', 45),
# ('ANIMAL', 'pigeon'),
# ('COUNT', 23),
# ('ANIMAL', 'cow'),
# ('COUNT', 11),
# ('ANIMAL', 'spider')]
[0]: https://stackoverflow.com/a/693818/252218
[1]: https://en.wikipedia.org/wiki/Lexical_analysis#Tokenization
- boomlinde
Die erste Adresse sollte wahrscheinlich nicht als IP-Adresse geparst werden, da sie auch ein Hostname sein kann. Das mag wie eine Kleinigkeit erscheinen, aber es schafft eine Gelegenheit zu zeigen, was man tut, wenn man eines von mehreren möglichen Konstrukten erwartet.
Der Artikel war wegen der begrenzten Fläche für den Textkörper etwas schwer zu lesen. Ich musste trotz der kurzen Kapitel auf mehreren Seiten scrollen.