前端AST
前端AST
- 1、什么是编译器
- 2、什么是AST
- 3、编译器的基本思路
- 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/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 完整链路
- input => tokenizer => tokens; // 词法分析
- tokens => parser => ast; // 语法分析，生成AST
- ast => 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;
}