[UNSW] COMP9414: Artificial Intelligence ["SCSE"]

Tutorial Solutions - Chart Parsing

*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.

CRICOS Provider Code No. 00098G