Schreiben eines Compilers in seiner eigenen Sprache

Intuitiv scheint es, dass ein Compiler für Sprache Foonicht selbst in Foo geschrieben werden kann. Insbesondere kann der erste Compiler für Sprache Foonicht in Foo geschrieben werden, aber jeder nachfolgende Compiler könnte für geschrieben werden Foo.

Aber ist das tatsächlich wahr? Ich habe eine sehr vage Erinnerung daran, wie ich über eine Sprache gelesen habe, deren erster Compiler in "sich selbst" geschrieben wurde. Ist das möglich und wenn ja wie?

Dies wird als "Bootstrapping" bezeichnet. Sie müssen zuerst einen Compiler (oder Interpreter) für Ihre Sprache in einer anderen Sprache (normalerweise Java oder C) erstellen. Sobald dies erledigt ist, können Sie eine neue Version des Compilers in der Sprache Foo schreiben. Sie verwenden den ersten Bootstrap-Compiler, um den Compiler zu kompilieren, und verwenden dann diesen kompilierten Compiler, um alles andere (einschließlich zukünftiger Versionen von sich selbst) zu kompilieren.

Die meisten Sprachen werden in der Tat auf diese Weise erstellt, teilweise weil Sprachdesigner die von ihnen erstellte Sprache gerne verwenden, und auch, weil ein nicht trivialer Compiler häufig als nützlicher Maßstab dafür dient, wie "vollständig" die Sprache sein kann.

Ein Beispiel hierfür wäre Scala. Der erste Compiler wurde in Pizza erstellt, einer experimentellen Sprache von Martin Odersky. Ab Version 2.0 wurde der Compiler in Scala komplett neu geschrieben. Von diesem Zeitpunkt an konnte der alte Pizza-Compiler vollständig verworfen werden, da der neue Scala-Compiler verwendet werden konnte, um sich für zukünftige Iterationen selbst zu kompilieren.

Ich erinnere mich an einen Podcast von Software Engineering Radio, in dem Dick Gabriel über das Bootstrapping des ursprünglichen LISP-Interpreters sprach, indem er eine Bare-Bones-Version in LISP auf Papier schrieb und sie von Hand zu Maschinencode zusammensetzte. Von da an wurden die restlichen LISP-Funktionen in LISP geschrieben und mit LISP interpretiert.

Den vorherigen Antworten eine Neugier hinzufügen.

Hier ist ein Zitat aus dem Linux From Scratch- Handbuch, in dem Schritt, in dem mit dem Erstellen des GCC-Compilers aus seiner Quelle begonnen wird. (Linux From Scratch ist eine Möglichkeit, Linux zu installieren, die sich grundlegend von der Installation einer Distribution unterscheidet, da Sie wirklich jede einzelne Binärdatei des Zielsystems kompilieren müssen .)

make bootstrap

Das 'Bootstrap'-Ziel kompiliert GCC nicht nur, sondern kompiliert es mehrmals. Es verwendet die in einer ersten Runde kompilierten Programme, um sich ein zweites Mal und dann erneut ein drittes Mal zu kompilieren. Anschließend werden diese zweiten und dritten Kompilierungen verglichen, um sicherzustellen, dass sie sich fehlerfrei reproduzieren können. Dies bedeutet auch, dass es korrekt kompiliert wurde.

Diese Verwendung des 'Bootstrap'-Ziels ist durch die Tatsache motiviert, dass der Compiler, mit dem die Toolchain des Zielsystems erstellt wird, möglicherweise nicht dieselbe Version des Ziel-Compilers hat. Wenn man so vorgeht, erhält man im Zielsystem sicher einen Compiler, der sich selbst kompilieren kann.

Wenn Sie Ihren ersten Compiler für C schreiben, schreiben Sie ihn in einer anderen Sprache. Jetzt haben Sie einen Compiler für C in Assembler. Schließlich kommen Sie an den Ort, an dem Sie Zeichenfolgen analysieren müssen, insbesondere Escape-Sequenzen. Sie schreiben Code, um ihn \nin das Zeichen mit dem Dezimalcode 10 (und \rin 13 usw.) umzuwandeln .

Nachdem dieser Compiler fertig ist, werden Sie ihn in C erneut implementieren. Dieser Vorgang wird als " Bootstrapping " bezeichnet.

Der String-Parsing-Code lautet:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Wenn dies kompiliert wird, haben Sie eine Binärdatei, die '\ n' versteht. Dies bedeutet, dass Sie den Quellcode ändern können:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Wo ist also die Information, dass '\ n' der Code für 13 ist? Es ist in der Binärdatei! Es ist wie bei DNA: Das Kompilieren von C-Quellcode mit dieser Binärdatei erbt diese Informationen. Wenn der Compiler sich selbst kompiliert, gibt er dieses Wissen an seine Nachkommen weiter. Ab diesem Zeitpunkt ist es nicht mehr möglich, allein aus der Quelle zu erkennen, was der Compiler tun wird.

Wenn Sie einen Virus in der Quelle eines Programms verstecken möchten, gehen Sie folgendermaßen vor: Rufen Sie die Quelle eines Compilers ab, suchen Sie die Funktion, die Funktionen kompiliert, und ersetzen Sie sie durch diese:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

