Bison-Grammatik, die jedes Präfix einer definierten Sprache akzeptiert

Ich versuche, einen Parser für Haskell-Sprache mit dem zusätzlichen Vorbehalt zu schreiben, dass das geparste Programm jedes Präfix eines gültigen Haskell-Quellcodes sein kann.Bison-Grammatik, die jedes Präfix einer definierten Sprache akzeptiert

Zum Beispiel ist dies gültige Quelle in meinem Fall:

func x = (x +

Es gibt eine BNF-ähnliche Spezifikation für Haskell hier: https://www.haskell.org/onlinereport/syntax-iso.html#sect9.5.

Gibt es eine schematische Möglichkeit, BNF-Grammatik in eine Bison-Grammatik zu konvertieren, die eine solche Präfix-Sprache akzeptiert?

Der Kontext dieser Übung ist Emacs Editor und Quellcode ist Programm geschrieben, das Ziel ist es, Einrückungshinweise zu geben, wie der Programmierer den Quellcode schreibt.

Quelle

2016-04-09 Gracjan Polak

Es ist ziemlich geradlinig eine CFG zu nehmen und es in eine CFG für die Sprache zu verwandeln, die alle Präfixe matches:

für jeden Nicht-Terminal, eine zusätzliche -prefix Version des nicht hinzufügen
Terminal
für jede Regel der Form X := A B C, fügen Sie Regeln der Form X_prefix := A B C_prefix | A B | A B_prefix | A | A_prefix
alle Regeln löschen, die auf terminal_prefix beziehen, und dann recursivel y für Y_prefix wo Y_prefix hat keine Regeln übrig.

Natürlich ist diese neue CFG vielleicht nicht LALR (1), so kann nicht einfach direkt von Bison verwendet werden - Sie müssen es Refactoring, um es LALR zu machen (1), oder ein GLR verwenden Parser mit entsprechenden Zusammenführungsregeln.

Quelle

2016-04-09 23:03:03

Sieht wie eine gute Idee aus. Wir sollten irgendwie alle diese XX_prefix Produktionen zurückgeben? –

Was auch immer Sie wollen, dass sie zurückkehren - der grundlegende shift-reduce Parser erkennt nur, ob eine Zeichenkette in der beschriebenen Sprache ist oder nicht. Sie können die semantischen Informationen von bison verwenden, um einen AST zu erstellen, der dem Parse entspricht, oder jede andere gewünschte Datenstruktur. –

Dies beantwortet meine Frage so die Antwort angenommen. Es ist mir immer noch unklar, was ich von diesen _prefix-Regeln zurückbekomme, aber das ist ein Thema für eine andere Forschung. Danke. –

Bison-Grammatik, die jedes Präfix einer definierten Sprache akzeptiert

Antwort

Verwandte Themen