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
    constituents: add
    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
    active-arcs: add
    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
    constituents: add
    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
    active-arcs: add
    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
    constituents: add
    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
    active-arcs: add
    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
    constituents: add
    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
    active-arcs: add
    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
    constituents: add
    PREP2: PREP → "for" 5..6 by lexicon entry e
    active-arcs: add
    ARC24: PP → PREP2 • NP 5..6 by rule 10

    sentence: might might prevail over hope for a
    constituents: add
    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
    constituents: add
    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
    active-arcs: add
    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