Die interessanten Teile sind A und B. A ist der Quellcode für compileFunctiondie Aufnahme des Virus, wahrscheinlich auf irgendeine Weise verschlüsselt, sodass es bei der Suche in der resultierenden Binärdatei nicht offensichtlich ist. Dadurch wird sichergestellt, dass beim Kompilieren in den Compiler mit sich selbst der Virusinjektionscode erhalten bleibt.

B ist dasselbe für die Funktion, die wir durch unseren Virus ersetzen möchten. Zum Beispiel könnte es die Funktion "login" in der Quelldatei "login.c" sein, die wahrscheinlich vom Linux-Kernel stammt. Wir könnten es durch eine Version ersetzen, die zusätzlich zum normalen Passwort das Passwort "joshua" für das Root-Konto akzeptiert.

Wenn Sie das kompilieren und als Binärdatei verbreiten, können Sie den Virus nicht anhand der Quelle finden.

Die ursprüngliche Quelle der Idee: https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/

Sie können keinen Compiler selbst schreiben, da Sie nichts haben, mit dem Sie Ihren Startquellcode kompilieren können. Es gibt zwei Lösungsansätze.

Am wenigsten bevorzugt ist das Folgende. Sie schreiben einen minimalen Compiler in Assembler (yuck) für einen minimalen Satz der Sprache und verwenden diesen Compiler dann, um zusätzliche Funktionen der Sprache zu implementieren. Bauen Sie sich auf, bis Sie einen Compiler mit allen Sprachfunktionen für sich haben. Ein schmerzhafter Prozess, der normalerweise nur durchgeführt wird, wenn Sie keine andere Wahl haben.

Der bevorzugte Ansatz ist die Verwendung eines Cross-Compilers. Sie ändern das Back-End eines vorhandenen Compilers auf einem anderen Computer, um eine Ausgabe zu erstellen, die auf dem Zielcomputer ausgeführt wird. Dann haben Sie einen schönen vollständigen Compiler, der auf dem Zielcomputer arbeitet. Am beliebtesten ist hierfür die C-Sprache, da es viele vorhandene Compiler gibt, die über steckbare Backends verfügen, die ausgetauscht werden können.

Eine wenig bekannte Tatsache ist, dass der GNU C ++ - Compiler eine Implementierung hat, die nur die C-Teilmenge verwendet. Der Grund dafür ist normalerweise, dass es einfach ist, einen C-Compiler für einen neuen Zielcomputer zu finden, mit dem Sie den vollständigen GNU C ++ - Compiler daraus erstellen können. Sie haben sich jetzt darauf festgelegt, einen C ++ - Compiler auf dem Zielcomputer zu haben.

Im Allgemeinen muss zuerst ein funktionierender (wenn auch primitiver) Schnitt des Compilers funktionieren - dann können Sie darüber nachdenken, ihn selbst zu hosten. Dies wird in einigen Sprachen tatsächlich als wichtiger Meilenstein angesehen.

Soweit ich mich an "Mono" erinnere, müssen sie wahrscheinlich ein paar Dinge zur Reflexion hinzufügen, damit es funktioniert: Das Mono-Team weist immer wieder darauf hin, dass einige Dinge mit einfach nicht möglich sind Reflection.Emit; Natürlich könnte das MS-Team ihnen das Gegenteil beweisen.

