20
  • Given the lexicon and grammar information below, trace the steps in chart-parsing the two sentences Time flies. It flies like an arrow.

    Lexicon must cover any words to be processed.
    timeNOUN, VERB
    fliesNOUN, VERB
    itPRONOUN
    likePREP, ADJ, VERB, NOUN, ADV, CONJ
    anDET
    arrowNOUN

    Grammar
    RuleName
    S → NP VPG-S1
    S → VERB NPG-S2
    NP → NOUNG-NP1
    NP → PRONOUNG-NP2
    NP → DET NOUNG-NP3
    PP → PREP NPG-PP1
    VP → VERBG-VP1
    VP → VERB PPG-VP2

    Note: The numbers that are part of active arc names are not especially significant. All that matters is that different arcs have different names.