Soll ich einen Parser-Generator verwenden oder meinen eigenen benutzerdefinierten Lexer- und Parser-Code rollen?

81

Welche spezifischen Vor- und Nachteile ergeben sich aus der Arbeit an einer Programmiersprachengrammatik?

Warum / Wann sollte ich meine eigenen rollen? Warum / Wann sollte ich einen Generator verwenden?

Maniero
quelle
Gib Boost.Spirit Qi einen Schuss.
Ebrahim Mohammadi

Antworten:

78

Es gibt drei Optionen, die in verschiedenen Situationen vorzuziehen sind.

Option 1: Parser-Generatoren oder "Sie müssen eine Sprache analysieren und möchten sie nur zum Laufen bringen, verdammt"

Angenommen, Sie werden gebeten, JETZT einen Parser für ein altes Datenformat zu erstellen. Oder Sie müssen Ihren Parser schnell sein. Oder Sie benötigen einen Parser, der leicht zu warten ist.

In diesen Fällen ist es wahrscheinlich am besten, einen Parser-Generator zu verwenden. Sie müssen sich nicht mit den Details auseinandersetzen, Sie müssen nicht viel komplizierten Code besorgen, um richtig zu funktionieren. Sie müssen nur die Grammatik aufschreiben, an die sich die Eingabe hält.

Die Vorteile liegen auf der Hand:

  • Es ist (normalerweise) recht einfach, eine Spezifikation zu schreiben, insbesondere wenn das Eingabeformat nicht zu komisch ist (Option 2 wäre besser, wenn es so ist).
  • Am Ende haben Sie eine sehr leicht zu wartende Arbeit, die leicht zu verstehen ist: Eine Grammatikdefinition fließt normalerweise viel natürlicher als Code.
  • Die von guten Parser-Generatoren generierten Parser sind in der Regel viel schneller als handgeschriebener Code. Handgeschriebener Code kann schneller sein, aber nur, wenn Sie sich mit Ihren Inhalten auskennen. Aus diesem Grund verwenden die meisten weit verbreiteten Compiler einen handgeschriebenen rekursiven Parser.

Bei Parser-Generatoren gilt es eines zu beachten: Sie können Ihre Grammatik manchmal ablehnen. Um einen Überblick über die verschiedenen Arten von Parsern zu erhalten und zu erfahren, wie sie Sie beißen können, können Sie hier beginnen . Hier finden Sie eine Übersicht über viele Implementierungen und die von ihnen akzeptierten Grammatiktypen.

Option 2: handgeschriebene Parser oder "Sie möchten einen eigenen Parser erstellen und möchten möglichst benutzerfreundlich sein"

Parser-Generatoren sind nett, aber nicht sehr benutzerfreundlich (der Endbenutzer, nicht Sie). Normalerweise können Sie keine guten Fehlermeldungen ausgeben und auch keine Fehlerbehebung durchführen. Vielleicht ist Ihre Sprache sehr seltsam und Parser lehnen Ihre Grammatik ab oder Sie benötigen mehr Kontrolle als der Generator Ihnen gibt.

