M. Dennis Mickunas
Abstract
A direct, one-step transformation is presented for transforming an arbitrary LR(k) context-free grammar, G, to an LR(1) grammar, G′, which completely covers G. Under additional hypotheses, G′ may be made LR(0).
- 1 AHO, A V , AND ULLMAN, J D. The Theory of Parsing, Translatwn, and Compilzng, Vol. 2 Prentice-Hall, Englewood Chffs, N J, 1973 Google Scholar
Digital Library
- 2 GINSBURG, S, AND GREIBACH, S A Deterministic context-free languages. Inform. and Contr. 9 (1966), 620-648Google ScholarCross Ref
- 3 GRAY, J.N , AND HARRISON, M.A. On the covering and reduction problems for context-free grammars. J. A CM 19, 4 (Oct. 1972), 675-698. Google ScholarDigital Library
- 4 HARRISON, M A., AND HAVEL, I M Strmt determimstm grammars. J. Comput and Syst Sc~s. 7 (1973), 237-277.Google ScholarDigital Library
- 5 HOPCROFT, J.E, AND ULLMAN, j.D Formal Languages and Their Relatwn to Automata. Addison-Wesley, Reading, Mass., 1969 Google ScholarDigital Library
- 6 KNUTH, D.E. On the translation of languages from left to right. Inform. and Contr. 8 (1965), 607-639.Google ScholarCross Ref
- 7 MICKUNAS, M D, LANCASTER, R.L, AND SCHNEIDER, V B. Transforming LR(k) grammars to R(1), SLR(1), and (1, 1) bounded-right-context (unpublished manuscript, 1974).Google Scholar
- 8 h{{ICKUNAS, 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 Annual Symp on Switching and Automata Theory, Oct 1973, pp 109-121Google Scholar
- 9 EYNOLDS, J.C., AND HASKELL, R. Grammatical coverings (unpubhshed manuscript, 1970).Google Scholar
Index Terms
- On the Complete Covering Problem for LR(k)Grammars
Recommendations
Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars
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 ...
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 ...
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 ...
Comments