A parsing method for strict deterministic grammars is presented and a technique for using it to parse any deterministic language is indicated. An important characterization of the trees of strict deterministic grammars is established. This is used to prove iteration theorems for (strict) deterministic languages, and hence proving that certain sets are not in these families becomes comparatively straightforward. It is shown that every strict deterministic grammar is LR(0) and that any strict deterministic grammar is equivalent to a bounded right context (1, 0) grammar. Thus rigorous proofs that the families of deterministic, LR ( k ), and bounded right context languages are coextensive are presented for the first time.

The family of strict deterministic languages has been studied for its theoretical properties and applications to parsing. In particular, these languages have been shown to be precisely the prefix-free deterministic languages. Deterministic pushdown automata are called (quasi-)real time if they have no (only a bounded number of consecutive) null moves. It is shown that for strict deterministic languages, the quasi-real-time and real-time constraints are equivalent (except for $\{ \Lambda \} $). A grammatical characterization of these languages is also given. For quasi-real-time strict deterministic languages, an easy and elegant decision method is given for testing regularity. For all known methods of accepting deterministic languages, it is shown that the families of real-time languages are a proper subset of the full families. A relation is established among these sets, the simple deterministic languages, and some hierarchies.