Programming Languages

Presentation at OOPSLA conference

Tillmann Rendel
Tillmann Rendel
presents the paper From Object Algebras to Attribute Grammars at the International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA) in Portland, Oregon. The paper is joint work with Jonathan Brachthäuser
Jonathan Brachthäuser
and Klaus Ostermann
Klaus Ostermann


Oliveira and Cook (2012) and Oliveira et al. (2013) have recently introduced object algebras as a program structuring technique to improve the modularity and extensibility of programs. We analyze the relationship between object algebras and attribute grammars (AGs), a formalism to augment context-free grammars with attributes.

We present an extension of the object algebra technique with which the full class of L-attributed grammars—an important class of AGs that corresponds to one-pass compilers—can be encoded in Scala. The encoding is modular (attributes can be defined and type-checked separately), scalable (the size of the encoding is linear in the size of the AG specification) and compositional (each AG artefact is represented as a seman- tic object of the host language).

To validate these claims, we have formalized the encoding and we have re-implemented a one-pass compiler for a subset of C with our technique. We also discuss how advanced features of modern AG systems, such as higher-order and parameterized attributes, reference attributes, and forwarding can be supported.

Further Information