Bagian kedua dari kisah kompiler Swift saya. Kami akan mulai mempelajari front-end, atau lebih tepatnya, bagian-bagiannya yang bertanggung jawab untuk analisis awal dan analisis kode sumber.
Bagian pertama artikel dapat ditemukan di sini .
Frontend
Tugas frontend adalah untuk menghasilkan representasi perantara dari kode sumber dan mentransfernya ke LLVM. Proses ini dapat dibagi menjadi 8 langkah. Hasil dari hampir masing-masing dapat ditampilkan dengan mengirimkan parameter khusus ke kompiler.
Di bawah ini saya akan menunjukkan implementasi kompiler untuk "bahasa pemrograman" primitif yang hanya berisi "ruang lingkup" dan angka. Satu-satunya fungsi adalah untuk menampilkan nomor (jika ada) ke konsol. Misalnya, sebagai hasil dari eksekusi "kode" ini, angka 678 akan ditampilkan:
{{{678}}}
Kompiler ini hanya diperlukan untuk memudahkan Anda memahami apa yang terjadi pada tahapan yang berbeda. Implementasi bahasa nyata, tetapi sederhana dapat dilihat pada contoh Kaledoscope .
Setiap ruang lingkup terdiri dari braket pembuka, konten, dan braket penutup. Ini dapat ditulis seperti ini:
scope ::= open_brace x close_brace open_brace ::= "{" close_brace ::= "}"
Konten mungkin memiliki cakupan, jumlah yang sama, atau tidak ada yang ditunjukkan di sini :
scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}"
Simbol | berarti "atau." Angka terdiri dari satu atau lebih digit:
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"
Catatan semacam itu disebut bentuk Backus-Naur (BNF), dan totalitas semua aturan disebut tata bahasa atau sintaksis.
Ada juga BPF yang ditingkatkan (RBNF). Karakter khusus tambahan ditambahkan ke dalamnya, misalnya, tanda kurung untuk pengelompokan.
Kurung kurawal menunjukkan pengulangan. Catatan semacam itu berarti bahwa A kosong atau sama dengan sejumlah B:
A ::= { B }
Kurung kotak digunakan untuk kejadian bersyarat. Catatan semacam itu berarti bahwa A kosong atau sama dengan B:
A ::= [B]
Menggunakan RBNF tata bahasa dari kompiler tanda kurung, Anda dapat mengubahnya menjadi bentuk ini:
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"
Selain kompiler tanda kurung, saya akan menunjukkan cara menggunakan kompiler Swift untuk mendapatkan hasil dari setiap langkah menggunakan contoh ekspresi sederhana:
let x = 16
Kode ini sangat sederhana untuk membuatnya lebih mudah dimengerti. Tata bahasa bahasa pemrograman yang sebenarnya jauh lebih rumit daripada yang di atas. Anda dapat melihat sintaks Swift di situs web resmi.
Lexer
Dari sudut pandang kompiler, file kode sumber adalah aliran karakter acak, dan mungkin semacam sampah. Oleh karena itu, langkah pertama adalah konversi karakter acak ini menjadi kata-kata yang dapat digunakan dalam bahasa pemrograman.
Ini dilakukan oleh penganalisa leksikal (lexer / tokenizer). Kata-kata yang ia cari disebut token atau token (kami tidak akan masuk ke detail yang tidak perlu dan menerima istilah ini secara sinonim). Karena itu, proses ini juga disebut tokenization.
Lexer melakukan analisis sesuai dengan sintaks bahasa. Memindai simbol demi simbol, ia menemukan korespondensi dari kode sumber dan sisi kanan catatan, dan kemudian menghasilkan token yang sesuai dari sisi kiri.
Contoh implementasi Lexer
Tata bahasa memungkinkan tiga token: braket pembuka, braket penutup, dan angka. Mereka disajikan sebagai enumerasi. Serta daftar kemungkinan kesalahan:
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 }
Lexer sendiri menyimpan string input dan indeks karakter saat ini:
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 }
Analisis dimulai dengan memanggil metode startAnalyze () . Di dalamnya, sebuah metode disebut dalam satu lingkaran untuk mendapatkan token berikutnya, yang ditambahkan ke array. Pada akhirnya - intersepsi kesalahan pengakuan:
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 }
Memperoleh token terdiri dari memeriksa karakter saat ini dan memajukan indeks satu atau lebih karakter:
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 }
Jika digit ditemukan, maka metode getNumber () dipanggil untuk menguraikannya. Ini hanya mengumpulkan semua digit menjadi satu baris dan mengubahnya menjadi 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) }
Untuk memulai lexer, Anda harus memberikannya baris dengan kode sumber dan memanggil metode startAnalyze () :
let lexer = Lexer(string: "{{5678}}") let tokens = lexer.startAnalyzing()
Hasilnya memenuhi harapan:
[openBraceToken, openBraceToken, 5678, closeBraceToken, closeBraceToken]
Di Swift, lexer adalah bagian dari parser, dan Anda tidak bisa mendapatkan daftar token yang sesuai dengan kode sumber.
Kode Sumber:
Parser
Parser melakukan parsing. Urutan token ditransmisikan ke input, dan hasil pekerjaan adalah AST.
AST adalah grafik di mana simpul adalah operator dan daun adalah operan mereka. Misalnya, ekspresi 1 + (2 * 3) terdiri dari dua operator: penjumlahan dan perkalian. Operan tambahan pertama adalah 1, dan yang kedua adalah hasil dari produk 2 dan 3. Kurung pengelompokan tidak digunakan dalam AST, karena tidak diperlukan. Grafik itu sendiri menentukan operasi bersarang:
Setiap node dapat diwakili, misalnya, oleh suatu struktur atau enumerasi yang mengandung elemen anak.
Selama pembentukan pohon, parser memeriksa tata bahasa: apakah urutan yang benar terdiri dari "kata-kata". Misalnya, string "{{}" akan berhasil diurai oleh lexer, tetapi tidak benar karena braket penutup kedua tidak ada.
Pengurai Swift adalah pengurai menurun rekursif. Ini berarti bahwa ia pertama kali menemukan entitas eksternal, dan kemudian secara rekursif menganalisis isinya. Pengurai naik pertama-tama menemukan entitas yang paling bersarang, dan kemudian naik.
Contoh implementasi Parser
Ada sejumlah besar tipe dan implementasi parser. Di bawah ini adalah implementasi paling sederhana dari parser descending dan ascending untuk secara jelas menunjukkan perbedaannya.
Umum untuk kedua parser adalah enumerasi yang mewakili salah satu kesalahan dan simpul 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 }
Pengurai menurun
Parser ke bawah menyimpan array token dan indeks token saat ini:
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 }
Satu-satunya metode publik adalah mulai parsing. Pertama, parsing sepasang kurung disebut. Karena entitas root hanya bisa berupa kurung (string "{} {}" tidak diizinkan), ini sudah cukup. Analisis lebih lanjut akan dilakukan secara rekursif. Tetap hanya memverifikasi bahwa array token kosong dan untuk menangkap pengecualian:
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 }
Saat parsing tanda kurung, braket pembuka dipindai terlebih dahulu, kemudian secara rekursif konten dalam pasangan (jika ada), dan pada akhirnya braket penutup.
Poin penting: segera setelah parser melihat braket pembuka, ia menganggap bahwa ia telah berhasil menemukan pasangan berikutnya dan Anda dapat melanjutkan ke analisis konten. Itu sebabnya ia beralih dari entitas eksternal ke entitas internal.
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 }
Pemindaian terdiri dari memeriksa token dan memindahkan indeks saat ini:
private func consumeOpenBrace() throws { if let currentToken = self.currentToken, case .openBraceToken = currentToken { print("Open brace found") moveIndex() } else { throw ParserError.expectedOpenBrace } }
Pengurai naik
Mengimplementasikan parser hulu sedikit lebih rumit. Dia perlu mempertahankan statusnya, setumpuk token, dan tabel konversi antar negara.
Status disajikan sebagai enumerasi. Hal ini diperlukan untuk memperhitungkan token sebelumnya dan menanggapi dengan benar penampilan yang baru. Karena contoh ini sangat sederhana, ternyata pada kondisi pertama, parser mengurai kurung pembuka, dan pada yang kedua - kurung penutup:
class BottomUpParser { private enum State { case state1 case state2 }
Parser diinisialisasi mirip dengan yang pertama. Tidak ada tabel transisi sebagai entitas terpisah. Demi penyederhanaan, switch akan memainkan perannya:
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 }
Analisis juga diluncurkan menggunakan metode startParsing () . Di dalamnya, setiap token diproses secara bergantian, dan pada akhirnya, sebuah cek disebut bahwa stack kosong dan penguraian selesai dengan sukses:
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 }
Token in switch berikutnya diproses dengan mempertimbangkan kondisi saat ini. Jika braket pembuka tiba dan negara adalah 1, maka ditambahkan ke tumpukan. Jika ditutup, parser memeriksa untuk melihat apakah ada braket pembuka pada tumpukan untuknya, kemudian memindahkannya dari tumpukan dan beralih ke status 2. Transisi ke keadaan kedua juga dilakukan ketika angka ditemukan.
Parser terus menghapus satu elemen dari tumpukan untuk setiap braket penutup. Jika braket atau nomor pembuka datang pada saat ini, ini merupakan kesalahan dalam array input.
Poin penting: parser ke atas menganggap bahwa mereka menemukan pasangan hanya setelah menurunkan hierarki, ia melihat braket penutup, asalkan yang membuka ada di tumpukan. Hanya setelah itu ia akan mencari esensi yang mengandungnya, dan seterusnya ke root. Itulah sebabnya itu disebut naik.
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) }
Untuk memulai kedua parser, Anda perlu mentransfer sejumlah token yang diterima dari lexer dan memanggil metode startParsing () :
let parserTD = TopDownParser(tokens: tokens) let ast1 = parserTD.startParsing() let parserBU = BottomUpParser(tokens: tokens) let ast2 = parserBU.startParsing()
Hasil untuk kedua parser itu benar:
brace(brace(5678))
Menggunakan Swift Parser
Untuk memulai parser Swift, Anda harus meneruskan flag -dump-parse ke kompiler:
swiftc -dump-parse main.swift
AST nyata memiliki struktur yang lebih kompleks daripada parser tanda kurung. Tetapi karena kecil, Anda dapat dengan mudah mengetahuinya dan menemukan bilangan bulat 16 dan konstanta 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))
Bentuk AST ini adalah pohon yang tidak diketik. Oleh karena itu, konstanta x tidak memiliki tipe type = '' yang ditentukan. Jika Anda menentukannya secara eksplisit - misalkan x: Int = 16 pohon akan berubah, tetapi jenisnya tidak akan terdaftar:
(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))
Kode Sumber:
Sema
Pohon yang diterima dari parser benar secara tata bahasa, tetapi mungkin masih ada kesalahan di dalamnya. Misalnya, selama parsing tidak mungkin (tidak murah) untuk menentukan bahwa variabel dideklarasikan sebelum digunakan. Ini dilakukan oleh penganalisa semantik. Ini berjalan melalui seluruh pohon dan menetapkan jenis ekspresi, memeriksa dukungan protokol, mensintesis inisialisasi default untuk struktur, dan banyak lagi.
Menggunakan penganalisis semantik Swift
Untuk memulai penganalisis semantik, gunakan flag -dump-ast :
swiftc -dump-ast main.swift
Hasil dari perintah:
(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))
Konstanta memiliki tipe type = 'Int' , serta tingkat akses. Inisialisasi konstanta sedikit lebih rumit. Menambahkan panggilan konstruktor _builtinIntegerLiteral . Jika Anda mewakili pohon ini sebagai kode Swift, Anda mendapatkan:
internal let x: Int = Int(_builtinIntegerLiteral: 16)
Contoh berikut berisi kesalahan:
let x: Bool = 16
Jika Anda meneruskannya ke parser, maka itu tidak akan mendeteksi penyimpangan:
(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))
Tetapi penganalisis semantik akan menunjukkan apa yang salah dengan kode yang diteruskan ke sana:
error: cannot convert value of type 'Int' to specified type 'Bool' let x: Bool = 16
Jelas, kesalahan itu mencoba untuk menetapkan nilai tipe Int ke konstanta tipe Bool. Swift tidak mengizinkan ini. Terima kasih kepada penganalisa semantik.
Kode Sumber:
Importir dentang
Pada tahap ini, kita mengimpor modul Dentang dan memetakan API C dan Objective-C ke panggilan yang sesuai dari Swift.
Kode Sumber:
Sekarang kami memiliki kode sumber yang telah diuraikan sepenuhnya yang telah lulus tes awal. Tetapi sebelum beralih ke generasi IR LLVM, Anda perlu melakukan optimasi khusus Swift.
Versi lengkap dari kode sumber dapat ditemukan di repositori .