A context-free grammar is deterministic iff its rules allow a (left-to-right, bottom-up) parser to proceed without having to guess the correct continuation at any point.

A language is deterministic context-free iff it is generated by some deterministic context-free grammar. Not all context-free languages are deterministic.

To illustrate: the following grammar is not deterministic:

  S -> aS
  S -> aSb
  S -> b
While we are parsing, we cannot decide which rule to apply without knowing the rest of the string in advance. The language being described is in fact nondeterministic: it is impossible to write a deterministic context-free grammar for it.

Determinism is a stronger notion than nonambiguity. A grammar is ambiguous if it allows two different parses for the same sentence. Determinism requires that ambiguity never arises even temporarily during parsing.

Log in or register to write something here or to contact authors.