Jsonz bug-log

后续更新会放在 github.com/jsonz1993/blog

0%

一步步实现极简编译器 —— 了解编译器原理

Posted on Edited on In
从零开始写一个自己的编译器

welcome

今天在看 babel 的时候，无意中被引到一个外链

关于编译器的优秀/简单的教程，请查看 the-super-tiny-compiler ，同时它也从宏观角度上解释了 Babel 本身是如何工作的。

觉得挺感兴趣的，加上代码也不多，就跟着思路自己理解敲了一遍。

本文主要是帮助理解编译器的原理 不做过多的其他扩展

编译器的基本组成

一般简单的编译器可以由以下几部分组成:

  • tokenizer 词法分析器 把代码或文本按类型分开，返回: tokens
  • parser 语法剖析器 对分析后的文本按照语法分析转换成 抽象语法树 返回：ast
  • transformer 语法转换器 把语法剖析后的抽象语法树转换成我们想要的: newAst
  • codeGenerator 代码生成器 把AST 转换为 目标代码

babel 初始阶段并没有做任何事，基本上等于 const babel = code=> code;
先 tokenizer， parser 解析代码，再 transformer 的时候，完全不改动原来的 ast

接下来以最简单的编译器组成 一个环节一个环节走下去

tokenizer 词法分析器

词法分析器其实可以理解为简单的将文本切割，然后将有价值的按照相邻同等类型的 文本组合一起输出。
ps:无价值指对代码生成没有影响的部分，比如js里面非文本 一个空格和一百个空格对编译器来说是没有区别的

实现思路：

  1. 有一个值存着当前的光标 current
  2. 有一个数组用来存放按类型分出来的值 tokens
  3. 对文本进行循环， 取 current 的值做 分类型处理
  4. (
  5. )
  6. 空格
  7. 数字
  8. 字符串
  9. 方法名
  10. 将处理后的值存进数组 token 并返回
tokenizer
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
67
68
69
70
71
72
73
74
75
76
77
78
function tokenizer(input) {
  let current = 0;
  const tokens = [];
  while (current < input.length) {
    let char = input[current];

    if (char === "(" || char === ")") {
      tokens.push({
        type: 'paren',
        value: char
      });
      current++;
      continue;
    }

    const WHITESPACE = /\s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }

    const LETTERS = /[a-z]/i;
    if (LETTERS.test(char)) {
      let name = "";
      
      while (LETTERS.test(char)) {
        name += char;
        current++;
        char = input[current];
      }
      
      tokens.push({
        type: 'name',
        value: name
      });
      continue;
    }

    const NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {
      let numbers = "";

      while(NUMBERS.test(char)) {
        numbers += char;
        current++;
        char = input[current];
      }

      tokens.push({
        type: 'number',
        value: numbers
      });
      continue;
    }

    if (char === '"') {
      let string = '';
      current++;
      char = input[current];

      while(char !== '"') {
        string += char;
        current++;
        char = input[current];
      }

      tokens.push({
        type: 'string',
        value: string
      });
      current++;
      continue;
    }

    throw new TypeError('不知道你输入的是什么鬼东西 ' + char);
  }
  return tokens;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const input = '(add 2 (subtract 4 2 "djwaqp"))';
tokenizer(input);
// 输出
/*
[{ type: 'paren', value: '(' },
{ type: 'name', value: 'add' },
{ type: 'number', value: '2' },
{ type: 'paren', value: '(' },
{ type: 'name', value: 'subtract' },
{ type: 'number', value: '4' },
{ type: 'number', value: '2' },
{ type: 'string', value: 'djwaqp' },
{ type: 'paren', value: ')' },
{ type: 'paren', value: ')' }];
*/

parser

语法剖析器就是把 tokens 解析，转化为抽象语法树(AST)🌲🌲🌲，方便后续的处理。

1
[{ type: 'paren', value: '(' }, ...]   =>   { type: 'Program', body: [...] }

实现思路：

  1. 首先也要有一个 current 对 tokens 进行遍历，每一项 token 进行分析处理
  2. 有一棵树，顶级结构为 {type: 'Program' , body: [...]}
  3. 根据 token.type 进行相应的归类处理:
  4. number： 直接返回 {type: 'NumberLiteral', value, }
  5. string： 直接返回 {type: 'StringLiteral', value, }
  6. paren ( ： 对下一个进行递归，直到出现 paren )
  7. 将处理后的 ast 返回
