Grammar Engineering

Location: Vrije Universiteit or CWI in Amsterdam, The Netherlands.

In many areas of computing, languages play a central role. Programming languages, data definition languages, scripting languages, mark-up-languages, query languages, etc. Unfortunately, it is common practise in software engineering to apply mostly ad-hoc techniques when dealing with language syntaxes. Grammar Engineering seeks to remedy this situation by regarding grammars as valueable software artifacts, and applying good engineering practises to their development, deployment, and maintenance.

In this project you will implement a tool-suite for Grammar Engineering. The tool-suite will include (i) support for grammar reconstruction from language reference manuals, (ii) a combinator library for reshaping grammars, and (iii) support for generating parsers, XML shema's, transformation libraries, and other software components from grammars. Your tool-suite will use the Syntax Definition Formalism (SDF) as internal representation format. To design your tool-suite you will take inspiration from published work and previously developed prototypes.

The implementation of this tool-suite will normally require some technology that it is fit to implement all of the above components while this technology should then also benefit from the provided components. Here are some options:

• A Haskell-centric approach with combinator parsing.
• An ASF+SDF Meta-Environment approach with its SGLR parsing technology.
• General-purpose programming languages and main-stream parser generators like ANTLR.

For example, in the Haskell scenario, the tool-suite is implemented in Haskell and it would be useful for the Haskell programmer. That is, the tool-suite would then help with deploying Haskell-based parsers, XML components and others while processing SDF grammars as input.

See also: the Grammar Ware page.

Supervisors: Ralf Laemmel (VU & CWI, The Netherlands), JoostVisser (UMinho)

Benchmarking Generic Programs

Location: Vrije Universiteit or CWI in Amsterdam, The Netherlands.

Generic Programming encompasses programming techniques that allow the construction of programs that work for just about any kind of data type. Examples of generic programming solutions are Strafunski, traversal functions in ASF+SDF, Generic Haskell, Polytypic Programming, and visitor combinators.

In this project you will perform thorough benchmarking of various generic programming approaches, and investigate some options for improving the efficiency of generic programs. To this end, you will develop a benchmark suite of generic programming problems, and corresponding solutions for each approach under scrutiny. You will investigate both time and space consumption by the various approaches. You will publish your benchmark suite and the results of running it on the internet, such that in future others can take advantage of it when comparing and evaluating generic programming approaches in future.

Supervisors: Ralf Laemmel (VU & CWI, The Netherlands), JoostVisser (UMinho)