教你使用swift写编译器玩具（2）

前言

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

教程如下:

开始

AST

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

1	`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")
            }
            lexer.nextToken()
        }
    }
    
    lexer.nextToken()
    
    return CallExprAST(idName, args)
}

现在我们已经有了所有简单表达式解析的逻辑了，我们把它们的调用写一个统一的入口。

/// 解析基本表达式的入口
///
/// - Returns: AST
private func parsePrimary() -> ExprAST? {
    guard lexer.currentToken != nil else {
        return nil
    }
    if lexer.currentToken!.val == "(" {
        return parseParenExpr()
    }
    switch lexer.currentToken!.token {
    case .identifier:
        return parseIdentifierExpr()
    case .number:
        return parseNumberExpr()
    default:
        fatalError("unknow token when expecting an expression")
    }
}

解析二元表达式

首先我们需要定义一个全局的操作符优先级表

1	`var BinOpPrecedence: [String: UInt] = ["<": 10, "+": 20, "-": 20, "*": 40]`

value越大代表优先级越大，很明显”*”是大于”+”的，目前我们只支持4个运算符，当然你自己可以支持更多的运算符。

接着在Parser中定义获得操作符优先级的方法。

/// 获取currentToken对应的运算符优先级
///
/// - Returns: 优先级
private func getTokenPrecedence() -> Int {
    if BinOpPrecedence[lexer.currentToken!.val] == nil {
        return -1
    } else {
        return Int(BinOpPrecedence[lexer.currentToken!.val]!)
    }
}

接下来我们需要实现parseExpression()方法。

/// 解析表达式
///
/// - Returns: AST
func parseExpression() -> ExprAST? {
    var lhs = parsePrimary()
    guard lhs != nil else {
        return nil
    }
    return parseBinOpRHS(0, &lhs!)
}

运算优先级的解析思想是将二元运算符的表达式分为多个部分。运算符优先级解析的基本思想就是通过拆解含有二元运算符的表达式来解决可能的二义性问题。以表达式a+b+(c+d)*e*f+g为例，在进行运算符优先级解析时，它将被视作一串按二元运算符分隔的主表达式。按照这个思路，解析出来的第一个主表达式应该是a，紧跟着是若干个有序对，即：[+, b]、[+, (c+d)]、[*, e]、[*, f]和[+, g]。注意，括号表达式也是主表达式，所以在解析二元表达式时无须特殊照顾(c+d)这样的嵌套表达式。

/// 解析二元运算符
///
/// - Parameters:
///   - exprPrec: 二元运算符优先级
///   - lhs: 左表达式
/// - Returns: AST
private func parseBinOpRHS(_ exprPrec: Int, _ lhs: inout ExprAST) -> ExprAST? {
    while true {
        let tokPrec = getTokenPrecedence()
        if tokPrec < exprPrec {
            return lhs
        }
        
        //获取二元运算符
        let binOp = lexer.currentToken
        lexer.nextToken()
        
        //解析二元运算符右边的表达式
        var rhs = parsePrimary()
        guard rhs != nil else {
            return nil
        }
        
        let nextPrec = getTokenPrecedence()
        if tokPrec < nextPrec {
            //如果下一个符号优先级更高，则递归调用自己把它们拼成一个rhs返回
            rhs = parseBinOpRHS(tokPrec + 1, &rhs!)
            guard rhs != nil else {
                return nil
            }
        }
      	//合并lhr和rhs
        lhs = BinaryExprAST(binOp!.val, lhs, rhs!)
    }
}

解析其余结构

下面来解析函数原型。在Kaleidoscope中，有两处会用到函数原型：一是extern函数声明，二是函数定义。

/// 解析函数原型
///
/// - Returns: 函数原型AST
func parsePrototype() -> PrototypeAST {
    var fnName: String
    
    switch lexer.currentToken!.token {
    case .identifier:
        fnName = lexer.currentToken!.val
        lexer.nextToken()
        break
    default:
        fatalError("Expected function name in prototype.")
    }
    
    if lexer.currentToken!.val != "(" {
        fatalError("Expected '(' in prototype")
    }
    
    lexer.nextToken()
    var argNames: [String] = []
    while lexer.currentToken!.token == .identifier {
        argNames.append(lexer.currentToken!.val)
        lexer.nextToken()
    }
    if lexer.currentToken!.val != ")" {
        fatalError("Expected ')' in prototype")
    }
    lexer.nextToken()
    
    return PrototypeAST(fnName, argNames)
}

解析函数定义就更简单了，只需要先解析函数原型再解析表达式即可。

/// 解析函数定义
///
/// - Returns: 函数定义AST
private func parseDefinition() -> FunctionAST? {
    lexer.nextToken()
    let proto = parsePrototype()
    if let e = parseExpression() {
        return FunctionAST(proto, e)
    }
    return nil
}

解析extern也很简单，因为也是解析函数原型。

/// 解析extern导出定义
///
/// - Returns: 原型AST
private func parseExtern() -> PrototypeAST {
    lexer.nextToken()
    return parsePrototype()
}

最后我们还要允许用户能够输入任意表达式并求值，这个方式可以通过添加一个特殊的匿名函数实现，这个函数不需要任何参数。

/// 解析顶级表达式
///
/// - Returns: 函数AST
private func parseTopLevelExpr() -> FunctionAST? {
    if let e = parseExpression() {
        //__anon_expr为默认占位函数名
        let proto = PrototypeAST("__anon_expr", [])
        return FunctionAST(proto, e)
    }
    return nil
}

入口代码

我们还需要编写一段输入代码能够让我们愉快的解析代码。

首先我们定义一种存放Kaleidoscope语言的文件，这里就让扩展名为.k好了。这样的话我们需要先写一个读取文本内容的函数。

func readFile(_ path: String) -> String? {
    var path = path
    if path.hasSuffix("\n") {
        path.removeLast()
    }
    guard path.split(separator: ".").last! == "k" else {
        print("Expected file is *.k.")
        return nil
    }
    do {
        return try String(contentsOfFile: path, encoding: .utf8)
    } catch {
        print("Read file \(path) failure.")
        return nil
    }
}

接着我们通过输入的文件路径读这个文件的内容进行解析即可。

func main() {
    //解析器
    let parser = Parser()
    
    if let path = String(data: FileHandle.standardInput.availableData, encoding: .utf8) {
        if let str = readFile(path) {
            parser.parse(str)
        }
    }
}

main()

编译原理

swift

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

教你使用swift写编译器玩具（3）上一篇

教你使用swift写编译器玩具（1）下一篇