18°

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

前言

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

概要

  1. 本篇和大家一起学习写一款超级简单轻量,去掉注释只有不到200行代码的编译器。
  2. 该编译器将类 lisp 语法函数调用 编译为 类C语言函数调用
  3. 如果不熟悉上述的两种语法的其中任意一种,下面给出了简单的介绍
  4. 例如有两个函数 addsubtract 他们用对应的语言分别实如余下:
内容 类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))
  1. 本篇要实现编译的全部语法如上所示。虽然既不涵盖完整的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() {},
};

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

  • 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 &lt; 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' &amp;&amp; 
        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' &amp;&amp; token.value !==')')){   
            node.params.push(walk());
            token = tokens[current];
        }
        current++;
        return node;
    }
    // 如果不是以上检测的类型则抛出异常
    throw new TypeError(token.type);
}
let ast = {
    type:'Program',
    body:[]
}
while(current &lt; 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 &amp;&amp; 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 &amp;&amp; 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,但是通过代码实现有一个更直观的感受。后续有需要实现一些可能与编译有关的功能可以起到一定的帮助。

本文由【g】发布于开源中国,原文链接:https://my.oschina.net/u/1453302/blog/3160443

全部评论: 0

    我有话说: