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: ₀ The ₁ large ₂ can ₃ can ₄ hold ₅ the ₆ water ₇

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
*constituents*: add
ADJ1: ADJ → "large" from 1 to 2
*active-arcs*: add
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
*constituents*: add
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
*active-arcs*: add
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
*constituents*: add
N2: N → "can" from 3 to 4
AUX2: AUX → "can" from 3 to 4
V2: V → "can" from 3 to 4
*active-arcs*: add
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
*constituents*: add
N3: N → "hold" from 4 to 5
V3: V → "hold" from 4 to 5
*active-arcs*: add
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
*constituents*: add
DET2: DET → "the" from 5 to 6
*active-arcs*: add
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
*constituents*: add
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
*active-arcs*: add
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

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