Context-Free Grammars: Covers, Normal Forms, and Parsing

Anton Nijholt (Editor)

    Research output: Book/ReportBook editingAcademic

    597 Downloads (Pure)

    Abstract

    This monograph develops a theory of grammatical covers, normal forms and parsing. Covers, formally defined in 1969, describe a relation between the sets of parses of two context-free grammars. If this relation exists then in a formal model of parsing it is possible to have, except for the output, for both grammars the same parser. Questions concerning the possibility to cover a certain grammar with grammars that conform to some requirements on the productions or the derivations will be raised and answered. Answers to these cover problems will be obtained by introducing algorithms that describe a transformation of an input grammar into an output grammar which satisfies the requirements. The main emphasis in this monograph is on transformations of context-free grammars to context-free grammars in some normal form. However, not only transformations of this kind will be discussed, but also transformations which yield grammars which have useful parsing properties.
    Original languageEnglish
    Place of PublicationBerlin
    PublisherSpringer
    Number of pages253
    ISBN (Print)0-387-10245-0
    DOIs
    Publication statusPublished - 1980

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume93

    Fingerprint

    Grammar
    Parsing
    Monographs

    Keywords

    • IR-66928
    • HMI-SLT: Speech and Language Technology
    • EWI-9219

    Cite this

    Nijholt, A. (Ed.) (1980). Context-Free Grammars: Covers, Normal Forms, and Parsing. (Lecture Notes in Computer Science; Vol. 93). Berlin: Springer. https://doi.org/10.1007/3-540-10245-0
    Nijholt, Anton (Editor). / Context-Free Grammars: Covers, Normal Forms, and Parsing. Berlin : Springer, 1980. 253 p. (Lecture Notes in Computer Science).
    @book{3a45ec824632472aa0b16234ae2accd6,
    title = "Context-Free Grammars: Covers, Normal Forms, and Parsing",
    abstract = "This monograph develops a theory of grammatical covers, normal forms and parsing. Covers, formally defined in 1969, describe a relation between the sets of parses of two context-free grammars. If this relation exists then in a formal model of parsing it is possible to have, except for the output, for both grammars the same parser. Questions concerning the possibility to cover a certain grammar with grammars that conform to some requirements on the productions or the derivations will be raised and answered. Answers to these cover problems will be obtained by introducing algorithms that describe a transformation of an input grammar into an output grammar which satisfies the requirements. The main emphasis in this monograph is on transformations of context-free grammars to context-free grammars in some normal form. However, not only transformations of this kind will be discussed, but also transformations which yield grammars which have useful parsing properties.",
    keywords = "IR-66928, HMI-SLT: Speech and Language Technology, EWI-9219",
    editor = "Anton Nijholt",
    year = "1980",
    doi = "10.1007/3-540-10245-0",
    language = "English",
    isbn = "0-387-10245-0",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",

    }

    Context-Free Grammars: Covers, Normal Forms, and Parsing. / Nijholt, Anton (Editor).

    Berlin : Springer, 1980. 253 p. (Lecture Notes in Computer Science; Vol. 93).

    Research output: Book/ReportBook editingAcademic

    TY - BOOK

    T1 - Context-Free Grammars: Covers, Normal Forms, and Parsing

    A2 - Nijholt, Anton

    PY - 1980

    Y1 - 1980

    N2 - This monograph develops a theory of grammatical covers, normal forms and parsing. Covers, formally defined in 1969, describe a relation between the sets of parses of two context-free grammars. If this relation exists then in a formal model of parsing it is possible to have, except for the output, for both grammars the same parser. Questions concerning the possibility to cover a certain grammar with grammars that conform to some requirements on the productions or the derivations will be raised and answered. Answers to these cover problems will be obtained by introducing algorithms that describe a transformation of an input grammar into an output grammar which satisfies the requirements. The main emphasis in this monograph is on transformations of context-free grammars to context-free grammars in some normal form. However, not only transformations of this kind will be discussed, but also transformations which yield grammars which have useful parsing properties.

    AB - This monograph develops a theory of grammatical covers, normal forms and parsing. Covers, formally defined in 1969, describe a relation between the sets of parses of two context-free grammars. If this relation exists then in a formal model of parsing it is possible to have, except for the output, for both grammars the same parser. Questions concerning the possibility to cover a certain grammar with grammars that conform to some requirements on the productions or the derivations will be raised and answered. Answers to these cover problems will be obtained by introducing algorithms that describe a transformation of an input grammar into an output grammar which satisfies the requirements. The main emphasis in this monograph is on transformations of context-free grammars to context-free grammars in some normal form. However, not only transformations of this kind will be discussed, but also transformations which yield grammars which have useful parsing properties.

    KW - IR-66928

    KW - HMI-SLT: Speech and Language Technology

    KW - EWI-9219

    U2 - 10.1007/3-540-10245-0

    DO - 10.1007/3-540-10245-0

    M3 - Book editing

    SN - 0-387-10245-0

    T3 - Lecture Notes in Computer Science

    BT - Context-Free Grammars: Covers, Normal Forms, and Parsing

    PB - Springer

    CY - Berlin

    ER -