NOWHERE

2020年5月29日

coding

用 Golang 撸一个玩具编译器

codingnote

社畜以来每日搬砖，很久没有像读书时一样学习一些东西沉淀下了。最近在 GitHub 上看到 the-super-tiny-compiler 这个项目，很喜欢它极简的设计和实现，也给了对编译原理一知半解的我一个从头再来的机会。个人感觉原项目用 JavaScript 抹去了一些实现细节的同时也模糊了具体的理解，故此用 Golang 学习与实现。

概述

这里我们实现的玩具编译器是将 lisp 风格的代码转化为 C 语法，例如 (add 2 (subtract 4 2)) 会被转化成 add(2, subtract(4, 2));。大部分现代编译器工作主要有三个过程：

  • Parsing：将源代码解析为抽象表达（如抽象语法树 Abstract syntax tree）
  • Transformation：操作 AST 并做一些编译器需要的工作
  • Code Generation：将变形后的代码生成新的代码

按照我 iOS 的经验，这大概对应的是：

  • Clang 对 C/C++/Objective-C/Swift 代码进行词法分析、静态分析等，生成 AST clang -Xclang -ast-dump
  • Clang 将 AST 生成 LLVM 中间代码并进行编译优化，例如全局变量、循环、尾递归等情况 clang -emit-llvm
  • Clang 将优化后的 LLVM 代码生成汇编代码 clang -S -o，assembler 将汇编代码生成机器码，linker 将机器码和静态库链接生成 Mach-O 可执行文件

Parsing

解析主要是词法分析（lexical analysis）和句法分析（syntactic analysis）。

Lexical Analysis

词法分析中 tokenizer 将原始代码拆分成 token（或 lexer）。比如 (add 2 4) 会被解析为

[
    {
        type: 'paren', value: '(',
    }, {
        type: 'name', value: 'add',
    }, {
        type: 'number', value: '2',
    }, {
        type: 'number', value: '4',
    }, {
        type: 'paren', value: ')',
    }
]

这里我们定义 token 包括两个属性：type 和 value。首先声明我们需要的 token type 和结构体：

type TokenType string

const (
    TokenTypeParen  TokenType = "paren"
    TokenTypeName   TokenType = "name"
    TokenTypeNumber TokenType = "number"
    TokenTypeString TokenType = "string"
)

type Token struct {
    tokenType TokenType
    value     string
}

Tokenizer 函数接受 input 字符串，遍历并根据当前字符生成 token，最后返回 token 数组。这里我们利用了 Golang 的 unicode 包实现快速的判断。

func Tokenizer(input string) []Token {
    // counter
    current := 0
    // token array to be returned
    tokens := make([]Token, 0)
    // iterate
    for current < len(input) {
        char := input[current]
        charStr := string(char)
        if charStr == "(" || charStr == ")" {
            tokens = append(tokens, Token{TokenTypeParen, charStr})
            current++
            continue
        }

        charRune := rune(char)
        if unicode.IsSpace(charRune) {
            current++
            continue
        }

        if unicode.IsDigit(charRune) {
            value := ""
            for unicode.IsDigit(rune(char)) {
                value = value + string(char)
                current++
                char = input[current]
            }
            tokens = append(tokens, Token{TokenTypeNumber, value})
            continue
        }

        if charStr == "\"" {
            value := ""
            // skip opening parenthesis
            current++
            char = input[current]

            // for characters that are not "\"", append to value of current token
            for string(char) != "\"" {
                value = value + string(char)
                current++
                char = input[current]
            }

            // skip closing parenthesis
            current++
            char = input[current]

            tokens = append(tokens, Token{TokenTypeString, value})
            continue
        }

        if unicode.IsLetter(charRune) {
            value := ""
            for unicode.IsLetter(rune(char)) {
                value = value + string(char)
                current++
                char = input[current]
            }
            tokens = append(tokens, Token{TokenTypeName, value})
            continue
        }
    }
    return tokens
}

Syntactic Analysis

句法分析将 token 数组解析为抽象语法树。顾名思义，AST 是树状结构，例如上文的 (add 2 4) 解析而来的 token 数组会被进一步解析为 AST 如下：

{
    type: 'Program',
    params: [{
        type: 'CallExpression',
        value: 'add',
        params: [{
            type: 'NumberLiteral',
            value: '2',
        }, {
            type: 'NumberLiteral',
            value: '4',
        }],
    }],
}

AST 的每个节点可定义如下，注意 params 我们定义为一个指针数组，数组中每个元素都是指向 ASTNode 的指针。

type ASTNodeType string

const (
    ASTNodeTypeProgram             ASTNodeType = "Program"
    ASTNodeTypeNumberLiteral       ASTNodeType = "NumberLiteral"
    ASTNodeTypeStringLiteral       ASTNodeType = "StringLiteral"
    ASTNodeTypeCallExpression      ASTNodeType = "CallExpression"
    ASTNodeTypeExpressionStatement ASTNodeType = "ExpressionStatement"
)

type ASTNode struct {
    nodeType   ASTNodeType
    value      string
    params     []*ASTNode
}

Parser 函数接受 token 数组并返回 AST 根结点。

func Parser(tokens []Token) ASTNode {
    current := 0

    // recursively walk through nodes
    var walk func() ASTNode
    // ...

    // create root node
    ast := ASTNode{
        nodeType: ASTNodeTypeProgram,
    }
    // push nodes to ast.params
    for current < len(tokens) {
        tmp := walk()
        ast.params = append(ast.params, &tmp)
    }
    return ast
}

中间我们使用一个闭包 walk() 来根据 current 把 Token 解析为 ASTNode。预先声明闭包的原因是 Golang 不允许通过海象运算符（:=）声明的闭包调用自己。walk 闭包实现如下：

walk = func() ASTNode {
    token := tokens[current]

    if token.tokenType == TokenTypeNumber {
        current++
        return ASTNode{
            nodeType: ASTNodeTypeNumberLiteral,
            value:    token.value,
        }
    }

    if token.tokenType == TokenTypeString {
        current++
        return ASTNode{
            nodeType: ASTNodeTypeStringLiteral,
            value:    token.value,
        }
    }

    if token.tokenType == TokenTypeParen && token.value == "(" {
        // skip opening parenthesis
        current++
        token = tokens[current]

        node := ASTNode{
            nodeType: ASTNodeTypeCallExpression,
            value:    token.value,
            params:   []*ASTNode{},
        }
        // skip name token
        current++
        token = tokens[current]

        for token.tokenType != TokenTypeParen || (token.tokenType == TokenTypeParen && token.value != ")") {
            tmp := walk()
            node.params = append(node.params, &tmp)
            token = tokens[current]
        }

        // skip closing parenthesis
        current++
        return node
    }

    // Should not get here
    return ASTNode{}
}

Transformation

真实的编译器可能会进行很多优化并生成中间代码，但在玩具编译器里我们只是操作 AST，进行一些改动并生成新的 AST。一般来说也可以直接更改原始 AST，但鉴于我们是 target 另一种语言（lisp -> C）我们还是创建一棵新的 AST。

Traverser

为了操作 AST，我们需要 traverser 去深度优先遍历 AST，并对每个类型的节点执行不同的操作。这里我们使用一个 map，key 是节点的类型，value 是我们需要执行的操作。对于每个节点，我们需要在开始遍历节点时（enter）以及结束遍历其子树时（exit）执行，因此我们声明一个 Methods 结构体，具有 enter 和 exit 两个闭包属性，每个闭包接受 node 和 parent 两个参数表示当前节点和父节点。由于闭包需要对节点进行改动，类型为指向节点的指针。

type Methods struct {
    enter func(*ASTNode, *ASTNode)
    exit  func(*ASTNode, *ASTNode)
}

由此我们的 map 类型为 map[ASTNodeType]Methods，可以实现 traverser 如下：

func Traverser(ast *ASTNode, visitor map[ASTNodeType]Methods) {
    var traverseNode func(*ASTNode, *ASTNode)
    var traverseArray func([]*ASTNode, *ASTNode)

    // helper that iterate over an array
    traverseArray = func(array []*ASTNode, parent *ASTNode) {
        for i := 0; i < len(array); i++ {
            traverseNode(array[i], parent)
        }
    }

    traverseNode = func(node *ASTNode, parent *ASTNode) {
        methods := visitor[node.nodeType]
        // call enter
        if methods.enter != nil {
            methods.enter(node, parent)
        }

        // traverse by current node type
        switch node.nodeType {
        case ASTNodeTypeProgram, ASTNodeTypeCallExpression:
            traverseArray(node.params, node)
        case ASTNodeTypeNumberLiteral, ASTNodeTypeStringLiteral, ASTNodeTypeExpressionStatement:
            break
        }
        
        // call exit
        if methods.exit != nil {
            methods.exit(node, parent)
        }
    }

    traverseNode(ast, nil)
}

Transformer

Transformer 需要调用 Traverser() 函数将 AST 生成新的 AST，转化的例子在 这里 可以看到。对于新的 AST，我们需要添加一些属性来扩充 ASTNode 的定义。比较重要的是 context *[]*ASTNode，我们用它来表示一个从旧 AST 到新 AST params 的引用，因此它的类型需要为指针数组的指针，这样当我们修改旧 AST 节点的 context 时，对应的变更也会反映在新 AST 的 params 上。

type Callee struct {
    calleeType string
    name       string
}

type ASTNode struct {
    nodeType   ASTNodeType
    value      string
    callee     Callee
    expression *ASTNode
    params     []*ASTNode

    // reference from old ast to new ast
    context    *[]*ASTNode
}

Transformer 函数如下：

func Transformer(ast *ASTNode) ASTNode {
    newAst := ASTNode{
        nodeType: ASTNodeTypeProgram,
        params:   []*ASTNode{},
    }

    // so we can push nodes to parent's context
    ast.context = &newAst.params

    Traverser(ast, map[ASTNodeType]Methods{
        // ...
    })

    return newAst
}

接下来我们来针对不同类型添加 enter 方法。对于 literal 节点，我们简单地创建新 ASTNode 并添加到父节点的 context 即可。由于 context 是指向新 AST params 的引用，新 ASTNode 也会被添加到新 AST 对应的 params 中。

map[ASTNodeType]Methods{
    ASTNodeTypeNumberLiteral: Methods{
        enter: func(node *ASTNode, parent *ASTNode) {
            tmp := ASTNode{
                nodeType: ASTNodeTypeNumberLiteral,
                value:    node.value,
            }
            *parent.context = append(*parent.context, &tmp)
        },
    },
    ASTNodeTypeStringLiteral: Methods{
        enter: func(node *ASTNode, parent *ASTNode) {
            tmp := ASTNode{
                nodeType: ASTNodeTypeStringLiteral,
                value:    node.value,
            }
            *parent.context = append(*parent.context, &tmp)
        },
    },
    // ...
}

注意这里将节点添加到 context 的操作，由于 context 是数组指针，我们需要对它指向的内容进行操作，因此有额外的取值符。而数组元素是指向节点的指针，因此需要对生成的节点取地址。许久以来 Swift 写得一把梭已经差不多忘记这个级别的操作了。

最后对 CallExpression 类型，由于表达式具有参数，我们需要把旧节点的 context 指向新节点的 params，就如同我们对根结点做的一样。另外在这个玩具解释器中，如果父节点不是 CallExpression 类型，我们需要创建一个 ExpressionStatement 去嵌套一下。

ASTNodeTypeCallExpression: Methods{
    enter: func(node *ASTNode, parent *ASTNode) {
        expression := ASTNode{
            nodeType: ASTNodeTypeCallExpression,
            callee:   Callee{"Identifier", node.value},
            params:   []*ASTNode{},
        }

        // context of CallExpression refer to express's params so
        // that we can push parameters
        node.context = &expression.params

        if parent.nodeType != ASTNodeTypeCallExpression {
            // if not CallExpression, we need to wrap
            newExpression := ASTNode{
                nodeType:   ASTNodeTypeExpressionStatement,
                expression: &expression,
            }
            *parent.context = append(*parent.context, &newExpression)
            return
        }

        *parent.context = append(*parent.context, &expression)
    },
},

Code Generation

最后就是将新 AST 解析成 C 风格代码了。Code generator 的实现非常直接，针对不同节点类型生成不同代码，并对子节点递归调用自身就可以了。

func CodeGenerator(node ASTNode) string {
    switch node.nodeType {
    case ASTNodeTypeProgram:
        res := []string{}
        for _, param := range node.params {
            res = append(res, CodeGenerator(*param))
        }
        return strings.Join(res, "\n")

    case ASTNodeTypeExpressionStatement:
        return CodeGenerator(*node.expression) + ";"

    case ASTNodeTypeCallExpression:
        params := []string{}
        for _, param := range node.params {
            params = append(params, CodeGenerator(*param))
        }
        return node.callee.name + "(" + strings.Join(params, ", ") + ")"

    case ASTNodeTypeNumberLiteral:
        return node.value

    case ASTNodeTypeStringLiteral:
        return "\"" + node.value + "\""

    default:
        return ""
    }
}

Compiler

最后把所有过程连起来：

func Compiler(input string) string {
    tokens := Tokenizer(input)
    ast := Parser(tokens)
    newAst := Transformer(&ast)
    output := CodeGenerator(newAst)
    return output
}

写一小段测试代码，输入为 (add 2 (subtract (add 3 5) 1))\n(print \"hello world\")，编译运行一下得到：

add(2, subtract(add(3, 5), 1));
print("hello world");

完整代码在这里。

总结

虽然是个没有卵用的东西，不过从头撸的过程也能学习到现代编译器大致的工作原理。原项目 the-super-tiny-compiler 利用代码步步解释的形式也是让人耳目一新。另外 Golang 确实兼具 Python 易学的语法、强大的标准库和 C 的底层操作能力，比我想象的要香，看来可以当 gopher 了。