1. S → NP VP |
the... DET |

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

*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*: thelarge*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]

*sentence*: the largecan*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]

*sentence*: the large cancan*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]

*sentence*: the large can canhold*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]

*sentence*: the large can can holdthe*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]

*sentence*: the large can can hold thewater*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]

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:

Copyright © Bill Wilson, 2008, except where another source is acknowledged.