On the covering of parsable grammars

    Research output: Book/ReportReportOther research output

    Abstract

    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, Department of Applied Mathematics
    Number of pages56
    Publication statusPublished - Sep 1975

    Keywords

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

    Cite this

    Nijholt, A. (1975). On the covering of parsable grammars. Enschede: University of Twente, Department of Applied Mathematics.