Golang Compiler 实现学习 #59
Description
之前写过关于怎么构造一个属于自己的 DSL 的博客--如何构造属于自己的 DSL —— PEG.js 使用指南，借助了 pegjs 这样的工具来完成，但是如果自行实现一个对于某些语法 ast 解析过程，将会更好理解 pegjs 这种工具的原理甚至能从中获取到灵感从而运用到项目中的效率工程中。
这里借助实现一个将 lisp-like 语法转换到 c-like 语法的编译器来说明编译器的大概原理与编译过程。
首先先明确两个语言的语法是怎么样的：
LISP C
2 + 2 (add 2 2) add(2, 2)
4 - 2 (subtract 4 2) subtract(4, 2)
2 + (4 - 2) (add 2 (subtract 4 2)) add(2, subtract(4, 2))我们在编译器程序中拿到的数据，往往是字符串数据，我们没有办法对字符串这么单一的数据做太多的变化，所以一般需要将字符串进行解析和数据结构的转换。
一般来说这个过程是分为三个步骤(模块)：
- 解析：将得到的二进制数据或者字符串数据转化为一个对于 DSL 的抽象描述
- 转化：将解析得到的抽象数据表示转化为此编译器希望得到的另一种形式的抽象 ast 数据表示
- 代码生成：得到转化后的抽象数据之后根据这份数据来生成自己想要的 DSL 代码。
类似上面的过程，入口代码可以类似下面这样：
// 这里基本就是对应上面所说的三个步骤
func compiler(input string) string {
tokens := tokenizer(input) // 解析
ast := parser(tokens) // 解析
newAst := transformer(ast) // 转化
out := codeGenerator(node(newAst)) // 代码生成
return out
}
// 输入字符串调用函数
func main() {
program := "(add 10 (subtract 10 6))"
out := compiler(program)
fmt.Println(out)
}解析
解析一般分为 词法分析与语法分析。
词法分析，它读取我们输入的字符数据(字符串形式的代码)，将字符串进行分割，根据类型来区分，比如数字，标识符，运算符等等。得到的结果一般是一维数组。即函数实现里面的 tokenizer:
type token struct {
Kind tokenType
Value string
}
func tokenizer(input string) []token {
input += "\n"
current := 0
tokens := []token{}
// 遍历每个字符
for current < len([]rune(input)) {
char := string([]rune(input)[current])
if char == "(" {
tokens = append(tokens, token{
Kind: Parenthesis,
Value: "(",
})
current++
continue
}
if char == ")" {
tokens = append(tokens, token{
Kind: Parenthesis,
Value: ")",
})
current++
continue
}
if char == " " {
current++
continue
}
if isNumber(char) {
value := ""
// 如果是数字类型，需要将后面的同数字类型的字符联合起来变成数字串
// 直到后面不再是数字类型
for isNumber(char) {
value += char
current++
char = string([]rune(input)[current])
}
tokens = append(tokens, token{
Kind: Numeric,
Value: value,
})
continue
}
if isLetter(char) {
value := ""
// 这里和数字类型一个道理，需要将同字符类型的串起来
for isLetter(char) {
value += char
current++
char = string([]rune(input)[current])
}
tokens = append(tokens, token{
Kind: Name,
Value: value,
})
continue
}
break
}
return tokens
}上面的程序得到的结果类似下面这样：
[
{ type: 'Parenthesis', value: '(' },
{ type: 'Name', value: 'add' },
{ type: 'Numeric', value: '2' },
{ type: 'Parenthesis', value: '(' },
{ type: 'Name': value: 'subtract' },
...
]语法分析，将词法分析得到的结果，按照各个字符之间的逻辑关系，将他们转化成另一种数据结构，比如抽象语法树。抽象语法树一般是一个深度嵌套的对象，其实上面词法分析的结果就是一个一维数组，每个元素说明这个字符的类型与它的值，去掉了无谓的空格。而语法分析的目的在于将这个一维数据，按照一定规则使其带有语法结构信息。
举个例子，在本文中的 lisp 语法中，括号遇上 add 代表执行 add 这个函数，那么我们在语法分析的结果，就要带上这个信息：
// NodeType node 类型
type NodeType string
type node struct {
Kind NodeType
Value string
Name string
Callee *node
Expression *node
Body []node
Params []node
Arguments *[]node
Context *[]node
}
type ast node
// 这里设定了一个全局变量，只是为了方便取值
var pc int
var pt []token
func walk() node {
token := pt[pc]
// 如果是数字类型直接返回
if token.Kind == Numeric {
pc++
return node{
Kind: NumberLiteral,
Value: token.Value,
}
}
// 如果是括号类型并且是左括号，按照语法来讲，属于函数调用的开始标志
if token.Kind == Parenthesis && token.Value == "(" {
// 直接拿下一个 token，作为函数调用的入口标识(调用哪个函数)
pc++
token = pt[pc]
// 可以看到 token 在转化 ast 的时候，括号直接完成了它的使命，被舍弃掉并转化为含有语义
// 语法的 CallExpression 类型(函数调用类型)
n := node{
Kind: CallExpression,
Value: token.Value,
Params: []node{},
}
pc++
token = pt[pc]
// 取这个函数的参数，直接遇到匹配上面这个括号的右括号为止
for token.Kind != Parenthesis || (token.Kind == Parenthesis && token.Value != ")") {
n.Params = append(n.Params, walk())
token = pt[pc]
}
pc++
return n
}
log.Fatal(token.Kind)
return node{}
}
func parser(tokens []token) ast {
pc = 0
pt = tokens
// 入口一定是以 Program 类型
ast := ast{
Kind: Program,
Body: []node{},
}
// pc 作为一个指针，直到指向 token 的最后一位
for pc < len(pt) {
ast.Body = append(ast.Body, walk())
}
return ast
}这一步得到的结构，会少了一些 token，token 已经转化为有实际意义的语法信息了：
{
type: 'Program',
body: [{
type: 'CallExpression',
name: 'add',
params: [{
type: 'NumberLiteral',
value: '2',
}, {
type: 'CallExpression',
name: 'subtract',
params: [{
type: 'NumberLiteral',
value: '4'
}, {
type: 'NumberLiteral',
value: '2'
}]
}]
}]
}转化
得到 ast 的下一步就是转化。这里的转化需要先明确你最后需要得到一个什么样的结果，如果你是需要对原来的语言(DSL)进行一些修改，那么转化就是对原来的 ast 进行一个增删查改，如果你是需要转化为另一个 DSL，那么就需要对原来的 ast 转化为一个新的 ast。
根据之前说的，ast 是一个深度嵌套的对象，所以我们需要对 ast 进行深度遍历。
// 定义 visitor 模式, 深度遍历模式下 enter 代表进入处理这个节点，leave 代表处理完毕此节点
type visitor map[string]struct {
Enter func(n *node, parent node) int
Leave func(n *node, parent node, idx int)
}
// 每个节点的处理
func traverseNode(n, p node, v visitor) {
nodeVisitor, exist := v[string(n.Kind)]
idx = -1 // idx 用来记录进入此节点的时候，遍历堆栈的下标
if exist {
idx = nodeVisitor.Enter(&n, p)
}
switch n.Kind {
case Program:
traverseArray(n.Body, n, v)
case CallExpression:
traverseArray(n.Params, n, v)
case NumberLiteral:
break
default:
log.Fatal(n.Kind)
}
if nodeVisitor.Leave != nil && idx != -1 {
nodeVisitor.Leave(&n, p, idx)
}
}
// 处理此节点下的子节点
func traverseArray(a []node, p node, v visitor) {
for _, child := range a {
traverseNode(child, p, v)
}
}
// 遍历入口函数
func traverser(a ast, v visitor) {
traverseNode(node(a), node{}, v)
}
var idx int
func transformer(a ast) ast {
newAst := ast{
Kind: Program,
Body: []node{},
}
traverseStack := make([]*[]node, 0)
// 记录遍历节点
traverseStack = append(traverseStack, &newAst.Body)
traverser(a, map[string]struct {
Enter func(n *node, parent node) int
Leave func(n *node, parent node, idx int)
}{
string(NumberLiteral): struct {
Enter func(n *node, parent node) int
Leave func(n *node, parent node, idx int)
}{
Enter: func(n *node, parent node) int {
currentStack := traverseStack[len(traverseStack)-1]
*currentStack = append(*currentStack, node{
Kind: NumberLiteral,
Value: n.Value,
})
return -1
},
Leave: nil,
},
string(CallExpression): struct {
Enter func(n *node, parent node) int
Leave func(n *node, parent node, idx int)
}{
Enter: func(n *node, parent node) int {
arguments := make([]node, 0)
e := node{
Kind: CallExpression,
Callee: &node{
Kind: Identifier,
Name: n.Value,
},
Arguments: &arguments,
}
if parent.Kind != CallExpression {
es := node{
Kind: ExpressionStatement,
Expression: &e,
}
currentStack := traverseStack[len(traverseStack)-1]
*currentStack = append(*currentStack, es)
} else {
currentStack := traverseStack[len(traverseStack)-1]
*currentStack = append(*currentStack, e)
}
traverseStack = append(traverseStack, e.Arguments)
// 返回插入的节点下标
return len(traverseStack) - 1
},
Leave: func(n *node, parent node, idx int) {
// 处理完之后删除当前遍历的节点
traverseStack = append(traverseStack[:idx], traverseStack[idx+1:]...)
},
},
})
return newAst
}这里抽象出一个 Visitor 模式，visitor 模式接收不同的类型，匹配到相同类型的节点的时候，调用对应的方法。这里的代码我重新重写过，原来仓库的代码对 ast 对象数据结构有侵入性，污染了原来的数据，重写的代码使用另一个堆栈记录维持节点关系，并创建一个新的 ast 结构。
代码生成
这个阶段是根据新的 ast 来进行操作，当然如果你是在原来的 ast 上面进行操作而不是新建一个 ast 对象，代码生成阶段的工作很可能是和转化阶段的工作重叠的。
func codeGenerator(n node) string {
switch n.Kind {
case Program:
var r []string
for _, no := range n.Body {
r = append(r, codeGenerator(no))
}
return strings.Join(r, "\n")
case ExpressionStatement:
return codeGenerator(*n.Expression) + ";"
case CallExpression:
var ra []string
c := codeGenerator(*n.Callee)
for _, no := range *n.Arguments {
ra = append(ra, codeGenerator(no))
}
r := strings.Join(ra, ", ")
return c + "(" + r + ")"
case Identifier:
return n.Name
case NumberLiteral:
return n.Value
default:
log.Fatal("err")
return ""
}
}一点感想
当你掌握上面的编译器大概原理，回看开源的解析器比如 graphql 的解析器，一看就知道大概模块的功能了，甚至后面想要对 Graphql Schema 做一些自定义的逻辑拓展，相信是比较容易的。
展望展望展望
当我们拿到一些强类型文件的 ast 信息，比如 proto 文件，graphql schema 信息，类型之间是可以互转的，回看我们平时开发中的接口层，有时候我们只是在 proxy 接口做一层聚合而已，而这种聚合代码在面对模板代码加上 ast 语法信息，是不是就能自动生成了呢？其实这也就是我们正在孵化的一个项目的技术方案的一个灵感所在。所以掌握编译器的一些知识，其实是可以运用到我们日常开发的效率工程中的。
注：以上学习代码改造自 the super tiny compiler。