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

    128 Downloads (Pure)


    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
    Number of pages13
    Publication statusPublished - Dec 1982
    Event6th G.I.-Conference on Theoretical Computer Science - Dortmund, Germany
    Duration: 5 Jan 19837 Jan 1983


    Conference6th G.I.-Conference on Theoretical Computer Science
    Other5-7 Jan 1983


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


    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