Python中的ast
模块允许多种遍历策略,我想了解的是,当选择一种特定的遍历方式时,在复杂性方面是否有显著的提高?
下面是两个例子:
- 示例1**
class GlobalVisitor(ast.NodeTransformer):
def generic_visit(self, tree):
for node in tree.body:
if isinstance(node, ast.Global):
*transform the ast*
- 示例2**
class GlobalVisitor(ast.NodeTransformer):
def visit_Global(self, tree):
*transform the ast*
在例1中,我重写了generic_visit方法,提供了我自己的遍历树的实现,但是这是通过访问树体中的每个节点来实现的,所以O(n)。
在例2中,我重写了visit_Global,这样就可以立即处理所有Global类型的节点,这就是ast
的工作原理。
我想知道,在示例2中,ast
是否可以通过重写visit_* field *(self,node)对我指定的节点进行即时的**O(1)访问,或者它只是在O(n)**中再次遍历树,在后台查找我需要的节点,从而稍微简化了我的工作?
1条答案
按热度按时间djmepvbi1#
@metatoaster、@user2357112和@rici提供的评论中的一些要点:
**1.**示例1完全错误。不应以所描述的方式遍历树为目标,因为在
tree.body
上迭代是完全错误的-tree.body
不是AST中每个节点的集合,它是Module
节点的一个属性,为模块中的顶级语句提供了节点列表。它将错过每一个重要的global
语句(因为除非出现非常奇怪的exec
情况,否则正确的global
语句永远不会是顶级的),它将在非模块节点输入时崩溃。如果要实现示例1的正确版本,只需使用ast.iter_child_nodes递归迭代即可。但是,请注意iter_child_nodes的名称是正确的。它不是iter_descendant_nodes。它只访问直接子代。递归遍历必须在对每个子代执行的操作中实现。
**2.**如果正确实现,两种方法是等效的,并且意味着递归遍历,但是覆盖visit_type(self,node)可以节省一些时间。在复杂性方面不会获得任何好处。
**3.**如果您想更改AST,则仅使用NodeTransformer,否则仅使用NodeVisitor。
最后,
ast
的文档似乎不够详尽,请参考this以获取更详细的文档。它有点过时(大约一年),但比原始的ast
更好地解释了一些基本原理。