On the covering of parsable grammars

    Research output: Book/ReportReportOther research output

    Abstract

    We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente, Department of Applied Mathematics
    Number of pages56
    Publication statusPublished - Sep 1975

    Keywords

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

    Cite this

    Nijholt, A. (1975). On the covering of parsable grammars. Enschede: University of Twente, Department of Applied Mathematics.
    Nijholt, Anton. / On the covering of parsable grammars. Enschede : University of Twente, Department of Applied Mathematics, 1975. 56 p.
    @book{5b26829ad5474a23b289b258bef78036,
    title = "On the covering of parsable grammars",
    abstract = "We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.",
    keywords = "EWI-9552, HMI-SLT: Speech and Language Technology",
    author = "Anton Nijholt",
    year = "1975",
    month = "9",
    language = "Undefined",
    publisher = "University of Twente, Department of Applied Mathematics",

    }

    Nijholt, A 1975, On the covering of parsable grammars. University of Twente, Department of Applied Mathematics, Enschede.

    On the covering of parsable grammars. / Nijholt, Anton.

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

    Research output: Book/ReportReportOther research output

    TY - BOOK

    T1 - On the covering of parsable grammars

    AU - Nijholt, Anton

    PY - 1975/9

    Y1 - 1975/9

    N2 - We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.

    AB - We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.

    KW - EWI-9552

    KW - HMI-SLT: Speech and Language Technology

    M3 - Report

    BT - On the covering of parsable grammars

    PB - University of Twente, Department of Applied Mathematics

    CY - Enschede

    ER -

    Nijholt A. On the covering of parsable grammars. Enschede: University of Twente, Department of Applied Mathematics, 1975. 56 p.