Der zweite Teil meiner Swift-Compiler-Geschichte. Wir werden beginnen, das Frontend oder vielmehr die Teile davon zu untersuchen, die für die anfängliche Analyse und Analyse des Quellcodes verantwortlich sind.
Den ersten Teil des Artikels finden Sie hier .
Frontend
Die Aufgabe des Frontends besteht darin, aus dem Quellcode eine Zwischendarstellung zu generieren und an LLVM zu übertragen. Dieser Vorgang kann in 8 Schritte unterteilt werden. Das Ergebnis von fast jedem von ihnen kann angezeigt werden, indem ein spezieller Parameter an den Compiler übergeben wird.
Im Folgenden werde ich die Implementierung des Compilers für eine primitive "Programmiersprache" demonstrieren, die nur "Gültigkeitsbereich" und eine Nummer enthält. Die einzige Funktion besteht darin, die Nummer (falls vorhanden) an die Konsole auszugeben. Als Ergebnis der Ausführung dieses "Codes" wird beispielsweise die Nummer 678 angezeigt:
{{{678}}}
Dieser Compiler wird nur benötigt, um Ihnen das Verständnis der verschiedenen Phasen zu erleichtern. Eine Implementierung einer realen, aber einfachen Sprache ist im Kaledoskop- Beispiel zu sehen.
Jeder Bereich besteht aus einer öffnenden Klammer, einem Inhalt und einer schließenden Klammer. Dies kann folgendermaßen geschrieben werden:
scope ::= open_brace x close_brace open_brace ::= "{" close_brace ::= "}"
Der Inhalt kann den gleichen Umfang, die gleiche Nummer oder nichts haben, was hier angegeben ist :
scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}"
Symbol | bedeutet "oder". Eine Zahl besteht aus einer oder mehreren Ziffern:
scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}" number ::= digit | number digit digit :: = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Ein solcher Datensatz wird als Backus-Naur (BNF) -Form bezeichnet, und die Gesamtheit aller Regeln wird als Grammatik der Sprache oder Syntax bezeichnet.
Es gibt auch einen verbesserten BPF (RBNF). Es wurden zusätzliche Sonderzeichen hinzugefügt, z. B. Klammern für die Gruppierung.
Geschweifte Klammern zeigen Wiederholung an. Ein solcher Datensatz bedeutet, dass A entweder leer ist oder einer beliebigen Anzahl von B entspricht:
A ::= { B }
Eckige Klammern werden für bedingte Ereignisse verwendet. Ein solcher Datensatz bedeutet, dass A entweder leer oder gleich B ist:
A ::= [B]
Mit RBNF, der Grammatik des Klammer-Compilers, können Sie diese in folgende Form konvertieren:
scope ::= open_brace [scope | number] close_brace open_brace ::= "{" close_brace ::= "}" number ::= digit {digit} digit :: = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Zusätzlich zum Klammer-Compiler werde ich anhand eines Beispiels eines einfachen Ausdrucks zeigen, wie der Swift-Compiler verwendet wird, um die Ergebnisse der einzelnen Schritte zu erhalten:
let x = 16
Der Code ist so einfach, dass er leichter zu verstehen ist. Die Grammatik einer echten Programmiersprache ist viel komplizierter als die oben genannten. Sie können sich die Swift-Syntax auf der offiziellen Website ansehen.
Lexer
Aus Sicht des Compilers ist die Quellcodedatei ein Strom von zufälligen Zeichen und möglicherweise eine Art Müll. Daher ist der erste Schritt die Umwandlung dieser zufälligen Zeichen in Wörter, die in einer Programmiersprache verwendet werden können.
Dies erfolgt durch den lexikalischen Analysator (Lexer / Tokenizer). Die Wörter, die er sucht, werden Token oder Token genannt (wir werden nicht auf unnötige Details eingehen und diese Begriffe synonym akzeptieren). Daher wird dieser Prozess auch als Tokenisierung bezeichnet.
Der Lexer führt die Analyse gemäß der Syntax der Sprache durch. Beim symbolischen Scannen wird die Entsprechung des Quellcodes und der rechten Seite des Datensatzes gefunden und anschließend das entsprechende Token von der linken Seite generiert.
Lexer-Implementierungsbeispiel
Die Grammatik erlaubt drei Token: eine öffnende Klammer, eine schließende Klammer und eine Zahl. Sie werden als Aufzählung dargestellt. Sowie eine Liste möglicher Fehler:
enum Token: CustomStringConvertible { case openBraceToken case closeBraceToken case number(Int) var description: String { switch self { case .openBraceToken: return "openBraceToken" case .closeBraceToken: return "closeBraceToken" case .number(let value): return "\(value)" } } } enum LexerError: Error { case unexpectedCharacted case invalidNumber }
Im Lexer selbst werden die Eingabezeichenfolge und der Index des aktuellen Zeichens gespeichert:
class Lexer { private let string: String private var index: String.Index private var currentCharacter: Character? { return index != string.endIndex ? string[index] : nil } init(string: String) { self.string = string index = string.startIndex }
Die Analyse wird durch Aufrufen der Methode startAnalyze () gestartet. Darin wird eine Methode in einer Schleife aufgerufen, um das nächste Token zu erhalten, das dem Array hinzugefügt wird. Am Ende - Abfangen von Erkennungsfehlern:
func startAnalyzing() -> [Token] { var result: [Token] = [] do { while let token = try getNextToken() { result.append(token) } } catch LexerError.unexpectedCharacted { print("Unexpected character at index \(index.encodedOffset)") result = [] } catch LexerError.invalidNumber { print("Invalid number at index \(index.encodedOffset)") result = [] } catch { print("Unexpected error") result = [] } return result }
Das Abrufen eines Tokens besteht darin, das aktuelle Zeichen zu überprüfen und den Index um ein oder mehrere Zeichen vorwärts zu verschieben:
private func getNextToken() throws -> Token? { guard let character = currentCharacter else { return nil } switch character { case "{": return getOpenBrace() case "}": return getCloseBrace() default: break } if let scalar = character.unicodeScalars.first, CharacterSet.decimalDigits.contains(scalar) { return try getNumber() } throw LexerError.unexpectedCharacted } private func getOpenBrace() -> Token { moveIndex() return Token.openBraceToken } private func getCloseBrace() -> Token { moveIndex() return Token.closeBraceToken }
Wenn eine Ziffer gefunden wird, wird die Methode getNumber () aufgerufen , um sie zu analysieren. Es sammelt einfach alle Ziffern in einer Zeile und konvertiert sie in Int:
private func getNumber() throws -> Token { var numberString = "" while let character = currentCharacter, let scalar = character.unicodeScalars.first, CharacterSet.decimalDigits.contains(scalar) { numberString.append(character) moveIndex() } guard let number = Int(numberString) else { throw LexerError.invalidNumber } return Token.number(number) }
Um den Lexer zu starten, müssen Sie ihm eine Zeile mit dem Quellcode übergeben und die Methode startAnalyze () aufrufen :
let lexer = Lexer(string: "{{5678}}") let tokens = lexer.startAnalyzing()
Das Ergebnis entspricht den Erwartungen:
[openBraceToken, openBraceToken, 5678, closeBraceToken, closeBraceToken]
In Swift ist der Lexer Teil des Parsers, und Sie können keine Liste der Token erhalten, die dem Quellcode entsprechen.
Quellcode:
Parser
Der Parser führt eine Analyse durch. Eine Folge von Token wird an die Eingabe übertragen, und das Ergebnis der Arbeit ist AST.
AST ist ein Diagramm, in dem die Eckpunkte Operatoren und die Blätter ihre Operanden sind. Zum Beispiel besteht der Ausdruck 1 + (2 * 3) aus zwei Operatoren: Addition und Multiplikation. Der erste Additionsoperand ist 1 und der zweite ist das Ergebnis der Produkte 2 und 3. Gruppierungsklammern werden in AST nicht verwendet, da sie nicht erforderlich sind. Das Diagramm selbst bestimmt die Verschachtelung von Operationen:
Jeder Knoten kann beispielsweise durch eine Struktur oder eine Aufzählung mit untergeordneten Elementen dargestellt werden.
Während der Bildung des Baums überprüft der Parser die Grammatik der Sprache: ob die richtige Reihenfolge aus „Wörtern“ besteht. Beispielsweise wird die Zeichenfolge "{{}" vom Lexer erfolgreich analysiert, ist jedoch falsch, da die zweite schließende Klammer fehlt.
Der Swift-Parser ist ein rekursiver absteigender Parser. Dies bedeutet, dass er zuerst eine externe Entität findet und dann deren Inhalt rekursiv analysiert. Der aufsteigende Parser findet zuerst die am meisten verschachtelte Entität und steigt dann auf.
Parser-Implementierungsbeispiel
Es gibt eine große Anzahl von Arten und Implementierungen von Parsern. Im Folgenden finden Sie die einfachste Implementierung eines absteigenden und aufsteigenden Parsers, um den Unterschied deutlich zu machen.
Beiden Parsern gemeinsam ist eine Aufzählung, die einen der Fehler und den AST-Knoten darstellt:
indirect enum ASTNode: CustomStringConvertible { case brace(childNode: ASTNode?) case number(value: Int) var description: String { switch self { case let .brace(childNode?): return "brace(\(childNode.description))" case .brace(nil): return "brace(nil)" case let .number(value): return "\(value)" } } } enum ParserError: Error { case expectedOpenBrace case expectedCloseBrace case expectedNumber case expectedEndOfArray }
Absteigender Parser
Ein Abwärtsparser speichert ein Array von Token und einen Index des aktuellen Tokens:
class TopDownParser { private let tokens: [Token] private var index: Int private var currentToken: Token? { return index != tokens.endIndex ? tokens[index] : nil } init(tokens: [Token]) { self.tokens = tokens index = tokens.startIndex }
Die einzige öffentliche Methode besteht darin, mit dem Parsen zu beginnen. Zunächst wird das Parsen eines Klammerpaares aufgerufen. Da die Stammentität nur aus zwei Klammern bestehen kann (die Zeichenfolge "{} {}" ist nicht zulässig), reicht dies aus. Weitere Analysen werden rekursiv durchgeführt. Es bleibt nur zu überprüfen, ob das Token-Array leer ist und um Ausnahmen abzufangen:
func startParsing() -> ASTNode? { var rootNode: ASTNode? do { rootNode = try parseBraces() guard currentToken == nil else { rootNode = nil throw ParserError.expectedEndOfArray } } catch ParserError.expectedCloseBrace { print("Expected close brace at index \(index)") } catch ParserError.expectedOpenBrace { print("Expected open brace at index \(index)") } catch ParserError.expectedEndOfArray { print("Expected end of tokens array at index \(index)") } catch { print("Unexpected error") } return rootNode }
Beim Parsen von Klammern wird zuerst die öffnende Klammer gescannt, dann rekursiv der Inhalt innerhalb des Paares (falls vorhanden) und am Ende die schließende Klammer.
Ein wichtiger Punkt: Sobald der Parser die öffnende Klammer sieht, geht er davon aus, dass er das nächste Paar erfolgreich gefunden hat, und Sie können mit der Analyse des Inhalts fortfahren. Deshalb geht es von externen zu internen Entitäten.
private func parseBraces() throws -> ASTNode? { try consumeOpenBrace() print("Pair found") let node: ASTNode? if let currentToken = self.currentToken, case .openBraceToken = currentToken { node = .brace(childNode: try parseBraces()) } else if let currentToken = self.currentToken, case let .number(value) = currentToken { node = .brace(childNode: .number(value: value)) try consumeNumber() } else { node = .brace(childNode: nil) } try consumeCloseBrace() return node }
Das Scannen besteht aus dem Überprüfen des Tokens und dem Verschieben des aktuellen Index:
private func consumeOpenBrace() throws { if let currentToken = self.currentToken, case .openBraceToken = currentToken { print("Open brace found") moveIndex() } else { throw ParserError.expectedOpenBrace } }
Aufsteigender Parser
Die Implementierung eines Upstream-Parsers ist etwas komplizierter. Er muss seinen Status, einen Stapel Token und eine Umrechnungstabelle zwischen den Status behalten.
Der Status wird als Aufzählung dargestellt. Es ist notwendig, um frühere Token zu berücksichtigen und korrekt auf das Erscheinen eines neuen zu reagieren. Da dieses Beispiel sehr einfach ist, stellte sich heraus, dass der Parser im ersten Zustand die öffnenden Klammern und im zweiten die schließenden Klammern analysiert:
class BottomUpParser { private enum State { case state1 case state2 }
Der Parser wird ähnlich wie der erste initialisiert. Es gibt keine Übergangstabelle als separate Entität. Der Einfachheit halber wird der Schalter seine Rolle spielen:
private let tokens: [Token] private var index: Int private var state: State = .state1 private var stack: [Token] = [] private var rootNode: ASTNode? private var currentToken: Token? { return index != tokens.endIndex ? tokens[index] : nil } init(tokens: [Token]) { self.tokens = tokens index = tokens.startIndex }
Die Analyse wird auch mit der Methode startParsing () gestartet. Darin wird jedes Token nacheinander verarbeitet, und am Ende wird eine Überprüfung aufgerufen, ob der Stapel leer ist und das Parsen erfolgreich abgeschlossen wurde:
func startParsing() -> ASTNode? { do { guard !tokens.isEmpty else { throw ParserError.expectedOpenBrace } while index != tokens.endIndex { try parseNextToken() moveIndex() } guard stack.isEmpty else { rootNode = nil throw ParserError.expectedCloseBrace } } catch ParserError.expectedCloseBrace { rootNode = nil print("Expected close brace at index \(index)") } catch ParserError.expectedOpenBrace { rootNode = nil print("Expected open brace at index \(index)") } catch ParserError.expectedEndOfArray { rootNode = nil print("Expected end of tokens array at index \(index)") } catch { rootNode = nil print("Unexpected error") } return rootNode }
Das nächste Token im Switch wird unter Berücksichtigung des aktuellen Status verarbeitet. Wenn eine öffnende Klammer eintrifft und der Status 1 ist, wird sie dem Stapel hinzugefügt. Beim Schließen prüft der Parser, ob sich auf dem Stapel eine öffnende Klammer befindet, entfernt sie dann aus dem Stapel und wechselt in den Status 2. Ein Übergang in den zweiten Status wird auch ausgeführt, wenn eine Zahl gefunden wird.
Der Parser entfernt weiterhin ein Element für jede schließende Klammer vom Stapel. Wenn zu diesem Zeitpunkt eine öffnende Klammer oder Nummer kommt, ist dies ein Fehler im Eingabearray.
Ein wichtiger Punkt: Der Aufwärtsparser ist der Ansicht, dass er das Paar erst gefunden hat, nachdem er die Hierarchie heruntergestürzt hat. Er sieht eine schließende Klammer, vorausgesetzt, die erste befindet sich auf dem Stapel. Erst danach wird er nach der Essenz suchen, die sie enthält, und so weiter bis zur Wurzel. Deshalb heißt es aufsteigend.
private func parseNextToken() throws { guard let currentToken = currentToken else { return } switch (state, currentToken) { case (.state1, .openBraceToken): print("Open brace found") stack.append(.openBraceToken) case (.state1, .number(let value)): if stack.isEmpty { throw ParserError.expectedOpenBrace } else { consumeNumber(value: value) state = .state2 } case (.state1, .closeBraceToken): if stack.isEmpty { throw ParserError.expectedOpenBrace } else { consumeCloseBrace() state = .state2 } case (.state2, .closeBraceToken): if stack.isEmpty { throw ParserError.expectedEndOfArray } else { consumeCloseBrace() } case (.state2, .number), (.state2, .openBraceToken): if stack.isEmpty { throw ParserError.expectedEndOfArray } else { throw ParserError.expectedCloseBrace } } } private func consumeCloseBrace() { print("Close brace found") _ = stack.popLast() print("Pair found") if rootNode == nil { rootNode = .brace(childNode: nil) } else { rootNode = .brace(childNode: rootNode) } } private func consumeNumber(value: Int) { rootNode = .number(value: value) }
Um beide Parser zu starten, müssen Sie ein Array von Token übergeben, die vom Lexer empfangen wurden, und die Methode startParsing () aufrufen :
let parserTD = TopDownParser(tokens: tokens) let ast1 = parserTD.startParsing() let parserBU = BottomUpParser(tokens: tokens) let ast2 = parserBU.startParsing()
Das Ergebnis für beide Parser war korrekt:
brace(brace(5678))
Verwenden des Swift Parser
Um den Swift-Parser zu starten, müssen Sie das Flag -dump-parse an den Compiler übergeben:
swiftc -dump-parse main.swift
Ein realer AST hat eine komplexere Struktur als ein Parser in Klammern. Da es jedoch klein ist, können Sie es leicht herausfinden und das ganzzahlige Literal 16 und die Konstante x finden :
(source_file (top_level_code_decl (brace_stmt (pattern_binding_decl (pattern_named 'x') (integer_literal_expr type='<null>' value=16)) )) (var_decl "x" type='<null type>' let storage_kind=stored))
Diese Form von AST ist ein untypisierter Baum. Daher ist für die Konstante x nicht der Typ type = '' angegeben. Wenn Sie es explizit angeben - lassen Sie x: Int = 16, der Baum ändert sich, aber der Typ wird trotzdem nicht registriert:
(source_file (top_level_code_decl (brace_stmt (pattern_binding_decl (pattern_typed (pattern_named 'x') (type_ident (component id='Int' bind=none))) (integer_literal_expr type='<null>' value=16)) )) (var_decl "x" type='<null type>' let storage_kind=stored))
Quellcode:
Sema
Der vom Parser empfangene Baum ist grammatikalisch korrekt, kann jedoch weiterhin Fehler enthalten. Während des Parsens ist es beispielsweise unmöglich (unzweckmäßig) festzustellen, dass eine Variable vor der Verwendung deklariert wird. Dies erfolgt durch den semantischen Analysator. Es durchläuft den gesamten Baum und weist Ausdrücken Typen zu, überprüft die Protokollunterstützung, synthetisiert Standardinitialisierer für Strukturen und vieles mehr.
Verwenden des Swift Semantic Analyzer
Verwenden Sie das Flag -dump-ast, um den semantischen Analysator zu starten:
swiftc -dump-ast main.swift
Das Ergebnis des Befehls:
(source_file (top_level_code_decl (brace_stmt (pattern_binding_decl (pattern_named type='Int' 'x') (call_expr implicit type='Int' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] nothrow arg_labels=_builtinIntegerLiteral: (constructor_ref_call_expr implicit type='(_MaxBuiltinIntegerType) -> Int' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] nothrow (declref_expr implicit type='(Int.Type) -> (_MaxBuiltinIntegerType) -> Int' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] decl=Swift.(file).Int.init(_builtinIntegerLiteral:) function_ref=single) (type_expr implicit type='Int.Type' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] typerepr='Int')) (tuple_expr implicit type='(_builtinIntegerLiteral: Int2048)' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] names=_builtinIntegerLiteral (integer_literal_expr type='Int2048' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] value=16)))) )) (var_decl "x" type='Int' interface type='Int' access=internal let storage_kind=stored))
Die Konstante hat den Typ type = 'Int' sowie die Zugriffsebene. Die Initialisierung der Konstante ist etwas komplizierter. Konstruktoraufruf _builtinIntegerLiteral hinzugefügt . Wenn Sie diesen Baum als Swift-Code darstellen, erhalten Sie:
internal let x: Int = Int(_builtinIntegerLiteral: 16)
Das folgende Beispiel enthält einen Fehler:
let x: Bool = 16
Wenn Sie es an den Parser übergeben, werden keine Abweichungen festgestellt:
(source_file (top_level_code_decl (brace_stmt (pattern_binding_decl (pattern_typed (pattern_named 'x') (type_ident (component id='Bool' bind=none))) (integer_literal_expr type='<null>' value=16)) )) (var_decl "x" type='<null type>' let storage_kind=stored))
Der semantische Analysator zeigt jedoch an, was mit dem an ihn übergebenen Code nicht stimmt:
error: cannot convert value of type 'Int' to specified type 'Bool' let x: Bool = 16
Offensichtlich hat der Fehler versucht, einer Konstante vom Typ Bool einen Wert vom Typ Int zuzuweisen. Swift erlaubt das nicht. Dank des semantischen Analysators.
Quellcode:
Clang Importeur
In dieser Phase importieren wir die Clang-Module und ordnen die C- und Objective-C-APIs den entsprechenden Aufrufen von Swift zu.
Quellcode:
Jetzt haben wir einen vollständig analysierten Quellcode, der den ersten Test bestanden hat. Bevor Sie jedoch mit der LLVM-IR-Generierung fortfahren, müssen Sie Swift-spezifische Optimierungen durchführen.
Die Vollversion des Quellcodes finden Sie im Repository .