La deuxième partie de mon histoire de compilateur Swift. Nous allons commencer à étudier le front-end, ou plutôt, les parties de celui-ci qui sont responsables de l'analyse initiale et de l'analyse du code source.
La première partie de l'article se trouve ici .
Frontend
La tâche du frontend est de générer une représentation intermédiaire à partir du code source et de la transférer vers LLVM. Ce processus peut être divisé en 8 étapes. Le résultat de presque chacun d'eux peut être affiché en passant un paramètre spécial au compilateur.
Ci-dessous, je vais démontrer l'implémentation du compilateur pour un "langage de programmation" primitif qui ne contient que "portée" et un nombre. Sa seule fonction est de sortir le numéro (le cas échéant) sur la console. Par exemple, suite à l'exécution de ce "code", le nombre 678 sera affiché:
{{{678}}}
Ce compilateur est uniquement nécessaire pour vous permettre de comprendre plus facilement ce qui se passe à différentes étapes. Une implémentation d'un langage réel mais simple peut être vue dans l'exemple Kaledoscope .
Chaque portée se compose d'un support d'ouverture, d'un contenu et d'un support de fermeture. Cela peut être écrit comme ceci:
scope ::= open_brace x close_brace open_brace ::= "{" close_brace ::= "}"
Le contenu peut avoir la même portée, le même numéro ou rien d'indiqué ici :
scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}"
Symbole | signifie "ou". Un numéro est composé d'un ou plusieurs chiffres:
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"
Un tel enregistrement est appelé la forme Backus-Naur (BNF), et la totalité de toutes les règles est appelée grammaire du langage ou de la syntaxe.
Il existe également un BPF amélioré (RBNF). Des caractères spéciaux supplémentaires y ont été ajoutés, par exemple des parenthèses pour le regroupement.
Les accolades frisées indiquent la répétition. Un tel enregistrement signifie que A est vide ou égal à un nombre quelconque de B:
A ::= { B }
Les crochets sont utilisés pour les occurrences conditionnelles. Un tel enregistrement signifie que A est vide ou égal à B:
A ::= [B]
En utilisant RBNF la grammaire du compilateur de parenthèses, vous pouvez le convertir sous cette forme:
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"
En plus du compilateur de parenthèses, je montrerai comment utiliser le compilateur Swift pour obtenir les résultats de chacune des étapes en utilisant un exemple d'une expression simple:
let x = 16
Le code est si simple qu'il est plus facile à comprendre. La grammaire d'un vrai langage de programmation est beaucoup plus compliquée que la précédente. Vous pouvez consulter la syntaxe Swift sur le site officiel .
Lexer
Du point de vue du compilateur, le fichier de code source est un flux de caractères aléatoires, et peut-être une sorte de poubelle. Par conséquent, la première étape est la conversion de ces caractères aléatoires en mots pouvant être utilisés dans un langage de programmation.
Cela se fait par l'analyseur lexical (lexer / tokenizer). Les mots qu'il recherche sont appelés jetons ou jetons (nous n'entrerons pas dans les détails inutiles et n'accepterons pas ces termes de manière synonyme). Par conséquent, ce processus est également appelé tokenisation.
Le lexer effectue l'analyse selon la syntaxe du langage. Balayant symbole par symbole, il trouve la correspondance du code source et du côté droit de l'enregistrement, puis génère le jeton correspondant du côté gauche.
Exemple d'implémentation de Lexer
La grammaire autorise trois jetons: une parenthèse ouvrante, une parenthèse fermante et un nombre. Ils sont présentés comme une énumération. Ainsi qu'une liste d'erreurs possibles:
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 }
Dans le lexer lui-même, la chaîne d'entrée et l'index du caractère courant sont stockés:
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 }
L'analyse est lancée en appelant la méthode startAnalyze () . Dans ce document, une méthode est appelée dans une boucle pour obtenir le prochain jeton, qui est ajouté au tableau. À la fin - interception des erreurs de reconnaissance:
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 }
L'obtention d'un token consiste à vérifier le caractère courant et à faire avancer l'index d'un ou plusieurs caractères:
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 }
Si un chiffre est trouvé, la méthode getNumber () est appelée pour l'analyser. Il recueille simplement tous les chiffres sur une seule ligne et le convertit en 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) }
Pour démarrer le lexer, vous devez lui passer une ligne avec le code source et appeler la méthode startAnalyze () :
let lexer = Lexer(string: "{{5678}}") let tokens = lexer.startAnalyzing()
Le résultat répond aux attentes:
[openBraceToken, openBraceToken, 5678, closeBraceToken, closeBraceToken]
Dans Swift, le lexer fait partie de l'analyseur et vous ne pouvez pas obtenir une liste de jetons correspondant au code source.
Code source:
Analyseur
L'analyseur effectue l'analyse. Une séquence de jetons est transmise à l'entrée et le résultat du travail est AST.
AST est un graphique dans lequel les sommets sont des opérateurs et les feuilles sont leurs opérandes. Par exemple, l'expression 1 + (2 * 3) se compose de deux opérateurs: addition et multiplication. Le premier opérande d'addition est 1, et le second est le résultat des produits 2 et 3. Les crochets de regroupement ne sont pas utilisés dans AST, car ils ne sont pas nécessaires. Le graphique lui-même détermine l'imbrication des opérations:
Chaque nœud peut être représenté, par exemple, par une structure ou une énumération contenant des éléments enfants.
Lors de la formation de l'arbre, l'analyseur vérifie la grammaire de la langue: si la séquence correcte est composée de «mots». Par exemple, la chaîne "{{}" sera correctement analysée par le lexer, mais elle est incorrecte car le deuxième crochet de fermeture est manquant.
L'analyseur Swift est un analyseur descendant récursif. Cela signifie qu'il trouve d'abord une entité externe, puis analyse récursivement son contenu. L'analyseur ascendant trouve d'abord l'entité la plus imbriquée, puis se lève.
Exemple d'implémentation de l'analyseur
Il existe un grand nombre de types et d'implémentations d'analyseurs. Vous trouverez ci-dessous la mise en œuvre la plus simple d'un analyseur descendant et ascendant pour démontrer clairement la différence.
Commun aux deux analyseurs sera une énumération qui représente l'une des erreurs et le nœud AST:
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 }
Analyseur descendant
Un analyseur vers le bas stocke un tableau de jetons et un index du jeton actuel:
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 }
La seule méthode publique consiste à démarrer l'analyse. Tout d'abord, l'analyse d'une paire de crochets est appelée. Étant donné que l'entité racine ne peut être qu'une paire de crochets (la chaîne "{} {}" n'est pas autorisée), cela suffit. Une analyse plus approfondie sera effectuée de manière récursive. Il ne reste plus qu'à vérifier que le tableau de jetons est vide et à intercepter les exceptions:
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 }
Lors de l'analyse des parenthèses, le crochet ouvrant est d'abord scanné, puis récursivement le contenu de la paire (le cas échéant), et à la fin le crochet fermant.
Un point important: dès que l'analyseur voit la parenthèse ouvrante, il considère qu'il a réussi à trouver la paire suivante et vous pouvez procéder à l'analyse du contenu. C'est pourquoi il passe des entités externes aux entités internes.
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 }
L'analyse consiste à vérifier le jeton et à déplacer l'index en cours:
private func consumeOpenBrace() throws { if let currentToken = self.currentToken, case .openBraceToken = currentToken { print("Open brace found") moveIndex() } else { throw ParserError.expectedOpenBrace } }
Analyseur ascendant
L'implémentation d'un analyseur en amont est un peu plus compliquée. Il doit conserver son état, une pile de jetons et une table de conversion entre les états.
Le statut est présenté comme une énumération. Il est nécessaire pour prendre en compte les jetons précédents et répondre correctement à l'apparition d'un nouveau. Étant donné que cet exemple est très simple, il s'est avéré que dans le premier état, l'analyseur analyse les crochets d'ouverture et dans le second - les crochets de fermeture:
class BottomUpParser { private enum State { case state1 case state2 }
L'analyseur est initialisé de la même manière que le premier. Il n'y a pas de table de transition en tant qu'entité distincte. Par souci de simplification, le commutateur jouera son rôle:
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 }
L'analyse est également lancée à l'aide de la méthode startParsing () . Dans celui-ci, chaque jeton est traité à son tour, et à la fin, une vérification est appelée que la pile est vide et que l'analyse est terminée avec succès:
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 }
Le prochain jeton dans le commutateur est traité en tenant compte de l'état actuel. Si un support d'ouverture arrive et que l'état est 1, il est ajouté à la pile. En cas de fermeture, l'analyseur vérifie s'il y a un support d'ouverture sur la pile pour celui-ci, puis le supprime de la pile et passe à l'état 2. Une transition vers le deuxième état est également effectuée lorsqu'un nombre est trouvé.
L'analyseur continue de supprimer un élément de la pile pour chaque support de fermeture. Si une parenthèse ou un nombre d'ouverture vient à ce moment, c'est une erreur dans le tableau d'entrée.
Un point important: l'analyseur ascendant considère qu'il n'a trouvé la paire qu'après avoir plongé dans la hiérarchie, il voit un crochet fermant, à condition que celui ouvrant soit sur la pile. Ce n'est qu'après cela qu'il recherchera l'essence qui le contient, et ainsi de suite jusqu'à la racine. C'est pourquoi il est appelé ascendant.
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) }
Pour démarrer les deux analyseurs, vous devez passer un tableau de jetons reçus du lexer et appeler la méthode startParsing () :
let parserTD = TopDownParser(tokens: tokens) let ast1 = parserTD.startParsing() let parserBU = BottomUpParser(tokens: tokens) let ast2 = parserBU.startParsing()
Le résultat pour les deux analyseurs était correct:
brace(brace(5678))
Utilisation de l'analyseur Swift
Pour démarrer l'analyseur Swift, vous devez passer l' indicateur -dump-parse au compilateur:
swiftc -dump-parse main.swift
Un véritable AST a une structure plus complexe qu'un analyseur de parenthèses. Mais comme il est petit, vous pouvez facilement le découvrir et trouver le littéral entier 16 et la constante x :
(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))
Cette forme d'AST est un arbre non typé. Par conséquent, la constante x n'a pas le type type = '' spécifié. Si vous le spécifiez explicitement - laissez x: Int = 16 l'arborescence changera, mais le type ne sera pas enregistré de toute façon:
(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))
Code source:
Sema
L'arbre reçu de l'analyseur est grammaticalement correct, mais il peut encore contenir des erreurs. Par exemple, lors de l'analyse, il est impossible (inopportun) de déterminer qu'une variable est déclarée avant utilisation. Cela se fait par l'analyseur sémantique. Il parcourt toute l'arborescence et attribue des types aux expressions, vérifie la prise en charge du protocole, synthétise les initialiseurs par défaut des structures, et bien plus encore.
Utilisation de l'analyseur sémantique Swift
Pour démarrer l'analyseur sémantique, utilisez l' indicateur -dump-ast :
swiftc -dump-ast main.swift
Le résultat de la commande:
(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))
La constante a le type type = 'Int' , ainsi que le niveau d'accès. L'initialisation de la constante est un peu plus compliquée. Ajout du constructeur appel _builtinIntegerLiteral . Si vous représentez cet arbre comme un code Swift, vous obtenez:
internal let x: Int = Int(_builtinIntegerLiteral: 16)
L'exemple suivant contient une erreur:
let x: Bool = 16
Si vous le transmettez à l'analyseur, il ne détectera aucun écart:
(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))
Mais l'analyseur sémantique indiquera ce qui ne va pas avec le code qui lui est transmis:
error: cannot convert value of type 'Int' to specified type 'Bool' let x: Bool = 16
De toute évidence, l'erreur tentait d'affecter une valeur de type Int à une constante de type Bool. Swift ne le permet pas. Merci à l'analyseur sémantique.
Code source:
Importateur de Clang
À ce stade, nous importons les modules Clang et mappons les API C et Objective-C dans les appels correspondants de Swift.
Code source:
Nous avons maintenant un code source complètement analysé qui a réussi le test initial. Mais avant de passer à la génération IR LLVM, vous devez effectuer des optimisations spécifiques à Swift.
La version complète du code source peut être trouvée dans le référentiel .