Problem Set 1

Assigned: Sept. 6
Due: Sept 18.

Consider the following grammar and lexicon:

Grammar
S -> NP VP
NP -> Noun
NP -> Noun PPLIST
VP -> Verb NP
VP -> Verb NP PPLIST
PPLIST -> PP
PPLIST -> PP PPLIST
PP -> Prep NP

Lexicon
books -- Noun, Verb,
bookstores -- Noun
buy -- Noun, Verb
classes -- Noun, Verb
for -- Prep
in -- Prep
people -- Noun, Verb

Problem 1

Show all possible parse trees for "People buy books for classes in bookstores."

(To save drawing you may wish to define abbrevations for subtrees that recur in different parse trees.)

Problem 2

In what sequence will a recursive descent parser find the parse trees in (1)? Do NOT draw a complete trace, just give the sequence of parse trees. (Assume that the different rules are attempted in the order given above.)