Re: matching ASTs

J Alan Brogan <compilers@al-got-rhythm.net> 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:


@InProceedings{crew/97/astlog,
    author = "Roger F. Crew",
    title = "{ASTLOG}: {A} Language for Examining Abstract Syntax
                                  Trees",
    booktitle = "Proc.~of the Conference on Domain-Specific Languages",
    pages = "229--242",
    year = "1997",
    url = "http://research.microsoft.com/~rfc/astlog/",
    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
lindig@eecs.harvard.edu 33 Oxford St, MD 242, Cambridge MA 02138
phone: +1 (617) 496-7157 http://www.eecs.harvard.edu/~lindig/

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