Parsing methods 2005 - Lab 1 - Björn Bringert

Overview

I have implemented the times flies grammar and simple versions of the parsing algorithms in Haskell.

For a quick test and usage examples, see the Main module.

Part 1: A simple context-free grammar

The CF module declares a data type for context-free grammars, and some simple operations on such grammars. Grammars are restricted to rules on the forms A -> A1 ... An and A -> t.

The grammar operations use some general utility functions defined in the Util module.

The module TimeFlies contains three versions of the time flies grammar: the one given in the lecture, a modified version without left recursion, and one in Chomsky normal form.

Part 2: Recursive-descent parsing

The RecursiveDescent module implements a recursive-descent recognizer.

Part 3: Shift-reduce parsing

The ShiftReduce module implements a shift-reduce recognizer.

Part 4: Cocke-Kasami-Younger parsing

The CKY module implements a CKY recognizer.