7 Nov 2002 00:50:34 -0500

Related articles |
---|

Building a parse tree that reflects C Semantics vbdis@aol.com (VBDis) (2002-10-13) |

Re: Building a parse tree that reflects C Semantics grosch@cocolab.de (Josef Grosch) (2002-10-18) |

Re: Building a parse tree that reflects C Semantics idbaxter@semdesigns.com (Ira Baxter) (2002-10-20) |

Re: Building a parse tree that reflects C Semantics whopkins@alpha2.csd.uwm.edu (Mark) (2002-10-20) |

Re: Building a parse tree that reflects C Semantics rbates@southwind.net (Rodney M. Bates) (2002-10-20) |

Re: Building a parse tree that reflects C Semantics david.thompson1@worldnet.att.net (David Thompson) (2002-10-25) |

Re: Building a parse tree that reflects C Semantics rbates@southwind.net (Rodney M. Bates) (2002-11-06) |

Re: Building a parse tree that reflects C Semantics idbaxter@semdesigns.com (Ira Baxter) (2002-11-07) |

From: | "Ira Baxter" <idbaxter@semdesigns.com> |

Newsgroups: | comp.compilers |

Date: | 7 Nov 2002 00:50:34 -0500 |

Organization: | Compilers Central |

References: | 02-10-058 02-10-086 02-11-011 |

Keywords: | parse |

Posted-Date: | 07 Nov 2002 00:50:34 EST |

"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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.