Abstract Syntax Tree

Are there any good algorithms to find out whether two abstract syntax
trees are equal or not. Any rules which will increase the chances of
getting more equality among ASTs which are semantically the same but
syntactically different. Any algorithms to combine the ASTs of two
parsed inputs. Any algorithm to find whether an AST is a sub AST of
another AST.
[Assuming you have your list of semantic equivalents firmly in hand
(which isn't trivial, e.g., people hate it when you treat floating
point arithmetic as associative) I'd try rewriting trees into a
canonical form based on equivalences, then look for common subtrees.
I also recall that there are some pretty good techinques for detecting
common subexpressions as you build your tree so you get a DAG rather
than a tree. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.