ROSE 編譯器框架/AST 匹配
AST 匹配機制
- rose/src/midend/astMatching
以下文件位於以下檔案（但尚未完成，並且不會顯示在 doxygen 中）
- rose/src/midend/astMatching/AstMatching.docs
這些示例很好地概述了您可以使用匹配器執行的操作。請注意，它使用自己的解析器並實現了自己的規範語言來指定匹配表示式（具有許多不同的運算子）。匹配器是在 AST 迭代器之上實現的 - 因此，匹配器是迭代器的一個用例。
AstMatching 機制允許指定任意大的模式，以便在 AST 中的任何子樹上進行匹配。這些模式以字串形式指定，並且可以使用 AST 節點的型別名稱來指定 AST 模式。此外，還提供變數和一些運算子，以允許指定複雜的模式。也可以使用 '_' 忽略匹配中的子樹。二元運算子 '|' 允許將不同的匹配子表示式組合成一個表示式。變數用於指定儲存在匹配結果中的已匹配子樹的指標，以便使用者進一步處理。
在下面的示例中，我們匹配兩邊都有變數的賦值，例如 x=y，並將結果分配給變數 $R。
#include "rose.h"
#include "AstTerm.h"
#include "AstMatching.h"
AstMatching m;
MatchResult res=m.performMatching("$R=SgAssignOp(SgVarRef,SgVarRef)",astRoot);
其中 'astRoot' 是指向 AST 中某個節點的指標。AssignOp 和 SgVarRef 是 ROSE AST 節點的名稱，$R 是匹配器變數的名稱。
在上面的示例中，將匹配所有表示具有兩個變數作為運算元的賦值操作的子樹。美元符號表示變數。在上面的示例中，指向已匹配子樹的指標被分配給變數 $R。所有已匹配賦值的結果儲存在型別為 AstMatchingResult 的變數 res 中。匹配結果是一組對映，其中每個對映代表一次成功匹配的結果，幷包含變數名稱和指向相應 AST 子樹的指標對。
變數用作鍵來儲存/檢索結果中已匹配的子樹。可以隨意使用多個變數（鍵），並且支援兩種使用形式。變數以引導美元符號和任意數量的字母和下劃線（單個下劃線用作萬用字元）表示。可以使用變數賦值符號將指定模式的指標分配給變數。
例如，$R=SgAssignOp(SgVarRef,_,_) 與所有在左側具有變數並在右側具有某些表示式的賦值匹配。
或者，我們也可以使用 $R=SgAssignOp($X=SgVarRef,$Y=_) - 在這種情況下，我們還將指向已匹配變數節點的指標和指向 rhs 上表達式的指標儲存在匹配結果中。
對於表示式 $Y=_，我們也可以簡單地將其寫為 $Y 作為簡寫，因此我們也可以使用 $R=SgAssignOp($X=SgVarRef,$Y) 代替。不允許將變數分配給變數，例如 $Z=$Y。
也可以使用匹配表示式中的 '_' 指定忽略子樹進行匹配。例如，如果我們使用 SgAssignOp(_,_)，我們可以匹配 AST 中的所有賦值節點，但忽略表示 rhs 和 lhs 的 AST 的結構。
可以透過在匹配表示式中使用“null”顯式匹配空值。例如，$X=SgForStatement(_,_,_,_,null) 將匹配所有第五個引數為 0 的 SgForStatement 項。
在匹配表示式中放置運算子 '#' 允許從後續匹配中排除任意子樹，以便對匹配操作進行應用。即，標記的子樹不會被遍歷。例如，如果我們只想匹配最外層的 for 語句，而不是巢狀的 for 語句，我們可以使用
$FOR=SgForStatement(_,_,_,#_,..)
這僅匹配外部 for 語句，因為主體（第四個引數）被排除在應用匹配運算子之外。如果沒有 '#'，我們也會匹配內部迴圈。
此運算子可以在匹配表示式中使用，以指定可以跟隨任意數量的引數。例如，我們可以使用 SgBlock($First,..) 來匹配 SgBlock 中的第一條語句。由於 SgBlock 可以具有任意元數，因此在這方面非常有用。運算子 '..' 在指定節點的元數時最多隻能使用一次，但在匹配模式中可以任意多次使用，例如 SgBlock(SgForStatement($Cond,..),..) 是可以的，但 SgBlock(_,..,_,..) 是不行的。
此運算子允許組合多個匹配表示式。例如，“SgAddOp($L,$R)|SgSubOp($L,$R)”將匹配 SgAddOp 並將指向其兩個子節點的指標繫結到 $L 和 $R，或者它將匹配 SgSubOp。運算子 '|' 執行短路計算，因此，匹配是從左到右執行的，並且只要其中一個模式可以成功匹配，匹配就會停止。
- performMatching("$R=AssignOp(_,_)",astRoot);
Match all assignment operators in an AST.
- performMatching("$R=SgAssignOp(SgVarRefExp,SgIntVal)",astRoot);
Match all assignment operators with a variable on the lhs and an integer value on the rhs.
- performMatching("$FORROOT=SgForStatement(_,_,_,#_)",astRoot);
Match all outer most for loops, but no nested for-loops. The operator '#' ensures that the match expression is not applied on the AST representing the body of the for-statement (4th argument). The pointer to the root of the AST representing the for-loop is bound to $FORROOT.
- performMatching("$N=_(null)",astRoot);
Match all nodes with arity 1 and a single null value. The main purpose for such match-expressions is to perform consistency checks in the AST.
- performMatching("$N=SgInitializedName(null)",astRoot); // 預設ROSE AST中存在許多這樣的節點
Specifically match all SgInitializedName nodes with a null pointer.
變數可以巢狀在模式內部。如果不需要，頂級模式不需要變數。
- performMatching("SgForStatement($LoopCond,_,_,_)|SgWhile($LoopCond,_)|SgDoWhile(_,$LoopCond)",astRoot);
Match different Loop constructs and bind variable $LoopCond to the respective loop condition.
- performMatching("SgAssignOp(SgVarRef,SgAddOp($X,$Y))",astRoot)
Match assignments with a variable on the rhs and an add-operator on the rhs(root). The pointers to the sub-ASTs representing the lhs and rhs of the add-operator are bound to variables $X and $Y for each match in the AST:
- performMatching("$Func=SgFunctionCallExp($FuncRef,$Params)",astRoot)
Match all function calls and bind variable $Func to the root of each such expression, bind $FuncRef to the SgFunctionRefExp (which can be used to obtain the name) and $Params to the AST representing the parameters:
#include "AstTerm.h"
#include "AstMatching.h"
AstMatching m;
// match i++
MatchResult res=m.performMatching("SgForStatement(_,_,SgPlusPlusOp($I=SgVarRefExp),..)",forloop);
// match i++ or i==
// MatchResult res=m.performMatching("SgForStatement(_,_,SgPlusPlusOp($I=SgVarRefExp)|SgMinusMinusOp($I=SgVarRefExp),..)",forloop);
// cout<<res.size()<<endl;
for(MatchResult::iterator i=res.begin();i!=res.end();++i) {
// obtain the result:each variable is a map
SgVarRefExp* ivar = isSgVarRefExp( (*i)["$I"]);
cout<<"var:"<< ivar->unparseToString()<<endl;
}
通常，對於給定的子樹，不清楚應該使用哪種模式字串。在這種情況下，您可以先找到其根節點，並使用AstTerm::astTermWithNullValuesToString() 打印出一個模式字串。
#include "AstTerm.h"
// check if this is within auto kernel = ...;
SgStatement* stmt = SageInterface::getEnclosingStatement(exp);
AstMatching m;
MatchResult r =m.performMatching ("$L=SgVariableDeclaration", stmt);
for(MatchResult::iterator i=r.begin();i!=r.end();++i) {
SgVariableDeclaration* i1 = isSgVariableDeclaration((*i)["$L"]);
cout<< AstTerm::astTermWithNullValuesToString(i1)<<endl;
}
一些示例輸出可能如下所示
"SgAggregateInitializer(SgExprListExp(SgDesignatedInitializer(SgExprListExp(SgAdaOthersExp:others),SgAssignInitializer(SgAggregateInitializer(SgExprListExp(SgDesignatedInitializer(SgExprListExp(SgAdaOthersExp:others),SgAssignInitializer(SgLongDoubleVal:2.0))))))))"
請注意，您不應該直接複製貼上輸出字串作為匹配模式。您需要刪除表示式中的:value 部分。
例如：(SgLongDoubleVal:2.0) 應該變成 (SgLongDoubleVal)
有一個專門的翻譯器來轉儲輸入檔案的 AST 項
- exampleTranslators/defaultTranslator/astTermGenerator.C
結果收集在 std::list of std::maps 中。每個 map 代表 AST 中一個位置的一次成功匹配，幷包含所有繫結變數。可以使用名稱和隨機訪問運算子訪問變數。列表中的元素數量（= maps）對應於 AST 中匹配模式的數量。
typedef std::map<std::string,SgNode*> SingleMatchVarBindings; typedef std::list<SingleMatchVarBindings> MatchResult;
可以按如下方式訪問 AST 中匹配模式的指標
/* 1 */ AstMatching m;
/* 2 */ MatchResult res=m.performMatching("$R=SgInitializedName($X)",root);
/* 3 */ std::cout << "Number of matched patterns: " << r.size() << std::endl;
/* 4 */ for(MatchResult::iterator i=r.begin();i!=r.end();++i) {
/* 5 */ cout<<"Match expression variable $R:"<<isSgLocatedNode((*i)["R"])->unparseToString()<<endl;
/* 6 */ cout<<"Match expression variable $X:"<<isSgLocatedNode((*i)["R"])->unparseToString()<<endl;
/* 7 */ }
在第 1 行建立了 AstMatching 物件。在第 2 行，將匹配表示式和 AST 的根節點提供給匹配機制，並計算結果。匹配可以在任何感興趣的 AST 子樹上執行，方法是在開始匹配操作時讓 'root' 指向相應的 AST 子樹。在第 3 行列印匹配模式的數量。在第 4-7 行訪問變數 $R 變數 $X，並使用 unparseToString 函式解析相應的匹配 AST 子樹。匹配變數 $R 和 $X 的指標值引用成功匹配 AST 子樹的根節點。
以下是一個更詳細的程式碼示例，用於在整個 ROSE AST 上執行一次匹配操作，並使用迭代器列印所有匹配結果中的 map
#include "AstTerm.h"
#include "AstMatching.h"
// Fragment from the matcher_demo program
AstMatching m;
MatchResult r=m.performMatching("$R=SgInitializedName(_)",root);
// print result in readable form for demo purposes
std::cout << "Number of matched patterns: " << r.size() << std::endl;
// for each matched instance
for(MatchResult::iterator i=r.begin();i!=r.end();++i) {
std::cout << "MATCH: \n";
// obtain the map
SingleMatchVarBindings& dict=(*i);
SgNode* matched_op = dict["$R"] ; // retrieve the node by its key/variable
// Alternatively, iterate through all entries in the map.
// for each variable in the matched instance
for(SingleMatchVarBindings::iterator vars_iter=(*i).begin();vars_iter!=(*i).end();++vars_iter) {
SgNode* matchedTerm=(*vars_iter).second;
std::cout << " VAR: " << (*vars_iter).first << "=" << AstTerm::astTermWithNullValuesToString(matchedTerm) << " @" << matchedTerm << std::endl;
}
std::cout << std::endl;
}
變數 matchedTerm 被賦予指向與變數繫結的相應 ROSE AST 節點的指標。(*vars_iter).first 是呼叫 performMatching 時匹配表示式中使用的變數的名稱。在本例中，它們是 $R、$X 和 $Y。generateAstTerm 函式是一個輔助函式，用於以可讀的形式在 stdout 上列印 AST。它使用與匹配機制相同的 Ast::iterator_with_null 實現。
示例輸出
MATCH:
VAR: $R=SgInitializedName(null) @0x7f1f8914da00
MATCH:
VAR: $R=SgInitializedName(null) @0x7f1f8914db28
MATCH:
VAR: $R=SgInitializedName(SgAssignInitializer(SgIntVal)) @0x7f1f8914dc50
MATCH:
VAR: $R=SgInitializedName(null) @0x7f1f8914dd78
MATCH:
VAR: $R=SgInitializedName(null) @0x7f1f8914dea0
MATCH:
VAR: $R=SgInitializedName(SgAssignInitializer(SgIntVal)) @0x7f1f8914dfc8