Matching templates against a tree - any ideas?

Greg Ewing greg.ewing at compaq.com
Wed Sep 29 16:58:06 EDT 1999


Ian Clarke wrote:
> 
> I
> came across the problem of trying to find an efficient method to match a
> tree, or subtree of that tree, against a template

You might like to take a look at the following. I examined it
briefly a while ago, and it seems to do very much what you are
after -- transforming one parse tree into another using a set of
transformation rules.

You might be able to use it as is, or get some insights from 
the tree-transformation part of its implementation.

URL:

	http://archie.inesc.pt/free-dir/free-S-1.299.html

Excerpt:

TXL [TXL: Tree Transformation Language]

     TXL is a language for performing source to source transformations
and is well suited for rapidly prototyping new languages and language
     processors. It has also been used to prototype specification
languages, command languages, and more traditional program
transformation tasks
     such as constant folding, type inference, source optimization and
reverse engineering. TXL takes as input an arbitrary context-free
grammar in
     extended BNF-like notation, and a set of show-by-example
transformation rules to be applied to inputs parsed using the grammar.
TXL is a
     functional/rule-based hybrid programming language, using the
paradigm of structural transformation. 

Greg




More information about the Python-list mailing list