Reference. Properties of deterministic top-down grammars

Daniel J. Rosenkrantz, Richard E. Stearns · I&C · 1970 · parsing · DOI
The class of context-free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. These grammars, called LL(k) grammars where k is the amount of look-ahead are defined and a procedure is given for determining if a context-free grammar is LL(k) for a given value of k. A procedure is given for eliminating the ε-rules from an LL(k) grammar at the cost of increasing k by 1. There exist cases in which this increase is inevitable. A procedure is given for obtaining a deterministic push-down machine to recognize a given LL(k) grammar and it is shown that the equivalence problem is decidable for LL(k) grammars. Additional properties are also given.

Cite
Cite as @rosenkrantz_properties_1970 (helia, typst) · \cite{rosenkrantz_properties_1970} (LaTeX)
BibTeX
bibtex · 15 lines
@article{rosenkrantz_properties_1970,
 title = {Properties of deterministic top-down grammars},
 author = {Rosenkrantz, D. J. and Stearns, R. E.},
 year = {1970},
 doi = {10.1016/S0019-9958(70)90446-8},
 url = {https://www.sciencedirect.com/science/article/pii/S0019995870904468},
 urldate = {2024-11-14},
 journal = {Information and Control},
 volume = {17},
 number = {3},
 pages = {226--256},
 month = {October},
 abstract = {The class of context-free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. These grammars, called LL(k) grammars where k is the amount of look-ahead are defined and a procedure is given for determining if a context-free grammar is LL(k) for a given value of k. A procedure is given for eliminating the ε-rules from an LL(k) grammar at the cost of increasing k by 1. There exist cases in which this increase is inevitable. A procedure is given for obtaining a deterministic push-down machine to recognize a given LL(k) grammar and it is shown that the equivalence problem is decidable for LL(k) grammars. Additional properties are also given.},
 issn = {0019-9958}
}
hayagriva YAML (typst)
yaml · 20 lines
rosenkrantz_properties_1970:
  type: article
  title: Properties of deterministic top-down grammars
  author:
  - Rosenkrantz, D. J.
  - Stearns, R. E.
  date: 1970-10
  page-range: 226-256
  url:
    value: https://www.sciencedirect.com/science/article/pii/S0019995870904468
    date: 2024-11-14
  serial-number:
    doi: 10.1016/S0019-9958(70)90446-8
    issn: 0019-9958
  abstract: The class of context-free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. These grammars, called LL(k) grammars where k is the amount of look-ahead are defined and a procedure is given for determining if a context-free grammar is LL(k) for a given value of k. A procedure is given for eliminating the ε-rules from an LL(k) grammar at the cost of increasing k by 1. There exist cases in which this increase is inevitable. A procedure is given for obtaining a deterministic push-down machine to recognize a given LL(k) grammar and it is shown that the equivalence problem is decidable for LL(k) grammars. Additional properties are also given.
  parent:
    type: periodical
    title: Information and Control
    issue: 3
    volume: 17
Download: rosenkrantz_properties_1970.bib · rosenkrantz_properties_1970.yml
Cites 9 works (1 here)
With notes (1)

On the translation of languages from left to right KNUTH1965607I&C · 1965
There has been much recent interest in languages whose grammar is sufficiently simple that an efficient left-to-right parsing algorithm can be mechanically produced from the grammar. In this paper, we define LR(k) grammars, which are perhaps the most general ones of this type, and they provide the basis for understanding all of the special tricks which have been used in the construction of parsing algorithms for languages with simple structure, e.g. algebraic languages. We give algorithms for deciding if a given grammar satisfies the LR(k) condition, for given k, and also give methods for generating recognizes for LR(k) grammars. It is shown that the problem of whether or not a grammar is LR(k) for some k is undecidable, and the paper concludes by establishing various connections between LR(k) grammars and deterministic languages. In particular, the LR(k) condition is a natural analogue, for grammars, of the deterministic condition, for languages.
DOI
External (8)
rosenkrantz_properties_1970 reference entries/refs/rosenkrantz_properties_1970/rosenkrantz_properties_1970.hel