On the Covering and Reduction Problems for Context-Free Grammars

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Covering and Reduction Problems for Context-Free Grammars

Full text

Pdf (1.38 MB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 4 (October 1972) table of contents

Pages: 675 - 698

Year of Publication: 1972

ISSN:0004-5411

Authors

James N. Gray	IBM Thomas J. Watson research Center, P.O. Box 218, Yorktown Heights, NY and University of California, Berkeley, California
Michael A. Harrison	Department of Computer Science, University of California, Berkeley, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 34, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321724.321732 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	CROMSKY, N. Formal properties of grammars. In Handbook of Mathematical Psychology, Vol. 2, R. R. Bush, E. H. Galanter, and R. D. Luce (Eds.), Wiley, New York, 1962, pp. 323--418.
	2	Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
	3	Michael J. Fischer, Some properties of precedence languages, Proceedings of the first annual ACM symposium on Theory of computing, p.181-190, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805432]
	4	Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
	5	Robert W. Floyd, Bounded context syntactic analysis, Communications of the ACM, v.7 n.2, p.62-67, Feb. 1964 [doi>10.1145/363921.363927]
	6	Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
	7	GINSBURG, S., AND HARRISON, M. A. Bracketed context free languages. J. Computer and System Sci. 1 (1967), 1-23.
	8	GRAY, J. N. Precedence parsers for programming languages. Ph.D. Th., Dep. of Computer Sci., U. of California, Berkeley, Calif., Sept. 1969.
	9	James N. Gray , Michael A. Harrison, Canonical Precedence Schemes, Journal of the ACM (JACM), v.20 n.2, p.214-234, April 1973 [doi>10.1145/321752.321755]
	10	Sheila A. Greibach, A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, Journal of the ACM (JACM), v.12 n.1, p.42-52, Jan. 1965 [doi>10.1145/321250.321254]
	11	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	12	J. D. Ichbiah , S. P. Morse, A technique for generating almost optimal Floyd-Evans productions for precedence grammars, Communications of the ACM, v.13 n.8, p.501-508, Aug. 1970 [doi>10.1145/362705.362712]
	13	KNUTt-I,D. E. On the translation of languages from left to right. Information and Control 8 (1965), 607-639.
	14	Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
	15	REYNOLDS, J. C., AND HASKELL, R. Grammatical coverings. (unpublished manuscript, 1970).
	16	Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL and it formal definition: Part 1, Communications of the ACM, v.9 n.1, p.13-25, Jan. 1966 [doi>10.1145/365153.365162]
	17	GRAHAM, S.L. Extended precedence, bounded right context languages, and deterministic languages (extended abstract). Proc. Symp. on Switching and Automata Theory, Oct. 1970, pp. 175-180.
	18	Susan Lois Graham, Precedence languages and bounded right context languages, 1971

CITED BY 13

	H. B. Hunt, III, On the Decidability of Grammar Problems, Journal of the ACM (JACM), v.29 n.2, p.429-447, April 1982
	Ivan M. Havel , Michael A. Harrison, On the Parsing of Deterministic Languages, Journal of the ACM (JACM), v.21 n.4, p.525-548, Oct. 1974
	H. B. Hunt, III, Terminating Turing Machine Computations and the Complexity and/or decidability of Correspondence Problems, Grammars, and Program Schemes, Journal of the ACM (JACM), v.31 n.2, p.299-318, April 1984
	Eberhard Bertsch, An Observation on Relative Parsing Time, Journal of the ACM (JACM), v.22 n.4, p.493-498, Oct. 1975
	H. B. Hunt, III , D. J. Rosenkrantz, Efficient algorithms for structural similarity of grammars, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.213-219, January 28-30, 1980, Las Vegas, Nevada
	M. D. Mickunas , R. L. Lancaster , V. B. Schneider, Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars, Journal of the ACM (JACM), v.23 n.3, p.511-533, July 1976
	R. A. Ballance , J. Butcher , S. L. Graham, Grammatical abstraction and incremental syntax analysis in a language-based editor, ACM SIGPLAN Notices, v.23 n.7, p.185-198, July 1988
	James N. Gray , Michael A. Harrison, Canonical Precedence Schemes, Journal of the ACM (JACM), v.20 n.2, p.214-234, April 1973
	D. J. Rosenkrantz , H. B. Hunt, Efficient algorithms for automatic construction and compactification of parsing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.543-566, Oct. 1987
	A. Nijholt, On the covering of left recursive grammars, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.86-96, January 17-19, 1977, Los Angeles, California
	M. Dennis Mickunas, On the Complete Covering Problem for LR(k)Grammars, Journal of the ACM (JACM), v.23 n.1, p.17-30, Jan. 1976
	S. Crespi-Reghizzi , G. Guida , D. Mandrioli, Noncounting Context-Free Languages, Journal of the ACM (JACM), v.25 n.4, p.571-580, Oct. 1978
	Michael A. Harrison, Jim Gray at Berkeley, ACM SIGMOD Record, v.37 n.2, June 2008