ICS 661, Advanced Artificial Intelligence

Assignment 4

Implement the CKY algorithm and test it with your coverted L1 grammar (the output from assignment 3, or a copy of the right column of Figure 13.8 plus the right column of Figure 13.1 in ascii text format if you did not complete assignment 3). Your program should accept a single argument: the name of the ascii text file containing the CNF grammar. It should read input sentences from stdin (one sentence per line) and output to stdout "S" or "not S" followed by a newline for every input line. The program should exit upon EOF (control-D).

For extra credit, extend your parser to display the parse, for example in the bracket format: [S [NP I] [VP [Verb prefer] [NP TWA]]]. For even more extra credit, show all possible parses (you can separate the different parses with semi-colons or some other method).

Test your program with the L1 grammar and at least 10 sample input sentences (half of which should return S). Turn in to Laulima a zip file with your program code, your CNF file of the L1 grammar, a transcript of running your program with the 10 sample input sentences, and a README file describing how to compile and run your program.

David N. Chin / Chin@Hawaii.Edu