A new method for determining linear precedence functions for precedence grammars

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new method for determining linear precedence functions for precedence grammars

Full text

Pdf (453 KB)

Source

Communications of the ACM archive
Volume 12 , Issue 10 (October 1969) table of contents

Pages: 567 - 569

Year of Publication: 1969

ISSN:0001-0782

Author

James R. Bell

Digital Equipment Corp., Maynard, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 4

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

ABSTRACT

The precedence relations of a precedence grammar can be precisely described by a two-dimensional precedence matrix. Often the information in the matrix can be represented more concisely by a pair of vectors, called linear precedence functions. A new algorithm is presented for obtaining the linear precedence functions when given the precedence matrix; this algorithm is shown to possess several computational adavantages.

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	Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]
	2	Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]
	3	KcKEEMAN, W. M. An approach to computer language design. Tech. Rep. CS 48, Computer Science Dept., Stanford U., Stanford, Calif., Aug. 1966.
	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	Niklaus Wirth, Algorithm 265: find precedence functions [L2], Communications of the ACM, v.8 n.10, p.604-605, Oct. 1965 [doi>10.1145/365628.365647]
	6	Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
	7	Robert W. Floyd, Algorithm 96: Ancestor, Communications of the ACM, v.5 n.6, p.344-345, June 1962 [doi>10.1145/367766.368166]

CITED BY 4

	Eberhard Bertsch, The storage requirement in precedence parsing, Communications of the ACM, v.20 n.3, p.192-194, March 1977
	H. B. Hunt, III , J. D. Ullman , T. G. Szymanski, Operations on sparse relations, Communications of the ACM, v.20 n.3, p.171-176, March 1977
	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
	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