Dies hat einige echte Vorteile: Für den Anfang ist es ein ziemlich guter Unit-Test! Und Sie müssen sich nur um eine Sprache kümmern (dh es ist möglich, dass ein C # -Experte nicht viel über C ++ weiß; jetzt können Sie den C # -Compiler reparieren). Aber ich frage mich, ob hier nicht viel professioneller Stolz am Werk ist: Sie wollen einfach, dass es sich selbst hostet.

Nicht ganz ein Compiler, aber ich habe kürzlich an einem System gearbeitet, das sich selbst hostet. Der Codegenerator wird verwendet, um den Codegenerator zu generieren. Wenn sich das Schema ändert, führe ich es einfach auf sich selbst aus: neue Version. Wenn es einen Fehler gibt, gehe ich einfach zu einer früheren Version zurück und versuche es erneut. Sehr praktisch und sehr pflegeleicht.

Update 1

Ich habe gerade dieses Video von Anders bei PDC gesehen und (ungefähr eine Stunde später) gibt er einige viel gültigere Gründe an - alles über den Compiler als Service. Nur für das Protokoll.

Hier ist ein Dump (eigentlich schwer zu suchendes Thema):

• Smalltalk

• C.

Dies ist auch die Idee von PyPy und Rubinius :

(Ich denke, das könnte auch für Forth gelten , aber ich weiß nichts über Forth.)

Für GNAT, den GNU Ada-Compiler, muss ein Ada-Compiler vollständig erstellt sein. Dies kann schmerzhaft sein, wenn Sie es auf eine Plattform portieren, auf der keine GNAT-Binärdatei verfügbar ist.

Tatsächlich sind die meisten Compiler aus den oben genannten Gründen in der Sprache geschrieben, die sie kompilieren.

Der erste Bootstrap-Compiler ist normalerweise in C, C ++ oder Assembly geschrieben.

Der C # -Compiler des Mono-Projekts ist seit langem "selbst gehostet". Dies bedeutet, dass er in C # selbst geschrieben wurde.

Was ich weiß ist, dass der Compiler als reiner C-Code gestartet wurde, aber sobald die "grundlegenden" Funktionen von ECMA implementiert wurden, haben sie begonnen, den Compiler in C # neu zu schreiben.

Ich bin mir der Vorteile des Schreibens des Compilers in derselben Sprache nicht bewusst, aber ich bin sicher, dass dies zumindest mit den Funktionen zu tun hat, die die Sprache selbst bieten kann (C unterstützt beispielsweise keine objektorientierte Programmierung). .

Weitere Informationen finden Sie hier .

Ich habe SLIC (System of Languages ​​for Implementing Compilers) in sich selbst geschrieben. Dann von Hand zusammengestellt. SLIC hat viel zu bieten, da es sich um einen einzelnen Compiler aus fünf Untersprachen handelte:

• SYNTAX Parser Programmiersprache PPL
• GENERATOR LISP 2-basierte PSEUDO-Codegenerierungssprache zum Crawlen von Bäumen
• ISO In Sequence, PSEUDO-Code, Optimierungssprache
• PSEUDO Makro wie Assembler Code produzierende Sprache.
• MACHOP Assembly-Machine-Anweisung, die die Sprache definiert.

SLIC wurde von CWIC (Compiler zum Schreiben und Implementieren von Compilern) inspiriert. Im Gegensatz zu den meisten Compiler-Entwicklungspaketen haben SLIC und CWIC die Codegenerierung mit speziellen, domänenspezifischen Sprachen behandelt. SLIC erweitert die Codegenerierung von CWICs um die Subsprachen ISO, PSEUDO und MACHOP, die die Besonderheiten des Zielcomputers von der Sprache des Generators für das Crawlen von Bäumen trennen.

LISP 2 Bäume und Listen

Das dynamische Speicherverwaltungssystem der LISP 2-basierten Generatorsprache ist eine Schlüsselkomponente. Listen werden in der Sprache in eckigen Klammern angegeben, deren Komponenten durch Kommas getrennt sind, dh eine Liste mit drei Elementen [a, b, c].

Bäume:

     ADD
    /   \
  MPY     3
 /   \
5     x

werden durch Listen dargestellt, deren erster Eintrag ein Knotenobjekt ist:

[ADD,[MPY,5,x],3]

Bäume werden normalerweise mit dem separaten Knoten vor den Zweigen angezeigt:

ADD[MPY[5,x],3]

Aufheben der Analyse mit LISP 2-basierten Generatorfunktionen

Eine Generatorfunktion ist eine benannte Menge von (unparse) => Aktion> Paaren ...

<NAME>(<unparse>)=><action>;
      (<unparse>)=><action>;
            ...
      (<unparse>)=><action>;

Unparse-Ausdrücke sind Tests, die mit Baummustern und / oder Objekttypen übereinstimmen, die diese aufteilen und diese Teile einer lokalen Variablen zuweisen, die von ihrer prozeduralen Aktion verarbeitet werden soll. Ein bisschen wie eine überladene Funktion, die verschiedene Argumenttypen verwendet. Außer die () => ... Tests werden in der angegebenen Reihenfolge versucht. Die erste erfolgreiche unparse, die ihre entsprechende Aktion ausführt. Die unparsen Ausdrücke sind Zerlegungsprüfungen. ADD [x, y] entspricht einem ADD-Baum mit zwei Zweigen, der seine Zweige den lokalen Variablen x und y zuweist. Die Aktion kann ein einfacher Ausdruck oder ein gebundener Codeblock .BEGIN ... .END sein. Ich würde heute Blöcke im c-Stil {...} verwenden. Baumabgleich, [], unparse Regeln können Generatoren aufrufen, die die zurückgegebenen Ergebnisse an die Aktion übergeben:

expr_gen(ADD[expr_gen(x),expr_gen(y)])=> x+y;

Insbesondere stimmt die obige unparse expr_gen mit einem ADD-Baum mit zwei Zweigen überein. Innerhalb des Testmusters wird ein einzelner Argumentgenerator, der in einem Ast platziert ist, mit diesem Zweig aufgerufen. Die Argumentliste besteht jedoch aus lokalen Variablen, denen zurückgegebene Objekte zugewiesen wurden. Über dem unparse wird angegeben, dass zwei Zweige die ADD-Baumzerlegung sind, wobei rekursiv jeder Zweig auf expr_gen gedrückt wird. Die linke Verzweigungsrückgabe wird in die lokalen Variablen x eingefügt. Ebenso wurde der rechte Zweig mit y dem Rückgabeobjekt an expr_gen übergeben. Das Obige könnte Teil eines Evaluators für numerische Ausdrücke sein. Es gab Verknüpfungsmerkmale, die als Vektoren bezeichnet wurden. Oben konnte anstelle der Knotenzeichenfolge ein Knotenvektor mit einem Vektor entsprechender Aktionen verwendet werden:

expr_gen(#node[expr_gen(x),expr_gen(y)])=> #action;

  node:   ADD, SUB, MPY, DIV;
  action: x+y, x-y, x*y, x/y;

        (NUMBER(x))=> x;
        (SYMBOL(x))=> val:(x);

Der obige vollständigere Ausdrucksauswerter weist die Rückgabe vom linken Zweig expr_gen an x ​​und den rechten Zweig an y zu. Der entsprechende Aktionsvektor, der für x und y ausgeführt wurde, wurde zurückgegeben. Die letzten unparse => Aktionspaare stimmen mit numerischen und Symbolobjekten überein.

Symbol und Symbolattribute

Symbole können benannte Attribute haben. val: (x) Zugriff auf das val-Attribut des in x enthaltenen Symbolobjekts. Ein verallgemeinerter Symboltabellenstapel ist Teil von SLIC. Die SYMBOL-Tabelle kann verschoben und geöffnet werden, um lokale Symbole für Funktionen bereitzustellen. Neu erstellte Symbole werden in der oberen Symboltabelle katalogisiert. Die Symbolsuche durchsucht den Symboltabellenstapel von der obersten Tabelle zuerst rückwärts den Stapel hinunter.

Maschinenunabhängigen Code generieren

Die Generatorsprache von SLIC erzeugt PSEUDO-Anweisungsobjekte und hängt sie an eine Abschnittscodeliste an. Ein .FLUSH bewirkt, dass seine PSEUDO-Codeliste ausgeführt wird, wobei jeder PSEUDO-Befehl aus der Liste entfernt und aufgerufen wird. Nach der Ausführung wird ein PSEUDO-Objektspeicher freigegeben. Die Verfahrensorgane der PSEUDO- und GENERATOR-Aktionen sind bis auf ihre Ausgabe grundsätzlich dieselbe Sprache. PSEUDO sollen als Assembly-Makros fungieren und eine maschinenunabhängige Codesequenzierung ermöglichen. Sie bieten eine Trennung der spezifischen Zielmaschine von der Sprache des Baumcrawling-Generators. PSEUDOs rufen MACHOP-Funktionen auf, um Maschinencode auszugeben. MACHOPs werden verwendet, um Assembly-Pseudo-Ops (wie DC, Konstante usw.) und Maschinenanweisungen oder eine Familie von ähnlich formatierten Anweisungen unter Verwendung eines vektorisierten Eintrags zu definieren. Sie transformieren einfach ihre Parameter in eine Folge von Bitfeldern, aus denen der Befehl besteht. MACHOP-Aufrufe sollen wie Assembly aussehen und eine Druckformatierung der Felder bereitstellen, wenn Assembly in der Kompilierungsliste angezeigt wird. Im Beispielcode verwende ich Kommentare im C-Stil, die leicht hinzugefügt werden konnten, aber nicht in den Originalsprache waren. MACHOPs erzeugen Code in einem bitadressierbaren Speicher. Der SLIC-Linker verarbeitet die Ausgabe des Compilers. Ein MACHOP für die Anweisungen im DEC-10-Benutzermodus unter Verwendung eines vektorisierten Eintrags: MACHOPs erzeugen Code in einem bitadressierbaren Speicher. Der SLIC-Linker verarbeitet die Ausgabe des Compilers. Ein MACHOP für die Anweisungen im DEC-10-Benutzermodus unter Verwendung eines vektorisierten Eintrags: MACHOPs erzeugen Code in einem bitadressierbaren Speicher. Der SLIC-Linker verarbeitet die Ausgabe des Compilers. Ein MACHOP für die Anweisungen im DEC-10-Benutzermodus unter Verwendung eines vektorisierten Eintrags:

.MACHOP #opnm register,@indirect offset (index): // Instruction's parameters.
.MORG 36, O(18): $/36; // Align to 36 bit boundary print format: 18 bit octal $/36
O(9):  #opcd;          // Op code 9 bit octal print out
 (4):  register;       // 4 bit register field appended print
 (1):  indirect;       // 1 bit appended print
 (4):  index;          // 4 bit index register appended print
O(18): if (#opcd&&3==1) offset // immediate mode use value else
       else offset/36;         // memory address divide by 36
                               // to get word address.
// Vectored entry opcode table:
#opnm := MOVE, MOVEI, MOVEM, MOVES, MOVS, MOVSI, MOVSM, MOVSS,
         MOVN, MOVNI, MOVNM, MOVNS, MOVM, MOVMI, MOVMM, MOVMS,
         IMUL, IMULI, IMULM, IMULB, MUL,  MULI,  MULM,  MULB,
                           ...
         TDO,  TSO,   TDOE,  TSOE,  TDOA, TSOA,  TDON,  TSON;
// corresponding opcode value:
#opcd := 0O200, 0O201, 0O202, 0O203, 0O204, 0O205, 0O206, 0O207,
         0O210, 0O211, 0O212, 0O213, 0O214, 0O215, 0O216, 0O217,
         0O220, 0O221, 0O222, 0O223, 0O224, 0O225, 0O226, 0O227,
                           ...
         0O670, 0O671, 0O672, 0O673, 0O674, 0O675, 0O676, 0O677;

Die .MORG 36, O (18): $ / 36; Richtet die Position an einer 36-Bit-Grenze aus, wobei die Position $ / 36-Wortadresse mit 18 Bit im Oktal gedruckt wird. Das 9-Bit-Operationsregister, das 4-Bit-Register, das indirekte Bit und das 4-Bit-Indexregister werden kombiniert und gedruckt, als ob ein einzelnes 18-Bit-Feld. Die 18-Bit-Adresse / 36 oder der unmittelbare Wert wird ausgegeben und oktal gedruckt. Ein MOVEI-Beispielausdruck mit r1 = 1 und r2 = 2:

400020 201082 000005            MOVEI r1,5(r2)

Mit der Compiler-Assembly-Option erhalten Sie den generierten Assembly-Code in der Compile-Liste.

Verknüpfe es miteinander

Der SLIC-Linker wird als Bibliothek geliefert, die die Verknüpfungs- und Symbolauflösungen verwaltet. Die zielspezifische Formatierung der Ausgabedatei muss jedoch für Zielcomputer geschrieben und mit der Linkerbibliotheksbibliothek verknüpft werden.

Die Generatorsprache kann Bäume in eine Datei schreiben und lesen, sodass ein Multipass-Compiler implementiert werden kann.

Kurze Zusammenfassung der Codegenerierung und -herkunft

Ich habe zuerst die Codegenerierung durchgesehen, um sicherzustellen, dass SLIC ein echter Compiler-Compiler ist. SLIC wurde von CWIC (Compiler for Writing and Implementing Compilers) inspiriert, das Ende der 1960er Jahre bei der Systems Development Corporation entwickelt wurde. CWIC hatte nur SYNTAX- und GENERATOR-Sprachen, die numerischen Bytecode aus der GENERATOR-Sprache erzeugten. Bytecode wurde in Speicherpuffer, die benannten Abschnitten zugeordnet sind, eingefügt oder eingefügt (der in der CWIC-Dokumentation verwendete Begriff) und durch eine .FLUSH-Anweisung ausgeschrieben. Ein ACM-Dokument zu CWIC ist im ACM-Archiv erhältlich.

Erfolgreiche Implementierung einer wichtigen Programmiersprache

In den späten 1970er Jahren wurde SLIC verwendet, um einen COBOL-Cross-Compiler zu schreiben. Fertiggestellt in ca. 3 Monaten meist von einem einzigen Programmierer. Ich habe nach Bedarf ein bisschen mit dem Programmierer gearbeitet. Ein anderer Programmierer hat die Laufzeitbibliothek und MACHOPs für den Ziel-TI-990-Mini-COMPUTER geschrieben. Dieser COBOL-Compiler hat wesentlich mehr Zeilen pro Sekunde kompiliert als der native DEC-10-COBOL-Compiler, der in Assembly geschrieben wurde.

Mehr zu einem Compiler, über den dann normalerweise gesprochen wird

Ein großer Teil des Schreibens eines Compilers von Grund auf ist die Laufzeitbibliothek. Sie benötigen eine Symboltabelle. Sie benötigen Eingabe und Ausgabe. Dynamische Speicherverwaltung usw. Das Schreiben der Laufzeitbibliothek für einen Compiler kann einfacher sein als das Schreiben des Compilers. Mit SLIC ist diese Laufzeitbibliothek jedoch allen in SLIC entwickelten Compilern gemeinsam. Beachten Sie, dass es zwei Laufzeitbibliotheken gibt. Eine für die Zielmaschine der Sprache (z. B. COBOL). Die andere ist die Laufzeitbibliothek des Compilers.

Ich glaube, ich habe festgestellt, dass dies keine Parser-Generatoren waren. Mit ein wenig Verständnis des Backends kann ich nun die Parser-Programmiersprache erklären.

Parser-Programmiersprache

Der Parser wird mit einer Formel geschrieben, die in Form einfacher Gleichungen geschrieben ist.

<name> <formula type operator> <expression> ;

Das Sprachelement auf der untersten Ebene ist das Zeichen. Token werden aus einer Teilmenge der Zeichen der Sprache gebildet. Zeichenklassen werden verwendet, um diese Zeichenuntergruppen zu benennen und zu definieren. Der Operator, der die Zeichenklasse definiert, ist das Doppelpunktzeichen (:). Zeichen, die Mitglieder der Klasse sind, werden auf der rechten Seite der Definition codiert. Druckbare Zeichen sind in Primzahlen-Einzelzeichenfolgen eingeschlossen. Nicht druckbare und Sonderzeichen können durch ihre numerische Ordnungszahl dargestellt werden. Klassenmitglieder werden durch eine Alternative getrennt Operator. Eine Klassenformel endet mit einem Semikolon. Zeichenklassen können zuvor definierte Klassen enthalten:

/*  Character Class Formula                                    class_mask */
bin: '0'|'1';                                                // 0b00000010
oct: bin|'2'|'3'|'4'|'5'|'6'|'7';                            // 0b00000110
dgt: oct|'8'|'9';                                            // 0b00001110
hex: dgt|'A'|'B'|'C'|'D'|'E'|'F'|'a'|'b'|'c'|'d'|'e'|'f';    // 0b00011110
upr:  'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|
      'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';   // 0b00100000
lwr:  'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|
      'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z';   // 0b01000000
alpha:  upr|lwr;                                             // 0b01100000
alphanum: alpha|dgt;                                         // 0b01101110

Die skip_class 0b00000001 ist vordefiniert, kann jedoch überlastet sein, um eine skip_class zu definieren.

Zusammenfassend: Eine Zeichenklasse ist eine Liste von Alternativen, die nur eine Zeichenkonstante, eine Ordnungszahl eines Zeichens oder eine zuvor definierte Zeichenklasse sein kann. Wie ich Zeichenklassen implementiert habe: Der Klassenformel wird eine Klassenbitmaske zugewiesen. (In den obigen Kommentaren gezeigt) Jede Klassenformel mit einem Zeichenliteral oder einer Ordnungszahl bewirkt, dass ein Klassenbit zugewiesen wird. Eine Maske wird erstellt, indem die Klassenmaske (n) der enthaltenen Klasse (n) zusammen mit dem zugewiesenen Bit (falls vorhanden) geordnet werden. Aus den Zeichenklassen wird eine Klassentabelle erstellt. Ein durch die Ordnungszahl eines Charakters indizierter Eintrag enthält Bits, die die Klassenmitgliedschaften des Charakters angeben. Klassentests werden inline durchgeführt. Ein IA-86-Codebeispiel mit der Ordnungszahl des Zeichens in eax veranschaulicht das Testen von Klassen:

test    byte ptr [eax+_classmap],dgt

Gefolgt von einem:

jne      <success>

oder

je       <failure>

IA-86-Anweisungscodebeispiele werden verwendet, weil ich denke, dass IA-86-Anweisungen heute bekannter sind. Der Klassenname, der zu seiner Klassenmaske ausgewertet wird, ist zerstörungsfrei UND-verknüpft mit der Klassentabelle, die durch die Ordnungszahl (in eax) indiziert ist. Ein Ergebnis ungleich Null zeigt eine Klassenmitgliedschaft an. (EAX ist auf Null gesetzt, mit Ausnahme von al (den niedrigen 8 Bits von EAX), das das Zeichen enthält).

Tokens waren in diesen alten Compilern etwas anders. Schlüsselwörter wurden nicht als Token erklärt. Sie wurden einfach durch Anführungszeichen in der Parser-Sprache abgeglichen. Anführungszeichen werden normalerweise nicht beibehalten. Modifikatoren können verwendet werden. A + hält die Zeichenfolge übereinstimmend. (dh + '-' stimmt mit einem Zeichen überein, das das Zeichen bei Erfolg beibehält.) Die Operation, (dh 'E') fügt die Zeichenfolge in das Token ein. Leerzeichen werden durch die Tokenformel behandelt, die führende SKIP_CLASS-Zeichen überspringt, bis eine erste Übereinstimmung hergestellt wird. Beachten Sie, dass eine explizite Übereinstimmung mit den Zeichen "skip_class" das Überspringen stoppt, sodass ein Token mit einem Zeichen "skip_class" beginnen kann. Die Zeichenfolgen-Token-Formel überspringt führende skip_class-Zeichen, die mit einem einfachen Anführungszeichen oder einer doppelten Zeichenfolge übereinstimmen. Von Interesse ist die Übereinstimmung eines "Zeichens innerhalb einer" Zeichenfolge in Anführungszeichen:

string .. (''' .ANY ''' | '"' $(-"""" .ANY | """""","""") '"') MAKSTR[];

Die erste Alternative entspricht einem einfachen Anführungszeichen. Die richtige Alternative entspricht einer Zeichenfolge in doppelten Anführungszeichen, die doppelte Anführungszeichen enthalten kann, wobei zwei "Zeichen zusammen verwendet werden, um ein einzelnes" Zeichen darzustellen. Diese Formel definiert die in ihrer eigenen Definition verwendeten Zeichenfolgen. Die innere rechte Alternative '"' $ (-" "" ".ANY |" "" "", "" "") '"' entspricht einer doppelten Anführungszeichenfolge. Wir können ein einfaches Anführungszeichen verwenden, um mit einem doppelten Anführungszeichen übereinzustimmen. Wenn wir jedoch innerhalb der doppelten Anführungszeichenfolge ein Zeichen verwenden möchten, müssen wir zwei Zeichen verwenden, um eines zu erhalten. Zum Beispiel in der inneren linken Alternative, die mit einem beliebigen Zeichen außer einem Zitat übereinstimmt:

-"""" .ANY

Ein negativer Blick voraus - "" "wird verwendet, der bei Erfolg (ohne Übereinstimmung mit einem" Zeichen) mit jedem Zeichen übereinstimmt (das kein "Zeichen" sein kann, weil - "" "diese Möglichkeit beseitigt hat). Die richtige Alternative ist es, "" "" einen Charakter zu finden und zu scheitern, waren die richtige Alternative:

"""""",""""

versucht, zwei "Zeichen, die sie durch ein einzelnes Doppel ersetzen, mit", "" zu vergleichen, um das einzelne "Zeichen einzufügen. Beide inneren Alternativen, bei denen das schließende Zeichen in Anführungszeichen nicht erfüllt ist, werden abgeglichen und MAKSTR [] wird aufgerufen, um ein Zeichenfolgenobjekt zu erstellen Sequenz, Schleife, während erfolgreich, Operator wird zum Abgleichen einer Sequenz verwendet. Token-Formel überspringen führende Zeichen der Sprungklasse (mit Leerzeichen). Sobald eine erste Übereinstimmung hergestellt wurde, ist das Überspringen von skip_class deaktiviert. Mit []. MAKSTR können in anderen Sprachen programmierte Funktionen aufgerufen werden [], MAKBIN [], MAKOCT [], MAKHEX [], MAKFLOAT [] und MAKINT [] werden mit Bibliotheksfunktionen geliefert, die eine übereinstimmende Tokenzeichenfolge in ein typisiertes Objekt konvertieren. Die folgende Zahlenformel veranschaulicht eine recht komplexe Tokenerkennung:

number .. "0B" bin $bin MAKBIN[]        // binary integer
         |"0O" oct $oct MAKOCT[]        // octal integer
         |("0H"|"0X") hex $hex MAKHEX[] // hexadecimal integer
// look for decimal number determining if integer or floating point.
         | ('+'|+'-'|--)                // only - matters
           dgt $dgt                     // integer part
           ( +'.' $dgt                  // fractional part?
              ((+'E'|'e','E')           // exponent  part
               ('+'|+'-'|--)            // Only negative matters
               dgt(dgt(dgt|--)|--)|--)  // 1 2 or 3 digit exponent
             MAKFLOAT[] )               // floating point
           MAKINT[];                    // decimal integer

Die obige Zahlentokenformel erkennt Ganzzahl- und Gleitkommazahlen. Die - Alternativen sind immer erfolgreich. Bei Berechnungen können numerische Objekte verwendet werden. Die Token-Objekte werden nach Erfolg der Formel auf den Analysestapel verschoben. Interessant ist die Exponentenführung in (+ 'E' | 'e', ​​'E'). Wir möchten immer ein Großbuchstabe E für MAKEFLOAT [] haben. Wir erlauben jedoch, dass ein 'e' in Kleinbuchstaben durch 'E' ersetzt wird.

Möglicherweise haben Sie Konsistenzen zwischen Zeichenklasse und Tokenformel festgestellt. Die Parsing-Formel setzt das Hinzufügen von Backtracking-Alternativen und Baumkonstruktionsoperatoren fort. Alternative Operatoren für das Zurückverfolgen und Nicht-Zurückverfolgen dürfen nicht innerhalb einer Ausdrucksebene gemischt werden. Möglicherweise müssen Sie nicht (a | b \ c) Non-Backtracking | mischen mit \ backtracking Alternative. (a \ b \ c), (a | b | c) und ((a | b) \ c) sind gültig. Eine \ backtracking-Alternative speichert den Analysezustand, bevor die linke Alternative versucht wird, und stellt bei einem Fehler den Analysezustand wieder her, bevor die rechte Alternative versucht wird. In einer Folge von Alternativen erfüllt die erste erfolgreiche Alternative die Gruppe. Weitere Alternativen werden nicht versucht. Factoring und Gruppierung sorgen für eine kontinuierliche Analyse. Die Backtrack-Alternative erstellt einen gespeicherten Status der Analyse, bevor sie die linke Alternative versucht. Backtracking ist erforderlich, wenn die Analyse möglicherweise teilweise übereinstimmt und dann fehlschlägt:

(a b | c d)\ e

Im obigen Fall wird bei einem Rückgabefehler die alternative CD versucht. Wenn dann c einen Fehler zurückgibt, wird die Backtrack-Alternative versucht. Wenn a erfolgreich ist und b fehlschlägt, wird die Analyse zurückverfolgt und versucht. Ebenso ist ein fehlgeschlagenes c erfolgreich und b fehlgeschlagen. Die Analyse wird zurückverfolgt und die Alternative e genommen. Das Backtracking ist nicht auf eine Formel beschränkt. Wenn eine Analyseformel zu irgendeinem Zeitpunkt teilweise übereinstimmt und dann fehlschlägt, wird die Analyse auf den oberen Backtrack zurückgesetzt und ihre Alternative gewählt. Ein Kompilierungsfehler kann auftreten, wenn Code ausgegeben wurde und der Backtrack erstellt wurde. Vor dem Start der Kompilierung wird ein Backtrack gesetzt. Das Zurückgeben eines Fehlers oder das Zurückverfolgen ist ein Compilerfehler. Backtracks werden gestapelt. Wir können negativ verwenden - und positiv? Peek / Look-Ahead-Operatoren zum Testen, ohne die Analyse voranzutreiben. Ein String-Test ist ein Blick voraus, bei dem nur der Eingabestatus gespeichert und zurückgesetzt werden muss. Ein Blick nach vorne wäre ein Parsing-Ausdruck, der eine teilweise Übereinstimmung ergibt, bevor er fehlschlägt. Ein Blick nach vorne wird durch Backtracking implementiert.

Die Parser-Sprache ist weder ein LL- noch ein LR-Parser. Aber eine Programmiersprache zum Schreiben eines rekursiven anständigen Parsers, in dem Sie die Baumkonstruktion programmieren:

:<node name> creates a node object and pushes it onto the node stack.
..           Token formula create token objects and push them onto 
             the parse stack.
!<number>    pops the top node object and top <number> of parstack 
             entries into a list representation of the tree. The 
             tree then pushed onto the parse stack.
+[ ... ]+    creates a list of the parse stack entries created 
             between them:
              '(' +[argument $(',' argument]+ ')'
             could parse an argument list. into a list.

Ein häufig verwendetes Parsing-Beispiel ist ein arithmetischer Ausdruck:

Exp = Term $(('+':ADD|'-':SUB) Term!2); 
Term = Factor $(('*':MPY|'/':DIV) Factor!2);
Factor = ( number
         | id  ( '(' +[Exp $(',' Exp)]+ ')' :FUN!2
               | --)
         | '(' Exp ')" )
         (^' Factor:XPO!2 |--);

Exp und Term mit einer Schleife erstellen einen Baum für Linkshänder. Der Faktor, der die rechte Rekursion verwendet, erzeugt einen rechtshändigen Baum:

d^(x+5)^3-a+b*c => ADD[SUB[EXP[EXP[d,ADD[x,5]],3],a],MPY[b,c]]

              ADD
             /   \
          SUB     MPY
         /   \   /   \
      EXP     a b     c
     /   \
    d     EXP     
         /   \
      ADD     3
     /   \
    x     5

Hier ist ein Teil des cc-Compilers, einer aktualisierten Version von SLIC mit Kommentaren im c-Stil. Funktionstypen (Grammatik, Token, Zeichenklasse, Generator, PSEUDO oder MACHOP) werden durch ihre anfängliche Syntax nach ihrer ID bestimmt. Mit diesen Top-Down-Parsern beginnen Sie mit einer programmdefinierenden Formel:

program = $((declaration            // A program is a sequence of
                                    // declarations terminated by
            |.EOF .STOP)            // End Of File finish & stop compile
           \                        // Backtrack: .EOF failed or
                                    // declaration long-failed.
             (ERRORX["?Error?"]     // report unknown error
                                    // flagging furthest parse point.
              $(-';' (.ANY          // find a ';'. skiping .ANY
                     | .STOP))      // character: .ANY fails on end of file
                                    // so .STOP ends the compile.
                                    // (-';') failing breaks loop.
              ';'));                // Match ';' and continue

declaration =  "#" directive                // Compiler directive.
             | comment                      // skips comment text
             | global        DECLAR[*1]     // Global linkage
             |(id                           // functions starting with an id:
                ( formula    PARSER[*1]     // Parsing formula
                | sequencer  GENERATOR[*1]  // Code generator
                | optimizer  ISO[*1]        // Optimizer
                | pseudo_op  PRODUCTION[*1] // Pseudo instruction
                | emitor_op  MACHOP[*1]     // Machine instruction
                )        // All the above start with an identifier
              \ (ERRORX["Syntax error."]
                 garbol);                    // skip over error.

// Beachten Sie, wie die ID beim Erstellen des Baums berücksichtigt und später kombiniert wird.

formula =   ("==" syntax  :BCKTRAK   // backtrack grammar formula
            |'='  syntax  :SYNTAX    // grammar formula.
            |':'  chclass :CLASS     // character class define
            |".." token   :TOKEN     // token formula
              )';' !2                // Combine node name with id 
                                     // parsed in calling declaration 
                                     // formula and tree produced
                                     // by the called syntax, token
                                     // or character class formula.
                $(-(.NL |"/*") (.ANY|.STOP)); Comment ; to line separator?

chclass = +[ letter $('|' letter) ]+;// a simple list of character codes
                                     // except 
letter  = char | number | id;        // when including another class

syntax  = seq ('|' alt1|'\' alt2 |--);

alt1    = seq:ALT!2 ('|' alt1|--);  Non-backtrack alternative sequence.

alt2    = seq:BKTK!2 ('\' alt2|--); backtrack alternative sequence

seq     = +[oper $oper]+;

oper    = test | action | '(' syntax ')' | comment; 

test    = string | id ('[' (arg_list| ,NILL) ']':GENCALL!2|.EMPTY);

action  = ':' id:NODE!1
        | '!' number:MAKTREE!1
        | "+["  seq "]+" :MAKLST!1;

//     C style comments
comment  = "//" $(-.NL .ANY)
         | "/*" $(-"*/" .ANY) "*/";

Bemerkenswert ist, wie die Parser-Sprache mit Kommentaren und der Fehlerbehebung umgeht.

Ich glaube, ich habe die Frage beantwortet. Nachdem er einen großen Teil des SLIC-Nachfolgers geschrieben hat, ist die CC-Sprache an sich hier. Es gibt noch keinen Compiler dafür. Aber ich kann es von Hand in Assembler-Code kompilieren, nackte asm c- oder c ++ - Funktionen.

Ja, Sie können einen Compiler für eine Sprache in dieser Sprache schreiben. Nein, Sie benötigen keinen ersten Compiler, damit diese Sprache bootet.

Was Sie zum Bootstrap benötigen, ist eine Implementierung der Sprache. Das kann entweder ein Compiler oder ein Interpreter sein.

Historisch gesehen wurden Sprachen normalerweise entweder als interpretierte oder als kompilierte Sprachen angesehen. Dolmetscher wurden nur für die ersteren und Compiler nur für die letzteren geschrieben. Wenn also ein Compiler für eine Sprache geschrieben werden soll, wird der erste Compiler normalerweise in einer anderen Sprache geschrieben, um ihn zu booten, und optional wird der Compiler für die betreffende Sprache neu geschrieben. Es ist jedoch eine Option, stattdessen einen Dolmetscher in einer anderen Sprache zu schreiben.

Das ist nicht nur theoretisch. Ich mache das gerade selbst. Ich arbeite an einem Compiler für eine Sprache, Salmon, die ich selbst entwickelt habe. Ich habe zuerst einen Salmon-Compiler in C erstellt und jetzt schreibe ich den Compiler in Salmon, damit ich den Salmon-Compiler zum Laufen bringen kann, ohne jemals einen Compiler für Salmon in einer anderen Sprache geschrieben zu haben.

Vielleicht können Sie eine BNF schreiben, die BNF beschreibt.