Reconceptualising Bottom-Up Tree Rewriting (Prof. Dr. John Gough)

Description

Bottom-up tree rewriting is a widely used method for code selection in programming language compilers. The use of dynamic programming allows such rewriters to emit code sequences that are optimal with respect to some prescribed cost metric, at least for tree-structured computations. The semantics of rewriting are specified by the production rules of a tree grammar. In this talk, I show that a suitable reinterpretation of the meaning of the non-terminal symbols of such grammars provides a significant increase in the expressivity of the rewriting system. In particular, the generation of instructions for flow of control may be subsumed into the rewriter. Likewise, transformation rules normally associated with peephole optimization are also conveniently expressible.

Period	17 Jul 2013
Event type	Guest talk
Location	AustriaShow on map