200行代码实现超轻量级编译器

作者: gamedilong | 来源:发表于2019-11-11 11:53 被阅读0次

前言

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

概要

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

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

编译器组成

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

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

解析 Parsing

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

词法分析 获取原始代码，且将代码分割为一个一个词[token]
由这些词构成的词组用来描述语法，他们可以是数字，文本，标点符号，运算符等等
语法分析 获取词组[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，我们将：

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

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

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

Visitors

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

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

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

Program
- CallExpression
- NumberLiteral
- CallExpression
  - NumberLiteral
  - NumberLiteral

当我们往下遍历时，我们遍历尽所有分支时。我们“退出”它。因此，沿着树下来，我们“进入[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，但是通过代码实现有一个更直观的感受。后续有需要实现一些可能与编译有关的功能可以起到一定的帮助。

200行代码实现超轻量级编译器

前言

概要

编译器组成

解析 Parsing

示例语法

抽象语法树表示如下

翻译

遍历

Visitors

代码生成

代码

第一步获取token

parse 抽象语法树

转换抽象语法树

代码生成

组成编译器

总结

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序猿