all articles

compiler in JavaScript 1 - a tiny compiler

2017-04-10 @sunderls

compiler js

1. 背景

在上一篇自己实现一个简陋的webpack中,我们用到了esprima来parse js代码。具体我大学非cs科班,parser相关的没有啥概念,总之parser估计就是把某种格式的代码转化成另外一种表达吧,esprima在parse的时候,接受js字符串,然后根据js的语法定义进行分析,得到了一个js 程序的内部表达。在esprima的官网可以看到这样的例子:

输入:

var answer = 6 * 7;

没看parse结果之前个人的理解是分两部分:

  1. 变量声明 var answer
  2. 表达式 6 * 7

实际的结果是:

{
    "type": "Program",
    "body": [
        {
            "type": "VariableDeclaration",
            "declarations": [
                {
                    "type": "VariableDeclarator",
                    "id": {
                        "type": "Identifier",
                        "name": "answer"
                    },
                    "init": {
                        "type": "BinaryExpression",
                        "operator": "*",
                        "left": {
                            "type": "Literal",
                            "value": 6,
                            "raw": "6"
                        },
                        "right": {
                            "type": "Literal",
                            "value": 7,
                            "raw": "7"
                        }
                    }
                }
            ],
            "kind": "var"
        }
    ],
    "sourceType": "script"
}

也就是说得到了一个VariableDeclaration,这个声明的init初始化是一个BinaryExpression。另外可以看到Identifieranswerkindvar , 直观印象是,非常细碎。如果要写一个js的parser的话,需要清楚定义js的各个语法, oh my god

2. parser可以干嘛

像上篇文章进行代码分析,根据各个语法做各自的变化得到想要的结果,这就是parser的主要作用吧应该。esprima的官网上提供了一个重写的例子,比如把单引号改为双引号之类的,以及一个minification的例子,minification的话,主要是变量名重写,感觉可以检查var等的使用,然后根据字母顺序进行替换就可以吧?嗯,暂时还没试过。

parser是compiler的一部分。哎呀呀,真是麻烦,总之compiler有以下一些概念 :

  1. lexer - 将代码分解为单词
  2. parser - 单词组合为语句
  3. semantic Analysis - 检查语句的组合是否ok
  4. optimizer - 优化
  5. code generator - 输出code,和输入code意义一样但是有不同表述

上述概念看了,也有点懵,所以webpack属于一个compiler了嗯。为了加深理解,直接看compiler源代码吧(网上找到了一个the super tiny compiler)

3. the super tiny compiler

这个作者在源代码中写了很丰富的comment,强力建议去阅读试试。如果你比较偷懒的,可以看我在这里的学习笔记。

3.1 目标

这个compiler目标是转换LISP风格的语句为c风格的代码(我不会LISP。。。):

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

嘛,看了这个感觉像写个简单的计算器? compiler可以分三部分 parsing(建立语法树)),transformation(做需要的变形),code生成。

3.2 parsing

parsing分两步,第一步是取词(lexical analysis),将代码分解成一个一个token(像单词那样),然后第二步是语义分析(Syntactic Analysis),接受第一步的一个个token,然后组合成一个抽象语法输(Abstract Syntax Tree)

比如原来的语句

(add 2 (subtract 4 2))

抽词过后

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

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',
         }]
       }]
     }]
   }

3.2.1 tokenizer

如何抽词,感觉比较简单,直接一个一个字符读入就行了:

  1.  如果是括号,就判定为一个paren
  2. 如果是空白,就将连续的空白跳过
  3. 如果是数字,将连续的数字判定为一个number
  4. 如果遇到了双引号,双引号之内的判定为一个string
  5. 剩余的就是方法名了,比如add,这些连续的字符判定为一个name
  6. 其他的情况,报错

这个感觉还是很容易实现的,源文件的实现采用了while循环检测的方式,没毛病。不过其中关于连续的检测经常用到,可以单独抽离出来我觉得,后面自己写parser的时候试一试。

3.2.2 parser

上述tokenizer给了我们一堆单词(token),现在进行语法分析。目标语言非常简单,只有CallExpression:(add a b)这一种形式,复杂的地方在于其可以嵌套,如何处理呢?

首先CallExpression有2三部分:

  1. name: add substract
  2. params: 两个参数

其中参数可以是数字,或者又一个CallExpression,CallExpression的开始标志就是一个paren+name源代码使用了一个递归的walk()方法,这个方法返回下一个ast节点。

1. 依次取得下一个token,如果token是数字,则返回一个NumberLiteral

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

2. 如果是string,返回一个StringLiteral

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

3. 如果是起始括号,则创建CallExpression,params则用下一个walk()来补充

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

    // 这里tick下一次walk(), 在遇到闭合括号之前,都可以当做params来处理
    while (
        (token.type !== 'paren') ||
        (token.type === 'paren' && token.value !== ')')
    ) {
        // we'll call the `walk` function which will return a `node` and we'll
        // push it into our `node.params`.
        node.params.push(walk());
        token = tokens[current];
    }
    return node;
}

4. 其他情况下报错,最后wrap一下,返回一个根结点

let ast = {
    type: 'Program',
    body: [],
};

// 程序可能有多行
while (current < tokens.length) {
    ast.body.push(walk());
}
return ast;

parser部分也比较简单,不过感觉写法上可以更加自然一些,后面再看。

3.3 traversing 遍历

AST是个树形结构,所遍历也用递归好了,最终会形成深度优先。遍历只是一种方式,具体目的的话还是得看遇到了某一个语法需要做什么事情,源代码的travers方法支持传入一个visiter参数,这个visiter可以定义enter, exit两个hook,供节点进入和退出的时候调用。

而hook是为了改变自身,在json的情况下,需要保持一个对父节点的引用,所以hook的参数是(node, parent)

3.4 变形

有了上述遍历方法,我们可以给代码变形了。代码中的例子是把CallExpression

{
    type: 'CallExpression'
    name: String
    params: Array
}

变为

{
    type: 'CallExpression'
    callee: {
        type: 'Identifier',
        name: String
    }
    params: Array
}

感觉上就是从一棵树,构建出另外一棵树。所以保持两个cursor,复制和替换就好了。源代码看这里

如果要求值的话?可以看出可以写一个类似于reduce的visiter,把ast转换为一个值。

3.5 代码生成器

这个感觉还是很容易实现的。ast的生成是按照文本先后顺序生成的深度优先。所以深度优先遍历然后根据node不通种类生成字符串就ok,需要注意的是换行的处理。 代码

3.6 compiler

最后,wrap成一个compiler

function compiler(input) {
  let tokens = tokenizer(input);
  let ast    = parser(tokens);
  let newAst = transformer(ast);
  let output = codeGenerator(newAst);

  // and simply return the output!
  return output;
}

结束。感觉上还是可以hold住的,compiler的学习可以继续进行下去。