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.
Read more about this topic: Chart Parser
Famous quotes containing the words types of, types and/or chart:
“The wider the range of possibilities we offer children, the more intense will be their motivations and the richer their experiences. We must widen the range of topics and goals, the types of situations we offer and their degree of structure, the kinds and combinations of resources and materials, and the possible interactions with things, peers, and adults.”
—Loris Malaguzzi (1920–1994)
“If there is nothing new on the earth, still the traveler always has a resource in the skies. They are constantly turning a new page to view. The wind sets the types on this blue ground, and the inquiring may always read a new truth there.”
—Henry David Thoreau (1817–1862)
“Perhaps in His wisdom the Almighty is trying to show us that a leader may chart the way, may point out the road to lasting peace, but that many leaders and many peoples must do the building.”
—Eleanor Roosevelt (1884–1962)