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 
