This assignment is due at the start of class on Wednesday. It is worth 50% of a regular homework assignment.
S -> NP VP NP -> Det N NP -> N NP -> NP S/NP S/NP -> NP VP/NP VP -> V NP VP/NP -> gave | thrilled V -> gave | thrilled | ride | rides Det -> a | the N -> ride | rides | horse | horses | child | HarryParse the sentence rides the horse gave thrilled Harry according to the deductive parsing approach using Earley's algorithm (Shieber et al., Figure 5) and show the items that are added to the chart, similar to what you see in Shieber et al. on pages 9, 11, and 13. Note that you should not show every possible item added to the chart. That's a lot, even for a sentence this short. Just the show the steps that lead to a complete parse of the sentence, the same way that Shieber et al. do.
Just to be 100% clear: for this question, the Control part of Logic + Control is you. There's no need to be algorithmic, just pick out the sequence of operations that will get you to the complete parse. (You will not get credit for filling in an Earley dynamic programming table following conventional non-deductive presentations of the algorithm.)
They've decided that for every sentence, Adam's code should pass Betty's interpreter a list of all the valid parses for that input sentence, instead of just one parse tree for it, because without a probabilistic grammar Adam doesn't really have a good way of identifying which parse is best, if there's more than one.
Caitlin is Adam and Betty's boss. She's asked Adam and Betty how much time it will take for the app to process an n-word-long sentence in the worst case. Adam answers O(n^3). Betty says it's exponential in n.
After thinking for a minute, Caitlin points to one of them and says, "You're right!".