Assignment 3c, Ling 645/CMSC 723, Fall 1997

```
----------------------------------------------------------------
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