Ich frage mich, warum es keine verallgemeinerten Parser-Kombinatoren für das Bottom-up-Parsing in Haskell gibt wie ein Parsec-Kombinator für das Top-Down-Parsing.
(Ich konnte einige Forschungsarbeiten im Jahr 2004 finden, aber nichts nach dem Ссылка
Ссылка )
Gibt es einen bestimmten Grund dafür, es nicht zu erreichen?
Dies liegt an referenzieller Transparenz. So wie keine Funktion den Unterschied zwischen
ausmachen kann %Vor%Keine Funktion kann den Unterschied zwischen einer Grammatik, die ein endlicher Graph ist, und einer Grammatik, die ein unendlicher Baum ist, unterscheiden. Bottom-Up-Parsing-Algorithmen müssen in der Lage sein, die Grammatik als Graph zu erkennen, um alle möglichen Parsing-Zustände aufzählen zu können.
Die Tatsache, dass Top-down-Parser ihre Eingaben als unendliche Bäume sehen, erlaubt ihnen, leistungsfähiger zu sein, da der Baum rechnerisch komplexer sein könnte, als jeder Graph sein könnte; zum Beispiel
%Vor% akzeptiert jede endliche aufsteigende Folge von Zahlen beginnend bei n . Dies hat unendlich viele verschiedene Parsing-Zustände. (Es könnte möglich sein, dies in einer kontextfreien Weise darzustellen, aber es wäre schwierig und erfordert mehr Verständnis des Codes, als eine Parsing-Bibliothek in der Lage ist, denke ich)
Eine Bottom-Up-Kombinator-Bibliothek könnte geschrieben werden, obwohl sie etwas hässlich ist, indem sie verlangt, dass alle Parser so "etikettiert" werden, dass
An diesem Punkt sieht es mehr nach einer traditionellen Spezifikation einer Grammatik aus als nach einer kombinatorischen Spezifikation. Es könnte jedoch immer noch nett sein; Sie müssten nur rekursive Produktionen kennzeichnen, die beliebig große Regeln wie numSequence ausschließen würden.
Wie luquis Antwort zeigt, ist eine Bottom-Up-Parser Kombinator -Bibliothek nicht realistisch. Wenn jemand auf diese Seite kommt und nach Haskells Bottom-Up-Parser Generator sucht, heißt das, wonach du suchst der Happy-Parser-Generator . Es ist wie yacc für haskell.
Wie oben schon erwähnt: Haskells Behandlung von rekursiven Parser-Definitionen erlaubt keine Definition von Bottom-Up-Parsing-Bibliotheken. Bottom-up-Parsing-Bibliotheken sind jedoch möglich, wenn Sie rekursive Grammatiken anders darstellen. Mit Entschuldigungen für die Eigenwerbung ist eine (Forschungs-) Parser-Bibliothek, die einen solchen Ansatz verwendet, Grammatik-Kombinatoren . Es implementiert eine Grammatikumwandlung namens uniforme Paull-Transformation, die mit dem Top-down-Parseralgorithmus kombiniert werden kann, um einen Bottom-up-Parser für die ursprüngliche Grammatik zu erhalten.
Tags und Links haskell parsing parsec parser-combinators attoparsec