On the covering of left-recursive grammars

    Research output: Book/Report › Report › Other research output

    Abstract

    In this report we show that some prevailing ideas on the elimination of left recursion in a context-free grammar are not valid. An algorithm and a proof are given to show that every proper context-free grammar is covered by a non-left-recursive grammar. Some additional results concerning parsing and covering strict determinisitc grammars are also given.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Number of pages27
    Publication statusPublished - Apr 1976

    Keywords

    • HMI-SLT: Speech and Language Technology
    • EWI-9554
    • 1 Conference contribution

    • On the covering of left recursive grammars

      Nijholt, A., Jan 1977, POPL '77: Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. Graham, R. M. & Harrison, M. A. (eds.). ACM Publishing, p. 86-96 11 p.

      Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

      Open Access
      File
      6 Citations (Scopus)
      216 Downloads (Pure)

    Cite this