前端AST

1、什么是编译器

定义：编译器就是个将当前语言转为其他语言的过程
从某种语法代码转为另一种编写方式的代码
本质上是字符串的操作
babel：它所做的事就是语法糖之类的转换，比如ES6/ES7/JSX转为ES5或者其他指定版本
其他常见编译器：

• Less/Sass
• TypeScript/coffeeScript
• Eslint
• etc…

2、什么是AST

抽象语法树，ast，全称是 Abstract Syntax Tree，是源代码的抽象语法结构的树状表现形式
dsl：领域特定语言，如SQL、CSS、HTML、JSX
低代码平台，也有对应的dsl

3、编译器的基本思路

编译器的工作过程一般分为三个阶段：
1、解析：将源代码转换为抽象语法树（AST）@babel/core parse（词法分析tokenizer、语法分析parser）
2、变换：对AST进行变换操作。@babel/traverse traverse
3、生成：根据变换后的AST生成目标代码。@babel/generator generate

整个可以这样理解：源代码我们把它看做字符串，目标代码亦是字符串，编译器的工作就是将源代码字符串转换为目标代码字符串
结合自然语言的理解：源码字符串->词法分析->语法分析->语义分析->目标代码字符串

3.1 词法分析

分词器：tokenizer(code)

词法分析将文本分割成一个个的“token”，例如：init、main、init、x、;、x、=、3、;、}等等。同时它可以去掉一些注释、空格、回车等等无效字符；

词法分析生成token的办法有2种：

• 正则表达式
• 自动机

正则表达式只适合一些简单的模板语法，真正复杂的语言并不合适，需要写大量的正则表达式，正则之间还有冲突需要处理，不容易维护，性能不高。

自动机可以很好的生成token；有穷状态自动机（finite state machine）：在有限个输入的情况下，在这些状态中转移并期望最终达到终止状态。

有穷状态自动机根据确定性可以分为：
“确定有穷状态自动机”（DFA - Deterministic finite automaton）
在输入一个状态时，只得到一个固定的状态。DFA 可以认为是一种特殊的 NFA；
“非确定有穷自动机”（NFA - Non-deterministic finite automaton）
当输入一个字符或者条件得到一个状态机的集合。JavaScript 正则采用的是 NFA 引擎

3.2 语法分析

词法分析器：parser(tokens)
编译原理就是将一种语言转换为另一种语言， 语法分析的目的就是通过词法分析器拿到的token流 + 结合文法规则，通过一定算法得到一颗抽象语法树（AST）。
典型应用如babel插件，它的原理就是：es6代码 → Babylon.parse → AST → babel-traverse → 新的AST → es5代码。
从生成AST效率和实现难度上，前人总结主要有2种解析算法：自顶向下的分析方法和自底向上的分析方法。自顶向下算法实现相对简单，并且能够解析文法的范围也不错，所以一般的compiler都是采用深度优先索引的方式。

3.3 代码转换

转化器：transformer(ast)
在得到AST后，我们一般会先将AST转为另一种AST，目的是生成更符合预期的AST，这一步称为代码转换。

3.4 代码生成

生成器：generator(newAst)
在实际的代码处理过程中，可能会递归的分析（）我们最终生成的AST，然后对于每种type都有个对应的函数处理，当然，这可能是最简单的做法。总之，我们的目标代码会在这一步输出，对于我们的目标语言，它就是HTML了。

3.5 完整链路

1. input => tokenizer => tokens; // 词法分析
2. tokens => parser => ast; // 语法分析，生成AST
3. ast => transformer => newAst; // 中间层代码转换
4. newAst => generator => output; // 生成目标代码

4、一个简单的编译器的实现

如果我们有两个函数 add 和 subtract 他们会写成这样：

类似 C

• 2 + 2 ： (加 2 2) 加 (2, 2)
• 4 - 2 ： (减 4 2) 减 (4, 2)
• 2 + (4 - 2) ： (加 2 (减 4 2)) 加 (2, 减 (4, 2))

对于以下语法：(加 2 (减 4 2))
词法分析后，生成tokens

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

语法分析后，生成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',}]}]}]}   

4.1 词法分析

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;}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;}throw new TypeError('I dont know what this character is: ' + char);}return tokens;
}

4.2 语法分析

function parser(tokens) {let current = 0;function walk() {let token = tokens[current];if (token.type === 'number') {current++;return {type: 'NumberLiteral',value: token.value,};}if (token.type === 'string') {current++;return {type: 'StringLiteral',value: token.value,};}if (token.type === 'paren' && token.value === '(') {token = tokens[++current];let node = {type: 'CallExpression',name: token.value,params: [],};token = tokens[++current];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;
}

4.3 代码转换

/*** ============================================================================*                                 ⌒(❀>◞౪◟<❀)⌒*                              代码转换方法!!!* ============================================================================*/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);
}/*** ============================================================================*                                   ⁽(◍˃̵͈̑ᴗ˂̵͈̑)⁽*                              代码转换!!!* ============================================================================*//**** ----------------------------------------------------------------------------*   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) {let newAst = {type: 'Program',body: [],};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: [],};node._context = expression.arguments;if (parent.type !== 'CallExpression') {expression = {type: 'ExpressionStatement',expression: expression,};}parent._context.push(expression);},},});return newAst;
}

4.4 代码生成

function codeGenerator(node) {switch (node.type) {case 'Program':return node.body.map(codeGenerator).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);}
}

4.5 完整流程

/****   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;
}