Conference on Domain-Specific Languages, 1997
ASTLOG: A Language for Examining Abstract Syntax Trees
Roger F. Crew
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 in to 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 "insideout 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.
- View the full text of this paper in
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
- To become a USENIX Member, please see our Membership Information.