## Solutions - Chart Parsing

1. sentence: might
constituents:
NP1: NP → N1 0..1 by rule 8 & constituent N1
N1: N → "might" 0..1 by lexicon entry a
AUX1: AUX → "might" 0..1 by lexicon entry a
active-arcs:
ARC4: VP → AUX1 • V NP 0..1 by rule 2
ARC3: VP → AUX1 • V 0..1 by rule 6
ARC2: S → NP1 • VP 0..1 by rule 1
ARC1: NP → NP1 • PP 0..1 by rule 9

sentence: might might
NP2: NP → N2 1..2 by rule 8 & constituent N2
N2: N → "might" 1..2 by lexicon entry a
AUX2: AUX → "might" 1..2 by lexicon entry a
ARC8: VP → AUX2 • V NP 1..2 by rule 2
ARC7: VP → AUX2 • V 1..2 by rule 6
ARC6: S → NP2 • VP 1..2 by rule 1
ARC5: NP → NP2 • PP 1..2 by rule 9

sentence: might might prevail
S2: S → NP1 VP1 0..3 by rule 1 from ARC2
S1: S → NP2 VP2 1..3 by rule 1 from ARC6
VP2: VP → V1 2..3 by rule 5 & constituent V1
VP1: VP → AUX2 V1 1..3 by rule 6 from ARC7
V1: V → "prevail" 2..3 by lexicon entry b
ARC12: VP → VP1 • PP 1..3 by rule 4
ARC11: VP → VP2 • PP 2..3 by rule 4
ARC10: VP → AUX2 V1 • NP 1..3 from ARC8
ARC9: VP → V1 • NP 2..3 by rule 3

sentence: might might prevail over
S4: S → NP2 VP3 1..4 by rule 1 from ARC6
S3: S → NP1 VP4 0..4 by rule 1 from ARC2
VP4: VP → AUX2 V1 NP3 1..4 by rule 2 from ARC10
VP3: VP → V1 NP3 2..4 by rule 3 from ARC9
NP3: NP → N3 3..4 by rule 8 & constituent N3
N3: N → "over" 3..4 by lexicon entry c
PREP1: PREP → "over" 3..4 by lexicon entry c
ARC17: PP → PREP1 • NP 3..4 by rule 10
ARC16: VP → VP3 • PP 2..4 by rule 4
ARC15: VP → VP4 • PP 1..4 by rule 4
ARC14: S → NP3 • VP 3..4 by rule 1
ARC13: NP → NP3 • PP 3..4 by rule 9

sentence: might might prevail over hope
S7: S → NP3 VP7 3..5 by rule 1 from ARC14
VP7: VP → V2 4..5 by rule 5 & constituent V2
S6: S → NP2 VP5 1..5 by rule 1 from ARC6
S5: S → NP1 VP6 0..5 by rule 1 from ARC2
VP6: VP → VP1 PP1 1..5 by rule 4 from ARC12
VP5: VP → VP2 PP1 2..5 by rule 4 from ARC11
PP1: PP → PREP1 NP4 3..5 by rule 10 from ARC17
NP4: NP → N4 4..5 by rule 8 & constituent N4
N4: N → "hope" 4..5 by lexicon entry d
V2: V → "hope" 4..5 by lexicon entry d
ARC23: VP → VP7 • PP 4..5 by rule 4
ARC22: VP → V2 • NP 4..5 by rule 3
ARC21: VP → VP5 • PP 2..5 by rule 4
ARC20: VP → VP6 • PP 1..5 by rule 4
ARC19: S → NP4 • VP 4..5 by rule 1
ARC18: NP → NP4 • PP 4..5 by rule 9

sentence: might might prevail over hope for
PREP2: PREP → "for" 5..6 by lexicon entry e
ARC24: PP → PREP2 • NP 5..6 by rule 10

sentence: might might prevail over hope for a
ART1: ART → "a" 6..7 by lexicon entry f
active-arcs:
ARC25: NP → ART1 • N 6..7 by rule 7

