Review of Parsing

Sue the guy with the mustache.

To simplify things, the full features paths aren't shown, and word and phrase categories are shown like this: "NP:"

Bottom-up, depth-first
1. Sue can be either a noun or a verb. Let's start with the noun reading.
```
N:sue
```
2. A noun can be the head of an NP.
```
NP:[HEAD [N:sue]]
```
3. An NP can be the subject (COMP1) of an S.
```
S:[HEAD ?
   COMP1 [NP:[HEAD [N:sue]]]
   MOOD declarative]
```
4. We can't go any further with this, so it's back to the input. The has to be a determiner, and a determiner has to be the head of a DetP, and a DetP has to be the COMP of an NP. The "(MOD)" indicates that the NP has an optional modifier.
```
Det:the

DetP:[HEAD [Det:the]]

NP:[HEAD ?
    COMP [DetP:[HEAD [Det:the]]]
    (MOD)]
```
5. To go any further, we need to go back to the input. Guy has to be a noun, the head of an NP that requires a COMP DetP.
```
N:guy

NP:[HEAD [N:guy]
    COMP [DetP:[HEAD [Det:the]]]
    (MOD)]
```
6. This NP can't be incorporated in the S, but since this is a dumb bottom-up parser, it doesn't know that the VP has to come now, so we go back to the input. With, the, and mustache are unambiguously preposition, determiner and noun, making a PP.
```
Prep:with

PP:[HEAD [Prep:with]
    COMP ?]

Det:the

DetP:[HEAD [Det:the]]

NP:[HEAD ?
    COMP [DetP:[HEAD [Det:the]]]]

N:mustache

NP:[HEAD [N:mustache]
    COMP [DetP:[HEAD [Det:the]]]]

PP:[HEAD [Prep:with]
    COMP [NP:[HEAD [N:mustache]
              COMP [DetP:[HEAD [Det:the]]]]]]
```
7. It is possible to make the PP the modifier of the previous NP, and there is no other place to attach it yet. Let's go ahead and do it.
```
NP:[HEAD [N:guy]
    COMP [DetP:[HEAD [Det:the]]]
    MOD [PP:[HEAD [Prep:with]
             COMP [NP:[HEAD [N:mustache]
                       COMP [DetP:[HEAD [Det:the]]]]]]]]
```
8. Now we're out of words, but the S is still waiting for its head. None of the completed constituents unifies with this. So we have to backtrack to a choice point. The only one was the point where we picked the noun over the verb sue. So we try the verb reading. This leads us all the way up to the imperative S, the only one that the VP can be the head of because of the ordering constraints (which aren't shown).
```
V:sue

VP:[HEAD [V:sue]
    COMP ?
    (MOD)]

S:[HEAD [VP:[HEAD [V:sue]
             COMP ?
             (MOD)]]
   COMP [HEAD [N:you]
         PHON <>]
   MOOD imperative]
```
9. Now, making a long story short, we go back to the input, and if this is a chart parser, we don't have to reparse the NP. This gives us the following.
```
S:[HEAD [VP:[HEAD [V:sue]
             COMP [NP:[HEAD [N:guy]
                       COMP [DetP:[HEAD [Det:the]]]
                       MOD [PP:[HEAD [Prep:with]
                                COMP [NP:[HEAD [N:mustache]
                                          COMP [DetP:[HEAD [Det:the]]]]]]]]]
             (MOD)]]
   COMP [NP:[HEAD [N:you]
             PHON <>]]
   COMP2 
   MOOD imperative]
```
10. But if we want all parses, we are missing one, the one where the PP is attached to the VP. We realize this if we recognize that we could have unified the smaller NP (the guy) with the direct object slot as well.
```
S:[HEAD [VP:[HEAD [V:sue]
             COMP [NP:[HEAD [N:guy]
                       COMP [DetP:[HEAD [Det:the]]]]]
             MOD [PP:[HEAD [Prep:with]
                      COMP [NP:[HEAD [N:mustache]
                                COMP [DetP:[HEAD [Det:the]]]]]]]]]
   COMP [NP:[HEAD [N:you]
             PHON <>]]
   MOOD imperative]
```

Top-down, breadth-first

Say there are just two S rules, one declarative, the other imperative.

S:[HEAD ?
   COMP ?
   MOOD declarative]

S:[HEAD ?
   COMP [NP:[HEAD [N:you]
             PHON <>]]
   MOOD imperative]

We try to expand each of these just one step. Say there only two kinds of non-empty NPs and two kinds of VPs.

S:[HEAD ?
   COMP [NP:[HEAD [N]]
   MOOD declarative]

S:[HEAD ?
   COMP [NP:[HEAD [N]
             COMP [DetP]]]
   MOOD declarative]

S:[HEAD [VP:[HEAD [V]]
   COMP [NP:[HEAD [N:you]
             PHON <>]]
   MOOD imperative]

S:[HEAD [VP:[HEAD [V]
             COMP [NP]]]
   COMP [NP:[HEAD [N:you]
             PHON <>]]
   MOOD imperative]

Proceeding one step further with each branch, we get the following. Note that the intransitive VP path doesn't pan out because sue is a transitive verb (it subcategorizes for two NPs).

S:[HEAD ?
   COMP [NP:[HEAD [N:sue]]
   MOOD declarative]

S:[HEAD ?
   COMP [NP:[HEAD [N]
             COMP [DetP [HEAD [Det]]]]]
   MOOD declarative]

S:[HEAD [VP:[HEAD [sue]
             COMP [NP]]]
   COMP [NP:[HEAD [N:you]
              PHON <>]]
   MOOD imperative]

Beyond this point it gets tiring. The rest is left as an exercise to the reader.

[L645 Syllabus]

Last modified: Thu Oct 16 23:21:23 EST
Comments: gasser@cs.indiana.edu