AST编译学习

技术学习：AST

前言

前段时间在开发CMS更新模态框的需求，有做到将md文件解析“tokens”再将“tokens”转换为json的步骤，组内交流说业界有md转json的工具
想着自己原来只是简单了解过AST，而AST在我们前端开发中运用的还比较多，于是去系统学习一下（然后就有了这篇文章）

概念

AST是Abstract Syntax Tree(抽象语法树)的简称
抽象：源代码语法结构的一种抽象
语法树：树状形式表现（树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构）

可以说AST是前端工程化绕不过的一个名词，为什么呢？

1
2
3

Most people don't really have to think about compilers in their day
jobs. However, compilers are all around you, tons of the tools you use are based
on concepts borrowed from compilers.

涉及到工程化诸多环节的应用，比如：

Typescript => Javascript (typescript)
SASS/LESS => CSS (sass/less)
ES6+ => ES5 (babel)
Javascript 代码进行格式化 (eslint/prettier)
识别 React 项目中的 JSX (不是js原生的写法)
Vue SFC（单文件组件single file component）
js uglify
Tree Shaking（通过 AST 将用不到的函数进行移除，从而减小打包体积）

Vue SFC

vuesfc

js uglify

1. 代码精简
// 对两个数求和
function sum (first, second) {
  return first + second;
}
// ----------去除空格注释换行----------
function sum(first,second){return first+second}
// ----------压缩变量名，函数名及属性名----------
function s(x,y){return x+y}

2. 合并声明
// 压缩前
const a = 3;
const b = 4;

// 压缩后
const a = 3, b = 4;

3. 布尔简化
// 压缩前
!b && !c && !d && !e

// 压缩后
!(b||c||d||e)

4. 预计算
// 压缩前
const ONE_YEAR = 365 * 24 * 60 * 60

// 压缩后
const ONE_YAAR = 31536000

// 压缩前
function hello () {
  console.log('hello, world')
}

hello()

// 压缩后
console.log('hello, world')

在语言转换的过程中，实质上就是对其 AST 的操作

Code -> AST（Parse）解析
AST -> AST（Transform）转换另外一种语言的AST

如将ts转化为ts的ast，再将ts的ast转化为js的ast
AST -> Code（Generate）生成代码

以下是一段代码和它转换的AST

// Code
const a = 4

// AST
{
  "type": "Program",
  "start": 0,
  "end": 11,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 11,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 6,
          "end": 11,
          "id": {
            "type": "Identifier",
            "start": 6,
            "end": 7,
            "name": "a"
          },
          "init": {
            "type": "Literal",
            "start": 10,
            "end": 11,
            "value": 4,
            "raw": "4"
          }
        }
      ],
      "kind": "const"
    }
  ],
  "sourceType": "module"
}

不同的语言拥有不同的解析器：
比如 Javascript （Babel）的解析器和 CSS 的解析器（postcss）就完全不同
对相同的语言，也存在诸多的解析器，也就会生成多种 AST：
如babel与 espree

AstExplorer

AST生成

AST的生成是个复杂度极高过程，AST 的生成这一步骤被称为解析（Parser）

可以理解为把一门编程语言转成另一门编程语言的过程，一般是指高级语言到低级语言

解析步骤分为两个阶段:

词法分析（Lexical Analysis）
语法分析（Syntactic Analysis）

词法分析

词法：词法组成语言的单词，是语言中最小单元
词法分析：将代码转化为 Token 流，维护一个关于 Token 的数组

可以理解成代码中一系列独立的单词，var，for ，if，while等
词法分析的过程就是读取代码，识别每一个单词及其种类，将它们按照预定的规则合并成一个个的标识，也叫 token
同时，它会移除空白符，注释等，最终产出一个token数组。
即词法分析阶段把会字符串形式的代码转换为 令牌（tokens） 流

类比于开发CMS更新模态框时将md文档内容拆出一块块小块

// code
const a = 10;

// token
[
  { type: "KEYWORD_CONST", value: "const" }, 
  { type: "VARIABLE", value: "a" },
  { type: "OPERATOR_EQUAL", value: "=" },
  { type: "INTEGER", value: "10" }
  ...
]

应用：

代码检查，如 eslint 。例如：判断是否以分号结尾，则判断是否含有分号的 token（AST相同）
语法高亮，如 highlight.js / prism.js 使代码高亮
模板语法，如 ejs 等模板，参考hexo中使用到的ejs

语法分析

语法：描述逻辑的格式（源程序是按照一定的格式组织的描述逻辑的文本）
语法分析：根据词法，将 Token 流转化为结构化的 AST（树形的数据结构），方便操作
类比于CMS更新模态框需求将一个个小块转化为json

源码学习

❌ 看babel的源码了解编译器工作原理，很多人都会望而却步。

✅ babel的维护者之一 James Kyle 有一个最小编译器的开源项目 the-super-tiny-compiler，截止目前超过21.5k stars。项目去掉注释大约200行代码，代码虽少，但足以展现编译器的很多要点，通过学习这个项目，可以对编译原理有一个较系统的理解

the-super-tiny-compiler

链接：the-super-tiny-compiler

all written in js
Lisp语言风格函数调用 => 转换成C语言风格（不包含所有语法）
比如假设我们有add和subtract两个函数，两种语言的风格如下：

	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. input  => tokenizer   => tokens
 *  2. tokens => parser      => ast
 *  3. ast    => transformer => newAst
 *  4. newAst => generator   => output
 */
function compiler(input) {
  // 拆分成tokens
  let tokens = tokenizer(input);
  // tokens解析成ast
  let ast = parser(tokens);
  // ast => ast
  let newAst = transformer(ast);
  // generate new ast
  let output = codeGenerator(newAst);

  // output
  return output;
}

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

step1 input => tokenizer => tokens

function tokenizer(input) {

  let current = 0;

  let tokens = [];

  while (current < input.length) {

    let char = input[current];
   // 括号处理
    if (char === '(') {

      tokens.push({
        type: 'paren',
        value: '(',
      });

      current++;

      continue;
    }
   // 括号处理
    if (char === ')') {
      tokens.push({
        type: 'paren',
        value: ')',
      });
      current++;
      continue;
    }
   // 空白符号处理
    let WHITESPACE = /\s/;
    if (WHITESPACE.test(char)) {
      current++;
      continue;
    }
   // 对于数字处理
    let NUMBERS = /[0-9]/;
    if (NUMBERS.test(char)) {

      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;
    }
   // 对于字母处理
    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;
    }
   // unrecognized
    throw new TypeError('I dont know what this character is: ' + char);
  }

  return tokens;
}

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

step2 tokens => parser => ast

function parser(tokens) {

  let current = 0;

  // use recursion, so we use walk instead of a while loop
  function walk() {

    let token = tokens[current];

    // number
    if (token.type === 'number') {

      current++;

      return {
        type: 'NumberLiteral',
        value: token.value,
      };
    }

    // string
    if (token.type === 'string') {
      current++;

      return {
        type: 'StringLiteral',
        value: token.value,
      };
    }

    // open
    if (
      token.type === 'paren' &&
      token.value === '('
    ) {

      token = tokens[++current];

      let node = {
        type: 'CallExpression',
        name: token.value,
        params: [],
      };

      token = tokens[++current];

      //   [
      //     { 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
      //   ]

      // !close
      while (
        (token.type !== 'paren') ||
        (token.type === 'paren' && token.value !== ')')
      ) {

        // recursion
        node.params.push(walk());
        token = tokens[current];
      }

      current++;

      return node;
    }

    throw new TypeError(token.type);
  }

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

  while (current < tokens.length) {
    ast.body.push(walk());
  }

  return ast;
}

step3 ast => transformer => newAst

访问者模式

定义：
你可以只修改 Visitor 本身完成新操作的定义，而不需要修改原本对象
类似于polyfill实现
在使用的时候以目标浏览器版本作为访问者，实现对应访问者的功能

转换需要深度优先遍历AST：

Program 类型 - 从 AST 的根节点开始
CallExpression (add) - 进入 Program 节点 body 属性的第一个子元素
NumberLiteral (2) - 进入 CallExpression (add) 节点 params 属性的第一个子元素
CallExpression (subtract) - 进入 CallExpression (add) 节点 params 属性的第二个子元素
NumberLiteral (4) - 进入 CallExpression (subtract) 节点 params 属性的第一个子元素
NumberLiteral (2) - 进入 CallExpression (subtract) 节点 params 属性的第二个子元素

