Master Project: Building a Parser Generator (WS 15/16)

A parser generator is a tool that takes a formal description of a language and produces a parser for the language. The parser usually converts an input text to an abstract syntax tree (AST), a programmatic representation. Alternatively, it directly performs actions while processing the input.

In our lecture on Compiler and Language-Processing Tools we use the tool SableCC as a parser generator. This tool provides some a number of outstanding features:

  • It uses a powerful and and commonly used parsing algorithm (LALR(1))
  • In addition to the parser, it also generates a lexer
  • It can automatically generate an abstract syntax tree (AST)
  • It is free (GNU LGPL).

The goal of this Master Project is to improve SableCC, or to build a tool with similar functionality. Possible improvements are:

  • Error messages are not very user friendly
  • The syntax is unnecessary complex and does not follow some common conventions
  • Language descriptions usually need some redundant information
  • The grammar does not allow all EBNF constructs
  • The generated abstract syntax trees do not make good use of the Java type system
  • There is no support for defining attributes on the abstract syntax tree

It will be part of the project to elicit the concrete requirements, implement and evaluate them.

Module Information

  • Module: “Software Engineering (Project)” 89-3282
  • Presence Hours: project (4P)
  • Credit Points: 8 CP (corresponds to 240 working hours)
  • Level: Master (Advanced Level)
  • Language: English
  • Lecturer: Annette Bieniusa, Peter Zeller

Process

The project will take place during the lecture period of the winter term ’15/’16 (starting at 26.10.2015).

  • Kick-off meeting: between 26.10.2015 and 30.10.2015

Registration

Please register before 23rd of October 2015 via email with p_zeller@cs.uni-kl.de. Please include name, matriculation number, and field of studies. The number of places for the project is limited and will be assigned on a first come, first served basis.

Requirements

  • Good programming skills in Java

Optional:

  • Formal background knowledge about languages and grammars (lectures Software-Entwicklung 1, Formale Grundlagen der Programmierung)
  • Knowledge about compilers (see lecture on Compiler and Language-Processing Tools)

These skills are not a strict requirement, but you will need to acquire knowledge in these topics if you are not familiar with them yet.

Contact

In the case of further questions, please contact:

  • Peter Zeller (p_zeller@cs.uni-kl.de)