Simple chain grammars and languages

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    89 Downloads (Pure)


    A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar. Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.
    Original languageUndefined
    Article number10.1016/0304-3975(79)90032-X
    Pages (from-to)287-309
    Number of pages23
    JournalTheoretical computer science
    Issue number3
    Publication statusPublished - Oct 1979


    • EWI-9199
    • IR-66914
    • HMI-SLT: Speech and Language Technology

    Cite this