Earley chart parsing algorithm
Earley algorithm was given by Earley in 1970. This algorithm is similar to Top-down parsing. It can handle left-recursion, and it doesn't need CNF. It fills in a chart in the left to right manner.
Consider an example that illustrates parsing using the Earley chart parser:
>>> import nltk >>> nltk.parse.earleychart.demo(print_times=False, trace=1,sent='I saw a dog', numparses=2) * Sentence: I saw a dog ['I', 'saw', 'a', 'dog'] |. I . saw . a . dog .| |[---------] . . .| [0:1] 'I' |. [---------] . .| [1:2] 'saw' |. . [---------] .| [2:3] 'a' |. . . [---------]| [3:4] 'dog' |> . . . .| [0:0] S -> * NP VP |> . . . .| [0:0] NP -> * NP PP |> . . . .| [0:0] NP -> * Det Noun |> . . . .| [0:0] NP -> * 'I' |[---------] . . .| ...
Get Natural Language Processing: Python and NLTK now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
