natural language processing Natural language processing (NLP) is an interdisciplinary subfield of linguistics, computer science, and artificial intelligence concerned with the interactions between computers and human language, in particular how to program computers to pro ...

, deterministic parsing refers to

parsing Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s that do not

backtrack BackTrack was a Linux distribution that focused on security, based on the Knoppix Linux distribution aimed at digital forensics and penetration testing use. In March 2013, the Offensive Security team rebuilt BackTrack around the Debian distribut ...

. LR-parsers are an example. (This meaning of the words "deterministic" and "non-deterministic" differs from that used to describe

nondeterministic algorithm In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave diffe ...

s.) The deterministic behavior is desired and expected in

compiling In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...

programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...

s. 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 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 ...

had to be applied. However,

Mitch Marcus Mitch is a short form of the masculine given name Mitchell (given name), Mitchell. It is also sometimes a nickname, usually for a person with the surname Mitchell (surname), Mitchell. It may refer to: People * Mitch Altman (born 1956), hacker a ...

proposed in 1978 the Parsifal parser that was able to deal with

ambiguities Ambiguity is the type of meaning in which a phrase, statement or resolution is not explicitly defined, making several interpretations plausible. A common aspect of ambiguity is uncertainty. It is thus an attribute of any idea or statement ...

while still keeping the deterministic behavior.

References

* Alfred V. Aho,

Stephen C. Johnson Stephen Curtis Johnson (b. 1944; known as Steve Johnson) is a computer scientist who worked at Bell Labs and Old AT&T, AT&T for nearly 20 years. He is best known for Yacc, Lint (software), Lint, spell (Unix), spell, and the Portable C Compiler, w ...

Jeffrey D. Ullman Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the ...

(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. {{Comp-sci-stub Parsing

See also

References