你用过的所有前端编译工具,AST遍历思路就这一种
发布网友
发布时间：2024-10-14 09:47
共1个回答
热心网友
时间：2024-10-14 14:25
作为前端，我们会用很多编译工具：typescriptcompiler、babel、eslint、postcss等等，它们的AST不尽相同，但AST的遍历算法有且只有一种，不信我们慢慢来理一下。
AST的遍历思路编译工具会把源码转成AST，从而把对字符串的操作转为对AST对象树的操作。
既然要操作AST，那就要找到对应的AST，这就需要遍历。
怎么遍历呢？
AST不就是树嘛，而树的遍历就深度优先和广度优先两种，而这里只能是深度优先。
那对于每个AST怎么遍历呢？
比如a+b这个BinaryExpression，需要遍历left、right属性
比如if(a===1){}这个IfStatement，需要遍历test、consequece属性：
这样，我们记录下每种AST怎么遍历，然后从根结点开始递归的遍历就可以了。
比如像这样：
因为是每种AST访问那些key，所以叫做visitorKeys。
遍历每种AST的时候，就从visitorKeys里面找，看看要遍历哪些属性，之后取出来递归遍历就行了。
这就是AST的遍历过程，有且只有这么一种。（你还能想出第二种么？）
当然，思路虽然只有一种，但还是有一些变形的：
比如把递归变成循环，因为AST如果过深，那递归层次就过深，可能栈溢出，所以可以加一个数组（作为栈）来记录接下来要遍历AST，这样就可以变成循环了。（reactfiber也是把递归变循环）
比如可以不把visitorKeys提出来，而是直接在代码里写死，这样虽然不如提出来更容易扩展，但是做一些针对部分AST的逻辑变更还是比较方便的。
说了这么多，但是你可能不信，那我们就上源码来看下babel、eslint、tsc、estraverse、postcss都是怎么遍历AST的。
各种编译工具的AST遍历的实现源码里面有很多无关的信息，我们重点看遍历的部分就好了：
eslinteslint的遍历过程比较标准，我们先来看下这个：
就是对每种AST都从visitorKeys中拿到遍历的属性keys，然后递归遍历每个key的值就行了，数组的话还要循环遍历每个元素。
和我们上面理清的思路一毛一样。
而且，在遍历之前可以调用enter回调函数，在遍历之后可以调用exit回调函数。
babelbabel也是一样的思路，通过visitorKeys记录每种AST怎么遍历，然后遍历的时候取出对应的keys来递归访问：
babel分为了两个方法，没啥实质区别，而且也有enter和exit两个阶段的回调。
estraverseestraverse是专门用于遍历AST的库，一般和esprima的parser配合。它的AST遍历和上面两个不太一样，就是把递归变成了循环。
看到我标出来的地方了么，和上面的是一样的，只不过这里不是递归了，而是把要遍历的AST放入数组，之后继续循环。
递归改循环的思路都是这样，加个数组（作为栈）记录路径就可以了。
typescripttypescript的遍历和上面的也不太一样，它没有抽离出visitorKeys的数据，而是写死在代码里对什么AST访问什么属性：
这种方式比较命令式，要把所有AST枚举一遍，而上面那种把visitorKeys抽离出来的方式是声明式的思想，逻辑可以复用。不知道为什么ts是这样写遍历逻辑的，可能好处就是可以对某一些遍历逻辑做修改吧。
postcsspostcss也稍微有点不同，它的所有key都是可遍历的，也就不需要visitorKeys，直接遍历所有的key就行。
而且postcss的node是有方法的，通过面向对象的方式来组织遍历的过程。
写法上有点区别，但遍历的思路没有变。
总结前端领域的编译工具有挺多的，它们都是基于AST，而操作AST就需要遍历来查找。
eslint、babel、estraverse、postcss、typescriptcompiler这些编译工具的遍历AST的实现我们都过了一遍，虽然有的用递归、有的用循环，有的是面向对象、有的是函数，有的是抽离visitorKeys、有的是写死在代码里，但思路都是一样的。
所以，我们来正式的下个结论：编译工具的遍历实现思路只有一种，就是找到每种AST的可遍历的keys，深度优先的遍历。
