A segunda parte da minha história do compilador Swift. Começaremos a estudar o front-end, ou melhor, as partes dele responsáveis pela análise inicial e análise do código-fonte.
A primeira parte do artigo pode ser encontrada aqui .
Frontend
A tarefa do front-end é gerar uma representação intermediária a partir do código-fonte e transferi-la para o LLVM. Este processo pode ser dividido em 8 etapas. O resultado de quase cada um deles pode ser exibido passando um parâmetro especial para o compilador.
Abaixo, demonstrarei a implementação do compilador para uma "linguagem de programação" primitiva que contém apenas "escopo" e um número. Sua única função é gerar o número (se houver) para o console. Por exemplo, como resultado da execução desse "código", o número 678 será exibido:
{{{678}}}
Esse compilador é necessário apenas para facilitar a compreensão do que acontece em diferentes estágios. Uma implementação de uma linguagem real, mas simples, pode ser vista no exemplo do Kaledoscope .
Cada escopo consiste em um colchete de abertura, conteúdo e um colchete de fechamento. Isso pode ser escrito assim:
scope ::= open_brace x close_brace open_brace ::= "{" close_brace ::= "}"
O conteúdo pode ter o mesmo escopo, número ou nada indicado aqui :
scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}"
Símbolo significa "ou". Um número consiste em um ou mais 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"
Esse registro é chamado de forma Backus-Naur (BNF) e a totalidade de todas as regras é chamada gramática do idioma ou sintaxe.
Há também um BPF aprimorado (RBNF). Caracteres especiais adicionais foram adicionados a ele, por exemplo, parênteses para agrupamento.
Aparelhos encaracolados indicam repetição. Esse registro significa que A é vazio ou igual a qualquer número de B:
A ::= { B }
Os colchetes são usados para ocorrências condicionais. Esse registro significa que A é vazio ou igual a B:
A ::= [B]
Usando RBNF a gramática do compilador de parênteses, você pode convertê-lo neste formato:
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"
Além do compilador de parênteses, mostrarei como usar o compilador Swift para obter os resultados de cada uma das etapas usando um exemplo de uma expressão simples:
let x = 16
O código é muito simples para facilitar a compreensão. A gramática de uma linguagem de programação real é muito mais complicada do que a anterior. Você pode ver a sintaxe do Swift no site oficial.
Lexer
Do ponto de vista do compilador, o arquivo de código-fonte é um fluxo de caracteres aleatórios e talvez algum tipo de lixo. Portanto, o primeiro passo é a conversão desses caracteres aleatórios em palavras que podem ser usadas em uma linguagem de programação.
Isso é feito pelo analisador lexical (lexer / tokenizer). As palavras que ele procura são chamadas de tokens ou tokens (não entraremos em detalhes desnecessários e aceitaremos esses termos como sinônimos). Portanto, esse processo também é chamado de tokenização.
O lexer realiza a análise de acordo com a sintaxe do idioma. Procurando símbolo por símbolo, ele encontra a correspondência do código-fonte e o lado direito do registro e gera o token correspondente do lado esquerdo.
Exemplo de implementação Lexer
A gramática permite três tokens: um colchete de abertura, um colchete de fechamento e um número. Eles são apresentados como uma enumeração. Bem como uma lista de possíveis erros:
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 }
No próprio lexer, a cadeia de entrada e o índice do caractere atual são armazenados:
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 }
A análise é iniciada chamando o método startAnalyze () . Nele, um método é chamado em um loop para obter o próximo token, que é adicionado à matriz. No final - interceptação de erros de reconhecimento:
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 }
A obtenção de um token consiste em verificar o caractere atual e mover o índice para frente um ou mais 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 }
Se um dígito for encontrado, o método getNumber () será chamado para analisá-lo. Ele simplesmente coleta todos os dígitos em uma linha e o converte em 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 o lexer, você precisa passar uma linha com o código-fonte e chamar o método startAnalyze () :
let lexer = Lexer(string: "{{5678}}") let tokens = lexer.startAnalyzing()
O resultado atende às expectativas:
[openBraceToken, openBraceToken, 5678, closeBraceToken, closeBraceToken]
No Swift, o lexer faz parte do analisador e você não pode obter uma lista de tokens correspondentes ao código-fonte.
Código fonte:
Analisador
O analisador executa a análise. Uma sequência de tokens é transmitida para a entrada e o resultado do trabalho é AST.
AST é um gráfico no qual os vértices são operadores e as folhas são seus operandos. Por exemplo, a expressão 1 + (2 * 3) consiste em dois operadores: adição e multiplicação. O primeiro operando de adição é 1 e o segundo é o resultado dos produtos 2 e 3. Os colchetes de agrupamento não são usados no AST, pois não são necessários. O próprio gráfico determina o aninhamento de operações:
Cada nó pode ser representado, por exemplo, por uma estrutura ou uma enumeração contendo elementos filho.
Durante a formação da árvore, o analisador verifica a gramática do idioma: se a sequência correta é composta de "palavras". Por exemplo, a cadeia "{{}" será analisada com êxito pelo lexer, mas está incorreta porque o segundo colchete está ausente.
O analisador Swift é um analisador descendente recursivo. Isso significa que ele primeiro encontra uma entidade externa e depois analisa recursivamente seu conteúdo. O analisador ascendente primeiro encontra a entidade mais aninhada e depois sobe.
Exemplo de implementação do analisador
Há um grande número de tipos e implementações de analisadores. Abaixo está a implementação mais simples de um analisador descendente e ascendente para demonstrar claramente a diferença.
Comum a ambos os analisadores será uma enumeração que representa um dos erros e o nó 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 }
Analisador descendente
Um analisador descendente armazena uma matriz de tokens e um índice do token atual:
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 }
O único método público é começar a analisar. Primeiro, é chamado analisar um par de colchetes. Como a entidade raiz pode ser apenas um par de colchetes (a cadeia "{} {}" não é permitida), isso é suficiente. Uma análise mais aprofundada será feita recursivamente. Resta apenas verificar se a matriz de tokens está vazia e capturar exceções:
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 }
Ao analisar parênteses, o colchete de abertura é varrido primeiro, depois recursivamente o conteúdo dentro do par (se houver) e, no final, o colchete de fechamento.
Um ponto importante: assim que o analisador vê o colchete de abertura, ele considera que encontrou o próximo par com sucesso e você pode prosseguir com a análise do conteúdo. É por isso que passa de entidades externas para 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 }
A digitalização consiste em verificar o token e mover o índice atual:
private func consumeOpenBrace() throws { if let currentToken = self.currentToken, case .openBraceToken = currentToken { print("Open brace found") moveIndex() } else { throw ParserError.expectedOpenBrace } }
Analisador ascendente
A implementação de um analisador upstream é um pouco mais complicada. Ele precisa manter seu estado, uma pilha de tokens e uma tabela de conversão entre estados.
O status é apresentado como uma enumeração. É necessário levar em consideração os tokens anteriores e responder corretamente à aparência de um novo. Como esse exemplo é muito simples, no primeiro estado, o analisador analisa os colchetes de abertura e, no segundo - os colchetes de fechamento:
class BottomUpParser { private enum State { case state1 case state2 }
O analisador é inicializado de maneira semelhante à primeira. Não há tabela de transição como uma entidade separada. Por uma questão de simplificação, o switch desempenhará seu 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 }
A análise também é iniciada usando o método startParsing () . Nele, cada token é processado por sua vez e, no final, é chamada uma verificação de que a pilha está vazia e a análise concluída com ê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 }
O próximo token na chave é processado levando em consideração o estado atual. Se um colchete de abertura aparecer e o estado for 1, ele será adicionado à pilha. Se estiver fechando, o analisador verifica se há um colchete de abertura na pilha, remove-o da pilha e muda para o estado 2. Uma transição para o segundo estado também é executada quando um número é encontrado.
O analisador continua removendo um elemento da pilha para cada colchete de fechamento. Se um colchete ou número de abertura aparecer neste momento, isso é um erro na matriz de entrada.
Um ponto importante: o analisador ascendente considera que encontrou o par somente depois de mergulhar na hierarquia, vê um colchete de fechamento, desde que o de abertura esteja na pilha. Somente depois disso ele procurará a essência que a contém, e assim por diante até a raiz. Por isso é chamado 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 os dois analisadores, você precisa passar uma matriz de tokens recebidos do lexer e chamar o método startParsing () :
let parserTD = TopDownParser(tokens: tokens) let ast1 = parserTD.startParsing() let parserBU = BottomUpParser(tokens: tokens) let ast2 = parserBU.startParsing()
O resultado para ambos os analisadores estava correto:
brace(brace(5678))
Usando o analisador Swift
Para iniciar o analisador Swift, você precisa passar o sinalizador -dump-parse para o compilador:
swiftc -dump-parse main.swift
Um AST real tem uma estrutura mais complexa do que um analisador de parênteses. Mas como é pequeno, você pode facilmente descobrir e encontrar o literal inteiro 16 e a 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 é uma árvore sem tipo. Portanto, a constante x não possui o tipo type = '' especificado. Se você especificar explicitamente - deixe x: Int = 16 a árvore será alterada, mas o tipo não será registrado de qualquer maneira:
(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 fonte:
Sema
A árvore recebida do analisador está gramaticalmente correta, mas ainda pode haver erros. Por exemplo, durante a análise, é impossível (impraticável) determinar que uma variável seja declarada antes do uso. Isso é feito pelo analisador semântico. Ele percorre toda a árvore e atribui tipos a expressões, verifica o suporte ao protocolo, sintetiza inicializadores padrão para estruturas e muito mais.
Usando o analisador semântico Swift
Para iniciar o analisador semântico, use o sinalizador -dump-ast :
swiftc -dump-ast main.swift
O resultado do 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))
A constante tem o tipo type = 'Int' , bem como o nível de acesso. A inicialização da constante é um pouco mais complicada. Adicionada chamada de construtor _builtinIntegerLiteral . Se você representa essa árvore como um código Swift, obtém:
internal let x: Int = Int(_builtinIntegerLiteral: 16)
O exemplo a seguir contém um erro:
let x: Bool = 16
Se você o passar para o analisador, ele não detectará nenhum desvio:
(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))
Mas o analisador semântico indicará o que há de errado com o código passado para ele:
error: cannot convert value of type 'Int' to specified type 'Bool' let x: Bool = 16
Obviamente, o erro estava tentando atribuir um valor do tipo Int a uma constante do tipo Bool. Swift não permite isso. Graças ao analisador semântico.
Código fonte:
Importador de clang
Nesta fase, importamos os módulos Clang e mapeamos as APIs C e Objective-C para as chamadas correspondentes do Swift.
Código fonte:
Agora, temos um código-fonte completamente analisado que passou no teste inicial. Mas antes de passar para a geração de LLVM IR, você precisa executar otimizações específicas do Swift.
A versão completa do código fonte pode ser encontrada no repositório .