Compiler Construction In Haskell
Center
Goal of the Tutorial
Over the years Utrecht University has been constructing the attribute
grammar system UUAGC, which by now incorporates many different ways of
generating compilers. In this course we wil show how UUAGC can be used
in combination with parsing combinator libraries which support the
applicative style of programming (including, but not excluding others,
the libraries from Utrecht). The system can be used for a whole range
of transformational tasks: from generating web pages from BiBTeX files
up to generating large systems such as the Utrecht Haskell Compiler.
In the course we will show how to design attribute grammars and how to
generate code from them using the various options which have become
available over the years.
Contents of the course
Attribute Grammars
Although many compiler construction books mention attribute grammars as a method for further processing once a program in a particular language has been parsed, not many tools are actually available for doing so. Over the years we have developed the
Utrecht University Attribute Grammar Compiler, which takes input structured as an attribute grammar and generates Haskell code from this description.
The advantages of this approach are that the various aspects of processing a language can be described separately. Advantages of this approach are:
- the possibility to describe aspects separately; we advocate our approach over the more conventional monad stacks. These seem at first sight attractive, but when things become more involved also lead to hard to maintain monad stacks.
- the possibility to write so-called circular programs in a compositional way. One if largely liberated from being forced to schedule one's computations, which becomes much more explicit when making use of monads. In this respect writing attribute grammars is more a Haskell style of programming than using monads.
- the possibility to analyze the dependencies between the attributes, which can lead to better strictness annotations, less space consumption, etc.
Over the years the UUAGC has evolved into a large system; in the course we will show how to use the system, what the various options stand for, and how to start building your own compiler with it.
Parser Combinators
In combination with the UUAGC system we also have developed a collection of parser combinators (
uu-parsinglib), which fits nicely in with the UUAGC system. Notice however that the use of this library is in no way limited to the UUAGC system, nor that the UUAGC system depends on this library. In the course we will show:
- how to use the applicative style of writing parsers
- how to deal with error messages generated by the parsing process
- how to make a range of design choices when starting to use these systems
Entrance requirements
Since we write all our code in Haskell and our tools generate Haskell a working knowledge of Haskell is required. It will be nice if you bring your laptop with the |uuagc| and the |uu-parsinglib| already installed. This can be easily done from hackage.
Lecturers
- Atze Dijkstra
- Doaitse Swierstra
Intended Audience
We aim with this tutorial at a wide class of people; these may be
- people teaching courses on compiler construction
- Ph.D. students who want to implement some experimental language
- people who want to experiment with the Utrecht Haskell Compiler
- people from industry who are building any sort of program which processes structured input.
Number of Participants
25
Materials
You might want to bring your laptop. We will make further information available through our websites.
Tutorial slides
Tutorial examples
The examples used throughout the tutorial. The examples require
uuagc and
uulib (containing the parser combinators used by the examples) to be installed. The tutorial part about the parser combinators explains the
uu-parsinglib library.
Contact
| Name | Doaitse Swierstra |
| Address | Princetonplein 5 |
| Email | doaitse@swierstra.net |
| Phone | +31 30 253 3962 |
| Mobile | +31 6 4563 6929 |
pdf 
tgz