Simple chain grammars

Anton Nijholt, Arto Salomaa (Editor), Magnus Steinby (Editor)

    Research output: Contribution to conferencePaperpeer-review

    4 Citations (Scopus)
    74 Downloads (Pure)


    A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k, this new class of grammars is very close related to the class of LL(1) and simple LL(1) grammars. In fact it can be proved (not in this paper) that each simple chain grammar has an equivalent simple LL(1) grammar. A very simple (bottom-up) parsing method is provided. This method follows directly from the definition of a simple chain grammar and can easily be given in terms of the well-known LR(0) parsing method.
    Original languageUndefined
    Number of pages13
    Publication statusPublished - Jul 1977
    EventFourth Conference on Automata, Languages and Programming - Turku, Finland
    Duration: 18 Jul 197722 Jul 1977


    ConferenceFourth Conference on Automata, Languages and Programming
    Other18-22 July 1977


    • IR-66788
    • EWI-8807

    Cite this