如何用 Python 编写抽象语法树的访问者模式?

问题描述

我的同事建议我编写一个访问者模式来导航 AST.谁能告诉我更多我将如何开始写它?

My collegue suggested me to write a visitor pattern to navigate the AST. Can anyone tell me more how would I start writing it?

据我了解,AST 中的每个节点都会有 visit() 方法(?),它会以某种方式被调用(从哪里?).我的理解到此结束.

As far as I understand, each Node in AST would have visit() method (?) that would somehow get called (from where?). That about concludes my understanding.

为了简化一切,假设我有节点 RootExpressionNumberOp 并且树看起来像这样:

To simplify everything, suppose I have nodes Root, Expression, Number, Op and the tree looks like this:

       Root
        |
       Op(+)
      /   
     /     
 Number(5)  
             Op(*)
             /   
            /     
           /       
       Number(2)   Number(444)

谁能想到访问者模式将如何访问这棵树以产生输出:

Can anyone think of how the visitor pattern would visit this tree to produce output:

 5 + 2 * 444

谢谢,博达·赛多.


解决方案

维基百科对 有很好的概述访问者模式是如何工作的,尽管他们使用的示例实现是在 Java 中.不过,您可以轻松地将其移植到 Python 中,不是吗?

Wikipedia has a great overview of how the Visitor pattern works, although the sample implementation that they use is in Java. You can easily port that to Python, though, no?

基本上,您希望实现一种双重分派的机制.AST 中的每个节点都需要实现 accept() 方法(不是 visit() 方法).该方法将访问者对象作为参数.在此 accept() 方法的实现中,您调用访问者对象的 visit() 方法(每种 AST 节点类型都有一个;在 Java 中,您'将使用参数重载,在 Python 中我想你可以使用不同的 visit_*() 方法).然后将使用正确的节点类型作为参数分派正确的访问者.

Basically, you want to implement a mechanism for double dispatch. Each node in your AST would need to implement an accept() method (NOT a visit() method). The method takes, as an argument, a visitor object. In the implementation of this accept() method, you call a visit() method of the visitor object (there will be one for each AST node type; in Java, you'll use parameter overloading, in Python I suppose you can use different visit_*() methods). The correct visitor will then be dispatched with the correct Node type as argument.

相关文章