Construct a chart parse using CFG G, given below, for this ambiguous sentence: refuse discount hardship

Sample Question Answer(for understanding)

robot reports leak

0 1 2 3

G = {

S → NP VP

NP → N | AttrNP

VP → V | VP NP

AttrNp → NP N

N → robot | reports | leak

V → reports | leak

}

row 0: ℇ

Anticipate S, NP variants, and AttrNP

0.a S → • NP VP [0,0] anticipate complete parse

0.b NP → • N [0,0] anticipate NP variant to start 0.a

0.c NP → • AttrNP [0,0] anticipate NP variant to start 0.a

0.d AttrNP → • NP N [0,0] anticipate NP to complete 0.c

row 1: robot

Complete NP, start AttrNP and S, anticipate VPs

1.a N → robot • [0,1] scan

1.b NP → N • [0,1] use 1.a to complete 0.b

1.c S → NP • VP [0,1] use 1.b to continue 0.a

1.d VP → • V [1,1] anticipate VP to complete 1.c

1.e VP → • VP NP [1,1] anticipate VP to complete 1.c

1.f AttrNP → NP • N [0,1] use 1.b to continue 0.d

row 2: reports

Scan N — complete AttrNP and NP, start S, and recursively start AttrNP;

anticipate VPs

2.a N → reports • [1,2] scan

2.b AttrNP → NP N • [0,2] use 2.a to complete 1.f

2.c NP → AttrNP • [0,2] use 2.b to complete 0.c

2.d S → NP • VP [0,2] use 2.c to continue 0.a

2.e VP → • V [2,2] anticipate VP to complete 2.d

2.f VP → • VP NP [2,2] anticipate VP to complete 2.d

2.g AttrNP → NP • N [0,2] use 2.c to continue 0.d

Scan V — complete one VP variant & S; start the other VP variant;

anticipate NP/AttrNP

2.h V → reports • [1,2] scan

2.i VP → V • [1,2] anticipate VP to complete 1.c

2.j S → NP VP • [0,2] use 2.i to "complete" 1.c

2.k VP → VP • NP [1,2] use 2.i to continue 1.e

2.l NP → • N [2,2] anticipate NP variant to complete 2.k

2.m NP → • AttrNP [2,2] anticipate NP variant to complete 2.k

2.n AttrNP → • NP N [2,2] anticipate AttrNP to complete 2.m

CSC 520 S20 chart parse lab Page 1

row 3: leak

Scan N — complete [0,3] AttrNP and NP, start S, and recursively start

AttrNP; anticipate VP; complete [2,3] NP, complete [1,3] VP,

completes S[0,3]

3.a N → leak • [2,3] scan

3.b AttrNP → NP N • [0,3] use 3.a to complete 2.g

3.c NP → AttrNP • [0,3] use 3.b to complete 0.c

3.d S → NP • VP [0,3] use 3.c to continue 0.a

3.e VP → • V [3,3] anticipate VP variant to complete 3.d

3.f VP → • VP NP [3,3] anticipate VP variant to complete 3.d

3.g AttrNP → NP • N [0,3] use 3.c to continue 0.d

3.h NP → N • [2,3] use 3.a to complete 2.l

3.i VP → VP NP • [1,3] use 3.h to complete 2.k

3.j S → NP VP • [0,3] use 3.i to complete 1.

3.k AttrNP → NP • N [2,3] use 3.h to continue 2.n

3.l VP → VP • NP [1,3] use 3.i to continue 1.e

(anticipate NP variants)

Scan V — completes VP [2,3], and S[0,3]; start VP [2,3], anticipate NP/AttrNP

3.m V → leak • [2,3] scan

3.n VP → V • [2,3] apply 3.m to 2.e

3.o S → NP VP • [0,3] apply 3.n to 2.d

3.p VP → VP • NP [2,3] apply 3.n to 2.f

3.q NP → • N [3,3] anticipate for 3.p & 3.l

3.r NP → • AttrNP [3,3] anticipate for 3.p & 3.l

3.s AttrNP → • NP N [3,3] anticipate for 3.r

CSC 520 S20 chart parse lab Page 2