Bounded context syntactic analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Bounded context syntactic analysis

Full text

Pdf (629 KB)

Source

Communications of the ACM archive
Volume 7 , Issue 2 (February 1964) table of contents

Pages: 62 - 67

Year of Publication: 1964

ISSN:0001-0782

Author

Robert W. Floyd

Computer Associates, Inc., Wakefield, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 29, Citation Count: 33

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

ABSTRACT

Certain phase structure grammars define languages in which the phrasehood and structure of a substring of a sentence may be determined by consideration of only a bounded context of the substring. It is possible to determine, for any specified bound on the number of contextual characters considered, whether a given grammar is such a bounded context grammar. Such grammars are free from syntactic ambiguity. Syntactic analysis of sentences in a bounded context language may be performed by a standard process and requires a number of operations proportional to the length of sentence analyzed. Bounded context grammars form models for most languages used in computer programming, and many methods of syntactic analysis, including analysis by operator precedence, are special cases of bounded context analysis.

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	B. Arden , R. Graham, On GAT and the construction of translators, Communications of the ACM, v.2 n.7, p.24-26, July 1959 [doi>10.1145/368370.368373]
	2	BAR-HILLEL, Y., PERLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwise, und Kommunikationsforach. 14, 2(1961), 143-172.
	3	CHOMSKY, N. On certain formal properties of grammars. Inf. Contr. 2 (1959), 137-167.
	4	EICKEL, J., PAUL, M., BAUER, F. L,, AND SAMELSON, K. A syntax-controlled generator of formal languages processors. Institut f~r Angew. Math., Johannes Gutenberg Univ. in Mainz (Sept. 1962).
	5	Robert W. Floyd, A Descriptive Language for Symbol Manipulation, Journal of the ACM (JACM), v.8 n.4, p.579-584, Oct. 1961 [doi>10.1145/321088.321096]
	6	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]
	7	Saul Gorn, Detection of Generative Ambiguities in Context-Free Mechanical Languages, Journal of the ACM (JACM), v.10 n.2, p.196-208, April 1963 [doi>10.1145/321160.321168]
	8	PAUL, M. A general processor for certain formal languages. Symbolic Languages in Data Processing, Proc. 1962 Rome Symposium, Gordon and Breach, New York, 1962.
	9	K. Samelson , F. L. Bauer, Sequential formula translation, Communications of the ACM, v.3 n.2, p.76-83, Feb. 1960 [doi>10.1145/366959.366968]
	10	SCHUTZENBERGER, M. P., AND CHOMSKY, N. The algebraic theory of context-free languages. Computer Programming and Formal Systems, North-Holland, 1963.

CITED BY 33

	David F. Martin, Programming Languages: Boolean matrix methods for the detection of simple precedence grammars, Communications of the ACM, v.11 n.10, p.685-687, Oct. 1968
	Yeu-hsiung Liang, A parsing method on l-1 bounded context parsing, Proceedings of the 18th annual Southeast regional conference, March 24-26, 1980, Tallahassee, Florida
	Robert M. Graham, Bounded context translation, Proceedings of the April 21-23, 1964, spring joint computer conference, April 21-23, 1964, Washington, D.C.
	W. M. McKeeman , J. J. Horning , E. C. Nelson , D. B. Wortman, The XPL compiler generator system, Proceedings of the December 9-11, 1968, fall joint computer conference, part I, December 09-11, 1968, San Francisco, California
	Gérard Terrine, An algorithm generating the decision table of a deterministic bottom up parser for a subset of context free grammars, Proceedings of the third annual ACM symposium on Theory of computing, p.185-205, May 03-05, 1971, Shaker Heights, Ohio, United States
	Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967
	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
	David S. Wise, Domolki's algorithm applied to generalized overlap resolvable grammars, Proceedings of the third annual ACM symposium on Theory of computing, p.171-184, May 03-05, 1971, Shaker Heights, Ohio, United States
	J. J. Horning , W. R. Lalonde, Empirical comparison of LR(k) and precedence parsers, ACM SIGPLAN Notices, v.5 n.11, November 1970
	James N. Gray , Michael A. Harrison, Canonical Precedence Schemes, Journal of the ACM (JACM), v.20 n.2, p.214-234, April 1973
	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
	Stephen H. Unger, A global parser for context-free phrase structure grammars, Communications of the ACM, v.11 n.4, p.240-247, April 1968
	Dennis F. Cudia, The degree hierarchy of undecidable problems of formal grammars, Proceedings of the second annual ACM symposium on Theory of computing, p.10-21, May 04-06, 1970, Northampton, Massachusetts, United States
	Robert C. Berwick , Amy S. Weinberg, Syntactic constraints and efficient parsability, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts
	Tatsuya Hayashi, On the construction of LR(k) analyzers, Proceedings of the 1971 26th annual conference, p.538-553, January 1971
	Jerome A. Feldman, A formal semantics for computer languages and its application in a compiler-compiler, Communications of the ACM, v.9 n.1, p.3-9, Jan. 1966
	Franklin L. Deremer, Generating parsers for BNF grammars, Proceedings of the May 14-16, 1969, spring joint computer conference, May 14-16, 1969, Boston, Massachusetts
	G. V. Cormack, An LR substring parser for noncorrecting syntax error recovery, ACM SIGPLAN Notices, v.24 n.7, p.161-169, July 1989
	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
	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
	Jan Rekers , Wilco Koorn, Substring parsing for arbitrary context-free grammars, ACM SIGPLAN Notices, v.26 n.5, p.59-66, May 1991
	Helmut Richter, Noncorrecting syntax error recovery, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.478-489, July 1985
	David Gries, Use of transition matrices in compiling, Communications of the ACM, v.11 n.1, p.26-34, Jan. 1968
	Kou-Chung Tai, Noncanonical SLR(1) Grammars, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.295-320, Oct. 1979
	Jacques Loeck, An algorithm for the construction of bounded-context parsers, Communications of the ACM, v.13 n.5, p.297-307, May 1970
	Martin Ruckert, Continuous grammars, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.303-310, January 20-22, 1999, San Antonio, Texas, United States
	Doron J. Cohen , C. C. Gotlieb, A List Structure Form of Grammars for Syntactic Analysis, ACM Computing Surveys (CSUR), v.2 n.1, p.65-82, March 1970
	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
	Dennis F. Cudia, General Problems of Formal Grammars, Journal of the ACM (JACM), v.17 n.1, p.31-43, Jan. 1970
	F. L. Bauer, The Cellar Principle of State Transition and Storage Allocation, IEEE Annals of the History of Computing, v.12 n.1, p.41-49, January 1990
	Bruce W. Arden, The role of programming in a Ph.D. computer science program, Communications of the ACM, v.12 n.1, p.31-37, Jan. 1969
	Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968
	William F. Atchison , Samuel D. Conte , John W. Hamblen , Thomas E. Hull , Thomas A. Keenan , William B. Kehl , Edward J. McCluskey , Silvio O. Navarro , Werner C. Rheinboldt , Earl J. Schweppe , William Viavant , David M. Young, Jr., Curriculum 68: Recommendations for academic programs in computer science: a report of the ACM curriculum committee on computer science, Communications of the ACM, v.11 n.3, p.151-197, March 1968