Schreiben eines Compilers Compiler - Einblick in Verwendung und Funktionen

10

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 .

Alexander Morou
quelle
8
Textwand. Verstehen Sie das nicht falsch, ich schätze ein gründlich erklärtes Problem. In diesem Fall ist es einfach etwas zu ausführlich. Nach allem, was ich gesammelt habe, fragen Sie sich, welche Funktionen in einem Grammatik-Parser enthalten sein sollten oder wie Sie eine erstellen können, ohne von vorne zu beginnen? Bitte bearbeiten Sie, um die folgenden Fragen zu beantworten (Sie müssen nicht umschreiben, sondern einfach zusammenfassend an das Ende anhängen): Was ist Ihr Problem? An welche Einschränkungen sind Sie bei möglichen Lösungen für Ihr Problem gebunden (es muss schnell sein, es muss LL * sein usw.)?
Neil
1
Ich bitte um Einblick in die Funktionen. Der Fokus liegt auf der Benutzerfreundlichkeit. Die Schwierigkeit besteht darin, jemanden, der das Projekt nicht kennt, einen Einblick in das Projekt zu bekommen, damit er über dessen Fokus informiert wird. Ich frage nicht nach der Vorgehensweise, sondern nach der Benutzerfreundlichkeit. Vorschläge zum Trimmen der Frage sind willkommen.
Alexander Morou
1
Für mich ist nicht klar, worum es bei dem Projekt geht. Zum Beispiel haben wir seit den Tagen von yacc viele Parser-Generatoren gesehen. Was ist anders in Ihrem OILexer? Was ist das Neue?
Ingo
1
Ziel dieses Projekts ist es, die Parser-Generierung zu vereinfachen. Ähnlich wie bei YACC / Bison und FLEX / LEX. Der Hauptunterschied besteht darin, die Komplexität dieser Programme zu vermeiden. Das Hauptziel ist es, die Dinge einfach und auf den Punkt zu bringen. Aus diesem Grund habe ich ein Format erstellt, das keine ungeraden Abschnitte enthält. Ziel ist es jedoch, es der regulären Programmierung ähnlich zu machen: nur spezifisch für die Sprachentwicklung. Tokens werden mit ': =' nach ihrem Namen definiert, Regeln werden mit :: = nach ihrem Namen definiert. Vorlagen verwenden '<' und '>' für ihre Argumente, gefolgt von ":: =", da sie die Regelsyntax gemeinsam nutzen.
Alexander Morou
3
Dieser höllische Fokus auf das Parsen scheint fehl am Platz zu sein. Es ist ein gut gelöstes Problem, und es beeinträchtigt kaum das, was Sie zum Verarbeiten von Programmiersprachen benötigen. Google für meinen Aufsatz über "Leben nach dem Parsen".
Ira Baxter

Antworten:

5

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).


quelle
Ich habe den Fragentext so bearbeitet, dass er einen Link zum PrecedenceHelper in das Aufzählungszeichen "Vorlagen" einfügt. Es erlaubt Parameterarray-Tupel. Wenn Sie also vier Parameter haben, jedes Parameterarray, muss die Vorlage in vier Argumentargumenten verwendet werden.
Alexander Morou
Der Hauptgrund, warum Sie das CST erstellen würden, ist das Gesamtlayout der analysierten Datei. Wenn Sie das Dokument hübsch drucken möchten , verwenden Sie am besten ein CST, da ASTs, wie der Name schon sagt, keine Informationen enthalten, um den ungeraden Abstand zu bewältigen, den ein CST erfassen würde. Das Transformieren eines CST ist normalerweise ziemlich einfach, wenn es ein gutes CST ist.
Alexander Morou
Ich habe die Frage zum Thema der zur Verfügung stehenden integrierten Funktionen erneut bearbeitet.
Alexander Morou
Ich denke, ich habe keine großartige Arbeit geleistet, um meinen Standpunkt zu Vorlagen / Funktionen auszudrücken: Ich meinte, weil Sie nie genug haben können, sollte ein System nicht versuchen, sie im Voraus herauszufinden: Der Benutzer muss in der Lage sein, sie zu erstellen sein eigenes.
1
Ich fand einen Ansatz besonders nützlich für die Fehlerberichterstattung mit unendlichem Backtracking (Packrat): Jede Produktionsregel ist mit Fehlermeldungen (formuliert als "bla-bla-bla erwartet") versehen, und bei einem Fehler wird diese Nachricht auf die gleiche Weise im Stream gespeichert als auswendig gelernte Token. Wenn nicht alle Fehler behoben werden können (die Analyse wurde vor Erreichen des Stream-Endes beendet), ist die Fehlermeldung ganz rechts (oder eine Sammlung solcher Meldungen) am besten geeignet. Das ist am einfachsten, natürlich gibt es Möglichkeiten, es mit mehr Anmerkungen weiter zu verfeinern.
SK-Logik
5

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.

