使用訪問者模式的樹轉換

（免責聲明：這些例子是在構建編譯器的情況下給出的，但這個問題都是關於訪問者模式，並且不需要任何編譯器理論知識。）我正在通過Andrew Appel的現代編譯器在Java中的實現嘗試自學習編譯器理論（所以不，這不是家庭作業），而且我很難理解他希望如何使用Visitor模式將AST轉換爲IR樹。（注意：我在Python中這樣做，所以我也可以學習Python，這就是爲什麼即將到來的示例不在Java中。）據我所知，Visitor模式中的訪問和接受方法是無效設計的，所以，如果我有像使用訪問者模式的樹轉換

class PlusExp(Exp): 
    def __init__(self, exp_left, exp_right): 
     self.exp_left = exp_left 
     self.exp_right = exp_right 

    def accept(self, v): 
     v.visit_plus_exp(self)

然後我想能寫這樣

def visit_plus_exp(self, plus_exp): 
    return BINOP(BinOp.PLUS, 
       plus_exp.exp_left.accept(self), 
       plus_exp.exp_right.accept(self))

訪問者方法，將兩個子表達式轉換成紅外線，然後將它們與BINOP連接起來代表加號表達。當然，這是不可能的，除非我修改所有的接受函數來返回額外的信息，這也是一團糟，因爲有時你只是想要一個不返回任何東西的打印訪問者。然而，這篇文章堅持說訪問者是正確的路，而在Java中，這意味着它可以在沒有Python靈活性的情況下完成。我想不出任何不是非常難以理解的解決方案 - 任何人都可以點亮我的預期設計？

來源

2009-12-14 danben

哎我也想研究編譯器...那本書是研究編譯器的好書嗎？ – 2009-12-14 04:58:01

我認爲這是一個很好的介紹。它會引導您（而不是牽着你的手）執行一個編譯器，該編譯器將Java的一個子集作爲源併發布本地代碼。它還包含編譯器理論中的一系列高級主題。 – danben 2009-12-14 05:05:35

它是否包含代碼生成部分？ – 2009-12-14 05:15:50

SAX解析器是一種訪問者。爲避免向方法中添加返回值，您可以使用堆棧：

class Visitor { 
    Stack<Node> stack = new Stack<Node>(); 

// . . . 

    void visitPlus(PlusExp pe) { 
     pe.left.accept(this); 
     pe.right.accept(this); 
     Node b = stack.pop(); 
     Node a = stack.pop(); 
     stack.push(new BinOp(BinOp.PLUS, a, b)); 
    }

來源

2009-12-14 10:11:11

是的，這是我的非常感謝。 – danben 2009-12-14 15:28:10

警告：我沒有看過那本書。

該方法可能是無效類型的，但在Java中（本書是爲它編寫的）它也是對象的一部分。因此，訪問者方法可以在本地成員變量中構建結構，從而維護調用之間的必要上下文。

因此，例如，您的打印訪問者將附加到作爲成員變量保存的StringBuilder（或作爲創建訪問者對象的方法中的最終本地變量 - 這在Java中很常見，其中創建小型匿名內部類對象是一種常見習慣）。

在python中，您可以類似地讓visitor方法訪問非方法局部變量來維護上下文並構建結構。例如封閉物或小物體。

更新 - 的碼位小加入如實施例從下面的評論

result = new Node(); 
result.left.add(n1.accept(this)); 
result.right.add(n2.accept(this)); 
return result;

或

result = new Node(); 
this.nextLoc.add(result); 
this.nextLoc = result.left; 
n1.accept(this); 
this.nextLoc = result.right; 
n2.accept(this);

首先是漂亮（儘管仍然蹩腳評論例如代碼），但是第二如果你真的需要的話，會讓你保持無效的返回類型。

來源

2009-12-14 05:02:54

對不起，我想你誤會了 - 打印訪問者將非常容易構建，因爲每個節點的字符串表示可以在訪問節點時寫入輸出流。但是這裏的問題是，如果我們想要構建一棵樹，那麼當我們完成訪問一個孩子時，我們必須知道將哪個父節點附加到該父節點，以及該父節點的哪個屬性。 – danben 2009-12-14 05:07:45

這可能是我誤解你的，但在我看來，無論你是改變返回類型還是改變「下一個位置」目標引用，訪問者代碼總是設置下一個（更深）調用結果的位置。（請參閱添加回答的低質量代碼。） – 2009-12-14 07:45:08

正確 - 您最初沒有提及位置參考，但這更接近我想要的位置。我也想到了這一點，但我認爲這是有問題的（儘管我可能會誤解），因爲nextLoc只會指向我想要設置的位置，因此直接指定它並不會實際影響它指向的位置至。相反，我認爲（至少在Python中）可以通過構造和傳遞一個可以設置下一個位置的函數來實現，但在Java中這是不可能的。 – danben 2009-12-14 15:33:43

查看THIS編譯器的源代碼。我認爲這個人使用了訪問者模式。

來源

2009-12-14 05:18:06

是的，他的代碼只是實現訪問/接受函數以在需要時返回值。我可以做到這一點，並且它比Python更清潔，但是我想知道是否沒有按照規定使用Visitor做一些有意的方法。 – danben 2009-12-14 05:40:59

對不起（我不知道我能不能做得更好） – 2009-12-14 05:51:44

沒問題，謝謝你的試用 – danben 2009-12-14 06:38:03

使用訪問者模式的樹轉換

回答

相關問題