Re: TWIG any info (Todd A. Proebsting)
24 May 1996 15:42:02 -0400

          From comp.compilers

Related articles
TWIG any info (1996-05-14)
Re: TWIG any info (1996-05-19)
Re: TWIG any info Peter.Damron@Eng.Sun.COM (1996-05-19)
Re: TWIG any info (1996-05-19)
Re: TWIG any info (1996-05-21)
Re: TWIG any info (David Hanson) (1996-05-24)
Re: TWIG any info (1996-05-24)
| List of all articles for this month |

From: (Todd A. Proebsting)
Newsgroups: comp.compilers
Date: 24 May 1996 15:42:02 -0400
Organization: University of Arizona CS Department, Tucson AZ
References: 96-05-094 96-05-138
Keywords: tools () writes:
> wrt:
> TWIG code generator generator using tree pattern matching/rewriting.

> Can anybody give links to TWIG ? Where is it available
> source/binary form / at what terms/conditions for non-commercial use.

David Chase <> wrote:
>You'd probably be better off with either burg, or iburg. Iburg is most like
>twig, algorithmically speaking. Burg generates faster matchers, but you
>don't have as much freedom in figuring out the costs at runtime (as in, none
>-- costs for patterns must be statically assigned). I think the consensus
>of the people who build and use these things is that iburg's algorithm is
>the one most people should use, except for applications in which speed of
>code generation is extraordinarily important.

I agree with David completely. I *wrote* burg, but I don't use it except
when speed is paramount. The good news is that burg and iburg have compatible
interfaces, so plugging in burg after using iburg for development is trivial.
The bad news is that while iburg-generated matchers *could* use costs
determined at pattern-matching time, they don't.

TWIG does support match-time cost functions. If those are important, it would
be easy to add them to iburg, although some of iburg's optimizations would
need to be disabled.

TWIG also supports trees of arity greater than 2, while iburg does not.
Extending iburg to handle greater arity would not be difficult either, but it
would require extending the interface because the maximum arity of the trees
is currently burned into the specification language.

>(Note that I am explicitly
>un-tooting my own horn here; years ago I made a decent contribution to the
>technology used in burg, but I think you'd be better off with iburg. In my
>own work, I would always use iburg first, and only consider burg after I had
>measured the time spent generating code and found it too costly.)

I'll toot David's horn for him. Without his contribution, burg would have
been impractical and would not exist. (David contributed the key insight
on how to build a pattern-matching automaton of reasonable size.)

>My copy of iburg says:
> iburg is available for anonymous ftp from
> ( in pub/iburg.tar.Z or pub/

You can also take a look at

Todd Proebsting


Post a followup to this message

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