每個編程的人都學習過樹遍歷算法，但是AST的遍歷并不是開始想象的那么簡單。有幾個因素會影響遍歷算法：1）是否擁有節點的源碼；2）是否子節點的訪問方式是統一的；3）ast是homogeneous或heterogeneous；4）遍歷的過程中是否需要修改ast；5）以何種順序呢遍歷。這一章會討論常用的四個ast遍歷模式。

• Pattern 12, Embedded Heterogeneous Tree Walker, AST的node類包含了對應的訪問方法，后者執行嵌入的操作，并訪問所有的子節點。這種模式將訪問邏輯遍布所有的節點類，比較簡單直接，但是缺乏靈活性；
• Pattern 13, External Tree Visitor, 一個獨立于AST存在的Visitor類，很靈活，但是手動編寫很復雜；
• Pattern 14, Tree Grammar, 通過一個語法來描述AST的結構，就像用語法來描述語言一樣，這樣可以通過工具來生成Visitor代碼。
• Pattern 15, Tree Pattern Matcher, 該模式不通過語法描述整個AST，而是針對某些我們關注的subtree。與前面的模式不一樣的是，該模式不關注如何訪問整個AST，只關注尋找符合條件的子樹

AST訪問順序

我們說“訪問“一顆樹，意思是我對樹中的節點執行某些操作，因此訪問節點的順序是非常重要的，這直接影響了執行操作的順序。與一般的樹結構一樣，存在前序、中序、后序3種遍歷順序。

對AST訪問來說，情況稍微復雜一點，我們采用一種叫做depth-first search的算法，如果算法到達一個節點t，表示我們discover該節點，等到對t的訪問、處理結束，表示我們finished該節點。

對某種的的訪問機制來說，discover節點的順序是固定的，但是會產生不同的遍歷效果，取決與將相關操作放在walk()方法的哪個位置。
以表達式1+2+3為例，節點的訪問順序如下：

左側的圖描述了節點的discover和finish順序，右側圖種的星指出了操作可能執行的時機。如果所有的操作發生在discover的時候，那么相當于前序遍歷；如果所有的操作發生在兩個子節點之間，相當與中序遍歷；如果所有的操作發生在finish的時候，相當于后序遍歷。

Pattern 12 Embedded Heterogeneous Tree Walker

每中節點類型增加一個訪問方法，遞歸調用

public void walk() {?preorder-action? left.walk(); ?inorder-action? right.walk();?postorder-action? }

Pattern 13, External Tree Visitor

<b》將上面嵌入式的訪問代碼，抽取出來放入一個獨立的類里面
第一種實現適合heterogeneous tree，依賴傳統的double-dispatcher設計模式，每個節點類型添加一個方法來dispatch自身的訪問到合適的visotor方法。

/** A generic heterogeneous tree node used in our vector math trees */ public abstract class Node {public abstract void visit(Visitor visitor); // dispatcher }

節點子類的visit方法實現基本是一樣的:public void visit(VecMathVisitor visitor) { visitor.visit(this); }。
Visitor的實現如下：

public interface VecMathVisitor { void visit(AssignNode n); void visit(PrintNode n);void visit(StatListNode n);void visit(VarNode n);void visit(AddNode n);void visit(DotProductNode n);void visit(IntNode n);void visit(MultNode n);void visit(VectorNode n); }

visitor的節點的visit方法也是遞歸形式：

public void visit(AssignNode n) {n.id.visit(this); System.out.print("=" ); n.value.visit(this); System.out.println(); }

第二種方式通過node的token類型來分別執行訪問操作。

public class Visitor {public void print(ExprNode n) {switch ( n.token.type ) { // switch on token typecase Token.PLUS : print((AddNode)n); break;case Token.INT : print((IntNode)n); break; default : ?error-unhandled-node-type?} public void print(AddNode n) {print(n.left); // walk left child System.out.print("+"); // print operatorprint(n.right); // walk right child}public void print(IntNode n) {...} }

這個模式依據節點類型來執行不同的訪問操作，只要節點能夠提供type信息即可。

Pattern 14，Tree Grammar

描述AST節點樹結構的語法，在前面的Parser語法里面也有涉及，通過Tree Grammar來生成的visitor，與Pattern 13具備的能力一致，更加緊湊。
下面是Tree Grammar的一個片段：

expr: ^('+' expr {print("+");} expr)| ^('*' expr {print("*");} expr)| ^('.' expr {print(".");} expr)| ^(VEC {print("[");} expr ({print(", ");} expr)* {print("]");})| INT {print($INT.text);}| ID {print($ID.text);};

里面嵌入了操作代碼，可以控制這些代碼的插入位置來達到PreOrder，InOrder，PostOrder的效果。

通過Tree Grammar來訪問AST的過程，類似通過語言Grammar來解析語句，因此如果能先把AST轉換成線性結構，就可以使用傳統的Parser模式來生成訪問代碼；
在前面的章節說過如何通過文本來表示樹結構，表達式1+2可以表示為(+ 1 2)，將括號替換成特殊的token DOWN和UP，得到序列 + DOWN 1 2 UP。DOWN和UP模擬了tree訪問的移動操作。
對上面的Tree Grammar，生成的訪問代碼類似：

void expr() { // match an expression subtreeif ( LA(1)==Token.PLUS ) { // if next token is +match(Token.PLUS);match(DOWN); // simulate down movementexpr();expr();match(UP); // simulate up movement}... }

因此Tree Grammar，不是基于Node類型來執行操作，而是基于某種子樹模式來執行操作。

Tree Grammar同時定義了AST有效的結構，運行基于Tree Grammar的visitor，可以在運行時檢查AST的合法性。

Pattern 15， Tree Pattern Matcher

該模式用于掃描AST，當遇到感興趣的子樹模式的時候，執行操作或樹重寫。這種書重寫操作叫做”項重寫“(term rewriting)。

Pattern Matcher就好像文本匹配&改寫工具：awk、sed、perl等；Tree Grammar需要所有子樹對應的Grammar，而該模式只需要為關注的子樹模式指定Grammar，因而并不會發現ast的所有節點。

下面先看一個通過項重寫來簡化向量乘法的例子，我們想把向量乘法4*[0,5*0,3]簡化為[40,450,43]，進一步簡化”乘0"運算，得到[0,0,4*3]。

向量乘法的Grammar為:^('*' INT ^(VEC .+)),其中“.”表示任意的節點類型，轉換的規則定義如下：

scalarVectorMult : ^('*' INT ^(VEC (e+=.)+)) -> ^(VEC ^('*' INT $e)+)

“e”是引入的變量，通過e+=.成為包含向量元素的list.
簡化“乘零”運算的規則如下：

zeroX : ^('*' a=INT b=INT {$a.int==0}?) -> $a ; // 0*x -> 0 xZero : ^('*' a=INT b=INT {$b.int==0}?) -> $b ; // x*0 -> 0

{$a.int==0}?是語法謂詞，用來控制該匹配選項。
剩下的事情，就是指定上述規則的運用時機：

topdown : scalarVectorMult ; // tell ANTLR when to attempt which rule bottomup: zeroX | xZero ;

ANTLR采用depth-first搜尋，當dicovery一個node時候，執行topdown；finish一個node的時候執行bottomup。
有時候"項重寫”需要對AST多次執行Tree Pattern Matcher；比如將操作3+3重寫為3<<1，需要盡力3+3=》3*2》3<<1。

轉載于:https://www.cnblogs.com/longhuihu/p/4002264.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的《Language Implementation Patterns》之访问重写语法树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。