In diesen Fällen ist die Verwendung eines handgeschriebenen rekursiven Parsers wahrscheinlich die beste. Auch wenn es kompliziert sein mag, den Parser in Ordnung zu bringen, haben Sie die vollständige Kontrolle über ihn, sodass Sie alle nützlichen Dinge erledigen können, die Sie mit Parsergeneratoren nicht tun können, wie Fehlermeldungen und sogar die Fehlerbehebung (versuchen Sie, alle Semikolons aus einer C # -Datei zu entfernen : Der C # -Compiler beschwert sich, erkennt jedoch die meisten anderen Fehler, unabhängig vom Vorhandensein von Semikolons.

Handgeschriebene Parser erzielen in der Regel auch eine bessere Leistung als generierte, vorausgesetzt, die Qualität des Parsers ist hoch genug. Wenn Sie andererseits keinen guten Parser schreiben können - normalerweise aufgrund (einer Kombination aus) mangelnder Erfahrung, mangelndem Wissen oder mangelndem Design -, ist die Leistung normalerweise langsamer. Für Lexer gilt jedoch das Gegenteil: Generierte Lexer verwenden im Allgemeinen Tabellensuchen, wodurch sie schneller sind als (die meisten) handgeschriebenen.

Wenn Sie Ihren eigenen Parser schreiben, lernen Sie mehr als nur die Verwendung eines Generators. Schließlich muss man immer komplizierteren Code schreiben und genau verstehen, wie man eine Sprache parst. Wenn Sie andererseits lernen möchten, wie Sie Ihre eigene Sprache erstellen (machen Sie also Erfahrung mit Sprachdesign), ist Option 1 oder Option 3 vorzuziehen: Wenn Sie eine Sprache entwickeln, wird sich wahrscheinlich viel ändern. und Option 1 und 3 erleichtern Ihnen das.

Option 3: Handgeschriebene Parser-Generatoren oder "Sie versuchen, viel aus diesem Projekt zu lernen, und es würde Ihnen nichts ausmachen, wenn Sie ein raffiniertes Stück Code erhalten, das Sie häufig wiederverwenden können."

Dies ist der Pfad, den ich gerade beschreite: Sie schreiben Ihren eigenen Parser-Generator. Dies ist zwar höchst untrivial, wird Ihnen aber wahrscheinlich am meisten beibringen.

Um Ihnen eine Vorstellung davon zu geben, wie ein solches Projekt abläuft, erzähle ich Ihnen von meinen Fortschritten.

Der Lexer Generator

Ich habe zuerst meinen eigenen Lexer-Generator erstellt. Normalerweise entwerfe ich Software, beginnend mit der Art und Weise, wie der Code verwendet wird. Deshalb habe ich mir überlegt, wie ich meinen Code verwenden kann, und dieses Stück Code geschrieben (es ist in C #):

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a lex specification:
      //                    regex   token
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

Die eingegebenen Zeichenfolge-Token-Paare werden in eine entsprechende rekursive Struktur umgewandelt, die die regulären Ausdrücke beschreibt, die sie mit den Ideen eines Rechenstapels darstellen. Dies wird dann in einen NFA (nicht deterministischer endlicher Automat) umgewandelt, der wiederum in einen DFA (deterministischer endlicher Automat) umgewandelt wird. Sie können dann Zeichenfolgen mit dem DFA abgleichen.

Auf diese Weise erhalten Sie eine gute Vorstellung davon, wie genau Lexer funktionieren. Wenn Sie es richtig machen, können die Ergebnisse Ihres Lexergenerators ungefähr so ​​schnell sein wie professionelle Implementierungen. Sie verlieren auch keine Ausdruckskraft im Vergleich zu Option 2 und nicht viel Ausdruckskraft im Vergleich zu Option 1.

Ich habe meinen Lexer-Generator in etwas mehr als 1600 Codezeilen implementiert. Mit diesem Code funktioniert das oben Genannte, der Lexer wird jedoch bei jedem Programmstart automatisch generiert: Ich werde irgendwann Code hinzufügen, um ihn auf die Festplatte zu schreiben.

Wenn Sie wissen möchten, wie man einen eigenen Lexer schreibt, ist dies ein guter Anfang.

Der Parser-Generator

Sie schreiben dann Ihren Parser-Generator. Ich verweise hier noch einmal auf eine Übersicht über die verschiedenen Arten von Parsern - als Faustregel gilt: Je mehr sie analysieren können, desto langsamer werden sie.

Da Geschwindigkeit für mich kein Problem darstellt, habe ich einen Earley-Parser implementiert. Es hat sich gezeigt , dass erweiterte Implementierungen eines Earley-Parsers etwa doppelt so langsam sind wie andere Parsertypen.

Als Gegenleistung für diesen Schnelligkeitstreffer erhalten Sie die Möglichkeit, jede Art von Grammatik zu analysieren , auch mehrdeutige. Dies bedeutet, dass Sie sich keine Gedanken machen müssen, ob Ihr Parser eine Linksrekursion enthält oder was ein Konflikt zur Reduzierung der Schicht ist. Sie können Grammatiken auch einfacher mit mehrdeutigen Grammatiken definieren, wenn es nicht darauf ankommt, welcher Analysebaum das Ergebnis ist. So spielt es keine Rolle, ob Sie 1 + 2 + 3 als (1 + 2) +3 oder als 1 analysieren + (2 + 3).

So kann ein Teil des Codes mit meinem Parsergenerator aussehen:

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(Beachten Sie, dass IntWrapper einfach ein Int32 ist, mit der Ausnahme, dass C # dies als Klasse erfordert. Daher musste ich eine Wrapper-Klasse einführen.)

Ich hoffe, Sie sehen, dass der obige Code sehr mächtig ist: Jede Grammatik, die Ihnen einfällt, kann analysiert werden. Sie können der Grammatik beliebige Codebits hinzufügen, die viele Aufgaben ausführen können. Wenn Sie alles zum Laufen bringen, können Sie den resultierenden Code sehr einfach wiederverwenden, um viele Aufgaben zu erledigen: Stellen Sie sich vor, Sie erstellen einen Befehlszeileninterpreter mit diesem Code.

Alex ten Brink
quelle
3
Ich denke, Sie unterschätzen den Arbeitsaufwand, der erforderlich ist, um einen leistungsstarken Parser und Lexer zu erstellen.
Ich habe bereits meinen eigenen Lexer-Generator fertiggestellt und war ziemlich weit davon entfernt, meinen eigenen Parser-Generator zu erstellen, als ich mich entschied, stattdessen einen anderen Algorithmus zu implementieren. Ich habe nicht so lange gebraucht, um alles zum Laufen zu bringen, aber ich habe auch nicht auf "hohe Leistung", sondern nur auf "gute Leistung" und "hervorragende asymptotische Leistung" gesetzt - Unicode ist eine Hündin, für die ich gute Laufzeiten habe und die Verwendung von C # verursacht bereits einen Performance-Overhead.
Alex ten Brink
Sehr nette Antwort. Ich stimme Ihrer Option Nr. 3 aus all den Gründen, die Sie oben angegeben haben. Aber ich kann hinzufügen, dass, wenn Sie, wie in meinem Fall, auch sehr ernsthaft eine Sprache entwerfen, Sie vielleicht auch Parser-Generatoren verwenden sollten, während Sie versuchen, Ihre eigenen zu erstellen. So haben Sie einen Vorsprung vor den Sprachproblemen und können Ihre Sprache schneller in Aktion sehen
Lefteris,
1
Es gibt eine vierte Option: Parser-Kombinatoren.
YuriAlbuquerque
@AlextenBrink Hast du zufällig einen Github-Account? Ich möchte diesen Lexer / Parser wirklich in die Hände bekommen. Beeindruckende Sache, die Sie gemacht haben.
Behrooz
22

Wenn Sie noch nie einen Parser geschrieben haben, würde ich Ihnen empfehlen, dies zu tun. Es macht Spaß, und Sie lernen, wie die Dinge funktionieren, und Sie schätzen den Aufwand, den Parser- und Lexer-Generatoren leisten, um Sie davon abzuhalten, wenn Sie das nächste Mal einen Parser benötigen.

Ich würde auch vorschlagen, dass Sie versuchen, http://compilers.iecc.com/crenshaw/ zu lesen, da es eine sehr bodenständige Haltung dazu hat.


quelle
2
Guter Vorschlag und ein sehr nützlicher Link.
Maniero
14

Der Vorteil des Schreibens eines eigenen rekursiven Abstiegsparsers besteht darin, dass Sie bei Syntaxfehlern qualitativ hochwertige Fehlermeldungen generieren können. Mit Parser-Generatoren können Sie an bestimmten Stellen Fehlerproduktionen durchführen und benutzerdefinierte Fehlermeldungen hinzufügen, aber Parser-Generatoren sind einfach nicht so leistungsfähig, dass Sie die vollständige Kontrolle über das Parsing haben.

Ein weiterer Vorteil des eigenen Schreibens besteht darin, dass es einfacher ist, eine einfachere Darstellung zu analysieren, die keine Eins-zu-Eins-Entsprechung zu Ihrer Grammatik aufweist.

Wenn Ihre Grammatik repariert ist und Fehlermeldungen wichtig sind, sollten Sie Ihre eigene rollen oder zumindest einen Parser-Generator verwenden, der Ihnen die benötigten Fehlermeldungen liefert. Wenn sich Ihre Grammatik ständig ändert, sollten Sie stattdessen Parsergeneratoren verwenden.

Bjarne Stroustrup spricht darüber, wie er YACC für die erste Implementierung von C ++ verwendet hat (siehe Das Design und die Entwicklung von C ++ ). In diesem ersten Fall wünschte er sich, er hätte stattdessen seinen eigenen rekursiven Abstiegsparser geschrieben!

Macneil
quelle
Ich bin kaum davon überzeugt, dass die ersten Experimente mit einem Parsergenerator durchgeführt werden sollten. Sie gaben mir einige Vorteile, um zu einer kundenspezifischen Lösung zu wechseln. Ich entscheide noch nichts, aber es ist eine nützliche Antwort, um mir zu helfen.
Maniero
++ Diese Antwort ist genau das, was ich sagen würde. Ich habe zahlreiche Sprachen aufgebaut und fast immer rekursive Abstammung verwendet. Ich möchte nur hinzufügen, dass es Zeiten gab, in denen die von mir benötigte Sprache am einfachsten durch Überlagern einiger Makros auf C oder C ++ (oder Lisp) erstellt wurde.
Mike Dunlavey
JavaCC soll die besten Fehlermeldungen haben. Beachten Sie auch die JavaScript-Fehler- und Warnmeldungen unter V8 und Firefox. Ich glaube, sie haben keine Parser-Generatoren verwendet.
Ming-Tang,
2
@SHiNKiROU: In der Tat ist es wahrscheinlich kein Zufall, dass JavaCC auch rekursives Abstiegsparsing verwendet.
Macneil,
10

Option 3: Weder noch (Roll deinen eigenen Parser-Generator)

Nur weil es gibt einen Grund , nicht zu verwenden ANTLR , Bison , Coco / R , Grammatica , JavaCC , Zitrone , Parboiled , SableCC , Quex , etc - das bedeutet nicht , dass Sie sofort Ihren eigenen Parser + Lexer rollen sollte.

Finden Sie heraus, warum all diese Tools nicht gut genug sind. Warum können Sie damit Ihr Ziel nicht erreichen?

Sofern Sie nicht sicher sind, dass die Kuriositäten in der Grammatik, mit der Sie zu tun haben, eindeutig sind, sollten Sie nicht nur einen einzigen benutzerdefinierten Parser + Lexer dafür erstellen. Erstellen Sie stattdessen ein Tool, mit dem Sie erstellen können, was Sie möchten, das Sie aber auch für zukünftige Anforderungen verwenden können. Geben Sie es dann als freie Software frei, um zu verhindern, dass andere Benutzer das gleiche Problem haben wie Sie.

Peter Boughton
quelle
1
Ich bin damit einverstanden, zuerst Parser-Generatoren zu testen und dann eine benutzerdefinierte Lösung zu versuchen, aber welche spezifischen (Dis-) Vorteile? Dies ist fast ein allgemeiner Ratschlag.
Maniero
1
Es ist ein allgemeiner Rat - aber dann haben Sie eine allgemeine Frage gestellt. : P Ich werde es morgen um einige spezifischere Gedanken zu Vor- und Nachteilen erweitern.
Peter Boughton
1
Ich denke, Sie unterschätzen den Arbeitsaufwand, der zum Erstellen eines benutzerdefinierten Parsers und Lexers erforderlich ist. Besonders wiederverwendbar.
8

Wenn Sie Ihren eigenen Parser rollen, müssen Sie direkt über die Komplexität Ihrer Sprache nachdenken. Wenn die Sprache schwer zu analysieren ist, wird sie wahrscheinlich schwer zu verstehen sein.

In den Anfängen gab es großes Interesse an Parser-Generatoren, motiviert durch hochkomplizierte (manche würden sagen "gequält") Sprachsyntax. JOVIAL war ein besonders schlechtes Beispiel: Es erforderte einen Lookahead mit zwei Symbolen, zu einer Zeit, in der alles andere höchstens ein Symbol erforderte. Dies machte es schwieriger als erwartet, den Parser für einen JOVIAL-Compiler zu generieren (wie die Division General Dynamics / Fort Worth lernte, als sie JOVIAL-Compiler für das F-16-Programm beschaffte).

Rekursives Absteigen ist heute allgemein die bevorzugte Methode, da es für Compiler-Autoren einfacher ist. Compiler für rekursive Herkunft belohnen einfache, übersichtliche Sprachentwürfe, da es viel einfacher ist, einen Parser für rekursive Herkunft für eine einfache, übersichtliche Sprache zu schreiben, als für eine verschlungene, unübersichtliche Sprache.

Zum Schluss: Haben Sie darüber nachgedacht, Ihre Sprache in LISP einzubetten und einen LISP-Dolmetscher die schwere Aufgabe für Sie übernehmen zu lassen? AutoCAD hat dies getan und festgestellt, dass es ihnen das Leben erheblich erleichtert hat. Es gibt eine ganze Reihe leichter LISP-Interpreter, von denen einige eingebettet werden können.

John R. Strohm
quelle
Es ist ein interessantes Argument, eine benutzerdefinierte Lösung zu entwickeln.
Maniero
1
Sehr schön. Ich möchte nur als Informationsquelle hinzufügen, dass Fortran vor dem JOVIAL einen fast willkürlichen (gesamten Zeilen-) Lookahead benötigte, um die Dinge zu analysieren. Zu dieser Zeit hatten sie jedoch keine andere Idee, wie sie eine Sprache erstellen (oder implementieren) sollten.
Macneil
Gehen ist das beste Transportmittel, da Sie Zeit haben, sich zu überlegen, ob es sich wirklich lohnt, dorthin zu gehen, wohin Sie gehen. Es ist auch gesund.
Babou
6

Ich habe einmal einen Parser für kommerzielle Anwendungen geschrieben und yacc verwendet . Es gab einen konkurrierenden Prototyp, bei dem ein Entwickler das Ganze in C ++ von Hand schrieb und es ungefähr fünfmal langsamer funktionierte.

Das Lexer für diesen Parser habe ich komplett von Hand geschrieben. Es dauerte - sorry, das war vor fast 10 Jahren, so dass ich es nicht genau erinnern - etwa 1000 Zeilen in C .

Der Grund, warum ich den Lexer von Hand schrieb, war die Eingabe-Grammatik des Parsers. Dies war eine Anforderung, die meine Parser-Implementierung erfüllen musste, im Gegensatz zu etwas, das ich entworfen hatte. (Natürlich hätte ich es anders entworfen. Und besser!) Die Grammatik war stark kontextabhängig, und an einigen Stellen hing sogar das Lexieren von der Semantik ab. Beispielsweise könnte ein Semikolon Teil eines Tokens an einer Stelle sein, aber ein Trennzeichen an einer anderen Stelle - basierend auf einer semantischen Interpretation eines Elements, das zuvor analysiert wurde. Also habe ich solche semantischen Abhängigkeiten im handgeschriebenen Lexer "begraben" und das hat mich mit einer ziemlich einfachen BNF zurückgelassen , die einfach in yacc zu implementieren war.

ADDED als Antwort auf Macneil : yacc bietet eine sehr leistungsfähige Abstraktion, mit der der Programmierer über Terminals, Nicht-Terminals, Produktionen und ähnliches nachdenken kann. Außerdem hat yylex()es mir bei der Implementierung der Funktion geholfen, mich auf die Rückgabe des aktuellen Tokens zu konzentrieren und mir keine Gedanken darüber zu machen, was davor oder danach war. Der C ++ - Programmierer arbeitete auf der Zeichenebene ohne den Vorteil einer solchen Abstraktion und entwickelte einen komplizierteren und weniger effizienten Algorithmus. Wir kamen zu dem Schluss, dass die langsamere Geschwindigkeit nichts mit C ++ selbst oder irgendwelchen Bibliotheken zu tun hat. Wir haben die reine Parsing-Geschwindigkeit mit Dateien gemessen, die in den Speicher geladen wurden. Wenn wir ein Problem mit der Dateipufferung hätten, wäre yacc nicht das Werkzeug unserer Wahl, um es zu lösen.

AUCH HINZUFÜGEN : Dies ist kein Rezept zum Schreiben von Parsern im Allgemeinen, sondern nur ein Beispiel dafür, wie es in einer bestimmten Situation funktioniert hat.

Azheglov
quelle
Ich bin gespannt auf die fünfmal langsamere C ++ - Implementierung von Hand: Vielleicht war es eine schlechte Dateipufferung? Es kann einen großen Unterschied machen.
Macneil
@ Macneil: Ich werde eine Ergänzung zu meiner Antwort posten. Der Kommentar ist zu lang.
Azheglov
1
++ Gute Erfahrung. Ich würde nicht zu viel Gewicht auf die Leistung legen. Es ist einfach für ansonsten gute Programme, durch etwas Dummes und Unnötiges gebremst zu werden. Ich habe genug rekursiv absteigende Parser geschrieben, um zu wissen, was nicht zu tun ist, und bezweifle, dass es etwas viel schnelleres gibt. Immerhin müssen die Zeichen gelesen werden. Ich vermute, dass Parser, die von den Tischen runterlaufen, etwas langsamer sind, aber wahrscheinlich nicht genug, um es zu bemerken.
Mike Dunlavey
3

Das hängt ganz davon ab, was Sie analysieren müssen. Können Sie Ihre eigenen schneller rollen, als Sie die Lernkurve eines Lexers erreichen könnten? Ist das zu analysierende Zeug statisch genug, dass Sie die Entscheidung später nicht bereuen werden? Finden Sie bestehende Implementierungen zu komplex? Wenn ja, dann viel Spaß beim Selberdrehen, aber nur, wenn Sie keine Lernkurve durchgehen.

In letzter Zeit habe ich den Zitronenparser wirklich gemocht , der wohl der einfachste und einfachste ist, den ich je benutzt habe. Um die Wartung zu vereinfachen, benutze ich das für die meisten Anforderungen. SQLite verwendet es ebenso wie einige andere bemerkenswerte Projekte.

Aber ich interessiere mich überhaupt nicht für Lexer, außer dass sie mir nicht in die Quere kommen, wenn ich einen verwenden muss (daher Zitrone). Vielleicht bist du es und wenn ja, warum machst du es nicht? Ich habe das Gefühl, dass Sie wieder eine verwenden werden, die es gibt, aber kratzen Sie den Juckreiz, wenn Sie müssen :)

Tim Post
quelle
3
+1 für "Kannst du deine eigenen schneller würfeln, als du die Lernkurve eines Lexers erreichen könntest?"
Bobah
Ja, guter Punkt.
Maniero
3

Es kommt darauf an, was Ihr Ziel ist.

Versuchen Sie zu lernen, wie Parser / Compiler funktionieren? Dann schreiben Sie Ihre eigenen von Grund auf neu. Nur so lernst du wirklich, all das zu schätzen, was sie tun. Ich habe in den letzten paar Monaten eine geschrieben, und es war eine interessante und wertvolle Erfahrung, insbesondere das 'ah, deshalb macht Sprache X das ...' Momente.

Müssen Sie für eine Bewerbung kurzfristig etwas zusammenstellen? Dann verwenden Sie vielleicht ein Parser-Tool.

Benötigen Sie etwas, das Sie in den nächsten 10, 20, vielleicht sogar 30 Jahren erweitern möchten? Schreiben Sie Ihre eigenen und nehmen Sie sich Zeit. Es wird sich lohnen.

GroßmeisterB
quelle
Es ist meine erste Arbeit an Compilern, ich lerne / experimentiere und es ist meine Absicht, sie für lange, lange Zeit aufrechtzuerhalten.
Maniero
3

Haben Sie über den Ansatz der Martin Fowlers Language Workbench nachgedacht ? Zitat aus dem Artikel

Die offensichtlichste Änderung, die eine Sprachumgebung an der Gleichung vornimmt, ist die einfache Erstellung externer DSLs. Sie müssen keinen Parser mehr schreiben. Sie müssen die abstrakte Syntax definieren - aber das ist eigentlich ein ziemlich einfacher Schritt zur Datenmodellierung. Außerdem erhält Ihr DSL eine leistungsstarke IDE - obwohl Sie einige Zeit damit verbringen müssen, diesen Editor zu definieren. Der Generator ist immer noch etwas, was Sie tun müssen, und ich habe das Gefühl, dass es nicht viel einfacher ist als jemals zuvor. Aber dann ist der Bau eines Generators für ein gutes und einfaches DSL einer der einfachsten Teile der Übung.

Wenn ich das lese, würde ich sagen, dass die Tage, in denen Sie Ihren eigenen Parser geschrieben haben, vorbei sind und es besser ist, eine der verfügbaren Bibliotheken zu verwenden. Sobald Sie die Bibliothek gemeistert haben, profitieren alle DSLs, die Sie in Zukunft erstellen, von diesem Wissen. Auch müssen andere nicht Ihre Herangehensweise an das Parsen lernen.

Bearbeiten, um Kommentar abzudecken (und überarbeitete Frage)

Vorteile des eigenen Rollens

  1. Sie werden den Parser besitzen und all die schöne Erfahrung sammeln, eine komplizierte Reihe von Problemen zu durchdenken
  2. Möglicherweise fällt Ihnen etwas Besonderes ein, an das noch niemand gedacht hat (unwahrscheinlich, aber Sie scheinen ein kluger Kerl zu sein).
  3. Es wird Sie mit einem interessanten Problem beschäftigen

Kurz gesagt, Sie sollten Ihre eigenen Rollen spielen, wenn Sie wirklich tief in die Eingeweide eines ernsthaft schwierigen Problems eindringen möchten, für dessen Bewältigung Sie sich stark motiviert fühlen.

Vorteile der Verwendung der Bibliothek eines anderen Benutzers

  1. Sie werden es vermeiden, das Rad neu zu erfinden (ein häufiges Problem bei der Programmierung, dem Sie zustimmen werden)
  2. Sie können sich auf das Endergebnis konzentrieren (Ihre neue, glänzende Sprache) und müssen sich nicht zu viele Gedanken darüber machen, wie es analysiert wird usw
  3. Sie werden Ihre Sprache viel schneller in Aktion sehen (aber Ihre Belohnung wird weniger sein, weil Sie es nicht waren)

Wenn Sie also ein schnelles Endergebnis erzielen möchten, verwenden Sie die Bibliothek eines anderen Benutzers.

Insgesamt hängt dies davon ab, inwieweit Sie das Problem und damit die Lösung besitzen möchten. Wenn Sie alles wollen, dann rollen Sie Ihre eigenen.

Gary Rowe
quelle
Es ist eine großartige Alternative zum Denken.
Maniero
1
@bigown Bearbeitet, um Ihre Frage besser zu beantworten
Gary Rowe
2

Der große Vorteil beim Schreiben von eigenen Texten ist, dass Sie wissen, wie man eigene Texte schreibt. Der große Vorteil bei der Verwendung eines Tools wie yacc ist, dass Sie wissen, wie man das Tool verwendet. Ich bin ein Fan von Baumwipfeln für erste Erkundungen.

philosodad
quelle
Nicht besonders hilfreich. Sie hätten genauso gut sagen können: „Der Vorteil des Fahrlernens ist, dass Sie fahren können. Das Fahrradfahren zu lernen hat den Vorteil, dass man Fahrrad fahren kann. “
Zearin,
1

Warum nicht einen Open-Source-Parser-Generator ausgeben und selbst erstellen? Wenn Sie keine Parser-Generatoren verwenden, ist Ihr Code sehr schwer zu pflegen, wenn Sie die Syntax Ihrer Sprache stark geändert haben.

In meinen Parsern habe ich reguläre Ausdrücke (ich meine, Perl-Stil) zum Token verwendet und einige praktische Funktionen verwendet, um die Lesbarkeit des Codes zu verbessern. Ein von einem Parser generierter Code kann jedoch schneller sein, indem Sie Statustabellen und long switch- cases erstellen, wodurch der Quellcode möglicherweise vergrößert wird, sofern Sie dies nicht .gitignoretun.

Hier sind zwei Beispiele für meine benutzerdefinierten Parser:

https://github.com/SHiNKiROU/DesignScript - ein BASIC-Dialekt. Da ich zu faul war, um Lookaheads in Array-Notation zu schreiben, habe ich die Qualität von Fehlermeldungen geopfert. https://github.com/SHiNKiROU/ExprParser - Ein Formelrechner. Beachten Sie die seltsamen Metaprogrammier-Tricks

Ming-Tang
quelle
0

"Soll ich dieses bewährte" Rad "verwenden oder neu erfinden?"

JBRWilkinson
quelle
1
Von was für einem "Rad" sprichst du? ;-)
Jason Whitehorn
IMO ist dies keine gute Meinung zu dieser Frage. Dies ist nur ein allgemeiner Rat, der für den jeweiligen Fall nicht geeignet ist. Ich vermute, dass der Vorschlag für area51.stackexchange.com/proposals/7848 vorzeitig geschlossen wurde.
Maniero
2
Wenn das Rad nie neu erfunden worden wäre, würden wir nicht täglich mit über 100 km / h fahren - es sei denn, Sie schlagen vor, dass große, schwere Felsbrocken, die sich auf Holzachsen drehen, besser sind als die vielen Varianten moderner Reifen, die in verwendet werden so viele Fahrzeuge?
Peter Boughton
Das ist eine gültige Meinung und es ist die richtige Intuition. Ich denke, diese Antwort könnte hilfreicher sein, wenn Sie bestimmte Vor- oder Nachteile auflisten könnten, da dies völlig von den Umständen abhängt.
Macneil
@Peter: Es ist eine Sache, etwas neu zu erfinden (impliziert, es völlig anders zu machen), aber eine vorhandene Lösung zu verfeinern, um zusätzliche Anforderungen zu erfüllen, ist besser. Ich bin alle für 'Verbesserung', aber für ein bereits gelöstes Problem zum Zeichenbrett zurückzukehren, scheint falsch.
JBRWilkinson