Warum Online-do-Parser scheinen regexps zu stoppen?

Question

Ich habe für lange fragen, warum es scheint nicht zu irgendwelche Parser für sein, sagen wir, BNF , dass wie regexps in verschiedenen Bibliotheken verhalten.

Sicher, es gibt Dinge, wie ANTLR , Yacc und viele andere, die em <> Code generieren , was wiederum ein CFG , aber es scheint nicht, eine Bibliothek zu sein, dass ohne den Zwischenschritt machen kann.

Ich interessiere mich für das Schreiben eines Packrat Parser , noch dazu alle jene verschachtelt -parenthesis-Macken mit regexps assoziiert (und vielleicht sogar noch mehr, für den Sport), aber irgendwie habe ich das Gefühl, dass ich gerade in eine andere Halteproblem -ähnlichen Klasse von Sümpfen zu Fuß.

Gibt es eine technische / theoretische Begrenzung für diese Parser, oder bin ich gerade etwas fehlt?

Answer 1

Ich denke, es ist mehr eine kulturelle Sache. Die Verwendung von kontextfreien Grammatiken ist vor allem auf Compiler beschränkt, die in der Regel Code mit jeder Produktionsregel zugeordnet. In einigen Sprachen ist es zur Ausgabe von Code einfacher als Rückrufe zu simulieren. Parser Kombinatoren in Haskell, zum Beispiel: In anderen Ländern werden Sie Parser-Bibliotheken sehen. Auf der anderen Seite finden Sie reguläre Ausdrücke breite Verwendung in Tool wie grep, wo es den C-Compiler jedes Mal läuft der Benutzer gibt einen neuen regulären Ausdruck unbequem ist.

Answer 2

Boost.Spirit sieht aus wie, was Sie nach.

Wenn Sie schauen, um Ihre eigenen zu machen, habe ich verwendet BNFC für mein neuestes Compiler-Projekt und bietet die Grammatik in einer eigenen Implementierung verwendet. Dies könnte ein guter Ausgangspunkt sein ...

Answer 3

Es gibt nicht und technische / theoretische Begrenzung lauern in den Schatten. Ich kann nicht sagen, warum sie nicht mehr populär sind, aber ich weiß von mindestens einer Bibliothek, die diese Art von „on-line“ Analyse bereitstellt, die Sie suchen.

SimpleParse ist eine Python-Bibliothek, die Sie einfach fügen Sie Ihre haarige EBNF Grammatik in Ihr Programm und es verwenden kann Dinge sofort, keine itermediate Schritte zu analysieren. Ich habe es für mehrere Projekte verwendet, in denen ich eine benutzerdefinierten Eingabesprache wollte, aber ich will wirklich nicht auf einen formalen Build-Prozess begehen.

Hier ist ein kleines Beispiel aus der Spitze von meinem Kopf:

decl = r"""
    root := expr
    expr := term, ("|", term)*
    term := factor+
    factor := ("(" expr ")") / [a-z]
"""
parser = Parser(decl) 
success, trees, next = parser.parse("(a(b|def)|c)def")

Der Parser combinator Bibliotheken für Haskell und Scala auch lassen Sie Ihre Grammatik für Ihren Parser in dem gleichen Stück Code ausdrücken, die es verwendet. Allerdings kann man nicht, sagen wir, den Benutzertyp in einer Grammatik zur Laufzeit lassen (die nur von Interesse für Menschen, die Software sein könnte Menschen Grammatiken helfen sowieso verstehen).

Answer 4

Pyparsing ( http://pyparsing.wikispaces.com ) hat eine integrierte Unterstützung für packrat Parsing und es ist reiner Python, so können Sie die tatsächliche Implementierung sehen.

Answer 5

Da ausgewachsene kontextfreie Grammatiken sind verwirrend genug, da sie ohne etwas kryptisch dicht und unverständlich Syntax sind, um sie noch verwirrender?

Es ist schwer zu wissen, was Sie fragen. Versuchen Sie, so etwas wie ein regulärer Ausdruck zu erstellen, aber für kontextfreie Grammatiken? Wie, mit $var =~ /expr = expr + expr/ (in Perl) und das Match "1 + 1" oder "1 + 1 + 1" oder "1 + 1 + 1 + 1 + 1 + ..." mit? Ich denke, eine der Grenzen dieser sein wird, Syntax: mehr als etwa drei Regeln zu haben wird Ihren „Grammatik-Ausdruck“ noch nicht lesbar als jeder heutigen regulärer Ausdruck machen

.

Answer 6

Nebeneffekt ist das einzige, was ich Sache sehen, die Sie erhalten. Die meisten der Parser-Generatoren umfassen Code für die Verarbeitung eingebettet und Sie würden eine eval brauchen, um diese Arbeit zu machen.

Ein Weg, um das wäre Aktionen zu nennen und dann eine „Aktion“ -Funktion machen, die den Namen der Aktion nimmt zu tun und die args es mit zu tun.

Answer 7

Sie tun könnten es theoretisch mit Geist in C ++ steigern, aber es ist vor allem für statische Grammatiken gemacht. Ich denke, der Grund, warum dies nicht üblich ist, dass CFGs ist nicht so häufig wie regexs verwendet. Ich habe noch nie eine Grammatik mit Ausnahme Compiler Konstruktion zu verwenden habe, aber ich habe regexs viele Male verwendet. CFG ist in der Regel sehr viel komplexer als regexs, so macht es Sinn, Code mit einem Tool wie YACC oder ANTLR statisch zu erzeugen.

Answer 8

tcllib hat so etwas, wenn Sie mit Parse Expression Grammatiken und auch TCL. Wenn Perl ist Ihre Sache CPAN hat Parse :: Earley . Hier ist eine reine Perl Variation, die vielversprechend aussieht. PLY scheint eine plausible Lösung für Python

zu sein