InteractiveParsingForHaskell

Interactive Parsing for Haskell

(added 081113)

The goal of the project is to develop a parser for the Haskell programming language for use in a syntax-aware editor such as Yi.

Most programming environments provide interactive feedback to the programmer. This feedback is often largely based on syntactic analysis of the source code being edited.

In order to give meaningful feedback, the parser employed must be:

Robust: Errors in the input should be handled as gracefully as possible. Ideally, errors in the input should only have local effects on the parsing.
Efficient: Fast feedback is important. If feedback is slow, either the user will have to make frequent pauses, disrupting their work, or they risk reacting to outdated, incorrect information. In this project we aim for accurate feedback after each keystroke.
Precise: The analysis performed by the parser should be as close as possible to that made by the compiler.

Editors normally have regular-expression based parsers, which are efficient and robust, but lack in precision: they are unable to recognize complex structures. Parsers used in compilers are precise, but typically not robust: they fail to recover after an error. They are also not efficient for editing purposes, because they have to parse files from the beginning, even if the user makes incremental changes to the input. More modern IDEs use compiler-strength parsers, but they give delayed feedback to the user. Building a parser with good characteristics is challenging: no system offers such a combination of properties.

Yi has a parsing library to aid building robust and efficient parsers. This library is used to provide support for Haskell, and its precision is between a that of a regular-expression matcher and a compiler.

To complete this project, a student should write a parser for Haskell which combines robustness, efficiency and precision. This can be done using the existing parsing library, but it's likely that improvements to it will be required.

Background: AFP (Haskell), Programming languages
Number of people: 1-2
Contact: Jean-Philippe