Abstract Syntax Tree

6 Nov 1998 16:00:11 -0500

          From comp.compilers

Related articles
Abstract Syntax Tree bharath3@my-dejanews.com (1998-11-06)
| List of all articles for this month |

From: bharath3@my-dejanews.com
Newsgroups: comp.compilers
Date: 6 Nov 1998 16:00:11 -0500
Organization: Deja News - The Leader in Internet Discussion
Keywords: AST, analysis, question

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]

Post a followup to this message

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