Chart Parsing in Artificial Intelligence
The chart is a record of all the substructures built during parsing. It is also known as a well-formed substring table. Chart parsing works on the principle of Dynamic Programming. It uses and stores solutions of the smaller part of a sentence to solve larger problems.
Chart parsing works incrementally word by word. In the worst case, chart parsing will parse a sentence of n words in O(n3) time. In many cases, it will perform better than this and will parse most of the sentences in O(n2) or even O(n) time.