NOWHERE

一些碎碎念

用 Golang 撸一个玩具编译器

社畜以来每日搬砖,很久没有像读书时一样学习一些东西沉淀下了。最近在 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) 会被解析为

1
2
3
4
5
6
7
8
9
10
11
12
13
[
{
type: 'paren', value: '(',
}, {
type: 'name', value: 'add',
}, {
type: 'number', value: '2',
}, {
type: 'number', value: '4',
}, {
type: 'paren', value: ')',
}
]

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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 包实现快速的判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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 如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{
type: 'Program',
params: [{
type: 'CallExpression',
value: 'add',
params: [{
type: 'NumberLiteral',
value: '2',
}, {
type: 'NumberLiteral',
value: '4',
}],
}],
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 根结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 闭包实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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 结构体,具有 enterexit 两个闭包属性,每个闭包接受 nodeparent 两个参数表示当前节点和父节点。由于闭包需要对节点进行改动,类型为指向节点的指针。

1
2
3
4
type Methods struct {
enter func(*ASTNode, *ASTNode)
exit func(*ASTNode, *ASTNode)
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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 上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 去嵌套一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 的实现非常直接,针对不同节点类型生成不同代码,并对子节点递归调用自身就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

最后把所有过程连起来:

1
2
3
4
5
6
7
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\"),编译运行一下得到:

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

完整代码在 这里

总结

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