Simple chain grammars

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

    Research output: Contribution to conferencePaper

    4 Citations (Scopus)
    17 Downloads (Pure)

    Abstract

    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
    Pages352-364
    Number of pages13
    DOIs
    Publication statusPublished - Jul 1977

    Keywords

    • IR-66788
    • EWI-8807

    Cite this

    Nijholt, A., Salomaa, A. (Ed.), & Steinby, M. (Ed.) (1977). Simple chain grammars. 352-364. https://doi.org/10.1007/3-540-08342-1_27
    Nijholt, Anton ; Salomaa, Arto (Editor) ; Steinby, Magnus (Editor). / Simple chain grammars. 13 p.
    @conference{2868cc7bbf2e40c7b4aa93ec068d9b81,
    title = "Simple chain grammars",
    abstract = "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.",
    keywords = "IR-66788, EWI-8807",
    author = "Anton Nijholt and Arto Salomaa and Magnus Steinby",
    year = "1977",
    month = "7",
    doi = "10.1007/3-540-08342-1_27",
    language = "Undefined",
    pages = "352--364",

    }

    Nijholt, A, Salomaa, A (ed.) & Steinby, M (ed.) 1977, 'Simple chain grammars' pp. 352-364. https://doi.org/10.1007/3-540-08342-1_27

    Simple chain grammars. / Nijholt, Anton; Salomaa, Arto (Editor); Steinby, Magnus (Editor).

    1977. 352-364.

    Research output: Contribution to conferencePaper

    TY - CONF

    T1 - Simple chain grammars

    AU - Nijholt, Anton

    A2 - Salomaa, Arto

    A2 - Steinby, Magnus

    PY - 1977/7

    Y1 - 1977/7

    N2 - 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.

    AB - 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.

    KW - IR-66788

    KW - EWI-8807

    U2 - 10.1007/3-540-08342-1_27

    DO - 10.1007/3-540-08342-1_27

    M3 - Paper

    SP - 352

    EP - 364

    ER -