learn.ifs.name

Context-Free Grammars and Constituency Parsing

Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19

11 cards in “19.6 CKY parsing” · whole deck

19.6 CKY parsing

  1. Why is dynamic programming effective for parsing ambiguous sentences?
    Because rules are context-free, once a constituent has been found over a span it can be recorded and reused in any larger derivation, rather than reanalyzed. Such table-based methods are also called chart parsing.
  2. What grammar form does CKY require?
    Chomsky normal form (rules A → B C or A → w).
  3. How is a general CFG converted to CNF?
    (1) Keep conforming rules; (2) replace terminals inside longer rules with dummy non-terminals (INF-VP → to VP becomes INF-VP → TO VP, TO → to); (3) eliminate unit productions (A → B) by rewriting with the non-unit rules they lead to; (4) binarize long rules with new non-terminals (S → Aux NP VP becomes S → X1 VP, X1 → Aux NP).
  4. What are unit productions, and what does eliminating them do to the grammar?
    Rules with a single non-terminal on the right (Nominal → Noun). Eliminating them flattens the grammar and promotes terminals to high levels, e.g. verbs become both VPs and Ss (S → book | include | prefer).
  5. What does cell \([i, j]\) of the CKY table contain, and what are fenceposts?
    The set of non-terminals for all constituents spanning positions \(i\) to \(j\). Indices point at the gaps between words (0 Book 1 the 2 flight 3 …), called fenceposts; the whole sentence is cell \([0, n]\).
  6. How is a cell \([i, j]\) filled in CKY?
    Since every constituent has two daughters, for each split point \(k\) with \(i < k < j\), combine an entry B in \([i, k]\) (to the left, along row \(i\)) with an entry C in \([k, j]\) (below, along column \(j\)) whenever the grammar has A → B C, and add A.
  7. In what order does CKY fill the table, and why?
    Column by column from left to right, each column from bottom to top, so the cells to the left and below that a cell depends on are already filled. This also mirrors processing words one at a time.
  8. Fill in the CKY table for “Book the flight through Houston”.
    BooktheflightthroughHouston
    0S, VP, Verb, Nominal, NounS, VP, X2S, VP, X2 (3 parses)
    1DetNPNP
    2Nominal, NounNominal
    3PrepPP
    4NP, ProperNoun
    Row = start position \(i\), column = end word; empty cells hold no constituent.
  9. Why does cell [0, 5] for “Book the flight through Houston” contain several S entries?
    There are alternative parses: the PP through Houston modifies the flight, modifies the booking (VP → VP PP), or is the second argument of the original VP → Verb NP PP (now X2 PP).
  10. Is the basic CKY algorithm a parser?
    No, a recognizer: it tells whether an S spans [0, n]. To parse, store with each non-terminal backpointers to the cells it came from and allow multiple copies of a non-terminal per cell; then the table contains all parses.
  11. What practical problem does CNF conversion cause, and how is it handled?
    Returned trees don’t match the original grammar. Binarization can be undone by deleting dummy non-terminals and promoting their daughters; unit productions are easier to handle by modifying CKY itself.

Source