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


Nijholt, A. and Pittl, J. (1982) A general scheme for some deterministically parsable grammars and their strong equivalents. In: 6th G.I.-Conference on Theoretical Computer Science, 5-7 Jan 1983, Dortmund, Germany (pp. pp. 243-255).

open access
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.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66940
Official URL:https://doi.org/10.1007/BFb0036485
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page