Wie implementiere ich Referenzen in einem Compiler nach vorn?

Question

Ich erstelle einen Compiler mit Lex und YACC (eigentlich Flex und Bison). Die Sprache ermöglicht die uneingeschränkte Vorwärts Verweise auf jedes Symbol (wie C #). Das Problem ist, dass es die Sprache zu analysieren, ohne zu wissen, was eine Kennung ist.

unmöglich

Die einzige Lösung, die ich kenne, ist die gesamte Quelle lex, und dann tun bekommen analysiert eine „Breite-first“ analysieren, so höhere Ebene Dinge wie Klassendeklarationen und Funktionsdeklarationen, bevor die Funktionen, die sie benutzen. Allerdings würde dies eine große Menge an Speicher für große Dateien, und es wäre schwierig, mit YACC zu behandeln (ich würde für jede Art von Erklärung / Körper getrennt Grammatiken erstellen haben). Ich würde auch die Lexer Hand schreiben muß (was nicht so sehr ein Problem ist).

Ich interessiere mich nicht eine ganze Menge über die Effizienz (obwohl es nach wie vor wichtig ist), weil ich den Compiler selbst neu zu schreiben werde, sobald ich es fertig, aber ich mag diese Version schnell sein (also, wenn es alle schnell allgemeine Techniken, die in Lex / YACC getan werden kann, nicht aber von Hand gemacht werden, schlagen sie bitte auch). So jetzt, einfache Entwicklung ist der wichtigste Faktor.

Gibt es gute Lösungen für dieses Problem? Wie wird dies in der Regel in Compiler für Sprachen wie C # getan oder Java?

Answer 1

Es ist durchaus möglich, es zu analysieren. Zwar gibt es eine Mehrdeutigkeit zwischen Identifikatoren und Schlüsselwörtern, wird lex glücklich damit fertig, indem Sie die Keywords Priorität zu geben.

Ich sehe nicht, was andere Probleme gibt. Sie brauchen nicht zu bestimmen, ob Bezeichner gültig während des Parsing-Stadiums sind. Sie bauen entweder einen Parse-Baum oder einen abstrakten Syntaxbaum (der Unterschied ist subtil, aber irrelevant für die Zwecke dieser Diskussion), wie Sie analysieren. Danach können Sie Ihre verschachtelte Symboltabelle Strukturen aufzubauen, indem ein Durchgang über den AST Führen Sie während des Parse erzeugt. Dann machen Sie einen weiteren Durchgang über den AST zu prüfen, ob verwendeten Bezeichner gültig sind. Folgen Sie dieser mit einem oder mehreren zusätzlichen Parsen über die AST den Ausgangscode zu erzeugen oder eine andere Zwischendatenstruktur und fertig!

EDIT: Wenn Sie sehen wollen, wie es gemacht wird, überprüfen Sie den Quellcode für die Mono C # Compiler. Dies wird tatsächlich in C # geschrieben und nicht in C oder C ++, aber es funktioniert .NET Hafen von Jay verwenden, die zu yacc sehr ähnlich ist.

Answer 2

Eine Möglichkeit ist, mit Vorwärtsreferenzen nur durch Scannen und Caching-Token zu tun, bis Sie etwas getroffen Sie wissen, wie man real mit (Art wie „Panik-Modus“ Fehlerkorrektur). Sobald Sie die vollständige Datei gedacht ausgeführt haben, gehen Sie zurück und versuchen, die Bits erneut zu analysieren, die nicht vor dem Parsen hat.

In Bezug auf mit der Lexer Hand schreiben; nicht, verwendet lex einen normalen Parser zu erzeugen und nur von ihm über eine handgeschriebene Shim gelesen, dass man von einem Cache zurück und speist die Parser kann als auch, was lex macht.

In Bezug auf mehrere Grammatiken zu machen, einen wenig Spaß mit einem Prä-Prozessor auf der yacc-Datei und Sie sollen in der Lage sein, sie alle aus derselben Quelle zu machen