编译程序(compiler)的简单分析

在现今前端项目中，模块化是一个避不开的话题。所以就会出现AMD,CMD等模块加载方式。同时由于JS不停的在更新迭代。出现很多实用的新语法。但是由于有些语法有些超前，JS的宿主环境(浏览器/Node没有跟上JS更新步骤)，但是为了在项目中使用这些好用到令人发指的新特性，来提高开发效率等。就出现了各种前端编译插件(Babel)。

Babel is a JavaScript compiler

大多数编译程序(compiler)分为三个步骤：Parsing(分析阶段)/Transformation(转换)/Code Generation（代码生成或者说生成目标代码）

1. Parsing 将源代码(raw code)转换为AST(抽象语法树)。
2. Transformation 接收Parsing生成的AST，并且按照compiler内定的规则进行代码的转换。
3. Code Generation 接受被compiler转换过的代码，按照一定的规则将代码转换为最终想要输出的代码格式。 现在有一个场景： 我们将一些LISP（高级计算机程序语言）方法通过compiler转码为C语言(通用计算机编程语言)的方法。 假如我们有'add'和'subtract'方法

Parsing(语法解析)

Parsing 一般被分成两个步骤：Lexical Analysis（词法分析）和 Syntactic Analysis(语法分析)

1. Lexical Analysis 接受raw code 同时通过tokenizer(标记器)或者lexer(词法分析器)将raw code 拆解为许多tokens。Tokens 是一系列描述独立的语法的对象。他们可以是数字，标签，标点符号，操作符等
2. Syntactic Analysis 接收LA处理过的tokens并且将他们重新构建为能够描述每一个语法代表什么含义并且描绘每个语法之间是如何关联的树行结构-----将每一个token视为一个Node结点，各个token之间存在的关联视为"树枝"，从而会构建一个能够表明各个token含义同时各个token之间关系的树形结构-------Abstract Syntax Tree(AST)。

AST 是一个层级很深的对象。

e.g. 对(add 2 (subtract 4 2))进行Parsing处理。 Tokens如下(Note:其实Token是根据lexer生成的，不同的lexer处理结果是不一样的。)

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

对应的Abstract Syntax Tree (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',
          }]
        }]
      }]
    }

复制代码

Transformation(AST转换)

transformation是compiler的第二个阶段。他会接收经过SA处理生成的AST。在该阶段能够利用一些语法规则，将AST转换为想被转换的语言。

通过观察AST会发现，每一个elements(从AST角度看)或者token(从LA角度看)都有一个type属性。这些element是属于AST的Node结点。这些nodes通过对type属性赋特定的值将AST划分成各自独立的区块。

e.g.

NumberLiteral 类型的Node

{

 type: 'NumberLiteral',

 value: '2',

 }
复制代码

CallExpression 类型的Node

{

 type: 'CallExpression',

 name: 'subtract',

 params: [...内嵌的node逻辑...],

 }
复制代码

在transforming AST过程中，我们可以通过adding/removing/replacing 属性来修改nodes，同时我们可以add/remove nodes,甚至我们可以基于现有的AST来重新构建新的AST对象。

由于我们是需要将LISP语法的代码转换为C的，所以我们的关注点就是基于SA输出的AST构建一个全新的适用于目标语言的AST对象。

Traversal(遍历)

为了能够在transforming过程中检测这些nodes。同时由于AST是一个层级很深的对象树，所以需要对AST进行depth-first（深度优先遍历）。(其实这和React在Render阶段是一样的)

{
      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，在traversal阶段，范围每个node的先后顺序如下

1. Program - Starting at the top level of the AST
2. CallExpression (add) - Moving to the first element of the Program's body
3. NumberLiteral (2) - Moving to the first element of CallExpression's params
4. CallExpression (subtract) - Moving to the second element of CallExpression's params
5. NumberLiteral (4) - Moving to the first element of CallExpression's params
6. NumberLiteral (2) - Moving to the second element of CallExpression's params

Visitors(游标)

为了用代码实现traversal过程，我们构建一个内置能够接收不同node类型函数的"visitor"对象。

var visitor = {
      NumberLiteral() {},
      CallExpression() {},
    };
复制代码

当在遍历AST的时候，在我们访问对应的node结点时，就会触发与之类型匹配的visitor中的方法。

如果只是单纯的在访问结点的时候触发对应的方法，这种情况是无法纪录访问的"轨迹"，所以需要对visitor进行改进。传入被访问的node结点，还有该node的直接父级结点。

var visitor = {
      NumberLiteral(node, parent) {},
      CallExpression(node, parent) {},
    };
复制代码

如果没有返回处理，"游标"在遍历到最后的node就会停止，因为他不知道下一步该如何进行。

- Program
      - CallExpression
        - NumberLiteral
        - CallExpression
          - NumberLiteral
          - NumberLiteral

复制代码

由于在遍历AST的过程中是采用depth-first的方式，就需要在访问到最后的node的时候，需要按照原路返回，直到返回到起点，这样才能被程序识别，这颗树被遍历完成了。

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

复制代码

为了实现上述逻辑，需要对visitor做额外的处理

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

复制代码

Code Generation(生成指定格式的代码)

compiler的最后阶段是code generation。有些compiler在CG阶段做的工作会和transformation的重叠，但是大部分的CG的工作就是接收 被处理过 的AST然后将AST对象字符化(该操作类似于JSON.stringify(Object))。 一个高效的CG是能够根据AST不同的node type输出对应的code，同时能够在树内进行递归调用直到所有的node都被字符化。