sentence: might might prevail over hope for a while
S12: S → NP2 VP11 1..8 by rule 1 from ARC6
S11: S → NP1 VP12 0..8 by rule 1 from ARC2
VP12: VP → VP1 PP3 1..8 by rule 4 from ARC12
VP11: VP → VP2 PP3 2..8 by rule 4 from ARC11
PP3: PP → PREP1 NP7 3..8 by rule 10 from ARC17
S10: S → NP1 VP8 0..8 by rule 1 from ARC2
S9: S → NP2 VP9 1..8 by rule 1 from ARC6
S8: S → NP3 VP10 3..8 by rule 1 from ARC14
VP10: VP → VP7 PP2 4..8 by rule 4 from ARC23
VP9: VP → VP5 PP2 2..8 by rule 4 from ARC21
VP8: VP → VP6 PP2 1..8 by rule 4 from ARC20
NP7: NP → NP4 PP2 4..8 by rule 9 from ARC18
PP2: PP → PREP2 NP5 5..8 by rule 10 from ARC24
NP6: NP→ N5 7..8 by rule 8 & constit. N5
NP5: NP→ ART1 N5 6..8 by rule 7 from ARC25
N5: N → "while" 7..8 by lexicon entry g
CONJ3: CONJ → "while" 7..8 by lexicon entry g
ARC36: VP → VP11 • PP 2..8 by rule 4
ARC35: VP → VP12 • PP 1..8 by rule 4
ARC34: S → NP7 • VP 4..8 by rule 1
ARC33: NP → NP7 • PP 4..8 by rule 9
ARC32: VP → VP8 • PP 1..8 by rule 4
ARC31: VP → VP9 • PP 2..8 by rule 4
ARC30: VP → VP10 • PP 4..8 by rule 4
ARC29: S → NP5 • VP 6..8 by rule 1
ARC28: NP → NP5 • PP 6..8 by rule 9
ARC27: S → NP6 • VP 7..8 by rule 1
ARC26: NP → NP6 • PP 7..8 by rule 9

<Full parses in bold above; S10 not illustrated>
You should replace VERB by V, NOUN by N, and DET by ART in this diagram.

2. This is the house that Jack built.

sentence: This
constituents:
N1: N → "this" from 0 to 1 by lexicon entry a
NP1: NP → PRO1 from 0 to 1 by rule ii
active-arcs:
ARC1: NP → NP1 • VP from 0 to 1 by rule i
ARC2: NP → NP1 • REL S from 0 to 1 by rule v

sentence: This is
constituents:
V1: VERB → "is" from 1 to 2 by lexicon entry b
VP1: VP → V1 from 1 to 2 by rule vi
S1: S → NP1 VP1 from 0 to 2 from rule i from ARC1
active-arcs:
ARC3: VP → V1 • NP from 1 to 2 by rule vii

sentence: This is the
constituents:
ART1: ART → "the" from 2 to 3 by lexicon entry c
active-arcs:
ARC4: NP → ART1 • NOUN from 2 to 3 by rule iii

sentence: This is the house
constituents:
N2: NOUN → "house" from 3 to 4 by lexicon entry d
NP2: NP → ART1 N2 from 2 to 4 by rule iii from ARC4
active-arcs:
ARC4: NP → ART1 • NOUN from 3 to 4 by rule iii
ARC5: S → NP2 • VP from 2 to 4 by rule i
ARC6: NP → NP2 • REL S from 2 to 4 by rule v

sentence: This is the house that
constituents:
PRO2: PRO → "that" from 4 to 5 by lexicon entry e
REL1: REL → "that" from 4 to 5 by lexicon entry e
NP3: NP → PRO2 from 4 to 5 by rule ii
active-arcs:
ARC7: S → NP3 • VP from 4 to 5 by rule iii
ARC8: NP → NP2 REL1 • S from 3 to 5 from ARC6

sentence: This is the house that Jack
constituents:
NAME1: NAME → "Jack" from 5 to 6 by lexicon entry f
NP4: NP → NAME1 from 5 to 6 by rule iv
active-arcs:
ARC9: S → NP4 • VP from 5 to 6 by rule i
ARC10: NP → NP4 • REL S from 5 to 6 by rule v

sentence: This is the house that Jack built
constituents:
V2: VERB → "built" from 6 to 7 by lexicon entry g
VP2: VP → V2 from 6 to 7 by rule vi and constituent V2
S2: NP → NP4 VP2 from 5 to 7 by rule i from ARC9
NP3: NP → NP2 REL1 S2 from 2 to 7 by rule v from ARC8
VP3: VP → V1 NP3 from 1 to 7 by rule vii from ARC3
S3: S → NP1 VP3 from 0 to 7 by rule i from ARC1
active-arcs:
ARC11: VP → V2 • NP from 6 to 7 by rule vii

CRICOS Provider Code No. 00098G