CS 254: Automata and Computability

Assignment #5: implementation of the CKY

Hand in via the Courses hand-in folder by 11:59PM Monday, May 16. Call your program cky.py.

Your job for this assignment is to write a Python implementation of the CKY algorithm as described in Lecture 27 of your textbook.

Command-line syntax

To invoke your program, a user should type something like:

python cky.py grammarfile stringtoparse

For example:

python cky.py grammar.txt 'aabbbab'

Expected output

Your program should print to standard output:

1. a human-readable display of the CKY chart
2. a horizontal line (e.g. "================")
3. (optional) a display of a parse tree extracted from the CKY chart showing the structure of the input string in terms of the grammar
4. (if you print the tree) another horizontal line
5. A short statement saying whether the input string can be generated by the given grammar.

If an error of some kind occurs, your program should print a suitable error message. In particular, if the grammar is not in Chomsky Normal Form or has a syntax error of some kind, your program should say so.

The top grade for this assignment if you don't print out a parse tree will be B+ (which is, of course, a good grade).

Grammar file syntax

Your program should be able to handle any grammar in Chomsky Normal Form, stored in a text file. A grammar file should have one line per production, with colons separating the symbols in the productions. For example, "S:A:B" would correspond to the production "S → AB". side of the production and the right. Similarly, the grammar on page 192 of your textbook would look like this:

S:A:B
S:B:A
S:S:S
S:A:C
S:B:D
A:a
B:b
C:S:B
D:S:A

You may (but need not) assume that nonterminals are single capital letters, and that terminals are single lower-case letters.