On the Parsing of Deterministic Languages
- 1 October 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 21 (4) , 525-548
- https://doi.org/10.1145/321850.321851
Abstract
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.Keywords
This publication has 11 references indexed in Scilit:
- Strict deterministic grammarsJournal of Computer and System Sciences, 1973
- Canonical Precedence SchemesJournal of the ACM, 1973
- On the Covering and Reduction Problems for Context-Free GrammarsJournal of the ACM, 1972
- Weak and Mixed Strategy Precedence ParsingJournal of the ACM, 1972
- Simple LR(k) grammarsCommunications of the ACM, 1971
- An efficient context-free parsing algorithmCommunications of the ACM, 1970
- A practical method for constructing LR ( k ) processorsCommunications of the ACM, 1969
- The definition of random sequencesInformation and Control, 1966
- On the translation of languages from left to rightInformation and Control, 1965
- Bounded context syntactic analysisCommunications of the ACM, 1964