Below we give the CKY chart for a parse of the 10-word sentence:
The assignment is to explain some features of the chart resulting from use of the CKY algorithm to parse this sentence.
We first give the grammar the parser uses (in Chomsky Normal Form), as well as the lexicon.
pp -> p np vpg -> vbg np X2 -> X1 pp vp -> vbz np vp -> X1 pp vp -> X2 pp ap -> rb a s -> np vp np -> dt nbar np -> X3 np np -> ap nbar np -> nbar pp np -> n n np -> vbg np X3 -> np cc X1 -> vbz np nbar -> ap nbar nbar -> nbar pp nbar -> n n nbar -> vbg np
a: dt and: cc use: n np nbar codes: n np nbar sees: vbz of: p agency: n np nbar rapidly: rb handling: vbg labor: n np nbar volume: n np nbar as: p costs: n np nbar controlling: vbg way: n np nbar growing: a ap mail: n np nbar the: dt widespread: a ap
Your task concerns only the entries in the last column of the chart, which includes all entries ending at index 10. In "chart parsing" speak. These entries are referred to as edges.
Basically there are two possible kinds of explanation for an edge appearing in the chart.
You can report your discovery of a lexical edge in a very simple format known as a lexical record. Just report the word, the span, and the category:
Lexical edge way (9,10) n
np -> dt nbar
You can report your discovery of a rule edge in a simple format called a dtr record. Just give cat, the span, cat1 and cat2, and the value of k. So for our example, this is:
np (8,10) (det,9,nbar)
Finally, this sentence has 5 parses in this grammar. This is because certain edges contributing to the s edge in the (0,10) cell can be built in more than one way, given the grammar. These are called ambiguous edges. Find these ambiguous edges. They may not be in the last column, but they are in the chart, Give the lexical records or daughter records for these edges. You do not have to find all the ambiguous edges, just the ones contributing to the final 5 parses. Finally you do not have to find all the edges contributing to the final 5 parses, just the ambiguous ones.
j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
i | (0, 1) the |
(1, 2) agency |
(2, 3) sees |
(3, 4) use |
(4, 5) of |
(5, 6) the |
(6, 7) codes |
(7, 8) as |
(8, 9) a |
(9, 10) way |
0 | dt | np | s | s | s | |||||
1 | np nbar n | s | s | s | ||||||
2 | vbz | vp X1 | vp X2 X1 | vp X2 X1 | ||||||
3 | np nbar n | np nbar | np nbar | |||||||
4 | p | pp | pp | |||||||
5 | dt | np | np | |||||||
6 | np nbar n | np nbar | ||||||||
7 | p | pp | ||||||||
8 | dt | np | ||||||||
9 | np nbar n |