Chart parser

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Chart parser" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

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. This eliminates backtracking and prevents a combinatorial explosion.

Chart parsing is generally credited to Martin Kay.^[1]