Regular Expression Matching: The Virtual Machine Approach (2009)
The article discusses the implementation of regular expression matching using a virtual machine approach. It outlines how regular expressions can be compiled into bytecode and executed by a virtual machine, allowing for features like submatching. The author presents various strategies for executing regular expressions, emphasizing the flexibility of adding new instructions to enhance functionality.
- ▪Henry Spencer's regular expression library is one of the most widely used bytecode interpreters.
- ▪The article presents two strategies for implementing regular expression matching through a virtual machine.
- ▪Submatching instructions can be added to the virtual machine to enhance its capabilities.
Hacker News (Newest) files mainly under programming. We currently carry 5,306 of its stories.
Story provenance
Source · retrieval · rights · ranking — open for full record
inspect →
Story provenance
Attribution is not the same as permission. This drawer separates discovery metadata, excerpts, WeSearch-generated summaries, reuse status, and whether the publisher receives the visit. Nothing here claims a legal grant the publisher has not made.
Record
| Original publisher | Swtch |
| Canonical URL | https://swtch.com/~rsc/regexp/regexp2.html |
| Publication time | Sat, 30 May 2026 15:08:57 +0000 |
| Retrieval time | 2026-05-30T15:29:38.710Z |
| Last seen | 2026-05-30T15:29:38.710Z |
| Headline source | Publisher (no WeSearch rewrite) |
| Excerpt source | publisher body |
| Excerpt method | First ~120 words (~800 chars) of extracted publisher body, fair-use limited. |
| Summary | WeSearch · cerebras-chat (WeSearch summarizer) |
| Summary source text | contentText |
| Citation coverage | Summary is a WeSearch-generated derivative; primary citation is the original publisher URL. |
| Cluster | CIkp4TfIGNwG |
| Cluster logic | Grouped by semantic title/content similarity across sources within a rolling window. Same-publisher template collisions are excluded from coverage comparison. |
| Ranking reason | Story pages are not engagement-ranked. Hub feeds use recency, with optional source-diversified chronological ordering (cap consecutive stories per source). No personalized ranking. |
| Publisher visit | Yes — open original |
| Substitutes article? | No — link-out required for full text |
Rights status (four layers)
WeSearch handling by dimension
| Indexing | May the item be indexed (stored, ranked, made findable)? | Allowed |
| Snippet | May a short excerpt of the publisher's text be shown? | Allowed |
| AI summary | May WeSearch generate its own short summary of the article? | Limited |
| Retrieval / RAG | May the content be exposed for third-party retrieval-augmented generation? | Not asserted |
| Model training | May the content be used to train AI models? | Not asserted |
| Commercial reuse | May the content be reused commercially? | Not permitted |
Basis: Derived from the published RSS/Atom feed. Contact: [email protected]. Reviewed: 2026-07-24.
Opening excerpt (first ~120 words) tap to expand
Regular Expression Matching: the Virtual Machine Approach Russ Cox [email protected] December 2009 Introduction Name the most widely used bytecode interpreter or virtual machine. Sun's JVM? Adobe's Flash? .NET and Mono? Perl? Python? PHP? These are all certainly popular, but there's one more widely used than all those combined. That bytecode interpreter is Henry Spencer's regular expression library and its many descendants. The first article in this series described the two main strategies for implementing regular expression matching: the worst-case linear-time NFA- and DFA-based strategies used in awk and egrep (and now most greps), and the worst-case exponential-time backtracking strategy used almost everywhere else, including ed, sed, Perl, PCRE, and Python.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at Swtch.
Discussion
0 commentsMore from Swtch
.jpg&w=320)