CYK chart parsing algorithm
The drawback of Recursive Descent Parsing is that it causes the Left Recursion Problem and is very complex. So, CYK chart parsing was introduced. It uses the Dynamic Programming approach. CYK is one of the simplest chart parsing algorithms. The CYK algorithm is capable of constructing a chart in O(n3) time. Both CYK and Earley are Bottom-up chart parsing algorithms. But, the Earley algorithm also makes use of Top-down predictions when invalid parses are constructed.
Consider the following example of CYK parsing:
tok = ["the", "kids", "opened", "the", "box", "on", "the", "floor"] gram = nltk.parse_cfg(""" S -> NP VP NP -> Det N | NP PP VP -> V NP | VP PP PP -> P NP Det -> 'the' N -> 'kids' | 'box' | 'floor' V -> 'opened' ...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.
