Chart Parsing

===================== Grammar ====================

S  -> Aux NP VP
NP -> Det Noun
NP -> Noun
VP -> Verb NP

====================== Goal ======================

Parse "Does this boy like pets?"

----------------- Initialization -----------------
Agenda
e(0, 0, S -> .Aux NP VP)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(0, 0, Aux -> .Does)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(0, 1, Aux -> Does.)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(0, 1, S -> Aux(Does) .NP VP)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(1, 1, NP -> .Det Noun)
e(1, 1, NP -> .Noun)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Det Noun)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Det Noun)
e(1, 1, NP -> .Noun)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Det Noun)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)

------- Rule Invocation & Fundamental Rule -------
------- Rule Invocation & Fundamental Rule -------
Agenda
e(1, 2, Det -> this.)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Det Noun)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(1, 2, NP -> Det(this) .Noun)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(2, 3, Noun -> boy.)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(1, 3, NP -> Det(this) Noun(boy).)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(3, 3, VP -> .Verb NP)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(3, 3, Verb -> .like)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(3, 4, Verb -> like.)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(3, 4, VP -> Verb(like) .NP)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(4, 4, NP -> .Det Noun)
e(4, 4, NP -> .Noun)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)
e(3, 4, VP -> Verb(like) .NP)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(4, 4, NP -> .Noun)
e(4, 4, Det -> .this)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)
e(3, 4, VP -> Verb(like) .NP)
e(4, 4, NP -> .Det Noun)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(4, 4, Det -> .this)
e(4, 4, Noun -> .boy)
e(4, 4, Noun -> .pets)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)
e(3, 4, VP -> Verb(like) .NP)
e(4, 4, NP -> .Det Noun)
e(4, 4, NP -> .Noun)

------- Rule Invocation & Fundamental Rule -------
------- Rule Invocation & Fundamental Rule -------
Agenda
e(4, 4, Noun -> .pets)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)
e(3, 4, VP -> Verb(like) .NP)
e(4, 4, NP -> .Det Noun)
e(4, 4, NP -> .Noun)
e(4, 4, Det -> .this)
e(4, 4, Noun -> .boy)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(4, 5, Noun -> pets.)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)
e(3, 4, VP -> Verb(like) .NP)
e(4, 4, NP -> .Det Noun)
e(4, 4, NP -> .Noun)
e(4, 4, Det -> .this)
e(4, 4, Noun -> .boy)
e(4, 4, Noun -> .pets)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(4, 5, NP -> Noun(pets).)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)
e(3, 4, VP -> Verb(like) .NP)
e(4, 4, NP -> .Det Noun)
e(4, 4, NP -> .Noun)
e(4, 4, Det -> .this)
e(4, 4, Noun -> .boy)
e(4, 4, Noun -> .pets)
e(4, 5, Noun -> pets.)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(3, 5, VP -> Verb(like) NP(Noun(pets)).)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)
e(3, 4, VP -> Verb(like) .NP)
e(4, 4, NP -> .Det Noun)
e(4, 4, NP -> .Noun)
e(4, 4, Det -> .this)
e(4, 4, Noun -> .boy)
e(4, 4, Noun -> .pets)
e(4, 5, Noun -> pets.)
e(4, 5, NP -> Noun(pets).)

------- Rule Invocation & Fundamental Rule -------
Agenda
e(0, 5, S -> Aux(Does) Det(this) Noun(boy) VP(Verb(like) NP(Noun(pets))).)

Chart
e(0, 1, Does.)
e(1, 2, this.)
e(2, 3, boy.)
e(3, 4, like.)
e(4, 5, pets.)
e(0, 0, S -> .Aux NP VP)
e(0, 0, Aux -> .Does)
e(0, 1, Aux -> Does.)
e(0, 1, S -> Aux(Does) .NP VP)
e(1, 1, NP -> .Noun)
e(1, 1, Det -> .this)
e(1, 1, Noun -> .boy)
e(1, 1, Noun -> .pets)
e(1, 2, Det -> this.)
e(1, 2, NP -> Det(this) .Noun)
e(2, 2, Noun -> .boy)
e(2, 2, Noun -> .pets)
e(2, 3, Noun -> boy.)
e(1, 3, NP -> Det(this) Noun(boy).)
e(0, 3, S -> Aux(Does) NP(Det(this) Noun(boy)) .VP)
e(3, 3, VP -> .Verb NP)
e(3, 3, Verb -> .like)
e(3, 4, Verb -> like.)
e(3, 4, VP -> Verb(like) .NP)
e(4, 4, NP -> .Det Noun)
e(4, 4, NP -> .Noun)
e(4, 4, Det -> .this)
e(4, 4, Noun -> .boy)
e(4, 4, Noun -> .pets)
e(4, 5, Noun -> pets.)
e(4, 5, NP -> Noun(pets).)
e(3, 5, VP -> Verb(like) NP(Noun(pets)).)

===================== Result =====================

e(0, 5, S -> Aux(Does) NP(Det(this) Noun(boy)) VP(Verb(like) NP(Noun(pets))).)

                 S
           /     |      \
        Aux      NP      VP
        /       /  \    /  \
       |      Det Noun Verb NP
       |       |   |   |    |
       |       |   |   |   Noun
       |       |   |   |    |  
      Does   this boy like pets