Encyclopedia > Chart parsing

  Article Content

Chart parser

Redirected from Chart parsing

A chart parser is a type of parser commonly used for natural languages that uses a data-driven approach based on a set of grammatical rules and a dictionary with each of the possible grammatical senses of each word indicated. There may also be a set of probabilities obtained from analysis of a text corpus.

A systematic search is used to explore the space of possible parses of the input string, and a data structure called a "chart" is used to eliminate backtracking and prevent a combinatorial explosion[?].

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-Kasami-Younger (CKY) algorithm.

Chart parsers can also be used for parsing computer languages. Earley parsers in particular have been used in compiler compilers such as the Accent system where their ability to parse using arbitrary Context Free language 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.

See also:

External links:



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Grateful Dead

... "The Electric Kool-Aid Acid Test." Their musical influences varied widely with input from the psychedelic music of the era, combined with rhythm and blues, jazz, and ...

 
 
 
This page was created in 23.7 ms