Schreiben eines Compilers Compiler - Einblick in Verwendung und Funktionen

Dies ist Teil einer Reihe von Fragen, die sich auf das Schwesterprojekt des Abstraktionsprojekts konzentrieren, das darauf abzielt, die im Sprachdesign verwendeten Konzepte in Form eines Frameworks zu abstrahieren. Das Schwesterprojekt heißt OILexer und zielt darauf ab, einen Parser aus Grammatikdateien ohne die Verwendung von Code-Injection für Übereinstimmungen zu erstellen.

Einige andere Seiten zu diesen Fragen, die sich auf die strukturelle Typisierung beziehen, können hier angezeigt werden . Die Benutzerfreundlichkeit finden Sie hier . Das Meta-Thema, das mit einer Anfrage zum Framework und dem richtigen Ort zum Posten verbunden ist, finden Sie hier .

Ich komme zu dem Punkt, an dem ich anfangen werde, den Analysebaum aus einer bestimmten Grammatik zu extrahieren, gefolgt von einem Parser für rekursiven Abstieg, der DFA verwendet, um Vorwärtspfade zu erkennen (ähnlich wie bei LL (*) von ANTLR 4) Ich dachte, ich würde es öffnen, um einen Einblick zu bekommen.

Welche Funktionen sind in einem Parser-Compiler ideal?

Bisher gibt es hier einen kurzen Überblick über die Implementierung:

1. Vorlagen
2. Schauen Sie voraus, um zu wissen, was an einem bestimmten Punkt gültig ist.
3. Regel 'Deliteralisierung', bei der die Literale in Regeln übernommen und aufgelöst werden, von welchem ​​Token sie stammen.
4. Nichtdeterministische Automaten
5. Deterministische Automaten
6. Einfache lexikalische Zustandsmaschine zur Tokenerkennung
7. Methoden zur Token-Automatisierung:
   • Scan - nützlich für Kommentare: Kommentar: = "/ *" Scan ("* /");
   • Subtrahieren - Nützlich für Bezeichner: Bezeichner: = Subtrahieren (IdentifierBody, Schlüsselwörter);
     • Stellt sicher, dass der Bezeichner keine Schlüsselwörter akzeptiert.
   • Codieren - Codiert eine Automatisierung als eine Reihe X der Anzahl der Basis-N-Übergänge.
     • UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
       • Lässt ein Unicode hexadezimal mit hexadezimalen 4-Übergängen entkommen. Der Unterschied zwischen diesem und: [0-9A-Fa-f] {4} ist die resultierende Automatisierung mit Encode, die den zulässigen Satz von Hexadezimalwerten auf den Bereich von IdentifierCharNoEscape beschränkt. Wenn Sie also \ u005c angeben, akzeptiert die Codierungsversion den Wert nicht. Solche Dinge haben eine ernsthafte Einschränkung: Sparsam verwenden. Die daraus resultierende Automatisierung kann sehr komplex sein.

Was nicht implementiert ist, ist die CST-Generierung. Ich muss die deterministischen Automatisierungen anpassen, um den richtigen Kontext zu übernehmen, damit dies funktioniert.

Für alle Interessierten habe ich einen hübschen Ausdruck der Originalform des T * y♯-Projekts hochgeladen . Jede Datei sollte mit jeder anderen Datei verknüpft sein. Ich habe begonnen, die einzelnen Regeln zu verknüpfen, um sie zu befolgen, aber es hätte viel zu lange gedauert (wäre einfacher zu automatisieren gewesen!).

Wenn mehr Kontext benötigt wird, posten Sie bitte entsprechend.

Bearbeiten 5-14-2013 : Ich habe Code geschrieben, um GraphViz-Diagramme für die Zustandsautomaten in einer bestimmten Sprache zu erstellen. Hier ist ein GraphViz-Digraph des AssemblyPart . Die in der Sprachbeschreibung verknüpften Mitglieder sollten in ihrem relativen Ordner eine rulename.txt mit dem Digraphen für diese Regel haben. Einige der Sprachbeschreibungen haben sich geändert, seit ich das Beispiel veröffentlicht habe. Dies ist auf die Vereinfachung der Grammatik zurückzuführen. Hier ist ein interessantes Grafikbild .

Dies ist eine ausgezeichnete Frage.

Ich habe in letzter Zeit viel an der Analyse gearbeitet, und meiner Meinung nach sind einige der Hauptfunktionen:

• eine programmatische API - so kann sie aus einer Programmiersprache heraus verwendet werden, idealerweise durch einfaches Importieren einer Bibliothek. Es kann auch eine GUI- oder BNF-ähnliche Oberfläche haben, aber die programmatische ist der Schlüssel, da Sie Ihre Werkzeuge, IDE, statische Analyse, Tests, Sprachabstraktionsfunktionen, Vertrautheit mit Programmierern, Dokumentationsgenerator, Erstellungsprozess, wiederverwenden können. usw. Außerdem können Sie interaktiv mit winzigen Parsern spielen, was die Lernkurve drastisch verkürzt. Aus diesen Gründen steht es ganz oben auf meiner Liste der "wichtigen Funktionen".

• Fehlerberichterstattung, wie @guysherman erwähnt. Wenn ein Fehler gefunden wird, möchte ich wissen, wo der Fehler war und was passiert ist, als er passiert ist. Leider konnte ich keine guten Ressourcen finden, um zu erklären, wie beim Backtracking anständige Fehler generiert werden können. (Obwohl Anmerkung @ Sk-Logik unten Kommentar).