parser
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
function parser(tokens) {
  let current = 0;
  const ast = { 
    type: 'Program', 
    body: []
  };

  function walk() {
    let token = tokens[current];

    if (token.type === 'number') {
      current ++;
      return {
        type: 'NumberLiteral',
        value: token.value
      }
    }

    if (token.type === 'string') {
      current ++;
      return {
        type: 'StringLiteral',
        value: token.value
      }
    }

    if (token.type === 'paren' && token.value === '(') {
      token = tokens[++current];
      let node = {
        type: "CallExpression",
        name: token.value,
        params: []
      }
      
      token = tokens[++current];
      while ((token.type !== 'paren') || (token.type === 'paren' && token.value !== ')')) {
        node.params.push(walk());
        token = tokens[current];
      }

      current++;
      return node;
    }
    throw new TypeError(token.type);
  }

  while(current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

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
input:
[{ type: 'paren', value: '(' },
{ type: 'name', value: 'add' },
{ type: 'number', value: '2' },
{ type: 'paren', value: '(' },
{ type: 'name', value: 'subtract' },
{ type: 'number', value: '4' },
{ type: 'number', value: '2' },
{ type: 'string', value: 'djwaqp' },
{ type: 'paren', value: ')' },
{ type: 'paren', value: ')' }]
=>
output:
{
	"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"
			}, {
				"type": "StringLiteral",
				"value": "djwaqp"
			}]
		}]
	}]
}

transformer

transformer 顾名思义，为转换部分，最复杂 也最常用。
.babelrc 添加的插件，也只是在这个环节进行操作，将原本的 ast( es6 ) 转换为目标的 newAst (es5)。

1
ast { type: 'Program', body: [...] }   =>   newAst { type: 'Program', body: [...] }

实现思路：

  1. 首先，要有一颗树，和 ast 一样。 顶级结构为 { type: 'Program', body: [...] }
  2. 在 ast 上建一个引用_context到 newAst.body;
  3. 对 ast 树进行处理, 直接处理 _context
  4. 对 ast 上 每个类型都做 enter 处理与 exit处理的钩子
  5. Number 或 String 直接处理并添加到树节点上即可
  6. CallExpression 则要创建一个数组去存参数
  7. 对类型为：Program 或 CallExpression 对子级进行 递归 4 处理
  8. 将处理后的 newAst 返回
transformer 部分
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
function traverser(node, visitor) {

  function traverseArray(nodeArr, parent) {
    nodeArr.forEach(child => traverseNode(child, parent));
  }
  
  function traverseNode(node, parent) {
    const methods = visitor[node.type];

    if (methods && methods.enter) {
      methods.enter(node, parent);
    }

    switch (node.type) {
      case 'Program':
        traverseArray(node.body, node);
        break;

      case 'CallExpression':
        traverseArray(node.params, node);
        break;

      case 'NumberLiteral':
      case 'StringLiteral':
      break;
    
      default:
        throw new TypeError(node.type);
    }

    if (methods && methods.exit) {
      methods.exit(node, parent);
    }

  }

  traverseNode(node, null);
}

function transformer(ast) {
  const newAst = {
    type: 'Program',
    body: []
  };
  ast._context = newAst.body;

  traverser(ast, {

    NumberLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'NumberLiteral',
          value: node.value
        });
      }
    },

    StringLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'StringLiteral',
          value: node.value,
        });
      }
    },

    CallExpression: {
      enter(node, parent) {

        let expression = {
          type: 'CallExpression',
          callee: {
            type: 'Identifier',
            name: node.name
          },
          arguments: []
        }

        node._context = expression.arguments;

        if (parent.type !== 'CallExpression') {
          expression = {
            type: 'ExpressionStatement',
            expression: expression
          }
        }

        parent._context.push(expression);
      }
    }

  });

  return newAst;
}
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
input:
{
	"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"
			}, {
				"type": "StringLiteral",
				"value": "djwaqp"
			}]
		}]
	}]
}
=>
output:
{
	"type": "Program",
	"body": [{
		"type": "ExpressionStatement",
		"expression": {
			"type": "CallExpression",
			"callee": {
				"type": "Identifier",
				"name": "ADD"
			},
			"arguments": [{
				"type": "NumberLiteral",
				"value": "2"
			}, {
				"type": "CallExpression",
				"callee": {
					"type": "Identifier",
					"name": "subtract"
				},
				"arguments": [{
					"type": "NumberLiteral",
					"value": "4"
				}, {
					"type": "NumberLiteral",
					"value": "2"
				}, {
					"type": "StringLiteral",
					"value": "djwaqp"
				}]
			}]
		}
	}]
}

