traversing an ast having complex conditional expression to generate linq expression

Question

I'm using Irony.net for generating a parse tree out of the source. Essentially I'm using ExpressionEvaluatorGrammer like grammer for binary expressions (arithmetic, relational and logical/conditional). I want to convert the resultant parse tree into Linq expression by traversing it. However, the tree does not seem to have a formation directly convertable to linq conditional expression. Hypothetical example of such an expression:

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

generates (pseudo xml tree for brevity):

<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>

In the tree above, the arithmetic expression (4 - 1) becomes the right expression to the && logical operation as the parent node closes after it. In the ideal world, it should have been a left expression of the nodes representing "== 3".

How do you traverse such a tree to generate a proper and operation? Or, is there a way to generate the tree in the form I desire?

Edit: here's the grammer (partial) definition. I have taken it from ExpressionEvaluatorGrammer that comes with Irony.interpreter.

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

Assuming the operator precedence is correct, you should walk the tree recursively using the Visitor Pattern, returning an Expression at each level:

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();
}

Now that you have the Visit structure, you simply write each specific visitor to use your main 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

You cannot fix this by traversing the tree in a magical/special way. Your parser is incorrect! Probably, it is just misconfigured. You absolutely need to get the correct tree from it in order to process it further.

Probably you have wrong operator precedence rules in it. It looks like it, at least. Try adding parenthesis to see if it fixed up the tree.