• Teilergebnisse. Wenn das Parsen fehlschlägt, möchte ich sehen können, was erfolgreich aus dem Teil der Eingabe analysiert wurde, der sich vor dem Ort des Fehlers befand.

• Abstraktion. Sie können nie genug Funktionen einbauen, und der Benutzer wird immer mehr benötigen. Daher ist der Versuch, alle möglichen Funktionen im Voraus herauszufinden, zum Scheitern verurteilt. Meinen Sie das mit Vorlagen?

• Ich stimme Ihrer Nummer 2 zu (Vorausschau). Ich denke, es hilft, gute Fehlerberichte zu erstellen. Ist es für irgendetwas anderes nützlich?

• Unterstützung für das Erstellen eines Analysebaums beim Parsen, möglicherweise:

  • Ein konkreter Syntaxbaum, bei dem die Struktur des Baums direkt der Grammatik entspricht und Layoutinformationen für die Fehlerberichterstattung späterer Phasen enthält. In diesem Fall sollte der Client nichts tun müssen , um die richtige Baumstruktur zu erhalten - dies sollte direkt von der Grammatik abhängen.
  • ein abstrakter Syntaxbaum. In diesem Fall kann der Benutzer mit allen Analysebäumen herumspielen

• eine Art Protokollierung. Ich bin mir da nicht sicher; Vielleicht, um eine Spur der Regeln anzuzeigen, die der Parser versucht hat, oder um Junk-Token wie Leerzeichen oder Kommentare zu verfolgen, falls Sie (zum Beispiel) die Token zum Generieren von HTML-Dokumentation verwenden möchten.

• Fähigkeit, mit kontextsensitiven Sprachen umzugehen. Ich bin mir auch nicht sicher, wie wichtig dies ist - in der Praxis scheint es sauberer, eine Obermenge einer Sprache mit einer kontextfreien Grammatik zu analysieren und dann in weiteren späteren Durchgängen kontextsensitive Einschränkungen zu überprüfen.

• Benutzerdefinierte Fehlermeldungen, damit ich die Fehlerberichte in bestimmten Situationen optimieren und Probleme möglicherweise schneller verstehen und beheben kann.

Andererseits finde ich die Fehlerkorrektur nicht besonders wichtig - obwohl ich über den aktuellen Fortschritt nicht auf dem Laufenden bin. Die Probleme, die mir aufgefallen sind, sind, dass die möglichen Korrekturen, die die Werkzeuge liefern, sind: 1) zu zahlreich und 2) nicht den tatsächlich gemachten Fehlern entsprechen und daher nicht allzu hilfreich sind. Hoffentlich wird sich diese Situation verbessern (oder hat dies vielleicht bereits getan).

Ich habe keine Erfahrung mit Sprachdesign, aber ich habe einmal versucht, einen Parser zu schreiben, als ich eine IDE für eine Spiel-Engine erstellt habe.

Was für Ihre Endbenutzer meiner Meinung nach wichtig ist, sind sinnvolle Fehlermeldungen. Ich weiß, dass dies kein besonders erderschütternder Punkt ist, aber wenn man ihn rückwärts verfolgt, ist eine der wichtigsten Implikationen, dass man in der Lage sein muss, Fehlalarme zu vermeiden. Woher kommen die Fehlalarme? Sie kommen vom Parser, der beim ersten Fehler umfällt und sich nie ganz erholt. C / C ++ ist dafür berüchtigt (obwohl die neueren Compiler etwas schlauer sind).

Was brauchst du stattdessen? Ich denke, anstatt nur zu wissen, was zu einem bestimmten Zeitpunkt gültig ist / nicht gültig ist, müssen Sie wissen, wie Sie das, was nicht gültig ist, nehmen und eine minimale Änderung vornehmen, um es gültig zu machen - damit Sie mit dem Parsen fortfahren können, ohne falsche Fehler zu generieren zu Ihrem rekursiven Abstieg wird verwirrt. Wenn Sie einen Parser erstellen können, der diese Informationen generieren kann, erhalten Sie nicht nur einen sehr robusten Parser, sondern auch einige fantastische Funktionen für die Software, die den Parser verwendet.

Mir ist klar, dass ich vielleicht etwas wirklich Schwieriges oder Dummes vorschlage. Tut mir leid, wenn dies der Fall ist. Wenn dies nicht das ist, wonach Sie suchen, werde ich meine Antwort gerne löschen.

Die Grammatik darf keine Einschränkungen wie "keine rekursiven Regeln hinterlassen haben" haben. Es ist lächerlich, dass die heute weit verbreiteten Tools dies haben und nur das Saugen von LL-Grammatiken verstehen können - fast 50 Jahre nachdem yacc es richtig gemacht hat.

Ein Beispiel für die richtige Rekursion (unter Verwendung der Yacc-Syntax):

list: 
      elem                  { $$ = singleton($1); }
    | elem ',' list         { $$ = cons($1, $2);  }
    ;

Ein Beispiel für die Linksrekursion (mit yacc synatx):

funapp:
    term                    { $$ = $1; }
    | funapp term           { $$ = application($1, $2); }
    ;

Dies könnte möglicherweise zu etwas anderem "umgestaltet" werden, aber in beiden Fällen ist die spezifische Art der Rekursion genau die "richtige" Art, dies zu schreiben, da (in der Beispielsprache) Listen rechtsrekursiv sind, während die Funktionsanwendung rekursiv bleibt .

Von fortgeschrittenen Werkzeugen kann man erwarten, dass sie die natürliche Art und Weise unterstützen, Dinge aufzuschreiben, anstatt zu verlangen, dass man alles "refaktoriert", was links / rechts rekursiv ist, wie es das Werkzeug einem auferlegt.