G22.2590 - Natural Language Processing -- Spring 2003 -- Prof. Grishman

Assignment #3

February 6, 2003

You may want to use the Jet parser for the first three exercises, and particularly for #2.  Keep in mind in doing these exercises that many words have several parts of speech.

  1. Using the tiny grammar below, draw the two parse trees for the sentence “The fair features live music.”  Suggest a constraint which would resolve this ambiguity.
  2. Using the same tiny grammar, compare the efficiency of the top-down backtracking parser, a bottom-up (immediate constituent) parser, and a top-down chart parser on the sentence “The program answers questions.”  For the two grammar symbols, S and NP
  3. Modify this grammar to capture subject-verb number agreement.  Does it now produce one parse?
  4. J&M exercise 8.1. (practice tagging some text)
  5. sentence :=  np v | np v np;
    np     :=  n | art n | art adj n;
Due February 13th.