On the parsing and covering of simple chain grammars

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

    3 Citations (Scopus)
    137 Downloads (Pure)


    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
    Number of pages15
    ISBN (Print)978-3-540-08860-8
    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
    ISSN (Print)0302-9743


    ConferenceFifth Colloquium on Automata, Languages and Programming 1978


    • HMI-SLT: Speech and Language Technology


    Dive into the research topics of 'On the parsing and covering of simple chain grammars'. Together they form a unique fingerprint.

    Cite this