Jungsherman
quelle
Dies ist eine Sache, die ich vorhabe zu tun. Um mein Wissen über die Domain zu verbessern, schlug ein Freund vor, einen tatsächlichen Parser von Hand zu schreiben, um die Automatisierung zu verstehen. Eines wurde mir ziemlich schnell klar: Parser sind komplex und es gibt Dinge, die wir von Hand tun, um den Prozess zu vereinfachen. Regeln und Vorlagen haben dieselbe Syntax. Es gibt jedoch Sprachelemente, die in Vorlagen gültig sind, aber keine Regeln. Es gibt interne Zustände, die diese Aufgabe behandeln. Was an eine Idee erinnerte: Regeln sollten in der Lage sein, Pfadhilfen anzugeben, um das Teilen von Unterregeln zu vereinfachen.
Alexander Morou
... dies sollte ziemlich einfach in die Automatisierung zu übertragen sein, würde aber erfordern, dass die Automatisierungen zustandsbasierte Bedingungen haben. Ich werde daran arbeiten und mich bei Ihnen melden. ANTLR verwendet Automatisierungen mit endlichen Zuständen, um Zyklen von beispielsweise "T" * zu verarbeiten, wobei ich den größten Teil des Analyseprozesses verwenden werde, da die Reduzierungen als Zustände sauberer sein sollten, wenn eine Regel mehr als 800 Variationen enthält (dies würde aufblähen schnell als Spaghetti-Code in Standard-if / else-Form.)
Alexander Morou
0

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.

Ingo
quelle
Ja, es ist schön, solche willkürlichen Einschränkungen nicht zu haben. Was ist jedoch ein Beispiel für eine Linksrekursion, die nicht durch einen Wiederholungsoperator (wie Regexe *oder +Quantifizierer) ersetzt werden kann? Ich gebe frei zu, dass mein Wissen auf diesem Gebiet begrenzt ist, aber ich bin nie auf eine Linksrekursion gestoßen, die nicht in Wiederholung umgestaltet werden konnte. Und ich fand die Wiederholungsversion auch klarer (obwohl das nur eine persönliche Präferenz ist).
1
@ MattFenwick Siehe meine Bearbeitung. Beachten Sie, wie die Syntaxdirektion zu einfachen und natürlichen semantischen Aktionen (z. B.) zum Erstellen eines Syntaxbaums führt. Während der Wiederholung (die übrigens nicht in yacc verfügbar ist) müssen Sie wahrscheinlich oft überprüfen, ob Sie eine leere Liste, einen Singleton usw. haben.
Ingo
Danke für die Antwort. Ich glaube , ich verstehe jetzt besser - ich würde es vorziehen , diese Beispiele zu schreiben list = sepBy1(',', elem)und funapp = term{+}(und natürlich sepBy1und +würde in Bezug auf die Links- / Rechts Rekursion implementiert werden und produzieren Standardsyntaxbäume). Es ist also nicht so, dass ich die Links- und Rechtsrekursion für schlecht halte, sondern nur, dass ich das Gefühl habe, dass sie auf niedriger Ebene sind und wenn möglich eine Abstraktion auf höherer Ebene verwenden möchten, um die Dinge klarer zu machen. Danke noch einmal!
1
Gern geschehen @MattFenwick. Aber dann ist es vielleicht Geschmackssache. Rekursion ist für mich (zumindest im Kontext von Sprachen, die alle von Natur aus rekursiv oder völlig uninteressant sind) die natürlichere Art, darüber nachzudenken. Außerdem ist ein Baum eine rekursive Datenstruktur, sodass ich nicht auf die Iteration zurückgreifen muss , um die Rekursion zu simulieren. Aber natürlich sind die Vorlieben unterschiedlich.
Ingo