Chart parser
This article needs additional citations for verification. (December 2009) |
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]
Types of chart parsers
A common approach is to use a variant of the
Chart parsers can also be used for parsing computer languages. Earley parsers in particular have been used in
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.
Chart parsers are distinguished between top-down and bottom-up, as well as active and passive.
See also
References
- ^ "Chart Parsing" (PDF). Archived from the original (PDF) on 21 February 2015. Retrieved 20 November 2011.