前言

本篇内容主要由 [https://github.com/jamiebuilds/the-super-tiny-compiler]中的注释翻译而来，该项目实现了一款包含编译器核心组成的极简的编译器。希望能够给想要初步了解编译过程的同学提供到一些帮助。

概要

1. 本篇和大家一起学习写一款超级简单轻量,去掉注释只有不到200行代码的编译器。
2. 该编译器将类 lisp 语法函数调用 编译为 类C语言函数调用
3. 如果不熟悉上述的两种语法的其中任意一种，下面给出了简单的介绍
4. 例如有两个函数 add 和 subtract 他们用对应的语言分别实如余下:
   

5. 本篇要实现编译的全部语法如上所示。虽然既不涵盖完整的lisp语法和c语法，但是足够展示一个现代编译器需要的主要组成部分

编译器组成

大部分的编译器可以粗略的划分为3个阶段: 解析 Parsing，翻译 Transformation，代码生成Code Generation

1. 解析 获取原始代码并将其转化为一个更抽象的代码表示
2. 翻译 用抽象的代码表示为编译器想要完成的操作做准备
3. 代码生成 将翻译过的抽象表示转化为新的要编译的代码

解析 Parsing

解析过程通常被分为两个部分: 词法分析，语法分析

1. 词法分析 获取原始代码 ，且将代码分割为一个一个词[token]
   由这些词构成的词组用来描述语法，他们可以是数字，文本，标点符号，运算符等等
2. 语法分析 获取词组[tokens]且将他们重新格式化为一个表示形式，该表示形式描述语法的每个部分及其相互之间的关系。这称为中间表示或抽象语法树。
   抽象语法树（简称AST）是一个嵌套很深的对象，它以一种既容易使用又能告诉我们很多信息的方式表示代码。

示例语法

(add 2 (subtract 4 2))

tokens表示如下

[
 { 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: 'paren', value: ')' },
 { type: 'paren', value: ')' },
 ]

抽象语法树如下

 {
 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并对其进行更改。它可以用同一种语言操纵AST，也可以将AST翻译成一种全新的语言。

让我们看看如何转换AST。

你可能会注意到我们的AST中有看起来非常相似的元素。这些对象具有类型属性。每个节点都称为AST节点。这些节点定义了描述树的一个独立部分的属性。

我们有一个数字节点 "NumberLiteral"

{
 type: 'NumberLiteral',
 value: '2',
}

或者一个调用表达式节

 {
 type: 'CallExpression',
 name: 'subtract',
 params: [...nested nodes here...],
 }

点转换AST时，我们可以通过添加/删除/替换属性来操纵节点，可以添加新节点，删除节点，也可以不使用现有的AST直接基于它创建一个全新的AST。

由于我们定位的是新语言，因此我们将专注于创建特定于目标语言的全新AST。

遍历

为了浏览所有这些节点，我们需要能够遍历它们。 如下将通过深度优先方式的遍历AST的每个节点。

{
 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，我们将：

1. Program - 从AST的顶层开始
2. CallExpression (add) - 转到程序的第一个元素
3. NumberLiteral (2) - 移至CallExpression参数的第一个元素
4. CallExpression (subtract) - 移至CallExpression参数的第二个元素
5. NumberLiteral (4) - 移至CallExpression参数的第一个元素
6. NumberLiteral (2) - 移至CallExpression参数的第二个元素

如果我们直接操作此AST，而不是创建单独的AST，则可能会在这里引入各种抽象。 但是仅访问树中的每个节点就足以完成我们要尝试的操作。

我之所以使用“访问”一词，是因为存在这种模式来表示对象结构元素上的操作。

Visitors

这里的基本思想是，我们将创建一个“访客”对象，该对象的方法将接受不同的节点类型。

var visitor = {
 NumberLiteral() {},
 CallExpression() {},
};

但是，也有可能在“退出”时调用相应的操作。 想象一下之前列表形式的树结构

当我们往下遍历时，我们遍历尽所有分支时。我们“退出”它。 因此，沿着树下来，我们“进入[enter]”每个节点，然后“退出[exit]”。

 -> Program (enter)
 -> CallExpression (enter)
 -> Number Literal (enter)
 <- Number Literal (exit)
 -> Call Expression (enter)
 -> Number Literal (enter)
 <- Number Literal (exit)
 -> Number Literal (enter)
 <- Number Literal (exit)
 <- CallExpression (exit)
 <- CallExpression (exit)
 <- Program (exit) 

为了支持进入和退出操作，我们将vistitor定义调整如下

 var visitor = {
 NumberLiteral: {
 enter(node, parent) {},
 exit(node, parent) {},
 }
 };

代码生成

• 编译器的最后一步就是代码生成.有时，编译器会执行与转换重叠的操作，但是在大多数情况下，代码生成只是意味着将AST抽象语法树字符串化代码化。
• 代码生成器以几种不同的方式工作，一些编译器将复用前面获取的tokens，另一些创建单独表示，以便它们可以线性打印节点，但是据我所知，大多数将使用我们刚创建的AST， 这也是我们后续主要关注的方式，
• 综上就是一个编译器应该具备的核心部分.
  请注意，并不是说每个编译器看起来都和这里描述的完全一样。编译器根据目的不同有很多种，可能需要比如下详细介绍的步骤更多的步骤。

代码

现在您应该对编译器的主要外观有一个大致的总体了解。

经过上面的解释和介绍，现在可以开始编写自己的编译器了，那么开始代码走起。

第一步获取token

我们将获取我们的代码串将其解析成token数组

(add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]

function tokenizer(input) {
 // current变量，用来标记当前读入代码的字符位置的游标
 let current = 0;
 // tokens数组变量，用来存入解析的token词组
 let tokens = [];

 // 开启一个while循环，将current设置为循环内部的增量
 while(current < input.length){
 // 获取当前游标对应的字符
 let char = input[current];
 // 检查当前字符是否是一个括号
 if(char=== "("){
 // 如果是括号，则新增一个`paren`括号类型的,值为做括号的词到tokens词组 
 tokens.push({
 type: 'paren',
 value: '(',
 }); 
 //然后游标向后前进一位
 current ++;
 // 进入下一循环
 continue;
 }
 // 检查是否右括号，如是则新增一个右括号词组，增加游标，继续下一次循环
 if (char === ')') {
 tokens.push({
 type: 'paren',
 value:')'
 })
 current++;
 continue;
 }
 // 检查当前字符是否空格，如果是空格则直接跳过，游标后移
 // (add 123 456)
 // ^^^ ^^^ number
 let WHITESPACE = /\s/;
 if (WHITESPACE.test(char)) {
 current++;
 continue;
 }
 
 //下一个将检测的类型是number数字.和之前不同的是number类型可能由多个数字字符组成，我们需要
 // 获取整个连续的数字串作为一个number类型的词token

 let NUMBERS = /[0-9]/;
 if(NUMBERS.test(char)){
 //新建一个value串用来设置数字字符串
 let value='';
 while(NUMBERS.test(char)){
 value += char;
 char = input[++current];
 }
 tokens.push({type:'number',value});
 continue;
 }

 // 在将要实现的编译器中也支持被双引号括起来的字符串
 // (concat "foo" "bar")
 // ^^^^ ^^^^ 支付串

 if (char === '"') {
 let value = '';
 char = input[++current];
 while (char != '"') {
 value += char;
 char = input[++current]
 }
 // 游标跳过终结的引号
 char = input[++current];
 tokens.push({
 type:'string',
 value
 })
 continue;
 }
 // 最后一个类型的token是`name`类型.由一串字母构成。该类型用作本编译器
 // 的lisp语法风格的函数名
 let LETTERS = /[a-z]/i;
 if(LETTERS.test(char)) {
 let value = '';
 while (LETTERS.test(char)){
 value += char;
 char = input[++current];
 }
 tokens.push({type: 'name', value});

 continue;

 }

 // 如果不匹配上述任意类型抛出类型异常，介绍循环
 throw new TypeError('I dont know what this character is: ' + char);
 }

 return tokens;
}

第二步 parse 抽象语法树

function parser(tokens) {
 // 新建current变量作为游标
 let current = 0;
 // 该方法中将用递归代替while循环，先定义一个walk方法
 function walk() {
 //获取当前token
 let token = tokens[current];
 // 从number类型的token开始，将不同类型的token置入代码的不同位置
 if (token.type === 'number') {
 // 如果当前是number类型，游标向前
 current++;
 // 返回一个number类型的AST 节点
 return {
 type: 'NumberLiteral',
 value: token.value
 }
 }
 // 字符token返回一个字符类型的AST节点
 if (token.type === 'string') {
 current++;

 return {
 type: 'StringLiteral',
 value: token.value
 }
 }
 // 下面检查是否调用表达式.先判断是否是一个括号类型，且是左括号token
 if (
 token.type === 'paren' && 
 token.value === '('
 ) {
 // 跳过当前左括号游标，获取下一个token
 token = tokens[++current];
 let node = {
 type:'CallExpression',
 name: token.value,
 params: []
 }
 // 游标向前移一位跳过 name类型的token
 token = tokens[++current];
 // 现在开始遍历 CallExpression的参数，直到遇到右括号
 // 这里开始会存在递归，我们通过递归解决嵌套节点问题。

 // 为了解释这一点，让我们采用我们的Lisp代码。 您可以看到
 // add的参数是一个数字和一个包含自己的参数的嵌套的CallExpression。
 // [
 // { 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: 'paren', value: ')' }, <<< Closing parenthesis
 // { type: 'paren', value: ')' }, <<< Closing parenthesis
 // ]

 // 我们通过递归调用walk方式，去向前遍历内嵌的`CallExpression`.
 // 这里我们创建一个While循环遍历直到遇到左括号
 while(
 (token.type !== 'paren')||
 (token.type === 'paren' && token.value !==')')){ 
 node.params.push(walk());
 token = tokens[current];
 }
 current++;
 return node;
 }
 // 如果不是以上检测的类型则抛出异常
 throw new TypeError(token.type);
 }
 let ast = {
 type:'Program',
 body:[]
 }
 while(current < tokens.length){
 ast.body.push(walk());
 }
 return ast;
}

第三步转换抽象语法树

/***
 * ===================================
 * ⌒(?>???<?)⌒
 * THE TRAVERSER!!!
 * ===================================
 * 现在通过parser有了一颗AST抽象语法树,现在通过vistor访问
 * 每一个节点
 * traverse(ast, {
 * Program: {
 * enter(node, parent) {
 * // ...
 * },
 * exit(node, parent) {
 * // ...
 * },
 * },
 *
 * CallExpression: {
 * enter(node, parent) {
 * // ...
 * },
 * exit(node, parent) {
 * // ...
 * },
 * },
 *
 * NumberLiteral: {
 * enter(node, parent) {
 * // ...
 * },
 * exit(node, parent) {
 * // ...
 * },
 * },
 * });
 */

function traverser(ast, visitor) {
 function traverseArray(array, parent) {
 array.forEach(child => {
 traverseNode(child, parent);
 });
 }
 function traverseNode(node, parent) {
 let 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(ast, null);
}

/**
 * ============================================================================
 * ?(??????????)?
 * THE TRANSFORMER!!!
 * ============================================================================
 */

/**
 * 下一步Ast转化. 将已经构建好的Ast树通过visitor转化成一颗新的Ast抽象语法树
 *
 * ----------------------------------------------------------------------------
 * Original AST | Transformed AST
 * ----------------------------------------------------------------------------
 * { | {
 * type: 'Program', | type: 'Program',
 * body: [{ | body: [{
 * type: 'CallExpression', | type: 'ExpressionStatement',
 * name: 'add', | expression: {
 * params: [{ | type: 'CallExpression',
 * type: 'NumberLiteral', | callee: {
 * value: '2' | type: 'Identifier',
 * }, { | name: 'add'
 * type: 'CallExpression', | },
 * name: 'subtract', | arguments: [{
 * params: [{ | type: 'NumberLiteral',
 * type: 'NumberLiteral', | value: '2'
 * value: '4' | }, {
 * }, { | type: 'CallExpression',
 * type: 'NumberLiteral', | callee: {
 * value: '2' | type: 'Identifier',
 * }] | name: 'subtract'
 * }] | },
 * }] | arguments: [{
 * } | type: 'NumberLiteral',
 * | value: '4'
 * ---------------------------------- | }, {
 * | type: 'NumberLiteral',
 * | value: '2'
 * | }]
 * (sorry the other one is longer.) | }
 * | }
 * | }]
 * | }
 * ----------------------------------------------------------------------------
 */

//该方法接收类lisp抽象语法树，转化为类c语言的ast树
function transformer(ast) {
 //创建新的ast节点
 let newAst = {
 type: 'Program',
 body: []
 }
 // 将新ast树的body作为原ast树的_context属性
 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: [],
 };
 
 // 接下来，我们将在原CallExpression节点
 //定义一个上下文，引用expression的参数，以便设置参数。
 node._context = expression.arguments;
 
 // 检测父节点是否CallExpresssion，如果不是执行下列代码
 if (parent.type !== 'CallExpression') {
 
 // 用`ExpressionStatement`节点包裹 `CallExpression`
 // 做这一步转换的原因是调用表达式最终是一个语句
 expression = {
 type: 'ExpressionStatement',
 expression: expression
 };
 }
 parent._context.push(expression);
 }
 }
 })

 return newAst;
}

代码生成

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

组成编译器

/**
 * 最后创建`compiler`编译函数，将上述方法按如下顺序结合即可
 * 1. input => tokenizer => tokens
 * 2. tokens => parser => ast
 * 3. ast => transformer => newAst
 * 4. newAst => generator => output
 */
function compiler(input) {
 let tokens = tokenizer(input);
 let ast = parser(tokens);
 let newAst = transformer(ast);
 let output = codeGenerator(newAst);
 return output;
}

总结

如上即用javscript完成了一个简单的编译器，如果你习惯用其他的语言如java，go，python等等，可以尝试改写一下。当然以上介绍分享的内容只包含了编译器的主要步骤，相当于一个编译器的hello world，但是通过代码实现有一个更直观的感受。后续有需要实现一些可能与编译有关的功能可以起到一定的帮助。

以上内容如有对您有所帮助，欢迎关注、分享、收藏。有任何问题或者建议也欢迎随时反馈，大家一起交流沟通，后续会提供更多优质的内容给到各位爱好技术的伙伴，谢谢！

#编译器##架构##前端##后台##JavaScript#