M. D. Mickunas
Abstract
A method is presented for directly transforming an arbitrary LR(k) grammar to an equivalent LR(1) grammar. It is further shown that the method transforms an arbitrary prefix-free LR(k) grammar to an equivalent LR(0) grammar. It is argued that the method is efficient and offers some advantages over traditional “look-ahead” parsing methods. Finally, it is demonstrated that the method can be used to transform an LR(1) grammar to an equivalent SLR(1) grammar, which in turn can be easily transformed to an equivalent (1, 1) bounded right-context grammar.
- 1 AHO, A V , DENNING, P J., AND ULLMAN, J.D Weak and mixed strategy precedence parsing. J ACM 19, 2 (April 1972), 225-243. Google Scholar
- 2 AHo, A.V , AND ULLMAN, J.D. The Theory of Parszng, Translatwn, and Comphng, Vol. Prentice-Hall, Englewood Cliffs, N.J, 1973. Google Scholar
- 3 DRMER, F L. Practical translators for LR(k) languages Doctoral DiNs , M I T , Cambridge, Mass, Sept. 1969Google Scholar
- 4 DEREMR, F.L Simple LR(k) grammars. Comm. ACM 14, 7 (July 1971), 453---460. Google Scholar
- 5 FLOYD, R W Syntactic analysis and operator precedence J. ACM 10, 3 (July 1963), 316-333 Google Scholar
- 6 FLOYD, R.W. Bounded-context syntactic analysis Comm. ACM 7, 2 (Feb 1964), 62-67 Google Scholar
- 7 GELLER, M.M, AND HARRISON, M A Characterizations of LR(0) languages (extended abstract) Proc. of the 14th Ann Symp on Switching and Automata Theory, Iowa City, I a , Oct. 1973, pp. 103-108 (sponsored by IEEE, New York)Google Scholar
- 8 GINSBURG, S , AND GREIBACH, S A. Deterministic context-free languages. Inform. and Contr. 9 (1966), 620-648.Google Scholar
- 9 GRAHAM, S.L. Precedence languages and bounded right context languages Doctoral DiNs , Stanford U, Stanford, Calif., July 1971 Google Scholar
- 10 GRAHAM, S L. On bounded right context languages and grammars. SIAM J. Comput. (1974), 224-254.Google Scholar
- 11 GRAY, J N , AND HARRISON, M.A On the covering and reduction problems for context-free grammars, J. ACM 19, 4 (Oct. 1972), 675-698 Google Scholar
- 12 HARRISON, M.A. On the parsing of deterministic languages. Inv:ted presentation, ACM Comput. Sci. Conf, Columbus, Ohio, 1973 (oral presentatmn)Google Scholar
- 13 HARRISON, M.A, AND HVEL, I.M. Strict determmmtlc grammars J Comput and Syst. Scls. 7 (1973), 237-277Google Scholar
- 14 HOPCROFT, J.E., AND ULLMAN, J D. Formal Languages and Their Relatzon to Automata Addison-Wesley, Reading, Mass., 1969 Google Scholar
- 15 ICHBIAH, J.D , AND MORSE, S P A technique for generating almost optimal Floyd-Evans productions for precedence grammars. Comm ACM 13, 8 (Aug. 1970), 501-508. Google Scholar
- 16 KNUTH, D.E On the translation of languages from left to right. Inform. and Contr. 8 (1965), 607-639.Google Scholar
- 17 LALONDE, W R An efficmnt LALR parser generator Tech. Rep CSRG-2, U of Toronto, Toronto, Ont , Canada, 1971Google Scholar
- 18 McAFEE, J., AND PRESSER, L. An algorithm for the design of simple precedence grammars J ACM 19, 3 (July 1972), 385-395. Google Scholar
- 19 MICKUNAS, M.D User's manual for the PUCSD parser generating system. Tech Rep, Purdue U., West Lafayette, Ind., Aug. 1973.Google Scholar
- 20 MICKUNAS, M.D Techmques for compressing bounded-context aceeptors. Doctoral DiNs., Purdue U , West Lafayette, Ind , May 1973. Google Scholar
- 21 MICKUNAS, M D., AND SCHNEIDER, V.B. On the ability to cover LR(k) grammars with LR(1), SLR(1), and (1, 1) bounded-context grammars Proc of the 14th Ann Symp. on Switching and Automata Theory, Iowa City, I a , Oct 1973, pp. 109-121 (sponsored by IEEE, New York).Google Scholar
- 22 MICKUNAS, M D , XND SCHNEIDER, V.B. A parser-generating system for constructing compressed compilers Comm ACM i6, 11 (Nov. 1973), 669-676 Google Scholar
- 23 REYNOLDS, J.C., AND HASKELL, R. Grammatical coverings Unpublished manuscript, 1970Google Scholar
- 24 SCHNEIDER, V.B. A system for designing fast programminglanguage translators Proc.AFIPS 1969 SJCC, Vol. 34, AFIPS Press, Montvale, N J., pp. 777-792.Google Scholar
- 25 WIRTH, N , AND WEBER, H. EULER: a generalization of ALGOL and its formal defimtlon: Parts I, II. Comm. ACM 9, 1, 2 (Jan , Feb. 1966), 13-23, 25, 89-99f Google Scholar
Index Terms
- Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars
Recommendations
Simple LR(k) grammars
A class of context-free grammars, called the “Simple LR(k)” or SLR(k) grammars is defined. This class has been shown to include weak precedence and simple precedence grammars as proper subsets. How to construct parsers for the SLR(k) grammars is also ...
Noncanonical SLR(1) Grammars
Two noncanonical extensions of the simple LR(1) (SLR(1)) method are presented, which reduce not only handles but also other phrases of sentential forms. A class of context-free grammars called leftmost SLR(1) (LSLR(1)) is defined by using lookahead ...
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 ...
Comments