Programming Assignment 3: Natural Language

Assigned: November 10
Due: December 1.

General Description

Implement a chart parser (see Russell and Norvig, pp. 800-805) for the context-free grammar and lexicon showed below:


S -> NP VP
NP -> Pronoun
NP -> Name
NP -> Noun
NP -> Article Noun
VP -> VG
VG -> Verb
VG -> Modal Verb
PP -> Prep NP


a -- Article
Amy -- Name
ate -- Verb
can -- Modal, Verb, Noun
fish -- Noun, Verb
had -- Verb
I -- Pronoun
in -- Prep
John -- Name
king -- Noun
of -- Prep
put -- Verb
the -- Article
to -- Prep
stream -- Verb, Noun
swim -- Verb, Noun
swims -- Verb, Noun
The program should output the chart. For example, for the sentence "I can fish" the program should output a list of the 26 edges, as in the example of chart parsing. ( Just the edges, not all the function calls.)

If there is no parse tree, the program should output "No parse tree".

Extra credit (20 points)

Write a routine that outputs a parse tree.

Comments about implementation

The chart parsing algorithm is very clearly described in the textbook. There are no singular or anomalous cases that you need to worry about.

You may assume that each sentence is on a single line of input, and that sentences are unpunctuated.

I recommend that you use data structures that do not assume any particular size limits. However, if you want to use fixed size arrays, you can assume that no sentence is more than 20 words long and that no row in the chart has more than 100 edges.

As in the previous assignments, you may use any programming language you choose. You may input the test sentences in any reasonable manner, except imbedding them in the code.

To submit

Email to the grader (

No late submissions

I regret to say that I cannot accept any late submissions (past midnight on Monday Dec. 1.) The grader has his own exams to prepare for.