Growing an abstract grammar: teaching language engineering

Abstract grammars are neglected resources in language processor implementations. In the most favourable case they are used to format first-class program representations. In the worst case they serve as a temporary interface between compiler phases. But they can enable so much more âĂe certainly in teaching. In this presentation we report on a long-running experiment (>5 y.) to develop a language interpreter that is maximally supported by an extensible (abstract) grammar. The context of the experiment is an advanced course on Programming Language Engineering (http://soft.vub.ac.be/PLE). The reference language is a simplified variation on Scheme, so: no objects in this story. In this course abstract grammars serve as backbone for material ranging from formal language specifications to low-level implementation with an eye for optimisation. In order to do so, we require that an instance of an abstract grammar be first class, and that all of its attributes should be setable and getable from within any program that is associated with this instance. Depending on the level of detail at which its semantics are captured in the abstract grammar, this regulates the depth at which the program can reflect over its specification. Nothing new here, this is lisp and s-expressions, only more so. A central idea to this notion of a rich abstract grammar, is a unified memory model. At a basic level no distinction is made between stacks, heaps, frames c and if the interpretation strategy is based on a transformation into continuation passing style (as is the case here), structures resulting from lambda-lifting should be considered. However, the most interesting extensions to the abstract grammar are related to optimisations: tail call optimisation, inlining, prevalent function call patterns, &c. This approach proved to be an interesting setting to expose graduate students to the vagaries low level language processor implementations. But it has also been suitable as a platform for sophisticated experiments with optimisations for language interpreters.