Chart Parsing in Artificial Intelligence

Chart Parsing:

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(n³) time. In many cases, it will perform better than this and will parse most of the sentences in O(n²) or even O(n) time.