一步步实现极简编译器 —— 了解编译器原理:2018-1-14 #4

jsonz1993 · 2021-07-27T06:26:25Z

本文为博客迁移过来，原文链接: 一步步实现极简编译器 —— 了解编译器原理:2018-1-14

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里面非文本一个空格和一百个空格对编译器来说是没有区别的

实现思路：

有一个值存着当前的光标 current
有一个数组用来存放按类型分出来的值 tokens
对文本进行循环，取 current 的值做分类型处理
(
)
空格
数字
字符串
方法名
将处理后的值存进数组 token 并返回

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;
}

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)🌲🌲🌲，方便后续的处理。

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

实现思路：

首先也要有一个 current 对 tokens 进行遍历，每一项 token 进行分析处理
有一棵树，顶级结构为 {type: 'Program' , body: [...]}
根据 token.type 进行相应的归类处理:
number：直接返回 {type: 'NumberLiteral', value, }
string：直接返回 {type: 'StringLiteral', value, }
paren ( ：对下一个进行递归，直到出现 paren )
将处理后的 ast 返回

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;
}

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)。

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

实现思路：

首先，要有一颗树，和 ast 一样。顶级结构为 { type: 'Program', body: [...] }
在 ast 上建一个引用_context到 newAst.body;
对 ast 树进行处理, 直接处理 _context
对 ast 上每个类型都做 enter 处理与 exit处理的钩子
Number 或 String 直接处理并添加到树节点上即可
CallExpression 则要创建一个数组去存参数
对类型为：Program 或 CallExpression 对子级进行递归 4 处理
将处理后的 newAst 返回

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;
}

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。

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

实现思路：

根据 node.type 做对应逻辑：
Program => 对 node.body 进行递归
ExpressionStatement=> 对 node.expression 进行处理
CallExpression => 对 node.callee 与 node.arguments 进行处理
Identifier && NumberLiteral && StringLiteral 直接返回对应的字段

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);
  }
}

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

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

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 插件，都是在转换的部分运行

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"');
      }
    }
  };
};

function demo() {
  return 1===2;
}

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

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

function demo() {
  return "sebmck" === "dork";
}

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

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

The text was updated successfully, but these errors were encountered:

jsonz1993 added JavaScript migrate labels Jul 27, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

一步步实现极简编译器 —— 了解编译器原理:2018-1-14 #4

一步步实现极简编译器 —— 了解编译器原理:2018-1-14 #4

jsonz1993 commented Jul 27, 2021

一步步实现极简编译器 —— 了解编译器原理:2018-1-14 #4

一步步实现极简编译器 —— 了解编译器原理:2018-1-14 #4

Comments

jsonz1993 commented Jul 27, 2021

welcome

编译器的基本组成

tokenizer 词法分析器

parser

transformer

codeGenerator

compiler

babel