Programming Techniques: Regular expression search algorithm

1968/06/01 by Thompson Ken · 8 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Character (mathematics) #Character encoding #Compiler #Computer science #Expression (computer science) #IBM #Mathematics #Natural Language Processing Techniques #Object (grammar) #Programming language #Regular expression #String (physics) #Theoretical computer science #semigroups and automata theory

paper · pdf · doi:10.1145/363347.363387

openalex publication_date 1968/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

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.

Citations

• Derivatives of Regular Expressions

Cited by

• Selective Memoization for Efficient Backtracking Regular Expression Matching
• PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities
• Localising Stochasticity in Weighted Automata
• Fast text searching for regular expressions or automaton searching on tries
• Linear Time Subsequence and Supersequence Regex Matching
• A general framework for the derivation of regular expressions
• Just-in-time compilation [wikipedia]
• Regular expression [wikipedia]