Was ist der kürzeste Weg, Parser für meine Sprache zu schreiben?

Es ist immer eine gute Idee, das Drachenbuch zu lesen. Aber sei dir bewusst, dass es, wenn deine Sprache nicht trivial ist, keine "kurze" Möglichkeit gibt, dies zu tun.

Zusammenfassung: die kürzeste ist wahrscheinlich Antlr.

Es ist verlockend, zum Dragon Book zu gehen, um etwas über die Parsing-Theorie zu lernen. Aber ich glaube nicht, dass das Drachenbuch und du die gleiche Vorstellung davon haben, was "Theorie" bedeutet. Das Dragon Book beschreibt, wie man handgeschriebene Parser, Parser-Generatoren, usw. erstellt, aber Sie wollen mit Sicherheit stattdessen ein Parser-Generierungs-Tool verwenden.

Einige Leute haben Bison und Flex (oder ihre älteren Versionen Yacc und Lex) vorgeschlagen. Das sind die alten Stalwarts, aber sie sind nicht sehr brauchbare Werkzeuge. Ihre Dokumentation ist nicht per se schlecht, nur dass sie nicht hilft, mit der versehentlichen Komplexität , sie zu benutzen. Ihre internen Daten sind nicht gut gekapselt, und es ist sehr schwierig, etwas mit ihnen voranzutreiben. Als Beispiel haben wir in phc immer noch keine korrekten Zeilennummern, da dies sehr schwierig ist. Sie sind besser geworden, als wir die Grammatik so modifiziert haben, dass sie No-Op-Anweisungen enthalten, aber das ist ein unglaublicher Hack, der nicht nötig sein sollte.

Scheinbar arbeiten Bison und Flex zusammen, aber die Schnittstelle ist peinlich. Schlimmer noch, es gibt viele Versionen von jedem, die nur gut mit einigen spezifischen Versionen des anderen spielen. Und zuletzt habe ich zumindest nachgeprüft, welche Dokumentation mit welchen Versionen ging, war ziemlich schlecht.

Das Schreiben eines rekursiven Sink-Parsers ist einfach, kann aber mühsam sein. Antlr kann das für Sie tun, und es scheint ein ziemlich gutes Toolset zu sein, mit dem Vorteil, dass das, was Sie in diesem Projekt lernen, auf viele andere Sprachen und Plattformen angewendet werden kann (Antlr ist sehr portabel). Es gibt auch viele existierende Grammatiken, von denen man lernen kann.

Es ist nicht klar, in welcher Sprache Sie arbeiten, aber einige Sprachen haben ausgezeichnete Parsing-Frameworks. Insbesondere scheint die Haskell Parsec Bibliothek sehr elegant zu sein. Wenn Sie C ++ verwenden, könnten Sie versucht sein, Spirit zu verwenden. Ich fand es sehr einfach, damit anzufangen, und schwierig - aber immer noch möglich - fortgeschrittene Dinge damit zu machen. Dies entspricht meiner Erfahrung mit C ++ im Allgemeinen. Ich sage, dass ich es einfach fand, zu beginnen, aber dann hatte ich bereits ein paar Parser geschrieben und studierte Parsing in der Compiler-Klasse.

Lange Rede kurzer Sinn: Antlr, es sei denn, Sie haben einen sehr guten Grund.

Es hängt eher von Ihrer Sprache ab. Einige sehr einfache Sprachen benötigen sehr wenig Parsing, so dass sie von Hand kodiert werden können; andere Sprachen verwenden PEG-Generatoren wie Rats! (PEG ist eine Parser-Ausdrucksgrammatik, die zwischen einem Regex und einem ein LR-Parser) oder herkömmliche Parser-Generatoren wie Antlr und Yacc. Weniger formale Sprachen erfordern probabilistische Techniken wie Linkgrammatiken .

Schreiben Sie einen Rekursiven Descent-Parser . Dies ist manchmal einfacher als YACC / BISON und normalerweise intuitiver.

Douglas Crockford hat ein zugängliches Beispiel eines in JavaScript geschriebenen Parsers .

YACC , es gibt verschiedene Implementierungen für verschiedene Sprachen.

Viel Glück mit Ihrer Sprache; -)

Ich habe das GOLD Parsing System verwendet, weil es einfacher zu benutzen war als ANTLR für einen Anfänger wie mich, obwohl es immer noch so ist ausreichend voll für meine Bedürfnisse. Die Website enthält Dokumentation (einschließlich einer Anleitung zu Schreiben von Grammatiken , was die halbe Arbeit ist) sowie Software .

Die Verwendung eines Parser-Generators für Ihre Host-Sprache ist der schnellste Weg, kombiniert mit der Parsing-Theorie aus einem Buch wie dem Dragon Book oder der Modern Compiler Construction in der {C, ML} Serie.

Wenn Sie C verwenden, sind yacc und die GNU-Version bison die Standardgeneratoren. Antlr ist in vielen Sprachen weit verbreitet und unterstützt, soweit ich weiß, Java, C # und C ++. Es gibt auch viele andere in fast jeder Sprache.

Mein persönlicher Favorit ist derzeit Menhir , ein exzellenter Parser-Generator für OCaml. ML-Stil-Sprachen (Ocaml, Standard ML, etc.) Dialekte im Allgemeinen sind sehr gut für die Erstellung von Compilern und Dolmetscher.