~2025-32570-03: /* Types of chart parsers */

2025-11-10T12:04:06Z

Types of chart parsers

← Previous revision		Revision as of 12:04, 10 November 2025
Line 8:		Line 8:
	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 algorithm\|Cocke-Younger-Kasami]] (CYK) algorithm.		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 algorithm\|Cocke-Younger-Kasami]] (CYK) algorithm.

	Chart parsers can also be used for parsing computer languages. Earley parsers in particular have been used in [[compiler-compiler]]s 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.		Chart parsers can also be used for parsing computer languages. Earley parsers in particular have been used in [[compiler-compiler]]s 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 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.

imported>Citation bot: Removed parameters. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Parsing algorithms | #UCB_Category 25/25

2024-11-29T12:44:58Z

Removed parameters. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Parsing algorithms | #UCB_Category 25/25

New page

{{Short description|Type of parser for ambiguous grammars}}
{{More citations needed|date=December 2009}}
In [[computer science]], a '''chart parser''' is a type of [[parsing|parser]] suitable for [[ambiguous grammar]]s (including grammars of [[natural language]]s). 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]].<ref>{{cite web |url=http://webdocs.cs.ualberta.ca/~lindek/650/papers/chartParsing.pdf |title=Chart Parsing |accessdate=20 November 2011 |url-status=dead |archiveurl=https://web.archive.org/web/20150221021038/http://webdocs.cs.ualberta.ca/~lindek/650/papers/chartParsing.pdf |archivedate=21 February 2015 }}</ref>

== 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 algorithm|Cocke-Younger-Kasami]] (CYK) algorithm.

Chart parsers can also be used for parsing computer languages. Earley parsers in particular have been used in [[compiler-compiler]]s 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.

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

== See also ==
* [[Brute-force search]]

== References ==
{{reflist}}

== External links ==
* [https://bishoy.github.io/ArcExtensionAlgorithm/ Bottom-up Chart parsing Web Implementation]

{{Parsers}}

{{DEFAULTSORT:Chart Parser}}
[[Category:Natural language parsing]]
[[Category:Parsing algorithms]]

Chart parser - Revision history

~2025-32570-03: /* Types of chart parsers */

imported>Citation bot: Removed parameters. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Parsing algorithms | #UCB_Category 25/25