HW-2

Computer Science

Theory of Computing (Csc 520 Course)

1.(12.5points). 

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

refuse discount hardship

0  1  2 3

Note that in G, an S can simply be a VP, as in the imperative English sentences look before you leap or live for today. 

For full credit, your chart parse should capture all three of these

Meanings:

• As a VP that is a complete S, refuse discount hardship could mean do not stint on the suffering.

• refuse as an N could mean unwanted people, as in the Emma Lazarus Statue of Liberty poem:

…Give me your tired, your poor,

Your huddled masses yearning to breathe free,

The wretched refuse of your teeming shore. …

With that sense of refuse, refuse discount hardship could mean that those whom Liberty gathers downplay their difficulties.

• refuse as a noun could also mean objects people throw away. So, as an NP, not in itself an S,

refuse discount hardship could mean something like a difficulty caused by a lack of coupons

at thrift stores.

Include all entries, even if they are not continued on subsequent rows, as well as all complete

parses for S that do not consume the entire input string.

G = {

S → NP VP | VP

NP → N | AttrNP

AttrNP → NP N

VP → V | VP NP

N → discounts | hardship | refuse

V → discount | refuse |

}

Remember that—

AttrNP stands for attribute noun phrase, where one noun modifies another

HW-2(2)

Computer Science

Theory of Computing (Csc 520 Course)

1.(12.5points).

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

refuse discount hardship

0 1 2 3

Note that in G, an S can simply be a VP, as in the imperative English sentences look before you leap or live for today.

For full credit, your chart parse should capture all three of these

Meanings:

• As a VP that is a complete S, refuse discount hardship could mean do not stint on the suffering.

• refuse as an N could mean unwanted people, as in the Emma Lazarus Statue of Liberty poem:

…Give me your tired, your poor,

Your huddled masses yearning to breathe free,

The wretched refuse of your teeming shore. …

With that sense of refuse, refuse discount hardship could mean that those whom Liberty gathers downplay their

difficulties.

• refuse as a noun could also mean objects people throw away. So, as an NP, not in itself an S,

refuse discount hardship could mean something like a difficulty caused by a lack of coupons

at thrift stores.

Include all entries, even if they are not continued on subsequent rows, as well as all complete

parses for S that do not consume the entire input string.

G = {

S → NP VP | VP

NP → N | AttrNP

AttrNP → NP N

VP → V | VP NP

N → discounts | hardship | refuse

V → discount | refuse |

}

Remember that—

AttrNP stands for attribute noun phrase, where one noun modifies another

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