Chart parser: Example Grammar 1. S -> NP VP 2. NP -> Pronoun 3. NP -> Noun 4. VP -> VG 5. VP -> VG NP 6. VG -> Verb 7. VG -> Modal Verb Lexicon can -- Modal, Verb, Noun fish -- Noun, Verb I -- Pronoun Trace of the chart parsing algorithm on the sentence "I can fish" Edges in Chart C1: CHART-PARSE("I can fish",GRAMMAR) C2: ADD-EDGE([0,0,S'-> * S]) 1. [0,0,S'->* S] C3: PREDICTOR([0,0,S' -> * S]) Match S after * with rule (1) C4: ADD-EDGE([0,0,S -> * NP VP] 2. [0,0,S -> * NP VP] C5: PREDICTOR([0,0,S -> * NP VP]) Match NP after * with rule (2) C6: ADD-EDGE([0,0,NP -> * Pronoun]) 3. [0,0,NP -> * Pronoun] C7: PREDICTOR([0,0,NP -> * Pronoun]) C7 returns C6 returns C5 continues: Match NP after * with rule (3) C8: ADD-EDGE([0,0,NP -> * Noun]) 4. [0,0,NP -> * Noun] C9: PREDICTOR([0,0,NP -> * Noun]) C9, C8, C5, C4, C3, and C2 return. C1 continues C10: SCANNER(0,"I") Match "I" with "Pronoun" following the * in edge (3). C11: ADD-EDGE([0,1,NP->Pronoun *] 5. [0,1,NP -> Pronoun *] C12: EXTENDER([0,1,NP->Pronoun *]) Match the "NP" on the right side of this edge with the "NP" after the dot in edge (2) Note that edge 2 ends at 0, where this edge begins. C13: ADD-EDGE([0,1,S->NP * VP]) 6. [0,1,S->NP * VP]) C14: PREDICTOR([0,1,S->NP * VP]) Match VP after * with rule 4 C15: ADD-EDGE([1,1,VP -> * VG]) 7. [1,1,VP->* VG] C16: PREDICTOR([1,1,VP -> * VG]) Match VG after * with rule 6 C17: ADD-EDGE([1,1,VG -> * Verb]) 8. [1,1,VG -> * Verb]) C18: PREDICTOR([1,1,VG->* Verb]) C18 and C17 return C16 continues: Match VG after * with rule 7 C19: ADD-EDGE([1,1,VG->* Modal Verb]) 9. [1,1,VG->* Modal Verb] C20: PREDICTOR([1,1,VG->* Modal Verb]) C20, C19, C16, C15 return C14 continues Match VP after * with rule 5 C21: ADD-EDGE([1,1,VP-> * VG NP]) 10. [1,1,VP->* VG NP] C22: PREDICTOR([1,1,VP-> * VG NP]) Match VG after * with rule 6 C23: ADD-EDGE([1,1,VG -> * Verb]) Edge already in chart. C23 returns. C22 continues Match VG after * with rule 7 C24: ADD-EDGE([1,1,VG->* Modal Verb]) Edge already in chart. C24, C22, C21, C14, C13, C12, C11, C10 return C1 continues C25: SCANNER(1,"can") Match "can" with Modal following * in edge 9. C26: ADD-EDGE([1,2,VG -> Modal * Verb]) 11. [1,2,VG->Modal * Verb] C27: PREDICTOR([1,2,VG->Modal * Verb]) C27, C26 return C25 continues: Match "can" with Verb following * in edge 8 C28: ADD-EDGE([1,2,VG->Verb *]) 12. [1,2,VG->Verb *] C29: EXTENDER([1,2,VG->Verb *]) Match this as extension of edge 7. C30: ADD-EDGE([1,2,VP->VG *]) 13. [1,2,VP->VG *]) C31: EXTENDER([1,2,VP->VG *]) Match this as extension of edge 6. C32: ADD-EDGE([0,2,S->NP VP *]) 14. [0,2,S->NP VP *] C33: EXTENDER([0,2,S->NP VP *]) Match this as extension of edge 1. C34: ADD-EDGE([0,2,S'->S *]) 15. [0,2,S'->S *] C35: EXTENDER([0,2,S'->S *]) C35, C34, C33, C32, C30 return C29 continues Match [1,2,VG-> Verb *] as extension of edge 10 C36: ADD-EDGE([1,2,VP -> VG * NP] 16. [1,2,VP->VG * NP] C37: PREDICTOR([1,2,VP->VG * NP] Match NP with rule 2 C38: ADD-EDGE([2,2,NP->* Pronoun] 17. [2,2,NP->* Pronoun] C39: PREDICTOR([2,2,NP->* Pronoun]17. C39, C38 return C37 continues: Match NP with rule 3 C40: ADD-EDGE([2,2,NP->* Noun]) 18. [2,2,NP->* Noun] C41: PREDICTOR([2,2,NP-> * Noun] C41, C40, C37, C29, C28 returns Note that the scanner C25 does not attempt to read "can" as a noun, because there is no edge looking for a noun at this point. C25 returns C1 continues C42: SCANNER(2,"fish") Match "fish" with Verb in edge 11. C43: ADD-EDGE([1,3,VG->Modal Verb *]) 19. [1,3,VG->Modal Verb *] C44: EXTENDER([1,3,VG->Modal Verb *]) Match this as extension of edge 7 C45: ADD-EDGE([1,3,VP->VG *]) 20. [1,3,VP->VG *] C46: EXTENDER([1,3,VP->VG *]) Match this as extension of edge 6 C47: ADD-EDGE([0,3,S->NP VP *]) 21. [0,3,S->NP VP *] C48: EXTENDER([0,3,S-> NP VP *]) Match this as extension of edge 1 C49: ADD-EDGE([0,3,S'->S *]) 22. [0,3,S'->S *] C50: EXTENDER([0,3,S'->S *]) C50, C49, C48, C47, C46, C45 return C44 continues. Match [1,3,VG->Modal Verb *] as extension of edge 10 C45: ADD-EDGE([1,3,VP -> VG * NP]) 23 [1,3,VP -> VG * NP] I abbreviate: Adds two edges 24. [3,3,NP->* Pronoun] 25. [3,3,NP->* Noun] C45, C44, C43 return C42 continues Match "fish" with Noun in edge 18 C46: ADD-EDGE([2,3,NP -> Noun *]) 26. [2,3,NP->Noun *] C47: EXTENDER([2,3,NP->Noun *]) Match as extension of edge 16 C48: ADD-EDGE(1,3,VP->VG NP *]) 27. [1,3,VP->VG NP *]) C49: EXTENDER(1,3,VP->VG NP *]) Match as extension of edge 6 C50: ADD-EDGE([0,3,S->NP VP *]) edge already in chart. C50, C49, C48, C47, C46, C42, C1 return.