COMP9414/9814 - Exercises on Bottom-Up Chart Parsing

  1. Given the following lexicon and grammar information, trace the steps in chart-parsing the eight-word sentence "0 Might 1 might 2 prevail 3 over 4 hope 5 for 6 a 7 while 8".

    Grammar rules:Lexicon entries:
    1: S → NP VPa: might: NOUN AUX
    2: VP → AUX VERB NPb: prevail: VERB
    3: VP → VERB NPc: over: NOUN PREP
    4: VP → VP PPd: hope: NOUN VERB
    5: VP → VERBe: for: PREP
    6: VP → AUX VERBf: a: ART
    7: NP → ART NOUNg: while: NOUN CONJ
    8. NP → NOUN
    9. NP → NP PP
    10. PP → PREP NP

    For each word processed, you should state what new active arcs and what new constituents are added. Report the active arcs in a format exemplified below:

    ARC99: A → B1 * C D FROM 0 TO 1 by rule 17format 1 for reporting active arcs
    ARC101: A → B1 C2 * D FROM 0 TO 2 from ARC99format 2 for reporting active arcs

    Similarly, report new constituents in a format exemplified below:

    A33: A → B1 C2 D3 FROM 0 TO 3 by rule 17 from ARC101format 1 for reporting constituents
    A55: A → B1 FROM 4 TO 5 by rule 99 & constituent B1format 2 for reporting constituents
    E66: E → "word" FROM 4 TO 5 by lexicon entry xformat 3 for reporting constituents

    Rule 17 would be a grammar rule that read 17: A → B C D, rule 99 would be a grammar rule that read 99: A → B, and lexicon entry x would read x: word: E ... where the "... " indicates that there could be other lexical categories of which "word" is a member. The label to the left of a new constituent should be of the form <name of the constituent type> followed by a unique identifying number. For example, if the new constituent was an NP, and it was the third one found by the algorithm, you could call it NP3.

    It is not necessary to draw a diagram showing constituents and/or arcs - you can if you want to.

  2. Given the grammar rules and lexicon shown below, use the chart-parsing algorithm, as above, to parse the sentence 0 This 1 is 2 the 3 house 4 that 5 Jack 6 built 7 .
    Grammar rules:   andLexicon:
    i. S → NP VPv. NP → NP REL Sa. this: PRO   e. that: PRO, REL
    ii. NP → PROvi. VP → VERBb. is: VERBf. Jack: NAME
    iii. NP → ART NOUN     vii. VP → VERB NPc. the: ARTg. built: VERB
    iv. NP → NAME d. house: NOUN

CRICOS Provider Code No. 00098G