codeGenerator

最后一步就是 codeGenerator， 用 newAst 递归调用，根据 node 与一系列规则去生成一个 string。

1
newAst { type: 'Program', body: [...] } => call(argumentsA, ...argumentsN);

实现思路：

  1. 根据 node.type 做对应逻辑：
  2. Program => 对 node.body 进行递归
  3. ExpressionStatement=> 对 node.expression 进行处理
  4. CallExpression => 对 node.callee 与 node.arguments 进行处理
  5. Identifier && NumberLiteral && StringLiteral 直接返回对应的字段
codeGenerator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function codeGenerator(node) {
  switch (node.type) {
    case 'Program':
      return node.body.map(codeGenerator).join('\n');
  
    case 'ExpressionStatement':
      return codeGenerator(node.expression) + ';';

    case 'CallExpression':
      return (codeGenerator(node.callee) +'(' + node.arguments.map(codeGenerator).join(', ') + ')');

    case 'Identifier':
      return node.name;
    
    case 'NumberLiteral':
      return node.value;

    case 'StringLiteral':
      return '"' + node.value + '"';

    default:
      throw new TypeError(node.type);
  }
}
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
input:
{
	"type": "Program",
	"body": [{
		"type": "ExpressionStatement",
		"expression": {
			"type": "CallExpression",
			"callee": {
				"type": "Identifier",
				"name": "ADD"
			},
			"arguments": [{
				"type": "NumberLiteral",
				"value": "2"
			}, {
				"type": "CallExpression",
				"callee": {
					"type": "Identifier",
					"name": "subtract"
				},
				"arguments": [{
					"type": "NumberLiteral",
					"value": "4"
				}, {
					"type": "NumberLiteral",
					"value": "2"
				}, {
					"type": "StringLiteral",
					"value": "djwaqp"
				}]
			}]
		}
	}]
}
=> 
output:
add(2, subtract(4, 2, "djwaqp"));

compiler

至此，编译器所需的几个步骤： 词法分析，解析，转换，生成都已经完成。

compiler
1
2
3
4
5
6
7
8
9
function compiler(input) {
  const tokens = tokenizer(input);
  const ast = parser(tokens);
  const newAst = transformer(ast);
  const output = codeGenerator(newAst);
  return output;
}
const input = '(add 2 (subtract 4 2 "djwaqp"))';
const output = compilter(input); // 'add(2, subtract(4, 2, "djwaqp"));'

babel

babel 的工作原理可以理解成就是一个简单的编译器：分析 => 转换 => 生成代码

bable 的篇幅太多，下面直接给出 demo源码。
具体可以看 官方插件手册 babel-handbook

我们写的babel 插件，都是在转换的部分运行

自定义插件 babel-plugin-jsonz
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const t = require('babel-types');

module.exports=  function() {
  // plugin contents
  return {
    visitor: {
      // visitor contents
      BinaryExpression(path, state) {
        // 如果操作符不是 === 则返回
        if (path.node.operator !== '===') {
          return;
        }
        // 操作符的左边替换为 sebmck, 右边替换为 dork
        path.node.left = t.identifier('"sebmck"');
        path.node.right = t.identifier('"dork"');
      }
    }
  };
};
目标代码./src/test1.js
1
2
3
function demo() {
  return 1===2;
}

安装相关依赖:npm i babel-cli babel-types --save-dev

运行脚本: babel src/ -d build/

生成后的代码 ./build/test2.js
1
2
3
function demo() {
  return "sebmck" === "dork";
}

最后再推一波关于学习中看到的好网站

源码
esprima 解析语法树🌲
AST Explorer
ast名词解释
babel-plugin-handbook