Your job for this assignment is to write a Python implementation of the CKY algorithm as described in Lecture 27 of your textbook.
To invoke your program, a user should type something like:
python cky.py grammarfile stringtoparse
For example:
python cky.py grammar.txt 'aabbbab'
Your program should print to standard output:
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).
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.