跳转到内容

ROSE 编译器框架/AST 匹配

Add links
来自维基教科书，自由的教科书，为一个开放的世界

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
摘自 "https://wikibooks.cn/w/index.php?title=ROSE_Compiler_Framework/AST_Matching&oldid=3997139"
华夏公益教科书