Deterministic parsing

In natural language processing, deterministic parsing refers to parsing algorithms that do not backtrack. LR-parsers are an example. (This meaning of the words "deterministic" and "non-deterministic" differs from that used to describe nondeterministic algorithms.)

The deterministic behavior is desired and expected in compiling programming languages. In natural language processing, it was thought for a long time that deterministic parsing is impossible due to ambiguity inherent in natural languages (many sentences have more than one plausible parse). Thus, 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 while still keeping the deterministic behavior.

References

Alfred V. Aho, Stephen C. Johnson, Jeffrey D. Ullman (1975): Deterministic parsing of ambiguous grammars. Comm. ACM 18:8:441-452.
Mitchell Marcus (1978): A Theory of Syntactic Recognition for Natural Language. PhD Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Parsing algorithms
Top-down	LL Recursive descent Tail recursive Pratt parser
Bottom-up	Precedence Simple Operator Shunting-yard Bounded-context LR Simple Look-ahead Canonical Generalized CYK Recursive ascent Shift-reduce
Mixed, other	Combinator Chart Earley
Related topics	PEG Definite clause grammar Deterministic parsing Dynamic programming Memoization Parser generator LALR Parse tree AST Scannerless parsing History of compiler construction Comparison of parser generators

Deterministic parsing

See also

References