A chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages). It uses 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. An example of parsing a mathematical expression. ... The term natural language is used to distinguish languages spoken and signed (by hand signals and facial expressions) by humans for general-purpose communication from constructs such as writing, computer-programming languages or the languages used in the study of formal logic, especially mathematical logic. ... In mathematics and computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ... Backtracking is a type of algorithm that is a refinement of brute force search. ... In cryptanalysis, a brute force attack on a cipher is a brute-force search of the key space; that is, testing all possible keys, in an attempt to recover the plaintext used to produce a particular ciphertext. ...

Chart parser was developed by Martin Kay. Martin Kay is a computer scientist known especially for his work in computational linguistics. ...

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. The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ... The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named after its inventor, Jay Earley. ... Computational linguistics is an interdisciplinary field dealing with the statistical and logical modeling of natural language from a computational perspective. ... The Cocke-Younger-Kasami (CYK) algorithm determines whether a string can be generated by a given context_free grammar and, if so, how it can be generated. ... A compiler-compiler or compiler generator is a program that generates the source code of a parser, interpreter, or compiler from a programming language description. ... In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a non-terminal symbol and w is a string consisting of terminals and/or non-terminals. ...

In bidirectional chart parsing, edges of the chart are marked with a direction, either forwards or backwards, and rules are enforced on the direction edges must point in 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. This article or section does not cite its references or sources. ... Bottom-up parsing is a strategy for analyzing unknown data relationships that attempts to identify the most fundamental units first, and then to infer higher-order structures from them. ...

See also

• Brute force search
• Dynamic programming