Programming Assignment 3: Natural Language

Assigned: October 31
Due: November 28.

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 26 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.

As in the previous assignments, you may use C, C++, or Java. You may input the test sentences in any reasonable manner, except imbedding them in the code.

To submit

Email me