Parsing Algorithms

Consider the following grammar:

 S    -->  NP VP
 VP   -->  V NP
 VP   -->  VP PP
 PP   -->  Prep NP
 NP   -->  Det N
 NP   -->  NP PP
 N    -->  dog | bit | man | yard
 V    -->  dog | man | bit
 Prep -->  in
 Det  -->  the

 the dog bit the man in the yard

Your assignment is to parse this sentence by hand using three different algorithms. Specifically, you must choose:

1. One of
   • Top down recursive descent
   • Bottom up shift-reduce
2. Left corner
3. One of
   • CKY
   • Earley's algorithm

For the stack-based parsers (top down, bottom up, left corner), you should show a trace of one path through the non-deterministic search space, according to the format we used in class, i.e.

  Operation     What's on the Stack    What's in the input

For the CKY or Earley parsers, you should show the final contents of the table. For CKY what you do should be consistent with the algorithm handout from class (e.g. words are numbered starting from 1). For Earley's algorithm, what you do should follow the textbook. For either algorithm, if you make mistakes you are more likely to get partial credit if you also show the chart data structure that corresponds to the parse (i.e. showing which edges cover which parts of the sentence.)

For people who have seen some of these algorithms before, I strongly recommend you choose the algorithms with which you are least familiar.

Extra Credit

Algorithm Specifications