Parsing


This assignment is due at the start of class on Wednesday. It is worth 50% of a regular homework assignment.

  1. Read Shieber et al., Principles and Implementation of Deductive Parsing, Sections 1-3 plus the beginning of Section 5, specifically the chart-based deduction procedure on page 27. (You can safely ignore all discussions related to proving soundness and completeness. That's not what we're interested in here.)

  2. Consider the following grammar:
    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 | Harry
    
    Parse 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.)

  3. Use the CYK (note: not alphabetical!) deductive parsing system (Shieber et al. Figure 1) to parse the same sentence. Once again, you only need to show the relevant items, not all of them. (You will not get credit for filling in a CKY dynamic programming table following conventional non-deductive presentations of the algorithm.)

  4. Adam and Betty are building an app for the Amazon Echo. Adam is using the version of the CKY algorithm with dynamic programming, to handle the analysis of input sentences using a non-probabilistic context-free grammar. (Naturally the grammar is in Chomsky normal form.) Betty is writing an interpreter that takes resulting parse trees as input. (Her interpreter has no problem handling trees that come from a grammar in Chomsky normal form.)

    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!".