A. 搞懂抽象语法书（AST）
【前端】搞懂抽象语法书（AST）什么是AST?抽象语法树（AbstractSyntaxTree，AST），或简称语法树（Syntaxtree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构--摘自维基网络
当写下一段代码的时候，其实写的就是一段字符串，如何让机器能够理解代码的逻辑，比如下面这段js代码：
const?x?=?1?+?2;每一种编程语言都有其独特的语法规则，而写下的代码是一个个的字符，为了让机器读懂书写的代码，需要一个个字符的去读取，第一步就是把其中的所有关键词提取出来，并且判断这些关键词属于什么类型，关系结构是怎么样。比如const是保留关键词，+和=号是操作符等等，并且把不同字段间的关系也表达出来，比如1+2是要赋值给x的等等。上述代码的抽象语法树如下：
//?采用?esprima?生成{??"type":?"Program",??"body":?[????{??????"type":?"VariableDeclaration",??????"declarations":?[????????{??????????"type":?"VariableDeclarator",??????????"id":?{?"type":?"Identifier",?"name":?"x"?},??????????"init":?{????????????"type":?"BinaryExpression",????????????"operator":?"+",????????????"left":?{?"type":?"Literal",?"value":?1,?"raw":?"1"?},????????????"right":?{?"type":?"Literal",?"value":?2,?"raw":?"2"?}??????????}????????}??????],??????"kind":?"const"????}??],??"sourceType":?"script"}这是用JSON的格式来表现了，不同的解析器其字段名可能有些不同，但是其本质是一样的。
如何生成AST生成AST的第一步就是读取字符串，然后识别出一个个的token，比如下面这个JS的代码片段，需要识别出const,a,=,19,1,2,-,a,/,10这些标识(token)，这些标识是有分类的，比如const是保留关键词，a、b是变量，=、*、-、/这些的操作符。
const?a?=?10const?b?=?sum(1?*?2?-?a?/?10,?10)然后根据语言的语法规则来排列、分类这些token，从而形成一种树状结构（AST）。
Shunting-Yard算法了解这个算法前，先来复习一些概念，下面摘录自wikipedia:
中缀表示法（Infixnotation，或中缀记法）是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间。例：1*2-10/10
波兰表示法（Polishnotation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。
逆波兰表示法（ReversePolishnotation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。例：12*1010/-
Shunting-Yard算法就是把中缀表示法转换为逆波兰表示法。也就是把1*2-a/10转换为12*1010/-的形式。这种形式非常易于计算机处理
为什么要使用逆波兰表示法？这种表示方法非常易于计算机处理，具体的解释不是本文的重点，可以看这里：https://zh.wikipedia.org/wiki/逆波兰表示法
这和抽象语法树有什么关系？把几种表示方式放在一起比较一下
逆波兰表示法：?1?2?*?10?10?/?-把?1?*?2?-?10?/?10?转换为下面的树形表示法，??????-??*????????/1???2???10???10//?再把上述的结构转换为，JSON数据结构表示：{??"type":?"Program",??"body":?[????{??????"type":?"ExpressionStatement",??????"expression":?{????????"type":?"BinaryExpression",????????"operator":?"-",????????"left":?{??????????"type":?"BinaryExpression",??????????"operator":?"*",??????????"left":?{?"type":?"Literal",?"value":?1,?"raw":?"1"?},??????????"right":?{?"type":?"Literal",?"value":?2,?"raw":?"2"?}????????},????????"right":?{??????????"type":?"BinaryExpression",??????????"operator":?"/",??????????"left":?{?"type":?"Identifier",?"name":?"a"?},??????????"right":?{?"type":?"Literal",?"value":?10,?"raw":?"10"?}????????}??????}????}??],??"sourceType":?"script"}当把几种方式放在一起比较的时候，发现其实是一致的，AST的数据结构只是给每一个token添加更多的属性，以实现更加复杂的语法，其本质没有变化。
算法实现原理直接用一个例子来看看算法的实现吧：
//?这里操作符的优先级，默认为从小学的数学的操作符的优先级，没有什么特殊哦1?*?2?+?(10?-?2)?*?5转换为RPN和AST的过程Token算法行为输出操作符堆栈1把1输出1*把*放入堆栈1*2把2输出12*+把*出栈输出12*+把+放入堆栈12*+(把(放入堆栈12*(+10把10输出12*10(+-把-放入堆栈12*10-(+2把2输出12*102-(+)把-出栈12*102-(+)把(出栈12*102-+*把*放入堆栈12*102-*+5把5输出12*102-5*+结束把所有的操作符出栈12102-5+*+转换为AST的过程和上述非常相似，最终的结果12*102-5*+
如果把这个放入一个堆栈，然后再一个个出栈就可以构建AST树了，来试试看：
Token类型算法行为+二元操作符（BinaryExpression）出栈，它就是树的root，发现是二元操作符，所以会有左右两个子节点*二元操作符出栈，它是root的右节点，本身是二元操作符，会有左右两个节点5数字出栈，它是*的右节点-二元操作符出栈，*的左节点，本身是二元操作符，会有两个子节点2数字出栈，-的右节点10数字出栈，-的左节点，-、*子节点都满了，回到+节点*二元操作符出栈，它是+根节点的左节点，本身是二元操作符，创建两个子节点2数字出栈，*的右节点1数字出栈，*的左节点这个例子中，只有数字和操作符，如果加入变量，那么过程也是一样的，只是类型不同罢了。
AST的一些应用场景AST的应用场景是非常广泛的，在写代码的过程中，在不知觉中就用到了，代码可以转换为AST，AST也可以转换为代码。下面是一些应用场景的例子：
IDE
代码高亮，纠错等功能都是基于AST的
代码转译
经常使用babel，通过分析AST，把新的语法转换为旧的语法实现。
比如像Typescript作为JS的超集，编译到JS的过程需要用到AST
代码的一些处理，比如JS的minify
通过代码生成文档的实现
代码静态扫描
解析器下面列举一些js、ts的解析器的实现库
库名针对语言地址acornesnext&JSX(usingacorn-jsx)https://github.com/acornjs/acornesprimaesnext&olderhttps://github.com/jquery/esprimacherowesnext&olderhttps://github.com/cherow/cherowespreeesnext&olderhttps://github.com/eslint/espreeshiftesnext&olderhttps://github.com/shapesecurity/shift-parser-jsbabelesnext,JSX&typescripthttps://github.com/babel/babelTypeScriptesnext&typescripthttps://github.com/Microsoft/TypeScriptBabelbabel是一个编译器，可以把新的js语法编译为老的语法实现。现在基本上为了提高生产力，babel必然是所用的构建工具中的一环。所以很有必要了解，简单从AST的角度介绍下。
babel主要三步走来完成编译的过程
读入JS源代码，转换成AST
遍历AST所有节点，运行插件，执行转换任务，比如把变量a重命名为x，这个过程生成了一个新的转换过的AST
把新的AST生成新的JS代码
这三个过程分别对应了三个包：@babel/parser,@babel/traverse,@babel/generator
当时通常不需要主动调用这些包的方法来自己手动做，只要通过一定的规范格式，写插件即可。
下面是一个简单的直接使用的例子：
const?parser?=?require("@babel/parser");const?traverse?=?require("@babel/traverse").default;const?generate?=?require("@babel/generator").default;const?sampleCode?=?`function?add(a,?b)?{??return?a?+?b}`;//?1.解析为ASTconst?ast?=?parser.parse(sampleCode);//?2.遍历，并做转换traverse(ast,?{??FunctionDeclaration:?function(path)?{????path.node.id.name?=?'addTwo'??}});//?3.重新生成新的代码const?result?=?generate(ast)console.log(result.code)//?打印的结果是//?function?addTwo(a,?b)?{//????return?a?+?b//?}这是一个非常基本的例子，但是涵盖了babel整个工作的基本打框架，可以看到AST在其中的关键作用。
总结虽然在平时工作中，尤其在业务开发中很少用到，但是当想要对一些编程工具、编译工具、写一些babel或者webpack的插件，去构建一些提效工具的时候，就需要涉及AST的概念，所以去理解，去了解是很有必要。
原文：https://juejin.cn/post/7100082653256220686