Regular extensions of some classes of grammars

    Research output: Book/ReportReportOther research output

    Abstract

    Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente, Department of Applied Mathematics
    Number of pages51
    Publication statusPublished - Sep 1975

    Keywords

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

    Cite this

    Nijholt, A. (1975). Regular extensions of some classes of grammars. Enschede: University of Twente, Department of Applied Mathematics.
    Nijholt, Anton. / Regular extensions of some classes of grammars. Enschede : University of Twente, Department of Applied Mathematics, 1975. 51 p.
    @book{f177500954c343439b06f860dc2a1dfe,
    title = "Regular extensions of some classes of grammars",
    abstract = "Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.",
    keywords = "HMI-SLT: Speech and Language Technology, EWI-9553",
    author = "Anton Nijholt",
    year = "1975",
    month = "9",
    language = "Undefined",
    publisher = "University of Twente, Department of Applied Mathematics",

    }

    Nijholt, A 1975, Regular extensions of some classes of grammars. University of Twente, Department of Applied Mathematics, Enschede.

    Regular extensions of some classes of grammars. / Nijholt, Anton.

    Enschede : University of Twente, Department of Applied Mathematics, 1975. 51 p.

    Research output: Book/ReportReportOther research output

    TY - BOOK

    T1 - Regular extensions of some classes of grammars

    AU - Nijholt, Anton

    PY - 1975/9

    Y1 - 1975/9

    N2 - Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.

    AB - Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular grammar can be transformed to an equivalent LL-regular grammar in Greibach Normal Form. LL-regular grammars can be parsed with a very simple two-scan parsing algorithm. Algorithms and some proofs of correctness are given. In this report extensions of some other classes of grammars are also considered.

    KW - HMI-SLT: Speech and Language Technology

    KW - EWI-9553

    M3 - Report

    BT - Regular extensions of some classes of grammars

    PB - University of Twente, Department of Applied Mathematics

    CY - Enschede

    ER -

    Nijholt A. Regular extensions of some classes of grammars. Enschede: University of Twente, Department of Applied Mathematics, 1975. 51 p.