On the parsing and covering of simple chain grammars

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    3 Citations (Scopus)
    55 Downloads (Pure)

    Abstract

    A method is presented for obtaining a simple deterministic pushdown transducer which acts as a parser for simple chain grammars. It is shown that a simple deterministic grammar can be constructed which covers the simple chain grammar. To obtain both the simple deterministic pushdown transducer and the cover result, a new type of parse is introduced which differs from the left and right parses which are common for the usual one pass no back-tracking parsing algorithms. For the simple chain grammars this parse, the so-called left part parse, follows from a simple left part property which is satisfied by the grammatical trees of simple chain grammars.
    Original languageEnglish
    Title of host publicationAutomata, Languages and Programming, Fifth Colloquium
    EditorsG. Ausiello, C. Bohm
    Place of PublicationBerlin
    PublisherSpringer
    Pages330-344
    Number of pages15
    ISBN (Print)978-3-540-08860-8
    DOIs
    Publication statusPublished - Jul 1978
    EventFifth Colloquium on Automata, Languages and Programming 1978 - Udine, Italy
    Duration: 17 Jul 197821 Jul 1978

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    Volume62
    ISSN (Print)0302-9743

    Conference

    ConferenceFifth Colloquium on Automata, Languages and Programming 1978
    CountryItaly
    CityUdine
    Period17/07/7821/07/78

    Fingerprint

    grammars
    coverings
    parsing algorithms
    transducers

    Keywords

    • HMI-SLT: Speech and Language Technology

    Cite this

    Nijholt, A. (1978). On the parsing and covering of simple chain grammars. In G. Ausiello, & C. Bohm (Eds.), Automata, Languages and Programming, Fifth Colloquium (pp. 330-344). [10.1007/3-540-08860-1_24] (Lecture Notes in Computer Science; Vol. 62). Berlin: Springer. https://doi.org/10.1007/3-540-08860-1_24
    Nijholt, Anton. / On the parsing and covering of simple chain grammars. Automata, Languages and Programming, Fifth Colloquium. editor / G. Ausiello ; C. Bohm. Berlin : Springer, 1978. pp. 330-344 (Lecture Notes in Computer Science).
    @inbook{aab2e225e3754753a6e6eaa515e0a0c2,
    title = "On the parsing and covering of simple chain grammars",
    abstract = "A method is presented for obtaining a simple deterministic pushdown transducer which acts as a parser for simple chain grammars. It is shown that a simple deterministic grammar can be constructed which covers the simple chain grammar. To obtain both the simple deterministic pushdown transducer and the cover result, a new type of parse is introduced which differs from the left and right parses which are common for the usual one pass no back-tracking parsing algorithms. For the simple chain grammars this parse, the so-called left part parse, follows from a simple left part property which is satisfied by the grammatical trees of simple chain grammars.",
    keywords = "HMI-SLT: Speech and Language Technology",
    author = "Anton Nijholt",
    year = "1978",
    month = "7",
    doi = "10.1007/3-540-08860-1_24",
    language = "English",
    isbn = "978-3-540-08860-8",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "330--344",
    editor = "G. Ausiello and C. Bohm",
    booktitle = "Automata, Languages and Programming, Fifth Colloquium",

    }

    Nijholt, A 1978, On the parsing and covering of simple chain grammars. in G Ausiello & C Bohm (eds), Automata, Languages and Programming, Fifth Colloquium., 10.1007/3-540-08860-1_24, Lecture Notes in Computer Science, vol. 62, Springer, Berlin, pp. 330-344, Fifth Colloquium on Automata, Languages and Programming 1978, Udine, Italy, 17/07/78. https://doi.org/10.1007/3-540-08860-1_24

    On the parsing and covering of simple chain grammars. / Nijholt, Anton.

    Automata, Languages and Programming, Fifth Colloquium. ed. / G. Ausiello; C. Bohm. Berlin : Springer, 1978. p. 330-344 10.1007/3-540-08860-1_24 (Lecture Notes in Computer Science; Vol. 62).

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    TY - CHAP

    T1 - On the parsing and covering of simple chain grammars

    AU - Nijholt, Anton

    PY - 1978/7

    Y1 - 1978/7

    N2 - A method is presented for obtaining a simple deterministic pushdown transducer which acts as a parser for simple chain grammars. It is shown that a simple deterministic grammar can be constructed which covers the simple chain grammar. To obtain both the simple deterministic pushdown transducer and the cover result, a new type of parse is introduced which differs from the left and right parses which are common for the usual one pass no back-tracking parsing algorithms. For the simple chain grammars this parse, the so-called left part parse, follows from a simple left part property which is satisfied by the grammatical trees of simple chain grammars.

    AB - A method is presented for obtaining a simple deterministic pushdown transducer which acts as a parser for simple chain grammars. It is shown that a simple deterministic grammar can be constructed which covers the simple chain grammar. To obtain both the simple deterministic pushdown transducer and the cover result, a new type of parse is introduced which differs from the left and right parses which are common for the usual one pass no back-tracking parsing algorithms. For the simple chain grammars this parse, the so-called left part parse, follows from a simple left part property which is satisfied by the grammatical trees of simple chain grammars.

    KW - HMI-SLT: Speech and Language Technology

    U2 - 10.1007/3-540-08860-1_24

    DO - 10.1007/3-540-08860-1_24

    M3 - Chapter

    SN - 978-3-540-08860-8

    T3 - Lecture Notes in Computer Science

    SP - 330

    EP - 344

    BT - Automata, Languages and Programming, Fifth Colloquium

    A2 - Ausiello, G.

    A2 - Bohm, C.

    PB - Springer

    CY - Berlin

    ER -

    Nijholt A. On the parsing and covering of simple chain grammars. In Ausiello G, Bohm C, editors, Automata, Languages and Programming, Fifth Colloquium. Berlin: Springer. 1978. p. 330-344. 10.1007/3-540-08860-1_24. (Lecture Notes in Computer Science). https://doi.org/10.1007/3-540-08860-1_24