Solution Set 6

General Description

Consider the following grammar and lexicon:

Grammar

S -> NP VP
NP -> Noun
NP -> NP PP
NP -> NP "and" NP
VP -> Verb
VP -> Verb NP
VP -> VP PP
VP -> VP "and" VP
PP -> Prep NP

Lexicon

bikes -- Noun, Verb
fields -- Noun, Verb
fishes -- Noun, Verb
in -- Prep
John -- Noun
streams -- Noun, Verb
through -- Prep

Problem 1:

Show all possible parse trees for "John fishes in streams and bikes through fields."
S ---> NP ---> Noun ---> "John"
   |
   |-> VP ---> VP ---> Verb ---> "fishes"
           |
           |-> PP ---> Prep ---> "in"
                   |
                   |-> NP ---> NP ---> Noun ---> "streams"
                           |
                           |-> "and"
                           |
                           |-> NP ---> NP ---> Noun ---> "bikes"
                                   |
                                   |-> PP ---> Prep ---> "through"
                                           |
                                           |-> NP ---> Noun ---> "fields"

S ---> NP ---> Noun ---> "John"
   |
   |-> VP ---> VP ---> VP ---> Verb ---> "fishes"
           |       |
           |       |-> PP ---> Prep ---> "in"
           |               |
           |               |-> NP ---> NP ---> Noun ---> "streams"
           |                       |
           |                       |-> "and"
           |                       |
           |                       |-> NP ---> Noun ---> "bikes"
           |
           |-> PP ---> Prep ---> "through"
                             |
                             |-> NP ---> Noun ---> "fields"

 
S ---> NP ---> Noun ---> "John"
   |
   |-> VP ---> VP ---> Verb ---> "fishes"
           |
           |-> PP ---> Prep ---> "in"
                   |
                   |-> NP ---> NP ---> NP ---> Noun ---> "streams"
                           |       |
                           |       |-> "and"
                           |       |
                           |       |-> NP ---> Noun ---> "bikes"
                           |
                           |-> PP ---> Prep ---> "through"
                                             |
                                             |-> NP ---> Noun ---> "fields"

 
S ---> NP ---> Noun ---> "John"
   |
   |-> VP ---> VP ---> VP ---> Verb ---> "fishes"
           |       |       |
           |       |       |-> PP ---> Prep ---> "in"
           |       |               |
           |       |               |-> NP ---> NP ---> Noun ---> "streams"
           |       |       
           |       |-> "and"
           |       |
           |       |-> VP ---> Verb ---> "bikes"
           |
           |-> PP ---> Prep ---> "through"
                   |
                   |-> NP ---> Noun ---> "fields"


S ---> NP ---> Noun ---> "John"
   |
   |-> VP ---> VP ---> Verb ---> "fishes"
           |       |
           |       |-> PP ---> Prep ---> "in"
           |               |
           |               |-> NP ---> Noun ---> "streams"
           |                       
           |-> "and"
           |                
           |-> VP ---> VP ---> Verb ---> "bikes"
                   |
                   |-> PP ---> Prep ---> "through"
                           |
                           |-> NP ---> Noun ---> "fields"

Problem 2:

Show all the edges constructed by a top-down chart parser for the sentence, "John fishes in streams". Identify the edges that are part of the final complete parse tree.

Answer: (Edges marked with a plus sign are part of the final parse tree.)

1. [0,0,S' -> * S] +
2. [0,0,S -> * NP VP] +
3. [0,0,NP -> * Noun] +
4. [0,0,NP -> * NP PP]
5. [0,0,NP -> * NP "and" NP]
6. [0,1,NP -> Noun *] +
7. [0,1,NP -> NP * PP]
8. [0,1,NP -> NP * "and" NP]
9. [0,1,S -> NP * VP]
10. [1,1,VP -> * Verb] +
11. [1,1,VP -> * Verb NP]
12. [1,1,VP -> * VP PP] +
13. [1,1,VP -> * VP "and" VP]
14. [1,1,PP -> * Prep NP]
15. [1,2,VP -> Verb *] +
16. [1,2,VP -> Verb * NP]
17. [1,2 VP -> VP * PP] +
18. [1,2 VP -> VP * "and" VP]
19. [0,2,S -> NP VP *]
20. [0,2,S' -> S]
21. [2,2,NP -> * Noun]
22. [2,2,NP -> * NP PP]
23. [2,2,NP -> * NP "and" NP]
24. [2,2,PP -> * Prep NP] +
25. [2,3,PP -> Prep * NP] +
26. [3,3,NP -> * Noun]
27. [3,3,NP -> * NP PP]
28. [3,3,NP -> * NP "and" NP]
29. [3,4,NP -> Noun *] +
30. [3,4,NP -> NP * PP]
31. [3,4,NP -> NP * "and" NP]
32. [2,4,PP -> Prep NP *]
33. [1,4,VP -> VP PP *]
34. [1,4,VP -> VP * PP]
35. [1,4,VP -> VP * "and" VP]
36. [4.4.PP -> Prep NP]
37. [0,4,S -> NP VP *]
38. [0,4,S' -> S *].