compare 2 Asts

[Alexander Dymo]

On Thursday 24 January 2008 23:47:00 Andreas Pakulat wrote:
> I'm having 2 AST's (if that doesn't mean anything to you, you can stop
> reading now ;) and I'd like to compare them. Basically walk them in a
> synchronous way and on each step compare a couple of values of the
> current node.

If 2 AST's are guaranteed to have the same structure (i.e. nodes/children of 
each node, etc.) then I can think of using 2 stacks to traverse the trees. 
Below is ruby-alike pseudocode;) and I haven't really checked if that works:

stack1 = [root1]
stack2 = [root2]

while !stack1.empty?
  node1 = stack1.pop
  node2 = stack2.pop

  compare_values node1, node2

  stack1.push node1.children
  stack2.push node2.children
end