Optimizing Attribute Grammars

Date: 2008-04-17

Time: 12:00

Room: BBL room 420

Speaker: Arie Middelkoop

Title: Optimizing Attribute Grammars

Abstract

A transformation tool (such as a compiler) has typically the following behaviour: a parser constructs an abstract syntax tree, which is subsequently analyzed and transformed by walking over it in complex ways. Tree-walks are often implemented with recursive functions, but writing them is a tedious task. Attribute grammars are a domain specific language for the specification of tree-walks. A compiler for attribute grammars then generates the recursive functions for you.

The Universiteit Utrecht Attribute Grammar system (UUAG) is such an attribute grammar compiler. It is used for the implementation of many compilers during courses such as Implementation of Programming Languages, but also for real-world programs, such as the compilers EHC and Helium, and the editor Proxima. These real-world programs have tighter performance requirements. The code generated by UUAG used to rely on lazy evaluation to compute attributes in the appropriate order, which may not perform well enough for these real-world programs.

For over a year now, the UUAG system has an option to produce optimized code that relies less on lazy evaluation and performs better. The optimization comes almost for free, except that the AG code has to satisfy certain properties (non-cyclic mainly). I show you what optimized code is generated, what issues are in practice when you use these optimizations, and how to deal with these practicalities.

Some familarity with attribute grammars is assumed. This talk may interest you in particular if you took the IPL course.