article

Free access

Programming Techniques: Regular expression search algorithm

Author:

Ken ThompsonAuthors Info & Claims

Communications of the ACM, Volume 11, Issue 6

Pages 419 - 422

https://doi.org/10.1145/363347.363387

Published: 01 June 1968 Publication History

PDF eReader

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]

BRZOZOWSKI, J. A. Derivatives of regular expressions. J. ACM 11, 4 (Oct. 1964), 481-494.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[3]

IBM Corp. IBM 7094 principles of operation. File No. 7094-01, Form A22-6703-1.

Google Scholar

[4]

KUNO, S., AND OETTINGER, A. G. Multiple-path syntactic analyzer. Proc. IFIP Congress, Munich, 1962, North-Holland Pub. Co., Amsterdam.

Google Scholar

Cited By

View all

Kwon SShim KJung W(2025)Cardinality Estimation of LIKE Predicate Queries using Deep LearningProceedings of the ACM on Management of Data10.1145/37096703:1(1-26)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709670
Zhang CKappé TNarváez DNaus N(2025)CF-GKAT: Efficient Validation of Control-Flow TransformationsProceedings of the ACM on Programming Languages10.1145/37048579:POPL(600-626)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704857
Varatalu IVeanes MErnits J(2025)RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted LookaroundsProceedings of the ACM on Programming Languages10.1145/37048379:POPL(1-32)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704837
Show More Cited By

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 ...
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, ...
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)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1968

Published in CACM Volume 11, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

706
Total Citations
View Citations
13,036
Total Downloads

Downloads (Last 12 months)2,216
Downloads (Last 6 weeks)314

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kwon SShim KJung W(2025)Cardinality Estimation of LIKE Predicate Queries using Deep LearningProceedings of the ACM on Management of Data10.1145/37096703:1(1-26)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709670
Zhang CKappé TNarváez DNaus N(2025)CF-GKAT: Efficient Validation of Control-Flow TransformationsProceedings of the ACM on Programming Languages10.1145/37048579:POPL(600-626)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704857
Varatalu IVeanes MErnits J(2025)RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted LookaroundsProceedings of the ACM on Programming Languages10.1145/37048379:POPL(1-32)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704837
Somaini ACarloni FAgosta GSantambrogio MConficconi DDoerfert JGrosser TLeather HSadayappan P(2025)Combining MLIR Dialects with Domain-Specific Architecture for Efficient Regular Expression MatchingProceedings of the 23rd ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3696443.3708916(255-270)Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1145/3696443.3708916
Hu DWu Z(2025)An efficient string solver for string constraints with regex-counting and string-lengthJournal of Systems Architecture10.1016/j.sysarc.2025.103340160(103340)Online publication date: Mar-2025
https://doi.org/10.1016/j.sysarc.2025.103340
Chapman JHolzer MWolf P(2025)On Switching Finite State AutomataMachines, Computations, and Universality10.1007/978-3-031-81202-6_3(35-51)Online publication date: 26-Feb-2025
https://doi.org/10.1007/978-3-031-81202-6_3
Wünschiers RWünschiers R(2025)Regular ExpressionsComputational Biology10.1007/978-3-031-70314-0_11(171-186)Online publication date: 19-Feb-2025
https://doi.org/10.1007/978-3-031-70314-0_11
Beurer-Kellner LFischer MVechev MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Guiding LLMs the right wayProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692216(3658-3673)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692216
Zhang CDeStefano ZArun ABonneau JGrubbs PWalfish MVanbever LZhang I(2024)ZombieProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691930(1917-1935)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.5555/3691825.3691930
Davies HNenadic GAlfattni GArguello Casteleiro MAl Moubayed NFarrell SRadford ANoble P(2024)Text mining for disease surveillance in veterinary clinical data: part one, the language of veterinary clinical records and searching for wordsFrontiers in Veterinary Science10.3389/fvets.2024.135223911Online publication date: 23-Jan-2024
https://doi.org/10.3389/fvets.2024.1352239
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

A regular expression matching circuit: Decomposed non-deterministic realization with prefix sharing and multi-character transition

Regular expression containment: coinductive axiomatization and computational interpretation

From regular expressions to smaller NFAs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations