|matching ASTs email@example.com (J Alan Brogan) (2000-10-12)|
|Re: matching ASTs firstname.lastname@example.org (Chris F Clark) (2000-10-15)|
|Re: matching ASTs email@example.com (2000-10-15)|
|Re: matching ASTs firstname.lastname@example.org (Bruce Ediger) (2000-10-15)|
|Re: matching ASTs email@example.com (Christian Lindig) (2000-10-18)|
|Re: matching ASTs firstname.lastname@example.org (Ira D. Baxter) (2000-10-19)|
|matching ASTs email@example.com (Robert Metzger) (2000-10-19)|
|From:||Robert Metzger <firstname.lastname@example.org>|
|Date:||19 Oct 2000 14:29:59 -0400|
|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
Return to the
Search the comp.compilers archives again.