Programming Assignment 3: Natural Language

Assigned: September 11
Due: October 4

General Description

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

Grammar

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

Lexicon

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 27 edges, as in the example of chart parsing. ( Just the edges, not all the function calls.)

If the sentence does not fit the given grammar, then output, "This sentence cannot be parsed."

Extra credit (2 points)

Write the program so that it takes the grammar and lexicon as input. (The format is up to you.)

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. You may assume that all the words in the sentence are in the lexicon.

I recommend that you use data structures that do not assume any particular size limits (and I require this for the extra credit version). However, if you want to use fixed size arrays, you can assume that no sentence is more than 20 words long and that the chart does not have more than 200 edges.

You may use C, C++, or Java; if you want to use another language, check with me. You may input the test sentences in any reasonable manner, except imbedding them in the code.

Late Policy

I will accept projects late (up to the end of the semester) with a penalty of 1 point out of 10. However, the second programming project will be handed out the day this one is due, so I recommend against letting programming projects pile up.

To submit

Email me