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

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
Khashaev A(2024)On the Cardinality Computation Problem for Regular Languages over Symmetric GroupsMoscow University Computational Mathematics and Cybernetics10.3103/S027864192470007948:2(130-136)Online publication date: 11-Jun-2024
https://doi.org/10.3103/S0278641924700079
Gou XYe XZou LYu J(2024)LM-SRPQ: Efficiently Answering Regular Path Query in Streaming GraphsProceedings of the VLDB Endowment10.14778/3641204.364121417:5(1047-1059)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.14778/3641204.3641214
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

695
Total Citations
View Citations
12,339
Total Downloads

Downloads (Last 12 months)2,021
Downloads (Last 6 weeks)395

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Khashaev A(2024)On the Cardinality Computation Problem for Regular Languages over Symmetric GroupsMoscow University Computational Mathematics and Cybernetics10.3103/S027864192470007948:2(130-136)Online publication date: 11-Jun-2024
https://doi.org/10.3103/S0278641924700079
Gou XYe XZou LYu J(2024)LM-SRPQ: Efficiently Answering Regular Path Query in Streaming GraphsProceedings of the VLDB Endowment10.14778/3641204.364121417:5(1047-1059)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.14778/3641204.3641214
Le Glaunec AKong LMamouras K(2024)HybridSA: GPU Acceleration of Multi-pattern Regex Matching using Bit ParallelismProceedings of the ACM on Programming Languages10.1145/36897718:OOPSLA2(1699-1728)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689771
Barrière APit-Claudel C(2024)Linear Matching of JavaScript Regular ExpressionsProceedings of the ACM on Programming Languages10.1145/36564318:PLDI(1336-1360)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656431
Xu XYuan YKincaid ZKrishnamurthy AMahajan RWalker DZhai ESekar VYu MSeneviratne AVeitch D(2024)Relational Network VerificationProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672238(213-227)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672238
David CFrancis NMarsault V(2024)Distinct Shortest Walk Enumeration for RPQsProceedings of the ACM on Management of Data10.1145/36516012:2(1-22)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651601
Ulus DFerrère TAsarin ENickovic DMaler O(2024)Elements of Timed Pattern MatchingACM Transactions on Embedded Computing Systems10.1145/364511423:4(1-45)Online publication date: 10-Feb-2024
https://dl.acm.org/doi/10.1145/3645114
Zhang SHe ZJing YZhang KWang X(2024)MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming GraphsProceedings of the ACM on Management of Data10.1145/36392602:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639260
Mamouras KChattopadhyay A(2024)Efficient Matching of Regular Expressions with Lookaround AssertionsProceedings of the ACM on Programming Languages10.1145/36329348:POPL(2761-2791)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632934
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

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations