Hallo allerseits! Als Programmierer bin ich immer auf der Suche nach Möglichkeiten, meine Fähigkeiten zu verbessern. An einem Freitagabend kam mir der Gedanke: "Würden Sie mir einen Compiler schreiben?"
Wer möchte herausfinden, was daraus geworden ist? Willkommen bei Cat.
Basierend auf der "Klassischen Theorie des Compilers" V. E. Karpov können wir 5 Hauptstufen der Kompilierung unterscheiden:
- Lexikalische Analyse
- Parsen
- Mittlere Codegenerierung
- Optimierung
- Generierung von Final, Objekt, Code
Über alles, fünf Teile, können Sie viele Sätze und Artikel schreiben. Aber heute werden wir über die ersten beiden sprechen und wie ich ihre Struktur in einer separaten Bibliothek ausgewählt habe.
Als ich mich entschied, auch nur einen kleinen Teil des Compilers zu schreiben, dachte ich nicht darüber nach, für welche Sprache ich schrieb. Aus diesem Grund war das Ergebnis eine Bibliothek für die lexikalische und syntaktische Analyse einer Sprache.
Tokenisierung
Bevor Sie eine Syntax und einen lexikalischen Baum erstellen, den resultierenden Code generieren und andere leckere Dinge tun, müssen Sie den Quellcode in Zeilen, Zeichen und Zahlen aufteilen.
Wobei jedes Element einen genau definierten Typ hat. Undefinierte Typ-Token werden beim Parsen als Syntaxfehler betrachtet.
Im Zusammenhang mit der Kompilierung wird der Quellcode als Quellzuordnung betrachtet. Es wird empfohlen, ihn während des Lexik- und Analyseprozesses zu speichern, um Rückmeldungen vom Programmierer zu erhalten und Syntaxfehler im Quellcode anzuzeigen.
Sie können den Quellcode mit einem einfachen regulären Ausdruck in ein Array von Token aufteilen:
/\S+/gm
Dies kann sich abhängig von zusätzlichen Analysebedingungen ändern, z. B.: Zeilenumbruchanalyse, Tabulatoranalyse, Leerzeichenanalyse.
Das Ergebnis der Trennung wird eine Anordnung von Wörtern des Quellcodes sein, und die Wörter werden von Raum zu Raum analysiert, d.h. dieses Design:
let hello = 'world';
Es wird in den folgenden Satz von Token konvertiert:
["let", "hello", "=", "'world';"]
Um den endgültigen Satz von Token zu erhalten, müssen Sie jeden mit einem zusätzlichen regulären Ausdruck durchgehen:
/(\W)|(\w+)/gm
Das Ergebnis ist die Menge an Token, die wir benötigen:
["let", "hello", "=", "'", "world", "'", ";"]
Alle Token, die wir erhalten haben, schreiben wir zusammen mit ihren Indizes in der Quellkarte in das Array
Lexikalische Analyse
Nachdem wir nun eine Reihe von Token haben, müssen wir ihren Typ bestimmen, um sie an das Parsen zu übergeben.
Der Algorithmus, der Token und ihre Typen definiert, heißt Lexer
Das Token und sein Typ, die Lexer definiert, werden als Token bezeichnet
Jedes Token kann einen eindeutig definierten Typ haben, zum Beispiel:
['let', 'const', 'var']
Ich habe jedoch ein Schema zur Bestimmung der Tokentypen unter Verwendung des sogenannten Solver'ov implementiert.
Es funktioniert wie folgt:
1. Sie definieren Konstanten für Tokentypen:
const DefaultTokenTypes = { KEYWORD: "Keyword", IDENTIFIER: "Identifier", OPERATOR: "Operator", DELIMITER: "Delimiter", LINEBREAK: "Linebreak", STRING: "String", NUMERIC: "Numeric", UNKNOWN: 'Unknown' };
2. Als nächstes ist es notwendig, den sogenannten Solver'y zu bestimmen:
const solvers = {}; solvers[MyTokenTypes.KEYWORD] = { include: [ 'const', 'let' ] }; solvers[MyTokenTypes.NUMERIC] = { regexp: /^[0-9.]*$/gm }; solvers[DefaultTokenTypes.STRING] = { type: StringSolver, delimiters: ['"', "'", '`'] }; solvers[MyTokenTypes.IDENTIFIER] = { regexp: /^[a-zA-Z_][a-zA-Z_0-9]*$/gm }; solvers[MyTokenTypes.DELIMITER] = { default: true };
Wie Sie sehen können, können Token unterschiedliche Einstellungen haben:
include - Eine Reihe von Wörtern, mit denen zufällig die Art des Tokens bestimmt werden kann.
regexp - Ein regulärer Ausdruck, mit dem zufällig die Art des Tokens bestimmt werden kann.
Standard - Der Standardtyp für undefinierte Token.
Sie können auch den Typparameter bemerken, der angibt, dass dieser Solver von dem in
type angegebenen Parameter geerbt werden soll
In diesem Fall definiert der Solver Zeichenfolgen, die in einem der in
Trennzeichen angegebenen Zeichen eingeschlossen sind
3. Wir verwenden Löser für das Token-Array und erhalten ein Array typisierter Token. Für einen bestimmten Quellcode:
let a = 50;
Wir bekommen folgenden Baum:
[ { "type": "Keyword", "value": "let", "range": [0, 3] }, { "type": "Identifier", "value": "a", "range": [4, 5] }, { "type": "Delimiter", "value": "=", "range": [6, 7] }, { "type": "Numeric", "value": "50", "range": [8, 10] }, { "type": "Delimiter", "value": ";", "range": [10, 11] } ]
Wobei
Bereich der Anfang und das Ende des Fragments im Quellcode ist.
Parsen
Nachdem Sie ein Array von Token erhalten haben, sollten Sie diese analysieren und die syntaktische Struktur (Baum) des Quellcodes bestimmen.
Es gibt verschiedene Optionen zum Parsen, aber ich habe einen direkten Top-Down-Algorithmus gewählt.
Token werden nacheinander mithilfe einer Reihe von Vorlagen analysiert. Wenn die Vorlage mit der aktuellen Token-Sequenz übereinstimmt, wird im Syntaxbaum ein neuer Zweig erstellt.
Ein Beispiel für eine Vorlage aus einem Array:
let declaration = new SequenceNode({ tokenType: MyTokenTypes.KEYWORD, type: MyNodeTypes.DECLARATION, sequence: [ {type: MyTokenTypes.KEYWORD}, {type: MyTokenTypes.IDENTIFIER}, {type: MyTokenTypes.DELIMITER}, {type: [MyTokenTypes.NUMERIC, MyTokenTypes.STRING]}, ';' ], onError: (e) => {
tokenType - Beschreibt das Token, von dem aus nach einer Übereinstimmung
gesucht werden soll .
Typ - Beschreibt den Knotentyp. Alle Typen sollten ebenfalls definiert werden, ähnlich wie bei Tokentypen.
Sequenz - Ein Array einer Sequenz, das Token-Typen, bestimmte Werte oder andere Knoten des Syntaxbaums enthält.
onError -
Rückruf , der funktioniert, wenn ein Syntaxfehler
auftritt . Beim Parsen dieses Knotens wird der Fehlertyp + sein Platz im Quellcode zurückgegeben.
Lassen Sie uns die
Reihenfolge dieses Knotens analysieren:
[ {type: MyTokenTypes.KEYWORD},
Ich habe verschiedene Variationen von Knoten für verschiedene Zwecke implementiert: Definieren von Token-Sequenzen, Definieren einer Gruppe von Elementen (Argumente, Blöcke). Dadurch können Pfeilfunktionen problemlos analysiert werden.
Sie können alle Variationen von Solvern und Knoten lesen, die ich in der Dokumentation dieser Bibliothek implementiert habe.
Material
→
Quelllink :
Tyk→
Klassische Compilertheorie