Re: Tree Pattern Matching

Below I have included a collection of the responses I got thus far in my
search. Several ppl have asked me to summarize the information I got, so
here it goes.


On Tue, 16 Sep 1997, Norman Ramsey wrote:


> Check out Phil Wadler's chapter in Simon Peyton Jones's book on
> implementing functional languages.


From: Allyn Dimock <dimock@deas.harvard.edu>


Two products that you might want to look into are
TWIG -- a top down rewriter. Haven't found it yet
BURG -- a bottom up rewriter. http://www.cs.arizona.edu/people/todd/todd.html


From: Daniel Wang <danwang@CS.Princeton.EDU>
@Article{pettersson:1992:tpc,
    author = "Mikael Pettersson",
    title = "A Term Pattern-Match Compiler Inspired by Finite
                                  Automata Theory",
    journal = "Lecture Notes in Computer Science",
    volume = "641",
    pages = "258--??",
    year = "1992",
    coden = "LNCSD9",
    ISSN = "0302-9743",
    bibdate = "Mon May 13 11:46:24 MDT 1996",
    acknowledgement = "Nelson H. F. Beebe, Center for Scientific Computing,
                                  Department of Mathematics, University of Utah, Salt
                                  Lake City, UT 84112, USA, Tel: +1 801 581 5254, FAX: +1
                                  801 581 4148, e-mail: \path|beebe@math.utah.edu|, URL:
                                  \path|http://www.math.utah.edu/~beebe/|",
}


Is a good place to start, as it relatively recent and has a good
biblography. I have a copy of an updated version of the article that's a
chapter in Pettersson's thesis.


This is avalible online in
          ftp://ftp.research.bell-labs.com/dist/smlnj/release/93/93.doc.tar.Z


@unpublished{baudinet:1986:tpm,
Author = "Marianne Baudinet and David MacQueen",
Title = "Tree Pattern Matching for {ML}",
Note="Available from David MacQueen, AT\&T Bell Laboratories, 600 Mountain
Avenue, Murray, Hill, NJ 07974",
Year = 1986
}


There's also a chapter in
@Book{jones:1987:adts,
    author = "Simon L. {Peyton Jones}",
    title = "The Implementation of Functional Programming
                                  Languages",
    publisher = "Prentice-Hall",
    year = "1987",
}


Here's a slightly different take on tree pattern matching. It's the
foundation for systems like iburg.


@Article{hoffman:1982:pp,
    author = "Christoph M. Hoffman and Michael J. O'Donnell",
    title = "Pattern matching in trees",
    journal = "Journal of the ACM",
    volume = "29",
    number = "1",
    pages = "68--95",
    year = "1982",
}


From: Dick Wesseling <ftu@fi.ruu.nl


Refers to BURG and IBURG and to the master thesis of Todd Proebsting
(http://www.cs.arizona.edu/people/todd/todd.html). There are also pointers
to BURG and IBURG there.


From: Nathaniel McIntosh <mcintosh@cs.rice.edu>


This paper might be a good place to start:


@inproceedings{chase:87b,
                author = "David R. Chase",
                title = "An improvement to bottom-up tree pattern matching",
                booktitle = "Conference, Record of the 14th Annual ACM Symposium
on Principles of Programming Languages"
                pages = "168--177",
                address = "Munich, West Germany",
                month = January,
                year = 1987}


It's a bit dense, but it's one of the most interesting theory papers.


Try also:


@Article{FHP:92,
                Author = {C. Fraser and R. Henry and T. Proebsting},
                Title = {BURG -- Fast Optimal Instruction Selection and Tree
                                  Parsing},
                Journal = SIGPLAN,
                Volume = 27,
                Number = 4,
                Pages = {68-76},
                Month = Apr,
                Year = 1992}




I also found a web-page with some references to papers presented at
the Compiler Construction conference 1992, so I'm gonna look into that too.
In fact, it appears someone from my group (H. Corporaal) also presented a
paper there, so he'll probably has all the others too. I'll ask him.
http://www.informatik.uni-trier.de/~ley/db/conf/cc/cc92.html


Maarten Boekhold




_____________________________________________________________________________
| Maarten Boekhold, Faculty of Electrical Engineering TU Delft, NL |
| Computer Architecture and Digital Technique section |
| M.Boekhold@et.tudelft.nl |
-----------------------------------------------------------------------------
--

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