La segunda parte de mi historia del compilador Swift. Comenzaremos a estudiar la interfaz, o más bien, aquellas partes de ella que son responsables del análisis inicial y el análisis del código fuente.
La primera parte del artículo se puede encontrar aquí .
Frontend
La tarea de la interfaz es generar una representación intermedia del código fuente y transferirla a LLVM. Este proceso se puede dividir en 8 pasos. El resultado de casi cada uno de ellos se puede mostrar pasando un parámetro especial al compilador.
A continuación, demostraré la implementación del compilador para un "lenguaje de programación" primitivo que contiene solo "alcance" y un número. Su única función es enviar el número (si lo hay) a la consola. Por ejemplo, como resultado de la ejecución de este "código", se mostrará el número 678:
{{{678}}}
Este compilador solo es necesario para que le resulte más fácil comprender lo que sucede en las diferentes etapas. Una implementación de un lenguaje real pero simple se puede ver en el ejemplo Kaledoscope .
Cada alcance consta de un corchete de apertura, contenido y un corchete de cierre. Esto se puede escribir así:
scope ::= open_brace x close_brace open_brace ::= "{" close_brace ::= "}"
El contenido puede ser el mismo alcance, número o nada indicado aquí :
scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}"
Símbolo | significa "o". Un número consta de uno o más dígitos:
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"
Tal registro se llama la forma Backus-Naur (BNF), y la totalidad de todas las reglas se llama gramática del lenguaje o sintaxis.
También hay un BPF mejorado (RBNF). Se le agregaron caracteres especiales adicionales, por ejemplo, paréntesis para la agrupación.
Las llaves indican la repetición. Tal registro significa que A está vacío o es igual a cualquier número de B:
A ::= { B }
Los corchetes se usan para ocurrencias condicionales. Tal registro significa que A está vacío o es igual a B:
A ::= [B]
Usando RBNF la gramática del compilador de paréntesis, puede convertirlo a esta forma:
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"
Además del compilador de paréntesis, mostraré cómo usar el compilador Swift para obtener los resultados de cada uno de los pasos usando un ejemplo de una expresión simple:
let x = 16
El código es muy simple para que sea más fácil de entender. La gramática de un lenguaje de programación real es mucho más complicada que la anterior. Puede consultar la sintaxis de Swift en el sitio web oficial.
Lexer
Desde el punto de vista del compilador, el archivo de código fuente es una secuencia de caracteres aleatorios, y tal vez algún tipo de basura. Por lo tanto, el primer paso es la conversión de estos caracteres aleatorios en palabras que pueden usarse en un lenguaje de programación.
Esto lo realiza el analizador léxico (lexer / tokenizer). Las palabras que busca se llaman tokens o tokens (no entraremos en detalles innecesarios y aceptaremos estos términos como sinónimos). Por lo tanto, este proceso también se llama tokenización.
El lexer realiza el análisis de acuerdo con la sintaxis del lenguaje. Al escanear símbolo por símbolo, encuentra la correspondencia del código fuente y el lado derecho del registro, y luego genera el token correspondiente desde el lado izquierdo.
Ejemplo de implementación de Lexer
La gramática permite tres fichas: un corchete de apertura, un corchete de cierre y un número. Se presentan como una enumeración. Además de una lista de posibles errores:
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 }
En el lexer mismo, la cadena de entrada y el índice del carácter actual se almacenan:
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 }
El análisis se inicia llamando al método startAnalyze () . En él, se llama a un método en un bucle para obtener el siguiente token, que se agrega a la matriz. Al final - intercepción de errores de reconocimiento:
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 }
La obtención de un token consiste en verificar el carácter actual y mover el índice hacia adelante uno o más caracteres:
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 se encuentra un dígito, se llama al método getNumber () para analizarlo. Simplemente recopila todos los dígitos en una línea y la convierte a 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) }
Para iniciar el lexer, debe pasar una línea con el código fuente y llamar al método startAnalyze () :
let lexer = Lexer(string: "{{5678}}") let tokens = lexer.startAnalyzing()
El resultado cumple con las expectativas:
[openBraceToken, openBraceToken, 5678, closeBraceToken, closeBraceToken]
En Swift, el lexer es parte del analizador y no puede obtener una lista de tokens correspondientes al código fuente.
Código fuente:
Analizador
El analizador realiza el análisis. Se transmite una secuencia de tokens a la entrada y el resultado del trabajo es AST.
AST es un gráfico en el que los vértices son operadores y las hojas son sus operandos. Por ejemplo, la expresión 1 + (2 * 3) consta de dos operadores: suma y multiplicación. El primer operando de adición es 1, y el segundo es el resultado de los productos 2 y 3. Los corchetes de agrupación no se usan en AST, ya que no son necesarios. El gráfico mismo determina el anidamiento de las operaciones:
Cada nodo puede estar representado, por ejemplo, por una estructura o una enumeración que contiene elementos secundarios.
Durante la formación del árbol, el analizador comprueba la gramática del lenguaje: si la secuencia correcta está compuesta de "palabras". Por ejemplo, la cadena "{{}" será analizada con éxito por el lexer, pero es incorrecta porque falta el segundo corchete de cierre.
El analizador Swift es un analizador descendente recursivo. Esto significa que primero encuentra una entidad externa y luego analiza recursivamente su contenido. El analizador ascendente primero encuentra la entidad más anidada y luego se levanta.
Ejemplo de implementación del analizador
Hay una gran cantidad de tipos e implementaciones de analizadores. A continuación se muestra la implementación más simple de un analizador descendente y ascendente para demostrar claramente la diferencia.
Común para ambos analizadores será una enumeración que representa uno de los errores y el nodo 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 }
Analizador descendente
Un analizador descendente almacena una matriz de tokens y un índice del token actual:
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 }
El único método público es comenzar a analizar. Primero, se llama analizar un par de paréntesis. Dado que la entidad raíz solo puede ser un par de paréntesis (la cadena "{} {}" no está permitida), esto es suficiente. El análisis adicional se realizará de forma recursiva. Solo queda verificar que la matriz de tokens esté vacía y detectar excepciones:
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 }
Al analizar paréntesis, primero se escanea el paréntesis de apertura, luego recursivamente los contenidos dentro del par (si corresponde) y al final el paréntesis de cierre.
Un punto importante: tan pronto como el analizador vea el paréntesis de apertura, considere que ha encontrado con éxito el siguiente par y puede proceder al análisis de los contenidos. Es por eso que pasa de entidades externas a internas.
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 }
El escaneo consiste en verificar el token y mover el índice actual:
private func consumeOpenBrace() throws { if let currentToken = self.currentToken, case .openBraceToken = currentToken { print("Open brace found") moveIndex() } else { throw ParserError.expectedOpenBrace } }
Analizador ascendente
Implementar un analizador ascendente es un poco más complicado. Necesita mantener su estado, una pila de tokens y una tabla de conversión entre estados.
El estado se presenta como una enumeración. Es necesario para tener en cuenta los tokens anteriores y responder correctamente a la aparición de uno nuevo. Como este ejemplo es muy simple, resultó que en el primer estado, el analizador analiza los corchetes de apertura y, en el segundo, los corchetes de cierre:
class BottomUpParser { private enum State { case state1 case state2 }
El analizador se inicializa de manera similar al primero. No hay una tabla de transición como una entidad separada. En aras de la simplificación, el interruptor jugará su papel:
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 }
El análisis también se inicia utilizando el método startParsing () . En él, cada token se procesa por turno, y al final, se llama a una verificación de que la pila está vacía y el análisis se completa con éxito:
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 }
El siguiente token en el interruptor se procesa teniendo en cuenta el estado actual. Si llega un corchete de apertura y el estado es 1, se agrega a la pila. Si se cierra, el analizador verifica si hay un paréntesis de apertura en la pila, luego lo retira de la pila y cambia al estado 2. También se realiza una transición al segundo estado cuando se encuentra un número.
El analizador continúa eliminando un elemento de la pila para cada paréntesis de cierre. Si aparece un paréntesis de apertura o un número en este momento, se trata de un error en la matriz de entrada.
Un punto importante: el analizador ascendente considera que encontró el par solo después de hundirse en la jerarquía, ve un corchete de cierre, siempre que el de apertura esté en la pila. Solo después de eso buscará la esencia que lo contiene, y así sucesivamente hasta la raíz. Por eso se llama ascendente.
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) }
Para iniciar ambos analizadores, debe pasar una matriz de tokens recibidos del lexer y llamar al método startParsing () :
let parserTD = TopDownParser(tokens: tokens) let ast1 = parserTD.startParsing() let parserBU = BottomUpParser(tokens: tokens) let ast2 = parserBU.startParsing()
El resultado para ambos analizadores fue correcto:
brace(brace(5678))
Usando el analizador Swift
Para iniciar el analizador Swift, debe pasar el indicador -dump-parse al compilador:
swiftc -dump-parse main.swift
Un AST real tiene una estructura más compleja que un analizador de paréntesis. Pero dado que es pequeño, puede resolverlo fácilmente y encontrar el entero literal 16 y 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))
Esta forma de AST es un árbol sin tipo. Por lo tanto, la constante x no tiene el tipo type = '' especificado. Si lo especifica explícitamente, deje que x: Int = 16 el árbol cambie, pero el tipo no se registrará de todos modos:
(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))
Código fuente:
Sema
El árbol recibido del analizador es gramaticalmente correcto, pero aún puede haber errores en él. Por ejemplo, durante el análisis es imposible (poco conveniente) determinar que una variable se declara antes de su uso. Esto lo hace el analizador semántico. Atraviesa todo el árbol y asigna tipos a expresiones, verifica el soporte de protocolo, sintetiza inicializadores predeterminados para estructuras y mucho más.
Usando el analizador semántico Swift
Para iniciar el analizador semántico, use el indicador -dump-ast :
swiftc -dump-ast main.swift
El resultado del comando:
(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 tiene el tipo type = 'Int' , así como el nivel de acceso. La inicialización de la constante es un poco más complicada. Se agregó la llamada al constructor _builtinIntegerLiteral . Si representa este árbol como un código Swift, obtendrá:
internal let x: Int = Int(_builtinIntegerLiteral: 16)
El siguiente ejemplo contiene un error:
let x: Bool = 16
Si lo pasa al analizador, no detectará ninguna desviación:
(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))
Pero el analizador semántico indicará qué está mal con el código que se le pasó:
error: cannot convert value of type 'Int' to specified type 'Bool' let x: Bool = 16
Obviamente, el error estaba tratando de asignar un valor de tipo Int a una constante de tipo Bool. Swift no permite esto. Gracias al analizador semántico.
Código fuente:
Importador de Clang
En esta etapa, importamos los módulos de Clang y asignamos las API C y Objective-C a las llamadas correspondientes de Swift.
Código fuente:
Ahora tenemos un código fuente completamente analizado que ha pasado la prueba inicial. Pero antes de pasar a la generación LLVM IR, debe realizar optimizaciones específicas de Swift.
La versión completa del código fuente se puede encontrar en el repositorio .