Some properties of precedence languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Some properties of precedence languages

Full text

Pdf (552 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the first annual ACM symposium on Theory of computing table of contents

Marina del Rey, California, United States

Pages: 181 - 190

Year of Publication: 1969

Author

Michael J. Fischer

Carnegie-Mellon University, Pittsburgh, Pennsylvania

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 20, Citation Count: 15

Additional Information:

abstract 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/800169.805432 What is a DOI?

ABSTRACT

The classes of languages definable by operator precedence grammars1 and by Wirth-Weber precedence grammars2 are studied. A grammar is backwards-deterministic3 if no two productions have the same right part. Operator precedence grammars have no more generative power than backwards deterministic operator precedence grammars, but Wirth-Weber precedence grammars (i.e., grammars having unique Wirth-Weber precedence relations) are more powerful than backwards-deterministic Wirth-Weber precedence grammars; indeed they can generate any context-free language. An algorithm is developed for finding a Wirth-Weber precedence grammar equivalent to a given operator precedence grammar, a result of possible practical significance. The operator precedence languages are shown to be a proper subclass of the backwards-deterministic Wirth-Weber precedence languages which in turn are a proper subclass of the deterministic context-free languages.

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	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]
	2	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]
	3	Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
	4	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969

CITED BY 15

	I. H. Sudborough, On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store, Proceedings of the eighth annual ACM symposium on Theory of computing, p.141-148, May 03-05, 1976, Hershey, Pennsylvania, United States
	James N. Gray , Michael A. Harrison, Canonical Precedence Schemes, Journal of the ACM (JACM), v.20 n.2, p.214-234, April 1973
	A. Fernandez , J. C. Heliard , J. D. Ichbiah, Overview of the syntax processor generator SYNPROC, ACM SIGPLAN Notices, v.6 n.12, p.51-55, December 1971
	A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-21, October 01-03, 1973, Boston, Massachusetts
	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
	Mario Schkolnick, The equivalence of reducing transition languages and deterministic languages, Communications of the ACM, v.17 n.9, p.517-520, Sept. 1974
	A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975
	I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, Journal of the ACM (JACM), v.25 n.3, p.405-414, July 1978
	David F. Martin, A Boolean matrix method for the computation of linear precedence functions, Communications of the ACM, v.15 n.6, p.448-454, June 1972
	James N. Gray , Michael A. Harrison, On the Covering and Reduction Problems for Context-Free Grammars, Journal of the ACM (JACM), v.19 n.4, p.675-698, Oct. 1972
	A. V. Aho , P. J. Denning , J. D. Ullman, Weak and Mixed Strategy Precedence Parsing, Journal of the ACM (JACM), v.19 n.2, p.225-243, April 1972
	Yael Krevner , Amiram Yehudai, An Iteration Theorem for Simple Precedence Languages, Journal of the ACM (JACM), v.30 n.4, p.820-833, Oct. 1983
	L. Presser , J. McAfee, An Algorithm for the Design of Simple Precedence Grammars, Journal of the ACM (JACM), v.19 n.3, p.385-395, July 1972
	James B. Morris, A result on the relationship between simple precedence languages and reducing transition languages, Proceedings of the second annual ACM symposium on Theory of computing, p.73-80, May 04-06, 1970, Northampton, Massachusetts, United States
	J. D. Ullman, Applications of language theory to compiler design, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada