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

Tutorial Week 7 - Bottom-Up Chart Parsing

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 0..1 by rule 17format 1 for reporting active arcs
ARC101: A -> B1 C1 * D 0..2 from ARC99format 2 for reporting active arcs
Similarly, report new constituents in a format exemplified below:

A33: A -> B1 C2 D3 0..3 by rule 17 from ARC101format 1 for reporting constituents
A55: A -> B1 4..5 by rule 99 & constituent B1format 2 for reporting constituents
E66: E -> "word" 4..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.

Print me with netscape, not mosaic. Mosaic gets confused when trying to print tables.

CRICOS Provider Code No. 00098G