Vorteile von Antlr (im Vergleich zu etwa lex / yacc / Bison) [geschlossen]

Question

I lex und yacc (häufiger Bison) in der Vergangenheit für verschiedene Projekte verwendet haben, in der Regel Übersetzer (wie eine Teilmenge von EDIF strömte in einem EDA-app). Darüber hinaus habe ich musste Code unterstützen, die auf lex / yacc Grammatiken Jahrzehnte zurückgeht. Also ich weiß, dass meine Art und Weise um die Werkzeuge, obwohl ich kein Experte bin.

Ich habe in der Vergangenheit in verschiedenen Foren positive Kommentare über Antlr gesehen, und ich bin neugierig, was ich fehle. Also, wenn Sie beide verwendet haben, bitte sagen Sie mir, was ist besser oder fortgeschrittenere in Antlr. Meine aktuellen Einschränkungen sind, dass ich in einem C ++ Shop arbeiten, und jedes Produkt, das wir versenden nicht enthält Java, so dass die resultierenden Parser dieser Regel folgen müßten.

Answer 1

Update / Warnung: Diese Antwort kann veraltet sein

!

---

Ein Hauptunterschied besteht darin, dass ein ANTLR LL (*) Parser erzeugt, während YACC und Bisons beide erzeugen, die LALR Parser sind. Dies ist eine wichtige Unterscheidung für eine Reihe von Anwendungen, die offensichtlichste ist Operatoren:

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

ANTLR ist völlig unfähig, diese Grammatik der Handhabung, wie sie ist. Zur Nutzung ANTLR (oder einen anderen LL Parser-Generator), würden Sie brauchen diese Grammatik etwas zu konvertieren, die nicht linksrekursive ist. Allerdings hat Bison kein Problem mit Grammatiken dieser Form. Sie müßten ‚+‘ und erklären, ‚-‘ als links assoziativen Operatoren, aber das ist nicht unbedingt für Linksrekursion erforderlich ist. Ein besseres Beispiel könnte Versand sein:

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

Beachten Sie, dass sowohl die expr und die actuals Regeln linksrekursive. Dadurch ergibt sich eine wesentlich effizientere AST, wenn es Zeit für die Codegenerierung kommt, weil es die Notwendigkeit für mehrere Register und unnötige verschütten (ein linksgerichtete Baum während eine rechtslastige Baum zusammengebrochen werden kann, kann nicht) vermeidet.

Im Hinblick auf dem persönlichen Geschmack, ich denke, dass LALR Grammatiken viel einfacher zu konstruieren und zu debuggen. Der Nachteil ist, dass Sie mit etwas kryptischen Fehler zu tun haben, wie shift-reduce und (die gefürchtete) Verminderungs reduzieren. Dies sind Fehler, den Bison fängt bei den Parser zu erzeugen, so dass es keinen Einfluss auf die Endanwender-Erfahrung, aber es kann den Entwicklungsprozess ein bisschen interessanter machen. ANTLR ist in der Regel leichter sein als als für YACC / Bison zu verwenden, genau aus diesem Grunde.

Answer 2

Der bedeutendste Unterschied zwischen YACC / Bison und ANTLR ist die Art von Grammatiken dieser Tools verarbeiten können. YACC / Bison Griff LALR Grammatiken, ANTLR Griffe LL Grammatiken.

Oft Menschen, die mit LALR Grammatiken für eine lange Zeit gearbeitet haben, finden mit LL Grammatiken arbeiten schwieriger und umgekehrt. Das bedeutet nicht, dass die Grammatiken oder Werkzeuge sind von Natur aus schwieriger, mit zu arbeiten. Welches Tool Sie finden leichter zu verwenden meist kommt auf Vertrautheit mit der Art der Grammatik.

Soweit Vorteile gehen, gibt es Aspekte, bei denen LALR Grammatiken Vorteile gegenüber LL Grammatiken haben und es gibt andere Aspekte, bei denen LL Grammatiken Vorteile gegenüber LALR Grammatiken haben.

YACC / Bison Tisch angetrieben Parser erzeugen, was bedeutet, dass die „Verarbeitungslogik“ wird in dem Parser-Programm Daten enthält, nicht so sehr in dem Code des Parsers. Die Pay-off ist, dass selbst ein Parser für eine sehr komplexe Sprache eine relativ kleine Code-Fußabdruck hat. Dies war wichtiger in den 1960er und 1970er Jahren, als Hardware sehr begrenzt war. Tabellengesteuerte Parser-Generatoren gehen Sie zurück zu dieser Zeit und kleinen Code-Fußabdruck wurden eine Hauptanforderung damals.

