KNUTH1965607:
  type: article
  title: On the translation of languages from left to right
  author: Knuth, Donald E.
  date: 1965
  page-range: 607-639
  url: https://www.sciencedirect.com/science/article/pii/S0019995865904262
  serial-number:
    doi: https://doi.org/10.1016/S0019-9958(65)90426-2
    issn: 0019-9958
  abstract: 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.
  parent:
    type: periodical
    title: Information and Control
    issue: 6
    volume: 8