matching ASTs

Robert Metzger <metzger@rsn.hp.com>
19 Oct 2000 14:29:59 -0400

          From comp.compilers

Related articles
matching ASTs compilers@al-got-rhythm.net (J Alan Brogan) (2000-10-12)
Re: matching ASTs cfc@world.std.com (Chris F Clark) (2000-10-15)
Re: matching ASTs plakal@cs.wisc.edu (2000-10-15)
Re: matching ASTs eballen1@uswest.net (Bruce Ediger) (2000-10-15)
Re: matching ASTs lindig@eecs.harvard.edu (Christian Lindig) (2000-10-18)
Re: matching ASTs idbaxter@semdesigns.com (Ira D. Baxter) (2000-10-19)
matching ASTs metzger@rsn.hp.com (Robert Metzger) (2000-10-19)
| List of all articles for this month |

From: Robert Metzger <metzger@rsn.hp.com>
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
"similar".


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.