matching ASTs

Robert Metzger <>
19 Oct 2000 14:29:59 -0400

          From comp.compilers

Related articles
matching ASTs (J Alan Brogan) (2000-10-12)
Re: matching ASTs (Chris F Clark) (2000-10-15)
Re: matching ASTs (2000-10-15)
Re: matching ASTs (Bruce Ediger) (2000-10-15)
Re: matching ASTs (Christian Lindig) (2000-10-18)
Re: matching ASTs (Ira D. Baxter) (2000-10-19)
matching ASTs (Robert Metzger) (2000-10-19)
| List of all articles for this month |

From: Robert Metzger <>
Newsgroups: comp.compilers
Date: 19 Oct 2000 14:29:59 -0400
Organization: Compilers Central
Keywords: tools, analysis
Article: 17915 of comp.compilers

>Can anyone give me any help in the matching of syntax trees - how to find
>out whether two such trees are "similar", and what "similar" might mean.
>Also - any references to work on the idea of canonical form of source code?
>Context: The idea (for a college project) is to try to match example
>source code (a "query") with some standard examples of known
>algorithms. I figure I should reduce the query code to some canonical
>form, then see which of the standard examples it is closest to.

Have a look at "Automatic Algorithm Recognition and Replacement:
A New Approach to Program Optimization" - R. Metzger and Z. Wen,
MIT Press, 2000.

The following chapters are most relevant to your problem:
5. Internal Program Representation
6. Converting to a Canonical Form
7. Matching Subprograms and Patterns
In Section 13.2 Future Research, we explain a couple of ways to use our
work to perform partial matches, which I believe is what you mean by

One of the unique aspects of the book is the use of trees as data
structures throughout. /Bob

Post a followup to this message

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