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