From: vikkous <google@...>
Date: 2005-04-26T07:29:32+09:00
Subject: Re: Announcing Reg 0.4.0

I included some small examples at the end of my initial post to try to
whet your appetite. Perhaps you can see applications of this kind of
thing to what you use ruby for? Searching for complicated patterns
within an arbitrary object graph is what Reg is about. If you have
complicated data, Reg may be a good choice for searching in it.
(Eventually it'll have search-and-replace, but that's not implemented
yet.)

Traditionally, parsing and pattern matching languages stop after the
parser stage of the compiler pipeline, but it seems to me that many
later compiler tasks are particularly well suited for pattern-matchers.
(They're never used because by this point, compiler data is in the form
of a parse tree,
and text-based pattern tools (most of them) can't deal with that.)
Let's take the example of a simple optimization, like strength
reduction. This is where the compiler changes multiplication by a
constant power of two into a left shift.

The problem, in other words, is to search for nodes of the syntax tree
that look like this:
  [<some expr>, :*, 4]

and turn them into into this:
  [<some expr>, :<<, 2]

In Reg, that would be:
  +[expr, :*, -{:power_of_2?=>:true}].sub{BR[0], :<<, BR[2].log2}

My post "Lalr(n) parsing with reg" outlines how to twist Reg to
actually be a parser.