Re: Tree Pattern recognition?

shoopak@romulus.rutgers.edu writes:
>Is there a tool out there which will allow pattern matching of a sub-tree
>(given its nodal structure and elements) to a section of a larger tree?


Yes. (oh, you wanted to know where.) I know of the following, which have
varying ability and license conditions. This is a somewhat USA-centric
list -- I know there is also work going in Europe (notably in Germany).


BURG (Todd Proebsting, formerly at U Wisconsin, go looking in ftp
directories at cs.uwisc.edu. Todd P. is now at a state university in one
of the big hot square states (New Mexico or Arizona)).


UWCODEGEN (Robert Henry et al, now at Tera Computers, formerly of U
Washington. Probably not FTP-able.)


IBURG (Proebsting and Hanson, ???)


TWIG (Al Aho, Steve Tjiang, Mahedevan Ganapathi et al at AT&T. As far as
I know, Al Aho is still at AT&T, Steve Tjiang is now at Synopsys and M.
Ganapathi is at UC Davis. I think the license conditions for this are
semi-restrictive.)


Chris Fraser has also done work on this in various forms.


To my knowledge, BURG and UWCODEGEN use the same basic algorithm, though
BURG incorporates some smart generation-time improvements based on grammar
simplification. Both are based on the BURS work done by Eduardo
Pelegri-Llopart at Berkeley, which is (roughly) a static encoding into
tables of cost-driven pattern matching. The pattern-matcher runs
bottom-up.


TWIG and IBURG use a top-down dynamic programming algorithm which is more
flexible, though slightly slower. Generally, the patterns must be
"linear" (I believe that is the term) meaning that the variable terms in
the patterns are not repeated. That is, you may have a pattern of the
form


    (ASSIGN (INDIRECT registerX) (INDIRECT registerY))
                                                        ^ ^


but not


    (ASSIGN (INDIRECT registerX) (INDIRECT registerX))
                                                        ^ ^


If you need to repeat variables, then you need to look into unification.


If you're just interested in pattern-matching (w/o costs) I did some work
along those lines long ago, and I can probably send you the code (it dates
back to gradual student days, and thus is not encumbered by licenses), but
I really recommend something like BURG or IBURG. Other improvements have
been made in the direction of incremental pattern processing (and in
asymptotic performance of the pattern matcher generator) by Cai, Paige,
and Tarjan. I don't think that work incorporates costs, yet.


One important point to note if you decide to play with bottom-up pattern
matching: if you don't compress the tables, they get VERY big. On-the-fly
compression makes the problem more manageable. That was my contribution,
a long time ago.


David Chase
Sun Microsystems
--

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