A theory of discrete patterns and their implementation in SNOBOL4

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A theory of discrete patterns and their implementation in SNOBOL4

Full text

Pdf (868 KB)

Source

Communications of the ACM archive
Volume 16 , Issue 2 (February 1973) table of contents

Pages: 91 - 100

Year of Publication: 1973

ISSN:0001-0782

Author

J. F. Gimpel

Bell Telephone Labs, Holmdel, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

The notion of a discrete pattern is formalized and certain properties deduced. A pattern is shown to be a generalization of a formal language. Algorithms for implementing the kinds of patterns in SNOBOL4 are given. The general approach is to create, in-so-far as possible, a bottom-up parse from a top-down specification.

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. Three models for the description of language. PGIT 2 (Mar. 1956), 113-124.
	2	Christensen, C. AMBIT/2 (programming language). Applied Data Research, Wakefield, Mass., 1970.
	3	Dewar, R.B. SPITBOL-version 2.0. SNOBOL4 Document s4D23, Illinois Inst. of Tech., Chicago, 1971.
	4	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]
	5	Floyd, R.W. The syntax of programming languages. IEEE Trans. EC-13 (Aug. 1964), 346-353.
	6	James F. Gimpel, Blocks—a new datatype for SNOBOL4, Communications of the ACM, v.15 n.6, p.438-447, June 1972 [doi>10.1145/361405.361410]
	7	Gimpel, J.F. The theory and implementation of pattern matching in SNOBOL4 and other programming languages. SNOBOL4 doc. S4D24, Bell Telephone Laboratories, Holmdel, N.J., 1971.
	8	David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
	9	Griswold, R.E., and Polonsky, I.P. String pattern matching in the programming language SNOBOL. Internal Memo., Bell Telephone Laboratories, Holmdel, N.J., 1964.
	10	Ralph E Griswold, The SNOBOL4 programming language, Bell Telephone Laboratories, 1968
	11	Harrison, M.C. Data-Structures and Programming. Courant Institute of Math. Sciences, New York, 1970, p. 289.
	12	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	13	McClure, R.M. TMG-A syntax directed compiler. Proc. ACM, 20th Nat. Conf., 1965, pp. 252-274.
	14	Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM, v.11 n.6, p.419-422, June 1968 [doi>10.1145/363347.363387]
	15	Thompson, K. QED-A text editor. (To be published.) Internal Memo., Bell Telephone Laboratories, Murray Hill, N.J.
	16	Yngve, V.H. A programming language for mechanical translation. Mech. Trans. 4 (Dec. 1957), 59-65.

CITED BY 14

	J. Nevil Brownlee, An Algol-based implementation of SNOBOL4 patterns, Communications of the ACM, v.20 n.7, p.527-529, July 1977
	Ralph E. Griswold , David R. Hanson, An Alternative to the Use of Patterns in String Processing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.153-172, April 1980
	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975
	Frederick C. Druseikis , John N. Doyle, A procedural approach to pattern matching in SNOBOL4, Proceedings of the 1974 annual conference, p.311-317, January 1974
	Ralph E. Griswold, Extensible pattern matching in SNOBOL4, Proceedings of the 1975 annual conference, p.248-252, January 1975
	George E. Rossmann , Louise H. Jones, Functional memory-based dynamic microprocessors for higher level languages, ACM SIGPLAN Notices, v.9 n.8, p.37-65, August 1974
	Ralph E. Griswold, String analysis and synthesis in SL5, Proceedings of the annual conference, p.410-414, October 20-22, 1976, Houston, Texas, United States
	P. Raulefs , J. Siekmann , P. Szabó , E. Unvericht, A short survey on the state of the art in matching and unification problems, ACM SIGSAM Bulletin, v.13 n.2, p.14-20, May 1979
	Stefan M. Silverston, A note on pattern matching under Quickscan in SNOBOL4, ACM SIGPLAN Notices, v.12 n.10, p.70-74, October 1977
	K. C. Liu , A. C. Fleck, String pattern matching in polynomial time, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.222-225, January 29-31, 1979, San Antonio, Texas
	Ralph E. Griswold, A history of the SNOBOL programming languages, ACM SIGPLAN Notices, v.13 n.8, p.275-308, August 1978
	R. D. Tennent, Mathematical semantics of SNOBOL4, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.95-107, October 01-03, 1973, Boston, Massachusetts
	Glenn F. Stewart, An algebraic model for string patterns, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.167-184, January 20-22, 1975, Palo Alto, California
	Ralph E. Griswold, A history of the SNOBOL programming languages, History of programming languages I, ACM Press, New York, NY, 1978

INDEX TERMS

Keywords:
SNOBOL4, parsing, pattern implementation, pattern matching, pattern theory, patterns, string processing

Collaborative Colleagues:

J. F. Gimpel: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player