Deterministic parsing

Deterministic parsing

In natural language processing, deterministic parsing refers to parsing algorithms that do not back up. 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.

See also

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.

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Deterministic context-free grammar — In formal grammar theory, the deterministic context free grammars (DCFGs) are a proper subset of the context free grammars. The deterministic context free grammars are those a deterministic pushdown automaton can recognize. A DCFG is the finite… …   Wikipedia

  • Parsing — In computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a sequence of tokens to determine their grammatical structure with respect to a given (more or less) formal grammar.Parsing is also… …   Wikipedia

  • Parsing table — A parsing table is the part of a parser that makes decisions about how to treat input tokens in compiler development.: This page is about LR parsing tables, there are also LL parsing tables which are substantially different. Overview A parsing… …   Wikipedia

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia

  • Comparison of parser generators — This is a list of notable lexer generators and parser generators for various language classes. Contents 1 Regular languages 2 Deterministic context free languages 3 Parsing expression grammars, deterministic boolean grammars …   Wikipedia

  • Sheila Greibach — (1939 ) is a researcher in formal languages, automata, compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles.She worked with Seymour Ginsburg… …   Wikipedia

  • LR parser — In computer science, an LR parser is a parser for context free grammars that reads input from Left to right and produces a Rightmost derivation. The term LR( k ) parser is also used; here the k refers to the number of unconsumed look ahead input… …   Wikipedia

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Flex++ — is a tool for creating a language parsing program. A parser generator creates a language parsing program. Flex++ is a general instantiation of the flex program.These programs perform character parsing, and tokenizing via the use of a… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”