前端AST
- 前端AST
- 编译器
- 什么是编译器
- 编译器的思路
- 手写编译器
- 词法分析
- 语法分析
- 代码转换
- 代码生成
- 编译过程汇总
前端AST
- 什么是AST、编译器
- 编译器基本思路
- 手写一个简单的编译器
编译器
什么是编译器
compiler - 编译器
将一种代码，转换为另外一种代码
输入代码，也可以叫 源代码
目标代码(浏览器识别代码)：js / css
包括：
- sass / less / stylus -> css
- ts / vue / jsx / tsx / coffeescript(JS基础上，JS超集) -> js
- eslint / tslint 语法检查首先要先将源代码变成可识别的代码
使用场景：
- 对浏览器无法识别的代码，进行转换 -> es5
很多支持 es6，但是不会转 es6，因为es5更安全，具备更大的兼容性 - 热更新：举例，webpack热更新，微信小程序热更新，通过将最新的代码以字符串的形式给到端上，端将代码跑起来，js执行的前端页面，动态的修改 JS 代码，是不安全的，eval / new Function，被微信小程序禁止掉的
想做热更新，那么自己可以写一个类似 eval,new Function，然后转换为JS可执行的代码，也就是在自己的代码中内置一个AST解析工具，可以把任何特定规定的字符串转成一段代码 => 让 JS 自己执行 JS
自启动：用 GoLang 写一个 GoLang 的编译器 - 代码压缩
- 代码混淆(加密)：前端编译器技术将代码做特性意义的混淆
- 语法检查
- 语法高亮
- 代码自动补全(不是现在AI的这种，就是之前IDE中的简单补全)
编译器的思路
- 词法分析：将一段代码变成最小的一个个单元 -> tokens => 函数名：tokenizer
const test = require("tape")
最小单元：const、空格、test、=、require、（、）、“”
- 语法分析：-> AST => 函数名：parser
将这段代码的含义分析出来，将一个个单元变成有含义的
例如，const -> 关键字，test->变量名 - 代码转换 -> 源AST => 目标AST =>函数名：transformer+traverse
AST主要是给开发人员看的，形式化的语言，将这段代码变成与本身代码没有具体关系的
- 代码生成 -> ES5 =>函数名：generator
上述思路以及后续的命名都是参考的 Babel 的，Babel 是常规编译器的具体表现
C语言 和 Babel 类似，C语言连接编译，只是 C语言 最终转的为 机器码
es6 -> @babel/parser(做AST生成的) -> AST -> @babel/traverse(一种AST转为另外一种AST) -> new AST -> es5
Taro：将 Taro 语言的代码结构转换为小程序的代码结构，其实用的就是Babel，写了一个自己的 babel/parser+babel/traverse，将它的语法结构转化为 AST
手写编译器
根据上述所讲的四个步骤，将 input 代码经过 tokenizer，parser，transformer，codeGenerator 转换成各个阶段对应的所需结果，最终生成 output。
test.js：
const {tokenizer,parser,transformer,codeGenerator,compiler,
} = require('./utils');// 做各种断言的，判断值，函数调用后期望的值是否符合预期const assert = require('assert');const input = '(add 2 (subtract 4 2))'; // lisp//4. 代码生成所生成的JS代码const output = 'add(2, subtract(4, 2));'; // JS// 1. 词法分析生成的结果const 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: ')' }];// lisp 2.语法分析所生成的AST结构const 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'}]}]}]};// 3.代码转换生成的新的JS的AST结构const newAst = {type: 'Program',body: [{type: 'ExpressionStatement',//expression：表达式expression: {type: 'CallExpression',callee: {type: 'Identifier',name: 'add'},//表达式的参数列表arguments: [{type: 'NumberLiteral',value: '2'}, {type: 'CallExpression',//callee就是调用方，当前函数本身的信息callee: {type: 'Identifier',name: 'subtract'},arguments: [{type: 'NumberLiteral',value: '4'}, {type: 'NumberLiteral',value: '2'}]}]}}]};//deepStrictEqual 深度比较两个值是否相等assert.deepStrictEqual(tokenizer(input), tokens, 'Tokenizer should turn `input` string into `tokens` array');assert.deepStrictEqual(parser(tokens), ast, 'Parser should turn `tokens` array into `ast`');assert.deepStrictEqual(transformer(ast), newAst, 'Transformer should turn `ast` into a `newAst`');assert.deepStrictEqual(codeGenerator(newAst), output, 'Code Generator should turn `newAst` into `output` string');assert.deepStrictEqual(compiler(input), output, 'Compiler should turn `input` into `output`');console.log('All Passed!');const input = '(add 2 (subtract 4 2))';
可以看成是 function xxx(function add(2,function subtract(4,2))) 这样的函数
const output = 'add(2, subtract(4, 2));'; // JS
=> function add(2,function subtract(4,2)) 这样
词法分析
第一步：词法分析：将这个input转换为tokens
- 状态机：一类状态转换为另外一类状态的结果
input 是一种状态，tokens是另一种状态 - 有穷状态机：转换的结果是确定性的 - 简单理解：循环
- 非确定有穷状态机：一个输入可能有多个输出
- 确定有穷状态机：一个输入代表一个确定的输出
而上述将 input 状态 转换为 tokens的状态，这种就叫确定有穷状态机
tokens的类型只有三种：paren、name、number
const tokenizer = (input) => {const tokens = [];// 判断是否是字符串if (typeof input !== 'string') {return tokens;}for (let i = 0; i <= input.length - 1; i++) {const char = input[i];switch (true) {case char === ' ': //空格不处理break;case char === '(' || char === ')': //括号处理tokens.push({type: 'paren',value: char,});break;case isStrNumber(char): //数字处理let fullNum = char;//取下一位，因为一位数，两位数，三位数等都有可能出现let nextChar = input[++i];//下一位不是数字if (!isStrNumber(nextChar)) {i--;}//下一位是数字，循环遍历到不是数字while(isStrNumber(nextChar)) {fullNum += nextChar;nextChar = input[++i];}tokens.push({type: 'number',value: fullNum,});break;default: //字符串处理let fullStr = char;let nextStr = input[++i]//判断下一个是否是字符串或者数字，函数名可能为：add1这种类型if (!(isStrLetter(nextStr) || isStrNumber(nextStr))) {i--;}while (isStrLetter(nextStr) || isStrNumber(nextStr)) {fullStr += nextStr;nextStr = input[++i];}tokens.push({type: 'name',value: fullStr,});break;}}return tokens;
}
//判断是否是数字
const isStrNumber = (str) => {if (typeof str === 'number') {return true;}// 不是字符串也不是数字if (typeof str !== 'string') {return false;}if (str === ' ' || str === '') {return false;}return !isNaN(str);
}
//判断是否是字符串
const isStrLetter = (str) => {if (typeof str !== 'string') {return false;}//空格或空字符串if (str === ' ' || str === '') {return false;}// 通过 正则，asci码，toUpperCase和toLowerCase，判断字符串是否是26个字母的其中一个return str.toLowerCase() !== str.toUpperCase();
}
通过 正则，asci码，toUpperCase和toLowerCase，判断字符串是否是26个字母的其中一个
语法分析
讲究代码本身的含义
第二步，语法分析所生成的AST结构
看到嵌套结构，想到可能要写一个递归，由于嵌套结构是不可预测的
const parser = (tokens) => {const ast = {type: 'Program',body: []};let current = 0;const handler = () => {let item = tokens[current];current++;if (!item || !item.type) {return;}switch(true) {//先判断简单的-先判断numbercase item.type === 'number':return {type: 'NumberLiteral',value: item.value,};//paren和name是一起出现的，而且paren的出现代表着一个函数的开始，所以这里判断paren类型case item.type === 'paren' && item.value === '(': //一个逻辑结构的开始//current 已经指向下一个位置了，所以这个取得是下一个，也就是函数的名字item = tokens[current];const astNode = {type: 'CallExpression',name: item.value,params: [],};//在往后移一个，下下一个是函数的参数item = tokens[++current];//当前元素不是括号类型，或者是括号类型但是不是 ) 的类型 while (item.type !== 'paren'|| (item.type === 'paren' && item.value !== ')')// !(item.value === ')')) {//括号里就是一个完整的新结构了，可以进行递归调用了const subItem = handler();if (subItem) {astNode.params.push(subItem);}item = tokens[current];}current++;return astNode;}};while(current < tokens.length) {const result = handler();if (result) {ast.body.push(result);}}return ast;
}
代码转换
第三步，代码转换生成的新的JS的AST结构
使用 babel 的思路，transform + traverse，为了方便做插件开发的。
将代码从上往下做解析了，解析的过程不在函数里面去写，而是在外部定义一个访问者叫visitor(其实就是一个map)，告诉traverse应该怎么去转换代码，具体怎么遍历，怎么做上下文的管理，在visitor中不用去管，visitor只局限于当前一个的处理，具体的上下文，从前往后的遍历，状态管理等，都是traverse来做的。
也就是说，traverse本身变成了负责从前到后，从里到外，从外到里进行AST递归的产物，再告诉traverse怎么去处理每一种状态。
// 只做一件事，一个一个的转换结构
const traverser = (ast, visitor) => {// 两种情况：处理单个成员，处理数组// 生成body[0]成员const traverserNode = (node, parent) => { //需要知道成员本身，以及成员的上下文(当个数组来说，上下文就是父节点)// 拿到visitor中的enter函数const enter = visitor[node.type]?.enter; if (enter) {// 调用enter函数enter(node, parent);}switch (node.type) {// number不需要处理，因为上面已经调用过了case 'CallExpression':traverserArray(node.params, node); //当前节点:node的子节点 父节点：node本身break;case 'Program':traverserArray(node.body, node);break;}};// 生成params数组成员const traverserArray = (nodes, parent) => {nodes.forEach(node => {traverserNode(node, parent);});};traverserNode(ast, null);};// transform只做两件事情，1.调用traverser,2.声明traverser应该用什么样的方法去转换两种不同的结构
const transformer = (ast) => {const newAst = {type: 'Program',body: []};ast._context = newAst.body;traverser(ast, {//visitor像写插件的窗口处理函数// 函数处理CallExpression: {enter(node, parent) {// 给到父级对象成员，让父级对象成员统一去处理，因为父级对象成员可能有n个对象成员，父级成员中定义一个变量，管理父级成员中所有的子成员，就可以从内部往上一级一级遍历，也就是先将叶子节点转换完，再一层一层往上给，最后将值存到parent中就行let expression = {type: 'CallExpression',callee: {type: 'Identifier',name: node.name,},// 不让子组件直接操作arguments，因为arguments本身还要做特殊的处理arguments: [],};// 因此给node添加一个属性，让子组件去操作上下文，最终将_context中的值赋给argumentsnode._context = expression.arguments;if (parent?.type !== 'CallExpression') {// 当前节点是根组件expression = {type: 'ExpressionStatement',expression: expression};}// 如果父组件也是函数的话，就将当前表达式的信息给到父组件parent?._context?.push(expression);}},// 数字结构NumberLiteral: {enter(node, parent) {// 由此这里操作的是父组件的_contextparent?._context?.push({type: 'NumberLiteral',value: node.value,});}},});return newAst;
}
代码生成
第四步，代码生成所生成的JS代码
将input代码转换为output代码
const codeGenerator = (newAst) => {// 5种情况，单层结构中只关注这五种情况，五种结构中自己再去调用codeGenerator即可switch (newAst.type) {// 数字和标识符最简单，先处理这两个case 'Identifier':return newAst.name;case 'NumberLiteral':return newAst.value;// 处理函数 subtract(4, 2)case 'CallExpression':return [codeGenerator(newAst.callee),'(',newAst.arguments.map(codeGenerator).join(', '),')'].join('')case 'ExpressionStatement':return codeGenerator(newAst.expression) + ';';case 'Program':return newAst.body.map(codeGenerator).join('\n');}
}
编译过程汇总
使用compiler函数将上述所有函数包裹一起：
const compiler = (input) => {return codeGenerator(transformer(parser(tokenizer(input))));
};
这样输入input 会得到对应的 output 结果
所有内容汇总：
utils.js:
const isStrNumber = (str) => {if (typeof str === 'number') {return true;}if (typeof str !== 'string') {return false;}if (str === ' ' || str === '') {return false;}return !isNaN(str);
}const isStrLetter = (str) => {if (typeof str !== 'string') {return false;}if (str === ' ' || str === '') {return false;}return str.toLowerCase() !== str.toUpperCase();
}const tokenizer = (input) => {const tokens = [];if (typeof input !== 'string') {return tokeens;}for (let i = 0; i <= input.length - 1; i++) {const char = input[i];switch (true) {case char === ' ':break;case char === '(' || char === ')':tokens.push({type: 'paren',value: char,});break;case isStrNumber(char):let fullNum = char;let nextChar = input[++i];if (!isStrNumber(nextChar)) {i--;}while(isStrNumber(nextChar)) {fullNum += nextChar;nextChar = input[++i];}tokens.push({type: 'number',value: fullNum,});break;default:let fullStr = char;let nextStr = input[++i]if (!(isStrLetter(nextStr) || isStrNumber(nextStr))) {i--;}while (isStrLetter(nextStr) || isStrNumber(nextStr)) {fullStr += nextStr;nextStr = input[++i];}tokens.push({type: 'name',value: fullStr,});break;}}return tokens;
}const parser = (tokens) => {const ast = {type: 'Program',body: []};let current = 0;const handler = () => {let item = tokens[current];current++;if (!item || !item.type) {return;}switch(true) {case item.type === 'number':return {type: 'NumberLiteral',value: item.value,};case item.type === 'paren' && item.value === '(':item = tokens[current];const astNode = {type: 'CallExpression',name: item.value,params: [],};item = tokens[++current];while (item.type !== 'paren'|| (item.type === 'paren' && item.value !== ')')// !(item.value === ')')) {const subItem = handler();if (subItem) {astNode.params.push(subItem);}item = tokens[current];}current++;return astNode;}};while(current < tokens.length) {const result = handler();if (result) {ast.body.push(result);}}return ast;
}// 只做一件事，一个一个的转换结构
const traverser = (ast, visitor) => {// 两种情况：处理单个成员，处理数组// 生成body[0]成员const traverserNode = (node, parent) => { //需要知道成员本身，以及成员的上下文(当个数组来说，上下文就是父节点)// 拿到visitor中的enter函数const enter = visitor[node.type]?.enter; if (enter) {// 调用enter函数enter(node, parent);}switch (node.type) {// number不需要处理，因为上面已经调用过了case 'CallExpression':traverserArray(node.params, node); //当前节点:node的子节点 父节点：node本身break;case 'Program':traverserArray(node.body, node);break;}};// 生成params数组成员const traverserArray = (nodes, parent) => {nodes.forEach(node => {traverserNode(node, parent);});};traverserNode(ast, null);};// transform只做两件事情，1.调用traverser,2.声明traverser应该用什么样的方法去转换两种不同的结构
const transformer = (ast) => {const newAst = {type: 'Program',body: []};ast._context = newAst.body;traverser(ast, {//visitor像写插件的窗口处理函数// 函数处理CallExpression: {enter(node, parent) {// 给到父级对象成员，让父级对象成员统一去处理，因为父级对象成员可能有n个对象成员，父级成员中定义一个变量，管理父级成员中所有的子成员，就可以从内部往上一级一级遍历，也就是先将叶子节点转换完，再一层一层往上给，最后将值存到parent中就行let expression = {type: 'CallExpression',callee: {type: 'Identifier',name: node.name,},// 不让子组件直接操作arguments，因为arguments本身还要做特殊的处理arguments: [],};// 因此给node添加一个属性，让子组件去操作上下文，最终将_context中的值赋给argumentsnode._context = expression.arguments;if (parent?.type !== 'CallExpression') {// 当前节点是根组件expression = {type: 'ExpressionStatement',expression: expression};}// 如果父组件也是函数的话，就将当前表达式的信息给到父组件parent?._context?.push(expression);}},// 数字结构NumberLiteral: {enter(node, parent) {// 由此这里操作的是父组件的_contextparent?._context?.push({type: 'NumberLiteral',value: node.value,});}},});return newAst;
}
const codeGenerator = (newAst) => {// 5种情况，单层结构中只关注这五种情况，五种结构中自己再去调用codeGenerator即可switch (newAst.type) {// 数字和标识符最简单，先处理这两个case 'Identifier':return newAst.name;case 'NumberLiteral':return newAst.value;// 处理函数 subtract(4, 2)case 'CallExpression':return [codeGenerator(newAst.callee),'(',newAst.arguments.map(codeGenerator).join(', '),')'].join('')case 'ExpressionStatement':return codeGenerator(newAst.expression) + ';';case 'Program':return newAst.body.map(codeGenerator).join('\n');}
}const compiler = (input) => { //层层嵌套return codeGenerator(transformer(parser(tokenizer(input))));
};module.exports = {tokenizer,parser,transformer,codeGenerator,compiler
}
