The construction of an SASL-Compiler

Abstract

These notes are intended to guide students during the construction of a compiler for a lazy pure functional language. The material covered here includes the lexing, parsing, and parse tree construction phase, as well as the combinator compilation and reduction component of a combinator reduction implementation of such a language. When there has been the choice between the exhaustive theoretical presentation of a topic or the discussion of the issues of its implementation, we chose the latter. After all it is the goal of this course to get a working compiler within reasonable time. However, topics like grammar transformation (for recursive descent parsing), combinator compilation, and reduction are discussed to a depth that should be sufficient to wake interest for the theoretical foundations. The students are expected to be familiar with formal language concepts like BNF grammars, production rules, and derivation. The knowledge of basic data structures, such as trees and stacks, is a prerequisite. Experience with functional programming languages is not assumed, though. Starting with Section 2, the material is intended as a handout to students. These notes have been the successful basis for a second year student's programming course in Konstanz. I make them available in the hope that they turn out to be useful or might speed up the preparation of a similar assignment.