作者：职业培训 时间： 2025-01-01 18:38:24 阅读：250

作为前端，我们会用很多编译工具：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遍历的实现

源码里面有很多无关的信息，我们重点看遍历的部分就好了：

eslint

eslint的遍历过程比较标准，我们先来看下这个：

就是对每种AST都从visitorKeys中拿到遍历的属性keys，然后递归遍历每个key的值就行了，数组的话还要循环遍历每个元素。

和我们上面理清的思路一毛一样。

而且，在遍历之前可以调用enter回调函数，在遍历之后可以调用exit回调函数。

babel

babel也是一样的思路，通过visitorKeys记录每种AST怎么遍历，然后遍历的时候取出对应的keys来递归访问：

babel分为了两个方法，没啥实质区别，而且也有enter和exit两个阶段的回调。

estraverse

estraverse是专门用于遍历AST的库，一般和esprima的parser配合。它的AST遍历和上面两个不太一样，就是把递归变成了循环。

看到我标出来的地方了么，和上面的是一样的，只不过这里不是递归了，而是把要遍历的AST放入数组，之后继续循环。

递归改循环的思路都是这样，加个数组（作为栈）记录路径就可以了。

typescript

typescript的遍历和上面的也不太一样，它没有抽离出visitorKeys的数据，而是写死在代码里对什么AST访问什么属性：

这种方式比较命令式，要把所有AST枚举一遍，而上面那种把visitorKeys抽离出来的方式是声明式的思想，逻辑可以复用。不知道为什么ts是这样写遍历逻辑的，可能好处就是可以对某一些遍历逻辑做修改吧。

postcss

postcss也稍微有点不同，它的所有key都是可遍历的，也就不需要visitorKeys，直接遍历所有的key就行。

而且postcss的node是有方法的，通过面向对象的方式来组织遍历的过程。

写法上有点区别，但遍历的思路没有变。

总结

前端领域的编译工具有挺多的，它们都是基于AST，而操作AST就需要遍历来查找。

eslint、babel、estraverse、postcss、typescriptcompiler这些编译工具的遍历AST的实现我们都过了一遍，虽然有的用递归、有的用循环，有的是面向对象、有的是函数，有的是抽离visitorKeys、有的是写死在代码里，但思路都是一样的。

所以，我们来正式的下个结论：编译工具的遍历实现思路只有一种，就是找到每种AST的可遍历的keys，深度优先的遍历。

本文地址： http://www.goggeous.com/20241127/1/71967

文章来源：天狐定制

版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。