Monoid Parsing - was ist das?

Question

Ich stolperte gerade über den Begriff Monoid Parsing von einem slide namens "Einführung in Monoids" von Edward Kmett. Die Folie verwendet durchgehend Haskell.

Jetzt bei der Suche nach dem Begriff fand ich nichts als eine sehr wenige Erwähnungen davon und die meisten von dem gleichen Autor. Also ich denke, dieser Begriff könnte hier erklärt werden.

Also, ist Monoid Parsing etwas, das interessant und neu ist? Erscheint es irgendwo außer auf der Folie, mit der ich verlinkt bin? Und vor allem, was ist das? Die Folie selbst schien keine Definition zu geben oder so stark hervorzuheben.

Answer 1

Ich beginne damit, wie Parser normalerweise arbeiten. Im Allgemeinen nimmt ein Parser Input-Tokens in sequentieller Reihenfolge. An einem bestimmten Punkt (normalerweise nachdem alle Token erschöpft sind) gibt der Parser die Ausgabe zurück. Ein Nachteil dieses Modells ist, dass es von Natur aus sequenziell ist: Da der Parser in einer Reihenfolge von Tokens arbeitet, ist es nicht offensichtlich, wie der Prozess parallelisiert werden soll.

Allerdings kann Parsing parallelisiert werden, wenn wir Zugang zu einem Betrieb haben die Lage, zu einem einzigen Ergebnis teilweise Parsen Ergebnisse kombiniert. Wenn unsere Sprache beispielsweise mit einer kontextfreien Grammatik darstellbar ist, könnten wir jede Definition der obersten Ebene getrennt und parallel analysieren und dann die Teile später mit der Kombinationsoperation zusammensetzen.

Monoid Parsing bedeutet einfach, dass der Parser Zugriff auf eine geeignete Kombinationsfunktion hat. Ein Monoid ist eine Struktur mit einem Nullelement und einem binären assoziativen Operator. Zum Beispiel bilden Listen ein Monoid, wobei die Null die leere Liste ist und der assoziative Operator eine Verkettung ist. Denken Sie daran, dass Assoziativität (a++b)++c == a++(b++c) bedeutet. Es kommt vor, dass dies die notwendige Eigenschaft ist, um sicherzustellen, dass wir Parsergebnisse auf sinnvolle Weise rekombinieren können. Die genaue Reihenfolge, in der die Unterparsere rekombiniert werden, spielt keine Rolle, solange jede Unterparse in der richtigen Sequenzposition gehalten wird.

Natürlich für tatsächlich einen parallelen Parser zu schreiben, ist es notwendig, die Stücke in geeigneter Weise auch aufzuteilen. Wenn Sie Definitionen auf oberster Ebene parallel analysieren möchten, müssen Sie erkennen können, wo diese Definition beginnt. Diese Aufgabe wird normalerweise vom Parser selbst ausgeführt. Soweit ich mich erinnere, deckt ein großer Teil seiner Folien dieses Thema ab. Die Aufteilung auf Top-Level-Definitionen ist ziemlich grobkörnig; Idealerweise könnte unser Parser von jedem beliebigen Token ausgehen und später aus den Teilen einen Sinn ergeben, wenn der Monoidoperator angewendet wird.

Leider kann ich nicht sagen, ob „monoidal Parsing“ neu ist, wie ich mit der Literatur nicht besonders vertraut bin. Ich vermute jedoch, dass alle Modelle oder Algorithmen für die parallele Analyse eine monoide Struktur enthalten, auch wenn sie nicht explizit benannt ist. Es ist seit einiger Zeit bekannt, dass Monoide für die Parallelisierung von Problemen geeignet sind, daher wäre ich nicht überrascht, wenn diese Technik unter Parser-Forschern üblich ist.

Answer 2

Versuchen Sie, seine andere Präsentation auf this page, es ist die Nummer zwei nach der, die Sie gerade lesen. Es ist etwas Neues und alles, was ich wirklich tun kann, ist seine Slides paraphrasieren und Ihnen sagen, dass es ein Versuch ist, monadische Parsing (wie Parsec) zu nehmen und eine schwächere algebraische Struktur verwenden, so dass es mehr Spielraum für die Umstrukturierung der Berechnung gibt. Die Idee ist, die Parallelität zu verbessern.

Edit: die Kommentare auf der Seite deuten die beiden Gespräche wurden Rücken an Rücken so vielleicht die Erwähnung auf der Folie geplant Sie ein Vorläufer für das zweite Gespräch sah, war.