This assignment is due Wednesday, October 19 at 11:59PM.

Goals

Through this assignment you will:

NOTE: You may work in teams of two (2) on this assignment. If you do so:

Background

Please review the class slides and readings in the textbook on the Cocke-Kasami-Younger (CKY) algorithm (J&M 13.4.1).

Implementing a CKY Parser

Based on the material in the lectures and text, develop an implementation of the CKY algorithm that will parse input sentences using a CNF grammar. You may use existing implementations of the data structures to represent the grammar in NLTK or other NLP toolkits, but you must implement the parsing algorithm yourself.

Your algorithm must return all parses derived for the input sentences given the grammar.

Parsing with your CKY Parser

The program you submit should do the following:

  1. Load the CNF grammar.
  2. Read in the example sentences.
  3. For each example sentence, output to a file:
    • The sentence itself
    • the simple bracket structure parse(s) based on your implementation of the CKY algorithm, and
    • the number of parses for that sentence.

Programming

Create a program named hw3_parser to perform CKY parsing as described above, invoked as:

hw3_parser.sh <grammar_filename> <test_sentence_filename> <output_filename>

where:

Files

Please adhere to the naming conventions.

Test and Example Files

All test and example files will be located in /dropbox/22-23/au571/hw3/ on patas.

Submission Files

If working in teams: