https://dl.acm.org/doi/10.1145/363347.363387 skip to main content ACM Digital Library home ACM home * Advanced Search * Browse * About * + Sign in + Register * * Advanced Search * Journals * Magazines * Proceedings * Books * SIGs * Conferences * People * * More * Search ACM Digital Library[ ] SearchSearch Advanced Search Communications of the ACM * Magazine Home * Online First * Latest Issue * * Archive * Authors * About + CACM Affiliations + ACM Award Winners * More * Home * Magazines * Communications of the ACM * Vol. 11, No. 6 * Programming Techniques: Regular expression search algorithm article Free Access Share on * * * * * Programming Techniques: Regular expression search algorithm * Author: * #Ken Thompson Bell Telphone Labs, Inc., Murray Hill Bell Telphone Labs, Inc., Murray Hill View Profile Authors Info & Claims Communications of the ACMVolume 11Issue 6June 1968pp 419-422https:// doi.org/10.1145/363347.363387 Published:01 June 1968Publication HistoryCheck for updates on crossmark * 643citation * 9,639 * Downloads Metrics Total Citations643 Total Downloads9,639 Last 12 Months1,692 Last 6 weeks172 * Get Citation Alerts New Citation Alert added! This alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited. To manage your alert preferences, click on the button below. Manage my Alerts New Citation Alert! Please log in to your account * Save to Binder Save to Binder [loader-7e6] Create a New Binder Name [ ] + Cancel + Create * Export Citation * Publisher Site * * eReader * PDF Communications of the ACM Volume 11, Issue 6 PreviousArticleNextArticle ACM Digital Library Skip Abstract Section Abstract A method for locating specific character strings embedded in character text is described and an implementation of this method in the form of a compiler is discussed. The compiler accepts a regular expression as source language and produces an IBM 7094 program as object language. The object program then accepts the text to be searched as input and produces a signal every time an embedded string in the text matches the given regular expression. Examples, problems, and solutions are also presented. References 1. 1 BRZOZOWSKI, J. A. Derivatives of regular expressions. J. ACM 11, 4 (Oct. 1964), 481-494. Google ScholarGoogle ScholarDigital LibraryDigital Library 2. 2 KLEENE, S. C. Representation of events in nerve nets and finite automata. In Automata Studies, Ann. Math. Stud. No. 34. Princeton U. Press, Princeton, N.J., 1956, pp. 3-41.Google ScholarGoogle ScholarCross RefCross Ref 3. 3 IBM Corp. IBM 7094 principles of operation. File No. 7094-01, Form A22-6703-1.Google ScholarGoogle Scholar 4. 4 KUNO, S., AND OETTINGER, A. G. Multiple-path syntactic analyzer. Proc. IFIP Congress, Munich, 1962, North-Holland Pub. Co., Amsterdam.Google ScholarGoogle Scholar Cited By View all [loader] Recommendations * A regular expression matching circuit: Decomposed non-deterministic realization with prefix sharing and multi-character transition This paper shows a compact realization of regular expression matching circuits on FPGAs. First, the given regular expression is converted into a non-deterministic finite automaton (NFA) by the modified McNaughton-Yamada method. Second, to reduce the ... Read More * Regular expression containment: coinductive axiomatization and computational interpretation POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages We present a new sound and complete axiomatization of regular expression containment. It consists of the conventional axiomatization of concatenation, alternation, empty set and (the singleton set containing) the empty string as an idempotent semiring, ... Read More * From regular expressions to smaller NFAs Several methods have been developed to construct @l-free automata that represent a regular expression. Among the most widely known are the position automaton (Glushkov), the partial derivatives automaton (Antimirov) and the follow automaton (Ilie and Yu)... Read More Comments Please enable JavaScript to view thecomments powered by Disqus. Login options Check if you have access through your login credentials or your institution to get full access on this article. Sign in Full Access Get this Article * Information * Contributors * Published in cover image Communications of the ACM Communications of the ACM Volume 11, Issue 6 June 1968 130 pages ISSN:0001-0782 EISSN:1557-7317 DOI:10.1145/363347 + Editor: + #Gerard Salton Cornell Univ., Ithaca, NY Issue's Table of Contents Copyright (c) 1968 ACM Sponsors In-Cooperation Publisher Association for Computing Machinery New York, NY, United States Publication History + Published: 1 June 1968 Permissions Request permissions about this article. Request Permissions Check for updates Check for updates on crossmark Author Tags + regular expression + match + search Qualifiers + article Conference Funding Sources * [loader-7e6] Other Metrics View Article Metrics * Bibliometrics * Citations643 * Article Metrics + 643 Total Citations View Citations + 9,639 Total Downloads + Downloads (Last 12 months)1,692 + Downloads (Last 6 weeks)172 Other Metrics View Author Metrics * Cited By View all PDF Format View or Download as a PDF file. PDF eReader View online with eReader. eReader Digital Edition View this article in digital edition. View Digital Edition * Figures * Other * * Share this Publication link https://dl.acm.org/doi/10.1145/363347.363387 Copy Link Share on Social Media Share on * * * * * * * * * 0References * * * Close Figure Viewer Browse AllReturnChange zoom level[ ] Caption View Issue's Table of Contents Export Citations Select Citation format[BibTeX ] * Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download,a status dialog will open to start the export process. The process may takea few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download + Download citation + Copy citation Categories * Journals * Magazines * Books * Proceedings * SIGs * Conferences * Collections * People About * About ACM Digital Library * ACM Digital Library Board * Subscription Information * Author Guidelines * Using ACM Digital Library * All Holdings within the ACM Digital Library * ACM Computing Classification System * Digital Library Accessibility Join * Join ACM * Join SIGs * Subscribe to Publications * Institutions and Libraries Connect * Contact * Facebook * Twitter * Linkedin * Feedback * Bug Report The ACM Digital Library is published by the Association for Computing Machinery. Copyright (c) 2023 ACM, Inc. * Terms of Usage * Privacy Policy * Code of Ethics ACM Digital Library home ACM home About Cookies On This Site We use cookies to ensure that we give you the best experience on our website. Learn more Got it! Your Search Results Download Request We are preparing your search results for download ... We will inform you here when the file is ready. Download now! Your Search Results Download Request Your file of search results citations is now ready. Download now! Your Search Results Download Request Your search export query has expired. Please try again.