Innatural language processing,deterministic parsing refers toparsingalgorithms that do notbacktrack.LR-parsers are an example. (This meaning of the words "deterministic" and "non-deterministic" differs from that used to describenondeterministic algorithms.)
The deterministic behavior is desired and expected incompilingprogramming 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 thechart parser had to be applied. However,Mitch Marcus proposed in 1978 the Parsifal parser that was able to deal withambiguities while still keeping the deterministic behavior.
 | Thiscomputer science article is astub. You can help Wikipedia byadding missing information. |