我的Swift编译器故事的第二部分。 我们将开始研究前端，或者更确切地说，是负责源代码的初始分析和分析的那些部分。
文章的第一部分可以在这里找到。
前端
前端的任务是从源代码生成中间表示并将其传输到LLVM。 此过程可以分为8个步骤。 通过将特殊参数传递给编译器，可以显示几乎每个参数的结果。
下面，我将演示仅包含“作用域”和数字的原始“编程语言”的编译器实现。 它的唯一功能是将数字（如果有）输出到控制台。 例如，作为执行此“代码”的结果，将显示数字678：
{{{678}}}
仅需要此编译器，以使您更容易了解不同阶段发生的情况。 在Kaledoscope示例中可以看到一种真实而简单的语言的实现 。
每个范围都由一个开头括号，内容和一个结尾括号组成。 可以这样写：
scope ::= open_brace x close_brace open_brace ::= "{" close_brace ::= "}"
内容可以是相同的范围，编号，或此处未显示任何内容：
scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}"
符号 表示“或”。 一个数字由一个或多个数字组成：
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"
这样的记录称为Backus-Naur（BNF）形式，所有规则的总和称为语言或语法的语法。
还有一个增强的BPF（RBNF）。 其他特殊字符已添加到其中，例如，用于分组的括号。
大括号表示重复。 这样的记录意味着A为空或等于B的任意数量：
A ::= { B }
方括号用于有条件的出现。 这样的记录意味着A为空或等于B：
A ::= [B]
使用RBNF括号编译器的语法，可以将其转换为以下形式：
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"
除了括号编译器之外，我还将通过一个简单表达式的示例演示如何使用Swift编译器获取每个步骤的结果：
let x = 16
该代码非常简单，易于理解。 真正的编程语言的语法比上述复杂得多。 您可以在官方网站上查看Swift语法。
Lexer
从编译器的角度来看，源代码文件是随机字符流，并且可能是某种垃圾。 因此，第一步是将这些随机字符转换为可以在编程语言中使用的单词。
这是由词法分析器（词法分析器/令牌生成器）完成的。 他寻找的单词称为标记或标记（我们将不再赘述，并以同义的方式接受这些术语）。 因此，此过程也称为令牌化。
词法分析器根据语言的语法执行分析。 逐个符号地扫描，找到源代码和记录右侧的对应关系，然后从左侧生成对应的令牌。
Lexer实现示例
语法允许使用三个标记：左括号，右括号和数字。 它们以枚举形式呈现。 以及可能的错误列表：
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 }
在词法分析器本身中，存储了输入字符串和当前字符的索引：
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 }
通过调用startAnalyze（）方法开始分析。 在其中，在循环中调用一个方法来获取下一个令牌，该令牌将添加到数组中。 最后-拦截识别错误：
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 }
获取令牌包括检查当前字符并将索引向前移动一个或多个字符：
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 }
如果找到一个数字，则调用getNumber（）方法进行解析。 它只是将所有数字收集到一行中，然后将其转换为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) }
要启动词法分析器，您需要向其传递源代码行并调用startAnalyze（）方法：
let lexer = Lexer(string: "{{5678}}") let tokens = lexer.startAnalyzing()
结果符合预期：
[openBraceToken, openBraceToken, 5678, closeBraceToken, closeBraceToken]
在Swift中，词法分析器是解析器的一部分，您无法获取与源代码相对应的标记列表。
源代码：
解析器
解析器执行解析。 令牌序列被传输到输入，并且工作结果为AST。
AST是一个图形，其中顶点是运算符，叶是它们的操作数。 例如，表达式1 +（2 * 3）由两个运算符组成：加法和乘法。 第一个加法操作数是1，第二个是乘积2和3的结果。AST中不使用分组括号，因为它们不是必需的。 图本身确定操作的嵌套：
每个节点可以例如由包含子元素的结构或枚举表示。
在树的形成过程中，解析器检查语言的语法：正确的序列是否由“单词”组成。 例如，字符串“ {{}”将被词法分析器成功解析，但是由于缺少第二个右括号，因此它是不正确的。
Swift解析器是递归的降序解析器。 这意味着他首先找到一个外部实体，然后递归分析其内容。 升序分析器首先找到嵌套最多的实体，然后上升。
解析器实现示例
解析器有很多类型和实现。 下面是降序和升序解析器的最简单实现，以清楚地说明两者之间的区别。
这两个解析器的共同点是代表错误之一和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 }
降序解析器
向下解析器存储令牌数组和当前令牌的索引：
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 }
唯一的公共方法是开始解析。 首先，调用解析一对括号。 由于根实体只能是一对括号（不允许使用字符串“ {} {}” ），这就足够了。 进一步分析将以递归方式进行。 它仅用于验证令牌数组为空并捕获异常：
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 }
解析括号时，首先会扫描开括号，然后递归扫描该对中的内容（如果有），最后是闭括号。
重要的一点是：解析器一看到括号，就认为它已经成功找到了下一对，您可以继续分析内容了。 这就是为什么它从外部实体变为内部实体的原因。
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 }
扫描包括检查令牌和移动当前索引：
private func consumeOpenBrace() throws { if let currentToken = self.currentToken, case .openBraceToken = currentToken { print("Open brace found") moveIndex() } else { throw ParserError.expectedOpenBrace } }
升序解析器
实现上游解析器要复杂一些。 他需要保持状态，一堆令牌和状态之间的转换表。
状态显示为枚举。 为了考虑以前的令牌并正确响应新令牌的出现，有必要。 由于此示例非常简单，因此结果表明，在第一种状态下，解析器解析左括号，而在第二种状态下，右括号：
class BottomUpParser { private enum State { case state1 case state2 }
解析器的初始化与第一个类似。 没有过渡表作为单独的实体。 为了简化起见，switch将扮演以下角色：
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 }
还使用startParsing（）方法启动分析。 其中，依次处理每个令牌，最后，调用检查以检查堆栈是否为空并成功完成解析：
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 }
考虑到当前状态，将处理switch中的下一个令牌。 如果到达左括号，并且状态为1，则将其添加到堆栈中。 如果关闭，则解析器检查堆栈上是否有一个开放括号，然后将其从堆栈中移出并切换到状态2。找到数字后，还将执行到第二状态的转换。
解析器继续为每个右括号从堆栈中删除一个元素。 如果此时有一个右括号或数字，则表示输入数组有误。
重要的一点是：向上解析器认为只有在降低层次结构之后才找到该对，如果打开的一个位于堆栈中，它将看到一个闭合括号。 只有在那之后，他才会搜索包含它的本质，依此类推。 这就是为什么它被称为上升。
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) }
要启动两个解析器，您需要传递从词法分析器收到的令牌数组，并调用startParsing（）方法：
let parserTD = TopDownParser(tokens: tokens) let ast1 = parserTD.startParsing() let parserBU = BottomUpParser(tokens: tokens) let ast2 = parserBU.startParsing()
两个解析器的结果都是正确的：
brace(brace(5678))
使用Swift解析器
要启动Swift解析器，您需要将-dump-parse标志传递给编译器：
swiftc -dump-parse main.swift
实际的AST具有比括号解析器更复杂的结构。 但是由于它很小，您可以轻松地找出来并找到整数文字16和常数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))
这种形式的AST是无类型的树。 因此，常量x没有指定类型type =''。 如果您明确指定它-令x：Int = 16，则树将更改，但是无论如何都不会注册类型：
(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))
源代码：
塞玛
从解析器收到的树在语法上是正确的，但是其中可能仍然存在错误。 例如，在解析期间，不可能（不方便）确定在使用变量之前声明了变量。 这是由语义分析器完成的。 它遍历整个树，为表达式分配类型，检查协议支持，为结构综合默认初始化程序，等等。
使用Swift语义分析器
要启动语义分析器，请使用-dump-ast标志：
swiftc -dump-ast main.swift
命令的结果：
(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))
该常量的类型为type ='Int' ，以及访问级别。 常量的初始化有点复杂。 添加了构造函数调用_builtinIntegerLiteral 。 如果将此树表示为Swift代码，则会得到：
internal let x: Int = Int(_builtinIntegerLiteral: 16)
以下示例包含一个错误：
let x: Bool = 16
如果将其传递给解析器，则它将不会检测到任何偏差：
(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))
但是语义分析器将指示传递给它的代码出了什么问题：
error: cannot convert value of type 'Int' to specified type 'Bool' let x: Bool = 16
显然，该错误试图将Int类型的值分配给Bool类型的常量。 Swift不允许这样做。 感谢语义分析器。
源代码：
lang族进口商
在这个阶段，我们导入Clang模块并将C和Objective-C API映射到Swift的相应调用中。
源代码：
现在，我们已经通过了最初的测试，已经完全解析了源代码。 但是在进行LLVM IR生成之前，您需要执行Swift特定的优化。
完整版本的源代码可以在存储库中找到。