Parsing


  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    -> NP S/NP
    S/NP  -> NP VP/NP
    VP    -> V NP
    VP/NP -> gave | thrilled 
    V     -> gave | thrilled | ride | rides
    Det   -> a | the
    NP    -> rides | Harry
    N     -> ride | rides | horse | horses | child | Harry
    

    Note that a symbol with a slash is a single nonterminal symbol. You can read X/Y as "an X that is missing a Y", e.g. S/NP is an S that is missing an NP. Special symbols like these don't change the context-freeness of the grammar, but they can be a convenient way of using a context-free grammar to capture non-local relationships -- for example in the noun phrase rides the horse gave (i.e. rides that were given by the horse), the word rides appears on the left of the phrase, but the semantic interpretation is the same as if it were the object of gave. (Nonterminals of this kind are often referred to as "slash categories".)

    What you should do: 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, in the same table format that 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. (Also, you are welcome to hand-write this if you prefer rather than typing everything in, as long as your handwriting is easy to read.)

    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. Nor should you simply copy all of the table entries produced by the Earley parser implementation you'll see below. The goal here is to work through it by hand.)

  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. Getting hands on.

    We're going to use this nice Earley parser demonstration in Javascript. You can download the code and run it locally (by going into the earley-parser-js/demo_nlp_live directory and opening demo.html in your browser) or you can just go to https://jsfiddle.net/2mb3w9c1/4/embedded/result/ in your browser.

    Either way, you're going to need to open the javascript console in your browser -- for example, see how to use the console in the Chrome browser. (I recommend Chrome, but other browsers have similar kinds of access to the console.)

    Begin by copying (or typing) the grammar above into the grammar pane, replacing the grammar that's there. With the console open, type Harry rides horses one word at a time. With each word, look at the updated information in the console. (Depending on which browser you're using, you might or might not get proper human-readable display of the right-arrow and the dot in dotted rules, but it should be obvious where they are.) Notice how in addition to the human readable dotted rules, you're seeing the internal data structures, organized by columns (or what Earley called "states"); for easier readability, you can copy/paste javascript elements like

    [{"56":{"lhs":"N","rhs":["horses"],"dot":1,"left":2,"right":3,"id":56,"ref":[{"55":{"lhs":"horses","rhs":["horses"],"dot":1,"left":2,"right":3,"id":55,"ref":[{}]}}]}}]
    
    into http://jsbeautifier.org/ to format them nicely.

    Play around with the grammar and/or the parser to get a hands-on feel for how the parser works. Then answer the following question: Using the Earley parser's behavior on the sentence rides the horse gave thrilled the child, illustrate how the Earley parser's top-down approach can avoid some local ambiguities that are faced by a bottom-up parser like CKY. (You are welcome to support your illustration by implementing, or running an implementation of, CKY on the same sentence, but that's not required. I wrote the grammar in Chomsky Normal Form just in case you want to do that.)

    Extra credit (up to 10%)

    Read Resnik (1992), Left-Corner Parsing and Psychological Plausibility. Then:

    1. Write a brief summary of the argument the paper is making in your own words. (No more than 1-2 paragraphs. That means you need to summarize, not just try to repeat everything. The ability to summarize is a demonstration of your understanding.)

      (Although it's not particularly relevant for this assignment, note that augmented transition networks [ATNs], discussed in Section 2.2, are basically recursive transition networks with the added ability to execute procedures, e.g. to build and store structure, on the arcs.)

    2. Consider the following grammar:
      S -> A S B
      S -> C 
      S -> X S
      S -> S Y
      A -> a
      B -> b
      C -> c
      X -> x
      Y -> y
      

      What is the Earley parser like, in terms of the Resnik (1992) argument about memory usage and psychological plausibility? That is, what are the maximum memory requirements (in terms of the number of incomplete constituents stored) on

      • (a) strings with right-branching structure (e.g. xc, xxc, xxxc, etc.)?
      • (b) strings with left-branching structure (e.g. cy, cyy, cyyy, etc.)?
      • (c) strings with center-embedded structure (e.g. acb, aacbb, aaacbbb, etc.)?

      You are welcome to use the javascript Earley parser above to help answer this question.