http://lionet.livejournal.com/68807.html?style=mine

Как известно, секрет правильного приготовления движков по выполнению регулярных выражений был когда-то промышленностью изобретён (grep, awk), утерян (Perl, Python, PHP, Ruby), и изобретён вновь.



Проект Google Re2 (C++) — успешная попытка [вос]создать промышленный regex движок, свободный от экспоненциальной зависимости от входных данных. Этот проект, выполненный Рассом Коксом (Russ Cox), дал возможность гуглу эффективно выполнять поиск по регулярным выражениям в программном коде, найденном гуглом в интернете. В качестве ценнейшего артефакта были порождены три статьи про построение движков регулярок, давая интересный исторический контекст и описание эффективной имплементации.
<...>

И оттуда по ссылкам — код на языках народов мира.
На питоне, например (с движущимися картинками)
http://morepypy.blogspot.com/2010/05/efficient-and-elegant-regular.html