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 conferencePaperpeer-review

    71 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
    Event6th G.I.-Conference on Theoretical Computer Science - Dortmund, Germany
    Duration: 5 Jan 19837 Jan 1983

    Conference

    Conference6th G.I.-Conference on Theoretical Computer Science
    Period5/01/837/01/83
    Other5-7 Jan 1983

    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