“Structural connections” in formal languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

“Structural connections” in formal languages

Full text

Pdf (665 KB)

Source

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

Pages: 67 - 72

Year of Publication: 1964

ISSN:0001-0782

Author

E. T. Irons

Institute for Defense Analyses, Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 11, Citation Count: 7

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

ABSTRACT

This paper defines the concept of “structural connection” in a mechanical language in an attempt to classify various formal languages according to the complexity of parsing structures on strings in the languages. Languages discussed vary in complexity from those with essentially no structure at all to languages which are self-defining. The relationship between some existing recognition techniques for several language classes is examined, as well as implications of language structure on the complexity of automatic recognizers.

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	CHOMSKY, N. On certain formal properties of grammars. Informat. Contr. 2, 137,167.
	2	----. A note on phrase structure grammars. Informat. Contr. 2, 393-395.
	3	PAUL, M. A General Processor for Certain Formal Languages. Gymbalie Languages in Data Processing, Gordon and Breach, London 1962, pp. 65-74.
	4	EICKEL, J., PAUL, M., BAUER, F. L., SAMUELSON, K. "A Syntax Controlled Generator of Formal Language Processors." Inst. fur Ant. Math. Univ. Mainz. (September, 1962).
	5	BACKU8, J. W. The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference. Proc. Internat. Conference on Information Processing, UNESCO, June, 1959, pp. 125-132.
	6	Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
	7	Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]

CITED BY 7

	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
	Jacques Loeck, An algorithm for the construction of bounded-context parsers, Communications of the ACM, v.13 n.5, p.297-307, May 1970
	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
	S. D. Conte , John W. Hamblen , William B. Kehl , Silvio O. Navarro , Werner C. Rheinboldt , David M. Young, Jr. , William F. Atchinson, An undergraduate program in computer science—preliminary recommendations, Communications of the ACM, v.8 n.9, p.543-552, Sept. 1965
	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