网站后台数据,北京分类信息网,铜山区建设局网站,小程序游戏制作平台前端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、什么是编译器
定义#xff1a;编译器就是个将当前语言… 前端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、解析将源代码转换为抽象语法树ASTbabel/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;
}
