Matthew M. Geller
ABSTRACT
Recently strict deterministic grammars and languages have been introduced [9,10,11]. This family of languages is quite fundamental in the study of the mathematical properties of deterministic languages and in dealing with some classical families of grammars such as LR(k) and bounded right context grammars [7,8,14]. These grammars are closely related to LR(0) grammars [1,12,13,14], in fact each strict deterministic grammar is also LR(0). In the present paper, we consider the question of how to parse strict deterministic grammars. We introduce part of a more general theory called "characteristic LR(k) parsing". This actually produces parsers which are tuned to the characteristics of a particular family of grammars. We apply the theory to the family of strict deterministic grammars and we get parsers which are as fast as canonical LR(k) parsers but are substantially smaller. They are not necessarily minimal but we postpone any discussion of minimality to the sequel.The techniques used in the present discussion are quite general [5]. For instance, the study in [3] is similar in spirit to our technique. The optimization techniques for LR(k) parsers in [2] do not work in the case k = 0 without modification. After modifying those methods for k = 0, it can be shown that our parsers cannot be produced by those techniques. This fact has its positive aspect in that our parsers may be smaller and its negative aspect in that error detection may be delayed.The present paper is divided into the present introduction and three sections. In the remainder of this introduction, some basic definitions of strict deterministic and LR(k) parsing are given. We have tried to follow [1] as much as possible in order to minimize the amount of new material to be absorbed. The order of the results is the order needed to prove that the characteristic parser works. In Section III, we apply the theory of Section II to strict deterministic parsing. A simple example shows that the new parsers can be unboundedly smaller than the canonical LR(0) parser.The present paper is meant to be an extended abstract and no proofs are included.The rest of the introduction is concerned with notational conventions for the technical concepts needed.
- Aho, A. V. and Ullman, J. D. , The Theory of of Parsing, Translating, and Compiling, Vols. I and II, Prentice Hall, Englewood Cliffs, New Jersey, 1972, and 1973. Google Scholar
Digital Library
- Aho, A. V. and Ullman, J. D. , "Optimization of LR(k) Parsers", Journal of Computer and System Sciences, Vol. 6, pp 573-602, 1972.Google ScholarDigital Library
- El Djabri, N., "Extending the LR Parsing Technique to Some Non-LR Grammars", Technical Report TR-121, Computer Science Laboratory, Princeton University, 1973.Google Scholar
- Floyd, R. W., "Nondeterministic Algorithms", Journal of the Association for Computing Machinery, Vol. 14, pp 636-644, 1967. Google ScholarDigital Library
- Geller, M. M., "Characteristic LR(k) Parsing", Ph.D. Thesis (in preparation), Computer Science Department, University of California, Berkeley, 1973.Google Scholar
- Geller, M. M. and Harrison, M. A., "Characterizations of LR(0) Languages", Fourteenth Annual Symposium on Switching and Automata Theory, 1973.Google Scholar
- Graham, S. L., "Extended Precedence, Bounded Right Context Languages and Deterministic Languages", Proceedings of Symposium on Switching and Automata Theory, pp 175-180, 1970.Google ScholarDigital Library
- Graham, S. L., "Precedence Languages and Bounded Right Context Languages ", Ph.D. Thesis and Technical Report CS-71 -- 233, Department of Computer Science, Stanford University, 1970. Google ScholarDigital Library
- Harrison, M. A., and Havel, I. M., "Strict Deterministic Grammars", Journal of Computer and Systems Science, Vol. 7 pp 237-277, 1973.Google ScholarDigital Library
- Harrison, M. A., and Havel, I. M., "On the Parsing of Deterministic Languages", submitted for publication.Google Scholar
- Harrison, M. A., and Havel, I. M., "Real-time Strict Deterministic Languages", SIAM Journal of Computing, Vol. 1, pp 333-Google ScholarCross Ref
- Kemp, R., "LR(k) Analysatoren", Technical Report A73/02, Mathematisches Institut und Institut für Angemandte Mathematik, Universitat des Saarlandes, Saarbrucken, Germany, 1973.Google Scholar
- Kemp, R., "An Estimation of the Set of States of the Minimal LR(0)-Acceptor", in Automata, Languages and Programming, (M.Nivat, editor) North Holland Publishing Co., Amsterdam, pp 563-574, 1973.Google Scholar
- Knuth, D. E., "On the Translation of Languages from Left to Right", Information and Control, Vol. 8, pp 607-639, 1965.Google ScholarCross Ref
- Strict deterministic versus LR(0) parsing
Recommendations
LR(k)-parsing of Coupled-Context-Free Grammars
COLING '94: Proceedings of the 15th conference on Computational linguistics - Volume 1Coupled-Context-Free Grammars are a generalization of context-free grammars obtained by combining nonterminals to parentheses which can only be substituted simultaneously. Referring to the generative capacity of the grammars we obtain an infinite ...
Parsing extended LR(k) grammars
An extended LR(k) (ELR(k)) grammar is a context free grammar in which the right sides of the productions are regular expressions and which can be parsed from left to right with k symbol look-ahead. We present a practical algorithm for producing small ...
LR(0) grammars generated by LR(0) parsers
Let be an LR (0) parser of a given LR (0) grammar G. Generally, does not only parse the words generated by G but also the words of some other LR (0) grammars different from G . In this paper we shall define a class of LR (0) parsers and ...
Comments