ANTLR erzeugt Rekursiver Abstieg, das heißt, die „Verarbeitungslogik“ in der Parser-Code enthielt, da jede Produktionsregel der Grammatik durch eine Funktion in dem Parser des Code dargestellt wird. Der Pay-off ist, dass es einfacher ist, zu verstehen, was der Parser durch das Lesen seines Codes tut. Auch ist Rekursiver Abstieg der Regel schneller als Tisch angetrieben diejenigen. Doch für sehr komplexe Sprachen, wird die Code-Fußabdruck größer sein. Das war ein Problem in den 1960er und 1970er Jahren. Damals nur relativ kleine Sprachen wie Pascal zum Beispiel auf diese Weise Einschränkungen aufgrund von Hardware implementiert wurden.

ANTLR erzeugten Parser sind in der Regel in der Nähe von 10.000 Zeilen Code und vieles mehr. Handwritten Rekursiver Abstieg sind oft in derselben Liga. Wirths Oberon-Compiler ist vielleicht das kompakteste mit etwa 4000 Zeilen Code einschließlich Codegenerierung, aber Oberon ist eine sehr kompakte Sprache mit nur etwa 40 Produktionsregeln.

Wie bereits jemand darauf hingewiesen hat, ein großes Plus für ANTLR ist das grafische IDE-Tool, genannt ANTLRWorks. Es ist eine komplette Grammatik und Sprache Design-Labor. Es visualisiert Ihre Grammatikregeln, wie Sie sie eingeben, und wenn es keine Konflikte findet, wird es Ihnen zeigen, grafisch, was der Konflikt ist und was es bewirkt. Es kann sogar automatisch Refactoring und Konflikte wie links Rekursion lösen. Sobald Sie eine konfliktfreie Grammatik haben, können Sie ANTLRWorks lassen eine Eingabedatei Ihrer Sprache analysieren und einen Parse-Baum und AST für Sie bauen und den Baum grafisch in dem IDE zeigen. Dies ist ein sehr großer Vorteil, weil es Ihnen viele Stunden Arbeit sparen kann: Sie werden konzeptionelle Fehler in Ihrer Sprache Design finden, bevor Sie Codierung beginnen! Ich habe kein solches Werkzeug für LALR Grammatiken gefunden, es scheint, gibt es kein solches Werkzeug.

Auch für Menschen, die nicht wollen ihre Parser aber Hand-Code, sie zu erzeugen, ist ANTLRWorks ein großes Werkzeug für Sprache Design / Prototyping. Wahrscheinlich das beste solches Werkzeug zur Verfügung. Leider hat das hilft Ihnen nicht, wenn Sie LALR Parser aufbauen wollen. Der Wechsel von LALR LL einfach Vorteil ANTLRWorks nehmen kann durchaus sinnvoll sein, aber für einige Leute, Grammatik Schaltungsarten kann eine sehr schmerzhafte Erfahrung sein. Mit anderen Worten:. YMMV

Answer 3

Ein paar Vorteile für ANTLR:

• ausgeben kann Parser in verschiedenen Sprachen -. Java nicht erforderlich, um die erzeugte Parser läuft
• Awesome GUI macht Grammatik Debugging leicht (z können Sie die erzeugte AST direkt in der grafischen Benutzeroberfläche sehen, keine zusätzlichen Werkzeuge erforderlich)
• generierte Code ist eigentlich für Menschen lesbaren (es ist eines der Ziele von ANTLR) und die Tatsache, dass es LL-Parser sicherlich hilft in dieser Hinsicht erzeugt.
• Definition von Terminals ist kontextfrei als auch (im Gegensatz in (f) lex regex) - so ermöglicht zum Beispiel die Definition von Terminals enthalten, müssen ordnungsgemäß geschlossen Klammern

Mein .02 $

Answer 4

Ein weiterer Vorteil von ANTRL ist, dass Sie ANTLRWorks verwenden können, obwohl ich nicht kann sagen, dass dies ein strenger Vorteil ist, da auch dort ähnliche Werkzeuge für andere Generatoren sein kann.

Answer 5

• Bison und Flex Ergebnis in einem kleineren Speicherbedarf, aber Sie haben keine grafischen IDE.
• antlr verwendet mehr Speicher, aber Sie haben ANTLRWorks, eine grafische IDE.

Bison / Flex Speichernutzung ist in der Regel ein mbyte oder so. Vergleichen Sie das mit antlr - vorausgesetzt, es ist 512 Byte Speicher verwendet für jedes Token in der Datei, die Sie analysieren möchten. 4.000.000 Jetons und Sie sind aus den virtuellen Speicher auf einem 32-Bit-System.

Wenn die Datei, die Sie wünschen, ist groß zu analysieren, antlr können über genügend Arbeitsspeicher ausgeführt, wenn Sie also nur eine Konfigurationsdatei analysieren wollen, wäre es eine praktikable Lösung. Andernfalls, wenn Sie eine Datei mit vielen Daten zu analysieren, versucht Bison.