On the covering of parsable grammars

    Research output: Book/ReportReportOther research output


    We introduce the notion of a parsable grammer, i.e. a grammar which can be parsed using a deterministic pushdown transducer. This class of grammars includes the LR(k)-grammars. The notion of covering is generalized and brought into a form making it possible to consider more than only left or righmost derivations. With this new definition of covering we prove that every parsable grammar can be covered by a strict deterministic grammar. A practical consequence is that every parsable grammar can be parsed using a strict deterministic parsing method. Some extensions of the definition of parsable grammars are considered.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Number of pages56
    Publication statusPublished - Sept 1975


    • EWI-9552
    • HMI-SLT: Speech and Language Technology

    Cite this