Chart parser
It is proposed that this article be deleted.
If you can address this concern by improving, copyediting, sourcing, renaming, or merging the page, please edit this page and do so. You may remove this message if you improve the article or otherwise object to deletion for any reason. Although not required, you are encouraged to explain why you object to the deletion, either in your edit summary or on the talk page. If this template is removed, do not replace it. This message has remained in place for seven days, so the article may be deleted without further notice. Find sources: "Chart parser" – news · newspapers · books · scholar · JSTOR Nominator: Please consider notifying the author/project: {{subst:proposed deletion notify|Chart parser|concern=}} ~~~~Timestamp: 20111026200046 20:00, 26 October 2011 (UTC) Administrators: delete |
 |
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 was developed by Martin Kay.
Types of chart parsers
A common approach is to use a variant of the Viterbi algorithm. The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named for its inventor. Another chart parsing algorithm is the Cocke-Younger-Kasami (CYK) algorithm.
Chart parsers can also be used for parsing computer languages. Earley parsers in particular have been used in compiler compilers where their ability to parse using arbitrary Context-free grammars eases the task of writing the grammar for a particular language. However their lower efficiency has led to people avoiding them for most compiler work.
In bidirectional chart parsing, edges of the chart are marked with a direction, either forwards or backwards, and rules are enforced on the direction in which edges must point in order to be combined into further edges.
In incremental chart parsing, the chart is constructed incrementally as the text is edited by the user, with each change to the text resulting in the minimal possible corresponding change to the chart.
We can distinguish top-down and bottom-up chart parsers, and active and passive chart parsers.
Parsing ambiguity in natural languages
The most serious problem faced by parsers is the ambiguity of natural languages.