Chart parser
Encyclopedia
A chart parser is a type of parser
suitable for ambiguous grammars (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 was developed by Martin Kay
.
. 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
In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
suitable for ambiguous grammars (including grammars of natural language
Natural language
In the philosophy of language, a natural language is any language which arises in an unpremeditated fashion as the result of the innate facility for language possessed by the human intellect. A natural language is typically used for communication, and may be spoken, signed, or written...
s). It uses the dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
approach—partial hypothesized results are stored in a structure called a chart and can be re-used. This eliminates backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
and prevents a combinatorial explosion
Combinatorial explosion
In administration and computing, a combinatorial explosion is the rapidly accelerating increase in lines of communication as organizations are added in a process...
.
Chart parsing was developed by Martin Kay
Martin Kay
Martin Kay is a computer scientist known especially for his work in computational linguistics.Born and raised in the United Kingdom, he received his M.A. from Trinity College, Cambridge, in 1961. In 1958 he started to work at the Cambridge Language Research Unit, one of the earliest centers for...
.
Types of chart parsers
A common approach is to use a variant of the Viterbi algorithmViterbi algorithm
The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources, and more generally, hidden Markov models...
. The Earley parser
Earley parser
In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language, named after its inventor, Jay Earley...
is a type of chart parser mainly used for parsing in computational linguistics
Computational linguistics
Computational linguistics is an interdisciplinary field dealing with the statistical or rule-based modeling of natural language from a computational perspective....
, 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
Top-down parsing
Top-down parsing is a type of parsing strategy where in one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar...
and bottom-up chart parsers, and active and passive chart parsers.