This assignment is due at 5pm on Thursday April 13th.
The files simple-parse.scm, simple-lexicon.scm, and sample-grammer.scm contain a simple chart parser. Your mission is to add the following upgrades:
You make these upgrades in any order. I recommend building the display function first, as it will be useful for debugging the later parts. And all the modifications should work together: you should turn in one version of the code containing all of them.
Hand in your code and written description as for the previous assignments.
The file simple-lexicon.scm contains extremely simple lexical analysis code, simple-parse.scm contains the chart parser itself, and sample-grammar.scm defines a simple lexicon (*sample-lexicon*) and grammar (*sample-grammar*). To parse a sentence, call the function chart-parse as follows:
>(chart-parse '(the duck ate some sand) *sample-grammar* *sample-lexicon*)
After it is finished parsing the input, chart-parse will display the contents of the chart and then returns the chart itself. For our example, the display looks like:
Chart for input (the duck ate some sand)
Start 0:
length 5
(s #{Rule (s -> np vp)})
length 4
length 3
(s #{Rule (s -> np vp)})
length 2
(np #{Rule (np -> det noun)})
length 1
(det the)
Start 1:
length 4
length 3
length 2
length 1
(noun duck)
Start 2:
length 3
(vp #{Rule (vp -> verb np)})
length 2
length 1
(vp #{Rule (vp -> verb)})
(verb ate)
Start 3:
length 2
(np #{Rule (np -> det noun)})
length 1
(det some)
Start 4:
length 1
(noun sand)
'#{Chart}
If you reset the variable *debugging-level* to 1 or 2, from its initial value of 0, the parser will print a detailed trace of its activities.
The parser returns a chart (a record of type chart), containing all the constituents that it has been able to build for the sentence. Write a function that tells the user whether the parse succeeded and, if so, displays one of the parse trees in this chart.
Specifically, your function should determine whether the chart contains a sentence spanning the entire input. That is, is a constituent in the appropriate chart cell whose type is the start symbol for the grammar? If so, the parse succeeded and the chart contains at least one parse tree for the sentence.
Your function should display one of the parse trees. For most examples in this assignment, I the chart will contain only one parse. However, it could contain more than one parse. If it does, you only have to display one. (Displaying multiple parses is not conceptually hard but it looks like a nuisance to code.)
For example, my display function runs as follows:
> (define foo (chart-parse '(the duck ate some sand) *sample-grammar* *sample-lexicon*))
.....
> (display-tree foo)
#{Rule (s -> np vp)}: the duck ate some sand
#{Rule (np -> det noun)}: the duck
input word: the
input word: duck
#{Rule (vp -> verb np)}: ate some sand
input word: ate
#{Rule (np -> det noun)}: some sand
input word: some
input word: sand
The chart may contain constituents that never formed part of the final parse tree. If it contains several alternative parse trees, some constituents may belong to only one of the parses. Therefore, your display function must trace the tree from the root node.
To do this tracing, you will need to add some additional information to the constituents stored in the chart. Each constituent needs to remember which smaller constituents it was made from. For example, the S node at the top of the tree in the above example needs to know that it is made up of an NP and a VP which are to be found in cells (0 2) and (2 3) of the chart.
The sample grammar does a rotten job of handling noun phrases, because it doesn't distinguish between mass nouns (e.g. milk), count nouns (e.g. duck) and proper nouns (e.g. Margaret). Only certain types of nouns can occur with determiners, only certain kinds can occur without determiners, and not all determiners work with same types of nouns. For example:
Modify the grammar for noun phrases so that it allows different determiner possibilities for these three different types of nouns.
Some words in English can belong to more than one lexical category. For example, "hit" can be either a noun or a verb. Modify the parser so that, in the lexicon, more than one lexical category can be specified for some words.
Add several such words to your lexicon and show me some examples that illustrate that the parser can accept sentences using both meanings of the word. For example, the word "hit" can occur in "Margaret wrote a hit." or "Margaret hit a wart."
Warning: the verbs in the sample lexicon are all past tense. This is to avoid issues of verb agreement. Most words that can be both nouns and verbs are ambiguous only in the present tense (e.g. rock, milk). Modifying the grammar to handle present tense verbs would be messy, so find words that belong to a different pair of categories.
In writing grammars, it is often convenient to write rules with optional items. For example:
NP -> (det) noun (PP) rather than the four rules: NP -> noun NP -> det noun NP -> noun PP NP -> det noun PP
Explain how to add this feature to the chart parser. If you have time, implement it.
This page is maintained by Margaret Fleck.