## Chart Parsing Example

 Grammar: 1. S → NP VP 2. NP → DET ADJ N 3. NP → DET N 4. NP → ADJ N 5. VP → AUX V NP 6. VP → V NP Lexicon: the... DET large... ADJ can... AUX, N, V hold... N, V water... N, V

Sentence: 0 The 1 large 2 can 3 can 4 hold 5 the 6 water 7

### Chart Parsing Example 2

Steps in Parsing:

```*sentence*: the   *position*: 1
*constituents*:
DET1: DET → "the" from 0 to 1
*active-arcs*:
ARC1: NP → DET1 • ADJ N from 0 to 1 [rule 2]
ARC2: NP → DET1 • N from 0 to 1     [rule 3]

*sentence*: the large   *position*: 2
ARC3: NP → DET1 ADJ1 • N from 0 to 2 [arc1*→]
ARC4: NP → ADJ1 • N from 1 to 2      [rule 4]
```

### Chart Parsing Example 3

```*sentence*: the large can  *position*: 3
NP2: NP → DET1 ADJ1 N1 from 0 to 3  [arc3*→]
NP1: NP → ADJ1 N1 from 1 to 3       [arc4*→]
N1: N → "can" from 2 to 3
AUX1: AUX → "can" from 2 to 3
V1: V → "can" from 2 to 3
ARC5: VP → V1 • NP from 2 to 3     [rule 6]
ARC6: VP → AUX1 • V NP from 2 to 3 [rule 5]
ARC7: S → NP1 • VP from 1 to 3     [rule 1]
ARC8: S → NP2 • VP from 0 to 3     [rule 1]
```

### Chart Parsing Example 4

```*sentence*: the large can can *position*: 4
N2: N → "can" from 3 to 4
AUX2: AUX → "can" from 3 to 4
V2: V → "can" from 3 to 4
ARC9: VP → AUX1 V2 • NP from 2 to 4 [arc6•→]
ARC10: VP → V2 • NP from 3 to 4     [rule 6]
ARC11: VP → AUX2 • V NP from 3 to 4 [rule 5]
```

### Chart Parsing Example 5

```*sentence*: the large can can hold
*position*: 5
N3: N → "hold" from 4 to 5
V3: V → "hold" from 4 to 5
ARC12: VP → AUX2 V3 • NP from 3 to 5 [arc11•→]
ARC13: VP → V3 • NP from 4 to 5      [rule 6]
```

### Chart Parsing Example 6

```*sentence*: the large can can hold the
*position*: 6
DET2: DET → "the" from 5 to 6
ARC14: NP → DET2 • ADJ N from 5 to 6 [rule 2]
ARC15: NP → DET2 • N from 5 to 6     [rule 3]
```

### Chart Parsing Example 7

```*sentence*: the large can can hold the water
*position*: 7
S2: S → NP1 VP2 from 1 to 7         [arc7*→]
S1: S → NP2 VP2 from 0 to 7         [arc8*→]
VP2: VP → AUX2 V3 NP3 from 3 to 7   [arc12*→]
VP1: VP → V3 NP3 from 4 to 7        [arc13*→]
NP3: NP → DET2 N4 from 5 to 7       [arc15*→]
N4: N → "water" from 6 to 7
V4: V → "water" from 6 to 7
ARC16: VP → V4 • NP from 6 to 7 [rule 6]
ARC17: S → NP3 • VP from 5 to 7 [rule 1]
```

### Chart Parsing Example 8

Doing the same steps diagrammatically:

the large can

the large can can

the large can can hold

the large can can hold the

the large can can hold the water

You are now in a position to do the exercises on grammars at http://www.cse.unsw.edu.au/~cs9414/Exercises/parsing.html

CRICOS Provider Code No. 00098G
Last updated: