----------------------------------------------------------------
Assignment 3c.  CFG formalisms and parsing algorithms
----------------------------------------------------------------

In this part of the assignment, you will work with the context-free
formalisms we discussed in class, including running parsing algorithms
by hand, and you'll also answer a few questions.  A main goal of this
assignment is for you to understand and be able to show the behavior
of the algorithms on inputs -- by the end of this assignment you
should be able to do that BY MEMORY for recursive-descent and
shift-reduce parsing, and for converting from a CFG to an equivalent
RTN. (Don't worry too much about memorizing how to convert an RTN to a
CFG.)  By the end of the assignment you should also be comfortable
running the CKY algorithm by hand with the algorithm in front of you
(but not from memory).


Problem 3.c.1 

  a-c.  Do Allen, Ch 3, Problem 10, parts a, b, and c.


Problem 3.c.2  

  Let G be the following grammar:

     S  -> NP VP
     NP -> NP PP
     NP -> DET N
     VP -> V NP
     VP -> V
     PP -> P NP
     
     DET -> a | the
     N   -> man | dog | house | telescope | spoon
     VP  -> saw | fed | barked
     P   -> with

  Show a shift-reduce parse of "the man fed the dog".
  Don't worry about nondeterminism: just show the configurations
  along the way to the correct parse.  Here are the first few steps
  to show you the format you should use:

	   1   2   3   4   5   6
	    the man fed the dog

	 Operation     Stack   Input-location

	   start        ()                1
	   shift        (the)             2
	   reduce       (DET)             2
           ...continue!

  Remember that the top of the stack is on the left of the list.


Problem 3.c.3

  (i)  Show a recursive-descent (top-down) parse of the same sentence.
       Here are the first few steps to show you the format you should use:

	  Operation     Stack   Input-location

	    start        (S)               1
	    expand       (NP VP)           1
            ...continue!

  (ii) If you've got multiple rules that a nonterminal can expand
       to, which rule you try first can matter in a top-down parse.
       Suppose that the parser always chose to try the rule that
       appeared first in the grammar.  What would happen when it
       went to continue in (i), above?  What is the general description
       of rules that cause this problem?

  (iii) Why is this not a problem for bottom-up parsers?


Problem 3.c.4

  Let G be the following grammar:

    S -> AB
    S -> AS
    A -> BB
    A -> BA
    B -> AA
    B -> b
    A -> a

  Run the CKY algorithm on the input string "abbaba", showing 
  the resulting table.  (Drawing the chart is optional, but 
  might help you keep track.)  Is the string in L(G)?