前端AST

1、什么是编译器2、什么是AST3、编译器的基本思路3.1 词法分析3.2 语法分析3.3 代码转换3.4 代码生成3.5 完整链路

4、一个简单的编译器的实现4.1 词法分析4.2 语法分析4.3 代码转换4.4 代码生成4.5 完整流程

1、什么是编译器

定义：编译器就是个将当前语言转为其他语言的过程

从某种语法代码转为另一种编写方式的代码

本质上是字符串的操作

babel：它所做的事就是语法糖之类的转换，比如ES6/ES7/JSX转为ES5或者其他指定版本

其他常见编译器：

Less/SassTypeScript/coffeeScriptEslintetc…

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 完整链路

input => tokenizer => tokens; // 词法分析tokens => parser => ast; // 语法分析，生成ASTast => transformer => newAst; // 中间层代码转换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;

}