Rascal 中的模式匹配 AST 节点

Question

我有以下 AST 定义：

data Exp =
    app(Exp fun, Exp body)
    | var(str name)
    | nat(int nat)
    | func(list[str] formal, Exp body)
    | cond(Exp cond, Exp then, list[tuple[Exp,Exp]] elifs, Exp otherwise)
    | let(list[str] vars, list[Exp] exps, Exp body)
    | seq(Exp lhs, Exp rhs)
    | mul(Exp lhs, Exp rhs)
    | div(Exp lhs, Exp rhs)
    | md(Exp lhs, Exp rhs)
    | add(Exp lhs, Exp rhs)
    | sub(Exp lhs, Exp rhs)
    | eq(Exp lhs, Exp rhs)
    | gt(Exp lhs, Exp rhs)
    | lt(Exp lhs, Exp rhs)
    | geq(Exp lhs, Exp rhs)
    | leq(Exp lhs, Exp rhs)
    ;

并且我试图在 switch 语句中匹配树的一个节点，以便我可以访问每个子节点。我尝试过的是：

private str synthesise_f(Core::AST::Exp exp) {
    switch (exp) {
        case \Exp(_, _): {
            println("EXP_,_!");
        }
    }
}

和

private str synthesise_f(Core::AST::Exp exp) {
    switch (exp) {
        case /Exp(_, _): {
            println("EXP_,_!");
        }
    }
}

和

private str synthesise_f(Core::AST::Exp exp) {
    switch (exp) {
        case "Exp"(_, _): {
            println("EXP_,_!");
        }
    }
}

和 private str synthesise_f(Core::AST::Exp exp) { 案例 \adt(,): { println("EXP_!"); } }

最后一个确实有效...但不允许我访问节点的子节点。如果我打印出 switch 语句中使用的 exp 我得到：

seq(var("x"),var("y"))

（删除评论和位置）

我想知道如何匹配这些节点然后访问它们的子节点。

谢谢！

Answer 1

执行此操作的标准方法是匹配实际的构造函数名称。例如，您可以编写如下 switch 语句：

switch(exp) {
    case app(f,b) : {
        // code to handle case app(Exp fun, Exp body) goes here
    }

    case var(n) : {
        // code to handle case var(str name) goes here
    }

    // etc...
}

然后每个定义的构造函数都有一个案例。另一种选择是编写单独的函数来处理不同的情况，这在某些情况下可以更清晰（并且更具可扩展性，因为您可以添加更多函数）：

Result eval(app(Exp fun, Exp body), Env env) {
    // evaluate app
}

Result eval(var(str name), Env env) {
    // evaluate var
}

不同的情况是相互递归的。如果您不想传递共享状态，我建议嵌套函数而不是创建全局变量：

Result evalProgram(Exp p) {
    Env env = createEnv();

    Result eval(app(Exp fun, Exp body)) {
        // evaluate app
    }

    Result eval(var(str name)) {
        // evaluate var
    }

    // The other functions...

    Result res = eval(p);
    return res;
}

Answer 2

好吧，我找到了解决办法。我所做的是创建一个基本案例节点（在本例中为 \str()）节点，然后我匹配任何其他泛型类型。所以，这应该捕捉到基本情况，如果不是，那意味着它必须是我可以处理的其他类型的 Exp 。代码：

private str synthesise_f(Core::AST::Exp exp) {
    switch (exp) {
        case \var(_): {
            doSomethingWithStr();
        }
        case &T _(Exp e0): {
            doSomethingWith1Exp();
        }
        case &T _(Exp e0, Exp e1): {
            doSomethingWith2Exps();
        }
    }
    return ret;
}

Rascal 中的模式匹配 AST 节点

Pattern matching AST nodes in Rascal

pattern-matching

abstract-syntax-tree

rascal