Thursday, October 12, 2006 1:09 PM
bart
DynCalc - Dynamic compilation illustrated - Part 2: Building an expression tree
Introduction
Time for some new dynamic compilation adventures. In the previous part we took a look at the infix to postfix transformation. As an example the expression ((1+2)+3)*2-8/4 gets translated into 1 2 Add 3 Add 2 Mul 8 4 Div Sub. Today, we'll translate this postfix notation into an expression tree.
Why expression trees?
You might wonder why we need to translate this into an expression tree first (which will be covered in this post). The postfix representation is already well-suited for translation to IL. Execution then would look like this:
Div
Add Add Mul 4 Sub
2 3 2 8 2 2
1 3 3 6 6 12 12 12 12 10
I agree we could simplify things, but expression trees play a prominent role in compiler techniques. More specifically, follow-up posts will travel you to the world of expression trees in C# 3.0 and LINQ, yielding to dynamic compilation of query expressions into some target domain language. I'm still working on this, so have a bit patience for this to appear online :-).
The code Right, we have the postfix expression, time to transform it into a tree representation. There's one method that does all the work:
static TreeNode ToTree(Queue<MathOpOrVal> q)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (MathOpOrVal mv in q)
{
if (mv.Value != null)
stack.Push(new TreeNode(mv.Value.Value));
else
{
TreeNode right = stack.Pop();
TreeNode left = stack.Pop();
stack.Push(new TreeNode(mv.Op.Value, left, right));
}
}
return stack.Pop();
}
TreeNode ToTree(Queue<MathOpOrVal> q)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (MathOpOrVal mv in q)
{
if (mv.Value != null)
stack.Push(new TreeNode(mv.Value.Value));
else
{
TreeNode right = stack.Pop();
TreeNode left = stack.Pop();
stack.Push(new TreeNode(mv.Op.Value, left, right));
}
}
return stack.Pop();
} Now, we're using a stack to build the tree bit by bit. When the algorithm completes, the top node of the stack will be the root node of the expression tree. To illustrate this, consider the following:
Input 1 2 Add 3 Add 2
Stack 1 2 Add(1,2) 3 Add(Add(1,2),3) 2
1 Add(1,2) Add(Add(1,2),3)
I guess you can imagine the rest yourself. Just for completeness, here's the code for the TreeNode class:
internal class TreeNode
{
public TreeNode(MathOp op, TreeNode left, TreeNode right)
{
Op = op;
Left = left;
Right = right;
}
public TreeNode(int value)
{
Value = value;
}
public MathOp? Op;
public TreeNode Left;
public TreeNode Right;
public int? Value;
}
internal class TreeNode
{
public TreeNode(MathOp op, TreeNode left, TreeNode right)
{
Op = op;
Left = left;
Right = right;
}
public TreeNode(int value)
{
Value = value;
}
public MathOp? Op;
public TreeNode Left;
public TreeNode Right;
public int? Value;
} Of course we create some helper methods to visualize the result:
static void Print(TreeNode tree)
{
PrintTree(tree, "");
}
static void PrintTree(TreeNode tree, string spacing)
{
if (tree.Op != null)
{
Console.WriteLine(spacing + "+" + tree.Op);
PrintTree(tree.Left, spacing + " ");
PrintTree(tree.Right, spacing + " ");
}
else
Console.WriteLine(spacing + tree.Value);
}
static void Print(TreeNode tree)
{
PrintTree(tree, "");
}
static void PrintTree(TreeNode tree, string spacing)
{
if (tree.Op != null)
{
Console.WriteLine(spacing + "+" + tree.Op);
PrintTree(tree.Left, spacing + " ");
PrintTree(tree.Right, spacing + " ");
}
else
Console.WriteLine(spacing + tree.Value);
} This is a very simple recursive tree printer. It should print something like this with our example:
+Sub
+Mul
+Add
+Add
1
2
3
2
+Div
8
4
So, the result is the subtraction of a left part and a right part. The left part on its turn is a multiplication of ... Etc. To translate this into code, we'll have to generate code that traverses the tree depth-first to calculate the expression step-by-step, like this:
+Sub +Sub +Sub +Sub +Sub 10
+Mul +Mul +Mul 12 12
+Add +Add 6 +Div 2
+Add 3 2 8
1 3 +Div 4
2 2 8
3 +Div 4
2 8
+Div 4
8
4
But that's to be covered in the next post. Have fun!
Right, we have the postfix expression, time to transform it into a tree representation. There's one method that does all the work:
static TreeNode ToTree(Queue<MathOpOrVal> q)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (MathOpOrVal mv in q)
{
if (mv.Value != null)
stack.Push(new TreeNode(mv.Value.Value));
else
{
TreeNode right = stack.Pop();
TreeNode left = stack.Pop();
stack.Push(new TreeNode(mv.Op.Value, left, right));
}
}
return stack.Pop();
}
TreeNode ToTree(Queue<MathOpOrVal> q)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (MathOpOrVal mv in q)
{
if (mv.Value != null)
stack.Push(new TreeNode(mv.Value.Value));
else
{
TreeNode right = stack.Pop();
TreeNode left = stack.Pop();
stack.Push(new TreeNode(mv.Op.Value, left, right));
}
}
return stack.Pop();
} Now, we're using a stack to build the tree bit by bit. When the algorithm completes, the top node of the stack will be the root node of the expression tree. To illustrate this, consider the following:
Input 1 2 Add 3 Add 2
Stack 1 2 Add(1,2) 3 Add(Add(1,2),3) 2
1 Add(1,2) Add(Add(1,2),3)
I guess you can imagine the rest yourself. Just for completeness, here's the code for the TreeNode class:
internal class TreeNode
{
public TreeNode(MathOp op, TreeNode left, TreeNode right)
{
Op = op;
Left = left;
Right = right;
}
public TreeNode(int value)
{
Value = value;
}
public MathOp? Op;
public TreeNode Left;
public TreeNode Right;
public int? Value;
}
internal class TreeNode
{
public TreeNode(MathOp op, TreeNode left, TreeNode right)
{
Op = op;
Left = left;
Right = right;
}
public TreeNode(int value)
{
Value = value;
}
public MathOp? Op;
public TreeNode Left;
public TreeNode Right;
public int? Value;
} Of course we create some helper methods to visualize the result:
static void Print(TreeNode tree)
{
PrintTree(tree, "");
}
static void PrintTree(TreeNode tree, string spacing)
{
if (tree.Op != null)
{
Console.WriteLine(spacing + "+" + tree.Op);
PrintTree(tree.Left, spacing + " ");
PrintTree(tree.Right, spacing + " ");
}
else
Console.WriteLine(spacing + tree.Value);
}
static void Print(TreeNode tree)
{
PrintTree(tree, "");
}
static void PrintTree(TreeNode tree, string spacing)
{
if (tree.Op != null)
{
Console.WriteLine(spacing + "+" + tree.Op);
PrintTree(tree.Left, spacing + " ");
PrintTree(tree.Right, spacing + " ");
}
else
Console.WriteLine(spacing + tree.Value);
} This is a very simple recursive tree printer. It should print something like this with our example:
+Sub
+Mul
+Add
+Add
1
2
3
2
+Div
8
4
So, the result is the subtraction of a left part and a right part. The left part on its turn is a multiplication of ... Etc. To translate this into code, we'll have to generate code that traverses the tree depth-first to calculate the expression step-by-step, like this:
+Sub +Sub +Sub +Sub +Sub 10
+Mul +Mul +Mul 12 12
+Add +Add 6 +Div 2
+Add 3 2 8
1 3 +Div 4
2 2 8
3 +Div 4
2 8
+Div 4
8
4
But that's to be covered in the next post. Have fun!
Right, we have the postfix expression, time to transform it into a tree representation. There's one method that does all the work:
static TreeNode ToTree(Queue<MathOpOrVal> q)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (MathOpOrVal mv in q)
{
if (mv.Value != null)
stack.Push(new TreeNode(mv.Value.Value));
else
{
TreeNode right = stack.Pop();
TreeNode left = stack.Pop();
stack.Push(new TreeNode(mv.Op.Value, left, right));
}
}
return stack.Pop();
}
TreeNode ToTree(Queue<MathOpOrVal> q)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (MathOpOrVal mv in q)
{
if (mv.Value != null)
stack.Push(new TreeNode(mv.Value.Value));
else
{
TreeNode right = stack.Pop();
TreeNode left = stack.Pop();
stack.Push(new TreeNode(mv.Op.Value, left, right));
}
}
return stack.Pop();
} Now, we're using a stack to build the tree bit by bit. When the algorithm completes, the top node of the stack will be the root node of the expression tree. To illustrate this, consider the following:
Input 1 2 Add 3 Add 2
Stack 1 2 Add(1,2) 3 Add(Add(1,2),3) 2
1 Add(1,2) Add(Add(1,2),3)
I guess you can imagine the rest yourself. Just for completeness, here's the code for the TreeNode class:
internal class TreeNode
{
public TreeNode(MathOp op, TreeNode left, TreeNode right)
{
Op = op;
Left = left;
Right = right;
}
public TreeNode(int value)
{
Value = value;
}
public MathOp? Op;
public TreeNode Left;
public TreeNode Right;
public int? Value;
}
internal class TreeNode
{
public TreeNode(MathOp op, TreeNode left, TreeNode right)
{
Op = op;
Left = left;
Right = right;
}
public TreeNode(int value)
{
Value = value;
}
public MathOp? Op;
public TreeNode Left;
public TreeNode Right;
public int? Value;
} Of course we create some helper methods to visualize the result:
static void Print(TreeNode tree)
{
PrintTree(tree, "");
}
static void PrintTree(TreeNode tree, string spacing)
{
if (tree.Op != null)
{
Console.WriteLine(spacing + "+" + tree.Op);
PrintTree(tree.Left, spacing + " ");
PrintTree(tree.Right, spacing + " ");
}
else
Console.WriteLine(spacing + tree.Value);
}
static void Print(TreeNode tree)
{
PrintTree(tree, "");
}
static void PrintTree(TreeNode tree, string spacing)
{
if (tree.Op != null)
{
Console.WriteLine(spacing + "+" + tree.Op);
PrintTree(tree.Left, spacing + " ");
PrintTree(tree.Right, spacing + " ");
}
else
Console.WriteLine(spacing + tree.Value);
} This is a very simple recursive tree printer. It should print something like this with our example:
+Sub
+Mul
+Add
+Add
1
2
3
2
+Div
8
4
So, the result is the subtraction of a left part and a right part. The left part on its turn is a multiplication of ... Etc. To translate this into code, we'll have to generate code that traverses the tree depth-first to calculate the expression step-by-step, like this:
+Sub +Sub +Sub +Sub +Sub 10
+Mul +Mul +Mul 12 12
+Add +Add 6 +Div 2
+Add 3 2 8
1 3 +Div 4
2 2 8
3 +Div 4
2 8
+Div 4
8
4
But that's to be covered in the next post. Have fun!
Right, we have the postfix expression, time to transform it into a tree representation. There's one method that does all the work:
static TreeNode ToTree(Queue<MathOpOrVal> q)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (MathOpOrVal mv in q)
{
if (mv.Value != null)
stack.Push(new TreeNode(mv.Value.Value));
else
{
TreeNode right = stack.Pop();
TreeNode left = stack.Pop();
stack.Push(new TreeNode(mv.Op.Value, left, right));
}
}
return stack.Pop();
}
TreeNode ToTree(Queue<MathOpOrVal> q)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (MathOpOrVal mv in q)
{
if (mv.Value != null)
stack.Push(new TreeNode(mv.Value.Value));
else
{
TreeNode right = stack.Pop();
TreeNode left = stack.Pop();
stack.Push(new TreeNode(mv.Op.Value, left, right));
}
}
return stack.Pop();
} Now, we're using a stack to build the tree bit by bit. When the algorithm completes, the top node of the stack will be the root node of the expression tree. To illustrate this, consider the following:
Input 1 2 Add 3 Add 2
Stack 1 2 Add(1,2) 3 Add(Add(1,2),3) 2
1 Add(1,2) Add(Add(1,2),3)
I guess you can imagine the rest yourself. Just for completeness, here's the code for the TreeNode class:
internal class TreeNode
{
public TreeNode(MathOp op, TreeNode left, TreeNode right)
{
Op = op;
Left = left;
Right = right;
}
public TreeNode(int value)
{
Value = value;
}
public MathOp? Op;
public TreeNode Left;
public TreeNode Right;
public int? Value;
}
internal class TreeNode
{
public TreeNode(MathOp op, TreeNode left, TreeNode right)
{
Op = op;
Left = left;
Right = right;
}
public TreeNode(int value)
{
Value = value;
}
public MathOp? Op;
public TreeNode Left;
public TreeNode Right;
public int? Value;
} Of course we create some helper methods to visualize the result:
static void Print(TreeNode tree)
{
PrintTree(tree, "");
}
static void PrintTree(TreeNode tree, string spacing)
{
if (tree.Op != null)
{
Console.WriteLine(spacing + "+" + tree.Op);
PrintTree(tree.Left, spacing + " ");
PrintTree(tree.Right, spacing + " ");
}
else
Console.WriteLine(spacing + tree.Value);
}
static void Print(TreeNode tree)
{
PrintTree(tree, "");
}
static void PrintTree(TreeNode tree, string spacing)
{
if (tree.Op != null)
{
Console.WriteLine(spacing + "+" + tree.Op);
PrintTree(tree.Left, spacing + " ");
PrintTree(tree.Right, spacing + " ");
}
else
Console.WriteLine(spacing + tree.Value);
} This is a very simple recursive tree printer. It should print something like this with our example:
+Sub
+Mul
+Add
+Add
1
2
3
2
+Div
8
4
So, the result is the subtraction of a left part and a right part. The left part on its turn is a multiplication of ... Etc. To translate this into code, we'll have to generate code that traverses the tree depth-first to calculate the expression step-by-step, like this:
+Sub +Sub +Sub +Sub +Sub 10
+Mul +Mul +Mul 12 12
+Add +Add 6 +Div 2
+Add 3 2 8
1 3 +Div 4
2 2 8
3 +Div 4
2 8
+Div 4
8
4
But that's to be covered in the next post. Have fun!
Del.icio.us |
Digg It |
Technorati |
Blinklist |
Furl |
reddit |
DotNetKicks
Filed under: .NET Framework v2.0, C# 2.0