遍历具有复杂条件表达式的ast以生成linq表达式

Question

我使用Irony.net从源代码中生成解析树。本质上，我使用的是ExpressionEvaluatorGrammer，就像语法一样，用于二进制表达式(算术表达式、关系表达式和逻辑/条件表达式)。我想通过遍历将生成的解析树转换为Linq表达式。但是，该树似乎没有可直接转换为linq条件表达式的形式。这样一个表达式的假设示例：

1 == 1 && 4 - 1 == 3

生成(为简洁起见，生成伪xml树)：

<binary>
  <binary>
    <binary>
      <literal>1</literal>
      <op>==</op>
      <literal>1</literal>
    </binary>
    <op>&&</op>
    <binary>
      <literal>4</literal>
      <op>-</op>
      <literal>1</literal>
    </binary>
  </binary>
  <op>==</op>
  <literal>3</literal>
</binary>

在上面的树中，算术表达式(4 - 1)成为&&逻辑操作的正确表达式，因为父节点在它之后关闭。在理想情况下，它应该是表示"== 3“的节点的左侧表达式。

如何遍历这样的树以生成正确的and操作？或者，有没有办法生成我想要的形式的树？

编辑:这是语法(部分)定义。我是从Irony.interpreter自带的ExpressionEvaluatorGrammer上拿的。

RegisterOperators(15, "&", "&&", "|", "||");
RegisterOperators(20, "==", "<", "<=", ">", ">=", "!=");
RegisterOperators(30, "+", "-");
RegisterOperators(40, "*", "/");
Expr.Rule = Term
Term.Rule = number | ParExpr | stringLit | FunctionCall | identifier | MemberAccess | IndexedAccess;
ParExpr.Rule = "(" + Expr + ")";
BinExpr.Rule = Expr + BinOp + Expr;
BinOp.Rule = ToTerm("+") | "-" | "*" | "/" | "**" | "==" | "<" | "<=" | ">" | ">=" | "!=" | "&&" | "||" | "&" | "|";

Answer 1

假设操作符的优先级是正确的，您应该使用访问者模式递归遍历树，在每个级别返回一个Expression：

XName xBinary = "binary";
XName xLiteral = "literal";
Expression Visit(XElement elt)
{
    if (elt.Name == xBinary)
    {
        return VisitBinary(elt);
    }
    else if (elt.Name == xLiteral)
    {
        return VisitLiteral(elt);
    } // ...

    throw new NotSupportedException();
}

现在您有了Visit结构，您只需编写每个特定的访问器来使用您的主Visit

Expression VisitLiteral(XElement elt)
{
    Debug.Assert(elt.Name == xLiteral);
    return Expression.Constant((int)elt);
}

Expression VisitBinary(XElement elt)
{
    Debug.Assert(elt.Name == xBinary);
    Debug.Assert(elt.Elements().Count() >= 3);

    var lhs = elt.Elements().ElementAt(0);
    var op = elt.Elements().ElementAt(1);
    var rhs = elt.Elements().ElementAt(2);

    switch((string)op)
    {
    case "+":
        // by chaining LHS and RHS to Visit we allow the tree to be constructed
        // properly as Visit performs the per-element dispatch
        return Expression.Add(Visit(lhs), Visit(rhs));
    case "&&":
        return Expression.AndAlso(Visit(lhs), Visit(rhs));
    default:
        throw new NotSupportedException();
    }
}

Answer 2

你不能通过神奇/特殊的方式遍历树来解决这个问题。您的解析器不正确！可能，它只是配置错误。为了进一步处理它，您绝对需要从中获得正确的树。

可能您在其中有错误的运算符优先规则。至少看起来是这样。尝试添加括号，看看它是否修复了树。