📑 Table of Contents▼

In computer science, a chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages). 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.[1]

Types of chart parsers

edit

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.

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

See also

edit

References

edit
  1. ^ "Chart Parsing" (PDF). Archived from the original (PDF) on 21 February 2015. Retrieved 20 November 2011.
edit

📚 Artikel Terkait di Wikipedia

Earley parser

is a chart parser that uses dynamic programming. Earley parsers are appealing because they can parse all context-free languages, unlike LR parsers and

Semantic parsing

representations. Most modern deep semantic parsing models are either based on defining a formal grammar for a chart parser or utilizing RNNs to directly translate

Parsing

Chart parser Compiler-compiler Deterministic parsing DMS Software Reengineering Toolkit Grammar checker Inverse parser LALR parser Left corner parser

Left corner parser

corner parser is a type of chart parser used for parsing context-free grammars. It combines the top-down and bottom-up approaches of parsing. The name

Deterministic parsing

non-deterministic approaches such as the chart parser had to be applied. However, Mitch Marcus proposed in 1978 the Parsifal parser that was able to deal with ambiguities

Syntactic parsing (computational linguistics)

decoder to make more globally-optimal parses. The first parser of this family to outperform a chart-based parser was the one by Muhua Zhu et al. in 2013

JSON

comments you like. Then pipe it through JSMin before handing it to your JSON parser." MongoDB uses JSON-like data for its document-oriented database. Some relational

Chart (disambiguation)

coastal regions Chart, in computer science, a data structure used by a chart parser to store partial hypothesized results for re-use Chart, in geometry or