A general scheme for some deterministically parsable grammars and their strong equivalents

A.B. Cremers (Editor), Anton Nijholt, H.P. Kriegel (Editor), J. Pittl

    Research output: Contribution to conferencePaperAcademicpeer-review

    50 Downloads (Pure)

    Abstract

    In the past years there have been many attempts to fill in the gap between the classes of LL(k) and LR(k) grammars with new classes of deterministically parsable grammars. Almost always the introduction of a new class was accompanied by a parsing method and/or a grammatical transformation fitting the following scheme. If parsers were at the centre of the investigation the new method used to be designed to possess certain advantages with respect to already existing ones. As far as transformations were concerned the intention was to produce methods of transforming grammars into "more easily" parsable ones. The problem of finding classes of context-free grammars which can be transformed to LL(k) grammars has received much attention. Parsing strategies and associated classes of grammars generating LL(k) languages have been extensively studied. An equally interesting class of grammars is the class of strict deterministic grammars, a subclass of the LR(O) grammars with elegant theoretical properties. Generalizations of this concept have been introduced by Friede and Pittl. The purpose of this paper is to show how the above mentioned classes of grammars can be dealt with within a general framework.
    Original languageEnglish
    Pages243-255
    Number of pages13
    DOIs
    Publication statusPublished - Dec 1982

    Keywords

    • EWI-9254
    • IR-66940
    • HMI-SLT: Speech and Language Technology

    Fingerprint Dive into the research topics of 'A general scheme for some deterministically parsable grammars and their strong equivalents'. Together they form a unique fingerprint.

    Cite this