Re: Building a parse tree that reflects C Semantics

"Rodney M. Bates" <rbates@southwind.net> wrote in message
> Ira Baxter wrote:
> >
> > > We build tools that are intended to transform the program structure,
> > for arbitrary source languages. We wish to write transforms that can
> > be expressed in terms of the surface syntax of the language, e.g.,
> >
> > c = c + 1 ==> c++
> >
> > To do this, we desire that language fragments (patterns) be mapped to
> > the same structures as entire programs;. So we've chosen a
> > representation which optimizes on matching trees. We too chose trees
> > to represent such structures, but not the "semantically oriented"
> > ones, <snip>


> I think I see your reasoning, but now you have gotten my curiosity up.
> What sorts of meaningful pattern transformations could be written when:
>
> 1) The surface syntax is quite different from the deep semantics, and
> 2) The fragment in a pattern to be matched is too small to be able
> to define how it maps to deep semantics?


For 1), we can actually write pattern matches that essentially say,
      "if [this concrete syntax] can be rewritten by [set of transforms]
        to match [this other syntax], then replace by [new syntax]".
This allows you to encode "deep semantics" to some extent
in the rewrites. Using this, you can say things like,
"if this expression can be rewritten using algebra to match
        x*a+x*b, then replace it by x*(a+b)".
This will match a part of "(p-3)*q + 4", given
  rewrite rules that understand that "-" is simply "+-1*"
  and the commutative law. (DMS implicitly knows
  about the commutative law, because otherwise
  you need what amounts to an infinite set of rules
  to represent it, and it makes for an efficient matcher).


For 2), you are observing that "local patterns" individually can't capture
all possible transforms. In general, a transform is an arbitrary function
from programs to programs: T:P -> P.
There are several ways out:
      a) If you recognize that Post systems are Turing capable,
                and that tree-writing is a generalization of string-rewriting,
                then you can encode an arbitrary computation T
                with a set of rewrites. This is nice in theory,
                but we don't like programming Turing machines,
                and for the same reason, we don't like programming Post
                systems. (There's another thread about W grammars
                running in comp.compilers that is making these same
                points :-{). FWIW, our tools will let you do this.
    b) To avoid low-level Turing machines, we build more expressive
              languages, usually having concepts we care about.
              Procedural languages are pretty popular. So escape
              two is to allow procedural programming against the
              representation. Most compilers are built exactly this way.
    c) A hybrid of a) and b).. this is just pushing expressivity.
            You code complex transforms
              using procedural glue to combine local pattern matches
              and rewriting. This is what we really offer with DMS:
              integration of low-level procedural transforms, with
            high-level pattern matching and rewriting.
            (DMS has a lot of additional machinery, but that's
              not the subject of this post).




--
Ira D. Baxter, Ph.D., CTO 512-250-1018
Semantic Designs, Inc. www.semdesigns.com

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