On the covering of left-recursive grammars

Anton Nijholt

    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, Department of Applied Mathematics
    Number of pages27
    Publication statusPublished - Apr 1976

    Keywords

    • HMI-SLT: Speech and Language Technology
    • EWI-9554

    Cite this

    Nijholt, A. (1976). On the covering of left-recursive grammars. Enschede: University of Twente, Department of Applied Mathematics.