Re: matching ASTs

Christian Lindig <>
18 Oct 2000 23:48:20 -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: Christian Lindig <>
Newsgroups: comp.compilers
Date: 18 Oct 2000 23:48:20 -0400
Organization: Harvard University, Cambridge, Massachusetts
References: 00-10-095
Keywords: bibliography

J Alan Brogan <> wrote:

> 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.

Roger Crew has developed a language to do pattern-matching on ASTs;
might be interesting for you:

    author = "Roger F. Crew",
    title = "{ASTLOG}: {A} Language for Examining Abstract Syntax
    booktitle = "Proc.~of the Conference on Domain-Specific Languages",
    pages = "229--242",
    year = "1997",
    url = "",
    address = "Santa Barbara, USA",
    month = "oct",
    organization = "USENIX",
    publisher = "",
    note = "",
    annote = "We desired a facility for locating/analyzing syntactic
                                  artifacts in abstract syntax trees of C/C++ programs,
                                  similar to the facility grep or awk provides for
                                  locating artifacts at the lexical level. Prolog, with
                                  its implicit pattern-matching and backtracking
                                  capabilities, is a natural choice for such an
                                  application. We have developed a Prolog variant that
                                  avoids the overhead of translating the source syntactic
                                  structures into the form of a Prolog database; this is
                                  crucial to obtaining acceptable performance on large
                                  programs. An interpreter for this language has been
                                  implemented and used to find various kinds of syntactic
                                  bugs and other questionable constructs in real programs
                                  like Microsoft SQL server (450Klines) and Microsoft
                                  Word (2Mlines) in time comparable to the runtime of the
                                  actual compiler. The model in which terms are matched
                                  against an implicit current object, rather than simply
                                  proven against a database of facts, leads to a distinct
                                  ``inside-out functional'' programming style that is
                                  quite unlike typical Prolog, but one that is, in fact,
                                  well-suited to the examination of trees. Also, various
                                  second-order Prolog set-predicates may be implemented
                                  via manipulation of the current object, thus retaining
                                  an important feature without entailing that the
                                  database be dynamically extensible as the usual
                                  implementation does.",

-- Christian

Christian Lindig Harvard University - DEAS 33 Oxford St, MD 242, Cambridge MA 02138
phone: +1 (617) 496-7157

Post a followup to this message

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