On the parsing and covering of simple chain grammars

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

    3 Citations (Scopus)
    64 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

    Keywords

    • HMI-SLT: Speech and Language Technology

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

  • 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