可以使用访问者模式：

创建一个类似下面的“访问者”对象，以提供访问各种数据类型的方法

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

当遍历AST的时，一旦匹配到特定类型的节点，就调用访问者提供的方法。同时为了保证访问者能够拿到当前节点信息，我们需要将当前节点和父节点传入（有点类似react fiber结构中断续传的实现）

var visitor = {
    NumberLiteral(node, parent) {},
    CallExpression(node, parent) {},
}

存在进入叶子节点，退出（exit）分支的行为。即对树深度遍历时，每个节点会存在两种操作，一种是enter/exit

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

/** -------------------------- **/

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

改造数据结构为

const visitor = {
  NumberLiteral: {
    enter(node, parent) {},
    exit(node, parent) {},
  },
  CallExpression: {
    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);
    }

    // Next we are going to split things up by the current node type.
    switch (node.type) {

      case 'Program':
        traverseArray(node.body, node);
        break;

      case 'CallExpression':
        traverseArray(node.params, node);
        break;

      // no child nodes to visit, just break.
      case 'NumberLiteral':
      case 'StringLiteral':
        break;

      default:
        throw new TypeError(node.type);
    }

    if (methods && methods.exit) {
      methods.exit(node, parent);
    }
  }

  traverseNode(ast, null);
}

transformer

/* ----------------------------------------------------------------------------
 *   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.)  |         }
 *                                    |       }
 *                                    |     }]
 *                                    |   }
 * ----------------------------------------------------------------------------
 */

function transformer(ast) {

  // init
  let newAst = {
    type: 'Program',
    body: [],
  };

  // （引用类型）通过 _context 引用，更新新旧节点
  ast._context = newAst.body;

  // ast and a visitor
  traverser(ast, {
   // NumberLiteral
    NumberLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'NumberLiteral',
          value: node.value,
        });
      },
    },

    // StringLiteral
    StringLiteral: {
      enter(node, parent) {
        parent._context.push({
          type: 'StringLiteral',
          value: node.value,
        });
      },
    },

    // 函数调用
    CallExpression: {
      enter(node, parent) {

        // create a new node CallExpression with a nested Identifier
        let expression = {
          type: 'CallExpression',
          callee: {
            type: 'Identifier',
            name: node.name,
          },
          arguments: [],
        };

        // _context 引用参数，供子节点使用
        node._context = expression.arguments;

        if (parent.type !== 'CallExpression') {

          // 顶层函数调用本质上是一个语句，写成特殊节点 ExpressionStatement？why
          expression = {
            type: 'ExpressionStatement',
            expression: expression,
          };
        }

        parent._context.push(expression);
      },
    }
  });

  return newAst;
}

step4 newAst => generator => output

function codeGenerator(node) {

  switch (node.type) {

    case 'Program':
      return node.body.map(codeGenerator) // item => codeGenerator(item)
        .join('\n');

    // 顶层
    case 'ExpressionStatement':
      return (
        codeGenerator(node.expression) +
        ';' // << (...because we like to code the *correct* way)
      );

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

end

1	add(2, subtract(4, 2))

Babel

再来简单了解一下babel：

@babel/parser
@babel/traverse和@babel/types
@babel/generate

利用上面所学的知识，实现对var => let的转换

const parser = require('@babel/parser');
const traverse = require('@babel/traverse');
const generator = require('@babel/generator');

const code = `const a = 1
var b = 2
let c = 3
var d = 4`;

const transToLet = code => {
  // 1. 解析成ast
  const ast = parser.parse(code);
  // 定义访问者
  const visitor = {
    // 遍历声明表达式
    VariableDeclaration(path) {
      // 类型 = 变量声明
      if (path.node.type === 'VariableDeclaration') {
        // 替换
        if (path.node.kind === 'var') {
          path.node.kind = 'let';
        }
      }
    },
  };
  // 2. 遍历ast
  traverse.default(ast, visitor);
  // 生成代码
  const newCode = generator.default(ast, {}, code).code;
  return newCode;
};

console.log(transToLet(code))

总结

了解AST概念及运用范围
对于大多数编译器的架构和原理有了系统的认知
对于编译器涉及到的访问者模式值得借鉴
利用the-super-tiny-compiler所学简单使用babel转换