Chart parser

In computer science, a chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages).

It uses the dynamic programming approach—partial hypothesized results are stored in a structure called a chart and can be re-used.

Chart parsing is generally credited to Martin Kay.

However their lower efficiency has led to people avoiding them for most compiler work.

Chart parsers are distinguished between top-down and bottom-up, as well as active and passive.