Lexer/Parser zum Erzeugen von Scala-Code aus BNF-Grammatik

Question

Ich bin derzeit auf der Suche nach einem Lexer/Parser, der Scala-Code aus einer BNF-Grammatik (eine ocamlyacc Datei mit Vorrang und Assoziativität) generiert. Ich bin ziemlich verwirrt, da ich fast nichts darüber gefunden habe.

Zum Parsen fand ich scala-bison (mit denen ich viel Mühe habe zu arbeiten). Alle anderen Tools sind nur Java-Parser, die in Scala importiert werden (wie ANTLR).

Für Lexing habe ich nichts gefunden.

Ich fand auch die berühmte Parser von Scala Kombinatoren, aber (korrigiert mich wenn ich falsch liege), auch wenn sie recht ansprechend sind, sie viel Zeit und Speicher verbrauchen, vor allem wegen Rückzieher. So

Ich habe zwei Hauptfragen:

• Warum scheinen die Menschen nur auf _parser combinators zu konzentrieren?
• Was ist Ihr bester Lexer/Parser Generator Vorschlag mit Scala zu verwenden?

Answer 1

Als einer der Autoren des ScalaBison-Papiers bin ich auf dieses Problem ein paar Mal gestoßen. :-) Was ich normalerweise zum Scannen in Scala tun würde, ist JFlex. Es funktioniert erstaunlich gut mit ScalaBison, und all unser Benchmarking wurde mit dieser Kombination durchgeführt. Der unglückliche Nachteil ist, dass es Java-Quellen generiert, und so braucht die Kompilation ein bisschen Gymnastik. Ich glaube, dass John Boyland (der Hauptautor des Artikels) einen Scala-Ausgabemodus für JFlex entwickelt hat, aber ich glaube nicht, dass es öffentlich veröffentlicht wurde.

Für meine eigene Entwicklung habe ich viel mit scannerlosen Analysetechniken gearbeitet. Die Packrat-Parser-Kombinatoren von Scala 2.8 sind ziemlich gut, aber noch nicht verallgemeinert. Ich habe an experimental library gebaut, die verallgemeinerte Parsing innerhalb des Parser-Kombinator-Framework implementiert. Seine asymptotischen Grenzen sind viel besser als herkömmliche Parser-Kombinatoren, aber in der Praxis ist der konstante Zeitaufwand höher (ich arbeite immer noch daran).

Answer 2

Scala 2.8 hat einen Packrat-Parser. Ich zitiere aus der API-Dokumentation hier:

Packrat Parsing eine Technik zur Implementierung Rückzieher ist, rekursiven Abstieg Parser, mit dem Vorteil, dass sie unbegrenzt Look-Ahead und eine lineare Analysezeit garantiert. Mit dieser Technik können auch links rekursive Grammatiken akzeptiert werden.

Answer 3

Ich weiß, dass diese Frage alt ist, aber für diejenigen immer noch auf der Suche nach einem Lexer-Generator, der Scala-Code ausgibt, habe ich geschrieben a fork of JFlex that emits Scala anstatt Java, einschließlich der entsprechenden Maven und sbt-Plugins. Alle sind jetzt auf Maven Central verfügbar.

Wir verwenden es zur Zeit (einschließlich der Maven/sbt Plugins) englischen Text als Teil der Verarbeitung natürlicher Sprache pipline in FACTORIE tokenize - Beispiel Scala here enthält .flex Datei.