Solutions COMP348 week 8 
========================

POS
---

1. The graph should be easy to draw

2. P(N|{}) * P(time|N) * P(V|N) * P(flies|V) * P(P|V) * P(like|P) *
P(D|P) * P(an|D) * P(N|D) * P(arrow|N) = ...

3. Fruit/NN flies/VBZ like/IN the/DT oranges/NNS like/VBP giraffes/NNS
like/IN the/DT leaves/NNS
 - No rules apply to Fruit/NN: no changes
 - No rules apply to flies/VBZ: no changes
 - Rule 7 applies to like/IN: 
Fruit/NN flies/VBZ *like/VPB* the/DT oranges/NNS like/VPB giraffes/NNS
like/IN the/DT leaves/NNS
 - and so on

PARSING
-------

1. Trace:
S
NP VP
Pron VP
"I" VP
"I" V NP
"I" "read" NP
"I" "read" Pron (it won't work so eventually we'll backtrack)
"I" "read" "I" (No match; backtrack)
"I" "read" Det N (it won't work either so eventually we'll backtrack)
"I" "read" "the" N
"I" "read" "the" "book" (there are still elements in the sentence; 
                         backtrack)
"I" "read" Det N PP
"I" "read" "the" N PP
"I" "read" "the" "book" PP
"I" "read" "the" "book" P NP
"I" "read" "the" "book" "in" NP
"I" "read" "the" "book" "in" Pron (Again, we'll backtrack here)
"I" "read" "the" "book" "in" "I" (no match; backtrack)
"I" "read" "the" "book" "in" Det N
"I" "read" "the" "book" "in" "the" N
"I" "read" "the" "book" "in" "the" "park" (in theory it will try
                                           "book" first)

2. Trace of shift reduce:

   Stack             Sentence                        Action
                     I read the book in the park
   I                 read the book in the park       Shift
   Pron              read the book in the park       Reduce
   NP                read the book in the park       Reduce
   NP read           the book in the park            Shift
   NP V              the book in the park            Reduce
   NP V the          book in the park                Shift
   NP V Det          book in the park                Reduce
   NP V Det book     in the park                     Shift
   NP V Det N        in the park                     Reduce
   NP V NP           in the park                     Reduce; wrong move
   NP VP             in the park                     Reduce
   S                 in the park                     Reduce
   S in              the park                        Shift
   S P               the park                        Reduce
   S P the           park                            Shift
   S P Det           park                            Reduce
   S P Det park                                      Shift
   S P Det N                                         Reduce
   S P NP                                            Reduce
   S PP                                              Reduce
   Parse failed; we need to backtrack

3. Chart table

See spreadsheet; this is a very laborious task so just show one or two
iterations and ask students to try out just a couple of the cells.


      0 I 1 read 2 the 3 book 4 in 5 the 6 park 7
0         
I
1
read
2
the
3
book
4
in
5
the
6
park
7