前言

本章对应 官方教程第2章 ，介绍实现解析器(Parser)和抽象语法树(AST)。

开始

AST

AST用来解释代码的行为，我们希望语言中的每个构造都有一个AST，所以我们首先需要一个AST的基类，在swift中我们可以使用 protocol 。

protocol ExprAST {}
复制代码

注意，在Kaleidoscope中我们只支持Double类型，所以首先我们需要有一个保存数值的AST。

class NumberExprAST: ExprAST {
    
    let value: Double
    
    init(_ value: Double) {
        self.value = value
    }
    
}
复制代码

用于保存变量名的AST，比如说保存"abc"。

class VariableExprAST: ExprAST {
    
    let name: String
    
    init(_ name: String) {
        self.name = name
    }
    
}
复制代码

用于保存二元运算符的AST，比如"+"。

class BinaryExprAST: ExprAST {
    
    let op: String
    
    let lhs: ExprAST
    
    let rhs: ExprAST
    
    init(_ op: String, _ lhs: ExprAST, _ rhs: ExprAST) {
        self.op = op
        self.lhs = lhs
        self.rhs = rhs
    }
    
}
复制代码

因为这个类适用于二元运算符，所以AST需要记录操作符左边的AST(lhs)以及右边的AST(rhs)以及操作符的名字。

函数的AST包括原型AST( PrototypeAST )、函数定义AST( FunctionAST )和函数调用AST( CallExprAST )。原型AST即函数的声明。

class PrototypeAST {
    
    let name: String
    
    let args: [String]
    
    init(_ name: String, _ args: [String]) {
        self.name = name
        self.args = args
    }
    
}
复制代码

PrototypeAST需要保存函数名以及参数名。

class FunctionAST {
    
    let proto: PrototypeAST
    
    let body: ExprAST
    
    init(_ proto: PrototypeAST, _ body: ExprAST) {
        self.proto = proto
        self.body = body
    }
    
}
复制代码

FunctionAST保存函数声明的AST proto和函数定义的AST body。

class CallExprAST: ExprAST {
    
    var callee: String?
    
    var args: [ExprAST]?
    
    init(_ callee: String, _ args: [ExprAST]) {
        self.callee = callee
        self.args = args
    }
    
}
复制代码

CallExprAST用来解析函数的调用。

开始解析

在上一章中，我们已经实现了一个可以解析出token的lexer。下面我们需要完善Lexer并且实现Parser，它用来解析出AST。

我们为Lexer添加输入方法以及代理方法提供给Parser。

    /// 解析代码
    ///
    /// - Parameter sourceInput: 代码数据源
    public func start(_ sourceInput: String) {
        let blockArray = sourceInput.split(separator: ";")
        for block in blockArray {
            source = Array(block + ";")
            index = 0
            lastChar = " "
            nextToken()
            switch currentToken!.token {
            case .def:
                delegate?.lexerWithDefinition(self)
                continue
            case .extern:
                delegate?.lexerWithExtern(self)
                continue
            case .number, .identifier:
                delegate?.lexerWithTopLevelExpression(self)
                continue
            default:
                continue
            }
        }
    }
复制代码

因为Kaleidoscope用";"分割代码块，为了方便处理我们就可以直接根据";"进行分块解析即可。

接下来我们定义Parser。

class Parser {
    
    private let lexer = Lexer()
    
    init() {
        lexer.delegate = self
    }
    
}

extension Parser {
    
    /// 解析代码
    ///
    /// - Parameter sourceInput: 代码数据源
    public func parse(_ sourceInput: String) {
        lexer.start(sourceInput)
    }
    
}
复制代码

解析基本表达式

我们从解析数字开始。

    /// 解析数值常量
    ///
    /// - Returns: AST
    private func parseNumberExpr() -> ExprAST {
        let result = NumberExprAST(Double(lexer.currentToken!.val)!)
        lexer.nextToken()
        return result
    }
复制代码

这个其实看代码毫无疑问，生成NumberAST完获取下一个token即可。

解析 "'(' expression ')'" 形式的表达式。

    /// 解析'('开头的表达式
    ///
    /// - Returns: AST
    func parseParenExpr() -> ExprAST? {
        lexer.nextToken()//跳过'('
        let v = parseExpression()
        guard v != nil else {
            return nil
        }
        if lexer.currentToken!.val != ")" {
            fatalError("Expected '\(lexer.currentToken!.val)'")
        }
        lexer.nextToken()//跳过')'
        return v
    }
复制代码

parseExpression()方法将会在下面介绍到。

解析变量或者函数调用。

    /// 解析变量引用和函数调用
    ///
    /// - Returns: AST
    private func parseIdentifierExpr() -> ExprAST? {
        let idName = lexer.currentToken!.val
        lexer.nextToken()
        if lexer.currentToken!.val != "(" {
          	//说明只是普通的变量
            return VariableExprAST(idName)
        }
      	//走到这说明是函数调用
        lexer.nextToken()
        var args: [ExprAST] = []
        if lexer.currentToken!.val != ")" {
          	//这个循环用来解析传入参数
            while true {
                let arg = parseExpression()
                guard arg != nil else {
                    return nil
                }
                args.append(arg!)
              	//匹配到")"说明解析该结束了
                if lexer.currentToken!.val == ")" {
                    break
                }
              	//不同参数之间用","分割
                if lexer.currentToken!.val != "," {
                    fatalError("Expected ')' or ',' in argument list"