✳flâneur — a map of the web's best reading

Implementing Regular Expressions

swtch.com · 492 words · saved by 1 readers

An introduction to using finite automata to implement regular expression matching, and why the standard backtracking implementation is a bad idea. Supporting programs: NFA | DFA | bounded-memory DFA | timing scripts NFAs with submatch tracking: Perl rules | POSIX rules Transliteration of Thompson's code for bytecode machine and x86, by Jan Burgy. “Regular Expression Matching: the Virtual Machine Approach” An introduction to submatch tracking during efficient (non-backtracking) NFA-based regular expression matching. Supporting programs: https://github.com/rsc/re1/ “Regular Expression Matching in the Wild” A tour of RE2, an efficient, production regular expression implementation. Supporting programs: https://github.com/google/re2/ “Regular Expression Matching with a Trigram Index” How Google Code Search worked. Supporting programs: https://github.com/google/codesearch/ “IBM 7094 Cheat Sheet” If you want to read Ken Thompson's original 1968 paper (see below), you'll want to take this with

Implementing Regular Expressions Implementing Regular Expressions Russ Cox rsc@swtch.com This page collects resources about implementing regular expression search efficiently. Articles and Notes " Regular Expression Matching Can Be Simple And Fast " An introduction to using finite automata to implement regular expression matching, and why the standard backtracking implementation is a bad idea. Supporting programs: NFA | DFA | bounded-memory DFA | timing scripts NFAs with submatch tracking: Perl rules | POSIX rules Transliteration of Thompson's code for bytecode machine and x86 , by Jan Burgy.

Explore this link on the map →

related reading